移动自组织网络

JieWuDepartmentofComputerandInformationSciencesTempleUniversityPhiladelphia,PA19122CIS9590AdHocNetworks(PartII)第一页，共一百一十三页。TableofContentsIntroductionInfrastructurednetworksHandofflocationmanagement(mobileIP)channelassignment第二页，共一百一十三页。TableofContents(cont’d.)InfrastructurelessnetworksWirelessMAC(IEEE802.11andBluetooth)AdHocRoutingProtocolsMulticastingandBroadcastingSecurityNetworkCoding第三页，共一百一十三页。TableofContents(cont’d.)Infrastructurelessnetworks(cont’d.)PowerOptimizationApplicationsSensornetworksandindoorwirelessenvironmentsPervasivecomputingSocialnetworksSampleon-goingprojects第四页，共一百一十三页。AdHocWirelessNetworks(Infrastructurelessnetworks)Anadhocnetworkisacollectionofwirelessmobilehostformingatemporarynetworkwithouttheaidofanycentralizedadministrationorstandardsupportservicesregularlyavailableonthewideareanetworktowhichthehostsmaynormallybeconnected(JohnsonandMaltz)第五页，共一百一十三页。AdHocWirelessNetworks(Infrastructurelessnetworks)Manet

(mobileadhocnetworks)

MobiledistributedmultihopwirelessnetworksTemporaryinnatureNobasestationandrapidlydeployableNeighborhoodawarenessMultiple-hopcommunicationUnitdiskgraph:hostconnectionbasedongeographicaldistance第六页，共一百一十三页。SampleAdHocNetworksSensornetworksIndoorwirelessapplicationsMeshnetworksPeople-basednetworks“smallworld”thatareverylargegraphsthattendtobesparse,clustered,andhaveasmalldiameter.“sixdegreeofseparation”第七页，共一百一十三页。Self-organizing:withoutcentralizedcontrolScarceresources:bandwidthandbatteriesDynamicnetworktopologyCharacteristics第八页，共一百一十三页。UnitDiskGraphFigure1:Asimpleadhocwirelessnetworkoffivewirelessmobilehosts.第九页，共一百一十三页。Defenseindustry(battlefield)LawenforcementAcademicinstitutions(conferenceandmeeting)PersonalareanetworksandBluetoothHomenetworkingEmbeddingcomputingapplications

