武雪姣 李雪晴 丁佳静

摘 要：为了解决DV-HOP算法在节点随机部署环境下定位误差较大的缺点，提出一种基于DV-HOP多通信半径的加权双曲线定位算法RWHDV-HOP。该算法通过理想跳数与实际跳数的差值修正平均跳距，结合多通信半径使跳数小数化，利用基于跳数加权的双曲线算法估算未知节点坐标。仿真结果表明，在相同条件设置下，RWHDV-HOP算法定位精度比传统DV-HOP算法提高了25%，比RWDV-HOP算法提高了10%。因此，基于DV-HOP多通信半径的加权双曲线定位算法RWHDV-HOP在节点随机部署环境下能够较大程度上提高节点定位精度。

关键词：多通信半径;无线传感器网络;跳距优化;定位精度;加权双曲线算法

DOI：10. 11907/rjdk. 191540 开放科学（资源服务）标识码（OSID）：

中图分类号：TP312 文献标识码：A 文章编号：1672-7800（2019）008-0052-04

An Improved Wireless Sensor Network DV-HOP Positioning Algorithm

WU Xue-jiao，LI Xue-qing，DING Jia-jing

（School of Information Engineering，Heibei GEO University，Shijiazhuang 050031，China）

Abstract：Aiming at the large positioning error of DV-HOP algorithm in the environment of node random deployment， a multi-communication radius weighted hyperbolic localization algorithm RWHDV-HOP based on DV-HOP algorithm is proposed. The algorithm corrects the average hop distance by the difference between the ideal hop count and the actual hop count. The multi-communication radius refines the number of hops between nodes， and uses the hyperbolic algorithm based on hop weight to estimate the coordinates of unknown nodes. The simulation results show that in the same experimental environment， the RWHDV-HOP algorithm has a 25% higher positioning accuracy than the traditional DV-HOP algorithm and a 10% higher accuracy than the RWDV-HOP algorithm. The RWHDV-HOP algorithm based on DV-HOP multi-communication radius weighted hyperbolic positioning algorithm can improve the node positioning accuracy to a large extent in the environment of node random deployment.

Key Words：multiple communication radius; wireless sensor network;hop distance optimization;positioning accuracy;weighted hyperbolic algorithm

作者簡介：武雪姣（1992-），女，河北地质大学信息工程学院硕士研究生，研究方向为无线传感器网络定位。

0 引 言

节点自定位技术是无线传感器网络领域的重要技术之一[1-2]。目前大多数定位系统采用距离无关的定位算法[3]，DV-HOP算法是其中一种应用较为广泛的算法。

传统DV-HOP定位算法在节点随机部署情况下存在较大定位误差，综合文献分析，对其误差的改进研究主要分为3类：①跳数改进。文献[4]提出基于双通信半径的DV-HOP算法，文献[5]在其基础上提出一种三通信半径改进方法，以细化锚节点与邻居节点的跳数，使节点跳数小数化，从而提高定位精度;②跳距改进。文献[6]提出一种基于RSSI优化跳数与平均跳距的DV-HOP改进算法，文献[7]提出一种基于跳距误差加权的改进算法，文献[8]通过控制功率大小修正每跳距离以提高定位精度，文献[9]研究节点间距离与跳数的关系计算平均每跳距离。这些文献主要对算法的第二阶段跳距进行修正，以进一步提高定位精度，但增加了计算量;③节点估算方法改进。文献[10]利用粒子群算法替换最大似然估计法，提高了定位精度，文献[11]提出基于差分进化的定位算法估计未知节点最优位置。但这些算法需要的参数较多，容易陷入局部最优解。

本文针对DV-HOP算法在跳数、跳距、估算方法方面存在误差的问题，对算法的每一阶段进行改进，通过理想跳数与实际跳数的差值修正平均跳距，结合多通信半径使跳数小数化，并利用基于跳数加权的双曲线算法估算未知节点坐标。

1 DV-HOP算法

DV-HOP定位算法原理与经典的距离矢量路由算法比较相似，是由Niculescu等[12-14]学者提出的非测距算法。

