跳数和跳距修正的距离向量跳段定位改进算法

孙利娟　胡凤启

摘 要： 由于在无线传感网络中传感节点随机分布，致使距离向量跳段（DV?Hop）定位算法的定位误差偏大，为此，采用跳数和跳距修正的方法对距离向量跳段定位算法进行改进。在计算信标节点和未知节点跳数的过程中引入节点通信距离的影响，使得节点之间的实际跳数计算更加准确；再利用线性搜索算法获取最优信标节点间的平均跳距，使信标节点的平均跳距更加精确。对比仿真实验结果表明，改进算法大大提升了定位的精度，提升幅度高达15%。

关键词： DV?Hop算法； 无线传感器网络； 跳数； 平均跳距； 定位精度

中图分类号： TN711?34； TP393 文献标识码： A 文章编号： 1004?373X（2017）07?0001?04

Improved DV?Hop localization algorithm based on hop count and hop distance modification

SUN Lijuan1， 2， HU Fengqi3

（1. School of Computer Science， Wuhan University， Wuhan 430072， China；

2. Department of Information and Electronics， Kaifeng Vocational College of Culture and Arts， Kaifeng 475000， China；

3. Hydrology and Water Resources Bureau of Henan Province， Zhengzhou 450003， China）

Abstract： The positioning error of the DV?Hop localization algorithm is big due to the sensing node′s random distribution existing in the wireless sensor network. Therefore the hop count and hop distance modification method is used to improve the DV?Hop localization algorithm. The node communication distance is introduced in the process of calculating the hop count of the beacon node and unknown node to make the actual hop count between the nodes more accurate. The linear search algorithm is used to obtain the average hop distance of the optimal beacon node to make the average hop distance of the beacon node more accurate. The comparative simulation results show that the algorithm has improved the positional accuracy greatly， and its accuracy is increased by 15%.

Keywords： DV?Hop algorithm； wireless sensor network； hop count； average hop distance； positional accuracy

0 引 言

无线传感器网络（WSN）是由大量节点形成的一种具有无线自组织能力的动态网络[1?2]。如何获取无线传感节点的位置信息是实现无线传感网络监控、跟踪和目标识别等应用的难点。节点位置信息可以在网络中进行规划，动态的节点大多采用定位模块获取[3?4]。但上述方法会严重消耗节点有限的能量，降低整体网络寿命。因此，通常在部分节点中安装定位模块并将它们视为信标节点，其他未知节点根据相应的节点定位算法来估计其位置[5?7]。DV?Hop（Distance Vector?Hop）算法是一种距离无关算法，但存在定位误差大的问题，文献[8]提出使用RSSI（Received Signal Strength Indicator）技术对节点间的跳数进行优化，但引入了RSSI测量模块，复杂度过高，不利于无线传感网广泛部署；文献[9]分析了无线传感器网络中DV?Hop算法存在的缺陷，并利用量化模型表示误差，最后利用加权修正节点位置。然而这些改进算法依然存在算法复杂度较高，不利于资源受限的节点部署。本文通过对DV?Hop算法同时进行跳数和平均跳距的修正，之后对信标节点利用线性搜索算法获得准确的最佳平均跳距。实验结果表明，本文改进算法在定位精度和性能上都有了较大的提高。

1 距离向量跳段算法及误差分析

1.1 DV?Hop 定位算法

DV?Hop定位算法首先由节点的通信半径获得节点间的跳数；然后每个节点记录其毗邻的信标节点的平均跳距；最后每个节点根据以上信息分布式地计算各自的位置信息。DV?Hop定位算法过程主要有以下三步：

Step1： 利用网络的拓扑结构在网络中广播一条距离矢量消息。这样网络中任意两个信标节点之间的最小跳数（节点间的平均跳数）就能够被记录下来，简略地估计了节点之间的空间关系。

Step2： 计算节点平均跳距。由于信标节点的坐标已知，利用信标节点之间的跳数和距离计算信标节点的平均跳距。该平均跳距通过广播协议在网络中传播，以使每个未知节点都能够近似地估计其与其他节点之间的距离[10]。设信标节点[i]和[j]的坐标分别为[（xi，yi）]和[（xj，yj），]之间的最小跳数为[hj。]信标节点[i]的平均跳距公式表示为：

[HopSizei=j≠i（xi-xj）2+（yi-yj）2j≠ihj] （1）

在平均跳距的传播过程中，为使得未知节点所存储的跳距信息来自距离其最近的信标节点[i，]各未知节点仅存储初次收到的平均跳距。由于是广播方式传输平均跳距信息，距未知节点远的平均跳距信息必定延迟于较近的。因此，未知节点所存储的平均跳距信息必定来自其毗邻的信标节点。此时，未知节点[u]到任意信标节点[j]的距离可以通过下式获得：

