基于多通信半径的加权DV-Hop改进算法

邴晓瑛　徐保国

1(江南大学轻工过程先进控制教育部重点实验室　江苏 无锡 214122)2(江南大学物联网工程学院　江苏 无锡 214122)



基于多通信半径的加权DV-Hop改进算法

邴晓瑛1徐保国2

1(江南大学轻工过程先进控制教育部重点实验室江苏 无锡 214122)2(江南大学物联网工程学院江苏 无锡 214122)

摘要针对网络拓扑结构不规则的无线传感器网络中经典DV-Hop定位算法计算未知节点位置存在较大误差的问题，提出一种基于多通信半径修正跳数，加权修正未知节点平均跳距的改进算法。首先对通信半径进行分级细化，利用多级通信半径修正信标节点到信邻节点的跳数信息。再根据信标节点与未知节点的距离，对能与未知节点通信的每个信标节点进行平均跳距加权处理，并将每个加权后的平均跳距参与未知节点平均跳距的计算，使未知节点的平均跳距更符合实际网络情况。仿真结果表明，在相同的网络拓扑结构下，改进的定位算法有效提高了传感器节点的定位精度。

关键词DV-Hop定位多通信半径加权平均跳距定位精度

0引言

无线传感器网络WSN(Wireless Sensor Network)现已在国防军事、智能交通、环境监控等很多领域，都得到了广泛的应用。而传感器节点的位置特别重要，是WSN应用的基础[1]。现阶段定位算法主要分为两类，基于测距[2]和基于非测距[3]。其中DV-Hop[4]算法、质心算法、凸规划算法等是典型的基于非测距的定位算法。Range-free定位算法硬件成本较低、能耗较小，传输的信号受外界影响较小，并且能满足大部分实际应用对定位精度要求。

美国Rutgers University的Dragos Niculescu等利用GPS和距离矢量路由思想提出了DV-Hop算法[5]。DV-Hop算法不需要直接测量距离，而是通过交换距离矢量信息和网络连通度来估算距离，导致了该算法定位精度较低。随着社会的发展的需要，对许多实际应用的定位精度要求愈来愈高。许多学者对经典的DV-Hop算法进行了深入研究并改进，文献[6] 采用双通信半径细化节点间的跳数信息，提高定位精度；文献[7] 利用RSSI修正节点间的跳数信息，使跳数值更精确；文献 [8]分别用信标节点修正未知节点平均跳距，并对未知节点估算位置迭代求精。

本文深入分析了传统DV-Hop定位算法定位误差大的原因，在不改变传统算法框架的基础上，利用多通信半径来修正传统算法第一阶段得到的未知节点与信标节点间的最小跳数，并对第二阶段中得到的平均每跳距离进行加权修正，使未知节点与信标节点间的距离更接近真实值。实验结果表明，改进的算法能有效地减小定位误差，提高定位精度。

1问题分析

1.1DV-Hop定位算法

DV-Hop算法可分为以下三个阶段[9]。

(1) 计算信标节点与未知节点间最小跳数

每个信标节点都在网络中广播含自身信息分组{ID,(x,y),hop}给邻居节点，初始化hop=0，接收节点每接收到一个分组信息，保存该信标节点的最小跳数并将hop=hop+1转发给邻居节点，若该分组来自同一信标节点，则忽略；以确保所有节点都能保存到网络中任一信标节点间的最小跳数。

(2) 估算未知节点的平均每跳距离

网络中任一信标节点的实际平均跳距：

(1)

信标节点i、j的坐标分别为(xi,yi)，(xj,yj)，i与j之间的最小跳段数为hopij。

未知节点接收并记录信标节点在网络中广播的自身平均每跳距离，且仅记录其接收到的第1个数值，继续转发该平均跳距，以保证尽可能多的未知节点记录的平均跳距是从离其最近的信标节点处获得。

(3) 计算未知节点位置

设未知节点D(x,y)能直接进行通信的信标节点为(x1,y1),(x2,y2),…,(xn,yn)，并假设步骤2中计算的D(x,y)到相应信标节点距离为d1,d2,…,dn，则:

(2)

可表示为线性方程组AL+ε=b，ε为n-1维随机误差向量，其中L=(x,y)T，则:

最小二乘法求得方程的解为:

L=(ATA)-1ATb

(3)

1.2误差分析

在经典DV-Hop定位算法中，利用到未知节点最近的信标节点的估算平均跳距与最小跳数乘积等效替代其直线距离，精确度受网络连通度影响较大[10]。经过深入分析，造成误差原因如下：

