资源描述：
《A theory of network localization》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、IEEETRANSACTIONSONMOBILECOMPUTING,VOL.5,NO.12,DECEMBER20061663ATheoryofNetworkLocalizationJamesAspnes,TolgaEren,Member,IEEE,DavidK.Goldenberg,StudentMember,IEEE,A.StephenMorse,Fellow,IEEE,WalterWhiteley,YangRichardYang,BrianD.O.Anderson,Fellow,IEEE,andPeterN.Belhumeur,Fellow,IEEEAbstr
2、act—Inthispaper,weprovideatheoreticalfoundationfortheproblemofnetworklocalizationinwhichsomenodesknowtheirlocationsandothernodesdeterminetheirlocationsbymeasuringthedistancestotheirneighbors.Weconstructgroundedgraphstomodelnetworklocalizationandapplygraphrigiditytheorytotesttheconditi
3、onsforuniquelocalizabilityandtoconstructuniquelylocalizablenetworks.Wefurtherstudythecomputationalcomplexityofnetworklocalizationandinvestigateasubclassofgroundedgraphswherelocalizationcanbecomputedefficiently.Weconcludewithadiscussionoflocalizationinsensornetworkswherethesensorsarepl
4、acedrandomly.IndexTerms—Computersystemsorganization,communication/networkingandIT,mobilecomputing,algorithm/protocoldesignandanalysis,architectures,theoryofcomputation,analysisofalgorithmsandproblemcomplexity,nonnumericalalgorithmsandproblems,geometricalproblemsandcomputation,mathemat
5、icsofcomputing,discretemathematics,graphtheory,networkproblems,computerapplications,mobileapplications,location-dependentandsensitive,wirelesssensornetworks.Ç1INTRODUCTIONOCATIONserviceisafundamentalbuildingblockofRecently,novelschemeshavebeenproposedtodeter-Lmanyemergingcomputing/net
6、workingparadigms.Forminethelocationsofthenodesinanetworkwhereonlyexample,inpervasivecomputing[23],[59],knowingthesomespecialnodes(calledbeacons)knowtheirlocationslocationsofthecomputersandtheprintersinabuilding(e.g.,[28],[44],[53]).Intheseschemes,networknodeswillallowacomputertosendap
7、rintingjobtothenearestmeasurethedistancestotheirneighborsandthentrytodeterminetheirlocations.Theprocessofcomputingtheprinter.Insensornetworks,thesensornodesneedtoknowlocationsofthenodesiscallednetworklocalization.Fortheirlocationsinordertodetectandrecordeventsandtoexample,in[53],Savvi
8、deset