HealthfacilitiesDisasterrecovery(search-and-rescue)ApplicationsApplications第十页，共一百一十三页。MobilitymanagementAddressingandrouting*LocationtrackingAbsolutevs.Relative,GPSNetworkmanagementMergeandsplitResourcemanagementNetworksresourceallocationandenergyefficiencyQoSmanagement*DynamicadvancereservationandadaptiveerrorcontroltechniquesMajorIssues第十一页，共一百一十三页。MACprotocols*Contentionvs.contention-freeApplicationsandmiddlewareMeasurementandexperimentationSecurity*Authentication,encryption,anonymity,andintrusiondetectionErrorcontrolandfailureErrorcorrectionandretransmission,deploymentofback-upsystemsNetworkcodingReducenumberoftransmissionsMajorIssues(Cont’d.)第十二页，共一百一十三页。IssuestobeCoveredWirelessMediaAccessProtocols(MAC)AdHocRoutingProtocolsMulticastingandBroadcastingPowerOptimizationSecurityNetworkCoding第十三页，共一百一十三页。WirelessMACAMAC(MediaAccessProtocol)isasetofrulesorprocedurestoallowtheefficientuseofasharedmedium.Contentionvs.contention-freeSender-initiatedvs.receiver-initiated第十四页，共一百一十三页。WirelessMAC:MajorIssuesDistributedoperationsSynchronizationHiddenterminalsExposedterminalsThroughputAccessdelayFairnessReal-timetrafficResourcereservationAbilitytomeasureresourceavailabilityPowerandratecontrolDirectionalantennas第十五页，共一百一十三页。WirelessMACContention-basedALOHA:nocollisionavoidancePure:transmittedatarbitrarytimeSlotted:transmittedatstartofatimeslotp-persistent:slottedandtransmittedwithaprobabilityp第十六页，共一百一十三页。WirelessMACCarrierSenseMultipleAccess(CSMA):listentodeterminewhetherthereisactivityonthechannelPersistent:continuouslylistensNonpersistent:waitsarandomamountoftimebeforere-testingp-persistent:slottedandtransmitwhenidlewithaprobabilityofp第十七页，共一百一十三页。WirelessMACContention-freeprotocolsBit-mapprotocol:eachcontentionperiodconsistsofNslots.Binarycountdown:usebinarystationaddressinbidding.HybridMixedcontention-freewithcontention第十八页，共一百一十三页。WirelessMACHiddenTerminalProblemTwonodes,hiddenfromoneanother(outoftransmissionrange),attempttosendinformationtothesamereceivingnode.Packetcollisions.ExposedNodeProblemAnodeisinhibitedfromtransmittingtoothernodesonoverhearingapackettransmission.Wastedbandwidth.第十九页，共一百一十三页。WirelessMACSender-initiatedMACA(MultipleAccesswithCollisionAvoidance)(RTS-CTS-data)MACAW(MACAwithAcknowledgement)BTMA(BusyToneMultipleAccess)DBTMA(DualBTMA)Receiver-initiatedMACA-BI(ByInvitation)OtherextensionsMarchandPAMAS第二十页，共一百一十三页。MACA(P.Khan)Nocarrier-sensingforchannelTwospecialsignalsRTS:request-to-sendCTS:clear-to-sendPacketlostBinaryexponentialback-upOvercomesthehiddenterminalissue第二十一页，共一百一十三页。SamplecollisionRTS-CTSproblem1第二十二页，共一百一十三页。SamplecollisionRTS-CSTproblem2第二十三页，共一百一十三页。MACAW(S.ShenkerandL.Zhang)RTS+CTS+DS+DATA+ACKDS:data-sending(avoidunnecessaryback-offcounterbuildup)RRTS:request-for-request-to-sendDistinctback-offcounterperflow第二十四页，共一百一十三页。DBTMA(Z.Haas)BTMA(BusyToneMultipleAccess)Separatecontrolanddata(busytone)NodessensedatacarryalsosendbusytoneToorestrictive(Disabletwo-hopneighbors)DualBTMARTSReceivebusytone+CTSTransmitbusytone+Data第二十五页，共一百一十三页。MACA-BI(M.Gerla)Receiver-initiatedRTR:ready-to-receiveData:datatransmission第二十六页，共一百一十三页。MARCH(C.T.Toh)MediaAccesswithReducedHandshake(MARCH)第二十七页，共一百一十三页。PAMAS(C.S.Raghavendra)Power-AwareMulti-AccessProtocolwithSignaling(PAMAS)Temp.reducingtransmitterrangeTurnoff第二十八页，共一百一十三页。Others(N.H.Vaidya)DifferentrangesTR:transmissionrange,IR:interferencerange,SR:sensingrange(TR<IR<SR)DifferentrangesforRTS,CTS,Data,andAckDirectionalantennasDO(sender:omni(O)andreceiver:directional(D))Othermodels:OO,OD,andDD第二十九页，共一百一十三页。Others(M.Fang)ImpactofMAConcommunicationIntra-flowcontentionInter-flowcontentionPhysicallayerrelatedissuesRate-adaptation(varyingthedatarate)Otheroptions:varyingthetransmissionpowerorthepacketlengthLinkDiversity:Multi-outputlinkdiversityandmulti-inputlinkdiversity第三十页，共一百一十三页。PowerSaving(Y.–C.Tseng)Tseng’sPower-savingProtocols:UseperiodicactivewindowtodiscoverneighborsOverlappingAwakeIntervalsWake-upPrediction第三十一页，共一百一十三页。PowerSavingDominating-Awake-IntervalProtocol第三十二页，共一百一十三页。PowerSavingPeriodically-Fully-Awake-Interval第三十三页，共一百一十三页。PowerSavingQuorum-BasedProtocols第三十四页，共一百一十三页。IEEE802.11TwooperationalmodesInfrastructure-basedInfrastructurelessoradhocTwotypesofserviceattheMAClayerContention-freeservicebyDistributedCoordinationFunction:DCFContention-freeservicebyPointCoordinationFunction:PCF第三十五页，共一百一十三页。IEEE802.11TwooperationalmodesInfrastructure-basedInfrastructurelessoradhocTwotypesofserviceattheMAClayerContention-freeservicebyDistributedCoordinationFunction:DCFContention-freeservicebyPointCoordinationFunction:PCF第三十六页，共一百一十三页。IEEE802-11RTS-CTShandshake第三十七页，共一百一十三页。IEEE802.11RTS-CTShandshakeRTS(requesttosend)CTS(cleartosend)DatatrasmissionAckOtheritemsNetworkAllocationVector(NAV)DistributedInterFrameSpace(DIFS)ShortInterFrameSpace(SIFS)Backofftime第三十八页，共一百一十三页。IEEE802.11RTS-CTS:contentionDatatransmissionLcontention-freeNAVsetupcannotworkproperlywhentherearecollisionsAllpackets:RTS,CTS,Data,AckaresubjecttocollisionsSIFS<DIFStoincreasethepriorityBackofftime:anintegerfrom(0,CW-1),whereCW(contentionwindow)isdoubledateachretransmission第三十九页，共一百一十三页。RoutinginAdHocNetworksTypes:(n:networksize)Unicasting:(1,1)=(source,destination)Multicasting:(1,k),1<k<nBroadcasting:(1,n)Geocasting:(1,kinaregion)Gossip:(n,n)Gathering:(k,1)Fusion:aspecialtypeofgathering(withsimpledataprocessingatintermediatenodes)第四十页，共一百一十三页。RoutinginAdHocNetworksQualitativeproperties:DistributedoperationLoop-freedomDemand-basedoperationProactiveoperationSecuritySleepperiodoperationUnidirectionallinksupport第四十一页，共一百一十三页。RoutinginAdHocNetworksQuantitativemetrics:End-to-enddatathroughputanddelayRouteacquisitiontimePercentageout-of-orderdeliveryEfficiency第四十二页，共一百一十三页。BasicRoutingStrategiesinInternetSourceRoutingvs.DistributedRoutingFigure2:AsamplesourceroutingFigure3:Asampledistributedrouting第四十三页，共一百一十三页。ClassificationProactivevs.reactiveproactive:continuouslyevaluatenetworkconnectivityreactive:invokearoutedeterminationprocedureon-demand.RightbalancebetweenproactiveandreactiveFlatvs.hierarchical第四十四页，共一百一十三页。SampleProtocolsProactiveProtocolsDestinationsequenceddistancevector(DSDV)ReactiveProtocolsDynamicsourcerouting(DSR)Adhocon-demanddistancevectorrouting(AODV)Temporallyorderedroutingalgorithms(TORA)第四十五页，共一百一十三页。SampleProtocolsHybrid:ZoneroutingHierarchicalCluster-basedConnected-dominating-set-based第四十六页，共一百一十三页。Proactive:DSDVBasedonBellman-FordroutingalgorithmsEnhancedwithfreedomfromloops.Enhancedwithdifferentiationofstaleroutesfromnewonesbysequencenumbers.第四十七页，共一百一十三页。ReactiveThreestepsRoutediscoveryDataforwardingRoutemaintenance第四十八页，共一百一十三页。DSRTherearenoperiodicroutingadvertisementmessages(therebyreducingnetworkbandwidthoverhead).Eachhostmaintainsaroutecache:sourceroutesthatithaslearned.Ifarouteisnotfoundfromroutecache,thesourceattemptstodiscoveroneusingroutediscovery.Routemaintenancemonitorsthecorrectoperationofarouteinuse.第四十九页，共一百一十三页。DSRRouting

