Location-aided routing (LAR) in mobile ad hoc netw

WirelessNetworks6(2000)307–321307Location-AidedRouting(LAR)inmobileadhocnetworksYoung-BaeKoandNitinH.VaidyaDepartmentofComputerScience,TexasA&MUniversity,CollegeStation,TX77843-3112,USAAmobileadhocnetworkconsistsofwirelesshoststhatmaymoveoften.Movementofhostsresultsinachangeinroutes,requiringsomemechanismfordeterminingnewroutes.Severalroutingprotocolshavealreadybeenproposedforadhocnetworks.Thispapersuggestsanapproachtoutilizelocationinformation(forinstance,obtainedusingtheglobalpositioningsystem)toimproveperformanceofroutingprotocolsforadhocnetworks.Byusinglocationinformation,theproposedLocation-AidedRouting(LAR)protocolslimitthesearchforanewroutetoasmaller“requestzone”oftheadhocnetwork.Thisresultsinasignificantreductioninthenumberofroutingmessages.Wepresenttwoalgorithmstodeterminetherequestzone,andalsosuggestpotentialoptimizationstoouralgorithms.1.IntroductionMobileadhocnetworksconsistofwirelessmobilehoststhatcommunicatewitheachother,intheabsenceofafixedinfrastructure.1RoutesbetweentwohostsinaMo-bileAdhocNETwork(MANET)mayconsistofhopsthroughotherhostsinthenetwork[7].Hostmobilitycancausefrequentunpredictabletopologychanges.Therefore,thetaskoffindingandmaintainingroutesinMANETisnontrivial.Manyprotocolshavebeenproposedformo-bileadhocnetworks,withthegoalofachievingefficientrouting[6,9,11,13,16,18–20,23,28,30,31,33,35].Theseal-gorithmsdifferintheapproachusedforsearchinganewrouteand/ormodifyingaknownroute,whenhostsmove.Inthispaper,wesuggestanapproachtodecreaseover-headofroutediscoverybyutilizinglocationinformationformobilehosts.Suchlocationinformationmaybeob-tainedusingtheglobalpositioningsystem(GPS)[10,29].WedemonstratehowlocationinformationmaybeusedbymeansoftwoLocation-AidedRouting(LAR)proto-cols[19,20,22]forroutediscovery.TheLARprotocolsuselocationinformation(whichmaybeoutofdate,bythetimeitisused)toreducethesearchspaceforadesiredroute.Limitingthesearchspaceresultsinfewerroutediscoverymessages.Thispaperisorganizedasfollows.Section2discussessomerelatedwork.Insection3,wedescribeproposedapproachforusinglocationinformationforroutediscov-eryinMANET.Performanceevaluationofourprotocolsispresentedinsection4,andseveraloptimizationstoourbasicapproacharedescribedinsection5.Finally,section6presentsconclusions.ResearchreportedissupportedinpartbyTexasAdvancedTechnologyProgramgrants010115-248and009741-052-C,andNationalScienceFoundationgrantCDA-9529442.1Wewillusethetermshostandnodeinterchangeably.2.RelatedworkDesignofroutingprotocolsisacrucialprobleminmo-bileadhocnetworks[5,32],andseveralroutingalgorithmshavebeendeveloped(e.g.,[6,9,11,13,16,18–20,23,28,30,31,33,35]).Onedesirablequalitativepropertyofaroutingprotocolisthatitshouldadapttothetrafficpatterns[7].JohnsonandMaltz[17,18]pointoutthatconventionalrout-ingprotocolsareinsufficientforadhocnetworks,sincetheamountofroutingrelatedtrafficmaywastealargepor-tionofthewirelessbandwidth,especiallyforprotocolsthatuseperiodicupdatesofroutingtables.Theyproposedus-ingDynamicSourceRouting(DSR),whichisbasedonon-demandroutediscovery.Anumberofprotocolopti-mizationsarealsoproposedtoreducetheroutediscov-eryoverhead.PerkinsandRoyer[31]presenttheAODV(AdhocOndemandDistanceVectorrouting)protocolthatalsousesademand-drivenrouteestablishmentprocedure.TORA(Temporally-OrderedRoutingAlgorithm)[27,28]isdesignedtominimizereactiontotopologicalchangesbylocalizingrouting-relatedmessagestoasmallsetofnodesnearthechange.HassandPearlman[13]attempttocom-bineproactiveandreactiveapproachesintheZoneRout-ingProtocol(ZRP),byinitiatingroutediscoveryphaseon-demand,butlimitingthescopeoftheproactiveprocedureonlytotheinitiator’slocalneighborhood.Recentpaperspresentcomparativeperformanceevaluationofseveralrout-ingprotocols[4,8].ThepreviousMANETroutingalgorithmsdonottakeintoaccountthephysicallocationofadestinationnode.Inthispaper,weproposetwoalgorithmstoreduceroutedis-coveryoverheadusinglocationinformation.Similarideashavebeenappliedtodevelopselectivepagingforcellu-larPCS(PersonalCommunicationService)networks[1].Inselectivepaging,thesystempagesaselectedsubsetofcellsclosetothelastreportedlocationofamobilehost.Thisallowsthelocationtrackingcosttobedecreased.WeproposeandevaluateananalogousapproachforroutinginMANET.InasurveyofpotentialapplicationsofGPS,J.C.BaltzerAG,SciencePublishers308Y.-B.Ko,N.H.Vaidya/Location-AidedRouting(LAR)inmobileadhocnetworksDommetyandJain[10]brieflysuggestuseoflocationinfor-mationinadhocnetworks,thoughtheydonotelaborateonhowtheinformationmaybeused.Otherresearchershavealsosuggestedthatlocationinformationshouldbeusedtoimprove(qualitativelyorquantitatively)performanceofamobilecomputingsystem[34,36].Metricom’sRicochetisapacketradiosystemusinglocationinformationfortheroutingpurpose[24].TheMetricomnetworkinfrastructureconsistsoffixedbasestationswhosepreciselocationisde-terminedusingaGPSreceiveratthetimeofinstallation.Metricomusesageographicallybasedroutingschemetodeliverpacketsbetweenbasestations.Thus,apacketisforwardedonehopclosertoitsfinaldestinationbycom-paringthelocationofpacket’sdestinationwiththelocationofthe