移动自组织网络-课件.ppt

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 Cont

2、ents(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 mobile ho

3、st 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 networks

4、)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 applicationsnMesh net

5、worksnPeople-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 topologyCharacteristicsUnit Disk GraphFigu

6、re 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 recovery(search-and-r

7、escue)ApplicationsApplicationsnMobility management nAddressing and routing*nLocation trackingnAbsolute vs.Relative,GPSnNetwork managementnMerge and splitnResource managementnNetworks resource allocation and energy efficiencynQoS management*nDynamic advance reservation and adaptive error control tech

8、niquesMajor IssuesnMAC protocols*nContention vs.contention-freenApplications and middlewarenMeasurement and experimentationnSecurity*nAuthentication,encryption,anonymity,and intrusion detectionnError control and failurenError correction and retransmission,deployment of back-up systemsnNetwork coding

9、nReduce 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 procedures to allow the efficien

10、t use of a shared medium.Contention vs.contention-free Sender-initiated vs.receiver-initiatedWireless MAC:Major IssuesnDistributed operationsnSynchronizationnHidden terminalsnExposed terminalsnThroughputnAccess delaynFairnessnReal-time trafficnResource reservationnAbility to measure resource availab

11、ilitynPower 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 MACnCarrier Sense Multiple Access(CSMA):listen

12、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 protocolsnBit-map protocol:each contention period consist

13、s 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 receiving node.Packet collisions.nExposed Node Pr

14、oblem 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(Busy Tone Multiple Access)DBTMA(Dual BTMA)nReceiver-initiate

15、d 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 issueSample collisionnRTS-CTS problem 1Sample collisionRTS-CST problem 2

16、MACAW(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)Separate control and data(busy tone)Nodes sense data carry also send busy tone

17、 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 with Reduced Handshake(MARCH)PAMAS(C.S.Raghavendra)Power-Aware Multi-Access Protocol with S

18、ignaling(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,Data,and AcknDirectional antennas DO(sender:omni(O)and receiver:directional(D)Other models:OO,OD,and DDOther

19、s(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 transmission power or the packet length Link Diversity:Multi-output link diversity and multi-input link diversityPower Sa

20、ving(Y.C.Tseng)Tsengs Power-saving Protocols:Use periodic active window to discover neighborsnOverlapping Awake IntervalsnWake-up PredictionPower SavingnDominating-Awake-Interval ProtocolPower SavingnPeriodically-Fully-Awake-IntervalPower SavingnQuorum-Based ProtocolsIEEE 802.11nTwo operational mode

21、s 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.11nTwo operational modes Infrastructure-based Infrastructureless or ad hocnTwo

22、 types of service at the MAC layer Contention-free service by Distributed Coordination Function:DCF Contention-free service by Point Coordination Function:PCFIEEE 802-11nRTS-CTS handshakeIEEE 802.11nRTS-CTS handshake RTS(request to send)CTS(clear to send)Data trasmission Ack nOther items Network All

23、ocation Vector(NAV)Distributed InterFrame Space(DIFS)Short InterFrame Space(SIFS)Backoff timeIEEE 802.11 RTS-CTS:contention Data transmissionL contention-free NAV setup cannot work properly when there are collisions All packets:RTS,CTS,Data,Ack are subject to collisions SIFS DIFS to increase the pri

24、ority Backoff time:an integer from(0,CW-1),where CW(contention window)is doubled at each retransmissionRouting in Ad Hoc NetworksTypes:(n:network size)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

25、 special type of gathering(with simple data processing at intermediate nodes)Routing in Ad Hoc NetworksQualitative properties:nDistributed operationnLoop-freedomnDemand-based operationnProactive operationnSecuritynSleep period operationnUnidirectional link supportRouting in Ad Hoc NetworksQuantitati

26、ve metrics:nEnd-to-end data throughput and delaynRoute acquisition timenPercentage out-of-order deliverynEfficiencyBasic Routing Strategies in InternetSource Routing vs.Distributed RoutingFigure 2:A sample source routing Figure 3:A sample distributed routingClassificationnProactive vs.reactivenproac

27、tive:continuously evaluate network connectivity nreactive:invoke a route determination procedure on-demand.nRight balance between proactive and reactivenFlat vs.hierarchicalSample ProtocolsnProactive ProtocolsnDestination sequenced distance vector(DSDV)nReactive ProtocolsnDynamic source routing(DSR)

28、nAd hoc on-demand distance vector routing(AODV)nTemporally ordered routing algorithms(TORA)Sample ProtocolsnHybrid:nZone routingnHierarchicalnCluster-basednConnected-dominating-set-basedProactive:DSDVnBased on Bellman-Ford routing algorithmsnEnhanced with freedom from loops.nEnhanced with differenti

29、ation of stale routes from new ones by sequence numbers.ReactiveThree stepsnRoute discoverynData forwardingnRoute maintenanceDSRnThere are no periodic routing advertisement messages(thereby reducing network bandwidth overhead).nEach host maintains a route cache:source routes that it has learned.nIf

30、a route is not found from route cache,the source attempts to discover one using route discovery.nRoute maintenance 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

31、(issued from different destinations)are used to avoid loopingnThe node should respond(ROUTE_REPLY)a request(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

32、 with destination as the sink:nEach node has a height metric.nA directed link always points to a node with 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:dec

33、entralizednMultiple pathsProactive:Route MaintenancenSource routing vs.distributed routing.nGlobal 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

34、 all its incoming links.n Partial reversalnEvery node u other than the destination keeps a list 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

35、do not appear on its list,and empties the list.If no such v exists,node u reverses the 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

36、 the nodes within a given number of hops.nEach host maintains routing information 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

37、bus routingGraph-theoretic DefinitionA set in G(V,E)is dominating if all the 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 mob

38、ile hosts.Existing ApproachesnGraph theory community:nBounds on the domination 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,Da

39、s,and Bharghavan,2019).nQuasi-global:spanning-tree-based(Wan,Alzoubi,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 selecte

40、d as the root and colored black.All the neighbors 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 domina

41、ting set)Figure 7:MCDS as an approximation 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

42、 based on their positions in the order 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.Span

43、ning-tree-based(Contd.)black nodes=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 blac

44、k.nAll its neighbors 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=CDSFig

45、ure 9: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 desi

46、red 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 networkD

47、ominating-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,which is eithe

48、r 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),then unmark v.nRul

49、e 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:dominating node and absorbant nodeFigure 1

50、5:Dominating and absorbant nodesDirected Networks(Contd.)Finding a subset that is both dominating and absorbant(Wu,IEEE TPDS 2019).Figure 16:An absorbant set and a dominating setMobility ManagementnUpdate/re-calculationnon/offnmovement recognizing a new link recognizing a broken linknLocalized maint