(Cont’d.)AsampleDSRroutediscovery第五十页，共一百一十三页。AODVCombinationofDSRandDSDVRoutingtableisconstructedondemand.Sequencenumbers(issuedfromdifferentdestinations)areusedtoavoidloopingThenodeshouldrespond(ROUTE_REPLY)arequest(ROUTE_REQ)ifItisthedestinationnodeAnintermediatenodewitharouteofadestinationsequencenumbernolessthanthatintherequestpacket.第五十一页，共一百一十三页。TORAForeachdestination,aDAGismaintainedwithdestinationasthesink:Eachnodehasaheightmetric.Adirectedlinkalwayspointstoanodewithalowerheightmetric.Tosendapacket,ahostforwardsthepackettoanyneighborwithalowermetric.第五十二页，共一百一十三页。Proactive:DataForwardingSourcerouting:centralizedatthesourceDistributedrouting:decentralizedMultiplepaths第五十三页，共一百一十三页。Proactive:RouteMaintenanceSourceroutingvs.distributedrouting.Globalre-constructionvs.localfixSinglepathvs.multiplepath第五十四页，共一百一十三页。TORA:routemaintenanceFullreversalAteachiterationeachnodeotherthanthedestinationthathasnooutgoinglinkreversesthedirectionsofallitsincominglinks.

