基于信标节点密度的DV-Hop改进算法

黄文永，王亚民，卢源远，解 忧

(西安科技大学 理学院，陕西 西安 710054)

0 引 言

按是否测距，WSN的定位可分为两种：与距离有关和无关。虽然基于测距的定位算法能达到相当高的定位精度，但其对节点硬件要求高、成本大、功耗多。相比之下，无需测距的定位要求不高，节点条件简易，能耗少，因此更具实用性。DV-Hop算法为比较典型的无需测距算法[1-3]。

DV-Hop算法也存在定位误差大的问题。针对于此，文献[4]提出基于RSSI的DV-Hop改进算法，在对第1跳细级划分基础上，以距离比权值对跳数进行修正；文献[5]采用共线度低的信标节点作参考，以可信度加权计算未知节点平均跳距与定位误差，并把低误差点化为信标节点从而增加信标节点数；文献[6]基于误差距离权重对信标节点平均每跳距离进行处理，利用改进遗传算法对未知节点坐标进行优化；文献[7,8]采用多通信半径对跳数细化或校正坐标来提高定位精度；文献[9]提出利用偏离度小的优良信标节点对未知节点进行定位，并对定位的坐标再次修正；文献[10]先利用RSSI测距定位技术选取误差比较小的数据组，再为DV-Hop构建最小二乘法。以上改进对DV-Hop定位精度都有所提高，但也存在硬件要求高或计算复杂等不足。本文将以信标节点密度为基础，提出一种有效简易的DV-Hop改进算法，在对信标节点密度三维图形化的基础上，修正补偿信标节点的平均每跳距离，重新定位未知节点坐标。该改进算法不仅有效提高定位精度，还能减少网络节点计算复杂度及计算过程中的高能损耗。

1 DV-Hop算法与误差分析

1.1 DV-Hop算法

DV-Hop算法是由美国Dragos Niculescu等提出的一种无需测距定位技术[11]。其步骤为：

(1)信标节点以距离矢量交换协议转发各自的位置和最小跳数信息。

(2)信标节点通过接受到的其它信标节点位置与跳数,计算其平均每跳距离,并广播到网络的未知节点中

(1)

式中：(xi，yi)、(xj，yj)——信标节点i，j的位置坐标。hij——其最小跳数。未知节点对接受到的平均每跳距离与其到信标节点的最小跳数进行运算，得出其与各信标节点的距离

diq=hopi×hiq

(2)

其中，hopi表示最近信标节点的平均每跳距离，hiq代表该未知节点与信标节点的最小跳数。

(3)通过极大似然估计或三边定位估算求出未知节点的坐标。

1.2 误差分析

对DV-Hop算法进行分析，可以看出误差的产生存在多方面的因素。例如，信标节点A，B之间的通信路径为A-a-c-d-b-B，如图1所示。信标节点的平均每跳距离采用该信标节点到其它信标节点的总距离与总跳数之比，由此求出的平均每跳距离总是小于实际的平均每跳距离，使得信标节点的平均每跳误差很大。用该误差大的平均每跳距离定位随机不均匀的未知节点，使误差不断积累，从而导致未知节点的定位精度变得更低。本文提出一种基于信标节点密度来修正定位误差的方法。由于节点随机分布性，采用通信半径作为衡量尺度。理想情况下A-B之间的平均每跳距离应为R，若hopi偏离R越大，即使各节点在A-B之间的直线上，也会因在定位中没有衡量尺度及各节点间距不同等原因，而使对未知节点定位产生较大的误差。

图1 节点随机分布

2 算法的改进思想

本文的改进算法分为两个部分。第一部分是对信标节点的平均每跳距离进行修正补偿，然后对求出的未知节点坐标进行重新定位。结果表明本文采用的算法不仅有效提高未知节点的定位精度而且定位方法简易，能够减少传感器节点复杂运算带来的功耗损失。

2.1 信标节点密度定义

通过节点的平均每跳距离偏离通信半径的大小定义为该信标节点的节点密度，其公式为

ρi=(R-hopi)/R

(3)

从式(3)可以看出，hopi越小，说明该信标节点与各信标节点之间在通信路径附近的节点数越多，其节点密度越大。为形象地表示信标节点的定义，把信标节点密度化为空间坐标的z轴，而平面区域仍为x，y坐标，如图2所示。

图2 信标节点密度三维化

在使用信标节点密度下，可以把整个区域信标节点密度分布化为空间曲面，各节点间距因信标节点密度不同扩展为间距相差不大的起伏面。其中信标节点所在山峰的高度由信标节点密度决定，即信标节点的节点密度越大，说明信标节点附近的节点越密集，而越密集区域，其对应第三维上的高度越高。

