一种改进型WSN DV-Hop定位算法

2017-10-17胡江坤冉松山唐宏成

电子科技 2017年10期

关键词：数据包无线距离

胡江坤，付晶，冉松山，唐宏成

(重庆机场集团有限公司航务管理部，重庆 401120)

一种改进型WSN DV-Hop定位算法

胡江坤，付晶，冉松山，唐宏成

(重庆机场集团有限公司航务管理部，重庆 401120)

针对无线传感器网络中DV-Hop定位精度较低，且定位精度完全依赖于未知节点到对应锚节点的跳数以及平均跳距的测量精度这一问题，提出一种改进型DV-Hop算法。通过仿真实验表明，在节点个数、通信半径、以及锚节点率一定时，该算法的平均定位误差比DV-Hop的平均定位误差分别减小25%，19%和22%。

无线传感器网络；测量精度；定位误差；DV-Hop

AbstractAccording to the lower localization accuracy of DV-Hop algorithm in WSN, as well as, itslocalization accuracy based on the distance between unknown nodes and anchor nodes, and the measure-ment precision of average jump distance, this paper presents an improved DV-Hop algorithm.The simula-tion results show that:when nodes numbers、communication radius and anchor nodes rates are under givenconditions，average positioning error of the improved algorithm has been reduced 25%,19% and 22% res-pectively.

Keywordswireless sensor networks;measurement precision;localization;DV-Hop

无线传感器网络(Wireless Sensor Networks，WSN)是由大量静止的或移动的传感器节点以自组织和多跳的方式构成的无线网络，其目的是协作地感知、采集、处理和传输网络覆盖地理区域内感知对象的监测信息，并报告给用户[1]。

在无线传感器网络中，节点的定位至关重要，GPS是目前应用最广的定位服务，但受到成本、功耗、扩展性等问题的限制，甚至在某些场合根本无法实现。目前最主要的节点定位方法是利用少量已知节点，通过节点定位算法获得未知节点的信息。因此需要采用一定的定位机制与算法来获得未知节点的信息。研究者已经提出了多种算法解决WSN定位问题，主要分为测距定位和非测距定位两种方法[2]，基于测距的定位算法通过测量节点间点到点的距离或角度信息，使用三边测量、三角测量或极大似然估计法计算未知节点位置。基于测距的定位算法常用的测距技术有接收信号强度指示器(Received Signal Strength Indicator，RSSI)[3]、到达时间(Time of Advent，TOA)[4]、到达时间差(Time Difference of Arrival，TDOA)[5]、到达角(Angle of Arrival，AOA)[6]。与距离无关的定位算法利用网络的连通性进行定位，成本和功耗相对较小，且无需额外的硬件支持，因此受到较大的关注[7]。

1 DV-Hop定位算法

DV-Hop(Distance Vector-Hop, DV-Hop)算法是Niculescu和Nath等人提出的[12-15]，基本思想分为3个步骤。

步骤1锚节点在全网中广播自己的位置数据包，格式为

{(xi,yi),idi,hopsi}

(1)

其中，(xi,yi)是锚节点i的位置坐标；idi是锚节点i的标识号，hopsi为跳数值，将其初始化为0，每个接收到此数据包的节点将此数据记录到自身的数据表中然后将其跳数值加1后转发给其邻居节点。当接收节点接收到相同id号的数据包时就将跳数值与自身数据表中存放的跳数值比较，如果较小则代替原表中的数据，否则丢弃该数据包，并且也不转发。最后，通过网络洪泛法，记录全网中的所有节点到对应锚节点的最小跳数值。

步骤2计算各个锚节点的平均每跳的距离。通过步骤1计算出各个锚节点到其它锚节点的跳数值和位置信息，再通过式(2)估算其平均每跳的距离

(2)

式中，(xi,yi)和(xj,yj)分别是锚节点i和j的坐标；hops(i,j)为锚节点i与j之间的最小跳数值。将HopSizei作为一个校正值通过可控洪泛法广播至网络中，而每个待定位节点仅接收获得的第一个校正值。待定位节点(xk,yk)到锚节点i的距离用该锚节点平均每跳的距离与到该锚节点的跳数的乘积表示，如式(3)所示

