无线传感器网络DV-HOP定位算法的改进*

李 辉，熊盛武，刘 毅，段鹏飞

(武汉理工大学计算机科学与技术学院，武汉430070)

无线传感器网络［1－4］集传感器技术、微机电系统技术、无线通信技术、嵌入式计算技术和分布式信息处理技术于一体，通过传感器与外界交互，并完成数据采集、处理及通信等功能，广泛应用于环境、交通、军事、航空、医疗卫生等多方面。而对于大多数应用来说，没有时空标识的数据用处有限，因此，节点的准确定位在传感器网络的应用中起关键作用［5］。

现有的定位算法大致可分为两类:距离相关定位算法 (Range-based)［6］和距离无关定位算法(Range-free)［7］。距离相关定位算法通过测量距离角度等信息来进行定位，对硬件要求较高且成本较高，这与无线传感器网络的硬件要求简单和能量消耗受限不相适应.。而距离无关算法不需要使用测距技术，只利用节点间的估计距离来计算未知节点的位置，因此由于传感器节点能源、成本、体积等因素的限制，距离无关定位算法具有更高的实用性。

文中首先描述DV-Hop定位算法的基本原理和误差产生的原因，然后针对DV-Hop算法和目前已有的改进算法的不足，提出了改进的无线传感器网络DV-Hop定位算法(IDV-Hop定位算法)，最后将IDV-Hop与传统的DV-Hop算法和已有改进算法进行分析比较，仿真结果表明，本文提出的IDV-Hop定位算法进一步提高了定位精度。

1 DV-Hop定位算法误差分析

DV-Hop定位算法［8－9］是一种基于距离矢量计算跳数的算法，其基本思想是将未知节点到信标节点之间的距离用平均每跳距离和两者之间跳数的乘积表示，使用三边定位法或最大似然估计法获得未知节点位置信息。

1.1 误差分析

由DV-Hop定位算法的原理可知，该算法的主要误差在于计算未知节点与信标节点之间的估计距离时，是用跳数乘以平均每跳距离来表示，而当网络中的跳数大于或等于2跳时，未知节点和信标节点之间的实际距离与平均每跳距离所得的值存在较大的误差，会使定位精度下降。

图1 信标节点与未知节点距离示意图

信标节点L1与未知节点A的实际距离(粗虚线)用跳数乘以平均每跳距离(细虚线)代替，此时，会产生较大误差。因此，针对传统DV-Hop算法的缺点，文献［10］对算法的改进主要是在第2阶段，当每个信标节点计算出自已的平均每跳距离以后，将自已的平均每跳距离作为一个校正值广播至网络中。广播的数据分组格式为{idi，Ci}，Ci是第i信标节点计算出的平均每跳距离。每个接收到此数据分组的节点将该信息添加到自已的数据表中，然后继续向其邻居广播，重复id的信息分组将被丢弃。经过此阶段的广播后，所有节点都已知所有信标节点的平均每跳距离，然后再将所有的平均每跳距离相加取平均，得到整个网络的平均每跳距离为:

其中:Ci是第i个信标节点计算的平均每跳距离;n为网络中的信标节点总数。

之后，每个未知节点计算到自已数据表中的各信标节点的距离为:

2 IDV-Hop定位算法

在文献［10］中，利用整个网络信标节点的平均每跳距离代替原始算法中最近信标节点的平均每跳距离，从而使未知节点计算到各信标节点之间的估计距离更接近实际距离，使得改进算法的平均定位精度得到提高，但是所有未知节点都用一个全网平均每跳距离，这样计算出的未知节点到信标节点的距离与实际距离仍存在误差。针对此问题，本文对未知节点计算到信标节点距离时，所用到的平均每跳距离做了进一步改进。

2.1 前提假设

为了讨论方便，本文做出如下假设:

(1)每个传感器节点有唯一的ID，传感器节点被随机部署;

(2)空间信号传输模型为理想的球体;

(3)所有传感器节点都是一样的，电量和计算能力有限;

(4)信标节点能够通过GPS接受装置或其他手段［11－12］即时地获取二维坐标信息;

(5)所有传感器节点和锚节点是时间同步的。

2.2 IDV-Hop定位算法描述

2.2.1 计算最小跳数

首先，所有信标节点向网络广播消息，消息中包括表{Xi，Yi，HopCount}，信标节点只与网络中邻近的节点交换信息。Xi，Yi是信标节点的坐标，HopCount是节点接收到广播消息信标节点的跳数，初始值设为0。当某个节点接收到这个表的消息，将HopCount值加1后继续向它的邻居广播(除了来源方向)，如果某节点接收到来自相同信标节点的多个消息，则表明它到该信标节点有多条路径。此时，节点将保留含有最小跳数值的信标，而忽略其他信标，这就保证了所得到的跳数值是它到信标节点的最短路径。最终，经过这个过程，只要整个网络是连通图，网络中的所有节点都能获得各信标节点的坐标以及它到各信标节点的最短距离，也就是跳数。

