移動(dòng)自組織網(wǎng)絡(luò)-112張課件

TableofContentsIntroduction

InfrastructurednetworksHandofflocationmanagement(mobileIP)channelassignmentTableofContents1TableofContents(cont’d.)InfrastructurelessnetworksWirelessMAC(IEEE802.11andBluetooth)AdHocRoutingProtocolsMulticastingandBroadcastingSecurityNetworkCodingTableofContents(cont’d.)2TableofContents(cont’d.)Infrastructurelessnetworks(cont’d.)PowerOptimizationApplicationsSensornetworksandindoorwirelessenvironmentsPervasivecomputingSocialnetworksSampleon-goingprojectsTableofContents(cont’d.)Inf3AdHocWirelessNetworks(Infrastructurelessnetworks)Anadhocnetworkisacollectionofwirelessmobilehostformingatemporarynetworkwithouttheaidofanycentralizedadministrationorstandardsupportservicesregularlyavailableonthewideareanetworktowhichthehostsmaynormallybeconnected(JohnsonandMaltz)AdHocWirelessNetworks(Infr4AdHocWirelessNetworks(Infrastructurelessnetworks)Manet

(mobileadhocnetworks)

MobiledistributedmultihopwirelessnetworksTemporaryinnatureNobasestationandrapidlydeployableNeighborhoodawarenessMultiple-hopcommunicationUnitdiskgraph:hostconnectionbasedongeographicaldistanceAdHocWirelessNetworks(Infr5SampleAdHocNetworksSensornetworksIndoorwirelessapplicationsMeshnetworksPeople-basednetworks“smallworld”thatareverylargegraphsthattendtobesparse,clustered,andhaveasmalldiameter.“sixdegreeofseparation”SampleAdHocNetworksSensorn6Self-organizing:withoutcentralizedcontrolScarceresources:bandwidthandbatteriesDynamicnetworktopologyCharacteristicsSelf-organizing:withoutcentr7UnitDiskGraphFigure1:Asimpleadhocwirelessnetworkoffivewirelessmobilehosts.UnitDiskGraphFigure1:Asim8Defenseindustry(battlefield)LawenforcementAcademicinstitutions(conferenceandmeeting)PersonalareanetworksandBluetoothHomenetworkingEmbeddingcomputingapplications

HealthfacilitiesDisasterrecovery(search-and-rescue)ApplicationsApplicationsDefenseindustry(battlefield)9MobilitymanagementAddressingandrouting*LocationtrackingAbsolutevs.Relative,GPSNetworkmanagementMergeandsplitResourcemanagementNetworksresourceallocationandenergyefficiencyQoSmanagement*DynamicadvancereservationandadaptiveerrorcontroltechniquesMajorIssuesMobilitymanagementMajorIssu10MACprotocols*Contentionvs.contention-freeApplicationsandmiddlewareMeasurementandexperimentationSecurity*Authentication,encryption,anonymity,andintrusiondetectionErrorcontrolandfailureErrorcorrectionandretransmission,deploymentofback-upsystemsNetworkcodingReducenumberoftransmissionsMajorIssues(Cont’d.)MACprotocols*MajorIssues(Co11IssuestobeCoveredWirelessMediaAccessProtocols(MAC)AdHocRoutingProtocolsMulticastingandBroadcastingPowerOptimizationSecurityNetworkCodingIssuestobeCoveredWirelessM12WirelessMACAMAC(MediaAccessProtocol)isasetofrulesorprocedurestoallowtheefficientuseofasharedmedium.Contentionvs.contention-freeSender-initiatedvs.receiver-initiatedWirelessMACAMAC(MediaAcces13WirelessMAC:MajorIssuesDistributedoperationsSynchronizationHiddenterminalsExposedterminalsThroughputAccessdelayFairnessReal-timetrafficResourcereservationAbilitytomeasureresourceavailabilityPowerandratecontrolDirectionalantennasWirelessMAC:MajorIssuesDist14WirelessMACContention-basedALOHA:nocollisionavoidancePure:transmittedatarbitrarytimeSlotted:transmittedatstartofatimeslotp-persistent:slottedandtransmittedwithaprobabilitypWirelessMACContention-based15WirelessMACCarrierSenseMultipleAccess(CSMA):listentodeterminewhetherthereisactivityonthechannelPersistent:continuouslylistensNonpersistent:waitsarandomamountoftimebeforere-testingp-persistent:slottedandtransmitwhenidlewithaprobabilityofpWirelessMACCarrierSenseMult16WirelessMACContention-freeprotocolsBit-mapprotocol:eachcontentionperiodconsistsofNslots.Binarycountdown:usebinarystationaddressinbidding.HybridMixedcontention-freewithcontentionWirelessMACContention-freepr17WirelessMACHiddenTerminalProblemTwonodes,hiddenfromoneanother(outoftransmissionrange),attempttosendinformationtothesamereceivingnode.Packetcollisions.ExposedNodeProblemAnodeisinhibitedfromtransmittingtoothernodesonoverhearingapackettransmission.Wastedbandwidth.WirelessMACHiddenTerminalPr18WirelessMACSender-initiatedMACA(MultipleAccesswithCollisionAvoidance)(RTS-CTS-data)MACAW(MACAwithAcknowledgement)BTMA(BusyToneMultipleAccess)DBTMA(DualBTMA)Receiver-initiatedMACA-BI(ByInvitation)OtherextensionsMarchandPAMASWirelessMACSender-initiated19MACA(P.Khan)Nocarrier-sensingforchannelTwospecialsignalsRTS:request-to-sendCTS:clear-to-sendPacketlostBinaryexponentialback-upOvercomesthehiddenterminalissueMACA(P.Khan)Nocarrier-sensi20SamplecollisionRTS-CTSproblem1SamplecollisionRTS-CTSproble21SamplecollisionRTS-CSTproblem2SamplecollisionRTS-CSTproble22MACAW(S.ShenkerandL.Zhang)RTS+CTS+DS+DATA+ACKDS:data-sending(avoidunnecessaryback-offcounterbuildup)RRTS:request-for-request-to-sendDistinctback-offcounterperflowMACAW(S.ShenkerandL.Zhang23DBTMA(Z.Haas)BTMA(BusyToneMultipleAccess)Separatecontrolanddata(busytone)NodessensedatacarryalsosendbusytoneToorestrictive(Disabletwo-hopneighbors)DualBTMARTSReceivebusytone+CTSTransmitbusytone+DataDBTMA(Z.Haas)BTMA(BusyTone24MACA-BI(M.Gerla)Receiver-initiatedRTR:ready-to-receiveData:datatransmissionMACA-BI(M.Gerla)Receiver-ini25MARCH(C.T.Toh)MediaAccesswithReducedHandshake(MARCH)MARCH(C.T.Toh)MediaAccess26PAMAS(C.S.Raghavendra)Power-AwareMulti-AccessProtocolwithSignaling(PAMAS)Temp.reducingtransmitterrangeTurnoffPAMAS(C.S.Raghavendra)Power27Others(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,andDDOthers(N.H.Vaidya)28Others(M.Fang)ImpactofMAConcommunicationIntra-flowcontentionInter-flowcontentionPhysicallayerrelatedissuesRate-adaptation(varyingthedatarate)Otheroptions:varyingthetransmissionpowerorthepacketlengthLinkDiversity:Multi-outputlinkdiversityandmulti-inputlinkdiversityOthers(M.Fang)29PowerSaving(Y.–C.Tseng)Tseng’sPower-savingProtocols:UseperiodicactivewindowtodiscoverneighborsOverlappingAwakeIntervalsWake-upPredictionPowerSaving(Y.–C.Tseng)Tse30PowerSavingDominating-Awake-IntervalProtocolPowerSavingDominating-Awake-I31PowerSavingPeriodically-Fully-Awake-IntervalPowerSavingPeriodically-Fully32PowerSavingQuorum-BasedProtocolsPowerSavingQuorum-BasedProto33IEEE802.11TwooperationalmodesInfrastructure-basedInfrastructurelessoradhocTwotypesofserviceattheMAClayerContention-freeservicebyDistributedCoordinationFunction:DCFContention-freeservicebyPointCoordinationFunction:PCFIEEE802.11Twooperationalmod34IEEE802.11TwooperationalmodesInfrastructure-basedInfrastructurelessoradhocTwotypesofserviceattheMAClayerContention-freeservicebyDistributedCoordinationFunction:DCFContention-freeservicebyPointCoordinationFunction:PCFIEEE802.11Twooperationalmod35IEEE802-11RTS-CTShandshakeIEEE802-11RTS-CTShandshake36IEEE802.11RTS-CTShandshakeRTS(requesttosend)CTS(cleartosend)DatatrasmissionAckOtheritemsNetworkAllocationVector(NAV)DistributedInterFrameSpace(DIFS)ShortInterFrameSpace(SIFS)BackofftimeIEEE802.11RTS-CTShandshake37IEEE802.11RTS-CTS:contentionDatatransmissionLcontention-freeNAVsetupcannotworkproperlywhentherearecollisionsAllpackets:RTS,CTS,Data,AckaresubjecttocollisionsSIFS<DIFStoincreasethepriorityBackofftime:anintegerfrom(0,CW-1),whereCW(contentionwindow)isdoubledateachretransmissionIEEE802.11RTS-CTS:contention38RoutinginAdHocNetworksTypes:(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)RoutinginAdHocNetworksType39RoutinginAdHocNetworksQualitativeproperties:DistributedoperationLoop-freedomDemand-basedoperationProactiveoperationSecuritySleepperiodoperationUnidirectionallinksupportRoutinginAdHocNetworksQual40RoutinginAdHocNetworksQuantitativemetrics:End-to-enddatathroughputanddelayRouteacquisitiontimePercentageout-of-orderdeliveryEfficiencyRoutinginAdHocNetworksQuan41BasicRoutingStrategiesinInternetSourceRoutingvs.DistributedRoutingFigure2:AsamplesourceroutingFigure3:AsampledistributedroutingBasicRoutingStrategiesinIn42ClassificationProactivevs.reactiveproactive:continuouslyevaluatenetworkconnectivityreactive:invokearoutedeterminationprocedureon-demand.RightbalancebetweenproactiveandreactiveFlatvs.hierarchicalClassificationProactivevs.re43SampleProtocolsProactiveProtocolsDestinationsequenceddistancevector(DSDV)ReactiveProtocolsDynamicsourcerouting(DSR)Adhocon-demanddistancevectorrouting(AODV)Temporallyorderedroutingalgorithms(TORA)SampleProtocolsProactiveProt44SampleProtocolsHybrid:ZoneroutingHierarchicalCluster-basedConnected-dominating-set-basedSampleProtocolsHybrid:45Proactive:DSDVBasedonBellman-FordroutingalgorithmsEnhancedwithfreedomfromloops.Enhancedwithdifferentiationofstaleroutesfromnewonesbysequencenumbers.Proactive:DSDVBasedonBellma46ReactiveThreestepsRoutediscoveryDataforwardingRoutemaintenanceReactiveThreesteps47DSRTherearenoperiodicroutingadvertisementmessages(therebyreducingnetworkbandwidthoverhead).Eachhostmaintainsaroutecache:sourceroutesthatithaslearned.Ifarouteisnotfoundfromroutecache,thesourceattemptstodiscoveroneusingroutediscovery.Routemaintenancemonitorsthecorrectoperationofarouteinuse.DSRTherearenoperiodicrouti48DSRRouting

(Cont’d.)AsampleDSRroutediscoveryDSRRouting(Cont’d.)Asample49AODVCombinationofDSRandDSDVRoutingtableisconstructedondemand.Sequencenumbers(issuedfromdifferentdestinations)areusedtoavoidloopingThenodeshouldrespond(ROUTE_REPLY)arequest(ROUTE_REQ)ifItisthedestinationnodeAnintermediatenodewitharouteofadestinationsequencenumbernolessthanthatintherequestpacket.AODVCombinationofDSRandDSD50TORAForeachdestination,aDAGismaintainedwithdestinationasthesink:Eachnodehasaheightmetric.Adirectedlinkalwayspointstoanodewithalowerheightmetric.Tosendapacket,ahostforwardsthepackettoanyneighborwithalowermetric.TORAForeachdestination,aDA51Proactive:DataForwardingSourcerouting:centralizedatthesourceDistributedrouting:decentralizedMultiplepathsProactive:DataForwardingSour52Proactive:RouteMaintenanceSourceroutingvs.distributedrouting.Globalre-constructionvs.localfixSinglepathvs.multiplepathProactive:RouteMaintenanceSo53TORA:routemaintenanceFullreversalAteachiterationeachnodeotherthanthedestinationthathasnooutgoinglinkreversesthedirectionsofallitsincominglinks.

PartialreversalEverynodeuotherthanthedestinationkeepsalistofitsneighboringnodesvthathavereversedthedirectionofthecorrespondinglink(u,v)Ateachiterationeachnodeuthathasnooutgoinglinkreversesthedirectionsofthelinks(u;v)forallvwhichdonotappearonitslist,andemptiesthelist.Ifnosuchvexists,nodeureversesthedirectionsofallincominglinksandemptiesthelist.TORA:routemaintenanceFullre54TORA:routemaintenance

TORA:routemaintenance55Trade-offs:networkcapacityusageinproactiveapproachesandthelongdelayinreactiveapproaches.Aroutingzone(forahost)includesthenodeswithinagivennumberofhops.Eachhostmaintainsroutinginformationonlytonodeswithinitsroutingzone.Informationoutsidetheroutingzoneisobtainedthroughondemand.Hybrid:Zone-basedRoutingTrade-offs:networkcapacityu56Zone-basedRouting(Cont’d.)Figure5:ZoneroutingZone-basedRouting(Cont’d.)Fi57Hiearchical:Domination-set-basedSchoolbusroutingHiearchical:Domination-set-ba58Graph-theoreticDefinitionAsetinG(V,E)isdominatingifallthenodesinthesystemareeitherinthesetorneighborsofnodesintheset.Graph-theoreticDefinitionAse59Five-QueenProblem(1850’s)Five-QueenProblem(1850’s)60DesirableFeaturesSimpleandquickConnecteddominatingsetFigure6:Asimpleadhocwirelessnetworkoffivewirelessmobilehosts.DesirableFeaturesSimpleandq61ExistingApproachesGraphtheorycommunity:Boundsonthedominationnumber(Haynes,Hedetniemi,andSlater,2019).Specialclassesofgraphforwhichthedominationproblemcanbesolvedinpolynomialtime.ExistingApproachesGraphtheor62ExistingApproaches(Cont’d.)Adhocwirelessnetworkcommunity:Global:MCDS(Sivakumar,Das,andBharghavan,2019).Quasi-global:spanning-tree-based(Wan,Alzoubi,andFrieder,2019).Quasi-local:cluster-based(LinandGerla,2019).Local:markingprocess(WuandLi,2019).ExistingApproaches(Cont’d.)63MCDS(Sivakumar,Das,andBharghavan,UIUC)Allnodesareinitiallycoloredwhite.Thenodewiththemaximumnodedegreeisselectedastherootandcoloredblack.Alltheneighborsoftherootarecoloredgray.Selectagraynodethathasthemaximumwhiteneighbors.Thegraynodeiscoloredblackanditswhiteneighborsaremarkedgray.Repeatstep(3)untilthereisnomorewhitenode.MCDS(Sivakumar,Das,andBhar64MCDS

(Cont’d.)blacknodes=CDS(connecteddominatingset)Figure7:MCDSasanapproximationofCDSMCDS(Cont’d.)blacknodes=CD65Spanning-tree-based(Wan,Alzoubi,andFrieder,IIT)A

spanningtreerootedatv(selectedthroughanelectionprocess)isfirstconstructed.Nodesarelabeledaccordingtoatopologicalsortingorderofthetree.Spanning-tree-based(Wan,Alzo66Spanning-tree-based(Cont’d.)Nodesaremarkedbasedontheirpositionsintheorderstartingfromrootv.Allnodesarewhiteinitially.Vismarkedblackandallnodesarelabeledblackunlessthereisablackneighbor.Eachblacknode(exceptrootv)selectsaneighborwiththelargestlabelbutsmallerthanitsownlabelandmarkitgray.Spanning-tree-based(Cont’d.)N67Spanning-tree-based

(Cont’d.)blacknodes=DS

blacknodes+graynodes=CDSFigure8:selectingCDSinaspanningtreeSpanning-tree-based(Cont’d.)b68Cluster-based(LeeandGerla,UCLA)Allnodesareinitiallywhite.Whenawhitenodefindsitselfhavingthelowestidamongallitswhiteneighbors,itbecomesaclusterheadandcolorsitselfblack.Allitsneighborsjoinintheclusterandchangetheircolorstogray.Cluster-based(LeeandGerla,69Cluster-based(Cont’d.)Repeatsteps(1)and(2)untilthereisnowhitenodeleft.Specialgraynodes:graynodesthathavetwoneighborsindifferentclusters.Cluster-based(Cont’d.)Repeat70Cluster-based(Cont’d.)blacknodes=DSblacknodes+specialgraynodes=CDSFigure9:sequentialpropagationinthecluster-basedapproach.Cluster-based(Cont’d.)blackn71LocalizedAlgorithmsProcessors(hosts)onlyinteractwithothersinarestrictedvicinity.Eachprocessorperformsexceedinglysimpletasks(suchasmaintainingandpropagatinginformationmarkers).Collectivelytheseprocessorsachieveadesiredglobalobjective.Thereisnosequentialpropagationofinformation.LocalizedAlgorithmsProcessors72MarkingProcess(WuandLi,2019)Anodeismarkedtrueifithastwounconnectedneighbors.Asetofmarkednodes(gatewaysnodes)V’formaconnecteddominatingset.MarkingProcess(WuandLi,2073MarkingProcess(Cont’d.)

Figure10:AsampleadhocwirelessnetworkMarkingProcess(Cont’d.)Figu74Dominating-set-basedRoutingIfthesourceisnotagatewayhost,itforwardspacketstoasourcegatewayneighbor.Thissourcegatewayactsasanewsourcetoroutepacketsintheinducedgraphgeneratedfromtheconnecteddominatingset.Eventually,packetsreachadestinationgateway,whichiseitherthedestinationhostitselforagatewayofthedestinationhost.Dominating-set-basedRoutingI75DominatingSetReductionReducethesizeofthedominatingset.Roleofgateway/non-gatewayisrotated.DominatingSetReductionReduce76DominatingSetReduction

(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(Cont77DominatingSetReduction

(Cont’d.)Figure12:twosampleexamplesDominatingSetReduction(Cont78Example

Figure13:(a)Dominatingsetfromthemarkingprocess(b)DominatingsetafterdominatingsetreductionExampleFigure13:(a)Dominat79DirectedNetworks:dominatingnodeandabsorbantnodeFigure15:DominatingandabsorbantnodesDirectedNetworks:dominating80DirectedNetworks

(Cont’d.)Findingasubsetthatisbothdominatingandabsorbant

(Wu,IEEETPDS2019).Figure16:AnabsorbantsetandadominatingsetDirectedNetworks(Cont’d.)81MobilityManagementUpdate/re-calculationon/offmovementrecognizinganewlinkrecognizingabrokenlinkLocalizedmaintenance(update)MobilityManagementUpdate/re-c82QoSroutingWirelesslink’sbandwidthmaybeaffectedbythetransmissionactivitiesofadjacentlinks.Unlikeone-hopnetwork(cellular),onemustguaranteethequalityofmultiplehopsinapath.Existinglinksmaydisappearandnewlinksmaybeformedasmobilehostsmove.QoSroutingWirelesslink’sban83QoS:Signalstability-basedadaptive(SSA)Eachnodemaintainsasignalstabilitytable.AreceivingnodepropagatesarequestifTherequestisreceivedoverastronglink.TherequesthanotbeenforwardedpreviouslyThelevelofqualifycanbeloweredatthesourceifthesourcefailtoreceiveareplywithinatime-outperiod.QoS:Signalstability-basedad84QoS:Ticket-basedroutingEachprobingpacketcarriesanumberoftickets.Thenumberofroute-searchingpacketsisconfinedtoavoidblindflooding.QoS:Ticket-basedroutingEach85HierarchicalroutingprotocolsHierarchicalstaterouting(HSR)Multi-levelclusteringAnodecanbeaheadatdifferentlevelsHierarchicalroutingprotocols86HierarchicalroutingprotocolsZone-basedRoutingProtocol(ZRP)Proactiveintra-zoneandreactiveinter-zone.FisheyeStateRoutingProtocol(FSR)Afish’seyethatcancapturepixelinformationwithgreateraccuracynearitseve’sfocalpoint.Thefrequencyofexchangesdecreaseswithanincreaseinscope.Hierarchicalroutingprotocols87GeometricRoutingGPS-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).GeometricRoutingGPS-basedrou88SamplesSamples89GeometricRoutingGreedyalgorithmClosertothedestinationDifferentgreedy:mostforwardingprogresswithinradiusFaceroutingRouteonafaceinGabrielgraphAlternatebetweenright-handandleft-handruleatintersection(ofthelineconnectedsourceanddest.)Greedy-Face-GreedyGFGonCDSGeometricRoutingGreedyalgori90SampleSample91CollectiveCommunicationBroadcast:onesourceandalldestinations.Multicast:onesourceandmanydestinations.CollectiveCommunicationBroadc92Broadcast:BlindFloodingRedundanttransmissionmaycausecontentionandcollisionBroadcast:BlindFloodingRedun93BroadcastStaticvs.dynamic

Forwardingstatusdeterminedbeforeorafterthebroadcastprocess)Self-pruningvs.neighbor-designatingForwardingstatusdeterminesbyeachnodeitselforbyneighbors.BroadcastStaticvs.dynamic94BroadcastConnected-dominating-set-basedOnlydominatingnodesforwardthebroadcastpacket.Cluster-based(independentset)Onlyclusterheadsforwardthepacket,somegateways(thatconnecttwoadjacentclusters)areselectedtorelaythepacket.BroadcastConnected-dominating-95BroadcastDominantpruning(multipointrelays)Selectasubsetof1-hopneighbortocoverall2-hopneighborsBroadcastDominantpruning(mul96BroadcastAgenericrule:Nodevhasanon-forwardingstatusifanytwoneighborsareconnectedbyapathconsistsofvisitednodesandnodeswithahigherpriorities.BroadcastAgenericrule:97MulticastSource-initiatedprotocolsJoinReqandJoinReplyReceiver-initiatedprotocolsJoinReqandJoinAckTree-basedvs.mesh-basedSoft-statevs.hard-stateMulticastSource-initiatedprot98MulticastShortestpathtree:foraparticularmulticastCoretree:sharedtreeforallmulticastMulticastShortestpathtree:f99Multicasting:ODMRPOn-demandmulticastroutingprotocolMulticasting:ODMRPOn-demandm100Multicasting:MulticastAODVMulticasting:MulticastAODV101DealingwithMobilityNodemobilityisconsideredtobeundesirableinMANETsusingaconnection-basedmodelRecoversfromandtolerates“bad”effectscausedbymobilityNodesareassumedtoberelativelystableDealingwithMobilityNodemobi102TwoSche