PartialreversalEverynodeuotherthanthedestinationkeepsalistofitsneighboringnodesvthathavereversedthedirectionofthecorrespondinglink(u,v)Ateachiterationeachnodeuthathasnooutgoinglinkreversesthedirectionsofthelinks(u;v)forallvwhichdonotappearonitslist,andemptiesthelist.Ifnosuchvexists,nodeureversesthedirectionsofallincominglinksandemptiesthelist.第五十五页，共一百一十三页。TORA:routemaintenance

第五十六页，共一百一十三页。Trade-offs:networkcapacityusageinproactiveapproachesandthelongdelayinreactiveapproaches.Aroutingzone(forahost)includesthenodeswithinagivennumberofhops.Eachhostmaintainsroutinginformationonlytonodeswithinitsroutingzone.Informationoutsidetheroutingzoneisobtainedthroughondemand.Hybrid:Zone-basedRouting第五十七页，共一百一十三页。Zone-basedRouting(Cont’d.)Figure5:Zonerouting第五十八页，共一百一十三页。Hiearchical:Domination-set-basedSchoolbusrouting第五十九页，共一百一十三页。Graph-theoreticDefinitionAsetinG(V,E)isdominatingifallthenodesinthesystemareeitherinthesetorneighborsofnodesintheset.第六十页，共一百一十三页。Five-QueenProblem(1850’s)第六十一页，共一百一十三页。DesirableFeaturesSimpleandquickConnecteddominatingsetFigure6:Asimpleadhocwirelessnetworkoffivewirelessmobilehosts.第六十二页，共一百一十三页。ExistingApproachesGraphtheorycommunity:Boundsonthedominationnumber(Haynes,Hedetniemi,andSlater,1998).Specialclassesofgraphforwhichthedominationproblemcanbesolvedinpolynomialtime.第六十三页，共一百一十三页。ExistingApproaches(Cont’d.)Adhocwirelessnetworkcommunity:Global:MCDS(Sivakumar,Das,andBharghavan,1998).Quasi-global:spanning-tree-based(Wan,Alzoubi,andFrieder,2002).Quasi-local:cluster-based(LinandGerla,1999).Local:markingprocess(WuandLi,1999).第六十四页，共一百一十三页。MCDS(Sivakumar,Das,andBharghavan,UIUC)Allnodesareinitiallycoloredwhite.Thenodewiththemaximumnodedegreeisselectedastherootandcoloredblack.Alltheneighborsoftherootarecoloredgray.Selectagraynodethathasthemaximumwhiteneighbors.Thegraynodeiscoloredblackanditswhiteneighborsaremarkedgray.Repeatstep(3)untilthereisnomorewhitenode.第六十五页，共一百一十三页。MCDS

(Cont’d.)blacknodes=CDS(connecteddominatingset)Figure7:MCDSasanapproximationofCDS第六十六页，共一百一十三页。Spanning-tree-based(Wan,Alzoubi,andFrieder,IIT)A

spanningtreerootedatv(selectedthroughanelectionprocess)isfirstconstructed.Nodesarelabeledaccordingtoatopologicalsortingorderofthetree.第六十七页，共一百一十三页。Spanning-tree-based(Cont’d.)Nodesaremarkedbasedontheirpositionsintheorderstartingfromrootv.Allnodesarewhiteinitially.Vismarkedblackandallnodesarelabeledblackunlessthereisablackneighbor.Eachblacknode(exceptrootv)selectsaneighborwiththelargestlabelbutsmallerthanitsownlabelandmarkitgray.第六十八页，共一百一十三页。Spanning-tree-based

