移动自组网中的最长生命期路径

lSSN1000-9825，CODENRUXUEW JournalofSoftware,Vol】7．No3，March2006，PP_-498—509 DoT：10136060s170498 @2006byJournalofSoftwareAllrightsresetwed 移动自组网中的最长生命期路径 魏晓海1一，陈国良1,2，万颖瑜1,2张信明1,2 1(国家高性能计算中心(台肥)，安徽合肥230027) 2『中国科学技术大学计算机系，安徽台肥230027) LongestLifetimePathinMobileAdHoeNetworks WEIXiao．Hail≯，CHENGun．Lian91--，WANYing—Yul一，ZHANGXin．Min91，2 E-mail：jUS@iseasaccn ht吣；／／www．josorgcn Te押ax：+86-10—62562563 。(Natinna]HighPerformanceCol／1putingCenterutHefei。Hefei230027，China) 2(DepartmentofComputerScienceandTechnotogy，UniversityofScienceandTechnologyofClfina，Hefei230027，China) +Correspondingauthor：Phn：+86—551-3601013．Fax：+86-551-3601013，E-mail：wistoeh@mailIIStCeducn，http：／／mailustceducn／一wistoch WeiXH，ChenGL，WanYY，ZbaugXM．Longestlifetimepathinmobileadhoenetworks．Journalof Software，2006，17(3)：499-508．http：Hwwwdos．org．co／1000—9825／17／498。htm Abstract：Dynamictopologyistheessentialdifferencebetweenmobileadhocnetworksandotherkinds．Itis meaningfulinboththeoryandindustryapplicationtostudythedynamictopologyofmobileadhocnetworksIn thispaper,amethodisproposedtostudythedynamictopologywithlongestlifetimepath．Onbasisoftheprevious research，themathematicmodelofnetworksisimprovedtodescribethechangeoftopology，Basedonit，the algorithmoflongestlifetimepathispresentedandthedistributionofitsdurationisstudied．Atthesametime，itis provedthatthere—routingisminimalwiththelongestlifetimepathsastheroutesSimulationwithNS一2showsthat thedistributionoflognormalcallbeusedtodescribethedurationoflongestlifetimepathsTheresultsshowthatthe longestlifetimepathandminimalre—routingaremoresuitablethantheshortestpathasthemetricstomeasurethe dynamicofnetworks． Keywords：connectivity；mobileadboenetwork；pathduration；re·routing；QoS 摘要：动态拓扑是移动自组网区别于其他形式网络的本质特征，对其进行研究具有很犬的理论价值和工业 应用背景提出一种方法，利用网络的最长生命期路径来研究其拓扑的动态性在已有研究的基础上，改进了网络 的数学模型，弥补了以往模型无法很好地描述移动自组网动态拓扑的缺陷，并在此基础上提出了最长生命期路 轻算法．利用该算法计算网络中的最长生命期路径深八研究了其持续时间的分布规律同时证明了使用最长生 命期路径作为路由．可以使网络的重路由次数最少．模拟实验表明，利用对数正态分布可以很好地描述移动自组 网的最长生命期路径持续时间实验结果表明，与以往利用最短路径作为研究对象相比，最长生命期路径和最小 重路由更适合用来衡量网络的动态性 关键词：连通性：移动自组网；路径持续时间：重路由；QoS 中图法分类号：TP393 文献标识码：A ·SupposedbytheFoundationofScienceandTechnologyofHuaweiofClfinanDderGrantNoYJCB2004036WL(华为科技基金)； theInt’1ScholarExchangeFellowship(ISEF)oftheKoreaFoundationforAdvancedStudies滞围高等教育财团国际交换学者奖) Received2004-09-13：Accepted2005—05，i8 万方数据 魏晓海等：移动自组网中的最长生命期路径 l IntrOduction MobileAdHocnetworks(MANETs)havebeengainingincreasingpopularityinrecentyearsbecauseofcase ofdeployment．Amobileadhocnetworkisacollectionofmobilenodesthatarecapableofmovementandcanbe connecteddynamicallyinanarbitraryma／Mrler，ThereaRnowiredbasestationsorinfrastroenu-esupported．and eachhostcommunicateswithoneanotherviapacketradios，TherearemanyapplicationsofMANETst“．suchasin thebattlefield，emergency，andsearch—and—rescueoperationsetc． Recently，therehasbeenagreaterfocusonthemobilityandconnectivityofmobileadSacnetworksandalso theeffectofmobilityontheperformanceofroutingprotocols．M0bileadhocnetworksdifrerfromo血arkindsin thechangeoftopologystructurebecauseofmobility．Studylugthepropertiesofthemobilitymadconnectvltyis importantformobileadhocnetworksCurrentlyspeedofmovementisusedtoexpressthemobilityofthenetworks． However，thespeedcannotexpressthetopologystructurechangeverywellHighspeedofmovementdoesnot alwaysmeanweakconnectivity．Manyresearcheshavetriedtoexpresstheconnectivityoftheadhocnetworksin otherways．SomepropertiesofmobilityandconnectivityhavebeenobtainedbypreviousresearchersInRef．【2】， theauthorspresentsomefundamentalstochasticpropertiesofrandomwaypointmodel．ReE[3IanalyzesthePATH durationstatisticspropertiesandtheirimpactonreactiveMANETroutingprotocols．InRefi[4]，theIMPORTANT frameworkisproposedtosystematicanyanalyzetheeffectofmobilityonroutingprotocolsandsomepropertiesof linkdurationarepresentedThepath"inRefs【3，4】istheshortestpathbetweentwonodes． Whiletheresearcheshaveobtainedsomepropertiesoftheconnectivity．wefoundthereweredisadvantagesin thepreviousworkInstaticnetworks，everynodehasitsnodedegree,andlargenodedegreeisnotsuretoresultin largenodeconnectivity．Byanalogy，inmobileadhocnetworks，everylillkhasitslinkduration，andlonglink durationisnotsuretoresultinlong1ifetimeroute．Inmobileadhocnetworks．thedirecteffectto tlle communicationoftopologystructurechangeisthedes”oyoftherouteLinkbreakwillnotalwaysbreakthe communication．OnlypathdestroywillaffectthecommunicationSousinglinkdurationtoevaluatethe connectivityofthenetworkhasdisadvantagesInthispaper，weusepathdurationtoevaluatetheconnectivityofthe networksInmobileadhoenetworks，theremaybemorethanonepathbetweentwonodesPathselection correspondstotheroutingalgorithm．Differentroutingalgorithmswillresultindifferentpathdurations．Inorderto makethepathdurationindependentoftheroutingalgorithm,weusethelongestlifetimepathdurationasthemetric． ItisonlyrelatedtothenetworkitselfandsocanbeusedtoevaluatethedynamicpropertyofthenetworkWeuse thelongestlifetimepathasthemetricinsteadoftheshortestpathbecausethelongestlifetimepathdemonstratesthe communicationpotentialofthenetworks Atthesametime，weprovedthatusingthelongestlifetimepathsasroutescanresultinminimalre—routing．In mobileadhocnetworks，routingprotocolsarechallengedwithestablishingandmaintainingmulti—hopsroutesinthe theeofmobility，bandwidthlimitationandpowerconstraints，whichmwidelystudiedbythedomestic researchersmJ．Becauseofthemobility，re—routingismlavoidableinmobileadhocnetworksAvoidingthefrequent re—routingis criticalwhentheapplicationsrequirestableconnectionstoguaranteea certaindegreeofQoS Reducingre—routingcanbringdowntheloadofnetworkandbatetheconsumptionofnetworkresourcessuchas energy，bandwidthandsoon Oneoftheearliestwerksinthecontextofreducingre—routingisoubuildingstablerouteinmobileadboo networksAssociativityBasedRouting(ABR∥1prefersstablelinksovertransientlinks．Alinkwithlifetimeofat leastAfhresS22‰～isconsideredtobestable，whereFtxisthetransmissionrangeandvdenotestherelativespeedof tWOnodesInordertomeasurethelifetimeofa linkinABR，thenodeshavetobroadcasthellomessages periodicallySignalStabilityAdaptive(SSA)routing⋯differsstronglyconnectedlinksfromweaklyconnected 万方数据 JournalofSoftware软件学报Vol17，No3，March2006 links．Alinkisconsideredstronglyconnectedwhenithasbeenactiveforacertainpredefinedamotmtoftime Insuchroutingalgorithms．alinkwithlonglifetimeisconsideredasstable．Inordertopredictthelifetimeofa link，thedistanceandrelativespeedoftwonodesmustbeobtainedinthenetworkBecausethesignalstrength betweentwonodesisstronglyrelatedtothedistance，thechangeofthesignalstrengthcanbeusedtopredictthe lifetimeofalinkI”． IfthemobilenodesareequippedwithGPS，thedistanceandrelativespeedoftwonodescanbeobtainedby GPSSomepredictionmethodsbasedonGPShavebeenpresented[1“曩Afurtherapproachbasedonthe availabilityofGPSmeasurementshasbeensuggestedinRef．[13] Anothermethodofpredictin2thelifetimeofalinkisbasedonstatisticalanalysisandstochasticstl4,1 5】 Withpredictionoftheroutelifetime，routingalgorithmcanobtainbetterperformancebyselectinglong lifetimeandstablerouteTheheuristicalgorithmscanreducethere—routingofthenetworks．hutnoworkisdone theoreticallytoshowhowmuchthere—routingcanbereducedThereisnostandardtoevaluatetheperformanceof suchalgorithms Inourearlierworkll61,weattempttostudytheminimalre—routingofthemobileadhocnetworksandwehave presentedamethodtobalancetheminimalre—routingandminimalroutehopsInthispaper，wefocusonthe propertiesofthelongestlifetimepaths．Thelongestlifetimepathdurationandminimalre—routing aretwoimportant propertiesformobileadhocnetworks．Thesetwometricsrepresentthecommunicationpotentialofthenetworkand cltllbeusedtoevaluatethedynamicpropenyofthemobileadhocnetworks Thepaperisorganizedinthefollowingway．Section2presentsthenetworkmodelofthispaper，whichis differentwithpreviousonesandmoresuitableformobileadhoenetworksSection3describesthealgorithmto obtainthelongestlifutimepathfromacertaintimepoint．InSection4，weanalyzethepropertiesofthelongest lifutimepathdurationindetail，andSection5presentsthepropertiesoftheminimalre—routingofmobileadhoc networks．Section6istheconclusionandfuturework 2 NetworkModel GraphisusuallyusedtodenoteanetworkThevertexesinagraphrepresentthenodesinnetworkswhilean edgeofthegraphrepresentsalinkbetweentwonodes．Inmobileadhocnetworks．graphcandenotethesnapshotof thenetworkatacertaintime，butitCallnotdenotethechangeofthenetworktopology,Inmobileadhocnetworks， anactivelinkwilllastforaperiodoftimeandthenbecomedisconnectedbecauseofthemobilityTheprevious graphmodelscannotexpresssuchachangeverywell Inthispaper,amodifiedgraphispresentedtodenotethenetwork．LetG。(一D，whereVisthesetofnodes， andEisthesetof(id，ts，te)whichindicatesthatthenodesiandJareconnectedintheperiodof【0te]and disconnectedattimek and‘—sfuranyinfinitesimalpositivenumber￡Define(il^，tls,tl。)≤(12√2⋯t2乜)营 (il巾=(垃止)，f1{>-tztandtie≤屯pIfthereexistsapath0=Hu，Y／I，?12⋯，”扯l，月广订betweensandt，andforeachlink (ni,／l川)(0≤匹扣1)，9ejeE’，(月。，月⋯仆t如)sFpthenthereexistsafixedpathbetweenjandtwithin[tl，t2]． Figure1representssuchanetworkin[0，20]，andtheedgesindicatethatthecorrespondinglinkshaveexisted andtheactiveperiodsarelisted．Forexample，node0 and1 isconnectedinperiodof[O，3]，【5，10]，[13，20]and disconnectedma11othertimes． 万方数据 魏晓海等：移动自组网中的最长生命期路径 8，i3) m)跚。廊，20)汝][12，17／[4拍【o，N8,201 3 LongestLifetimePath 0 【O，10][1 乏 ≮ ≮ }如)【o，12】[1幽) Fig．1Networkmode 501 Inthissection，wewillpresentanalgorithmtofindasinglelongestlifetimepathbetweentwonodesfroma giventimepoint Inthisalgorithm，wewanttofindalongesttimeslicefromcertaintimepointtwithinwhichthereexistsa fixedpathInthetimeslice，thepathshouldnotbedestroyed，sowecanderiveaweightedgraphG’(0fromhe networkmodelwepresent．G’(0=(r，F)，wherev∈矿骨r∈Vande=(1，，w)eE'c，3(id，‘，te)eEandt,≤t