无线传感器网络中非测距混合定位算法*

王 越， 周 奥， 刘金城

(重庆理工大学 计算机科学与技术学院,重庆 400054)

无线传感器网络中非测距混合定位算法*

王 越， 周 奥， 刘金城

(重庆理工大学 计算机科学与技术学院,重庆 400054)

节点定位是无线传感器网络中的关键技术。针对质心定位算法和DV-Hop算法的不足，提出了一种非测距混合定位算法，采用DV-Hop算法得到节点之间的距离和粗略的未知节点估计坐标以作为质心定位算法的权重，经过两次加权质心定位算法得到未知节点更为精确的坐标。仿真实验结果表明:在不同情况下，该混合算法均能获得比两种原始算法更高的定位精度；与其他混合定位算法相比，计算量小，耗能更低。

无线传感器网络； DV-Hop算法； 质心定位算法; 混合； 非测距

0 引 言

无线传感器网络系统主要应用于人为力量无法到达的环境复杂区域事件的监测和数据的采集与传输，而事件发生的位置对于监测消息是至关重要的，没有位置信息的监测消息是毫无意义的，因此，需要利用定位技术来确定相应节点的位置信息。

在无线传感器网络定位算法中，可分为基于距离(range-based)和距离无关(range-free)的定位算法。基于距离的定位算法有以下几种常见测距方法：基于到达时间(time of arrival,TOA)的测距方法[1]、基于到达时间差(time difference of arrival,TDOA)的测距方法[2]、基于接收信号强度指示(received signal strength indication,RSSI)的测距方法[3]。文献[4]中给出了基于TOA定位的一种简单实现，即采用伪噪声序列信号作为声波信号，根据声波的传播时间来测量节点间的距离。距离无关的定位技术不需要测量目标的距离或者方位角，对节点的硬件要求不高，但定位误差往往要比基于距离的定位方法要高。距离无关的定位方法需要确定包含待测目标的可能区域，以此确定目标位置，主要的算法包括质心(centroid)定位算法、距离向量—跳段(DV-Hop)定位算法、自组织定位(amorphous positioning)算法、近似三角形内点测试(APIT)法[5]等。

现有的混合定位算法基本是将基于距离和距离无关的定位方法结合起来以获得更高的定位精度，文献[6]提出了采用RSSI的改进质心定位算法，将RSSI作为质心定位的算法的权重求得未知节点坐标。文献[7]提出了一种基于RSSI测距误差修正的改进型DV-Distance差分定位算法。由于使用了基于距离的技术，这些混合定位算法需要外在的硬件设备支持，成本和能耗上没有优势；基于RSSI的测距方法虽然在实验环境中表现出良好的特性，但是在实际环境中，温度、障碍物、传播模式等条件往往都是变化的，使得该技术在实际应用中仍然存在困难。

本文所提出的DV-Hop和加权质心定位算法的混合定位算法是基于非测距技术的，DV-Hop算法和质心定位算法均是基于网络连通性，无需信标节点和未知节点协调，只需要节点之间能相互通信，较基于测距技术的混合定位算法实现比较简单，也不需要外在的硬件设备支持，成本很低，受环境影响小，通过仿真实验表明:混合定位算法可以获得比原有两种基础算法更好的定位精度。

1 非测距混合定位算法

在DV-Hop算法中，未知节点和锚节点之间的距离用平均每跳距离与跳数的乘积所求得，因此,在分布均匀、各项同性[8]的网络中误差较小。对传统的DV-Hop算法分析可知，无线传感器网络中节点均为随机分布，并且使用平均跳距来计算未知节点与锚节点之间的距离，并不能准确反映网络中的实际平均每跳距离，因此，定位精度较低，定位误差较大。同时，质心定位算法也适合在锚节点分布密集和节点分布均匀的的网络。如图1，A,B,C,D,E,F,G点为已知位置坐标的锚节点，X为待定位的节点，如果使用质心定位算法来计算的X的坐标，由于有奇异点D的存在，使得图形的重心发生向D的倾斜，故而所求得的X的坐标将出现较大的误差[9]。

针对以上这两种算法的优缺点，在本文中提出了一种基于DV-Hop和加权质心定位的混合定位算法。根据概率论原理[10]，这两种定位算法都是为了准确计算出未知节点的坐标，如果所计算出的坐标差值越小，那么,这些坐标就越接近未知节点的真实坐标。混合定位算法的基本思想是：首先使用DV-Hop定位算法得到每个锚节点的平均每跳距离和未知节点的粗略坐标，然后以质心定位算法为基础，进行两次加权质心定位，权值反映出不同锚节点坐标对未知节点坐标估计的影响大小。采用这种思想的目的是因为在锚节点数目较少的情况下DV-Hop算法定位精度要高于质心定位算法的精度，此时通过DV-Hop算法对加权质心定位算法中权值的影响来提高混合定位算法的定位精度，而当锚节点数目增加到一定数目时，质心定位算法将优于DV-Hop算法，混合定位算法经过两次加权的目的就是使得DV-Hop算法对混合定位算法不产生特别大的影响，使得在质心定位算法效果较好的情况下，混合定位算法的定位精度主要依赖于质心定位算法。具体的算法如下：