(1) 最小跳数信息

DV-Hop定位算法中，选择具有最少折点的几个跳段等效为未知节点与信标节点之间的直线段，那么该折线段中各点越接近共线，误差越小。由于网络中节点随机分布，共线概率较低，误差必然存在[11,12]。未知节点与信标节点间的跳数越多，与其相关的测量距离dn误差越大，式(3)中向量b的每个元素均包含测量距离dn，导致误差累加。

(2) 平均跳距信息

DV-Hop定位算法中，未知节点将离其最近的信标节点的平均跳距作为自身平均跳距，并以此来计算该未知节点与网络中其他信标节点间的距离[13-15]。由于实际网络拓扑结构部规则，各处平均跳距信息并不相同，上述做法必然会造成误差。信标节点平均跳距的精确度直接关系着与其相关的测量距离dn的精确性，亦会造成定位误差的累加。

针对上述DV-Hop定位误差的产生的原因，本文分别对未知节点与信标节点间的最小跳数与未知节点的平均跳距做出相应的改进研究。

2多通信半径改进跳数信息

2.1基本思想

图1　多通信半径跳数计算

在DV-Hop定位算法中，两点之间的直线距离小于通信半径，即将其记为1跳。若网络中节点分布如图1所示，设通信半径R=30 m，从图中可以看出，信标节点O可以与节点A、B、C进行通信，那么HopOA=1,HopOB=1,HopOC=1，HopOD=2，但是OA与OC的距离相差较大，OD间跳数记为2跳时，对计算信标节点O平均跳距影响比较大。在计算未知节点与信标节点最小距离时，这种计算节点间最小跳数的机制也会导致误差的产生，并在定位过程中继续累加误差。若能将信标节点到信邻节点间的跳数分级细化，必然能减小误差，提高定位精度。本文提出了一种利用多通信半径来精确信标节点与信邻节点间的跳数，减小定位误差。

2.2具体步骤

设网络通信半径为R，将信标节点与信邻节点间分为m级，网络中各信标节点与其邻居节点的实际距离为d，跳数记为H1,i∈[1,m]且为正整数，则:

(4)

具体步骤如下：

(1) 设定m,R值，首先取i=1；

(2) 若i

(4) 间隔时间t，令i=i+1，转向步骤(2)；

(5) 信标节点以通信半径R在网络中广播自身信息分组，接收节点每接收到一个分组信息，判断是否为记录的最小跳数值。若是，保存该信标节点的最小跳数并将hop=hop+1转发给邻居节点；若不是，将原来已保存的最小跳数值加1转发给邻居节点。若该分组来自同一信标节点，则忽略。

由于信标节点每次在网络中泛洪广播耗能较大，因此以小于R的通信半径向网络中广播信息分组时，接收节点不将接收到的信息分组转发，节约网络能量开销。

3加权修正平均跳距信息

3.1基本思想

设未知节点坐标为D(x,y)，能与该未知节点通信的信标节点为A1(x1,y1),A2(x2,y2),…,An(xn,yn)，这些信标节点的平均每跳距离为hopsize1,hopsize2,…,hopsizen，到D(x,y)的跳数为hop1,hop2,…,hopn,D(x,y)到信标节点Ai(xi,yi)的距离ri为：

ri=hopi×hopsize

(5)

由于hopsize是取离未知节点最近的信标节点的平均跳距作为未知节点到所有信标节点的平均跳距，但是实际网络中节点在不同区域的分布状况是不同的，平均每跳距离也是不同的，经典DV-Hop算法用单一的平均跳距不能正确反应网络状况，误差较大。由式(5)可以看出，距离未知节点较近的信标节点，节点间距离计算更精确。

3.2具体步骤

本文用下式修正未知节点平均跳距：

(6)

hopsizei=(1-ωi)×hopsizei

(7)

(8)

由式(6)可知，距离未知节点越近的信标及诶单，hopi越小，权值ωi越小，由式(7)得出的hopsizei值对原平均跳距修正得越少，在式(8)中求平均跳距时贡献的越多。

通过式(6)-式(8)的处理，每个能与未知节点通信的信标节点的平均跳距都参与计算未知节点平均跳距，每个信标节点平均跳距都根据与未知节点的距离远近进行了加权处理，使得每个未知节点根据平均跳距计算自身坐标时更接近网络的真实情况。

3.3改进DV-Hop具体实现步骤

基于多通信半径与加权修正未知节点平均跳距的改进DV-Hop定位算法流程如图2所示。

