DOC

Backbone Based GPS-Free Localization in Mobile Ad Hoc Networks

By Ashley Cooper,2014-02-17 21:29
9 views 0
Backbone Based GPS-Free Localization in Mobile Ad Hoc Networks

Backbone Based GPS-Free Localization in

    Mobile Ad Hoc Networks ChineseJournalofElectronics

    Vo1.16,No.1,Jan.2007

    BackboneBasedGPS..FreeLocalizationin

    MobileAdHocNetworks

    TIANMingjun,ZHAODanandYANWei

    (ComputerNetworksandDistributedSystemsLaboratory,PekingUniversity,Beijing1008

    71,China)

    Abstract——InthisPaPerwedescribeadistributed,

    GPs.freelocalizationalgorithmcalledBGFL(Backbone. basedGPS.freelocalization),whichdoesnotrelyonanY absolutepositionreferenceSUChasGPSorfixedanthor nodes.Instead,thealgorithmonlydependsonthedis- tancesbetweenthenodesandtheirneighbors.Itisback. bonebased,inwhichsomenodesinthenetworkarefirst selectedthenformedintoabackbonenetwork,whereever?Y nodeonthebackbonebuildsaLCS(Localcoordinatesys. tern).Finally.allLcssaremergedintoaglobalrelative coordinatesystem.Wesimulatetheperformanceofthe algorithmsunderavarietyofnodedensities,distancees- timationerrorsalldmovingspeeds.Theresultsshowthat ouralgorithmoutperformstheexistingGPS.freelocaliza- tionalgorithmsintermsofaccuracy.communicationcost, convergencetime,probabilitytobuildaglobalcoordinate systemandadaptab.1itytothemobileenvironment. KeywordsAdHocnetworks,Localization,GPS-

