基于距离虚拟补偿的DV-Hop定位算法

党宏社， 刘 勇， 苌 瑶， 黄梓岳

(陕西科技大学 电气与信息工程学院， 陕西 西安 710021)



基于距离虚拟补偿的DV-Hop定位算法

党宏社， 刘 勇， 苌 瑶， 黄梓岳

(陕西科技大学 电气与信息工程学院， 陕西 西安 710021)

针对DV-Hop(Distance Vector-Hop)定位算法中的未知节点到信标节点的距离计算存在较大的误差，从而降低了未知节点的定位精度这一问题，提出了基于距离虚拟补偿的DV-Hop定位算法.该算法从两个方面进行改进,首先根据跳数对信标节点之间的距离进行虚拟补偿；然后对与未知节点距离相等的多个信标节点求平均距离，从而使得未知节点到信标节点的距离更加接近实际距离.通过与传统算法和改进算法的性能进行仿真对比，结果表明改进的算法有效的提高了未知节点的定位精度.

无线传感器网络； DV-Hop定位算法； 距离虚拟补偿； 均值处理，定位精度

0 引言

无线传感器网络定位是无线传感器网络应用的一个重要前提条件，只有知道数据采集节点采集到的数据的具体位置，采集到的数据才有意义[1].所以如何准确获得每一个数据采集节点所在区域的具体位置，成为了国内外研究人员关注的重点[2,3].现今的定位算法按定位机制来分可以将定位算法分为基于测距的定位算法和无需测距的定位算法.基于测距的定位算法的定位精度比基于非测距的定位算法的定位精度高，但是前者对网络的硬件设施要求较高，而后者只需知道网络的连通性等信息就可以实现对未知节点的定位.这种优势使得无需测距定位算法受到了国内外研究人员的广泛关注.

无需测距的定位算法包括质心算法[4,5]，DV-Hop算法[6]，APIT算法[7]等.其中DV-Hop算法简单、容易实现并且具有较好的扩展性等优势，使其成为当今使用最广的一种非测距定位算法.文献[8-12]分别对DV-Hop算法进行了不同程度的改进，但是定位效果仍然不是很理想，因此本文提出了距离虚拟补偿的定位算法.

1 DV-Hop定位算法

1.1 DV-Hop算法的描述

DV-Hop定位算法首先是由美国路特格斯大学的Niculescu D.等[8]提出.该算法主要分为三个阶段.

(1)第1阶段

信标节点利用泛洪的方式向整个网络发送一个包含自身ID、坐标和跳数信息的一个数据包.当未知节点是第一次接收到该数据包时，它将会保存该数据包并将该数据包的跳数值加1广播到邻居节点；如果不是第一接收该类型的数据包时，那么它会将新收到的数据包的跳数值与先前接收的数据包的跳数值进行比较，如果新接收到数据包的跳数值小于原先保存的数据包中的跳数值，那么它会保存新接收到的数据包并将该数据包的跳数值加1广播到邻居节点，否则丢弃新接收到的数据包.通过这一机制所有的未知节点获得距离信标节点最小跳数信息.

(2)第2阶段

每个信标节点在获得其它信标节点的位置以及之间的最小跳数信息后，根据式(1)计算出信标节点i的平均跳距HopSizei：

(1)

式(1)中：(xi,yi)与(xj,yj)分别表示的是信标节点i与j的坐标；Hopij是信标节点i与j之间的最小跳数.

在计算出跳距后，每个信标节点通过泛洪的方式向网络广播平均跳距，当未知节点接收到平均跳距信息时，其只保存第一次接收到的平均跳距，并将其广播到邻居节点.通过这种方法，大部分的未知节点收到来自信标节点的平均跳距.当未知节点收到了信标节点的平均跳距，就可以通过式(2)计算出该未知节点u与信标节点i之间的距离：

dui=HopSizei×hopui

(2)

(3)第3阶段