2.2.2 计算未知节点和信标节点的距离

按照DV-Hop算法中第二阶段，每个信标节点计算出自已的平均每跳距离，即校正值，然后未知节点首先按文献［10］的方法计算出全网平均每跳距离Average(如式1所示)，之后得出信标节点i的平均每跳距离误差，如式(3):

其中，节点j为信标节点i数据表中的其他信标节点;|dtrueij－destimatedij|表示信标节点 i、j之间实际距离与计算距离之差的绝对值;anchor_to_anchorij表示信标节点i到信标节点j的最小跳数

最终，信标节点i的平均每跳距离，即校正值为:

其中，k为变量参数，k的取值根据具体的网络环境而定。

这样，各信标节点将自已按式5计算出的平均每跳距离anchor(i)作为一个校正值广播至网络中，校正值采用可控洪泛法在网络中传播，这意味着未知节点仅接受获得的第1个校正值，而丢弃所有后来者，这个策略确保了绝大多数未知节点可从最近的信标节点接收校正值。

最终，每个未知节点计算到自已数据表中的各个信标节点的估计距离为:

其中，anchor(i)为未知节点i获得的最近的信标节点校正值，hopij为未知节点i到信标节点j的最小跳数。

2.2.3 计算未知节点坐标

在传统DV-Hop定位算法中，未知节点利用记录3个以上到各个信标节点的距离值，通过三边测量法或极大似然估计法计算未知节点的坐标，而对于在其通信范围内少于3个信标节点的未知节点没有进行处理，从而造成有些节点无法定位。在IDV-Hop定位算法中对出现的这些节点也进行了处理，方法如下:

(1)当k大于或等于3时，设某未知节点在其通信范围内可参考的信标节点数为k，未知节点A通信范围内的信标节点为P1、P2、P3…Pk，取离未知节点A最近的3个信标节点P1、P2、P3。则:

①当向量P1P2和向量P2P3的笛卡尔乘积为0时，说明3个信标节点在同一直线，此时去掉信标节点P1、P2、P3中离节点A最远的一个，重新选取除节点P1、P2、P3以外距离节点 A较近的信标节点 P4，然后返回①中重新判断，直到未知节点参考的3个信标节点不在同一直线。

②当向量P1P2和向量P2P3的笛卡尔乘积不为0时，利用二维定位算法中的最小二乘法来求出未知节点的近似坐标，方法如下:设3个信标节点坐标P1(x1，y1)，P2(x2，y2)，P3(x3，y3)，未知节点离各锚节点的距离分别是 d1，d2，d3，建立方程组:

因为未知节点与信标节点的距离，避免不了和实际距离di有一定的误差，设ξ是距离测量误差，整理可得是 k－1维随机误差向量。由矩阵方程可得ξ=b－Ax，ξ越小，定位越准确，利用最小二乘法原理可以求出待测节点坐标的估计式:

(2)当K等于2时，未知节点与两个锚节点在一个平面上(设未知节点为P，两个锚节点为N0，N1)，则分别以N0，N1为圆心，以N0P，N1P为半径的两圆相交，如果交于一点时，则为所求的P点;如果交于两点(x1，y1)和(x2，y2)，则取为P点。

2.3 算法分析

根据IDV-Hop算法的实现过程，对其通信开销能耗进行分析，结果如下:

算法采取可控的洪泛过程，每个节点只转发相同的消息一次，每个锚节点共发3次消息，其中包括(1)锚节点向邻居节点广播自身位置信息;(2)各锚节点将自已的平均每跳距离作为一个校正值广播至网络;(3)各锚节点将自已修正后的校正值广播至网络中。这些消息被所有节点转发一次，假设一共有m个锚节点，n个未知节点，则网内的消息量为(3·m·n)packets。

3 实验仿真及分析

为了验证本文IDV-Hop定位算法的可行性和有效性，对算法进行仿真实验，并将DV-Hop算法、已有改进算法和本文IDV-Hop定位算法的仿真结果进行了对比分析。

3.1 仿真环境和参数

实验在 MATLAB 2009 的环境下进行［13－14］，网络中共有300个传感器节点随机地布设在1 000 m×1 000 m的二维区域内，锚节点比例为20%，采用随机布撒的方式，所有节点的分布如图2所示，此时网络的平均连通度为31.893 3，网络的邻居信标节点平均数目为6.553 3。在实验中，假定所有未知节点和锚节点的通信半径为200 m，信道衰减指数为4，运行50次。

图2 节点随机分布图

3.2 性能分析与比较