Free,Backbone.

    I.Introduction

    Inadhocnetworks,alargenumberoffunctions,bothat theapplicationlayersaswellasfortheunderlyingroutingin- frastructureneedtobesupportedbygeographicallocation. Agreatdealofresearchhasbeendoneforresolvingthisis- sue.GPSisbyfarthemostwidelypublicizedlocationsensing

    system[Jwhichsolvestheproblemoflocalizationinoutdoor environmentsforPCclassnodes.Mostofthecurrentliter

    atareonlocalizationinadhocnetworksassumestheavail

    abilityofGPSreceiversatsomenodest,.Also.someliter. atareassumesthepresenceofbeaconnodeswithpriorposi- tioninformation[2,3,9J.Althoughavoidingtheutilizationofthe GPS,itcannotadapttotheadhocdeploymentandmobility ofthenodes.Allofthemethodsabovearecalled"absolutelo- cation"becausethegroundtruthpositionorglobalcoordinate inaspecificenvironmentisacquired.

    Anotherkindoflocationestimationiscalled"relative location".inwhichalldevicesinthenetworksregardless oftheirabsolutecoordinateknowledgeestimatetherangebe. tweenthemselvesandtheirneighboringdevicas.Therela- tirelocationinformationisusefulinlocationawarerouting protocols[6l,orintheinformationdisseminat[onprotocols forqueryexpression[13.Furthermore.arelativelocalization systemcaneasilybetransformedtoanabsoluteoneifany threenodesnotalignedgettheirgroundtruthpositions.The solutionsinRefs.[6,1012]allbelongtorelativelocationalgo- rithmswhichdonotrelyonGPSoranyfixedbeaconnodes. ThispaperproposesadistributedGPSfreealgorithmfor

    localizingnodesinamobileadhocnetwork.Differentfromthe

    formerGPSfreealgorithms,ourmethodisbackbonebased.In whichfirstly,somenodesareselectedtoformintoabackbone network,whichcancoverthewholenetwork.Secondly,every nodeonthebackbonebuildsalocalcoordinatesystem.Fi

    nally,trytomergeallLCSsintoaglobalrelativecoordinate system.Wecompareoarmethodwithothertwomethods proposedinRefs.[10,11]bysimulationwithNS2.There

    suitsshowthatoarsystemperformsbetterthantheonein Ref.1101intermsofcommunicationcosts,convergencetime andtheprobabilitytoacquireaglobalcoordinatesystem.It isalsoshownthatalthoughoursystemhassimilarperfor

    manceintermsofcommunicationcostsandconvergencetime comparingwiththeoneproposedinRef.[11],itcanavoidflip ambiguity[12whichmayoccurinthelatterone.Whenflip ambiguityoccurs,alargenumberofnodeswillbepositioned bymistake.Soinshort,ouralgorithmhassuperiorsynthetic performancetothatofitsrivals.

    Therestofthepaperisorganizedasfollows.InSection I1wereviewrelatedwork.SectionIIIpresentsthebackbone basedGPS..freelocalizationalgorithmandourmethodtopo.. sitionit.SectionIVpresentsthesimulationresults,evaluates oarmethodologyandcomparesitsperformancewithexisting mechanisms.Asummaryaswellasconcludingremarkisin SectionV.

    II.RelatedW_0rk

    RelativepositioningwithoutGPSisproposedfirstbyCap? kuneta1.InRef_10],theydescribetheSPA(Selfpositioning algorithm)inwhichacoordinatesystemisdeterminedbya groupcalledtheLRG(Localreferencegroup).Thedisad

    vantageoftheSPAisthatitistooexpensiveintermsof

    communicationcostandconvergencetimebecauseeverynode participatesintheprocessofbuildinglocalcoordinatesystem andmerging.

    ManuscriptReceivedSept.2005;AcceptedMar.2006.Thisworkispartiallysupportedbythe

    CiscoAcademicResearchFund

156ChineseJournalo/Electronics2007

    ToovercometheshortcomingsofSPA.aCBA(Cluster basedapproach)isproposedinRef.[11].Inthismethod,the nodesareinitializedwithdifferentroles.asmallsubsetofthe totalnumberofnodesisselectedtobemasternodesandthe othersthenbecomeslavenodes.Everymasternodebuildsthe localcoordinatesystemjustlikeRef.101,twomasternodes

    needtwocommonslavenodestomergetheirLCSs.Com- paringwithSPA.CBAprovidesaconsiderableimprovement byreducingcommunicationoverheadsandconvergencetimes. Unfortunately,thealgorithmimportstheflipambiguitywhen mergingLCSsbecausetwomasternodescannotbewithinthe rangeofeachother,thequadrilateralcomposedbytwomaster nodesandtwoslavenodesisnotarobustone.

    LPS(Localpositioningsystem)providedinRef.[6isa

    methodtoachievepositioningforonlythenodesparticipating inforwarding.ItiscombinedwiththeTBF(Trajectorybased forwarding)[r].inwhicheachnodetouchedbyatrajectory spendssomecomputationtopositionitselfinthecoordinate systemofthesourceofthepacket.InRef.[12],Mooreeta1. providearobustdistributednetworklocalizationalgorithm. Thispaperfocusesonthephaseinwhichthelocalcoordi

    nationsystemisbuilt.Thecommunicationmechanismwhen implementingthealgorithminanetworkoflargescaleisnot

    describedindetail.Moreover,themethodofmergingdiffer- entLCSstoasinglecoordinatesystemalsoisnotwrittento length.

    Inthispaperwestateseveraldifferencesfromformerre- search.Atfirst.ourmethodisbackbonebased.inwhichonly thenodesonthebackboneparticipateinbuildingLCSsand mergingthem.Secondly,weestablishanintegratedGPSfree

    localizationsystem,followingthestepswedescribebelow;the algorithmcaneasilybeappliedpracticallytoamobileadhoc network.

    III.BackboneBasedGPS.Free

    Localization

    TheCBAl"jonlyconsidersthesituationthattwomaster nodeslocateatdifferentsidesofthelineconnectingtwobor

    dernodes,andneglectsthesituationthattwomasternodes areonthesameside.Thelattersituationwillbeml'stakenby thealgorithmfortheformer.Forexample,inFig.1,vertexk canbereflectedacrossthelineconnectingJandfwithoutal

    teringthedistanceconstraints.Accordingtothealgorithmin Re;『111,whennodekorientsitselftothecoordinatesofnode i.thepositionofkwillbemistakenask'.Therefore,allthe nodesinthecoverageofkgetawrongpositioninsuccession. Consideringtheaccumulatedeffect.alargepartofthenodes inthenetworkwillbepositionedincorrectly.Theerrorinthe algorithmisinevitablebecausewhenthedistancebetweentwo masternodesisunknown,itisimpossibletoiustifywhether twomastersareatthesamesideorcontrariwise.

    Oursolutiontothisproblemisestablishingabackbone throughmessagecommunication.Exceptmasternodes,some nodeswhichareconnectedwithseveralmasternodesarese-

    lectedtoestablishthebackbone.Becausethebackboneis aconnectednetwork.theflipambiguitiescanbeavoidedby robustnesschecking.

    Fig.1.PossibleerrorswhenmergingtwoLCSsincluster basedalgorithm

    Inthissectionwedescribeourproposedpositioningsys- tern;BGFL(backbonebasedGPSfreelocalizationalgorithm).

    Thealgorithmcanbebrokendownintothreemainphases. Thefirstphaseselectsasubnetofnodestoestablishback

    bone.Thesecondphaseisthelocalcoordinateestablishment ofthenodeinbackbone.Thethirdphasemergestheseindi

    vidualcoordinatesystemstoformaglobalcoordinatesystem. Thefollowingsectionsdescribethephasesofthealgorithmin moredetail.

    1.Backboneestablishment

    Thealgorithmisperformedperiodicallyduetoroaming ofthemobilenodeseverytimewhenthealgorithminitializes, everynodestartsadecrementtimerininverseproportionto itsdegree.Ifthetimerofnodeiexpiresbeforeitiscontracted byanyothernodes.itchangesitsstatetobeamasterand broadcastsaMASTERmessage.IfanodereceivesaMAS

    TERmessage.itbecomesaslavenodeandifmorethanone MASTERmessageisreceivedbyaslavenode.whosestateis changedtoaborder.Thenallthebordernodeswhosedegrees adduptomorethan3fonlythesenodeshavetheprobability tobuildalocalcoordinatesystem1sendBORDERmessages toselectbridgenode.Everytwomasternodeswhichhave commonbordernodeschooseabridgenode.andtheonewith thebiggestdegreeischosen.

    Nowthemasternodeswhichhavecommonbordernodes

    areconnectedbybridgenodes.Allthemasternodesand bridgenodesformabackbonewhichcancoverthewholenet

    works.Fig.2depictsthescenarioinwhichabackboneises- tablished.Inthediagram,threemasternodes(Mt,M2,and M3)andtwobridgenodes(BIandB2)makeupthebackbone. Althoughsomecommunicationisneededtoestablisha backbone,thescaleofcalculationinthesecondandthird phasesisdecreaseddramatically.Comparingwiththeover- headofbuildingalocalcoordinatesystemandbroadcastits results.thecostinthisphaseislow.Thesimulationresultsin theSectionIVfurtherverifythisviewpoint.

    2.Localcoordinatesystem

    Afterthebackboneisestablished,everynodebroadcastsa DISTANCEmessagewithdistancestoitsneighbors.Ifanode onthebackbonereceivesaDISTANCEmessage.itrecords aUitsneighbors'addressesandthedistancesbetweenthem. Then,everynodeinbackbonebuildsitsLCSfLocalcoordi

    natesystem).Fbrabackbonenode,tw.oneighborspand

    areselectedloj.whichmaximizethenumberofthenodesin LVSfLocalviewset).AdditionaUy'?readopttherobustness

    checkinginRef[12toouralgorithmwhenselectingLvs.w_e defineRSfR.esidualset1asthenodesnotinLVS.Thenodes inLVSareaUconnectedwithandi,whicharethede

    8criptorsf_ortheoriginandthetw.oae8.Thepositionofthe

    BackboneBasedGPS.FreeLocalizationinMobileAdHocNetworks157 nodesinLVScanbecalculatedusingthemethodproposedin Ref.[1O].

    AlthougheverynodeinRSisnotconnectedwithbothP andq.itispossiblethereareothertwonodesinLVSwhich

    arebothconnectedwithit.Thenodehasthreeneighbors whosepositionshavebeenestablished,soitspositioncanbe ,

    /

    ,?

    I

    f?

    \\

    ,

    ,

    ?;

    ?

    ?

    ?Slavenode?Masternode

    OBordernode@Bridgenode

    Fig.2.Adiagramshowingthees

    tablishmentofabackbone

    d

    .

    ?

    '5

    0

    calculatedusingthebasictriangulationmethod. ThroughthisextensiontothemethodinRef.[1O],most nodesconnectedwithanodeonthebackbonearepositioned, whichincreasestheprobabilitytoproduceasingleglobalco- ordinatesystemandimprovesthecoveragerateoftheglobal coordinatesystem.

    

    100100300500

    Position

    d

    .

    0

    500

    300

    100

    

    100

    .1?"

    .

    ?

    ??

    .

    .1..'

    .??.??'??一,..

    .

    :

    ????一,L,

    

    100100300500

    

    Position

    Fig.3.Thelocalizedpositionsof50nodesin500×500squaremeterregion.(a)the

    resultsofCBAalgorithm;(b)theresultsofSPAandBGFLalgorithms

    3.Gl0balcoordinatesystem

    AfterbuildingLCSs.thecoordinatesofthenodesindiffer-

    entLCSsmustbebroughtintocoincidence.BecausetheLCS

    isestablishedonlyatthenodesinbackboneandthebackbone

    isaconnectednetwork,themethodtoaajustthedirectionsof twooverlapLCSsandtheapproachtomergetheminR,ef.[10

    canbeappliedheredirectly.

    Inordertoensureanappropriateorderwhenbuildingthe globalcoordinatesystemanodewiththegreatestdegreein backboneshouldbeselectedasthecenter.Becausethescale ofthebackboneissmall,ittakesalittleoftimetoselectthe center.Afterthat,everynodeinbackbonel~roadcastsaCO. oRDINATEmessagewiththecoordinatesofthenodesinits LCS.Ifanon.backbonenodereceivesaCOORDINATEmes. sage.itrecordsitslocalposition.Ifabackbonenodereceives aCOORDINATEmessage.itrecordsthelocalcoordinateof itself.Moreover,itselectsanauxiliarynodeforreorienting andrecordsitscoordinatetoo.

    Thentheprocesstobuildtheglobalcoordinatesystem starts.Firstly,aMERGEmessageissentbycenternodewith thecorrectionangleandtheindicationwhethermirroringis necessary(forthecenternodethecorrectionangleis0and mirroringisunnecessarybydefault1.Ifanon-backbonenode receivesaMERGEmessage.itlocalizesitselfinglobalCOOl'- dinatesystemusingtheformulainAppendix.Ifabackbone nodereceivesaMERGEmessage.afterimplementingallthe operationslikeanon-backbonenode,itneedstoreorientits directiontobesamewiththecenter.thenbroadcastsMERGE messagewiththetransformingparametersanditsglobalcoor- dinate.Thetransformingproceduresarerepeatedforallthe nodesinbackboneintheorderfromthecentertotheout. sideuntilallthenodesinthenetworkarepositionedinglobal coordinatesystem.

    IV.SimulationResults

Report this document

For any questions or suggestions please email
cust-service@docsford.com