[duj=HopSizei*hj] （2）

Step3： 估计未知节点坐标。采用各信标节点提供的跳数和平均跳距信息估计未知节点的位置。最为常用的估计方法为极大似然法[11]。该算法的计算过程如下：假设未知节点处于[（xu，yu），]根据估计距离可得如下的系统方程：

[（x1-xu）2-（y1-yu）2=d2u1（x2-xu）2-（y2-yu）2=d2u2…（xn-xu）2-（yn-yu）2=d2un] （3）

通过式（3），利用最小二乘法可以获得未知节点的位置信息，实现定位。

1.2 误差分析

通过对DV?Hop算法的原理分析可知，该算法的定位精度受很多因素的影响。

首先，该方法假定节点间的通信距离均为1跳，如图1所示。未知节点1，2到信标节点A的跳数都是1跳，实际上它们到信标节点的实际距离相差很大，这就不能较好地反应出节点之间的实际距离关系。由此获取的最小跳数信息对实际平均跳距产生误差，最终会对未知节点的定位精度产生影响。

其次，该算法中平均跳距信息的来源过于单一。由于无线传感器网络中节点的分布是随机、不均匀的，原始算法中使用的毗邻未知节点的信标节点不能表征节点分布的随机性和不均匀性。因此，本文首先对未知节点间的跳数信息进行修正，使之更接近实际跳数值；再对信标节点进行重新定位，并运用线性搜索算法对信标节点的平均跳距进行修正，获得信标节点的最佳平均跳距。

2 算法的改进

2.1 修正信标节点之间的跳数

DV?Hop 定位算法在计算两个节点之间的跳数时，并未考虑每跳的通信距离[9]，如图2所示。

假设所有节点的通信距离为信标节点3和4之间的距离。信标节点1和4之间由于节点分布的不均匀性，其每条距离与通信距离相差较大。其中，第1跳远小于通信距离。DV?Hop算法定位时仍将两信标节点之间的最小跳数记为3跳，并据此进行位置估计，其估计结果受到每条距离不同的影响，偏差较大。

本文使用通信距离信息对跳数信息进行修正。记信标节点之间的理想跳数为[Hij=dijR，]其为信标节点之间实际距离与节点的通信距离之比。引入偏离因子对跳数进行修正，其表达式为：

[lij=hij-Hijhij] （4）

式中：[lij]越小，表示信标节点[i]和[j]之间的实际跳数越接近于理想跳数；跳数修正系数表示为[θij=1-lnij，][n]取正整数。

在DV?Hop算法中，由于在根据跳数和平均跳距信息计算未知节点的位置时，所得结果均存在约为0.5倍通信距离的误差。因此，在基于通信距离进行跳数修正时，要考虑0.5倍的通信距离误差，最终修正的信标节点之间的跳数计算公式为：

[h′ij=θij*hij-0.5] （5）

通过实验结果表明，修正系数在[n=2]时定位误差最小。

2.2 修正未知节点与信标节点间的跳数

（1） 未知节点[u]距其最近信标节点[i]的跳数：

[h′ui=huin-1i≠jnθij-0.5] （6）

式中：[n]为信标节点总数，[qij]为上一节设计的修正系数；[hui]为由式（2）估计的未知节点的跳数信息。此外，考虑了通信距离对跳数信息估计的影响，引入了0.5倍通信距离的修正系数。

（2） 未知节点[u]到信标节点[j]的跳数：

[h′uj=θij*huj-0.5] （7）

式中：[θij]为上一节设计的修正系数；[huj]为DV?Hop算法中使用的实际跳数。

在式（7）中引入0.5倍通信距離来改进跳数估计。由式（6）和式（7）可以看出，用偏离因子和0.5倍的通信距离来修正跳数，能够充分利用所有信标节点的跳数信息和节点通信能力，更能反映整个网络的节点分布情况。

2.3 修正信标节点的平均跳距

为了使信标节点的平均跳距计算的更加精确，把所有的信标节点当作未知节点进行重新定位。信标节点[i]的平均每跳跳距（AHS）定义如下：

[AHSi=i≠jnHopsizein-1] （8）

式中：[n]为信标节点总数；[Hopsizei]为原始DV?Hop算法Step2中计算的到各个信标节点的平均每跳距离；信标节点[i]和[j]之间的估计距离[dij=AHS*h′ij，]其中[h′ij]是信标节点[i]和[j]之间修正后的跳数。

最后用最大似然法计算出信标节点[i]的估计位置。设信标节点[i]的位置为[（xi，yi），]利用改进算法得未知节点坐标为[（xi，yi），]信标节点[i]的定位误差为：

[ei=（xi-xi）2+（yi-yi）2] （9）

所有信标节点的平均定位误差为：

[ea=i=1nein] （10）