假设在未知节点通信半径中的锚节点数量为N，用DV-Hop定位算法求得未知节点到锚节点的距离和未知节点的估计坐标P0，依此从中选出N个锚节点使用加权质心定位算法，得到 个重心Z1,Z2,…,ZN。权值计算方法和加权质心定位算法如下

(1)

(2)

在第一次加权质心定位算法中，Ri,Rj为未知节点到锚节点的估计距离，N为未知节点通信半径内的锚节点数量，Wi为锚节点i的权值。第二次加权知心定位算法中，Ri,Rj为P0与Zi之间的距离，N为第一次加权求得的重心数量，Wi为重心Zi的权值。

如图2所示，P为未知节点，P0为使用DV-Hop所计算出来的未知节点坐标，A,B,C,D,E,F,G为P通信半径内的锚节点，从这7个锚节点中依此选出7个使用质心定位算法得到了Z1,Z2,Z3,Z4,Z5,Z6,Z7。然后用求得的P0和7个重心第二次使用加权质心定位算法从而估算出更精确的未知节点的坐标。

图2 非测距混合定位算法

整个算法的步骤如下：

1)对未知节点P使用DV-Hop算法，得到P与通信半径内锚节点之间的距离Ri，同时估计出P的坐标P0。

2)依此从未知节点P通信半径内的N个锚节点中选出N-1个使用式(1)和式(2)得到N个重心Z1,Z2,…,ZN，计算出P0和这N个重心之间的距离

(3)

3)根据上一步所得的距离再一次使用质心定位算法得到更精确的估计坐标。

2 仿真实验

通过Matlab仿真平台对算法进行了验证，并且在相同的实验环境中与质心定位算法、DV-Hop算法以及一种混合定位算法进行了对比实验，最后在此基础上对实验结果进行了分析。

仿真实验环境为：网络节点随机分布在200 m×200 m的矩形区域中，通信半径为R=50 m。同样进行100次实验。

1)锚节点数量对定位精度的影响

节点数量为200个，在改变锚节点比例的情况下，质心定位算法、DV-Hop算法和混合定位算的性能如图3所示。随着锚节点数量的不断上升，质心定位算法、DV-Hop算法和混合定位算法的定位精度也不断上升。从图4可以看出:当锚节点数目小于40的时，改进的混合定位算法的定位误差要高于DV-Hop算法，但它们的曲线十分的相似，它们的相关性系数为0.955 1，而质心定位算法与混合定位算法的相关性系数为0.881，这是由于锚节点数目比较小的时质心定位算法定位误差比DV-Hop算法定位误差高15 %左右，故而此时的混合定位算法主要依赖于DV-Hop算法。随着锚节点数目的增加，混合定位算法的定位误差不断减小，质心定位算法定位精度不断提高，并且逐渐优于DV-Hop算法，此时混合定位算法对DV-Hop算法、质心定位算法的相关系数分别为0.898 4和0.958 4，这说明混合定位算法定位在此时主要依赖于质心定位算法。

图3 锚节点比例对定位精度的影响

2)节点数量对定位精度的影响

锚节点比例为30 %，在改变传感器网络中节点数量的情况下，质心定位算法、DV-Hop算法和混合定位算法的性能如图4所示。可以看到在节点数量不断增加的情况下，三种算法的定位误差都有着明显的下降，这是由于网络中未知节点周围的邻居节点越多，那么所获得的参考位置信息也就越多，从而将降低定位误差。从图4可以看出，混合定位算法的定位精度要高于原有的两种算法，混合定位算法的定位误差比DV-Hop算法平均减少10 %左右。

图4 节点数量对定位精度的影响

3)通信半径对定位精度的影响

节点数量为200个，锚节点比例为30 %,在改变节点通信半径的情况下，质心定位算法、DV-Hop算法和混合定位算的性能如图5所示。随着节点通信半径的增加，三种定位算法的定位精度也随之增加，这是由于通信半径增加，网络连通性更好，节点与节点之间的通信增加，从而未知节点所获得的参考信息也就更多，锚节点的平均跳距也就更加准确。从图5可知，混合定位算法要明显优于两种原始的算法，混合定位算法的定位误差比DV-Hop算法平均减少5 %～7 %。

图5 通信半径对定位精度的影响

4)在不同锚节点数量情况下与其他混合定位算法比较

