DOC

Designing

By Beatrice Olson,2014-11-07 22:24
8 views 0
Designing

    Designing

    Huangetal/JZhejiangUnivSciA20078(12J1971-1982

    JournalofZhejJangUniversitySCIENCEA

    ISSN1673565X(Print);ISSN18621775(Online)

    www.zjueducn/jzus;www.springerlinkcorn

    Email:jZUS@ZjUeducn

    Designingreducedbeacontrajectoryforsensorlocalization

    HUANGWenliang,LIShi-jian=}l'LIUDuo

    (sc17001ofComplttetScience,Zh~iangUnii,ersity,Hangzhou310027,China) (GraduateSchool,Zh~iangUniversiO,,Hangzhou310027,China)

    E-mail:shijianli@Zju.edu.cn

    ReceivedJan16,2007;revisionacceptedJuly11,2007

    

    1971

    Abstract:Localizationisoneofthesubstantia1issuesinwirelesssensornetworks.Thekeyproblemforthemobilebeacon

    localizationishowtochoosetheappropriatebeacontra3ectory.However,littleresearchhasbeendoneonit.Inthispapegfirstly,

    wededucethenumberofpositionsforabeacontosendapacketaccordingtotheacreageofROI(regionofinterest);andnextwe

    presentanovelmethodbasedonvirtualforcetoa~angethepositionsinarbitraryROI;thenweapplyTSP(travellingsalesman

    problem)algorithmtothepositionssequencetoobtaintheoptimaltouringpath,i.e.thereducedbeacontrajectory.Whenamobile

    beaconmovesalongthetouringpath,sendingRFsignalsateveryposition,thesensorsinROIcanworkouttheirpositionwith

    trilateration.Experimentalresultsdemonstratethatthelocalizationmethod,basedonthebea

conreducedpath,isefficientandhas

    flexibleaccuracy.

    Keywords:Sensornetwork,Sensorlocalization,Mobilebeacon,Virtualforce

    doi:10.I63l~zus.2007.A1971Documentcode:ACLCnumber:TP393.07 INTR0DUCT10N

    Wirelesssensornetworkswil1probablybecome

    thepervasivesensing(andactuating)technologyin thefuture.Formostapplicationsofsensornetwork, senseddatashouldbewithspatialandtemporalco

    ordinates.otherwiseitsusewilIbeverylimited.Be

    causeofthis,sensornodeshavetobeawareoftheir 1ocationssoastospecifywhereacertaineventtakes place.Therefore.theproblemoflocalizingthesen. SO1'SiSofparamountimportanceformanyclassesof sensornetworkapplications.

    Tosolvethe1ocalizationproblem.itisnaturalto considerplacingsensormanuallyorequippingeach sensorwithaGPSreceiver.However.duetothe1arge numberofsensors,thosetwomethodsbecomeeither ;Correspondingauthor

    ProjectsupportedbytheNationalNaturalScienceFoundationof ChinafNos.60603025and60503018).theNationaJBasicResearch Program(973)ofChinafNo2006CB303000)theNatlonalKey TechnologyR&DProgramofChinafNo2006BAHO2A01).the ChinaPostdoctoralScienceFoundationfNos.20060401039and 200604003l6).andtheNaturalScienceFoundationofZheiiang ProvincefNo.Y105463),China

    inefficientorcostly.Soresearcherssuggestmany locationmethodsbasedontherelationbetweensen

    SOIS.

