移动自组织网络.ppt

JieWuDepartmentofComputerandInformationSciencesTempleUniversityPhiladelphia,PA19122,CIS9590AdHocNetworks(PartII),TableofContents,IntroductionInfrastructurednetworksHandofflocationmanagement(mobileIP)channelassignment,TableofContents(contd.),InfrastructurelessnetworksWirelessMAC(IEEE802.11andBluetooth)AdHocRoutingProtocolsMulticastingandBroadcastingSecurityNetworkCoding,TableofContents(contd.),Infrastructurelessnetworks(contd.)PowerOptimizationApplicationsSensornetworksandindoorwirelessenvironmentsPervasivecomputingSocialnetworksSampleon-goingprojects,AdHocWirelessNetworks(Infrastructurelessnetworks),Anadhocnetworkisacollectionofwirelessmobilehostformingatemporarynetworkwithouttheaidofanycentralizedadministrationorstandardsupportservicesregularlyavailableonthewideareanetworktowhichthehostsmaynormallybeconnected(JohnsonandMaltz),AdHocWirelessNetworks(Infrastructurelessnetworks),Manet(mobileadhocnetworks)MobiledistributedmultihopwirelessnetworksTemporaryinnatureNobasestationandrapidlydeployableNeighborhoodawarenessMultiple-hopcommunicationUnitdiskgraph:hostconnectionbasedongeographicaldistance,SampleAdHocNetworks,SensornetworksIndoorwirelessapplicationsMeshnetworksPeople-basednetworks“smallworld”thatareverylargegraphsthattendtobesparse,clustered,andhaveasmalldiameter.“sixdegreeofseparation”,Self-organizing:withoutcentralizedcontrolScarceresources:bandwidthandbatteriesDynamicnetworktopology,Characteristics,UnitDiskGraph,Figure1:Asimpleadhocwirelessnetworkoffivewirelessmobilehosts.,Defenseindustry(battlefield)LawenforcementAcademicinstitutions(conferenceandmeeting)PersonalareanetworksandBluetoothHomenetworkingEmbeddingcomputingapplicationsHealthfacilitiesDisasterrecovery(search-and-rescue),Applications,Applications,MobilitymanagementAddressingandrouting*LocationtrackingAbsolutevs.Relative,GPSNetworkmanagementMergeandsplitResourcemanagementNetworksresourceallocationandenergyefficiencyQoSmanagement*Dynamicadvancereservationandadaptiveerrorcontroltechniques,MajorIssues,MACprotocols*Contentionvs.contention-freeApplicationsandmiddlewareMeasurementandexperimentationSecurity*Authentication,encryption,anonymity,andintrusiondetectionErrorcontrolandfailureErrorcorrectionandretransmission,deploymentofback-upsystemsNetworkcodingReducenumberoftransmissions,MajorIssues(Contd.),IssuestobeCovered,WirelessMediaAccessProtocols(MAC)AdHocRoutingProtocolsMulticastingandBroadcastingPowerOptimizationSecurityNetworkCoding,WirelessMAC,AMAC(MediaAccessProtocol)isasetofrulesorprocedurestoallowtheefficientuseofasharedmedium.Contentionvs.contention-freeSender-initiatedvs.receiver-initiated,WirelessMAC:MajorIssues,DistributedoperationsSynchronizationHiddenterminalsExposedterminalsThroughputAccessdelayFairness,Real-timetrafficResourcereservationAbilitytomeasureresourceavailabilityPowerandratecontrolDirectionalantennas,WirelessMAC,Contention-basedALOHA:nocollisionavoidancePure:transmittedatarbitrarytimeSlotted:transmittedatstartofatimeslotp-persistent:slottedandtransmittedwithaprobabilityp,WirelessMAC,CarrierSenseMultipleAccess(CSMA):listentodeterminewhetherthereisactivityonthechannelPersistent:continuouslylistensNonpersistent:waitsarandomamountoftimebeforere-testingp-persistent:slottedandtransmitwhenidlewithaprobabilityofp,WirelessMAC,Contention-freeprotocolsBit-mapprotocol:eachcontentionperiodconsistsofNslots.Binarycountdown:usebinarystationaddressinbidding.HybridMixedcontention-freewithcontention,WirelessMAC,HiddenTerminalProblemTwonodes,hiddenfromoneanother(outoftransmissionrange),attempttosendinformationtothesamereceivingnode.Packetcollisions.ExposedNodeProblemAnodeisinhibitedfromtransmittingtoothernodesonoverhearingapackettransmission.Wastedbandwidth.,WirelessMAC,Sender-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,Samplecollision,RTS-CTSproblem1,Samplecollision,RTS-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(TRIRSR)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),TsengsPower-savingProtocols:UseperiodicactivewindowtodiscoverneighborsOverlappingAwakeIntervalsWake-upPrediction,PowerSaving,Dominating-Awake-IntervalProtocol,PowerSaving,Periodically-Fully-Awake-Interval,PowerSaving,Quorum-BasedProtocols,IEEE802.11,TwooperationalmodesInfrastructure-basedInfrastructurelessoradhocTwotypesofserviceattheMAClayerContention-freeservicebyDistributedCoordinationFunction:DCFContention-freeservicebyPointCoordinationFunction:PCF,IEEE802.11,TwooperationalmodesInfrastructure-basedInfrastructurelessoradhocTwotypesofserviceattheMAClayerContention-freeservicebyDistributedCoordinationFunction:DCFContention-freeservicebyPointCoordinationFunction:PCF,IEEE802-11,RTS-CTShandshake,IEEE802.11,RTS-CTShandshakeRTS(requesttosend)CTS(cleartosend)DatatrasmissionAckOtheritemsNetworkAllocationVector(NAV)DistributedInterFrameSpace(DIFS)ShortInterFrameSpace(SIFS)Backofftime,IEEE802.11,RTS-CTS:contentionDatatransmissionLcontention-freeNAVsetupcannotworkproperlywhentherearecollisionsAllpackets:RTS,CTS,Data,AckaresubjecttocollisionsSIFSDIFStoincreasethepriorityBackofftime:anintegerfrom(0,CW-1),whereCW(contentionwindow)isdoubledateachretransmission,RoutinginAdHocNetworks,Types:(n:networksize)Unicasting:(1,1)=(source,destination)Multicasting:(1,k),1knBroadcasting:(1,n)Geocasting:(1,kinaregion)Gossip:(n,n)Gathering:(k,1)Fusion:aspecialtypeofgathering(withsimpledataprocessingatintermediatenodes),RoutinginAdHocNetworks,Qualitativeproperties:DistributedoperationLoop-freedomDemand-basedoperationProactiveoperationSecuritySleepperiodoperationUnidirectionallinksupport,RoutinginAdHocNetworks,Quantitativemetrics:End-to-enddatathroughputanddelayRouteacquisitiontimePercentageout-of-orderdeliveryEfficiency,BasicRoutingStrategiesinInternet,SourceRoutingvs.DistributedRouting,Figure2:Asamplesourcerouting,Figure3:Asampledistributedrouting,Classification,Proactivevs.reactiveproactive:continuouslyevaluatenetworkconnectivityreactive:invokearoutedeterminationprocedureon-demand.RightbalancebetweenproactiveandreactiveFlatvs.hierarchical,SampleProtocols,ProactiveProtocolsDestinationsequenceddistancevector(DSDV)ReactiveProtocolsDynamicsourcerouting(DSR)Adhocon-demanddistancevectorrouting(AODV)Temporallyorderedroutingalgorithms(TORA),SampleProtocols,Hybrid:ZoneroutingHierarchicalCluster-basedConnected-dominating-set-based,Proactive:DSDV,BasedonBellman-FordroutingalgorithmsEnhancedwithfreedomfromloops.Enhancedwithdifferentiationofstaleroutesfromnewonesbysequencenumbers.,Reactive,ThreestepsRoutediscoveryDataforwardingRoutemaintenance,DSR,Therearenoperiodicroutingadvertisementmessages(therebyreducingnetworkbandwidthoverhead).Eachhostmaintainsaroutecache:sourceroutesthatithaslearned.Ifarouteisnotfoundfromroutecache,thesourceattemptstodiscoveroneusingroutediscovery.Routemaintenancemonitorsthecorrectoperationofarouteinuse.,DSRRouting(Contd.),AsampleDSRroutediscovery,AODV,CombinationofDSRandDSDVRoutingtableisconstructedondemand.Sequencenumbers(issuedfromdifferentdestinations)areusedtoavoidloopingThenodeshouldrespond(ROUTE_REPLY)arequest(ROUTE_REQ)ifItisthedestinationnodeAnintermediatenodewitharouteofadestinationsequencenumbernolessthanthatintherequestpacket.,TORA,Foreachdestination,aDAGismaintainedwithdestinationasthesink:Eachnodehasaheightmetric.Adirectedlinkalwayspointstoanodewithalowerheightmetric.Tosendapacket,ahostforwardsthepackettoanyneighborwithalowermetric.,Proactive:DataForwarding,Sourcerouting:centralizedatthesourceDistributedrouting:decentralizedMultiplepaths,Proactive:RouteMaintenance,Sourceroutingvs.distributedrouting.Globalre-constructionvs.localfixSinglepathvs.multiplepath,TORA:routemaintenance,FullreversalAteachiterationeachnodeotherthanthedestinationthathasnooutgoinglinkreversesthedirectionsofallitsincominglinks.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(Contd.),Figure5:Zonerouting,Hiearchical:Domination-set-based,Schoolbusrouting,Graph-theoreticDefinition,AsetinG(V,E)isdominatingifallthenodesinthesystemareeitherinthesetorneighborsofnodesintheset.,Five-QueenProblem(1850s),DesirableFeatures,SimpleandquickConnecteddominatingset,Figure6:Asimpleadhocwirelessnetworkoffivewirelessmobilehosts.,ExistingApproaches,Graphtheorycommunity:Boundsonthedominationnumber(Haynes,Hedetniemi,andSlater,1998).Specialclassesofgraphforwhichthedominationproblemcanbesolvedinpolynomialtime.,ExistingApproaches(Contd.),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(Contd.),blacknodes=CDS(connecteddominatingset),Figure7:MCDSasanapproximationofCDS,Spanning-tree-based(Wan,Alzoubi,andFrieder,IIT),Aspanningtreerootedatv(selectedthroughanelectionprocess)isfirstconstructed.Nodesarelabeledaccordingtoatopologicalsortingorderofthetree.,Spanning-tree-based(Contd.),Nodesaremarkedbasedontheirpositionsintheorderstartingfromrootv.Allnodesarewhiteinitially.Vismarkedblackandallnodesarelabeledblackunlessthereisablackneighbor.Eachblacknode(exceptrootv)selectsaneighborwiththelargestlabelbutsmallerthanitsownlabelandmarkitgray.,Spanning-tree-based(Contd.),blacknodes=DSblacknodes+graynodes=CDS,Figure8:selectingCDSinaspanningtree,Cluster-based(LeeandGerla,UCLA),Allnodesareinitiallywhite.Whenawhitenodefindsitselfhavingthelowestidamongallitswhiteneighbors,itbecomesaclusterheadandcolorsitselfblack.Allitsneighborsjoinintheclusterandchangetheircolorstogray.,Cluster-based(Contd.),Repeatsteps(1)and(2)untilthereisnowhitenodeleft.Specialgraynodes:graynodesthathavetwoneighborsindifferentclusters.,Cluster-based(Contd.),blacknodes=DSblacknodes+specialgraynodes=CDS,Figure9:sequentialpropagationinthecluster-basedapproach.,LocalizedAlgorithms,Processors(hosts)onlyinteractwithothersinarestrictedvicinity.Eachprocessorperformsexceedinglysimpletasks(suchasmaintainingandpropagatinginformationmarkers).Collectivelytheseprocessorsachieveadesiredglobalobjective.Thereisnosequentialpropagationofinformation.,MarkingProcess(WuandLi,1999),Anodeismarkedtrueifithastwounconnectedneighbors.Asetofmarkednodes(gatewaysnodes)Vformaconnecteddominatingset.,MarkingProcess(Contd.),Figure10:Asampleadhocwirelessnetwork,Dominating-set-basedRouting,Ifthesourceisnotagatewayhost,itforwardspacketstoasourcegatewayneighbor.Thissourcegatewayactsasanewsourcetoroutepacketsintheinducedgraphgeneratedfromtheconnecteddominatingset.Eventually,packetsreachadestinationgateway,whichiseitherthedestinationhostitselforagatewayofthedestinationhost.,DominatingSetReduction,Reducethesizeofthedominatingset.Roleofgateway/non-gatewayisrotated.,DominatingSetReduction(Contd.),Nv=N(v)UvisaclosedneighborsetofvRule1:IfNvNuinGandid(v)id(u),thenunmarkv.Rule2:IfN(v)N(u)UN(w)inGandid(v)=minid(v),id(u),id(w),thenunmarkv.,DominatingSetReduction(Contd.),Figure12:twosampleexamples,Example,Figure13:(a)Dominatingsetfromthemarkingprocess(b)Dominatingsetafterdominatingsetreduction,DirectedNetworks:dominatingnodeandabsorbantnode,Figure15:Dominatingandabsorbantnodes,DirectedNetworks(Contd.),Findingasubsetthatisbothdominatingandabsorbant(Wu,IEEETPDS2002).,Figure16:Anabsorbantsetandadominatingset,MobilityManagement,Update/re-calculationon/offmovementrecognizinganewlinkrecognizingabrokenlinkLocalizedmaintenance(update),QoSrouting,Wirelesslinksbandwidthmaybeaffectedbythetransmissionactivitiesofadjacentlinks.Unlikeone-hopnetwork(cellular),onemustguaranteethequalityofmultiplehopsinapath.Existinglinksmaydisappearandnewlinksmaybeformedasmobilehostsmove.,QoS:Signalstability-basedadaptive(SSA),Eachnodemaintainsasignalstabilitytable.AreceivingnodepropagatesarequestifTherequestisreceivedoverastronglink.TherequesthanotbeenforwardedpreviouslyThelevelofqualifycanbeloweredatthesourceifthesourcefailtoreceiveareplywithinatime-outperiod.,QoS:Ticket-basedrouting,Eachprobingpacketcarriesanumberoftickets.Thenumberofroute-searchingpacketsisconfinedtoavoidblindflooding.,Hierarchicalroutingprotocols,Hierarchicalstaterouting(HSR)Multi-levelclusteringAnodecanbeaheadatdifferentlevels,Hierarchicalroutingprotocols,Zone-basedRoutingProtocol(ZRP)Proactiveintra-zoneandreactiveinter-zone.FisheyeStateRoutingProtocol(FSR)Afishseyethatcancapturepixelinformationwithgreateraccuracynearitsevesfocalpoint.Thefrequencyofexchangesdecreaseswithanincreaseinscope.,GeometricRouting,GPS-basedroutingThespaceispartitionedintoa2dgridOneclusterheadisselectedineachgridpoint.SparseagraphGabrielgraph:linkuvexistsifftheopendiskwithdiameteruvcontainsnoothernodes.RNG(relativeneighborhoodgraph):linkexistsifd(u,v)d(u,w)andd(u,v)d(v,w).Yaograph:Foreachnodeu,anyk(k6)equal-separatedraysoriginatedatudefinekcones.Ineachcone,choosetheclosetv(ifany)withinthetransmitterrangeofuandaddadirectedlink(u,v).,Samples,GeometricRouting,GreedyalgorithmClosertothedestinationDifferentgreedy:mostforwardingprogresswithinradiusFaceroutingRouteonafaceinGabrielgraphAlternatebetweenright-handandleft-handruleatintersection(ofthelineconnectedsourceanddest.)Greedy-Face-GreedyGFGonCDS,Sample,CollectiveCommunication,Broadcast:onesourceandalldestinations.Multicast:onesourceandmanydestinations.,Broadcast:BlindFlooding,Redundanttransmissionmaycausecontentionandcollision,Broadcast,Staticvs.dynamicForwardingstatusdeterminedbeforeorafterthebroadcastprocess)Self-pruningvs.neighbor-designatingForwardingstatusdeterminesbyeachnodeitselforbyneighbors.,Broadcast,Connected-dominating-set-basedOnlydominatingnodesforwardthebroadcastpacket.Cluster-based(independentset)Onlyclusterheadsforwardthepacket,somegateways(thatconnecttwoadjacentclusters)areselectedtorelaythepacket.,Broadcast,Dominantpruning(multipointrelays)Selectasubsetof1-hopneighbortocoverall2-hopneighbors,Broadcast,Agenericrule:Nodevhasanon-forwardingstatusifanytwoneighborsareconnectedbyapathconsistsofvisitednodesandnodeswithahigherpriorities.,Multicast,Source-initiatedprotocolsJoinReqandJoinReplyReceiver-initiatedprotocolsJoinReqandJoinAckTree-basedvs.mesh-basedSoft-statevs.hard-state,Multicast,Shortestpathtree:foraparticularmulticastCoretree:sharedtreeforallmulticast,Multicasting:ODMRP,On-demandmulticastroutingprotocol,Multicasting:MulticastAODV,DealingwithMobility,NodemobilityisconsideredtobeundesirableinMANETsusingac