在DV-HOP算法中，锚节点在网络中广播该锚节点位置和一个初始值为0的表示跳数的信息。该数据在网络中以泛洪方式传播出去，每次被转发时跳数都增加1。接收节点在其收到的关于某个锚节点所有数据中保存具有最小跳数值的信息。通过该机制，所有节点都获得了到其它节点的最小跳数值[15]。

为了将跳数转换成距离，需要估计网络中平均每跳距离。通过式（1）计算各锚节点平均跳距。

[Hopsizei=j=1，j≠iN（xi-xj）2+（yi-yj）2j=1，j≠iNhij]  （1）

其中，（xi，yi）、（xj，yj）是锚节点i和j的坐标，hij表示锚节点i和j的最小跳数，N表示锚节点数量，Hopsizei是每个锚节点的全网平均跳距。

将各个锚节点的平均跳距广播到网络中，未知节点将接收到距离自己最近的锚节点跳距作为自身跳距，并计算到其它锚节点的距离，最后通过最大似然估计法估算自身位置[16-17]。

2 改进DV-HOP算法描述

DV-HOP算法误差来源于以下几点：①锚节点在通信半径内广播数据包信息，受通信半径限制，在与其它节点通信过程中，即使同为一跳，跳距也相差很大;②锚节点在计算平均跳距时，受到网络连通的影响，锚节点并非全部进行共线式排列，导致锚节点跳距与真实值相比有一定差距;③未知节点在第三阶段估算自身跳距时，选择最近锚节点的平均跳距，不能反映出该未知节点局部范围内的网络分布情况;④最大似然估计法减少了数据使用量，降低了算法精度[18]。

本文针对DV-HOP算法存在的不足，对算法的每一阶段进行改进，提出基于多通信半径的加权双曲线定位算法RWHDV-HOP算法。

第一阶段中对锚节点引入多通信半径播送数据。具体过程如下：网络初始化，锚节点首先以通信半径R/n向网络播送数据包信息，同时将相邻节点与锚节点之间的跳数记为1/n跳[19];经过时间T，锚节点再以通信半径2R/n向网络传播数据包信息;接收到锚节点信息的节点若没有该锚节点的跳数信息，则将跳数记为2/n，如果有跳数信息，则将原跳数信息进行转发[19]。通过上述转发过程，每个节点都能获得与锚节点之间的最小跳数[19]。

第二阶段：传统DV-HOP算法计算锚节点平均跳距时忽视了锚节点共线情况，导致跳数越多，误差越大。文献[19]通过跳数加权方法对锚节点平均跳距进行改进，但只考虑了跳数越多、偏差越大的问题，而没有从节点共线度的本质上解决问题;文献[20]通过共线度检测方式优化跳距。

首先计算锚节点与矩形区域内4个顶点的距离，求出第i个锚节点在网络中理论上的最大跳数[ki]，去掉与其共线度低的锚节点，通过将实际跳数与理想跳数作差进行权重计算，最后加權计算锚节点跳距[20]。

[ki=max（di1R，di2R，di3R，di4R）]               （2）

[cij=1dij/R-hij]         （3）

[wij=cijj≠imcij]             （4）

其中，R表示通信半径，[wij]表示锚节点j对锚节点i的权重。

[Hopsizei=j≠imwij×dijhopij]        （5）

第三阶段：计算未知节点到锚节点距离时，将对应锚节点跳距考虑在内。

[dij=Hopsizei×hij]            （6）

[dij=Hopsizej×hij]           （7）

其中i为未知节点，j为锚节点，Hopsizei是距离未知节点最近的锚节点跳距，可以由式（7）或式（8）计算未知节点到锚节点的距离。综合考虑网络连通情况，将未知节点到相应锚节点的距离计算公式优化为：

[dij=1/2×（Hopsizei+Hopsizej）×hij]   （8）

第四阶段：使用加权的双曲线定位算法替换最大似然估计法。