2.2 信标节点平均跳距补偿

为使信标节点的平均每跳距离更接近于理想的跳距R，本文采用节点密度ρ作为信标节点平均每跳距离的修正因子，其含义为节点原平均每跳距离越小，其节点密度越大，则需要修正的量越大，反之越小。由于信标节点的平均每跳总比通信半径小，所以补偿方法应使信标节点在其原有的长度上增加修正量。即信标节点的补偿公式为

(4)

经补偿后的信标节点平均每跳距离为

Chopi=hopi×ci

(5)

其中，hopi为第i个信标节点的平均每跳距离，ci为其补偿因子。ρ对平均每跳距离的直接修正并不明显，因此对k的取值进行实验，当k=2时，对信标节点的平均每跳距离修正最优，具体参数请参考实验仿真与分析中的图7。最终修正的信标节点的平均每跳距离为

(6)

2.3 未知节点坐标重新定位

导致未知节点定位误差大的原因有很多，如果仅对信标节点的平均每跳距离进行补偿，则对未知节点的定位精度起不到太大作用，因此要对求出的未知节点的坐标进行重新定位。

利用信标节点密度，对未知节点的坐标修正的方法为：以最近的信标节点A’为中心，压缩A’与a’之间的距离，其曲面图如图2所示。用修正后的最近信标节点的平均每跳距离求出的未知节点位置的扩展性如图2中的a’，而未知节点a的实际坐标应是a’投影平面区域的a，对应图2中的a。在对未知节点的坐标修正过程中，认为压缩A(A’)与a’之间距离到1-ρ倍时约等于A与a之间的平面距离，其坐标如图3所示。在以A为中心对A-a’之间进行压缩中，设A的坐标为(xi，yi)，a’为经过最小二乘法求出的坐标(xa’,ya’)，a的坐标为(xa,ya)。假设A为坐标原点，则a’到A之间在x方向上的距离为

(7)

图3 压缩A-a’坐标

压缩后的长度为原长度的1-ρ倍，则压缩后的长度为

(8)

其中，ρi为信标节点i的节点密度。以信标节点A为中心(原点)，所求a在x方向上的修正坐标为

(9)

同理可求得a’到A之间在y方向上的距离为

(10)

压缩1-ρ倍后的长度为

(11)

a在y方向的修正坐标为

(12)

3 实验仿真与分析

本文采用MATLAB仿真平台对所提出的改进算法进行实验，并与原DV-Hop算法对比。实验中，在100×100的区域内随机产生节点坐标。在运算中采用的相对误差为

(13)

其中，N为未知节点的数量，Uje为经修正后未知节点j的坐标，Uj0为其实际坐标，R为通信半径。并且每个实验数据点都进行100次实验运算，求取平均值。实验结果表明，本文提出的改进算法能有效提高对未知节点的定位精度。

图4为节点总数对相对误差的影响。设置信标节点数为20，分别对节点总数为100，125，150，175，200，225，250，275及300进行实验。

图4 节点总数对相对误差的影响

图4(a)为通信半径R=25 m时的实验结果。可以看出，当节点数超过175时，节点的增加对提高定位精度作用不大，改进算法基本维持在0.25-0.26的定位误差，总体定位精度优化6%-7%。而当通信半径为50 m时，实验结果如图4(b)所示，改进算法比原DV-Hop算法的优化8%-9%。

图5为通信半径对相对误差的影响。实验中，节点数量为100，信标节点数为20，对通信半径为20,25,30,35,40,45,50,55分别进行仿真。

图5 通信半径对相对误差的影响

由图5可以看出，本文提出的改进算法，定位精度随着通信半径的增大而提高。在通信半径为55时，原DV-Hop算法的定位误差为27%左右，而经本文对算法改进后，定位误差下降到19%左右。从总体上来看，改进算法比原DV-Hop算法优化6%-8%。

图6为信标节点数对相对误差的影响。实验中，设置节点总数为100，在通信半径为R=25m和R=50m时，分别对信标数为15，20，25，30，35，40，45，50进行仿真，实验结果如图6所示。

图6 信标节点数对相对误差的影响

从图6(a)中可以看出，当通信半径R=25m时，在信标节点大于30时，原DV-Hop算法定位误差在33%-32%，改进的算法的定位误差在26%-24%，总体上改进算法比原DV-Hop算法优化6%-8%左右。而当通信半径R=50 m时，实验结果如图6(b)所示，改进算法比原DV-Hop算法优化8%-10%。说明通信半径的增大，改进算法的优化程度越好。

