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

刘玉锟，廖惜春，沈海燕，陈俊丽



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

刘玉锟1，廖惜春1，沈海燕1，陈俊丽2

（1. 五邑大学 信息学院，广东 江门 529020；2. 成都理工大学 信息科学与技术学院，四川 成都 610059）

通过分析DV-Hop算法定位过程误差产生的主要原因，在限制节点间跳数、校正相同跳数的节点之间的跳距和循环升级等3个方面进行改进，并对改进算法进行仿真实验，结果表明：在相同的环境下，本文提出的改进算法能显著提高节点定位精度和覆盖率.

无线传感器网络；节点定位；DV-Hop算法；改进DV-Hop算法

无线传感器网络（Wireless Sensor Networks，WSN）中，网络节点的位置信息是非常重要的，缺少位置信息的监测数据往往毫无意义[1]. 确定节点的位置信息后可以提供事件发生的地点信息，还可以实现对外部移动目标的定位和追踪、预测移动目标的前进轨迹等. 因此，传感器节点定位问题已成为WSN中的一个重要的研究方向.

近年来国内外学者提出了许多节点定位算法，按照定位过程中采用的技术手段基本可分为两类[2]：基于测距的定位算法[3-4]和无需测距的定位算法[5-6]. 在无需测距定位算法中，DV-Hop是一种经典的定位算法，该算法具有对信标节点比例要求较少，定位精度高等优点. 文章详细分析了DV-Hop算法过程，确定误差产生的主要原因，提出改进算法，并进行仿真实验.

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

1.1 DV-Hop算法基本原理

DV-Hop算法是由美国的Dragos Niculescu等人利用距离矢量路由和GPS定位原理提出来的一种无需测距的定位算法，该算法定位过程不依赖于直接测距方法，利用多跳信标节点信息来参与节点定位，定位覆盖率较大[7]. 其核心是在信标节点的选择过程中使用了最短路径算法，利用多跳信标节点的位置信息来计算未知节点的位置. 在该定位机制中，未知节点首先计算与信标节点的最小跳数，然后通过公式

计算平均每跳距离，其中，(x,y)、(x,y)是信标节点、的坐标，h是信标节点与()之间的跳段数. 利用平均每跳距离乘以最小跳数得到未知节点与信标节点之间的距离，最后再利用极大似然估计法计算出未知节点的坐标[8].

如图1所示，假设1，2和3是信标节点，其他节点是未知节点，定义节点通信半径为30 m. 经过信息广播和计算，由式（1）得信标节点1计算得到平均每跳距离为(50+100)/(2+7)=16.67 m，信标节点2计算得到平均每跳距离为(50+80)/(2+5)=18.57 m，信标节点3计算得到平均每跳距离为(80+100)/(5+7)=15 m. 未知节点A从信标节点3处获得平均每跳距离，则它与3个信标节点之间的距离分别为60 m(1)、30 m(2)、45 m(3)，最后利用极大似然估计法即可计算出未知节点A的位置.

图1 DV-Hop算法示意图

1.2 DV-Hop算法误差分析

1.2.1 跳距引起误差

DV-Hop算法采用平均每跳距离来估算实际距离，对节点的硬件技术要求低，实现简单. 其缺点是利用跳段距离代替直线距离，存在一定的误差，误差主要来源在于计算未知节点与信标节点之间的估计距离时，是用跳数与平均每跳距离的乘积来代替直线跳距离，然而在实际的网络拓扑中，信标节点到未知节点多数不是直线路径[9]. 该算法得出的平均每跳距离在密度均匀的各向同性网络中误差不大，但在密度不均匀的各向异性网络中，就会使定位精度下降，造成较大的误差[10]. 产生误差的原因如图l所示，未知节点A与信标节点1的实际距离（45 m）会用跳数乘以平均每跳距离（4×15 m）代替，误差由此产生.

1.2.2 跳数引起误差

在DV-Hop定位算法中，由于广播分组和传感器节点随机分布过程中可能存在冲突等因素，节点得到的到信标节点的最小跳数存在有一定偏差，且跳数越多，偏差越大. 文献[11]仿真结果显示，误差值较大的节点距信标节点跳数较大的点，而距离信标节点跳数较小的点定位精度相对较高. 这是因为DV-Hop算法采用跳段距离之和代替实际距离，跳段数增加将使累计误差加大，所以本文在改进算法中将采用限制节点跳数的方法，即未知节点若只接收距离较近的局部范围内的信标节点信息，这样会减少误差的累加，有助于提高定位精度，并从整体上降低网络通信量.