利用最小二乘法对未知节点的坐标进行估算.假设(x,y)为未知节点u的坐标，(xi,yi)为第i个信标节点的坐标，未知节点与信标节点的距离分别为d1,d2,…,dn，则有：

(3)

通过下面的公式即可计算出未知节点u的坐标：

(4)

(5)

(6)

则有P=(ATA)-1ATB.

1.2DV-Hop误差分析

在实际应用中，考虑到成本和能耗的问题，不可能在某一监测区域部署大量的信标节点.另外，节点通常是以飞机投放的方式将节点撒在监控区域内，所以节点的位置分布并不均匀.在这种情况下，利用少数的信标节点来估算大量未知节点的位置，势必会产生较大的误差.图1为传感器网络的拓扑结构图.下面对DV-Hop算法在计算平均跳距时所产生的误差进行具体分析.

在图1中，A,B,C为信标节点，u0,u1,…,u5为未知节点.①对于信标节点A与B而言，由于它们之间的跳数较多，使得计算出来的平均跳距小于未知节点到信标节点每跳的距离，因此计算出来的估计距离小于未知节点到信标节点的欧式距离；②对于未知节点u4而言，其与信标节点B和C的跳数一样，如果只选择其中的一个信标节点的平均跳距来计算，那将无法反映实际情况，所以也会产生误差.

图1 传感器网络拓扑结构图

2 改进的DV-Hop算法

2.1 已有的改进算法

针对传统的DV-Hop定位算法在随机分布的网络环境下定位误差较大这一问题，国内外一些专家和学者对此进行了大量的改进研究.文献[9]通过最小均方差获得平均每跳距离，然后利用未知节点到信标节点的最小跳数与该未知节点到所有的信标节点跳数之和的比值作为加权，最后使用粒子群优化算法来纠正双曲线定位算法来计算未知节点的位置.文献[10]采用曲线拟合的最小二乘法求解未知节点的坐标，并对未知节点的坐标进行优化处理.文献[11]首先借助信标节点之间的估计距离与实际距离的偏差来修正平均每跳距离，然后利用二维双曲线定位算法代替三边测量定位算法来估计未知节点的位置.文献[12]通过引入信号强度对每跳进行分级来修正节点间的跳数，接着利用最小均方差准则来获得信标节点距离估计误差最小的平均跳距.文献[13]首先对信标节点的跳数进行修正，其次对未知节点到信标节点间的跳数进行修正，修正后的跳数都不再是整数.上述的几种改进算法虽然在不同程度上都提高了对未知节点的定位精度，但也有考虑不周全、定位精度的提高不明显、可操作性不强等一系列问题.

2.2 本文改进的DV-Hop算法

传统的DV-Hop定位算法在统计两信标节点间的跳数时,当信标节点之间的距离在通信半径范围内，信标节点之间跳数为1，然而当信标节点之间的距离大于通信半径时，这时借助未知节点来获得信标节点之间的最小跳数，这就会出现图2信标节点A和B的情况:信标节点之间的距离不是很长，但跳数较多，使得信标节点计算出来的平均跳距小于未知节点与信标节点实际每跳的距离.针对这一问题，很多改进的DV-Hop算法都是通过减少跳数来增加平均每跳跳距，那么也可从另外一个角度来解决这个问题，即通过虚拟补偿信标节点间的距离.因为节点部署完成后，任意两信标节点之间的距离也就确定了，本文只是在计算的时候对其进行补偿，所以称之为距离虚拟补偿.

2.2.1 信标节点间的距离补偿

针对误差分析中的情况①，根据信标节点之间的跳数，提出了式(7)的距离补偿公式：

(7)

式(7)中：dcij表示的信标节点i与j补偿距离；Hopij表示的信标节点i与信标节点j之间的跳数；R表示的是通信半径；dij表示的是信标i与j之间实际距离；dij/R表示两信标节点i与j之间理想跳数，那么(R/dij)dij表示的是理想状态下的每跳的实际距离；(R/dij)ndij中的n是用来寻找每跳补偿距离的最优值；将(R/dij)ndij值乘以Hopij作为信标i与j节点之间的补偿距离.