(Cont’d.)blacknodes=DS

blacknodes+graynodes=CDSFigure8:selectingCDSinaspanningtree第六十九页，共一百一十三页。Cluster-based(LeeandGerla,UCLA)Allnodesareinitiallywhite.Whenawhitenodefindsitselfhavingthelowestidamongallitswhiteneighbors,itbecomesaclusterheadandcolorsitselfblack.Allitsneighborsjoinintheclusterandchangetheircolorstogray.第七十页，共一百一十三页。Cluster-based(Cont’d.)Repeatsteps(1)and(2)untilthereisnowhitenodeleft.Specialgraynodes:graynodesthathavetwoneighborsindifferentclusters.第七十一页，共一百一十三页。Cluster-based(Cont’d.)blacknodes=DSblacknodes+specialgraynodes=CDSFigure9:sequentialpropagationinthecluster-basedapproach.第七十二页，共一百一十三页。LocalizedAlgorithmsProcessors(hosts)onlyinteractwithothersinarestrictedvicinity.Eachprocessorperformsexceedinglysimpletasks(suchasmaintainingandpropagatinginformationmarkers).Collectivelytheseprocessorsachieveadesiredglobalobjective.Thereisnosequentialpropagationofinformation.第七十三页，共一百一十三页。MarkingProcess(WuandLi,1999)Anodeismarkedtrueifithastwounconnectedneighbors.Asetofmarkednodes(gatewaysnodes)V’formaconnecteddominatingset.第七十四页，共一百一十三页。MarkingProcess(Cont’d.)

Figure10:Asampleadhocwirelessnetwork第七十五页，共一百一十三页。Dominating-set-basedRoutingIfthesourceisnotagatewayhost,itforwardspacketstoasourcegatewayneighbor.Thissourcegatewayactsasanewsourcetoroutepacketsintheinducedgraphgeneratedfromtheconnecteddominatingset.Eventually,packetsreachadestinationgateway,whichiseitherthedestinationhostitselforagatewayofthedestinationhost.第七十六页，共一百一十三页。DominatingSetReductionReducethesizeofthedominatingset.Roleofgateway/non-gatewayisrotated.第七十七页，共一百一十三页。DominatingSetReduction

(Cont’d.)N[v]=N(v)U{v}isaclosedneighborsetofvRule1:IfN[v]N[u]inGandid(v)<id(u),thenunmarkv.Rule2:IfN(v)N(u)UN(w)inGandid(v)=min{id(v),id(u),id(w)},thenunmarkv.第七十八页，共一百一十三页。DominatingSetReduction

(Cont’d.)Figure12:twosampleexamples第七十九页，共一百一十三页。Example

Figure13:(a)Dominatingsetfromthemarkingprocess(b)Dominatingsetafterdominatingsetreduction第八十页，共一百一十三页。DirectedNetworks:dominatingnodeandabsorbantnodeFigure15:Dominatingandabsorbantnodes第八十一页，共一百一十三页。DirectedNetworks

(Cont’d.)Findingasubsetthatisbothdominatingandabsorbant

