DTN中的路由技术(英文版）.ppt

MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,QingsiWang,XinbingWangDepartmentofElectronicEngineeringShanghaiJiaoTongUniversity,ChinaXiaojunLinDepartmentofElectricalandComputerEngineeringPurdueUniversity,USA,MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,2,Outline,IntroductionBackgroundMotivationsObjectivesK-hopClusteredNetworkModelsMainResultsandIntuitionsTheImpactofMobilityConcludingRemarks,3,BackgroundI/II,Connectivityisabasicconcernindesigningandimplementingwirelessnetworks.Threemainschemesofconnectingstrategiesareproposedintheliterature.Distance-basedstrategyNumber-of-neighbor-basedstrategySector-basedstrategy,MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,4,BackgroundII/II,Theconnectivityofnetworksunderthedistance-basedconnectingstrategyiswidelystudied:Thecriticalvalueof,overallconnectivitycanbeestablishedwithprobabilityapproachingoneasifandonlyif12.,MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,1P.GuptaandP.R.Kumar,“CriticalPowerforAsymptoticConnectivityinWirelessNetworks”,1998.2M.D.Penrose,“TheLongestEdgeoftheRandomMinimalSpanningTree”,1997.,5,Motivation,Thenetworkmodelsstudiedinthesepriorworksarenon-clustered(orflat)andstationarynetworks.Clusteringandmobilityhavebeenfoundtoimprovevariousaspectsofnetworkperformance.Studiesontheconnectivityofmobileandclusterednetworksarequitelimited.-Wedontevenknowthedefinitionoftheconnectivityundersuchcircumstances.,MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,6,ObjectiveI/II,Openquestion:Whatistheimpactofmobilityonconnectivityofclusterednetworkssubjecttodelayconstraints?WestudyThecriticaltransmissionrangeforconnectivityK-hopmobileclusterednetworks(delayguarantee)Randomwalkmobilitymodelwithnon-trivialvelocityi.i.d.mobilitymodel(fastmobility).,MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,7,ObjectiveII/II,Wecomparewiththecriticaltransmissionrangeforconnectivityinstationaryk-hopclusterednetworks.Implicationsonthepower-delaytrade-offtheenergyefficiencyOurresultsshowthat:Mobilitydoesimproveconnectivityink-hopclusterednetworks,anditalsosignificantlydecreasestheenergyconsumptionandthepower-delaytrade-off.,8,Outline,IntroductionK-hopClusteredNetworkModelsAnoverviewofflatnetworksK-hopclusterednetworkmodelsMainResultsandIntuitionsTheImpactofMobilityConcludingRemarks,MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,9,AnOverviewofFlatNetworks,DefiningConnectivityinFlatNetworksLetAdenoteaunitareainR2,andG(n)bethegraphformedwhennnodesareplaceduniformlyandindependentlyinA.Anedgeeijexistsbetweentwonodesiandj,ifthedistancebetweenthemislessthanr(n)underthedistance-basedstrategy.,Flatnetworksunderthedistance-basedconnectingstrategy,MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,10,K-hopClusteredNetworkModels,Clusterednetworksnnormalnodesandndcluster-headnodesStaticormobileMobilityModelRandomWalkMobilityModelwithNon-TrivialVelocityUniformlychosendirectionConstantvelocity(continuouspath)I.I.D.MobilityModelIndependentlyanduniformlyreshuffledStaticwithinasingletimeslot,MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,11,MobileNetworks:TransmissionScheme,TTL(timetolive):thenumberofhopsthatthepackethasbeenforwarded.SYN(synchronize):preamblefordata-flowssynchroni-zation,MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,12,MobileNetworks:RoutingStrategy,Directdeliverytotheclusterheadwithoutrelay,MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,13,ClusteredNetworkModels,Forstationaryk-hopclusterednetworks,wesaythataclustermemberisconnectedifitcanreachaclusterheadwithinkhops.Formobileclusterednetworks,aclustermemberisconnectedifitcanreachaclusterheadwithinkslots.Ifalltheclustermembersinanetworkareconnected,wedefinethatthenetworkhasfullconnectivity.,MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,14,Outline,IntroductionK-hopClusteredNetworkModelsMainResultsandIntuitionsDefinitionofcriticaltransmissionrangeMainresultsIntuitiveexplanationsTheImpactofMobilityConcludingRemarks,MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,15,CriticalTransmissionRange,Definition:Forstationaryormobilek-hopclusterednetworks,r(n)isthecriticaltransmissionrangeifE:theeventthatallclustermembersareconnected,MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,16,MainResults,Undertherandomwalkmobilitypattern,thecriticaltransmissionrangeis,wheredistheclusterheadexponent,0d1,andvisthevelocityofallmembernodes.Underthei.i.d.mobilitypattern,thecriticaltransmissionrangeis,where1/kd1.Forstationaryk-hopclusterednetworks,thecriticaltransmissionrangeis,where0d1.,MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,17,IntuitiveExplanationsI/II,Supposetherearenclustermembersandndclusterheadsuniformlydistributedinaunitsquare.Thus,roughlyspeaking,thereisoneclusterheadwithinanareaof1/nd.Areaargumentforrandomwalkmobility:,MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,18,IntuitiveExplanationsI/II,Areaargumentfori.i.dmobility:,MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,19,IntuitiveExplanationsII/II,Areaargumentforstaticcase:,MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,kr(n),20,Outline,IntroductionK-hopClusteredNetworkModelsMainResultsandIntuitionsTheImpactofMobilityTransmissionpowerEnergyconsumptionperflowDiscussionConcludingRemarks,MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,21,TransmissionPowerI/II,Weassumethefreespacepropagationmodel,i.e.,Pt=transmissionpowerofanisotropicsource,Gt=transmittingantennagain,Gr=receivingantennagain,l=propagationdistancebetweenantennas,=carrierwavelength.ReplacePrwithPrthandreplacethepropagationdistancelbythetransmissionranger.Wethenhave,MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,22,EnergyConsumption,Letdenotetheenergyconsumptionperflow.whereistheaveragenumberofhopsperflow.Pvidesapictureofthelife-timeexpectationbothofeachsinglenodeandoftheentirenetwork.,MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,23,DiscussionI/VI,Notethatinthesecalculations,wehaveignoredtheenergyconsumptionduetomobility.Hence,theseresultsshouldnotbeinterpretedasareasontointroducemobilitytoanotherwisestaticnetwork,butratherrepresentaninherentadvantageofhavingmobilityinthesystem.Similarly,thecomparisonwiththeflatnetworkisnotentirelyfair,sinceinaclusterednetwork,apacketonlyneedstoreachaclusterhead.Hence,ourfollowingresultsshouldbeviewedasaninherentadvantageofclusterednetworkduetotheavailabilityofinfrastructuresupport.,MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,24,DiscussionII/VI,Usingthepreviousresultsofthecriticaltransmissionranger(n),wecancomputetheorderofPtand.Alltheresultsinthispaperarereportedinthefollowingtable.,MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,25,DiscussionIII/VI,Wehave3randomwalkmobilitywithclusteringcanincreasethenumberoftransmissionthatanodecanundertakeandextendthelife-timebothofeachsinglenodeandoftheentirenetwork.,MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,3Note:Bytheimplicationfrom27,weknowthatwhend1/2inourfollowingdiscussion.,27S.Toumpis,“CapacityBoundsforThreeClassesofWirelessNetworks:Asymmetric,Cluster,andHybrid”,2004.,26,DiscussionIV/VI,WehaveToidentifythecontributionofmobilityandk-hopclusteringontheimprovementofnetworkperformance,wehave,MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,27,DiscussionV/VI,WehaveFromtheperspectiveofenergyconsumptionperflow,clusterednetworkshaveaninherentadvantageintermsofenergy-efficiencyduetotheavailabilityofinfrastructuresupport.Mobilek-hopclusterednetworksunderthei.i.dmobilitymodelandstationaryclusterednetworksmayhavecomparableperformanceandthiscanbeunderstoodintuitivelysincenodesunderthei.i.d.mobilitymodelactuallyremainstaticduringthetime-slot.,MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,28,DiscussionVI/VI,Inconclusion,randomwalkmobilitywithnon-trivialvelocityincreasesconnectivityink-hopclusterednetworks,andthussignificantlyimprovestheenergyefficiencyandthepower-delaytrade-offofthenetwork.,MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,29,Outline,IntroductionK-hopClusteredNetworkModelsMainResultsandIntuitionsTheImpactofMobilityConcludingRemarks,MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,30,ConcludingRemarksI/II,Wehavestudiedtheeffectsofmobilityonthecriticaltransmissionrangeforasymptoticconnectivityink-hopclusterednetworks.Ourcontributionsaretwofold.developedthecriticaltransmissionrangeforthemobilek-hopclusterednetworkundertherandomwalkmobilitymodelwithnon-trivialvelocityandthei.i.d.mobilitymodel,andforthestationaryk-hopclusterednetwork,respectively.Theseformulationsnotonlyprovideanasymptoticdescriptionofthecriticalpowerneededtomaintaintheconnectivityofthenetwork,butalsohelptoidentifythecontributionofmobilityintheimprovementofnetworkperformance.,MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,31,ConcludingRemarksII/II,Forfuturework:Extendtheresultsfortherandomwalkmobilitymodeltoaccountforthecasewhereeachnodemoveswithdifferentspeed;Inourcurrentmodelforrandomwalk,eachnodechangesdirectionafteronetime-slot.Aninterestingextensionistostudythecasewherethechangeofdirectionsoccursatrandomtimes(e.g.,anodemaymovearandomdistancebeforeitchangesdirection).Accountforwirelessinterferenceinthesystem.Itwouldbeinterestingtostudythecasewherecluster-headsmaymoveaswell.,MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,Thankyou!,33,ReferenceI/II,1P.GuptaandP.R.Kumar,“CriticalPowerforAsymptoticConnectivityinWirelessNetworks,”StochasticAnalysis,Control,OptimizationandApplications:AVolumeinHonorofW.H.Fleming,W.M.McEneaney,G.Yin,andQ.Zhang,Boston:Birkhauser,1998.2M.D.Penrose,“TheLongestEdgeoftheRandomMinimalSpanningTree,”AnnalsofAppliedProbability,vol.7,pp.340-361,1997.8P.GuptaandP.R.Kumar,“TheCapacityofWirelessNetworks,”IEEETransactionsonInformationTheory,vol.46,pp.388-404,March2000.9P.Gupta,R.Gray,andP.R.Kumar,“AnExperimentalScalingLawforAdHocNetworks,”Univ.ofIllinoisatUrbana-Champaign,May2001.10W.Heinzelman,A.ChandrakasanandH.Balakrishnan,“Energy-efficientCommunicationProtocolforWirelessMicroSensorNetworks,”inProc.the33rdAnnualHawaiiInternationalConferenceonSystemSciences,pp.3005-3014,2000.11QiangfengJiangandD.Manivannan,“RoutingProtocolsforSensorNetworks,”inConsumerCommunicationsandNetworkingConference(CCNC2004),pp.93-98,2004.19U.KozatandL.Tassiulas,“Throughputcapacityofrandomadhocnetworkswithinfrastructuresupport,”inProc.ACMMobiCom2003,Annapolis,MD,USA,June2003.20M.GrossglauserandD.Tse,“MobilityIncreasestheCapacityofAdHocWirelessNetworks,”IEEE/ACMTransactionsonNetworking,vol.10,no.4,pp.477-486,August2002.,MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,34,ReferenceII/II,21S.apkun,J.HubauxandL.Buttyn,“MobilityHelpsSecurityinAdHocNetworks,”inProc.ACMMobiHoc2003,June2003.27S.Toumpis,“CapacityBoundsforThreeClassesofWirelessNetworks:Asymmetric,Cluster,andHybrid,”inProc.ACMMobiHoc2004,pp.133-144,Roppongi,Japan,May24-26,2004.,MobilityIncreasestheConnectivityofK-hopClusteredWirelessNetworks,35,MobilityPatternII/II,Duetotheassumptionthatv=(1),themixingtimeunderther.w.mobilitymodelisonthesameorderasthemixingtimeunderthei.i.d.mobilitymodel.However,sinceunderther.w.mobilitymodelnodescancommunicateduringthecourseofmovement,theywillhaveahigherchancetoconnecttotheclusterheadcomparedtonodesunderthei.i.d.mobilitymodel.1,1Note:Th