图3比较了改进算法中变量k的不同取值对算法定位精度的影响。从图可以看出，当节点总数和信标节点数均恒定的情况下，定位精度取决于变量参数k的值;当变量参数k的值为定值的情况下，定位精度取决于网络中信标节点的比例。从三条曲线可以看出，k的取值区间为［0.5 0.9］时，定位精度较小，尤其是当k取值在0.7左右。

图3 不同k值对定位精度的影响

改进后定位算法的定位结果如图4所示，其中线段连接的是未知节点实际位置与估计位置，圆代表未知节点实际位置，线段越长表示估计出的未知节点误差越大，从图中整体可以看出，改进后估计出的未知节点坐标与实际位置误差较小。

图4 IDV-Hop定位算法中未知节点实际位置与估计位置

图5出示了改进后定位算法在节点数为300，信标节点比例为20%，k值为0.7时，每个未知节点的定位精度，从图中可以看出，大部分未知节点的定位精度都在30%以内，部分未知节点的定位精度达到10%以内。

图5 IDV-Hop定位算法中各个未知节点的定位精度

将本文改进算法中变量k取值为0.7，与原DVHop算法、已有改进算法的定位精度进行比较。图6中网络节点为300，信标节点比例分别为5%、10%、15%、20%、25%、30%、35%时三种算法定位精度的比较情况，从仿真结果可知，在节点总数不变的情况下，三种定位算法的定位精度总体上都随信标节点的增加而提高，本文改进算法的定位精度比已有DV-Hop改进算法平均提高了3.6%，比DVHop算法平均提高了5.9%。

图6 锚节点数量对定位误差的影响

4 总结

节点定位在无线传感器网络的应用中起着重要作用，文中对DV-Hop算法原理以及产生误差的原因进行了分析，并针对原算法以及已有改进算法在未知节点到信标节点距离计算中的不足，对信标节点的平均每跳距离做出了改进，并消除了因拓扑结构而造成的不可定位节点，通过仿真实验结果可以看出，改进后的算法优于原算法和已有改进算法，提高了定位精度。由于该算法仍需要布设一定数量的锚节点来计算校正值，虽然数量不大但增加了成本，下一步将致力于研究采用单个移动锚节点来对三维空间中未知节点进行定位，使算法更加优化。

［1］杜治高，钱德沛，刘铁.无线传感器网络中的地址分配协议［J］.软件学报，2009，20(10):2787－2798.

［2］王福豹，史龙，任丰原.无线传感器网络中的自身定位系统和算法［J］.软件学报，2003，16(05):857－868.

［3］Arampatzis T，Lygeros J，Manesis S.A Survey of Applications of Wireless Sensors and Wireless Sensor Networks［C］//Proceedings of the IEEE International Symposium on Mediterrean Conference on Control and Automation，Limassol，Cyprus，2005:719－724.

［4］Demirkol I，Ersoy C，Alagoz F.MAC Protocols for Wireless Sensor Networks:A Survey［J］.IEEE Communications Magazine，2006，44(4):115－121.

［5］Jun Xiao，Hong Chen，Shi Zhang.Research of Range-Based Synergetic Localization Algorithm in Wireless Sensor Networks［C］//Chinese Control and Decision Conference 2008.Shandong.China:IEEE，2008:2040－2044.

［6］杨凤，史浩山，朱灵波，等.一种基于测距的无线传感器网络智能定位算法［J］.传感技术学报，2008，21(1):135－140.

［7］Basagni S，Carosi A，Melachrinoudis E，et al.Protocols and Model for Sink Mobility in Wireless Sensor Networks［J］.ACM SIGMOBILE Mobile Computing and Communications Review，2006(10):28－30.

［8］王新生，赵衍静，李海涛.基于DV-Hop定位算法的改进研究［J］.计算机科学，2011，38(02):76－78.

［9］刘少强，庞新苗，樊晓平，等.一种有效提高节点定位精度的改进 DV-Hop算法［J］.传感技术学报，2010，23(8):1179－1183.

［10］彭刚，曹元大，孙利民.无线传感器网络节点定位机制的研究［J］.计算机工程与应用，2004，40(35):27－29，83.

［11］Shen X，Wang Z，Jiang P，et al.Connectivity and RSSI Based Localization Scheme for Wireless Sensor Networks［C］//2005 International Conference on Intelligent Computing，Lecture Notes on Computer Science.Vol.3645，p.578－587，Aug.2005.

［12］张品秀，黄操军，乔相伟.基于自适应扩展Kalman滤波的SINS/GPS 深组合研究［J］.传感技术学报，2010，23(3):408－412.

［13］张葛样，李娜.MTLAB仿真技术与应用［M］.北京:清华大学出版社，2003.

［14］邱晓林.基于MATLAB的动态模型与系统仿真工具［M］.西安:西安交通大学出版社.2003.