双曲线估计算法[18]通过将第i个未知节点（xi，yi）到各个锚节点的距离公式展开，不需要方程求差，将含有未知量的项移到等式左侧得到。其中，di1，di2，…din分别表示未知节点到各个锚节点的距离。

[xi2+yi2-2x1xi-2y1yi=di12-x12-y12xi2+yi2-2x2xi-2y2yi=di22-x22-y22？xi2+yi2-2xnxi-2ynyi=din2-xn2-yn2]    （9）

则公式（9）可以转化为：

[AC=B]          （10）

[A=1-2x1-2y11-2x2-2y2？？？1-2xn-2yn]         （11）

[C=xi2+yi2xiyi]          （12）

[B=di12-x12-y12di22-x22-y22？din2-xn2-yn2]          （13）

由最小二乘准则估计出C。

[C=（ATA）-1ATB]                       （14）

为了使定位更加准确，在定位阶段引入基于跳数的权重。首先计算跳数因子[Vij]，使得锚节点距离未知节点跳数越小，V值越大，然后通过跳数因子计算权值[Wij]，最后得到加权系数矩阵W。

[Vij=j=1khopijhopij]          （15）

[Wij=Viji=1kVij]      （16）

[Wi=Wi10000Wi200？？？？000WiK]    （17）

结合式（11）、式（13）可得未知节点坐标为：

[C=（ATWA）-1ATWB]        （18）

3 实验仿真分析

为了验证本文提出的改进RWHDV-HOP算法在精确度和稳定性上是否得到提高，利用MATLAB R2016a仿真软件模拟网络测试环境，将改进RWHDV-HOP算法与传统DV-HOP算法及文献[19]中的RWDV-HOP算法进行比较。无线传感器网络区域面积为100*100m2，节点个数为100，节点随机分布，锚节点通信半径个数分别选取2、3、4。实验主要由两部分组成，分别变换锚节点比例及通信半径大小，每次实验重复200次，取平均值作为最后定位误差。为评估算法的精确度和稳定性，将定位误差Error作为评估标准。

[Error=i=1N（xi-xi）2+（yi-yi）2NR]      （19）

式（19）中，N为未知节点数目，[（xi，yi）]为未知节点估计位置，[（xi，yi）]是未知节点真实位置。

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

图1为R=35m时定位误差与锚节点比例的关系，可以看出，定位误差随锚节点比例的增大而不断降低，当锚节点比例超过0.2后，定位误差则下降缓慢。在R=35m，锚节点比例为0.2时，DV-Hop算法定位误差为30.96%，RWDV-HOP2、RWDV-HOP3、RWDV-HOP4算法定位误差分别为25.80%、19.77%、17.66%，RWHDV-HOP2、RWHDV-HOP3、RWHDV-HOP4算法定位误差分别为12.71%、8.93%、7.32%。RWHDV-HOP算法定位精度远高于DV-Hop与RWDV-HOP算法。

图1 R=35m时锚节点比例与定位误差

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

图2为锚节点n=15时定位误差与锚节点比例的关系，由图中可以清楚地看出，随着通信半径不断增大，定位误差也不断降低。当通信半径超过50m后，定位误差则下降缓慢。在R=50m，锚节点比例为0.15时，DV-HOP算法定位误差为29.52%，RWDV-HOP2、RWDV-HOP3、RWDV-HOP4算法定位误差分别为19.07%、13.35%、11.05%，RWHDV-HOP2、RWHDV-HOP3、RWHDV-HOP4算法定位误差分别为11.00%、7.77%、6.25%。RWHDV-HOP算法定位精度远高于DV-HOP和RWDV-HOP算法。

图2 通信半径与定位误差 锚节点=15

4 结语

本文针对经典DV-HOP算法存在的不足进行分析，并针对算法的每个阶段进行优化，首先利用多通信半径进行跳数小数化，优化跳距使其更接近真实值。计算未知节点到锚节点距离时，不再只考虑距离最近锚节点的影响，而是将对应的锚节点跳距考虑进去，最后通过基于跳数加权的双曲线算法进行未知节点定位，从而使定位精度得到了很大提高。但使用多通信半径在一定程度上会造成通信损耗，下一阶段考虑将RSSI算法与DV-HOP算法相结合，以克服跳数引起的误差。