图2　改进DV-Hop算法流程图

4仿真实验及结果分析

4.1仿真环境及参数设定

本文采用MATLAB仿真软件实现传感器节点定位算法。假设所有传感器节点均匀随机分布在100 m×100 m的正方形区域内。

为了能更直观地评价PD-DV-Hop算法的性能，将其分别与传统的DV-Hop算法，PSO改进的DV-Hop算法(PSO-DV-Hop)，DE改进的DV-Hop算法(DE-DV-Hop)进行对比仿真实验，并比较分析实验数据。为确保结果的准确性，在每种测试条件下，对上述4种算法分别进行50次随机分布测试，取算术平均值。定位算法性能评价标准为归一化定位误差，其计算公式为：

(9)

其中，(xir,yir)、(xie,yie)代表第i个未知节点的实际坐标和通过定位算法得出的估计坐标，R为网络通信半径，N为未知节点总数。

4.2仿真结果分析

4.2.1多通信半径下信标节点比例对定位精度的影响

图3表示了节点总数N=100，通信半径R=30m，信标节点比例在5%～35%变化时，通信半径分级m不同时节点定位误差图。由图可知，m=1,2,3,4,5时定位误差与信标节点比例整体上成反比。在信标节点比例为5%～15%时，定位误差受信标节点比例影响较大，当信标节点比例超过15%后，定位误差变化均趋于稳定。由图可知，m=1,2,3时定位误差减小效果较明显，m=4,5时定位误差减小的较少，m=2较m=1即DV-Hop定位算法定位误差平均减小了约17%；m=3较m=2定位算法定位误差平均减小了约12%；m=4较m=3定位算法定位误差平均减小了约8%；m=5较m=4定位算法定位误差平均减小了约5%。

图3　信标节点比例不同时定位误差

4.2.2多通信半径下通信半径对定位精度的影响

图4表示了节点总数N=100，信标节点数为30，通信半径在20m～50m变化时，通信半径分级m不同时节点定位误差图。由图可知，m=1,2,3,4,5时定位误差与通信半径变化整体上成反比。这是由于通信半径越大，每个节点的邻居节点越多，网络连通度越高，节点的平均跳距和跳数信息越准确。由图可知，m=1,2,3时定位误差减小效果较明显，m=4,5时定位误差减小的较少。m=2较m=1即DV-Hop定位算法定位误差平均减小了约15%；m=3较m=2定位算法定位误差平均减小了约10%；m=4较m=3定位算法定位误差平均减小了约6%；m=5较m=4定位算法定位误差平均减小了约4%。

图4　通信半径不同时定位误差

根据图3、图4，通信半径分为m=3级时节点定位误差较经典DV-Hop减小的较明显，由于信标节点每广播一次自身信息分组，都要有一定的能量消耗。综合考虑，本文选择将通信半径分为3级，细化精确节点间的跳数信息，并与本文改进的加权平均跳距结合进行改进DV-Hop定位算法的仿真研究。

4.2.3改进DV-Hop算法中信标节点数对定位精度的影响

图5表示了节点总数为100，通信半径R=30m，信标节点比例在5%～30%变化时，改进DV-Hop算法与经典DV-Hop算法节点定位误差图。由图5可知，在通信半径一定的情况下，2种算法定位误差与信标节点比例整体上成反比。改进DV-Hop定位算法比经典DV-Hop定位算法定位误差平均减小了约20%，且改进的定位算法更稳定。

图5　改进DV-Hop信标节点比例不同时的定位误差

4.2.4改进DV-Hop算法中通信半径对定位精度的影响

图6表示了节点总数为100，信标节点数为30，通信半径在20m～50m变化时，改进DV-Hop算法与经典DV-Hop算法节点定位误差图。由图5可知，在节点总数与信标节点数一定的情况下，2种算法定位误差与通信半径整体上成反比。改进DV-Hop定位算法比经典DV-Hop定位算法定位误差平均减小了约18%，且改进的定位算法更稳定。

图6　改进DV-Hop通信半径不同时的定位误差

5结语

本文提出了一种基于多通信半径分级细化节点间跳数和加权修正未知节点平均跳距的改进DV-Hop定位算法。通过多通信半径精确节点间跳数信息，并通过加权平均跳距修正未知节点到信标节点的平均跳距，使求得的未知节点坐标更接近实际坐标，提高定位精度。仿真实验结果表明，本文改进算法在相同的网络拓扑结构下，有效地提高了传感器节点的定位精度。如何更有效地节约网络能量开销，也是未来的一个研究方向。