1.2.3 计算过程中存在误差

2 DV-Hop算法改进

分析DV-Hop算法中存在的误差后，本文提出相应的改进措施，思路是：第1步限制未知节点与信标节点之间的跳数，可提高定位精度，减少数据包的发送量. 第2步校正相同跳数的未知节点与信标节点之间的距离，并且将限制条件只应用于限定跳数范围内的平均每跳距离，利用最小二乘法计算出未知节点坐标. 第3步采用循环升级的方法，确定坐标的未知节点经过校正后升级为信标节点，继续定位其他未知节点，此过程可提高定位精度和网络节点覆盖率.

本文对DV-Hop算法改进的具体步骤如下：

在此基础上，门限取值应能尽量满足可以定位所有未知节点并且尽量接近所能取到的最小值，以使网络通信量相对较小，同时取值应适当加大以满足网络整体的覆盖率.

第2步确定未知节点与信标节点之间距离S. 当未知节点计算出与信标节点的距离后，通过限制跳距的约束条件来校正存在的误差. 由理论可知，未知节点到各个信标节点的跳段距离的估计值总存在误差，这会引起较大的节点定位误差. 如图1所示，未知节点A到信标节点2的跳数为2，节点的通信半径为，则A与2的距离2应大于通信半径并且小于等于2，即＜2≤2. 传统DV-Hop方法对节点A进行定位时却可能得到A的位置在2的一跳通信半径内或者在2的两跳距离之外的结论，存在较大的误差. 为此，本阶段的改进思路是，在定位过程中校正未知节点到最近信标节点的跳段距离，从而有效提高节点定位精度. 改进后的算法规则是：节点通信距离为，当未知节点距离信标节点一跳范围之内时，未知节点与信标节点之间距离1满足条件：0＜1≤；当未知节点距离信标节点(>1)跳范围之内时，未知节点与信标节点之间距离S满足条件：≤S≤·.

图2 改进的DV-Hop算法流程图

第3步将已定位的节点升级为信标节点. 在经过以上两个阶段的广播和计算后，多数未知节点都能接收到限定跳数内的信标节点广播的平均跳距，并计算出符合限定条件的跳距，初步仿真显示少数未知节点未收到广播信息，或者接收到的广播信息个数小于3[14]，则不能参与定位，可定位节点的比例就会下降，为了提高定位精度和节点覆盖率，提出了本阶段的改进，即利用循环升级的方法将已求出坐标位置的未知节点升级为信标节点，然后新的信标节点继续广播位置信息，循环执行第1步和第2步，直到计算出最后一个可定位的节点. 不可定位的节点定义为不良节点，即邻居节点个数小于3的节点.

综合上述3步改进措施的汇总算法称为IDV-Hop（Improve DV-Hop），改进算法流程描述如图2所示.

3 算法仿真与分析

节点平均定位误差为

3.1 信标节点比例对定位误差的影响

在仿真过程中，取门限值=6，节点通信半径=25 m，通过设置不同信标节点比例，比较改进算法与原始算法的平均定位误差. 其中轴表示信标节点占总节点数的比例，轴表示节点平均定位误差.

图3 节点平均定位误差和信标节点比例之间的关系

从图3中可以看出，本文提出的改进算法定位误差低于DV-Hop算法，平均定位误差降低约10%，在信标节点比例较低的情况下，改进后的算法性能较明显，特别是信标节点比例为10%的时候，定位误差降低了约50%.

3.2 通信半径对定位误差的影响

在仿真过程中，取门限值=6，信标节点比例为20%，通过设置不同节点通信半径，比较改进算法与原始算法的平均定位误差.

图4 节点平均定位误差和节点通信半径之间的关系

图5 信标节点比例和网络覆盖率之间的关系

图4是在不同通信半径下定位误差的比较，相对于DV-Hop算法，改进算法明显降低了定位的误差，平均定位误差减少10%左右，在通信半径较小的情况下，改进算法性能较明显，特别是=15 m的时候，定位精度提高了约40%. 平均定位误差均随着通信半径的增加而在逐渐减少，但是当通信半径达到30 m后，随着通信半径的增加，节点定位误差几乎保持不变，因为通信半径在一定范围内增加可以增强网络的连通度，而连通度的增加也会引起误差的增长，即一跳内的节点数增加，定位过程中不同的节点可能会定位成同一位置.

3.3 信标节点比例对定位覆盖率的影响

取门限值=6，节点通信半径=25 m仿真，通过设置不同信标节点比例，比较改进算法与原始算法的定位节点覆盖率.