d(i,k)=HopSizei×hops(i,k)

(3)

步骤3当待定位节点获得3个或更多的锚节点的距离后，则执行三边测量定位法或极大似然估计法进行定位。

由于DV-Hop[8]节点定位法对锚节点的比例要求不高，且定位精度较高，算法比较简单，所以成为了一种与距离无关的经典的的定位算法。

目前，有学者对该算法进行了改进，如文献[9]提出了利用无线信号在同种介质中的传播速度不变性，用计时器来测量信息在锚节点间的传送时间以及锚节点与未知节点间的传送时间，并利用该时间比例来修正未知节点的估计距离；文献[10]提出了一种基于RSSI的DV-Hop加权算法，该算法利用节点接收锚节点位置信息时的信号强度对邻居节点间跳数进行加权处理，将节点间的跳数与距离相关联；文献[11]利用最小均方误差对平均跳距进行改进，并考虑到传感器节点通常部署在非平面应用场景，通过补偿系数来校正未知节点到锚节点之间的距离，提出一种基于补偿系数的定位算法。这些方法在一定程度上能够提高定位精度，但是为了提高定位精度和定位覆盖率，还需还需对DV-Hop算法进行改进。

2 改进型DV-Hop定位算法

本文主要从以下两方面进行算法的改进：

(1)通过极大似然估计法估计锚节点间的平均每跳距离值。首先假设锚节点i通过经典的距离矢量交换协议获得了n个锚节点的位置信息和跳数信息。再假设锚节点i和锚节点j之间测量距离Dij服从正态分布

N(cihopsij,σ2)

(4)

其概率密度函数为式(5)所示

(5)

其中，ci是锚节点i的平均每跳距离；hopsij是锚节点i和锚节点j之间的跳数，而实际距离di1,di2,…,din,即为一个样本值，其中

(6)

建立MLE法的似然函数

(7)

对式(7)两边同时取对数可得

(8)

以ci为变量，对式(8)两边同时求导得

(9)

令导数等于0得

(10)

假设网络中共有m个锚节点，则网络的平均每跳距离c如下

(11)

最后将网络平均每跳距离c广播出去；

(2)通过引入一种空数据包Empty Packet，没有实际的数据信息。在无线传感器网络路由拓扑已经建立好的情况下，用来在各个节点之间传送以计算路径之间的通信时间，然后利用此时间信息来校正节点间的跳数值。

步骤1锚节点广播自己的位置信息数据包，同时开始启动定时器。此位置信息数据包格式如式(12)所示

{(xi,yi),idi,hopsi}

(12)

每个锚节点在收到其他锚节点的位置信息后记录到自身的数据表中然后返回带自身标识的Empty Packet;

步骤2当某锚节点收到返回的Empty Packet后停止计时，此时计时器便会得到两个锚节点之间的数据包来回传送时间T(i,j)，计算两个锚节点之间单程数据包的纯传送时间t(i,j)如式(13)所示

(13)

其中，Δt为传感器节点从接收到完成发送数据包所需时间，不同类型的传感器节点该值不同但都是固定的。计算两锚节点之间的平均每跳的传送时间值Δt(i,j)为

(14)

步骤3假设锚节点i收到n个锚节点的位置信息和时间信息，则计算平均每跳距离值ci和平均每跳传送时间值Δti如下

(15)

然后将ci广播出去。当每个锚节点收到其他锚节点的平均每跳距离值后计算网络平均每跳距离值c如式(11)所示；

步骤4未知节点发送一个包含自身标识号的请求定位信息包，同时启动定时器。锚节点收到请求定位信息后发送数据包为

{(xi,yi),idi,c,Δti,hopsi}

(16)

步骤5未知节点收到锚节点发送的上述数据包后停止定时器并记录传送时间T(i,k)，然后计算自己到锚节点单程数据包的纯传送时间，如未知节点k到锚节点i的单程数据包纯传送时间为t(i,k)

(17)

步骤6计算未知节点k到锚节点i的跳数值h(i,k)

(18)

计算未知节点k到锚节点i的距离d(i,k)

d(i,k)=h(i,k)×c

(19)

步骤7如果未知节点得到了3个及其以上的距离值后，再通过极大似然估计法或者三边测量法计算未知节点的位置信息。