图7为ρ的次方k值的实验仿真，从图中可以看出，当k为2时，对信标节点的平均每跳距离修正起到最佳的效果，从而验证了在2.2中补偿因子中ρ的次方的合理性。

图7 k值对相对误差的影响

4 结束语

本文提出一种基于信标节点密度的DV-Hop改进算法，该算法以通信半径为衡量尺度，对信标节点平均每跳距离进行补偿，同时利用最近的信标节点坐标及其节点密度对未知节点的坐标进行重新定位。实验结果表明，与原DV-Hop算法相比，改进的算法在定位精度上有6%-10%的提高。在修正及重新定位的过程中，对信标节点密度三维图形化，不但直观明了，且改进方法简易。此外，该算法还能减少网络节点计算复杂度及计算过程中的高能损耗。

参考文献：

[1]FU Caixin.WCGDV-Hop localization algorithm for wireless sensor networks[D].Changchun:Jilin University,2014(in Chinese).[付彩欣.WCGDV-Hop无线传感器网络定位算法研究[D].长春:吉林大学,2014.]

[2]Gopakumar A,Jacob L.Power-aware range-free wireless sensor network localization using neighbor distance distribution[J].Wireless Communications & Mobile Computing,2013,13(5):460-482.

[3]Gui L,Val T,Wei A,et al.Improvement of range-free loca-lization technology by a novel DV-Hop protocol in wireless sensor networks[J].Ad Hoc Networks,2015,24:55-73.

[4]WEN Jiangtao,FAN Xuemin,WU Xijun.Improved DV-Hop location algorithm based on hop correction[J].Chinese Journal of Sensors and Actuators,2014,27(1):113-117(in Chinese).[温江涛,范学敏,吴希军.基于RSSI跳数修正的DV-Hop改进算法[J].传感技术学报,2014,27(1):113-117.]

[5]WANG Jinghui.A node location algorithm in wireless sensor network based on DV-Hop[J].Computer Engineering,2015,41(1):82-86(in Chinese).[王景珲.一种基于DV-Hop的无线传感器网络节点定位算法[J].计算机工程,2015,41(1):82-86.]

[6]CHENG Chao,QIAN Zhihong,FU Caixin,et al.Genetic optimization DV-Hop localization algorithm based on error distance weighted and hop algorithm selection[J].Journal of Electronics & Information Technology,2015,37(10):2418-2423(in Chinese).[程超,钱志鸿,付彩欣,等.一种基于误差距离加权与跳段算法选择的遗传优化DV-Hop定位算法[J].电子与信息学报,2015,37(10):2418-2423.]

[7]LIU Shixing,HUANG Junjie,LIU Hongyin,et al.An improving DV-Hop algorithm based on multi communication radius[J].Chinese Journal of Sensors and Actuators,2015,28(6):883-887(in Chinese).[刘士兴,黄俊杰,刘宏银,等.基于多通信半径的加权DV-Hop定位算法[J].传感技术学报,2015,28(6):883-887.]

[8]MA Shuli,ZHAO Jianping.Multi communication ranges DV-Hop localization algorithm for wireless sensor network[J].Chinese Journal of Sensors and Actuators,2016,29(4):593-600(in Chinese).[马淑丽,赵建平.多通信半径的无线传感器网络DV-Hop定位算法[J].传感技术学报,2016,29(4):593-600.]

[9]LIU Yuzhen,WANG Zhaofeng.Wireless sensor network localization algorithm based on DV-HOP improvement[J].Compu-ter Engineering and Applications,2016,52(4):79-83(in Chinese).[刘玉珍,王兆锋.基于DV-HOP改进的无线传感器网络定位算法[J].计算机工程与应用,2016,52(4):79-83.]

[10]JIN Chun,YE Cheng,HAN Zhibin,et al.Dv-Hop localization algorithm improvements in wireless sensor networks[J].Computer Engineering and Design,2013,34(2):401-404(in Chinese).[金纯,叶诚,韩志斌,等.无线传感器网络中Dv-Hop定位算法的改进[J].计算机工程与设计,2013,34(2):401-404.]

[11]SHANG Xiaohang.Research on wireless sensor networks localization algorithm based on DV-Hop[D].Changchun:Jilin University,2012(in Chinese).[尚小航.基于DV-Hop的无线传感器网络定位算法研究[D].长春:吉林大学,2012.]