参考文献：

[1] LI J，ZHANG J，XIANDE L. A weighted DV-Hop localization scheme for wireless sensor networks[C]. Dalian：International Conference on Scalable Computing & Communications/Eighth International Conference on Embedded Computing，2009.

[2] LEE S W，LEE D Y，LEE C W. Enhanced DV-Hop algorithm with reduced hop-size error in ad hoc networks[J].  IEICE Transactions on Communications， 2011 （7）：2130-2132.

[3] TOMIC S，MEZEI I. Improvements of DV-Hop localization algorithm for wireless sensor networks[J].  Telecommunication Systems， 2016， 61（1）：93-106.

[4] 李娟，劉禹，钱志鸿. 基于双通信半径的传感器网DV-Hop定位算法[J]. 吉林大学学报：工学版，2014，44（2）：502-507.

[5] 黄炎炎，陈向东，倪进权，等. 改进的DV-Hop无线传感器网络定位算法[J]. 通信技术，2014，47（7）：765-769.

[6] 张爱清，叶新荣，胡海峰，等. 基于RSSI每跳分级和跳距修正的DV-HOP改进算法[J]. 仪器仪表学报，2012，33（11）：2552-2559.

[7] 赵菊敏，李灯熬，武健. 基于DV-hop定位的误差加权改进算法[J]. 自动化仪表，2014，35（7）：1-4.

[8] LIAO W H，SHIH K P，LEE Y C. A localization protocol with adaptive power control in wireless sensor networks[J]. Computer Communications，2008，31：2496-2504.

[9] WU H，GAO R. An improved method of DV-Hop localization algorithm[J]. Journal of Computational Information Systems，2011：2293-2298.

[10] 黄艳，臧传治，于海斌. 基于改进粒子群优化的无线传感器网络定位算法[J]. 控制与决策，2012，27（1）：156-160.

[11] 林雯，张烈平，王守峰. 基于差分进化算法的无线传感器网络节点定位方法研究[J]. 计算机测量与控制，2013，21（7）：2023-2026.

[12] CUI L，CHONG X，LI G，et al. A high accurate localization algorithm with DV-Hop and differential evolution for wireless sensor network[J].  Applied Soft Computing，2018， 68：S1568494618301595.

[13] CHEIKHROUHOU O，G M B，ALROOBAEA R. A hybrid DV-Hop algorithm using RSSI for localization in large-scale wireless sensor networks[J].  Sensors， 2018， 18（5）：1469.

[14] YAN X，SUN L，ZHOU J，et al. DV-hop localisation algorithm based on optimal weighted least square in irregular areas[J]. Electronics Letters， 2018， 54（21）：1243-1245.

[15] GUI L， VAL T， WEI A， et al. Improvement of range-free localization technology by a novel DV-hop protocol in wireless sensor networks[J]. Ad Hoc Networks， 2015， 24：55-73.

[16] LI X， YAN L， WEI P， et al. Optimization of DV-hop localization algorithm in hybrid optical wireless sensor networks[J].  Journal of Heuristics， 2015， 21（2）：177-195.

[17] MAUNG N，KAWAI M. Experimental evaluationsof RSSI threshold-based optimised DV-HOP localisation for wireless ad-hoc networks[J].  Electronics Letters， 2014， 50（17）：1246-1248.

[18] 譚博，车进，张成. 基于最小二乘优化的加权DV-Hop改进算法[J]. 计算机工程与应用， 2015， 51（2）：82-86.

[19] 刘士兴，黄俊杰，刘宏银，等. 基于多通信半径的加权DV-Hop定位算法[J]. 传感技术学报，2015，28（6）：883-887.

[20] 高美凤，李凤超. 遗传粒子群优化的DV-Hop定位算法[J]. 传感技术学报，2017，30（7）：1084-1088.

（责任编辑：黄 健）