Exploiting Mobility in Large Scale Ad Hoc Wireless

ExploitingMobilityinLargeScaleAdHocWirelessNetworksMarioGerla,KaixinXuComputerScienceDepartmentUniversityofCalifornia,LosAngelesEmail:fgerla,[e-mail]ienceDepartmentUniversityofAlabamaEmail:[e-mail]—Mobilityisgenerallyviewedasamajorimpedimentinthecontrolandmanagementoflargescalewirelessnetworks.However,recentlyresearchershavelookedatmobilityinadiffer-entway,tryingtotakeadvantageofitinsteadofprotectingfromit.Intheliterature,mobilityisgenerallymodeledasindependentrandommovesbyeachnode.However,inreality,mobilenodestendtoshowsomedegreeofcorrelated(grouporiented)motionbehavior.Thisfeature,oncedetectedandunderstood,canbeexploitedtohelpimprovenetworkperformance,inparticular,scalability.Inthispaper,wepresentseveralschemesforexploringmobilitypatterns,inparticulargroupmobility.Weshow,viasimulations,thatthephysicalgroupmobilitybehaviorofmobilenodescanbeautonomouslyrecognizedanddiscoveredbythenetworklayerroutingschemes.Itcanthenbeutilizedtoreduceroutingoverheadandachievegoodscalabilityinlargescaleadhocnetworks.I.INTRODUCTIONMobilityisgenerallyviewedasamajorimpedimentinthecontrolandmanagementoflargescalewirelessnetworks.Infact,withoutmobility(ie,stationarynodes),ahierarchicalclusteringandaddressingscheme(ofthetypeusedintheInternet)couldbeeasilyappliedtomanagerouting,forexam-ple.Unfortunately,asnodesmove,thehierarchicalpartitioningstructurealsochanges,forcingfrequenthierarchicaladdresschangesfollowedbyupdatebroadcaststotheentirenetwork-averyresourceconsumingpropositionthatcaneasilycongesttheentirenetwork.Ondemandroutingisimmunefromthebackgroundupdateoverheadexperiencedbyhierarchicalroutingsinceroutesarecomputedonlyasneeded.However,highmobilitywillinthiscaseforcethefrequentrecomputationofondemandroutes,leadingtoexcessiveO/Hwhenthetrafficpatternisdense.Tobreakthisseeminglyinevitableimpasseresearchershavelookedatmobilityinadifferentway,tryingtotakeadvantageofitinsteadofprotectingfromit.Inthispaperwewillciteseveralexampleswheremobilitywashelpfulinovercomingscalingproblems.Tostart,inthestudyofcommunicationsintheautomatedbattlefieldonenoticesthatnodesmoveingroups(eg,tankbattalion,infantrycompany,UAVswarm,etc).Thissuggeststhatahierarchicalorganizationwherepar-titionsarebasedon“motionaffinity”ratherthan“geographicproximity”wouldbemorerobusttomotion.Thisprinciplehasleadtothesuccessfuldevelopmentofseveralmotion-robust,scalableroutingalgorithms.Wewillpresentonesuchalgorithm-LANMAR-andreportonitsperformance.Asecondexamplethatwewillreportistheuseofmobilenodesascarriersofroutinginformation.Inthiscase,groupmobilityisnotrequiredandrandommotionisfine.Thetypicalscenariowouldbetheurbantrafficgridwherecarsareequippedwithadhocradios.Imagineacarcontinuously“sniffs”theneighborhoodandlearns/storespassingcarIDs.ItthuscarriesaroundinitscachetheinfoaboutcarIDsitsawbefore.Assumingcarsmoverandomlyanduniformlyinthegrid,eventuallyatrailofcars-likepointers-isformed,tracingbacktoeachcarID.Thesuperpositionofthesetrailsisatree-itisaroutingtreethatcanbeusedtosendmessagesbacktosource.Therecentlyproposed”Lastencounter”routingschemeisbasedonthisprinciple:thenexthoptodestinationDisthecarthathasthemostrecentrecordofsuchdestination.Thisschemehasseveralbenefits.First,itavoidsperiodicrouteadvertisingoverheadandregistrationtolocationserver(toDNS,say).Inthisrespect,itremindsusofOnDemandrouting.However,iteliminatesthemajordrawbackofOnDemandroutingnamelyglobalfloodsearch(tofindthedestination).OnefinalexamplethatwewilldiscussistheInfo-Stations(ISs)deployedeveryfewkilometersalongthehighway.EachISisconnectedtothebroadbandInternet.ThecarcanpredictthetimewhenitwillbeinfrontofthenextIS.The“intelligentrouter”onboardofthecarwillthusdelaytheupanddownloadingofnontime-criticalfilesuntilitiswithinreachoftheinfostation.Thisisanexamplewheremotioncandramaticallyincreasethecapacityofawirelessnetwork.Therestofthepaperisorganizedasfollowing.InsectionII,webrieflyreviewhowthephysicalgroupmobilitybehaviorofmobilenodesaremodeled.WethenpresenttheschemeofdynamicallydiscoveringthesegroupinsectionIII.InsectionIV,LANMARroutingscheme,whichexploresthegroupmobilitybehaviorofnodesispresentedandevaluated.ThepaperisconcludedinsectionV.II.GROUPMOBILITYMODELMobileAdHocNetworks(MANETs)havefoundmanyapplicationsintacticalcommunications(militaryandlawenforcement)andcivilianforums(conventioncenters,con-ferences,sensornetworksandcarnetworks).InthestudyofcommunicationsintheautomatedbattlefieldonenoticesRP(t+1)RP(t)GMRM1gV2gVFig.1.GroupMobilityModelthatmobilenodesareoftenorganizedingroups(eg,tankbattalion,infantrycompany,UAVswarm,etc.)withdifferenttasksand,correspondingly,differentfunctionalandoperationalcharacteristics,e.g.,organizedgroupsofsmallunmannedground,seaandairbornevehiclestolaunchcomplexmissionsthatcompriseseveralsuchgroups.Morepossibleapplicationsinclude:coordinatedaerialsweepofvasturban/suburbanar-eastotracksuspects,searchandrescueoperationsinareasunfriendlytohumans(e.g.,chemicalspills,terroristattacks,etc),explorationofremoteplanets,reconnaissanceofenemyfield