2.2.2 调整未知节点到信标之间的距离

针对误差分析中的情况②，假设未知节点u到信标节点i1,i2,…,ik之间平均跳距分别为dui1,dui2,…,duik且跳数分别为Hopui1,Hopui2,…,Hopuik，则未知节点到信标节点的距离为：

(8)

3 实验仿真和结果分析

为了验证改进算法，本文首先对n和R取不同值时的性能进行了仿真,并对传统的DV-Hop算法、文献[13]和本文改进的算法进行了仿真对比.仿真环境设置：选用的是MATLAB7.12作为仿真测试平台.测试区域为100 m×100 m，为了获得更加客观准确的测试数据，对所有的数据都采集100次求平均值，假设所有节点的通信半径都相同.主要测试的是信标节点比例、节点个数等参数对定位误差的影响.

在无线传感器网络中，平均定位误差er为网络中所有未知节点的估计值和实际值的差值的平均值[14]：

(9)

式(9)中：(x,y)和(xi,yi)分别为未知节点的估计位置和实际位置；k表示仿真次数；un表示未知节点的个数.

归一化定位误差为平均定位误差er与通信半径R的比值[15]：

(10)

图2给出的是信标节点比例为10%，不同通信半径下，n取值从1～5的仿真图.从图2可以看出，当n的取值在1到3这个区间段时，未知节点的平均定位误差降低的幅度最大，随着n的逐渐增大平均定位误差变得越来越平稳，尤其当n的取值为4到5这一区段时，平均定位误差基本上没有变化，这说明当n取值达到某一值时定位误差基本上就处于一个稳定阶段.对于n取值在3到5这一区段，半径大的平均定位误差要比半径小的平均定位误差大.这是因为R值增大使得dij/R值变小，进而使得(dij/R)n值更小，这就使得距离补偿小于其实际需要的补偿距离，从而使得平均定位误差增大.为了在获得较好的定位精度的同时不让运算开销增加的特别大，将n取值为4.

图2 n和R取不同值的平均定位误差关系图

图3给出的是节点总数为100，通信半径为50 m，n取值为4的情况下节点归一化平均定位误差与信标节点比例仿真图.从图3可以看出，3种定位算法的归一化平均定位误差随着信标节点比例的增加而逐渐减小，当信标节点的比例增加到一定的程度，归一化定位误差逐渐趋于稳定.本文改进算法的归一化定位误差比传统的DV-Hop算法降低了约18%～25%，较文献[13]降低了7%～10%.

图3 信标节点比例与归一化定位误差关系图

图4给出了信标节点比例为10%，通信半径为50 m，n取值为4的情况下节点归一化平均定点定位误差与节点总数的仿真图.从图4可以看出，随着总节点数目增加，3条曲线都逐渐下降，并趋向稳定.这是因为在区域环境一定的情况下随着节点数据增加相当于网络中的节点密度增加，从而使得定位误差减小.本文改进算法的归一定位误差比传统的DV-Hop算法降低了约25%～35%，较文献[13]降低了约8%～12%.

图4 总节点个数与归一化平均定位误差关系图

图5给出的是信标节点的比例为10%,n的取值为4时平均定位误差与节点之间的通信半径仿真图.从图5可以看出，随着通信半径的增大，平均定位误差也增大，这是因为随着通信半径的增大使得节点之间的跳数误差也随之增大，从而造成了平均跳距误差的增大，这就使得通过跳数和平均跳距的乘积来估算未知节点的位置比实际的位置相差较大，在相同的条件下，本文的算法比文献[13]中的平均定位误差都要小.

图5 通信半径与平均定位误差关系图

4 结论

针对传统的平均跳距计算出未知节点到信标节点距离存在较大的误差，提出了一种改进的DV-Hop算法,通过对信标节点间的距离进行虚拟补偿，并且对未知节点到多个信标节点之间的距离相等进行均值化处理，从而修正了累计跳段距离.经仿真对比，本文改进算法较传统的DV-Hop算法在性能指标上有较大提升.

