改进的DV-Hop算法在节点定位中的应用

韩雪松，杨鹃

(承德石油高等专科学校计算机与信息工程系，河北承德067000)

改进的DV-Hop算法在节点定位中的应用

韩雪松，杨鹃

(承德石油高等专科学校计算机与信息工程系，河北承德067000)

基于传统DV-Hop算法的定位技术，通过分析该算法误差产生的主要原因，提出了节点间跳数的修正方法。通过在广播通信中采用双通信频率，将节点间的跳数缩减为0．5R，减少了平均跳距的误差。通过matlab软件的实验验证，本算法可以提高节点定位精度，且提高网络通信频率，可进一步提高定位精度，定位结果达到了预期的目的。

DV-Hop算法;节点定位;zigbee

节点定位通过节点间的数据和定位算法确定未知节点的具体位置，标识网络节点的空间位置，是无线传感网络研究的重点内容之一。目前应用较多的定位算法有RSSI测距算法、AOA算法、TOA算法、DV-Hop算法、质心定位算法、APIT算法等［1］。本文研究使用的DV-Hop算法基于距离矢量，根据锚节点的平均跳距和未知节点到锚节点的跳数估算未知节点到锚节点的距离值，建立坐标与距离的方程组，通过求解方程组获得未知节点的估计坐标。

1　传统DV-HOP定位算法

1．1定位过程

DV-HOP算法的定位过程如图1所示。

锚节点通过广播方式通告自身的位置和跳数信息，邻居节点接收到该数据分组后，首先判定是否是首次接收到该锚节点的数据包，如果是首次，则保留记录，否则，比较跳数大小，保存跳数小的记录。洪泛结束后，根据记录保存的锚节点信息、跳数信息和自身坐标，求取平均跳距。平均跳距与跳数的乘积就是未知节点与该锚节点间的距离，求解距离方程组即可获得未知节点的坐标值。

1．2误差产生的主要原因

1)多跳转发的定位误差。在DV-HOP算法计算过程中，未知节点与锚节点之间的距离值是由锚节点的平均跳距和跳数的乘积确定的，实际网络拓扑中，未知节点到锚节点的转发路径是一系列折线段，而锚节点间的实际距离是直线段，转发的跳数越多，累计的误差越大，定位误差也越大［2］。

2)锚节点密度不均造成的误差。锚节点的布局由于实际空间的限制，不能实现节点的均匀布局，会出现锚节点密度不均的现象。当密度不均匀布局时，估算的平均跳距误差较大，因而造成定位误差较大［3］。

3)锚节点密度过低。如果锚节点密度过低，则锚节点周围的多跳锚节点的数目越少，与之建立路径转发的锚节点位置对平均跳距的求取影响越大，因而造成定位误差值较大。并且锚节点密度过低，网络内不良节点数目的增加［4］，降低了网络的定位效果。

1．3研究情况

传统的DV-Hop算法定位误差较大，不适合于网络稀疏的复杂工作环境，很多研究者在本算法的改进中取得了较大的成果，提高了算法的适用性。文献［5］根据两节点间的通信覆盖率在跳数计算过程中，添加跳数系数，降低了每跳距产生的距离误差。文献［6］将锚节点划分两类，一跳内的节点采用RSSI定位算法，一跳以上采用DV-Hop算法，该方法简单易行，但不适用于复杂环境中使用。文献［7］针对于矿井复杂环境，在DV-Hop定位算法应用的基础上，对跳数和跳距进行了优化处理，提高了定位的精度。文献［8］添加锚节点的自定位过程，将定位结果与实际值相比较，得到计算的修正值，以提高定位的精度。改进的定位效果从多个角度进行了算法的优化，提高了定位精度，但也附加了一些其他技术问题，需要进一步的完善。

2　改进的DV-Hop算法

2．1改进的基本思想

DV-Hop算法的主要误差集中在平均跳距和跳数的问题，基于通信半径、节点间距离和跳数三者之间的关系，本文采用双通信半径的思想，减少平均跳距误差。文献［9］中采用双通信半径用于改善DVHop算法，但通信半径设定为R和R/2，在实际使用中由于网络通信环境不同，很难确定R/2的射频信号大小，需进行节点网络测试。

无线网络通信信号模型公式如下式所示。

其中:λ—路径损耗系数，一般取2～5;ξ—随机数，符合高斯分布，平均值为0，其标准差一般取4～10; d0—参考距离，m;d—估计距离，m;Pr(d0)—参考距离的接收信号强度，dbm;Pr(d)—估计距离的接收信号强度，dbm。

2．2DV-Hop算法的具体改进方法

