無線傳感器網(wǎng)絡(luò)中英文對照外文翻譯文獻(xiàn)

PAGE1中英文對照外文翻譯文獻(xiàn)(文檔含英文原文和中文翻譯)原文：Distributedlocalizationinwirelesssensornetworks:aquantitativecomparisonABSTRACTThispaperstudiestheproblemofdeterminingthenodelocationsinad-hocsensornetworks.Wecomparethreedistributedlocalizationalgorithms(Ad-hocpositioning,Robustpositioning,andN-hopmultilateration)onasinglesimulationplatform.Thealgorithmsshareacommon,three-phasestructure:(1)determinenode–anchordistances,(2)computenodepositions,and(3)optionallyrefinethepositionsthroughaniterativeprocedure.Wepresentadetailedanalysiscomparingthevariousalternativesforeachphase,aswellasahead-to-headcomparisonofthecompletealgorithms.Themainconclusionisthatnosinglealgorithmperformsbest;whichalgorithmistobepreferreddependsontheconditions(rangeerrors,connectivity,anchorfraction,etc.).Ineachcase,however,thereissignificantroomforimprovingaccuracyand/orincreasingcoverage1INTRODUCTIONWirelesssensornetworksholdthepromiseofmanynewapplicationsintheareaofmonitoringandcontrol.Examplesincludetargettracking,intrusiondetection,wildlifehabitatmonitoring,climatecontrol,anddisastermanagement.Theunderlyingtechnologythatdrivestheemergenceofsensorapplicationsistherapiddevelopmentintheintegrationofdigitalcircuitry,whichwillbringussmall,cheap,autonomoussensornodesinthenearfuture.Newtechnologyoffersnewopportunities,butitalsointroducesnewproblems.Thisisparticularlytrueforsensornetworkswherethecapabilitiesofindividualnodesareverylimited.Hence,collaborationbetweennodesisrequired,butenergyconservationisamajorconcern,whichimpliesthatcommunicationshouldbeminimized.Theseconflictingobjectivesrequireunorthodoxsolutionsformanysituations.ArecentsurveybyAkyildizetal.discussesalonglistofopenresearchissuesthatmustbeaddressedbeforesensornetworkscanbecomewidelydeployed.Theproblemsrangefromthephysicallayer(low-powersensing,processing,andcommunicationhardware)allthewayuptotheapplicationlayer(queryanddatadisseminationprotocols).Inthispaperweaddresstheissueoflocalizationinad-hocsensornetworks.Thatis,wewanttodeterminethelocationofindividualsensornodeswithoutrelyingonexternalinfrastructure(basestations,satellites,etc.).Thelocalizationproblemhasreceivedconsiderableattentioninthepast,asmanyapplicationsneedtoknowwhereobjectsorpersonsare,andhencevariouslocationserviceshavebeencreated.Undoubtedly,theGlobalPositioningSystem(GPS)isthemostwell-knownlocationserviceinusetoday.TheapproachtakenbyGPS,however,isunsuitableforlow-cost,ad-hocsensornetworkssinceGPSisbasedonextensiveinfrastructure(i.e.,satellites).Likewisesolutionsdevelopedintheareaofroboticandubiquitouscomputingaregenerallynotapplicableforsensornetworksastheyrequiretoomuchprocessingpowerandenergy.Recentlyanumberoflocalizationsystemshavebeenproposedspecificallyforsensornetworks.Weareinterestedintrulydistributedalgorithmsthatcanbeemployedonlarge-scalead-hocsensornetworks(100+nodes).Suchalgorithmsshouldbe:?self-organizing(i.e.,donotdependonglobalinfrastructure),?robust(i.e.,betoleranttonodefailuresandrangeerrors),?energyefficient(i.e.,requirelittlecomputationand,especially,communication).Theserequirementsimmediatelyruleoutsomeoftheproposedlocalizationalgorithmsforsensornetworks.Wecarriedoutathoroughsensitivityanalysisonthreealgorithmsthatdomeettheaboverequirementstodeterminehowwelltheyperformundervariousconditions.Inparticular,westudiedtheimpactofthefollowingparameters:rangeerrors,connectivity(density),andanchorfraction.Thesealgorithmsdifferintheirpositionaccuracy,networkcoverage,inducednetworktraffic,andprocessorload.Giventhe(slightly)differentdesignobjectivesforthethreealgorithms,itisnosurprisethateachalgorithmoutperformstheothersunderaspecificsetofconditions.Undereachcondition,however,eventhebestalgorithmleavesmuchroomforimprovingaccuracyand/orincreasingcoverage.Themaincontributionsofourworkdescribedinthispaperare:?weidentifyacommon,three-phase,structureinthedistributedlocalizationalgorithms.?weidentifyagenericoptimizationapplicabletoallalgorithms.?weprovideadetailedcomparisononasingle(simulation)platform.?weshowthatthereisnoalgorithmthatperformsbest,andthatthereexistsroomforimprovementinmostcases.Section2discussestheselection,genericstructure,andoperationofthreedistributedlocalizationalgorithmsforlarge-scalead-hocsensornetworks.Thesealgorithmsarecomparedonasimulationplatform,whichisdescribedinSection3.Section4presentsintermediateresultsfortheindividualphases,whileSection5providesadetailedoverallcomparisonandanin-depthsensitivityanalysis.Finally,wegiveconclusionsinSection6.2LOCALIZATIONALGORITHMSBeforediscussingdistributedlocalizationindetail,wefirstoutlinethecontextinwhichthesealgorithmshavetooperate.Afirstconsiderationisthattherequirementforsensornetworkstobeself-organizingimpliesthatthereisnofinecontrolovertheplacementofthesensornodeswhenthenetworkisinstalled(e.g.,whennodesaredroppedfromanairplane).Consequently,weassumethatnodesarerandomlydistributedacrosstheenvironment.Forsimplicityandeaseofpresentationwelimittheenvironmentto2dimensions,butallalgorithmsarecapableofoperatingin3D.Fig.1showsanexamplenetworkwith25nodes;pairsofnodesthatcancommunicatedirectlyareconnectedbyanedge.Theconnectivityofthenodesinthenetwork(i.e.,theaveragenumberofneighbors)isanimportantparameterthathasastrongimpactontheaccuracyofmostlocalizationalgorithms(seeSections4and5).Itcanbesetinitiallybyselectingaspecificnodedensity,andinsomecasesitcanbesetdynamicallybyadjustingthetransmitpoweroftheRFradioineachnode.Insomeapplicationscenarios,nodesmaybemobile.Inthispaper,however,wefocusonstaticnetworks,wherenodesdonotmove,sincethisisalreadyachallengingconditionfordistributedlocalization.Weassumethatsomeanchornodeshaveaprioriknowledgeoftheirownpositionwithrespecttosomeglobalcoordinatesystem.Notethatanchornodeshavethesamecapabilities(processing,communication,energyconsumption,etc.)asallothersensornodeswithunknownpositions;wedonotconsiderapproachesbasedonanexternalinfrastructurewithspecializedbeaconnodes(accesspoints)asusedin,forexample,theGPS-lesslocationsystemandtheCricketlocationsystem.Ideallythefractionofanchornodesshouldbeaslowaspossibletominimizetheinstallationcosts,andoursimulationresultsshowthat,fortunately,mostalgorithmsareratherinsensitivetothenumberofanchorsinthenetwork.Thefinalelementthatdefinesthecontextofdistributedlocalizationisthecapabilitytomeasurethedistancebetweendirectlyconnectednodesinthenetwork.FromacostperspectiveitisattractivetousetheRFradioformeasuringtherangebetweennodes,forexample,byobservingthesignalstrength.Experiencehasshown,however,thatthisapproachyieldspoordistanceestimates.Muchbetterresultsareobtainedbytime-of-flightmeasurements,particularlywhenacousticandRFsignalsarecombined;accuraciesofafewpercentofthetransmissionrangearereported.Oursimulationresultsprovideinsightintotheeffectoftheaccuracyofthedistancemeasurementsonthelocalizationalgorithms.Itisimportanttorealizethatthemainthreecontextparameters(connectivity,anchorfraction,andrangeerrors)aredependent.Poorrangemeasurementscanbecompensatedforbyusingmanyanchorsand/orahighconnectivity.Thispaperprovidesinsightinthecomplexrelationbetweenconnectivity,anchorfraction,andrangeerrorsforanumberofdistributedlocalizationalgorithms.2.1GENERICAPPROACHFromtheknownlocalizationalgorithmsspecificallyproposedforsensornetworks,weselectedthethreeapproachesthatmeetthebasicrequirementsforself-organization,robustness,andenergy-efficiency:?Ad-hocpositioningbyNiculescuandNath,?N-hopmultilaterationbySavvidesetal,and?RobustpositioningbySavareseetal.Theotherapproachesoftenincludeacentralprocessingelement,relyonanexternalinfrastructure,orinducetoomuchcommunication.Thethreeselectedalgorithmsarefullydistributedanduselocalbroadcastforcommunicationwithimmediateneighbors.Thislastfeatureallowsthemtobeexecutedbeforeanymultihoproutingisinplace,hence,theycansupportefficientlocation-basedroutingschemeslikeGAF.Althoughthethreealgorithmsweredevelopedindependently,wefoundthattheyshareacommonstructure.Wewereabletoidentifythefollowinggeneric,three-phaseapproach1fordeterminingtheindividualnodepositions：1.Determinethedistancesbetweenunknownsandanchornodes.2.Deriveforeachnodeapositionfromitsanchordistances.3.Refinethenodepositionsusinginformationabouttherange(distance)to,andpositionsofneighboringnodes.Theoriginaldescriptionsofthealgorithmspresentthefirsttwophasesasasingleentity,butwefoundthatseparatingthemprovidestwoadvantages.First,weobtainabetterunderstandingofthecombinedbehaviorbystudyingintermediateresults.Second,itbecomespossibletomix-and-matchalternativesforbothphasestotailorthelocalizationalgorithmtotheexternalconditions.Therefinementphaseisoptionalandmaybeincludedtoobtainmoreaccuratelocations.Intheremainderofthissectionwewilldescribethethreephases(distance,position,andrefinement)indetail.Foreachphasewewillenumeratethealternativesasfoundintheoriginaldescriptions.Table1givesthebreakdownintophasesofthethreeapproaches.Whenapplicablewealsodiscuss(minor)adjustmentsto(partsof)theindividualalgorithmsthatwereneededtoensurecompatibilitywiththealternatives.Duringoursimulationsweobservedthatweoccasionallyoperated(partsof)thealgorithmsoutsidetheirintendedscenarios,whichdeterioratedtheirperformance.Often,smallimprovementsbroughttheirperformancebackinlinewiththealternatives.2.2PHASE:DISTENCETOANCHORSInthisphase,nodesshareinformationtocollectivelydeterminethedistancesbetweenindividualnodesandtheanchors,sothatan(initial)positioncanbecalculatedinPhase2.NoneofthePhase1alternativesengagesincomplicatedcalculations,sothisphaseiscommunicationbounded.Althoughthethreedistributedlocalizationalgorithmseachuseadifferentapproach,theyshareacommoncommunicationpattern:informationisfloodedintothenetwork,startingattheanchornodes.Anetwork-widefloodbysomeanchorAisexpensivesinceeachnodemustforwardasinformationtoits(potentially)unawareneighbors.Thisimpliesascalingproblem:floodinginformationfromallanchorstoallnodeswillbecomemuchtooexpensiveforlargenetworks,evenwithlowanchorfractions.FortunatelyagoodpositioncanbederivedinPhase2withknowledge(positionanddistance)fromalimitednumberofanchors.Thereforenodescansimplystopforwardinginformationwhenenoughanchorshavebeen‘‘located’’.ThissimpleoptimizationpresentedintheRobustpositioningapproachprovedtobehighlyeffectiveincontrollingtheamountofcommunication(seeSection5.3).Wemodifiedtheothertwoapproachestoincludeafloodlimitaswell.2.2.1SUM-DISTThesimplesolutionfordeterminingthedistancetotheanchorsissimplyaddingtherangesencounteredateachhopduringthenetworkflood.ThisistheapproachtakenbytheN-hopmultilaterationapproach,butitremainednamelessintheoriginaldescription;wenameitSum-distinthispaper.Sum-diststartsattheanchorswhichsendamessageincludingtheiridentity,position,andapathlengthsetto0.Eachreceivingnodeaddsthemeasuredrangetothepathlengthandforwards(broadcasts)themessageifthefloodlimitallowsittodoso.Anotherconstraintisthatwhenthenodehasreceivedinformationabouttheparticularanchorbefore,itisonlyallowedtoforwardthemessageifthecurrentpathlengthislessthanthepreviousone.Theendresultisthateachnodewillhavestoredthepositionandminimumpathlengthtoatleastfloodlimitanchors.2.2.2DV-HOPAdrawbackofSum-dististhatrangeerrorsaccumulatewhendistanceinformationispropagatedovermultiplehops.Thiscumulativeerrorbecomessignificantforlargenetworkswithfewanchors(longpaths)and/orpoorranginghardware.Arobustalternativeistousetopologicalinformationbycountingthenumberofhopsinsteadofsummingthe(erroneous)ranges.ThisapproachwasnamedDV-hopbyNiculescuandNath,andHop-TERRAINbySavareseetal.SincetheresultsofDV-hopwerepublishedfirstwewillusethisname.DV-hopessentiallyconsistsoftwofloodwaves.Afterthefirstwave,whichissimilartoSum-dist,nodeshaveobtainedthepositionandminimumhopcounttoatleastfloodlimitanchors.ThesecondcalibrationwaveisneededtoconverthopcountsintodistancessuchthatPhase2cancomputeaposition.Thisconversionconsistsofmultiplyingthehopcountwithanaveragehopdistance.Wheneverananchora1infersthepositionofanotheranchora2duringthefirstwave,itcomputesthedistancebetweenthem,anddividesthatbythenumberofhopstoderivetheaveragehopdistancebetweena1anda2.Whencalibrating,ananchortakesallremoteanchorsintoaccountthatitisawareof.Nodesforward(broadcast)calibrationmessagesonlyfromthefirstanchorthatcalibratesthem,whichreducesthetotalnumberofmessagesinthenetwork.2.2.3EUCLIDEANAdrawbackofDV-hopisthatitfailsforhighlyirregularnetworktopologies,wherethevarianceinactualhopdistancesisverylarge.NiculescuandNathhaveproposedanothermethod,namedEuclidean,whichisbasedonthelocalgeometryofthenodesaroundananchor.Againanchorsinitiateaflood,butforwardingthedistanceismorecomplicatedthaninthepreviouscases.Whenanodehasreceivedmessagesfromtwoneighborsthatknowtheirdistancetotheanchor,andtoeachother,itcancalculatethedistancetotheanchor.Fig.2showsanode(_Self_)thathastwoneighbors:n1andn2withdistanceestimatestoananchor.Togetherwiththeknownrangesc,d,ande,Euclideanarrivesattwopossiblevalues(r1andr2)forthedistanceofthenodetotheanchor.Niculescudescribestwomethodstodecideonwhich,ifany,distancetouse.Theneighborvotemethodcanbeappliedifthereisathirdneighbor(n3)thathasadistanceestimatetotheanchorandthatisconnectedtoeithern1orn2.Replacingn2(orn1)byn3willagainyieldapairofdistanceestimates.Thecorrectdistanceispartofbothpairs,andisselectedbyasimplevoting.Ofcourse,moreneighborscanbeincludedtomaketheselectionmoreaccurate.Thesecondselectionmethodiscalledcommonneighborandcanbeappliedifnoden3isconnectedtobothn1andn2.Basicgeometricreasoningleadstotheconclusionthattheanchorandn3areonthesameoroppositesideofthemirroringlinen1–n2,andsimilarlywhetherornotselfandn3areonthesameside.Fromthisitfollowswhetherornotselfandtheanchorlayonthesameside.TohandletheuncertaintyintroducedbyrangeerrorsNiculescuimplementsasafetymechanismthatrejectsill-formed(flat)triangles,whichcaneasilyderailtheselectionprocessby‘neighborvote’and‘commonneighbor’.Thischeckverifiesthatthesumofthetwosmallestsidesexceedsthelargestsidemultipliedbyathreshold,whichissettotwotimestherangevariance.Forexample,thetriangleSelf-n1–n2inFig.2isacceptedwhenc+d>(1+2RangeVar)*e.Notethatthesafetycheckbecomesasstrictastherangevarianceincreases.Thisleadstoalowercoverage,definedasthepercentageofnon-anchornodesforwhichapositionwasdetermined2.3PHASE:NODEPOSITIONInthesecondphasenodesdeterminetheirpositionbasedonthedistanceestimatestoanumberofanchorsprovidedbyoneofthethreePhase1alternatives(Sum-dist,DV-hop,orEuclidean).TheAd-hocpositioningandRobustpositioningapproachesuselaterationforthispurpose.N-hopmultilateration,ontheotherhand,usesamuchsimplermethod,whichwenamedMin–max.Inbothcasesthedeterminationofthenodepositionsdoesnotinvolveadditionalcommunication.2.3.1LATERATIONThemostcommonmethodforderivingapositionislateration,whichisaformoftriangulation.Fromtheestimateddistancesandknownpositionsoftheanchorswederivethefollowingsystemofequations:Theunknownpositionisdenotedby.Thesystemcanbelinedbysubtractingthelastequationfromthefirstn_1equationsReorderingthetermsgivesapropersystemoflinearequationsintheformAx=b,whereThesystemissolvedusingastandardleast-squaresapproach.Inexceptionalcasesthematrixinversecannotbecomputedandlaterationfails.Inthemajorityofthecases,however,wesucceedincomputingalocationestimate.WerunanadditionalsanitycheckbycomputingtheresiduebetweenthegivendistancesandthedistancestothelocationestimateAlargeresiduesignalsaninconsistentsetofequations;werejectthelocation^xwhenthelengthoftheresidueexceedstheradiorange.2.3.2MIN-MAXLaterationisquiteexpensiveinthenumberoffloatingpointoperationsthatisrequired.AmuchsimplermethodispresentedbySavvidesetal.aspartoftheN-hopmultilaterationapproach.Themainideaistoconstructaboundingboxforeachanchorusingitspositionanddistanceestimate,andthentodeterminetheintersectionoftheseboxes.Thepositionofthenodeissettothecenteroftheintersectionbox.Fig.3illustratestheMin–maxmethodforanodewithdistanceestimatestothreeanchors.NotethattheestimatedpositionbyMin–maxisclosetothetruepositioncomputedthroughlateration(i.e.,theintersectionofthethreecircles).Theboundingboxofanchoriscreatedbyaddingandsubtractingtheestimateddistancefromtheanchorposition:Theintersectionoftheboundingboxesiscomputedbytakingthemaximumofallcoordinateminimumsandtheminimumofallmaximums:Thefinalpositionissettotheaverageofbothcornercoordinates.Asforlateration,weonlyacceptthefinalpositioniftheresidueissmall.2.4PHASE3:REFINEMENTTheobjectiveofthethirdphaseistorefinethe(initial)nodepositionscomputedduringPhase2.Thesepositionsarenotveryaccurate,evenundergoodconditions(highconnectivity,smallrangeerrors),becausenotallavailableinformationisusedinthefirsttwophases.Inparticular,mostrangesbetweenneighboringnodesareneglectedwhenthenode–anchordistancesaredetermined.TheiterativeRefinementprocedureproposedbySavareseetal.doestakeintoaccountallinternodesranges,whennodesupdatetheirpositionsinasmallnumberofsteps.Atthebeginningofeachstepanodebroadcastsitspositionestimate,receivesthepositionsandcorrespondingrangeestimatesfromitsneighbors,andperformsthePhase2todetermineitsnewposition.Inmanycasestheconstraintsimposedbythedistancestotheneighboringlocationswillforcethenewpositiontowardsthetruepositionofthenode.When,afteranumberofiterations,thepositionupdatebecomessmall,Refinementstopsandreportsthefinalposition.Thebasiciterativerefinementprocedureoutlinedaboveprovedtobetoosimpletobeusedinpractice.Themainproblemisthaterrorspropagatequicklythroughthenetwork;asingleerrorintroducedbysomenodeneedsonlyditerationstoaffectallnodes,wheredisthenetworkdiameter.Thiseffectwascounteredby(1)clippingundeterminednodeswithnon-overlappingpathstolessthanthreeanchors,(2)filteringoutdifficultsymmetrictopologies,and(3)associatingaconfidencemetricwitheachnodeandusingtheminaweightedleast-squaressolution.Thedetails(see)arebeyondthescopeofthispaper,buttheadjustmentsconsiderablyimprovedtheperformanceoftheRefinementprocedure.Thisislargelyduetotheconfidencemetric,whichallowsfilteringofbadnodes,thusincreasingthe(average)accuracyattheexpenseofcoverage.TheN-hopmultilaterationapproachbySavvidesetal.alsoincludesaniterativerefinementprocedure,butitislesssophisticatedthantheRefinementdiscussedabove.Inparticular,theydonotuseweights,butsimplygroupnodesintoso-calledcomputationsubtrees(over-constrainedconfigurations)andenforcenodeswithinasubtreetoexecutetheirpositionrefinementinturninafixedsequencetoenhanceconvergencetoapre-specifiedtolerance.IntheremainderofthispaperwewillonlyconsiderthemoreadvancedRefinementprocedureofSavareseetal.翻譯：無線傳感器網(wǎng)絡(luò)分布式定位的定量比較摘要本文研究的問題，在Ad-Hoc傳感器網(wǎng)絡(luò)確定節(jié)點(diǎn)位置。在同一仿真平臺上比較了3種分布式定位算法。該算法都有一個共同的，用三階段分布式定位結(jié)構(gòu)體系：（1）確定未知節(jié)點(diǎn)到錨節(jié)點(diǎn)距離，（2）節(jié)點(diǎn)定位，（3）迭代求精。我們提出一個詳細(xì)分析比較各個方案，為每一個階段，而且是一個一對一的比較完整的算法。主要的結(jié)論是，沒有一個單一的算法性能最好，哪一個算法較為可取，取決于條件（范圍錯誤，連接，錨分?jǐn)?shù)等）。在任何情況下都有有很大的空間提高準(zhǔn)確性和或增加集中性。關(guān)鍵詞：自組網(wǎng)；分布式算法；定位1簡介無線傳感器網(wǎng)絡(luò)持有的許多應(yīng)用在監(jiān)察和控制方面。例如：目標(biāo)跟蹤，入侵檢測，野生動物棲息地監(jiān)測，氣候控制，以及災(zāi)害管理?？焖侔l(fā)展一體化的數(shù)字電路驅(qū)動了傳感器的應(yīng)用，這將為我們帶來美小型，廉價，自治區(qū)傳感器節(jié)點(diǎn)在不久的將來。新技術(shù)提供新的機(jī)遇，但它還介紹了一些新的問題。這一點(diǎn)尤為重要，真正的傳感器網(wǎng)絡(luò)中的個別節(jié)點(diǎn)能力是很有限的。因此它們之間需要協(xié)作節(jié)點(diǎn)，但節(jié)省能源是一個重大的問題，這意味著通信應(yīng)盡量減少。這些目標(biāo)互有沖突，對于許多的情況需要非傳統(tǒng)的解決方案。最近的一項(xiàng)Akyildizetal.等人的調(diào)查顯示。討論一長串的開放式研究的問題，必須加以處理前傳感器網(wǎng)絡(luò)部署。問題的范圍從物理層（低功率傳感，處理和通信硬件）到應(yīng)用層（查詢和發(fā)布數(shù)據(jù)議定書）。在本文中，我們處理自組網(wǎng)傳感器網(wǎng)絡(luò)定位。也就是說，我們要確定位置的個別傳感器節(jié)點(diǎn)，而不必依賴外部基礎(chǔ)設(shè)施（基站，衛(wèi)星等）。自組織問題已得到相當(dāng)多注意，在過去，由于許多應(yīng)用需要知道物體或人在哪，并因此建立各種定位服務(wù)。毫無疑問，最知名的全球定位系統(tǒng)是今天所使用的位置服務(wù)。由全球定位系統(tǒng)實(shí)施，但是它不適合低成本，自組傳感器網(wǎng)絡(luò)，原因是全球定位系統(tǒng)是基于廣泛的基礎(chǔ)設(shè)施（即衛(wèi)星）的。同樣的解決方案開發(fā)中面積機(jī)器人和普適計(jì)算一般不適用于傳感器網(wǎng)絡(luò)因?yàn)樗麄冃枰嗟奶幚砟芰湍茉?。近來，一些定位系統(tǒng)已經(jīng)被建議專門為傳感器網(wǎng)絡(luò)。我們感興趣的，真正的分布式算法可以受用于大型Ad-Hoc傳感器網(wǎng)絡(luò)。這種算法應(yīng)該是：?自組織（即不依賴于全球基礎(chǔ)設(shè)施）?強(qiáng)大（即容納節(jié)點(diǎn)失敗和范圍錯誤）?能源效率（即需要很少計(jì)算，特別是通信）這些要求立即排除一些對于傳感器網(wǎng)絡(luò)建議的定位算法。我們進(jìn)行了一次徹底的分析并且符合上述規(guī)定的3種分布式算法，以確定它們在各種不同條件下的反應(yīng)。特別是，我們研究重點(diǎn)參數(shù)如下：范圍錯誤，連通性（密度），及錨節(jié)點(diǎn)密度。這些算法不同在于它們位置精確度，網(wǎng)絡(luò)復(fù)蓋范圍，誘發(fā)網(wǎng)絡(luò)交通和處理器負(fù)荷。三種算法基于不同的設(shè)計(jì)目標(biāo)，毫不奇怪的每個算法都要根據(jù)一套特定的條件實(shí)施。在每一個條件下，但是，即使是最好的算法還有很多改進(jìn)的余地，精確度和連通性。我們的工作描述在這個文件是：?我們可以找出一個共同的，分三個階段，在結(jié)構(gòu)分布式定位算法?我們可以找出一個通用的優(yōu)化適用所有算法?我們提供一份詳細(xì)的比較單一（仿真）平臺?顯示：不存在算法最好的，在大多數(shù)情況下存在著改進(jìn)的余地第2節(jié)論述了選擇，通用結(jié)構(gòu)，和運(yùn)作三個分布式定位算法大規(guī)模Ad-Hoc傳感器網(wǎng)絡(luò)。這些算法比較基于同一個模擬仿真平臺，它被描述在第3節(jié)，第4節(jié)介紹中間結(jié)果獨(dú)立描述，而第5條規(guī)定，一份詳細(xì)的總體比較，并進(jìn)行深入的敏感性分析。最后，我們給出的結(jié)論在第6節(jié)。2定位算法在詳細(xì)討論分布式定位之前，我們先前概要的上下文中，這些算法已經(jīng)被介紹。第一考慮到傳感器網(wǎng)絡(luò)要求和自組網(wǎng)沒有好的控制，安裝網(wǎng)絡(luò)時（例如，當(dāng)節(jié)點(diǎn)分別從飛機(jī)下落）。因此，我們假定節(jié)點(diǎn)是隨機(jī)分布在整個環(huán)境。為簡化和易用性陳述我們限制的環(huán)境，以2尺寸，但所有算法是能夠在三維。網(wǎng)絡(luò)有25個節(jié)點(diǎn)；一條線連接的兩個節(jié)點(diǎn)可以直接通信，網(wǎng)絡(luò)中節(jié)點(diǎn)的連通性是一個重要參數(shù)，具有很強(qiáng)的準(zhǔn)確性的影響對于定位算法。它可以設(shè)置初步通過選擇一個特定節(jié)點(diǎn)密度，并在一些情況下，可設(shè)定動態(tài)調(diào)整發(fā)射功率的射頻無線電在每個節(jié)點(diǎn)。在一些應(yīng)用情況下，節(jié)點(diǎn)可移動。在本文中，但是，我們專注于靜態(tài)網(wǎng)絡(luò)，即節(jié)點(diǎn)靜止，因?yàn)檫@已經(jīng)是一個具有挑戰(zhàn)性的條件分布式定位。我們假定一些錨節(jié)點(diǎn)有一個及嫩的了解針對一些全球坐標(biāo)系統(tǒng)。注這錨節(jié)點(diǎn)具有相同的功能（處理，通信，能源消耗，等），與其他所有傳感器未知節(jié)點(diǎn)；我們不考慮采取各種辦法的基礎(chǔ)上外部基礎(chǔ)設(shè)施與專門的錨節(jié)點(diǎn)節(jié)點(diǎn)（接入點(diǎn)）所用的，舉例來說，GPS的不足定位系統(tǒng)和板球定位系統(tǒng)。最理想的小錨節(jié)點(diǎn)應(yīng)盡可能低減少安裝成本，而我們的模擬結(jié)果表明，說，幸運(yùn)的是，大部分算法是相當(dāng)敏感的對于網(wǎng)絡(luò)中的錨節(jié)點(diǎn)。最后一項(xiàng)內(nèi)容，它定義分布式定位是有能力來衡量在網(wǎng)絡(luò)中它們之間的距離有直接關(guān)連的節(jié)點(diǎn)。從成本的角度來看，這是有吸引力的利用射頻無線電測量節(jié)點(diǎn)之間范圍，例如，通過觀察信號強(qiáng)度。經(jīng)驗(yàn)證明，然而這種做法產(chǎn)生惡劣的距離估計(jì)。許多更好的成果得到了通過飛行測量表明，尤其是當(dāng)聲波在與射頻信號相結(jié)合；精度幾個百分點(diǎn)的傳輸范圍報道。我們的模擬結(jié)果提供精確的距離測量對定位算法的影響。重要的是要意識到主要依靠三個參數(shù)（連接，錨分?jǐn)?shù)，和測距誤差）。惡劣的范圍測量利用許多錨節(jié)點(diǎn)或高連通測量范圍能得到補(bǔ)償。本文我們了解到，在分布式定位算法中連通性，錨分?jǐn)?shù)，測距誤差的關(guān)系。2.1通用方法從已知的對于傳感器網(wǎng)絡(luò)定位算法建議，我們選定三個辦法滿足網(wǎng)絡(luò)的基本要求對于自組織性，魯棒性，能源效率：?Ad-Hocpositioning?N-hopmultilateration?Robustpositioning其他途徑通常包括一個中央處理元素，依靠外部基礎(chǔ)設(shè)施或者導(dǎo)致太多的通信。三個選定的算法是完全分布和利用當(dāng)?shù)貜V播利用相鄰節(jié)點(diǎn)。這最后一項(xiàng)功能使其對任何多跳之前執(zhí)行路由已經(jīng)就位，因此，他們可以支持高效率基于位置的路由計(jì)劃如GAF。盡管三種算法開發(fā)獨(dú)立后，我們發(fā)現(xiàn)他們都有一個共同的結(jié)構(gòu)。我們可以找出以下通用的，三個階段的做法1確定個別節(jié)點(diǎn)的職務(wù)：1、未知節(jié)點(diǎn)到錨節(jié)點(diǎn)距離的測量：決定位置節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的距離2、節(jié)點(diǎn)定位：利用第一階段得出的到錨節(jié)點(diǎn)的距離和錨節(jié)點(diǎn)的位置信息計(jì)算出未知節(jié)點(diǎn)的坐標(biāo)3、迭代求精：利用鄰居節(jié)點(diǎn)距離信息對節(jié)點(diǎn)位置進(jìn)行求精原來描述的算法目前前兩個階段作為一個單一實(shí)體，而是我們發(fā)現(xiàn)，他們的分離提供了兩個好處。首先，我們得到了更深入的了解該組合行為由研究的結(jié)果。第二，它才成為可能，以MIN-MAX匹配備選方案為這兩個階段定制外部條件定位算法。優(yōu)化階段是可選的可能會包含要獲取更準(zhǔn)確的位置。在余下的本節(jié)中，我們將描述這三個階段（測距，定位和優(yōu)化）詳細(xì)研究。我們將枚舉每個階段備選方案為原來的說明中找到。提供分類到的階段三種方法。如果適用我們還討論調(diào)整每個確保所需的算法與備選方案兼容性。在我們模擬操作中觀察到，我們偶爾操作（部分）的算法外有意情景，使操作結(jié)果惡化。很多時候，這些都是由小的改進(jìn)帶來的。2.2第1期：距離主播在這一階段，節(jié)點(diǎn)的信息共享，以確定個別節(jié)點(diǎn)和錨節(jié)點(diǎn)的距離，使一個（初始）位置可以計(jì)算出來，在第2階段。沒有了第1期替代從事復(fù)雜的計(jì)算，所以這個階段的工作是通訊界的。雖然三個分布式定位算法每使用一種不同的方法，他們都有一個共同通信模式：信息泛洪到網(wǎng)絡(luò)，開始在主播節(jié)點(diǎn)。一個網(wǎng)絡(luò)性的泛洪，網(wǎng)絡(luò)范圍內(nèi)的大量通過一些標(biāo)記A是昂貴，因?yàn)槊總€節(jié)點(diǎn)必須將轉(zhuǎn)發(fā)A的信息到它（可能）不知道鄰居節(jié)點(diǎn)。這意味著誤差問題：泛洪信息從所有主播向所有節(jié)點(diǎn)將是太大昂貴對于大型網(wǎng)絡(luò)，即使使用低錨錨點(diǎn)分?jǐn)?shù)。幸運(yùn)的是一個好的位置可以導(dǎo)出在階段2與知識（測距和定位）從一個有限數(shù)量的定位標(biāo)記因此節(jié)點(diǎn)可以簡單地停止轉(zhuǎn)發(fā)信息當(dāng)足夠的錨已位于路由表中時。這個簡單的優(yōu)化提出了在魯棒定位的做法被證明是高度有效地控制數(shù)量的通信。我們修改了其他兩個辦法包括泛洪為好。2.2.1Sum-dist最簡單的解決辦法定距離到錨是將距離信息添加到洪泛的每跳通信中。這是所采取的做法的N-Hopmultilateration辦法，我們將它命名為Sum-dist在這一文件中。Sum-dist開始從錨節(jié)點(diǎn)出發(fā)，發(fā)出一個信息，錨節(jié)點(diǎn)發(fā)送包含它們身份和位置信息的消息，路徑初始長度設(shè)為0。每個接收到該消息的節(jié)點(diǎn)將測量到的距離添加到路徑長度里面并且當(dāng)洪泛限制允許時將其轉(zhuǎn)發(fā)出去。另一個制約因素是，其中，