从图5可以看出，随着信标节点比例的增大，改进算法和原始DV-Hop算法的定位覆盖率都在增加. 在信标节点比例为25%时，改进算法IDV-Hop的定位覆盖率即达到100%，比DV-Hop算法提高10%左右.

3.4 原始算法与改进算法仿真效果对比

图6 DV-HOP算法与IDV-HOP算法仿真效果图对比

原始DV-HOP算法仿真结果直观效果图如图6-a所示，未知节点与对应所求坐标位置用直线连接，改进DV-HOP算法仿真结果直观效果图如图6-b所示，根据两图对比能直观地得出改进算法显著地降低了定位误差的结论.

4 结论

通过对DV-Hop算法的理论分析，误差产生主要原因是由跳数、跳距和计算过程引起的，提出了限制节点间跳数，校正相同跳数的节点之间的跳距和循环升级三种措施对原始算法进行改进. 仿真实验证明：改进算法能提高原算法的定位精度和覆盖率，同时对于低密度的各向异性网络具有更高的适应性. 但由于改进算法采用了循环升级的方法，定位时间和能耗有所增加，在定位精度、定位时间和能耗之间找到一个平衡点将是下一步研究的重点.

[1] 孙利民，李建中，陈渝，等. 无线传感器网络[M]. 北京：清华大学出版社，2005.

[2] 王福豹，史龙，任丰原. 无线传感器网络中的自身定位系统和算法[J]. 软件学报，2005, 16(5): 857-868.

[3] GIROD L, BYCHOVSKIY V, ELSON J, et al. Locating tiny sensors in time and space: a case study [C]// 2002 IEEE Int’l Conf on Computer Design: VLSI in Computers and Processors, Freiburg: IEEE Computer Society, 2002: 214-219.

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

[5] NICULESSCUD D, NATH B. Ad-Hoc positioning systems (APS) [C]// 2001 IEEE Global Telecommunications Conference, San Antonio: IEEE Computer Society, 2001: 2926-2931.

[6] NAGPAL R. Organizing a global coordinate system from local information on an amorphous computer [R]. Cambridge MA: MIT AI Laboratory, 1990.

[7] 田金鹏. 无线传感器网络节点定位技术研究[D]. 上海：上海大学，2008.

[8] 卫开夏，田金鹏，王克谦. 无线传感器网络DV-Hop定位改进算法[J]. 传感技术学报，2010, 23(12): 1820-1824.

[9] 杨智锋，裴腾达，裴炳南. 基于代数重建法的DV-Hop定位算法[J]. 计算机工程，2010, 36(15): 117-119.

[10] 张佳，吴延海，石峰，等. 基于DV-HOP的无线传感器网络定位算法[J]. 计算机应用，2010, 30(2): 323-326.

[11] 于宁. 无线传感器网络定位优化方法[D]. 北京：北京邮电大学，2008.

[12] 杨智锋，裴炳南，刘波. 提高DV-Hop算法定位精度研究[J]. 计算机工程与应用，2011, 47(1): 113-115.

[13] 于宁，万江文，吴银锋. 无线传感器网络定位算法研究[J]. 传感技术学报，2007, 20(1): 188-193.

[14] 石为人，贾传江，梁焕焕. 一种改进的无线传感器网络DV-Hop定位算法[J]. 传感技术学报，2011, 24(1): 83-87.

[责任编辑：韦 韬]

Improvement on DV-Hop Localization Algorithm in Wireless Sensor Networks

LIUYu-kun1, LIAOXi-chun1, SHENHai-yan1, CHENJun-li2

(1. School of Information Engineering, Wuyi University, Jiangmen 529020, China; 2. College of Information Science and Technology, CDUT, Chengdu 610059, China)

After analyzing the localization process of the DV-Hop algorithm, in light of the main reasons for errors, this paper proposes improvements on 3 aspects: limiting inter-node hop counts, correcting the distance between nodes of the same number of hops and upgrading circulation. Simulation experiments on the improved algorithm are carried out. Simulation results show that in the same environment, the proposed algorithm can significantly improve localization accuracy and coverage.

wireless sensor networks; node localization; DV-Hop algorithm; improved DV-Hop algorithm

1006-7302（2013）02-0059-06

TP393

A

2013-01-09

广东省科技计划资助项目（2009B010800012）

刘玉锟（1988—），男，河南周口人，在读硕士生，主要从事无线传感器网络路由及定位算法的应用研究；廖惜春，教授，硕士生导师，通信作者，主要从事无线通信网络理论与技术应用研究.