移动自组织网络-课件

TableofContentsIntroduction

InfrastructurednetworksHandofflocationmanagement(mobileIP)channelassignmentTableofContents(cont’d.)InfrastructurelessnetworksWirelessMAC(IEEE802.11andBluetooth)AdHocRoutingProtocolsMulticastingandBroadcastingSecurityNetworkCodingTableofContents(cont’d.)Infrastructurelessnetworks(cont’d.)PowerOptimizationApplicationsSensornetworksandindoorwirelessenvironmentsPervasivecomputingSocialnetworksSampleon-goingprojectsAdHocWirelessNetworks(Infrastructurelessnetworks)Anadhocnetworkisacollectionofwirelessmobilehostformingatemporarynetworkwithouttheaidofanycentralizedadministrationorstandardsupportservicesregularlyavailableonthewideareanetworktowhichthehostsmaynormallybeconnected(JohnsonandMaltz)AdHocWirelessNetworks(Infrastructurelessnetworks)Manet

(mobileadhocnetworks)

MobiledistributedmultihopwirelessnetworksTemporaryinnatureNobasestationandrapidlydeployableNeighborhoodawarenessMultiple-hopcommunicationUnitdiskgraph:hostconnectionbasedongeographicaldistanceSampleAdHocNetworksSensornetworksIndoorwirelessapplicationsMeshnetworksPeople-basednetworks“smallworld”thatareverylargegraphsthattendtobesparse,clustered,andhaveasmalldiameter.“sixdegreeofseparation”Self-organizing:withoutcentralizedcontrolScarceresources:bandwidthandbatteriesDynamicnetworktopologyCharacteristicsUnitDiskGraphFigure1:Asimpleadhocwirelessnetworkoffivewirelessmobilehosts.Defenseindustry(battlefield)LawenforcementAcademicinstitutions(conferenceandmeeting)PersonalareanetworksandBluetoothHomenetworkingEmbeddingcomputingapplications