Manylocalizationalgorithmsrelyonthedis

    tancesbetweennodes.whichisknownastherange

    basedlocalization.TheestimationofdistanceisUSU

    allyimplementedbyusingsignalstrengthdecay, T0A.orTDOAforintemoderangeestimation(Pat

    wafteta1.,2003).Inanotherway,therangefree1o

    calizationalgorithmsobtainpositionestimationby usingaconnectivitymatrixofsensorinsteadofes

    timatingdistancebetweennodes(Dohertyeta1., 2001).Rangefreemethodsneedlesscomputingand communicationthanrangebasedmethod,which

    leadstolessenergyconsumptionandlongersystem life.However.its1ocalizationaccuracyismuchIower. So,wepaymoreattentiontorangebasedmethodsin

    thisarticle.

    Inasensornetworkwithrangebasedlocaliza.

    tionmethod,somenodesareequippedwithspecial positioningdevices(e.g.,aGPSreceiver)thatare awareoftheirlocations.Thesenodesarecalledbea. cons.Othernodesthatdonotinitiallyknowtheir

1972Huangetal/JZhejiangUnivSciA20078(12:19711982

    locationsarecalledunknownnodes.Generally,an unknownnodecanestimateitslocationbyrange. basedmethodsifthreeormorebeaconsareavailable inits2Dcoveragefield(NiculescuandNath.2004). Obviously,numberandpositionofbeaconshave noticeableinfluenceonthelocalizationaccuracy. Bulusueta1.(2000)andSavvideseta1.(2001showed thatthelocalizationprecisionincreaseswiththein.

    creaseofthebeacons'number.Themainproblem causedbyincreasednumberofbeaconsisthatthe beaconisfarmoreexpensivethantherestofthe sensornodes.Evenifonly1O%ofthenodesare beacons.thepriceofthewholenetworkwillincrease byabouttenfold(SichitiuandRamadurai,2004). Anotherobservationisthatafterthe(stationary)un knownnodeshavebeenlocalized,thebeaconsbe comeuseless.Theaforementionedreasonleadsusto considerusingasinglemobilebeacontolocalizethe entirenetwork(SichitiuandRamadurai,2004). Themainideaoflocalizationwithamobile beaconisasfollows(Patro.2004;Sichitiuand Ramadurai,2004;SunandGuo,2004).Aflersensor deployment,amobilebeacontraversesthesensor networkwhilebroadcastingbeaconpackets,which containthecoordinatesofthebeacon.Sensornodes receivingbeaconpacketscouldinfertheirdistance fromamobilebeaconandusethesemeasurementsas constraintstoconstructandmaintainpositionesti- mates.Thesemethodshaveacommonimportant question:"Whatistheoptimalbeacontrajectoryand whenshouldthebeaconpacketsbesent?".Tothebest ofourknowledge,thisquestionhasnoanswerwithin previouspublicationssincethepositionsofunknown nodescouldnotbeforecasted,thereforethebeacon trajectorycouldnotbedesignedaccordingtothe nodeslocations.

    Therestofthispaperisorganizedasfollows.In Section2.wesurveytherelatedworksinlocalization

    technologies,especiallythemethodsbasedonmobile beacons.InSection3wediscusstheoptimaltopoi. ogyofbeaconbroadcastingpositions,proposean improvedtopology(notoptima1)ofbeaconpositions, andbringforwardtwoalgorithmstoobtainthere. ducedbeacontrajectoryinrectangularROIandarbi. traryshapeROI.Experimentalresultsaregivenin Section4todemonstratetheperformanceofthe proposedapproach.Section5concludesthepaperand outlinesthedirectionsforfuturework.

    RELATEDWORKS

    Wangeta1.(2005)showedsometypicallimita- tionswithinexistinglocalizationmethods:(1)Un. knownnodesshouldbeneighboredtobeaconssothat toomanybeaconsareneeded,e.g.,Cricket(Priyantha a1.,2000),CooperativeRanging(Savareseeta1., 2001):f2)Localizationaccuracyreliesonthesensor deployment,e.g.,DV-hop(NiculescuandNath,2oo1) isjustapplicabletodenseisotropynetwork,and ConvexPositionEstimation(Dohertyeta1..2001) requiresthebeaconsbedeployedtotheedgeofthe network.Especially,themajorchallengeinbeacons localizationistomakelocalizationalgorithmsas robustaspossiblewhileusingasfewbeaconsas possible.Obviously,ifwecouldadvanceefficient optimalbeaconpathalgorithm.wewouldmakemo. bilebeaconbasedlocalizationmethodmorepractica1. andovercometheselimitations.

    BesidesSichitiuandRamadurai(2004).other researchersalsonoticedmobilebeaconbasedloca1.

    ization.DuttaandBergbreiter(2003)estimatedthe distancefromasensornodetoamobileobjectby ultrasoundtechnology.Neighboringsensorscooper- atedtoevaluatethedistancebetweenthemselvesby exploitingcommontangentconcept.Aslongasthe node.to.nodedistancesareavailable.thesensorpo. sitioncanbemeasuredbyrange.basedschemes.Sun andGuo(2004)proposedtheprobabilisticlocaliza. tionschemeswithamobilebeaconbyusingTOA techniqueforrangingandusingCentroidformula withdistanceinformationtocalculatethesensorpo. sition.Theaboveapproachesstillneedintegrating rangeinformationforlocalization.Inanotherway, Galstyaneta1.(2004)proposedacoarse-grained range.freelocalizationalgorithmtolowertheuncer. taintyofthesensors'positionsbyusingradiocon- nectivityconstraintsiewitheachreceivedbeacon

    packet.thereceiverlocationcouldbedefinitely boundedinthetransmissionareaofthesender.Ssuel a1.(2005)developedanovellocalizationmechanism byusingthegeometryconjecture,called"Perpen

    dicularBisectorofaChord".whichusestwolines connectingtheselectedbeaconpositionsasthe chords.then.theintersectionofthechords'perpen. dicularbisectorsistakenforthesensorlocation. Therepresentativemethodsmentionedabove bringussomeusefulideasoflocalizingsensorswith

    Huangelal/JZhejiangUnivSciA20078(12J1971-1982 mobilebeacons,butlloneofthemdiscussedhowto

    designanoptimalbeacontrajectory,otherthanSi- chitiuandRamaduraif20041mentionedthat:"the beacontrajectoryshouldbedesignedinsuchaway thatal1possiblepositionsarefullycoveredbyatIeast threenon.collinearbeacons,andthe'grid'formedby thebeaconsshouldbeastightaspossible(toincrease the1oca?zationaccuracy)".Recently.Koutsonikolas e,a1.(20071showedthreedifierentdeterministic beacontraiectoriesinasquareROI.andstudiedthe tradeoffsbetweenthetraiectoryresolutionandthe 1ocalizationaccuracyinthepresenceof2hop1oca1. ization.butthismethodcouldnotworkwel1inan arbitraryROI.

    ExtendingSichitiu'sidea,wegetseveralproper

    tiesofthebeacontrajectory.First,anarbitrarypoint shouldreceivethreenon.collinearbeaconpacketsat 1eastwhenthebeaconmovesalongthetraiectory,so thatanunknownsensorcouldbe1ocalizedwhereverit is.Second,thetrajectoryshouldbeasshortaspossible whilethenumberofsendingpositionsinthetrajectory, whichisforabeacontosendapacket.shouldbe minimized.Shorttrajectorywil1reducethetime neededto1ocalizethesensors.andreducetheenergy consumptionofsensorsandbeacons.Basedonthis idea,designinganoptimalbeacontrajectorycouldbe dividedintotwostages:f11Findtheminima1number andtopologyofbeaconbroadcastingpositionstriply covetingROI.whichmeanseachpointinR0Icould receiveat1eastthreebeaconpackets;f21Findthe shortesttrajectorytotourthepositions.

DESIGNINGREDUCEDMOBILEBEAC0N

    TRAJECTORY

    Inthissection.wewildescribeourideaofob.

    tainingthereducedbeacontrajectory.First,wede. ducethereducednumberofpositionsforthebeacon tosendapacket(beaconpositionorsendingposition, positionforshort1accordingtotheacreageofROI. Second,weadvanceamethodtogetthosepositionsin arectangleRO1.andanoveImethodbasedonvirtuaI force(ZouandChakrabarty,2004;LiS.J.eta1.,20051 toarrangethepositionsinanarbitraryshapeROI. ThenweapplyaTSP(travellingsalesmanproblem) aIgorithmtothepositionssequencetoobtaintheop. tima1touringpath.whichisthereducedbeacontra. iectorywewanttoobtain.Whenamobilebeacon 1973

    movesalongthereducedtrajectory,andsendsRF signalsateverykeyposition,theunknownsensorsin ROIcouldcalculatetheirpositionswithtrilateration. Topologyofbeaconbroadcastingpositions Forsimplicity,weassumeanysensorcouldinfer thedistancebetweenitselfandthemobilebeacon accordingtotheRSSI(radiosignalstrengthindicator) ofthebeaconpacketsitreceived(SeidelandRap- papog,1992).Consideringtheradiosignaltransmis- sionlossesintheair,weshouldpredefineabroad

    castingrangeofabeacon.Thebroadcastingareaisa circle,withthebeaconbeingitscenterandthe broadcastingradiusRsasitsradius.Onlysensors withintherangeareassumedcapableofreceivingthe

    packetsentbythebeacon.Moreover,weassumethat ROIislargeenoughcomparedwiththebroadcasting range,thentheboundaryeffectscanbeignored. Undertheseassumptions,findingoptimalbroad- castingposmonshasacorrespondinggeometry problem:howtofindtheminimalnumberandposi- tionofdiskstotriplycoverROI.Thediskcentersare eventheoptimalbeaconbroadcastingpositions. Someresearchers(HuangandTseng,2003;

    ZhangandHou,2005;MaandYang,2007)have drawnthefollowingconclusions:asallsensorshave thesamesensingrange,andsensorscompletelycover acertainROI,minimizingthenumberofworking sensorsisequivalenttominimizingtheoverlapof sensingareasofallsensors.Meanwhile,tocoverone crossingpointoftwodiskswiththeminimumoverlap, onlyonecircleshouldbeusedandthecentersofthe threecirclesshouldformanequilateraltrianglewith sidesof?3r.whereristheradiusofthedisks.Fur. thermore,forthewholenetwork,ifallDelaunaytri

    angleswiththeirverticesrepresentingsensorsare equilateraltriangleswithedgelengthofx/3r,the coverageareaofnsensorsismaximumwithoutCOV

    eragegap?

    Basedontheseconclusions,wecouldknowthat iftheDelaunaytrianglescomposedofasetofbeacon positionsareequilatera1triangleswiththeedgelength ofr,thesetofpositionsistheminimalsetCOV. eringROIfullyandwithoutcoveragegap,denotedas "

    optimal1-coverage"forROI.Apartialenlarged optimal1-coverageispresentedinFig.1,andthe

1974Huangetal/JZhejiangUnivSciA20078(12):19711982

    wholeoptimall-coverageisshowninFig.2.Fur

    thermore,weadvancethedefinitionofk-improved

    coverage.

    Fig.1Partialenlargedoptimal1-coverage positioncouldbeconsideredasacommonvertexof6 equilateraltriangles.So,weobtainEqs.(1)and(2)to

    calculatethenumberofbeaconpositions: nglenum=acre…×

    

    

    p.f,

    ,7=

    1

    ×3×j

    ,7,(2)

    whereTriangle——

    nHmmeansthenumberofequilateral trianglestotriplycovertheROI,andBea

    con~ositionnummeansthenumberofneeded GivenasetofbeaconpositionsB"ina2DROI, ifcouldbedividedintoKsubsets{,.,

    ,

    anytwoofwhichhavenointersection. Definition1Bkisconsideredtobeak-improved

    coveragetotheROI,ifeachsubsetBk(=2.,,7)is

Report this document

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