(Wu,IEEETPDS2002).Figure16:Anabsorbantsetandadominatingset第八十二页，共一百一十三页。MobilityManagementUpdate/re-calculationon/offmovementrecognizinganewlinkrecognizingabrokenlinkLocalizedmaintenance(update)第八十三页，共一百一十三页。QoSroutingWirelesslink’sbandwidthmaybeaffectedbythetransmissionactivitiesofadjacentlinks.Unlikeone-hopnetwork(cellular),onemustguaranteethequalityofmultiplehopsinapath.Existinglinksmaydisappearandnewlinksmaybeformedasmobilehostsmove.第八十四页，共一百一十三页。QoS:Signalstability-basedadaptive(SSA)Eachnodemaintainsasignalstabilitytable.AreceivingnodepropagatesarequestifTherequestisreceivedoverastronglink.TherequesthanotbeenforwardedpreviouslyThelevelofqualifycanbeloweredatthesourceifthesourcefailtoreceiveareplywithinatime-outperiod.第八十五页，共一百一十三页。QoS:Ticket-basedroutingEachprobingpacketcarriesanumberoftickets.Thenumberofroute-searchingpacketsisconfinedtoavoidblindflooding.第八十六页，共一百一十三页。HierarchicalroutingprotocolsHierarchicalstaterouting(HSR)Multi-levelclusteringAnodecanbeaheadatdifferentlevels第八十七页，共一百一十三页。HierarchicalroutingprotocolsZone-basedRoutingProtocol(ZRP)Proactiveintra-zoneandreactiveinter-zone.FisheyeStateRoutingProtocol(FSR)Afish’seyethatcancapturepixelinformationwithgreateraccuracynearitseve’sfocalpoint.Thefrequencyofexchangesdecreaseswithanincreaseinscope.第八十八页，共一百一十三页。GeometricRoutingGPS-basedroutingThespaceispartitionedintoa2dgridOneclusterheadisselectedineachgridpoint.SparseagraphGabrielgraph:linkuvexistsifftheopendiskwithdiameteruvcontainsnoothernodes.RNG(relativeneighborhoodgraph):linkexistsifd(u,v)≤d(u,w)andd(u,v)≤d(v,w).Yaograph:Foreachnodeu,anyk(k≥6)equal-separatedraysoriginatedatudefinekcones.Ineachcone,choosetheclosetv(ifany)withinthetransmitterrangeofuandaddadirectedlink(u,v).第八十九页，共一百一十三页。Samples第九十页，共一百一十三页。GeometricRoutingGreedyalgorithmClosertothedestinationDifferentgreedy:mostforwardingprogresswithinradiusFaceroutingRouteonafaceinGabrielgraphAlternatebetweenright-handandleft-handruleatintersection(ofthelineconnectedsourceanddest.)Greedy-Face-GreedyGFGonCDS第九十一页，共一百一十三页。Sample第九十二页，共一百一十三页。CollectiveCommunicationBroadcast:onesourceandalldestinations.Multicast:onesourceandmanydestinations.第九十三页，共一百一十三页。Broadcast:BlindFloodingRedundanttransmissionmaycausecontentionandcollision第九十四页，共一百一十三页。BroadcastStaticvs.dynamic

Forwardingstatusdeterminedbeforeorafterthebroadcastprocess)Self-pruningvs.neighbor-designatingForwardingstatusdeterminesbyeachnodeitselforbyneighbors.第九十五页，共一百一十三页。BroadcastConnected-dominating-set-basedOnlydominatingnodesforwardthebroadcastpacket.Cluster-based(independentset)Onlyclusterheadsforwardthepacket,somegateways(thatconnecttwoadjacentclusters)areselectedtorelaythepacket.第九十六页，共一百一十三页。BroadcastDominantpruning(multipointrelays)Selectasubsetof1-hopneighbortocoverall2-hopneighbors第九十七页，共一百一十三页。BroadcastAgenericrule:Nodevhasanon-forwardingstatusifanytwoneighborsareconnectedbyapathconsistsofvisitednodesandnodeswithahigherpriorities.第九十八页，共一百一十三页。MulticastSource-initiatedprotocolsJoinReqandJoinReplyReceiver-initiatedprotocolsJoinReqandJoinAckTree-basedvs.mesh-basedSoft-statevs.hard-state第九十九页，共一百一十三页。MulticastShortestpathtree:foraparticularmulticastCoretree:sharedtreeforallmulticast第一百页，共一百一十三页。Multicasting:ODMRPOn-demandmulticastroutingprotocol第一百零一页，共一百一十三页。Multicasting:MulticastAODV第一百零二页，共一百一十三页。DealingwithMobilityNodemobilityisconsideredtobeundesirableinMANETsusingaconnection-basedmodelRecoversfromandtolerates“bad”effectscausedbymobilityNodesareassumedtoberelativelystable第一百零三页，共一百一十三页。UIUCTwoSchemesRecoverySchemeIfaroutingpathisdisruptedb