基于Voronoi图的无需测距的无线传感器网络节点定位算法  

A Novel Range Free Localization Scheme Based on Voronoi Diagrams in Wireless Sensor Networks

作　　者：王继春[1] 黄刘生[1] 徐宏力[1] 徐犇[1] 李善亮[1] 

机构地区：[1]中国科学技术大学计算机科学与技术系,合肥230027

出　　处：《计算机研究与发展》2008年第1期119-125,共7页Journal of Computer Research and Development

基　　金：国家"九七三"重点基础研究发展规划基金项目(2006CB303006);国家"九七三"前期研究专项基金项目(2007CB316505)~~

摘　　要：将Voronoi图应用于无线传感器网络定位问题中,提出了VBLS(Voronoi diagrams based local-ization scheme)定位算法.它首先对接收到的anchor节点的接收信号强度(RSSI)从大到小进行排序,然后利用UDG图依次计算每个anchor节点的Voronoi区域,最后将所有Voronoi区域交集的质心输出作为定位结果.通过仿真将VBLS和另外两种无需测距的定位算法(W-Centroid和Centroid)进行了比较.仿真结果表明,对于anchor节点随机摆放的情况,VBLS的定位误差比Centroid和W-Centroid分别降低了18%和13%;对于anchor节点均匀摆放的情况,VBLS的定位误差比Centroid降低了7%,比W-Centroid增加了2%.Recently, the topic of wireless sensor networks has become a fast-growing research area. In wireless sensor networks, sensor location plays a crucial role in many applications. The global positioning system （GPS） solves the problem of localization in outdoor environments, but it is not suitable for wireless sensor networks. Having a GPS receiver on every sensor is always costly and not feasible. So, in the past, there are many localization procedures have been proposed in the literature. In this paper, a distributed, accurate and reliable Voronoi diagrams based localization scheme （VBLS） is introduced, which makes use of received signal strength indicator （RSS!） from anchors. First, VBLS sorts received signal strength indicator in descending order. Then unit disk graph is used to calculate the Voronoi area of anchors in turn. Finally, the overlapping region of different anchors＇ Voronoi area is identified as the possible region where sensor resides in. This work is compared via simulation with two other range-free localization schemes （W- Centroid and Centroid） to show the efficiency of VBLS. For random anchor placement, VBLS outperforms Centroid scheme and W-Centroid scheme significantly, estimation error decreases by 18% and 13%, respectively. For uniform anchor placement, VBLS gets a gain of 7% decrease and 2% increase of estimation error, respectively.

关 键 词：节点定位 无线传感器网络 VORONOI图 接收信号强度 无需测距 

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