无线传感器网络定位理论和算法  

Theory and Algorithms on Localization in Wireless Sensor Networks

作　　者：王小平[1] 罗军[1] 沈昌祥[2] 

机构地区：[1]国防科学技术大学计算机学院,长沙410073 [2]海军计算技术研究所,北京100841

出　　处：《计算机研究与发展》2011年第3期353-363,共11页Journal of Computer Research and Development

基　　金：国家"九七三"重点基础研究发展计划基金项目(2006CB303000);国家自然科学基金项目(60903224;60903223)

摘　　要：定位技术作为网络协议和应用的基础,已经成为无线传感器网络重要的支撑技术,是传感器网络研究的核心问题之一.系统地总结了近年来定位理论和算法的最新研究进展.全面阐述了定位问题的形式化定义、定位问题复杂度分析、基于刚性理论的定位理论和定位问题可计算性研究的最新成果.通过对定位理论的研究可以更好地揭示定位技术的本质,回答很多定位技术相关的基本问题.此外,还深入分析了近年来典型的定位算法,介绍每种算法的设计思想,分析其适用范围和不足.最后给出定位理论和定位算法未来的研究方向.As a basis of many network protocols and applications,localization is one of the major supportive technologies for wireless sensor networks,making it an indispensable part in the design of wireless sensor networks.In this paper,we comprehensively survey the recent advancements of the theory and algorithms on localization.We completely summarize the following aspects on localization theory.Firstly,we describe the formal definition of localization problem.Then,we analyze the computational complexity of the localization problem under various configurations.Next,we introduce the localization theory,which is developed from the rigidity theory.Finally,we present a special kind of location computable network：sequentially localizable network.In a global view,the study of localization theory is the basis of all the achievements,which not only shows great insights on the localization problem,but also further solves many fundamental problems of localization,especially in two-dimensional case.By localization theory,a lot of new localization algorithms are proposed.We also conclude the typical localization algorithms related to localization theory.We place special emphasis on their design ideas,as well as the application scope and disadvantage,for each localization algorithm.Finally,we point out the possible directions in both localization theory and localization algorithm for further research.

关 键 词：无线传感器网络 定位理论 刚性理论 定位算法 计算复杂性 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]