利用线性搜索算法对信标节点的平均跳距进行修正，获取信标节点的最佳平均跳距修正量，如图3所示。

在最低点时所有信标节点的平均定位误差最小，此时的ΔAHS就是最佳跳距修正量。信标节点[i]的最佳平均每跳距离为：

式中：ΔAHSoptimum为最佳的跳距修正量。

采用式（2）计算出未知节点与信标节点之间的位置关系，联立求解方程（3）即可得出未知节点的位置。

3 改进算法仿真结果及分析

为了检验改进算法的性能，本文对改进算法、文献[10]的改进算法和原始DV?Hop算法进行实验比较。考察的区域为100 m的正方形区域，无线传感节点均匀分布。记无线传感网中未知节点数为[N，]信标节点数为[n，]每个节点通信距离均为[R。]每次结果统计在相同节点分布下进行[K=100]次获得。为对比三种算法的性能，分别从信标节点个数、总节点个数和通信半径这三个方面对归一化后的定位误差影响进行仿真。图4给出了[N=100，][R=20，][n]依次从10增加到50时，平均定位误差同信标节点数之间的变化曲线。

从图4中可以看出，本文改进算法与对比算法的平均定位误差均随着信标节点个数的增加而减少，这是由于较多的信标节点使得跳数和平均跳距计算更加准确。而本文改进算法对定位误差的减少更加明显。相比于原始DV?Hop算法和文献[10]中的方法，本文方法分别能减少约12%～15%和2%～3%左右。

假设信标节点数目站总节点数目固定为[15，][R=]20，图5给出了[n]从100增加到200三种算法的估计误差率。

从图5中得出：随着总节点数量的不断增大，平均定位误差会逐渐减小，这是由于总节点数目增多，通信距离在跳数和平均估计中的影响减小。但本文改进算法相比于原始DV?Hop算法和文献[10]的改进方案额外分别获得了约14%～18%和2.5%的估计精度。图6则考察了通信距离对估计精度的影响。仿真条件为[N=100，][n=20。]

从图6中可以看出：三种归一化算法的定位误差均随着通信距离[R]的增大而减少。而本文的算法在进行跳数和平均跳距的估计时，采用0.5倍通信距离进行修正。改进算法的定位性能相比于文献[10]中的方法有了明显的提升，提升比例约为4%左右。

4 结 语

本文通过对跳数和平均跳距进行修正来减小定位误差。针对通信范围内节点间的跳数为1跳并且都是整数的现象，提出基于通信半径并综合考虑0.5倍的通信距离误差来对跳数进行修正，使得节点间的跳数估计更加准确。对于信标节点，提出了把信标节点当作未知节点进行重新定位并且运用线性搜索算法查找信标节点的最佳平均跳距修正量，使信标节点的总平均跳距误差最小。通过对比仿真实验，结果表明提出的改进算法定位精度得到了明显提升，相比于原始DV?Hop算法精度提升高达15%。

参考文献

[1] 陈辉，熊辉，殷昌盛，等.基于无线传感器网络时钟同步的定位算法研究[J].现代电子技术，2015，38（7）：23?27.

[2] 李云飞，江明，娄柯，等.无线传感器网络中DV?Hop定位算法的改进[J].计算机工程与应用，2014，50（3）：79?81.

[3] 王景珲.一种基于DV?Hop的无线传感器网络节点定位算法[J].计算机工程，2015，41（1）：82?86.

[4] ZHANG Y， XIANG S， FU W， et al. Improved normalized collinearity DV?Hop algorithm for node localization in wireless sensor network [J]. International journal of distributed sensor networks， 2014（11）： 1?14.

[5] 程超，钱志鸿，付彩欣，等.一种基于误差距离加权与跳段算法選择的遗传优化DV?Hop定位算法[J].电子与信息学报，2015，37（10）：2418?2423.

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

[7] 赵雁航，钱志鸿，尚小航，等.基于跳距修正粒子群优化的WSN定位算法[J].通信学报，2013，34（9）：105?114.

[8] 温江涛，范学敏，吴希军.基于RSSI跳数修正的DV?Hop改进算法[J].传感技术学报，2014，27（1）：113?117.

[9] 肖丽萍，刘晓红.一种基于跳数修正的DV?Hop定位算法[J].传感技术学报，2012，25（12）：1726?1730.

[10] 夏少波，邹建梅，朱晓丽，等.无线传感器网络DV?Hop定位算法的改进[J].计算机应用，2015， 35（2）：340?344.

[11] 李长庚，刘孟思，孙克辉.基于加权最小平方法的DV?Hop改进算法[J].微电子学与计算机，2016（1）：24?27.

[12] 赵吉，傅毅，王瀚波.改进的DV?Hop无线传感器网络定位算法[J].仪表技术与传感器，2013（6）：111?114.