3 仿真分析

为验证本文的改进算法对DV-Hop算法在对未知节点进行定位时各方面性能的改进，使用Matlab进行仿真。在一个100 m×100 m的正方形区域内随机部署了若干节点进行验证。初始节点的随机分布如图1所示。

图1 初始节点随机分布

定理1平均定位误差。平均定位误差是指所有未知节点的定位误差之和与未知节点个数的比值，如下

(20)

图2为节点个数与平均定位误差之间的关系。在固定大小的实验平面区域内通过改变节点总数来改变平均网络节点密度。其中节点通信半径R=15 m，锚节点比例为10%，节点数从150递增到400。由图2可知，改进型DV-Hop算法平均定位误差比DV-Hop算法平均定位误差减小了约25%。

图2 节点个数与定位误差

图3 通信半径与定位误差

图3为节点通信半径与节点平均定位误差之间的关系。其中节点数为400，锚节点数为40。当节点通信半径由15 m递增到50 m时，改进型DV-Hop算法平均定位误差比DV-Hop算法平均定位误差减小了约19%。

图4为锚节点比率与平均定位误差之间的关系。其中节点个数为400，通信半径为R=15 m，锚节点比率从5%递增到40%，由图4可知，改进型DV-Hop算法平均定位误差比DV-Hop算法平均定位误差减小了约22%。

图4 锚节点比率与定位误差

4 结束语

本文提出了一种基于标准的DV-Hop算法的改进算法，仿真实验表明，该改进算法有效提高了未知节点的定位精度。改进后算法也有不足之处，在用计数器计算信息在节点之间传输时，通信数据量增大，导致节点能量消耗增大。

[1] Mizugaki K,Fujiwara R,Nakagawa T,et al.Accurate wireless location system with 22-cm error using UWB-IR[C].Washington,DC:Radio and Wireless Symposium,2007.

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

[3] Hart A,Hopper A,Steggles P.The anatomy of a context aware application[J].Wireless Network, 2011(1):1-16.

[4] Chen Xiao,Zhang Benliang.Improved DV-Hop node locali-

zation algorithm in wireless sensor networks[J].Intetnational Jorunal of Distributed Sensor Networks,2012,10(6):111-113.

[5] Girod L,Bychovskiy V,Elson J,et al.Locating tiny sensors in time and space:a case study[C].Germany:IEEE I-CCD,2002.

[6] Girod L,Estrin D.Robust range estimation using acoustic and multimodal sensing[C].Hawaii:Proc of the IEEE/RSJ International Conference on Intelligent Robots and Systems(IROS01),2001.

[7] 李彦,田亮.一种结合辅助估距锚点的改进型算法[J].南京邮电大学学报:自然科学版,2016, 36(5):120-126.

[8] 纪杰,施伟斌.改进的无线传感器网络DV-Hop节点定位算法[J].电子科技,2016,29(10):86-88.

[9] 赵灵锴,洪志全.基于无线传感器网络的-定位算法的改进[J].计算机应用,2011,31(5):1189-1192.

[10] 周小波,乔钢柱,曾建潮.无线传感器网络中基于的加权定位方法[J].计算机工程与应用,2011,4(14):109-115.

[11] 朱青青,杨玉斌,刘娜,等.无线传感器网络中基于一致性的安全定位方法[J].计算机工程,2016,10(42):151-157.

[12] Niculescu D,Nath B.DV based positioning in Ad hoc networks[J].Journal of Telecommunication Systems,2003,22(174): 267-280.

[13] 韩震,肖铁军.基于跳数修正的DV-Hop改进算法[J].电子科技,2015,28(1):158-163.

[14] 刘彩霞,黄延磊.中抵御虫洞攻击的改进的算法研究[J].传感技术学报,2011,24(10):1473-1478.

[15] 李志远.无线传感器网络中DV-Hop算法研究[D].南京:南京理工大学,2010.

An Improved Algorithm for the DV-Hop Localization of Wireless Sensor Network

HU Jiangkun,FU Jing,RAN Songsan,TANG Hongcheng

(Navigation Department,Chongqing Airport Group Co.,Ltd.,Chongqing 401120,China)