1)网络锚节点首先以RF2广播数据包分组，其中包括节点ID、节点坐标、初始跳数、转发时间等信息，数据包分组的初始跳数值设定为0．5。收到数据包分组的锚节点保存记录，转发时间为0后，首次广播结束。

2)网络锚节点以RF1广播数据包分组，数据包格式与步骤1相同，但初始跳数为1。如果网络节点首次接收到该数据包分组，则保存记录，否则判定跳数大小，保存跳数小的记录。将跳数加后，数据包分组转发给其他邻居节点。转发时间为0后，广播结束。

3)与传统的DV-Hop算法计算一致，求取平均跳数，计算距离值，求解方程组。

3　仿真实验与分析

为了验证改进算法的有效性，本文基于matlab软件搭建仿真环境模拟和计算未知节点的定位效果，研究在不同锚节点密度和通信半径的条件下，平均定位误差的大小。仿真环境设定在100 m×100 m的范围内，初始锚节点个数12个，通信半径30 m，网络环境中假定路径损耗系数为4，信号的干扰用均值为5的高斯白噪声表示，采用最小二乘法求解方程组。实验中随机生成100个未知节点，计算节点定位的平均误差值。

通信半径对定位误差的影响如图2所示。网络通信半径增加，则平均定位误差相对减小，这也说明在网络情况允许的情况下，应尽量采用大功率的射频信号发射，可降低网络的平均定位误差。锚节点个数初始增加可明显减小平均定位误差，但当节点密度达到一定程度，平均定位误差基本保持不变。

以通信半径30 m为例，两种算法对比图如图3所示。平均定位误差相差很大，基于传统DV-Hop算法的平均定位误差在35．28%～38．8%，改进后的算法平均定位误差在25．1%～28．8%，改进后相比于改进前大约提高了10%个精度，达到了预期的目的。

4　结束语

本文在传统的DV-Hop基础上采用双通信半径方法，将节点间距离的求取误差降低了0．5R的误差，通过仿真实验看出，通信半径对于定位结果影响较大，锚节点密度在达到一定程度后对定位结果影响不大。本文只是针对于节点间距离的计算进行了改进，后续研究中应考虑求解方程组最优解的方法，更进一步提高定位精度。

［1］杨鹃，韩雪松．无线传感网络节点定位技术［J］．承德石油高等专科学校学报，2013，15(6):39－43．

［2］夏少波，周建梅，朱晓丽，等．基于跳数区域划分的DV－Hop改进算法［J］．传感技术学报，2014，27(7):964－969．

［3］李雪梅．基于DV-HOP算法的无线传感器网络节点定位技术的研究［D］．太原:太原理工大学，2012．

［4］李冬．基于DV-Hop的无线传感器网络定位算法研究与改进［D］．南京:南京理工大学，2013．

［5］谭志，张卉．基于节点间覆盖关系的改进DV-Hop算法［J］．北京邮电大学学报，2014，37(1):35－38．

［6］Liu Y，Qian ZH，Liu D，et al．A DV-hop positioning algorithm for wireless sensor network based on detection［A］//2009 Fifth International Joint Conference on INC，IMS and IDC［C］．Seoul:International joint conferences，2009．

［7］方旺盛，吴胜宝．基于井下异构无线传感器网络DV-Hop定位算法的改进［J］．传感器与微系统，2014，33(5):125－128．

［8］黄浩，卢文科．无线传感器网络中基于信标节点反馈的多跳测距定位算法改进［J］．传感技术学报，2009，22(2): 269－272．

［9］李娟，刘禹，钱志鸿，等．基于双通信半径的传感器网络DV-Hop定位算法［J］．吉林大学学报(工学版)，2014，44 (2):502－507．

Improvement of DV-Hop Algorithm in Application of Node Localization

HAN Xue-song，YANG Juan
(Department of Computer and Information Engineering，Chengde Petroleum College，Chengde 067000，Hebei，China)

Based on the traditional positioning technology of DV-Hop algorithm，through analysis of the main reason for the error occurring in the algorithm，this paper proposes the correction method of Hop count between nodes．Double frequency is used in radio communication．The hop count between nodes can be reduced to 0．5R，which can reduce the average jump distance error．Through matlab software experimental verification，this algorithm can improve the node location accuracy．The higher frequency of network communication can further make the positioning accuracy lower．Positioning results reached the expected purpose．

DV－Hop algorithm;node localization;zigbee

TP393

B

1008-9446(2015)02-0047-03

2014-11-12

韩雪松(1980－)，男，吉林省吉林市人，承德石油高等专科学校计算机与信息工程系讲师，主要研究方向为无线网络通信和数据融合技术等。