HealthfacilitiesDisasterrecovery(search-and-rescue)ApplicationsApplicationsMobilitymanagementAddressingandrouting*LocationtrackingAbsolutevs.Relative,GPSNetworkmanagementMergeandsplitResourcemanagementNetworksresourceallocationandenergyefficiencyQoSmanagement*DynamicadvancereservationandadaptiveerrorcontroltechniquesMajorIssuesMACprotocols*Contentionvs.contention-freeApplicationsandmiddlewareMeasurementandexperimentationSecurity*Authentication,encryption,anonymity,andintrusiondetectionErrorcontrolandfailureErrorcorrectionandretransmission,deploymentofback-upsystemsNetworkcodingReducenumberoftransmissionsMajorIssues(Cont’d.)IssuestobeCoveredWirelessMediaAccessProtocols(MAC)AdHocRoutingProtocolsMulticastingandBroadcastingPowerOptimizationSecurityNetworkCodingWirelessMACAMAC(MediaAccessProtocol)isasetofrulesorprocedurestoallowtheefficientuseofasharedmedium.Contentionvs.contention-freeSender-initiatedvs.receiver-initiatedWirelessMAC:MajorIssuesDistributedoperationsSynchronizationHiddenterminalsExposedterminalsThroughputAccessdelayFairnessReal-timetrafficResourcereservationAbilitytomeasureresourceavailabilityPowerandratecontrolDirectionalantennasWirelessMACContention-basedALOHA:nocollisionavoidancePure:transmittedatarbitrarytimeSlotted:transmittedatstartofatimeslotp-persistent:slottedandtransmittedwithaprobabilitypWirelessMACCarrierSenseMultipleAccess(CSMA):listentodeterminewhetherthereisactivityonthechannelPersistent:continuouslylistensNonpersistent:waitsarandomamountoftimebeforere-testingp-persistent:slottedandtransmitwhenidlewithaprobabilityofpWirelessMACContention-freeprotocolsBit-mapprotocol:eachcontentionperiodconsistsofNslots.Binarycountdown:usebinarystationaddressinbidding.HybridMixedcontention-freewithcontentionWirelessMACHiddenTerminalProblemTwonodes,hiddenfromoneanother(outoftransmissionrange),attempttosendinformationtothesamereceivingnode.Packetcollisions.ExposedNodeProblemAnodeisinhibitedfromtransmittingtoothernodesonoverhearingapackettransmission.Wastedbandwidth.WirelessMACSender-initiatedMACA(MultipleAccesswithCollisionAvoidance)(RTS-CTS-data)MACAW(MACAwithAcknowledgement)BTMA(BusyToneMultipleAccess)DBTMA(DualBTMA)Receiver-initiatedMACA-BI(ByInvitation)OtherextensionsMarchandPAMASMACA(P.Khan)Nocarrier-sensingforchannelTwospecialsignalsRTS:request-to-sendCTS:clear-to-sendPacketlostBinaryexponentialback-upOvercomesthehiddenterminalissueSamplecollisionRTS-CTSproblem1SamplecollisionRTS-CSTproblem2MACAW(S.ShenkerandL.Zhang)RTS+CTS+DS+DATA+ACKDS:data-sending(avoidunnecessaryback-offcounterbuildup)RRTS:request-for-request-to-sendDistinctback-offcounterperflowDBTMA(Z.Haas)BTMA(BusyToneMultipleAccess)Separatecontrolanddata(busytone)NodessensedatacarryalsosendbusytoneToorestrictive(Disabletwo-hopneighbors)DualBTMARTSReceivebusytone+CTSTransmitbusytone+DataMACA-BI(M.Gerla)Receiver-initiatedRTR:ready-to-receiveData:datatransmissionMARCH(C.T.Toh)MediaAccesswithReducedHandshake(MARCH)PAMAS(C.S.Raghavendra)Power-AwareMulti-AccessProtocolwithSignaling(PAMAS)Temp.reducingtransmitterrangeTurnoffOthers(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(M.Fang)ImpactofMAConcommunicationIntra-flowcontentionInter-flowcontentionPhysicallayerrelatedissuesRate-adaptation(varyingthedatarate)Otheroptions:varyingthetransmissionpowerorthepacketlengthLinkDiversity:Multi-outputlinkdiversityandmulti-inputlinkdiversityPowerSaving(Y.–C.Tseng)Tseng’sPower-savingProtocols:UseperiodicactivewindowtodiscoverneighborsOverlappingAwakeIntervalsWake-upPredictionPowerSavingDominating-Awake-IntervalProtocolPowerSavingPeriodically-Fully-Awake-IntervalPowerSavingQuorum-BasedProtocolsIEEE802.11TwooperationalmodesInfrastructure-basedInfrastructurelessoradhocTwotypesofserviceattheMAClayerContention-freeservicebyDistributedCoordinationFunction:DCFContention-freeservicebyPointCoordinationFunction:PCFIEEE802.11TwooperationalmodesInfrastructure-basedInfrastructurelessoradhocTwotypesofserviceattheMAClayerContention-freeservicebyDistributedCoordinationFunction:DCFContention-freeservicebyPointCoordinationFunction:PCFIEEE802-11RTS-CTShandshakeIEEE802.11RTS-CTShandshakeRTS(requesttosend)CTS(cleartosend)DatatrasmissionAckOtheritemsNetworkAllocationVector(NAV)DistributedInterFrameSpace(DIFS)ShortInterFrameSpace(SIFS)BackofftimeIEEE802.11RTS-CTS:contentionDatatransmissionLcontention-freeNAVsetupcannotworkproperlywhentherearecollisionsAllpackets:RTS,CTS,Data,AckaresubjecttocollisionsSIFS<DIFStoincreasethepriorityBackofftime:anintegerfrom(0,CW-1),whereCW(contentionwindow)isdoubledateachretransmissionRoutinginAdHocNetworksTypes:(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-basedoperationProactiveoperationSecuritySleepperiodoperationUnidirectionallinksupportRoutinginAdHocNetworksQuantitativemetrics:End-to-enddatathroughputanddelayRouteacquisitiontimePercentageout-of-orderdeliveryEfficiencyBasicRoutingStrategiesinInternetSourceRoutingvs.DistributedRoutingFigure2:AsamplesourceroutingFigure3:AsampledistributedroutingClassificationProactivevs.reactiveproactive:continuouslyevaluatenetworkconnectivityreactive:invokearoutedeterminationprocedureon-demand.RightbalancebetweenproactiveandreactiveFlatvs.hierarchicalSampleProtocolsProactiveProtocolsDestinationsequenceddistancevector(DSDV)ReactiveProtocolsDynamicsourcerouting(DSR)Adhocon-demanddistancevectorrouting(AODV)Temporallyorderedroutingalgorithms(TORA)SampleProtocolsHybrid:ZoneroutingHierarchicalCluster-basedConnected-dominating-set-basedProactive:DSDVBasedonBellman-FordroutingalgorithmsEnhancedwithfreedomfromloops.Enhancedwithdifferentiationofstaleroutesfromnewonesbysequencenumbers.ReactiveThreestepsRoutediscoveryDataforwardingRoutemaintenanceDSRTherearenoperiodicroutingadvertisementmessages(therebyreducingnetworkbandwidthoverhead).Eachhostmaintainsaroutecache:sourceroutesthatithaslearned.Ifarouteisnotfoundfromroutecache,thesourceattemptstodiscoveroneusingroutediscovery.Routemaintenancemonitorsthecorrectoperationofarouteinuse.DSRRouting

(Cont’d.)AsampleDSRroutediscoveryAODVCombinationofDSRandDSDVRoutingtableisconstructedondemand.Sequencenumbers(issuedfromdifferentdestinations)areusedtoavoidloopingThenodeshouldrespond(ROUTE_REPLY)arequest(ROUTE_REQ)ifItisthedestinationnodeAnintermediatenodewitharouteofadestinationsequencenumbernolessthanthatintherequestpacket.TORAForeachdestination,aDAGismaintainedwithdestinationasthesink:Eachnodehasaheightmetric.Adirectedlinkalwayspointstoanodewithalowerheightmetric.Tosendapacket,ahostforwardsthepackettoanyneighborwithalowermetric.Proactive:DataForwardingSourcerouting:centralizedatthesourceDistributedrouting:decentralizedMultiplepathsProactive:RouteMaintenanceSourceroutingvs.distributedrouting.Globalre-constructionvs.localfixSinglepathvs.multiplepathTORA:routemaintenanceFullreversalAteachiterationeachnodeotherthanthedestinationthathasnooutgoinglinkreversesthedirectionsofallitsincominglinks.

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

Trade-offs:networkcapacityusageinproactiveapproachesandthelongdelayinreactiveapproaches.Aroutingzone(forahost)includesthenodeswithinagivennumberofhops.Eachhostmaintainsroutinginformationonlytonodeswithinitsroutingzone.Informationoutsidetheroutingzoneisobtainedthroughondemand.Hybrid:Zone-basedRoutingZone-basedRouting(Cont’d.)Figure5:ZoneroutingHiearchical:Domination-set-basedSchoolbusroutingGraph-theoreticDefinitionAsetinG(V,E)isdominatingifallthenodesinthesystemareeitherinthesetorneighborsofnodesintheset.Five-QueenProblem(1850’s)DesirableFeaturesSimpleandquickConnecteddominatingsetFigure6:Asimpleadhocwirelessnetworkoffivewirelessmobilehosts.ExistingApproachesGraphtheorycommunity:Boundsonthedominationnumber(Haynes,Hedetniemi,andSlater,2019).Specialclassesofgraphforwhichthedominationproblemcanbesolvedinpolynomialtime.ExistingApproaches(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).MCDS(Sivakumar,Das,andBharghavan,UIUC)Allnodesareinitiallycoloredwhite.Thenodewiththemaximumnodedegreeisselectedastherootandcoloredblack.Alltheneighborsoftherootarecoloredgray.Selectagraynodethathasthemaximumwhiteneighbors.Thegraynodeiscoloredblackanditswhiteneighborsaremarkedgray.Repeatstep(3)untilthereisnomorewhitenode.MCDS

(Cont’d.)blacknodes=CDS(connecteddominatingset)Figure7:MCDSasanapproximationofCDSSpanning-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:selectingCDSinaspanningtreeCluster-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,2019)Anodeismarkedtrueifithastwounconnectedneighbors.Asetofmarkednodes(gatewaysnodes)V’formaconnecteddominatingset.MarkingProcess(Cont’d.)

Figure10:AsampleadhocwirelessnetworkDominating-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:twosampleexamplesExample

Figure13:(a)Dominatingsetfromthemarkingprocess(b)DominatingsetafterdominatingsetreductionDirectedNetworks:dominatingnodeandabsorbantnodeFigure15:DominatingandabsorbantnodesDirectedNetworks

(Cont’d.)Findingasubsetthatisbothdominatingandabsorbant

(Wu,IEEETPDS2019).Figure16:AnabsorbantsetandadominatingsetMobilityManagementUpdate/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-levelclusteringAnodecanbeaheadatdifferentlevelsHierarchicalroutingprotocolsZone-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).SamplesGeometricRoutingGreedyalgorithmClosertothedestinationDifferentgreedy:mostforwardingprogresswithinradiusFaceroutingRouteonafaceinGabrielgraphAlternatebetweenright-handandleft-handruleatintersection(ofthelineconnectedsourceanddest.)Greedy-Face-GreedyGFGonCDSSampleCollectiveCommunicationBroadcast:onesourceandalldestinations.Multicast:onesourceandmanydestinations.Broadcast:BlindFloodingRedundanttransmissionmaycausecontentionandcollisionBroadcastStaticvs.dynamic

