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

基于Voronoi图的无需测距的无线传感网络节点定位算法 基于Voronoi图的无需测距的无线传感网络节点定位算法 王继春 黄刘生 徐宏力 徐犇 李善亮 (中国科学技术大学计算机科学与技术系 合肥 230027) (jichunw@mail.ustc.edu.cn) A Novel Range Free Localization Scheme Based on Voronoi Diagrams in Wireless Sensor Networks Wang Jichun, Huang Liusheng, Xu Hongli, Xu Ben and Li Shanliang (Department of Computer Science and Technology, University of Science and Technology of China, Hefei 230027) Abstract 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 Position 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, we introduce a distributed, accurate and reliable Voronoi diagrams based localization scheme (VBLS), which makes use of received signal strength indicator (RSSI) from anchors. First, VBLS sorts received signal strength indicator in descending order. Then, we use unit disk graph 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. We compare our work 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. Key words localization; wireless sensor networks; Voronoi diagrams; RSSI; Range-free. 将Voronoi图应用于无线传感网络定位问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 中，提出了VBLS(Voronoi diagrams based 摘 要 localization scheme)定位算法。它首先对接收到的anchor节点的接收信号强度(RSSI)进行从 大到小的排序，然后利用UDG图依次计算每个anchor节点的Voronoi区域，最后将所有 Voronoi区域交集的质心输出作为定位结果。通过仿真将VBLS和另外两种无需测距的定位 算法(W-Centroid和 Centroid)进行了比较。仿真结果 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明， 对于anchor节点随机摆放的情况，VBLS的定位误差比Centroid和 W-Centroid分别降低 了18%和13%;对于anchor节点均匀摆放的情况，VBLS的定位误差比Centroid降低了7%, 比W-Centroid增加了2%。 关键词 节点定位;无线传感器网络;Voronoi图;接收信号强度(RSSI);无需测距 中图法分类号 TP393 无线传感器网络是由大量结构简单，廉价的传感器集成无线通信接口所组成，它在环境监测，灾难救助，目标跟踪等领域都有广泛的应用前景。在这些众多的应用中，传感节点自我定位非常重要。 到目前为止，为了解决定位问题出现了很多不同的算法。这些算法主要可以分为2大类:基于测距的和无需测距的。 基于测距的算法主要有以下几种:TOA(Time of Arrival)，TDOA(Time Difference of Arrival )，AOA(Angle of Arrival )和基于RSSI。基于TOA技术定位最典型的例子就是GPS[1]系统，GPS系统通过测量GPS接收器和卫星之间的信号传输时间来估算接收器和卫星之间的距离进行定位。基于TDOA的方法定位的比如AHLos[2]算法，TDOA通常通过测量2种速度不同的信号传输时间差来计算节点之间的距离，TDOA通常需要节点上附加特殊的信号收发设备(如超声波收发器等)。AOA[3]的方法测量信号的到达角度，通过计算扇形之间的重叠区域进行节点定位。和TDOA的方法一样，AOA也需要节点附加特殊的设备(如有向天线)。基于RSSI定位的系统比如RADAR[4]和MoteTrack[5]先对环境中存在的信号强度进行抽样，然后将定位时接收到的信号强度和先验的信号强度进行匹配得到定位结果。这种定位方式只能应用于静态的环 境，如环境发生变化，先验知识就不再有参考价值。 由于基于测距的方法通常都需要特殊的设备，或者像基于RSSI的定位受环境影响很大，所以出现很多了无需测距的定位算法，比如Bulusu等人提出的质心(Centroid[6])算法。定位节点收集能够和自己通信的所有anchor节点的信息，然后计算这些anchor节点的质心作为自己的位置，Centroid利用节点之间的连通性进行定位。Xingfa Shen等人提出了加权质心(W-Centroid[7])算法对于质心算法进行改进。W-Centroid将接收信号强度作为计算质心时的权重系数加以考虑从而提高质心算法的性能。DV-hop[8]是另外一种无需测距的定位算法，它利用最小跳数进行定位。在DV-hop算法中，传感节点维护一个自身到其他anchor的最小跳数表，然后利用每个anchor计算得出的平均每跳距离就可以计算出节点到anchor之间的距离，然后利用三角定位法就可以得出定位结果。APIT[9]是利用三角形区域相交进行定位的算法，APIT将传感节点的邻居anchor节点做不同的组合得到不同的三角形，然后判断传感节点是否在这些三角形的内部，通过这些三角形之间的交集就可以判断传感节点的位置。肖玲等人提出了基于非度量的多维标度技术的定位算法(NMDS[10]),NMDS基于节点RSSI和节点距离之间的单调关系，利用RSSI值构建相异性矩阵， 然后对相异性矩阵进行反复迭代计算得到定位结果。 考察上述所有的定位算法，我们认为一个好的定位算法至少要满足以下几个条件:第一，定位算法必须是分布式的，在一个大型的无线传感器网络中，收集全局的信息是非常困难的，而且如果采用集中式的算法，靠近基站的节点由于要承担过多的转发任务将会成为网络的瓶颈;第二，定位算法的消息复杂度不能过高，因为在无线传感网络中，节点之间的消息传递是能量耗费的主要方面;第三，定位系统必须有一定的容错性，因为传感节点通常放置在无人看管的区域，由于恶劣的环境或者能量不足很容易出现故障，所以定位系统必须健壮，小部分节点故障不能影响到整个系统的功能。 2 VBLS定位算法 现今主要存在3种信号传播模型:Free-space 模型，Two-ray ground reflection 模型和shadowing 模型。Free-space 模型和 Two-ray ground reflection 模型都认为接收信号的能量是距离的一个确定函数，因此他们的信号传输模型都是一个理想圆。但是由于多路径反射，障碍物阻隔等原因，实际的环境中信号传输往往是各向异性的。因此更为一般化的Shadowing模型使用更加广泛，Shadowing模型的表示如下: [Pr(d)P]dB ,10 log( d),X (1) dB r(d0) d0 其中XdB是一个平均值为0的高斯分布变量， 为路径损耗系数(path loss exponent), Pr(d0) 和 d0 分别是参考能量和参考距离。Shadowing 模型将环境噪声引入到接收信号能量的衡量中，因此更加的实用化。观察Shadowing传输模型，我们可以得出以下结论:在不考虑环境噪声的情况下，接收信号强度Pr(d)是一个随距离d增加单调递减的函数。 2.2 定位模型的阐述 在 ,V,E,， 其中V为空间中所有 传感节点的集合，E为连接所有相邻传感器的边的集合。我们令集合A(A V)为所有anchor节点的集合，这些节点都知道自身的位置，S V,A 为所有 待定位的节点集合。 Figure 1 Voronoi-based algorithm overview 图1基于Voronoi图定位算法演示 Figure 2 An example of Voronoi diagrams 图2 二维空间的Voronoi划分 假定传感节点Si S想要确定自身的位置，此时我们假设它能得到周围K(1 k A) 个anchor 节点的RSSI值,这些anchor节点的接收信号强度分别表示如下RSSI，不失一般性可i,j1,RSSIi,j2 RSSIi,jk以假设RSSI 。参考上一节提 i,j1 RSSI i,j2 RSSI i,jk 出的:在理想情况下，Pr(d)随d单调递减的结论，我们可以得到定位问题的如下数学表示: 寻找空间中的一个点集，集合中的每个点(x,y)满足如下条件: 0 Li,j1 Li,j2 Li,jk R (2) 其中Li,jx(1 x k)表示节点(x,y)到 anchor节 点 jx之间的欧几里德距离，R为节点的通信半径 (我们假设所有节点都是同类型的，拥有同样的通信半径)。我们采用Voronoi图解不等式(2)。 定义 1: Voronoi图指的是给定空间的一个点集，平面可以被划分为距离各个点最近的一系列不相交的凸多边形的集合，这些凸多边形分别和点集中的每个点相对应，称之为该点的Voronoi区域，如图2 所示。 对应于上述的不等式我们可以知道，点集合为anchor集合A。根据Voronoi区域的定义，我们可 以知道一开始传感节点Si位于j1的 Voronoi区域。 此时若将 j1从集合 A中除去，可以知道在剩下的所 有节点中，传感节点Si距离j2最近， 所以此时Si 位 于 j2的 Voronoi区域中，我们可以反复进行这个过 程直到K个anchor节点的Voronoi区域全部计算完 成，此时计算这些Voronoi区域的交集即为定位算法输出的结果。 2.3 VBLS算法描述 因为在一个完全图中计算节点的Voronoi区域需要整个图的全局信息，所以上面所描述的定位方 法是集中式的。幸运的是在单位圆图(unit disk graph)上计算节点的Voronoi区域可以分 布式进行。在图3 中我们比较了采用完全图和单位圆图得到的定位结果，可以看出相比于完全图，采用单位圆图在定位精度上的损失并不大。 定义 2:对于所有anchor节点集合A的单位圆图UDG(A)，UDG(A)中存在一条边uv,u,v A,， 当且仅当u，v之间的欧几里德距离小于通信半径R。 ) R(rorre noitamitsECommunication range Figure 3 AD=0.0025 DON=0.1 EF=0.1 图3完全图和UDG图的定位误差比较 为了得到集合A的单位圆图，集合A中的每个节点必须维护一个一跳邻居表，如表2 所示。每一个anchor节点定期的向周围节点发送包含自身坐标的 广播包，其他anchor接收到该广播包并且更新自身的一跳邻居表。通过这种方式，那些由于能量耗尽或者出故障而不再工作的anchor节点就能被及时的发现，因为它们的错误使得定位出错的可能就会被避免。所以VBLS是健壮的，少数anchor节点故障不会影响到整个系统正确的进行定位。 Table 1 Table of heard anchors T i 表 1 传感节点S的anchor节点接收表T i i 整个算法的流程如下: 上述的流程我们可以看出，一次定位需要的消息数为(m+1),其中m为传感节点的anchor邻居数。考虑到所有Voronoi图相交之后可能出现空集的情况，我们采用给每个Voronoi区域增加权重的方法，权重的数值就是对应anchor节点的接收信号 强度。最后选出所有最大权重的点计算它们的质心得到定位结果，采用这种方法可以解决由于噪声存在导致公式[2]无解的情况。 Table 2 Table of one-hop neighbors TB 表 2 anchor节点B的一跳邻居表TB Figure 4 Location problem when noise existing 图 4噪声存在情况下的定位问题 2.4 噪声存在情况下的定位研究 RSSI A RSSI B RSSI D RSSI C 映射到空间区域?。 所以如果噪声存在不改变接收信号强度的排序，定位结果不会受到影响。所以为了减小由 于噪声产生 的定位误差，我们只需考虑当噪声存在影响到了接收信号强度的排序。参考图4，假设传 感节点(紫色正方形)到anchor A和anchor B的距离分别为dA和 dB，由公式(1)可知: [Pr(dA)P]dB ,10 log( dA),X (3) A,dB r(d0)d0[ Pr(dB)]dBPdB ,10 log( r(d0) d),X (4) B,dB 将dA和dB分别用Pr(dA)和Pr(dB)表示如下: [Pr(dA)P]dB,X A,dB ,10 log(d0) ,10 log(dA) (5) r(d0)[ Pr(dB)P,X B,dB ,10 log(d0) ,10 log(dB) r(d0) ] (6) dB将公式(5),(6)相减，得到如下结果: (7) [Pr(dA)P]A,dB, Pr(dB) dB,X ) ,XB,dB ,10 log( dA) r(d0) Pr(d0 dB dB 假设噪声存在最大值MaxNoise，即XdB MaxNoise ，对 于公式(7),若满足 (8) [Pr(dA)P]dB,X A,dB , Pr(dB) P ,XB,dB 0 r(d0) r(d0) dB 则可以确定dA dB，将XdB MaxNoise 代入公式(8), 化简得: Pr(dB) P (9) P , r(dA) 2MaxNoiser(d0) dB Pr(d0) dB 由公式9可知，在噪声存在的情况下，只有当Pr(dA)和Pr(dB)之间的差值大于某个θ才能 确定dA dB 。 (θ的大小与环境噪声有关。)所以在VBLS算法中，当前后相继的两个接收信号强度之差 小于θ，那么我们认为他们的信号强度的排序不能反映他们的距离排序，计算前一个anchor 节点的Voronoi区域时要将该区域扩大η倍以包括更多的模糊区域。根据环境噪声的不同，具体参数θ和η可以进行调节。 3 仿真性能评估 在这一节我们将VBLS和另外两种定位算法，Centroid 和W-Centroid进行性能比较。 3.1 信号传输模型 在仿真中我们假设系统的噪声总体服从平均值为0的高斯分布(在每个方向上噪声的平均值不为0)。我们将高斯分布的标准差σ定义为参数DON(Degree of Noise)用于反映环境的噪声水平，图 5 和图6 分别表示当DON分别为0.2和0.1时信号 的传输情况(图中圆周表示没有噪声情况下得到的接收信号强度)。 Figure 5 Radio propagation pattern when DON=0.2 图5 DON=0.2时信号传输图 Figure 6 Radio propagation pattern when DON=0.1 图 6 DON=0.1时信号传输图 3.2 仿真参数设置: 在仿真中，我们采用以下参数衡量定位算法的性能: 通信半径(Communication Range(CR)):传感节 点和anchor节点的最大通信距离。 Anchor密度(Anchor Density(AD)):单位面积上的anchor数。 DON(Degree of Noise):DON用于表示环境中的Centroid是利用节点之间的连通性进行定位，并没有用到接收信号强度，所以接收信号强度存在误差不影响Centroid的性能。从图9和图10我们还可以看出，anchor节点均匀摆放能较大的提高噪声水平。 距离误差(Distance Error(DE)):传感节点的实际位置和估算位置之间的欧几里德距离。 估算误差(Estimate Error(EE)):距离误差和通信半径之间的比值，用估算误差可以很方便的比较在不同通信半径下的定位误差的变化。 扩张系数(Extend Factor(EF)):该系数用于指定在噪声存在的情况下，计算Voronoi区域时扩大的 百分比。 3.3 估算误差随通信半径(CR)和anchor密度(AD) 的变化情况 从图7 和图8 可以看出当改变通信半径(CR)和anchor密度(AD)时，VBLS，Centroid和W-Centroid的估算误差变化情况。我们可以看出估算误差随着通信半径和anchor密度的增加而降低，这是因为随着通信半径和节点密度的增加，每个传感节点平均能够通信的anchor节点数目开始增加，这样传感节点能够用于确定自身位置的信息变多 了，所以定位误差降低了。这告诉我们提高anchor节点的密度和节点的通信半径可以提高定位的精度。 3.4 定位误差随DON的变化情况 图9和图10分别是当anchor节点均匀分布和随机分布的情况下，估算误差随DON的变化情况。从中可以看出，除了Centroid，VBLS和W-Centroid的定位误差都随着DON的增大而增大，这是因为 Centroid和W-Centroid的性能，而VBLS对于anchor摆放的形式并不敏感。 ) R(rorre noitamitsECommunication range Figure 7 AD=0.0025 DON=0.1 EF=0.1 Random 图 7 估算误差随通信半径变化情况 ) R(rorre noitamitsEAnchor density (10-4) Figure 8 CR=40 DON=0.1 EF=0.1 random 图8 估算误差随anchor密度变化情况 ) R(rorre noitamitsEDegree of noise Figure 9 CR=40 AD=0.0011 EF=0.1 Uniform 图9 anchor均匀摆放时估算误差随DON变化情况 3.5 定位误差随扩展系数(EF)的变化情况 从图11我们可以看出定位误差一开始是随着扩 展系数的增大而减小，接下来随着扩展系数的增大而增加。这是因为增大扩展系数对于定 位的影响既有积极的作用也有消极的作用。一方面增大扩展系数可以包括更大的边界区域， 可以有效地纠正由于噪声存在导致接收信号强度排序发生变化可能产生的错误;另一方面增 大扩展系数，计算得到的Voronoi区域的交集就会变大，这样定位得到的结果误差会增大。 所有根据环境噪声情况选择合适的扩展系数可以有效地提高VBLS的定位性能。 ) R(rorre noitamitsEDegree of noise Figure 10 CR=40 AD=0.0011 EF=0.1 Random 图10 anchor随机摆放时估算误差随 DON变化情况 ) R(rorre noitamitsEExtending Factor Figure 11 CR=40 AD=0.0011 DON=0.1 图11 估算误差随扩张系数变化情况 4 结论 在 接下来，我们研究了噪声存在情况下的定位问题;最后，我们将VBLS 算法和 Centroid ,W-Centroid之间进行比较，可以看出无论在anchor节点均匀摆放和anchor节点随 机摆放的情况下，VBLS都能取得较为精确的定位效果。 参考文献: [1] B. H. Wellenhoff, H. Lichtenegger and J. Collins. Global Position System: Theory and Practice, Four Edition[M]. New York: Springer Verlag, 1997. [2] A. Savvides, C. C. Han and M. B. Srivastava. Dynamic Fine-Grained Localization in Ad-Hoc Networks of Sensors[C]. In: Proceedings of Mobile Computing and Networks, Rome, Italy: ACM Press, July 2001. 166,179 [3] D. Niculescu and B. Nath. Ad Hoc Position System using AoA[C]. In: Proceedings of the IEEE INFOCOM, San Francisco: IEEE Computer and Communication Societies Press, 2003. 1734,1743 [4] P. Bahl and V. N. Padmanabhan. RADAR: An In-Building RF-Based User Location and Tracking System[C]. In: Proceedings of IEEE INFOCOM, Tel-Aviv,Israel: IEEE Computer and Communications Societies Press,2000. 2: 775,784. [5] K. Lorincz, M. Welsh. MoteTrack: A Robust, Decentralized Approach to RF-Based Location Tracking[C]. In: Proceedings of International Workshop on Location and Contex-Awareness, Berlin , Germany: Springer-Verlag Press, 2005.pp 63,82 [6] N. Bulusu, J. Heidemann, D.Estrin. GPS-less Low Cost Outdoor Localization for Very Small Devices[J]. In: IEEE Huang Liusheng, born in 1957, Professor and Ph.D. supervisor in department of computer science and technology, University of Science and Technology of China. His main research interests include wireless Wireless Sensor Networks[C]. In: IEEE 2005 International Conference on Intelligent Computing, Hefei, China: sensor network, information security and Personal Communications Magazine,2000. Vol. 7, No. 5: 28,34 [7] X. F. Shen, Zh. Wang, P. Jiang, R. Zh. Lin, Y. X. Sun. Connectivity and RSSI Based Localization Scheme for distributed computing Springer-Verlag, Aug,2005. 578,587. [8] D. Niculescu and B. Nath. Ad hoc Positioning System (APS)[C]. In: Proceedings of IEEE Globecom, New York, USA: IEEE Press, 2001.pp 2926,2931 [9] He, T. Huang, C. Blum, B.M. Stankovic, J.A and Abdelzaher, T.: Range-free Localization Schemes for Large Scale Sensor Networks[C]. In: ACM International Conference on Mobile Computing and Networking (MobiCom), San Diego, California, USA:ACM Press,2003:pp 81,95. [10] Xiao Ling, Li Renfa and Luo Juan. A Sensor Localization Algorithm in Wireless Sensor Networks Based on Nonmetric Multidimensional Scaling[J]. Journal of Computer Research and Development,2007,44(3):399,405. (肖玲，李仁发，罗娟. 基于非度量多维标度的无线传感器网络节点定位算法[J].计算机研 究与发展，2007，44(3):399,405. ) Wang Jichun, born in 1981, Ph.D. degree candidate in department of computer science and technology, University of Science and Technology of China. His main research interests include wireless sensor network and mobile ad-hoc networks 王继春 1981年生，博士研究生，主要研究方向为无线传感器网络，ad-hoc网络。 黄刘生 1957年生，教授，博士生导师，主要研究方向为无线传感器网络，信息安全和分 布式计算。 Xu Hongli, born in 1980, Ph.D. degree candidate in department of computer science and technology, University of Science and Technology of China. His main research interests include wireless sensor network and distributed computing 徐宏力 1980年生，博士研究生，主要研究方向为无线传感器网络，分布式计算。 Xu Ben, born in 1982, Ph.D. degree candidate in department of computer science and technology, University of Science and Technology of China. His main research interests include wireless sensor network and mobile ad-hoc networks. 徐犇 1982年生，博士研究生，主要研究方向为 无线传感器网络，ad-hoc网络。 Li Shanliang born in 1982, Master in department of computer science and technology, University of Science and Technology of China. His main research interests include wireless sensor networks and mobile ad-hoc networks 李善亮 1982年生，硕士研究生，主要研究方向为无线传感器网络，ad-hoc网络 . Research Background Localization is a fundamental issue for wireless sensor networks. In the past few years, many location schemes have been proposed in literatures. In this paper we introduce a novel range-free localization algorithm VBLS, which is accurate, distributed and robust. Under ideal conditions, the received signal strength indicator (RSSI) is a monotonic decreasing function as distance increases. So the distance constraints to all neighbor anchors can be derived from received signal strength indicators of anchors. The step of VBLS is as follows: first, VBLS sorts received signal strength indicator in descending order. Then, we use unit disk graph 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. We compare our work via simulation with two other range-free location schemes to show that our algorithm is efficient in both uniform anchor deployment and random anchor deployment. This paper is supported by the National Grand Fundamental Research 973 Program of China under Grant No. 2006CB303006.