文献[11]提出了一种RSSI和DV-Hop的混合算法，图6是本文非测距混合定位算法与此种算法的仿真实验结果。实验环境为：网络节点随机分布在100 m×100 m的矩形区域中，节点数量为200个，通信半径为R=20 m。

如图6所示仿真结果，随着锚节点数目的提高，两种算法的定位精度都得到很大的提高，文献[12]的混合算法与本文的改进算法的定位精度差异不大，但是文献[12]的算法中使用了RSSI技术，这是一种利用信号衰减来估算距离的技术，必然会带来更高的算法复杂度和更大的计算量。

图6 与其他混合定位算法比较

3 结束语

本文对DV-Hop算法和质心定位算法进行了简单的介绍与分析，提出了一种基于DV-Hop算法和质心定位算法的混合定位算法。它采用DV-Hop算法得到节点之间的距离和粗略的未知节点估计坐标以作为质心定位算法的权重，经过两次加权质心定位算法得到未知节点更为精确的坐标。仿真实验表明:混合定位算法比原始算法定位精度更高，与其他混合的定位算法相比较定位精度差异不大，计算量更小。

[1] Harter A,Hopper A,Steggles P,et al.The anatomy of a context-aware application[C]∥Proc of the 5th Annual ACM/IEEE Int’l Conf on Mobile Computing and Networking,Seattle:ACM,1999:59-68.

[2] Girod L,Estrin D.Robust range estimation using acoustic and multimodal sensing[C]∥Proc of IEEE/RSJ Int’l Conf on Inte-lligent Robots and Systems,IROS’01,Maui:IEEE Robotics and Automation Society,2001:1312-1320.

[3] Girod L,Bychovskiy V,Elson J,et al.Locating tiny sensors in time and space:A case study[C]∥Proc of the 2002 IEEE Int’l Conf on Computer Design:VLSI in Computers and Processors,Freiburg:IEEE Computer Society,2002:214-219.

[4] Yang Z,Pan J,Cai L.Adaptive clock skew estimation with interactive multi-model Kalman filters for sensor network[C]∥Proceeding of IEEE International Conference on Communication,ICC 2010,Cape Town,South Africa,2010:1-5.

[5] Azzedine Boukerche.DV-LOC:A scalable localization protocol using voronoi diagrams for wireless sensor networks[J].IEEE Wireless Communications,2009,9:50-55.

[6] 李文辰，张 雷.无线传感器网络加权质心定位算法研究[J].计算机仿真，2013,30(2)：191-194.

[7] Bulusu N,Heidemann J.GPS-less low-cost outdoor localization for very small devices[J].IEEE Personal Communications,2000,7(5):28-34.

[8] Schuhmann Stephan,Herrmann Klaus,Rothermel Kurt,et al.Improved weighted centroid localization in smart ubiquitous environments[EB/OL].[2008—06—23].http:∥www.Springer-Iink.comlindex/131121u67r12445u.pdf.

[9] Bai Jinjing,Yan Xinping,Zhang Cunbao,et al.Research of location based on mixed algorithm of weighted centroid and DV-Hop in WSNs[J].Application Research of Computers,2009,26(6):2248-2250.

[10] Cheng Yuanguo,Xu Hui.Hops-weighted centroid localization algorithm for wireless sensor networks[J].Computer Engineering and Application,2009,45(7):105- 107.

[11] 金 纯，叶 诚，韩志斌，等.无线传感器网络中DV-Hop定位算法的改进[J].计算机工程与设计，2013,34(2):401-404.

Range-free and hybrid localization algorithm forwireless sensor networks*

WANG Yue, ZHOU Ao, LIU Jin-cheng

(School of Computer Science and Technology,Chongqing University of Technology,Chongqing 400054,China)

Node localization is a significant technology in wireless sensor networks(WSNs).Aiming at deficiency of centroid localization algorithm and DV-Hop algorithm,a range-free and hybrid localization algorithm is proposed,uses DV-Hop algorithm to get rough distance between different nodes and rough-estimated unknown node coordinate for weigh of centroid localization algorithm.By twice-weighed centroid computation,more precise coordinate of unknown node can be obtained．Simulation results show that this algorithm improves the precision of node localization compared with two original localization algorithms,and its calculation amount and energy consumption are lower than other hybrid localization algorithms.

wireless sensor networks(WSNs); DV-Hop algorithm; centroid localization algorithm; hybrid; range-free

2014—06—15

重庆市科学技术委员会科技攻关项目(2009AC2068)

10.13873/J.1000—9787(2015)02—0147—03

TP 393

A

1000—9787(2015)02—0147—03

王 越(1961-),男,重庆人,博士,教授,现从事计算机技术与无线传感器网络方向教学和研究工作。