1、Table of ContentsnIntroduction nInfrastructured networks nHandoffnlocation management (mobile IP)nchannel assignmentTable of Contents (contd.)nInfrastructureless networksnWireless MAC (IEEE 802.11 and Bluetooth)nAd Hoc Routing ProtocolsnMulticasting and BroadcastingnSecuritynNetwork CodingTable of C
2、ontents (contd.)nInfrastructureless networks (contd.)nPower OptimizationnApplicationsnSensor networks and indoor wireless environmentsnPervasive computing nSocial networksnSample on-going projectsAd Hoc Wireless Networks (Infrastructureless networks)nAn ad hoc network is a collection of wireless mob
3、ile host forming a temporary network without the aid of any centralized administration or standard support services regularly available on the wide area network to which the hosts may normally be connected (Johnson and Maltz)Ad Hoc Wireless Networks (Infrastructureless networks)nManet (mobile ad hoc
4、 networks) nMobile distributed multihop wireless networks nTemporary in nature nNo base station and rapidly deployable nNeighborhood awareness nMultiple-hop communication nUnit disk graph: host connection based on geographical distanceSample Ad Hoc NetworksnSensor networksnIndoor wireless applicatio
5、nsnMesh networksnPeople-based networksn“small world” that are very large graphs that tend to be sparse, clustered, and have a small diameter.n“six degree of separation”nSelf-organizing: without centralized control nScarce resources: bandwidth and batteries nDynamic network topologyCharacteristicsUni
6、t Disk GraphFigure 1: A simple ad hoc wireless network of five wireless mobile hosts.nDefense industry (battlefield)nLaw enforcement nAcademic institutions (conference and meeting)nPersonal area networks and Bluetooth nHome networking nEmbedding computing applications nHealth facilities nDisaster re
7、covery (search-and-rescue)ApplicationsApplicationsnMobility management nAddressing and routing*nLocation trackingnAbsolute vs. Relative, GPSnNetwork managementnMerge and splitnResource managementnNetworks resource allocation and energy efficiencynQoS management*nDynamic advance reservation and adapt
8、ive error control techniquesMajor IssuesnMAC protocols*nContention vs. contention-freenApplications and middlewarenMeasurement and experimentationnSecurity*nAuthentication, encryption, anonymity, and intrusion detectionnError control and failurenError correction and retransmission, deployment of bac
9、k-up systemsnNetwork codingnReduce number of transmissionsMajor Issues (Contd.)Issues to be CoverednWireless Media Access Protocols (MAC) nAd Hoc Routing ProtocolsnMulticasting and BroadcastingnPower OptimizationnSecuritynNetwork CodingWireless MACnA MAC (Media Access Protocol) is a set of rules or
10、procedures to allow the efficient use of a shared medium. Contention vs. contention-free Sender-initiated vs. receiver-initiatedWireless MAC: Major IssuesnDistributed operationsnSynchronizationnHidden terminalsnExposed terminalsnThroughputnAccess delaynFairnessnReal-time trafficnResource reservation
11、nAbility to measure resource availabilitynPower and rate controlnDirectional antennasWireless MAC Contention-basednALOHA: no collision avoidancenPure: transmitted at arbitrary timenSlotted: transmitted at start of a time slotnp-persistent: slotted and transmitted with a probability pWireless MACnCar
12、rier Sense Multiple Access (CSMA): listen to determine whether there is activity on the channelnPersistent: continuously listensnNonpersistent: waits a random amount of time before re-testingnp-persistent: slotted and transmit when idle with a probability of pWireless MACContention-free protocolsnBi
13、t-map protocol: each contention period consists of N slots.nBinary countdown: use binary station address in bidding.HybridnMixed contention-free with contentionWireless MACnHidden Terminal Problem Two nodes, hidden from one another (out of transmission range), attempt to send information to the same
14、 receiving node. Packet collisions.nExposed Node Problem A node is inhibited from transmitting to other nodes on overhearing a packet transmission. Wasted bandwidth.Wireless MACnSender-initiated MACA (Multiple Access with Collision Avoidance) (RTS-CTS-data) MACAW (MACA with Acknowledgement) BTMA (Bu
15、sy Tone Multiple Access) DBTMA (Dual BTMA)nReceiver-initiated MACA-BI (By Invitation)nOther extensions March and PAMASMACA (P. Khan)nNo carrier-sensing for channelnTwo special signals RTS: request-to-send CTS: clear-to-sendnPacket lost Binary exponential back-upnOvercomes the hidden terminal issueSa
16、mple collisionnRTS-CTS problem 1Sample collisionRTS-CST problem 2MACAW (S. Shenker and L. Zhang)nRTS+CTS+DS+DATA+ACK DS: data-sending (avoid unnecessary back-off counter build up)nRRTS: request-for-request-to-sendnDistinct back-off counter per flowDBTMA (Z. Haas)nBTMA (Busy Tone Multiple Access) Sep
17、arate control and data (busy tone) Nodes sense data carry also send busy tone Too restrictive (Disable two-hop neighbors)nDual BTMA RTS Receive busy tone + CTS Transmit busy tone + DataMACA-BI (M. Gerla)nReceiver-initiated RTR: ready-to-receive Data: data transmissionMARCH (C. T. Toh)Media Access wi
18、th Reduced Handshake(MARCH)PAMAS (C. S. Raghavendra)Power-Aware Multi-Access Protocol with Signaling (PAMAS)nTemp. reducing transmitter rangenTurn off Others (N. H. Vaidya)nDifferent ranges TR: transmission range, IR: interference range, SR: sensing range (TR IR SR) Different ranges for RTS, CTS, Da
19、ta, and AcknDirectional antennas DO (sender: omni (O) and receiver: directional (D) Other models: OO, OD, and DDOthers (M. Fang)nImpact of MAC on communication Intra-flow contention Inter-flow contentionnPhysical layer related issues Rate-adaptation (varying the data rate) Other options: varying the
20、 transmission power or the packet length Link Diversity: Multi-output link diversity and multi-input link diversityPower Saving (Y. C. Tseng)Tsengs Power-saving Protocols:Use periodic active window to discover neighborsnOverlapping Awake IntervalsnWake-up PredictionPower SavingnDominating-Awake-Inte
21、rval ProtocolPower SavingnPeriodically-Fully-Awake-IntervalPower SavingnQuorum-Based ProtocolsIEEE 802.11nTwo operational modes Infrastructure-based Infrastructureless or ad hocnTwo types of service at the MAC layer Contention-free service by Distributed Coordination Function: DCF Contention-free se
22、rvice by Point Coordination Function: PCFIEEE 802.11nTwo operational modes Infrastructure-based Infrastructureless or ad hocnTwo types of service at the MAC layer Contention-free service by Distributed Coordination Function: DCF Contention-free service by Point Coordination Function: PCFIEEE 802-11n
23、RTS-CTS handshakeIEEE 802.11nRTS-CTS handshake RTS (request to send) CTS (clear to send) Data trasmission Ack nOther items Network Allocation Vector (NAV) Distributed InterFrame Space (DIFS) Short InterFrame Space (SIFS) Backoff timeIEEE 802.11 RTS-CTS: contention Data transmissionL contention-free
24、NAV setup cannot work properly when there are collisions All packets: RTS, CTS, Data, Ack are subject to collisions SIFS DIFS to increase the priority Backoff time: an integer from (0, CW-1), where CW (contention window) is doubled at each retransmissionRouting in Ad Hoc NetworksTypes: (n: network s
25、ize)nUnicasting: (1, 1) = (source, destination)nMulticasting: (1, k), 1 k nnBroadcasting: (1, n)nGeocasting: (1, k in a region)nGossip: (n, n)nGathering: (k, 1)nFusion: a special type of gathering (with simple data processing at intermediate nodes)Routing in Ad Hoc NetworksQualitative properties:nDi
26、stributed operationnLoop-freedomnDemand-based operationnProactive operationnSecuritynSleep period operationnUnidirectional link supportRouting in Ad Hoc NetworksQuantitative metrics:nEnd-to-end data throughput and delaynRoute acquisition timenPercentage out-of-order deliverynEfficiencyBasic Routing
27、Strategies in InternetSource Routing vs. Distributed RoutingFigure 2: A sample source routing Figure 3: A sample distributed routingClassificationnProactive vs. reactivenproactive: continuously evaluate network connectivity nreactive: invoke a route determination procedure on-demand.nRight balance b
28、etween proactive and reactivenFlat vs. hierarchicalSample ProtocolsnProactive ProtocolsnDestination sequenced distance vector (DSDV)nReactive ProtocolsnDynamic source routing (DSR)nAd hoc on-demand distance vector routing (AODV)nTemporally ordered routing algorithms (TORA)Sample ProtocolsnHybrid: nZ
29、one routingnHierarchicalnCluster-basednConnected-dominating-set-basedProactive: DSDVnBased on Bellman-Ford routing algorithmsnEnhanced with freedom from loops.nEnhanced with differentiation of stale routes from new ones by sequence numbers.ReactiveThree stepsnRoute discoverynData forwardingnRoute ma
30、intenanceDSRnThere are no periodic routing advertisement messages (thereby reducing network bandwidth overhead).nEach host maintains a route cache: source routes that it has learned .nIf a route is not found from route cache, the source attempts to discover one using route discovery.nRoute maintenan
31、ce monitors the correct operation of a route in use.DSR Routing (Contd.)A sample DSR route discoveryAODVnCombination of DSR and DSDVnRouting table is constructed on demand.nSequence numbers (issued from different destinations) are used to avoid loopingnThe node should respond (ROUTE_REPLY) a request
32、 (ROUTE_REQ) ifnIt is the destination nodenAn intermediate node with a route of a destination sequence number no less than that in the request packet.TORAnFor each destination, a DAG is maintained with destination as the sink:nEach node has a height metric.nA directed link always points to a node wi
33、th a lower height metric.nTo send a packet, a host forwards the packet to any neighbor with a lower metric.Proactive: Data ForwardingnSource routing: centralized at the sourcenDistributed routing: decentralizednMultiple pathsProactive: Route MaintenancenSource routing vs. distributed routing.nGlobal
34、 re-construction vs. local fixnSingle path vs. multiple pathTORA: route maintenancenFull reversalnAt each iteration each node other than the destination that has no outgoing link reverses the directions of all its incoming links. n Partial reversalnEvery node u other than the destination keeps a lis
35、t of its neighboring nodes v that have reversed the direction of the corresponding link (u, v)nAt each iteration each node u that has no outgoing link reverses the directions of the links (u; v) for all v which do not appear on its list, and empties the list. If no such v exists, node u reverses the
36、 directions of all incoming links and empties the list.TORA: route maintenance nTrade-offs: network capacity usage in proactive approaches and the long delay in reactive approaches.nA routing zone (for a host) includes the nodes within a given number of hops.nEach host maintains routing information
37、only to nodes within its routing zone.nInformation outside the routing zone is obtained through on demand.Hybrid:Zone-based Routing Zone-based Routing (Contd.)Figure 5: Zone routingHiearchical: Domination-set-basedSchool bus routingGraph-theoretic DefinitionA set in G(V, E) is dominating if all the
38、nodes in the system are either in the set or neighbors of nodes in the set.Five-Queen Problem (1850s)Desirable FeaturesnSimple and quick nConnected dominating setFigure 6: A simple ad hoc wireless network of five wireless mobile hosts.Existing ApproachesnGraph theory community:nBounds on the dominat
39、ion number (Haynes, Hedetniemi, and Slater, 2019).nSpecial classes of graph for which the domination problem can be solved in polynomial time.Existing Approaches (Contd.)nAd hoc wireless network community:nGlobal: MCDS (Sivakumar, Das, and Bharghavan, 2019).nQuasi-global: spanning-tree-based (Wan, A
40、lzoubi, and Frieder, 2019).nQuasi-local: cluster-based (Lin and Gerla, 2019).nLocal: marking process (Wu and Li, 2019).MCDS (Sivakumar, Das, and Bharghavan, UIUC)nAll nodes are initially colored white.nThe node with the maximum node degree is selected as the root and colored black. All the neighbors
41、 of the root are colored gray.nSelect a gray node that has the maximum white neighbors. The gray node is colored black and its white neighbors are marked gray.nRepeat step (3) until there is no more white node.MCDS (Contd.)black nodes = CDS (connected dominating set)Figure 7: MCDS as an approximatio
42、n of CDSSpanning-tree-based (Wan, Alzoubi, and Frieder, IIT)nA spanning tree rooted at v (selected through an election process) is first constructed.nNodes are labeled according to a topological sorting order of the tree.Spanning-tree-based (Contd.)nNodes are marked based on their positions in the o
43、rder starting from root v.nAll nodes are white initially. nV is marked black and all nodes are labeled black unless there is a black neighbor.nEach black node (except root v) selects a neighbor with the largest label but smaller than its own label and mark it gray.Spanning-tree-based (Contd.)black n
44、odes = DS black nodes + gray nodes = CDSFigure 8: selecting CDS in a spanning treeCluster-based (Lee and Gerla, UCLA)nAll nodes are initially white.nWhen a white node finds itself having the lowest id among all its white neighbors, it becomes a cluster head and colors itself black.nAll its neighbors
45、 join in the cluster and change their colors to gray.Cluster-based (Contd.)nRepeat steps (1) and (2) until there is no white node left. nSpecial gray nodes: gray nodes that have two neighbors in different clusters.Cluster-based (Contd.)black nodes = DS black nodes + special gray nodes = CDSFigure 9:
46、 sequential propagation in the cluster-based approach.Localized AlgorithmsnProcessors (hosts) only interact with others in a restricted vicinity.nEach processor performs exceedingly simple tasks (such as maintaining and propagating information markers).nCollectively these processors achieve a desire
47、d global objective. nThere is no sequential propagation of information.Marking Process (Wu and Li, 2019)nA node is marked true if it has two unconnected neighbors. nA set of marked nodes (gateways nodes) V form a connected dominating set.Marking Process (Contd.) Figure 10: A sample ad hoc wireless n
48、etworkDominating-set-based Routing nIf the source is not a gateway host, it forwards packets to a source gateway neighbor.nThis source gateway acts as a new source to route packets in the induced graph generated from the connected dominating set.nEventually, packets reach a destination gateway, whic
49、h is either the destination host itself or a gateway of the destination host.Dominating Set ReductionnReduce the size of the dominating set. nRole of gateway/non-gateway is rotated.Dominating Set Reduction (Contd.)N v = N (v) U v is a closed neighbor set of vnRule 1: If N v N u in G and id(v) id(u),
50、 then unmark v.nRule 2: If N (v) N (u) U N (w) in G and id(v) = minid(v), id(u), id(w), then unmark v.Dominating Set Reduction (Contd.)Figure 12: two sample examplesExample Figure 13: (a) Dominating set from the marking process (b) Dominating set after dominating set reductionDirected Networks: domi