参考文献

[1] 张西红,周顺,陈立云.无线传感网技术及其军事应用[M].北京:国防工业出版社，2010.

[2] Yan Ling Chu, Jau Rong Tzeng, YungPin Cheng,et al.Density-Adaptive Range-free Localization in Large-Scale Sensor Networks[C]//Parallel Processing Workshops (ICPPW),2012 41st International Conference on,2012:488 - 495,1249-1250.

[3] Maung N A M,Kawai M.Experimental Evaluations of RSS threshold-based optimized DV-Hop localization for wireless ad-hoc networks [J].2014,50(17):1246-1248.

[4] Gayan S,Dias D.Improved DV-Hop algorithm through anchor poition re-estimation [C]//Wireless and Mobile,2014 IEEE Asia Pacific Conference on.2014:126-131.

[5] Niculescu D,Nath B.DV Based Positioning in Ad Hoc Networks[C]//Telecommunication Systems,2003:22(1/2/3/4):267-280.

[6] 李娟,刘禹,钱志鸿.基于双通信半径的传感器网络DV-Hop定位算法[J].吉林大学学报,2014,44 (2):502-507.

[7] 温江涛,范学敏,吴希军.基于RSSI跳数修正的DV-Hop改进算法[J].传感技术学报,2014,27(1):113-117.

[8] 刘红庆.一种针对无线传感器网络的WNDV-HOP算法[J].计算机应用与软件,2013,30(12):288-290,302.

[9] 杨祥,潘玮.基于RSSI比值修正的无线传感器网络DV-Hop定位算法[J].传感器与微系统,2013,32(7):126-135.

[10] 夏少波,连丽君,王鲁娜.基于DV-Hop定位算法的改进[J].计算机应用,2014,34(5):1247-1250.

[11] Munsuck Jang,Inseong Song.A study on Localization Algorithm using Hop Count and RSSI[J].International Journal of Control and Automation,2013:6(3):267-280.

[12] 罗维,姜秀柱,盛蒙蒙.无线传感器网络选择性DV-Hop定位算法[J].传感器与微系统,2012,31(3):71-77.

[13] Yu Weiqi,Li Hao.An improved DV-Hop localization method in wireless sensor networks [C]//2012 IEEE International Conference on Computer Science and Automatic Engineering.Zhangjiajie:IEEE Press,2012:25-27.

[14] 谭志，张卉.基于节点间覆盖关系的改进DV-Hop定位算法[J].北京邮电大学学报,2014,37 (1):35-38.

[15] 贾琦，周新志.基于无线传感器网络DV-Hop定位算法的改进和研究 [J].计算测量与控制,2013,21(11):3043-3046.

收稿日期：2015-02-16。国家自然科学基金面上项目(21276111)；国家自然科学基金青年基金项目(21206053);浙江省自然科学基金重大专项(2011C12033)。邴晓瑛，硕士生，主研领域：无线传感网定位算法。徐保国，教授。

中图分类号TP393

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.07.030

IMPROVED DV-HOP ALGORITHM WITH WEIGHTING BASED ON MULTIPLE COMMUNICATION RADIUS

Bing Xiaoying1Xu Baoguo2

1(KeyLaboratoryofIndustrialAdvancedProcessControlforLightIndustry,MinistryofEducation,JiangnanUniversity,Wuxi214122,Jiangsu,China)2(SchoolofInternetofThingsEngineering,JiangnanUniversity,Wuxi214122,Jiangsu,China)

AbstractTo solve the problem that in wireless sensor networks with irregular network topology rule,there is the rather bigger error in traditional DV-Hop localisation algorithm when calculating the location of unknown nodes,we proposed an improved algorithm which corrects the hop numbers based on multiple communication radius and corrects the average hop sizes of unknown nodes with weighting.First,we graded and refined the communication radius,and used multi-level communication radius to modify the information of hop numbers between beacon nodes and their neighbouring nodes.Secondly,according to the distance from unknown nodes to beacon nodes,we processed the average hop sizes of every beacon node capable of communicating with unknown nodes by weighting them,and made every weighted average hop size be involved in calculating the average hop sizes of unknown nodes,thus the average hop sizes of unknown nodes were more conformable to actual network situation.Simulation results showed that for the same network topology structure,the improved localisation algorithm effectively raised the localising precision of sensor nodes.

KeywordsDV-Hop localisationMultiple communication radiusWeightingAverage hop sizeLocalisation precision