Forwardingstatusdeterminedbeforeorafterthebroadcastprocess)Self-pruningvs.neighbor-designatingForwardingstatusdeterminesbyeachnodeitselforbyneighbors.BroadcastConnected-dominating-set-basedOnlydominatingnodesforwardthebroadcastpacket.Cluster-based(independentset)Onlyclusterheadsforwardthepacket,somegateways(thatconnecttwoadjacentclusters)areselectedtorelaythepacket.BroadcastDominantpruning(multipointrelays)Selectasubsetof1-hopneighbortocoverall2-hopneighborsBroadcastAgenericrule:Nodevhasanon-forwardingstatusifanytwoneighborsareconnectedbyapathconsistsofvisitednodesandnodeswithahigherpriorities.MulticastSource-initiatedprotocolsJoinReqandJoinReplyReceiver-initiatedprotocolsJoinReqandJoinAckTree-basedvs.mesh-basedSoft-statevs.hard-stateMulticastShortestpathtree:foraparticularmulticastCoretree:sharedtreeforallmulticastMulticasting:ODMRPOn-demandmulticastroutingprotocolMulticasting:MulticastAODVDealingwithMobilityNodemobilityisconsideredtobeundesirableinMANETsusingaconnection-basedmodelRecoversfromandtolerates“bad”effectscausedbymobilityNodesareassumedtoberelativelystableTwoSchemesRecoverySchem