[1] 达尔吉(德)，玻尔拉伯尔(美).无线传感器网络基础理论与实践[M].孙利民.北京：清华大学出版社，2014．

[2] 夏少波,邹建梅,朱晓丽,等.无线传感器网络DV-Hop定位算法的改进[J].计算机应用,2015,35(2):340-344.

[3] Maung N A M,Kawai M.Experimental evaluations of RSS threshold-based optimised DV-HOP localisation for wireless ad-hoc networks[J].Electronics Letters,2014,50(17):1 246-1 248.

[4] Xing T,Zhang S,Zhang F.RSSI enhanced microkernel-based LBS design[J].Journal of Geographic Information System,2013,6(2):109-114.

[5] 李文辰,张 雷,Li Wen-chen,等.无线传感器网络加权质心定位算法研究[J].计算机仿真,2013,30(2):191-194.

[6] 曹广华,张红杰.一种改进的无线传感器网络DV-Hop定位算法[J].化工自动化及仪表,2015,42(6):641-644,718.

[7] 冀常鹏,陈美玲,刘 巧.无线传感网络APIT定位算法的改进[J].仪表技术与传感器,2012(8):84-86.

[8] Niculescu D,Nath B.DV based positioning in ad hoc networks[J].Telecommunication Systems,2003,22(1):267-280.

[9] Shrawan Kumar,D K Lobiyal.An advanced DV-Hop localization algorithm for wireless sensor networks[J].Wireless Personal Communications,2013,71(2):1 365-1 368.

[10] Shrawan Kumar, D K Lobiyal.Power efficient range-free localization algorithm for wireless sensor networks[J].Wireless Networks,2014,20(4):681-694.

[11] Chen X,Zhang B.Improved DV-Hop node localization algorithm in wireless sensor networks[J].International Journal of Distributed Sensor Networks,2012(6):1 018-1 020.

[12] 张爱清,叶新荣,胡海峰,等.基于RSSI每跳分级和跳距修正的DV-HOP改进算法[J].仪器仪表学报,2012,33(11):2 552-2 559..

[13] 肖丽萍,刘晓红.一种基于跳数修正的DV-Hop定位算法[J].传感技术学报,2012,25(12):1 726-1 730.

[14] 潘琢金,刘文春,罗 振,等.无线传感器网络DV-Hop定位算法的改进[J].计算机工程与设计,2016,37(7):1 701-1 704,1 740.

[15] 邬春明,杨 涛,马冬梅,等.一种改进DV-Hop无线传感器网络定位算法[J].河南科技大学学报(自然科学版),2016,37(6):55-60.

【责任编辑：蒋亚儒】

DV-Hop localization algorithm based on distance virtual compensation

DANG Hong-she, LIU Yong, CHANG Yao, HUANG Zi-yue

(College of Electrical and Information Engineering, Shaanxi University of Science & Technology, Xi′an 710021, China)

The distance calculation between the unknown node and the beacon node has a large error,which reduces the positioning accuracy of the unknown nodes in the DV-Hop (Vector-Hop Distance) localization algorithm. Hence,DV-Hop localization algorithm based on the Distance virtual compensation is proposed.The improved algorithm from two aspects,Firstly,the distance between the beacon nodes is compensated according to the number of hops;Secondly,the average distance of multiple beacon nodes which are equal to the unknown nodes is obtaind,So that the distance from the unknown node to the beacon node is more close to the actual value.The simulation results show that the improved algorithm performs better in positioning accuracy than t that of the aditional .localiazation algorithm.

wireless sensor networks; DV-Hop localization algorithm; distance virtual compensation; mean processing; positioning accuracy

2017-01-08

陕西省科技厅社会发展科技攻关计划项目(2015SF275)

党宏社(1962-)，男，陕西武功人，教授，博士，研究方向：工业过程智能控制、数字图像处理

2096-398X(2017)03-0171-05

TP393

A