纪 杰，施伟斌

(上海理工大学 光电信息与计算机工程学院，上海 200093)



改进的无线传感器网络DV-Hop 节点定位算法

纪 杰，施伟斌

(上海理工大学 光电信息与计算机工程学院，上海 200093)

DV-Hop 算法是解决无线传感器网络节点定位问题的一种经典算法。文中根据经典的DV-Hop 算法提出了一种改进算法，通过引入更优的误差矫正和双曲线定位算法，减少了经典算法中多跳过程中积累的定位误差。比较和分析了经典DV-Hop 算法和改进后算法的仿真结果可以看出，改进后的DV-Hop 算法定位精度提高显著，在给定条件下的定位误差下降了约50%。

无线传感器网络；DV-Hop；误差矫正；双曲线定位算法

JI Jie, SHI Weibin

(School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology,Shanghai 200093,China)

无线传感器网络由大量无线传感器节点组成，广泛用于在军事、医疗、商业、环境监测等方面[1]，并成为计算机和通信领域的研究热点。由于传感器节点位置的随机性，无线传感器网络的应用大多基于传感器节点自我定位[2]。由于无线传感网络的应用受功耗、传感器节点成本等方面的限制，因此对无线传感网络定位算法的研究很有必要。

现有的无线传感器网络节点定位算法可以分为Range-based 定位算法和Range-free定位算法，即基于测距技术的定位算法和无需测距的定位算法[3]。Range-based 定位算法测量点到点精确的距离值或角度信息，并使用几何定位方法来定位未知节点，例如RSSI,TDOA,TOA 以及AOA。而Range-free 算法通过距离的估计值而非测量值来定位未知节点，例如质心算法和DV-Hop 算法。与Range-based 算法相比，Range-free 方案硬件成本更低、功耗更小，因此受到更多的关注。本文主要研究无线传感器网络节点的Range-free算法。

1 DV-Hop 算法

DV-Hop算法主要通过距离矢量和跳数来估测未知节点到锚节点的距离，然后使用三边或多边测量法求出未知节点的位置信息。在未知节点的通信范围内，锚节点数目并不多，采用上述方法可以得到节点到其通信范围外的多个锚节点的距离信息。

DV-Hop 算法主要由以下3个步骤组成[4]：

步骤1 所有锚节点向整个网络以洪泛方式发送一个信标，信标中包含锚节点的位置信息以及初始化为1 的跳数信息。所有接收到信标的节点都只保留到每个锚节点的最少跳数。然后节点将此信标继续向外扩展，跳数依次递增。第一步完成后，网络中所有的节点都得到到每个锚节点的相应的最少跳数；

步骤2 在完成第一步后，网络中所有锚节点得到到其它所有锚节点的跳数信息，对此引入一个估计量，用于估计锚节点之间平均每跳距离，然后将此估计量洪泛到整个传感器网络。网络中的未知节点接收到此估计量后，将此估计量和到锚节点的跳数之积作为未知节点到锚节点距离的估计量。锚节点i的平均每跳距离HopSize可以用下式估计

(1)

其中，(xi,yi)和(xj,yj)是锚节点i和锚节点j的坐标；hopij是锚节点i到锚节点j之间的跳数。

所有锚节点将其平均每跳距离HopSize广播到整个网络中，广播的方式采用受控洪泛法。未知节点接收到平均每跳信息，但只存储其接收到的第一个HopSize。同时，未知节点将接收到的HopSize 传播到它们的相邻节点。通过采用受控洪泛法可以基本保证大多数节点接收到的是到每个锚节点跳数最少的HopSize；

步骤3 当未知节点获得到锚节点的3个或3个以上的距离信息时，使用三边测量法或最大似然估计法来对未知节点的坐标进行估计。

设(xu,yu) 是未知节点u的坐标；(xi，yi) 是已知锚节点i的坐标；dui是它们之间的距离。由此可得

(2)

未知节点u的坐标可以通过下式求得

(3)

(4)

(5)

其中，P=(ATA)-1ATB。

2 改进的DV-Hop 算法

主要对DV-Hop 的第二步和第三步进行改进[3-5]。DV-Hop 算法的第二步中，每个锚节点在获得了锚节点之间的平均每跳距离HopSize 后将其广播到整个网络作为矫正值。锚节点广播的数据包形式为{id,HopSize}, 包含锚节点的序号及其平均每跳距离。网络中的节点接收到此数据包后，将其添加到自己的存储表中，并将其传播给邻居节点。第一步完成后，网络中所有节点都获得了各锚节点广播的HopSize。改进的DV-Hop 算法通过求取n个锚节点的HopSize的平均值作为网络中节点间平均每跳距离的估计值[6-8]，即

(6)

其中，n是锚节点的个数HopSize，通过式(1)可以求得。在第二步最后，未知节点到锚节点的距离可以用di来估计，即

di=Hops×HopSizeave

(7)

第三步，假设(x,y)是未知节点的坐标，(xi,yi) 是锚节点i的坐标，未知节点到锚节点之间的距离用di表示，显然有

(8)

在DV-Hop 算法中，未知节点到锚节点之间的距离估计量id和锚节点的坐标一起用于未知节点的几何定位方法中。在本文提出的改进DV-Hop 算法中，不再采取传统的几何定位方法，而采用一种二维双曲线定位算法[9]。

根据式(8)继续推导如下

(9)

即得到

(10)

Zc=[x,y，K]T

(11)

(12)

(13)

根据式(9)和式(10)得

(14)

未知节点的坐标(x，y)可表示为

(15)

3 算法仿真与结果分析

分别对经典DV-Hop 算法和改进DV-Hop 算法进行仿真,仿真参数设置如表1 所示。

表1 仿真参数设置

仿真中，节点通过随机数产生函数rand 在正方形区域内随机生成，经典DV-Hop 算法的节点分布如图1 所示。

对经典DV-Hop 算法进行仿真后，得到的未知节点的定位误差曲线如图2 所示，经典DV-Hop 算法未知节点的定位误差最高可达约60%，且围绕约40%上下波动。定位误差相对较大。

改进DV-Hop 算法的节点分布如图3 所示。对改进DV-Hop 算法进行仿真后，得到未知节点的定位误差曲线如图4 所示，改进DV-Hop 算法未知节点定位误差最高可达到约30%，且围绕约15%上下波动，定位误差相对较小。

图1 经典DV-Hop算法的节点分布图

图2 经典DV-Hop算法的未知节点定位误差

为更加直观地对比改进DV-Hop 算法与经典DV-Hop 算法的定位精确度，分别对两种算法进行了100 次独立重复实验，各得到未知节点定位误差的100 组数据。通过求取每组数据中92 个未知节点定位误差的算术平均值作为平均定位误差率，可以得到两种算法各100 个平均定位误差率的数值。仿真结果如图5 所示。

图3 改进DV-Hop 算法的节点分布图

图4 改进算法未知节点的定位误差

图5 经典DV-Hop 算法和改进DV-Hop 算法平均定位误差率比较

如图5所示，改进DV-Hop 算法明显比经典DV-Hop 算法误差率小、定位精度高。因此采用改进DV-Hop 算法能明显降低节点的平均定位误差率。

4 结束语

本文提出了一种改进的DV-Hop 算法，可以大幅地提高经典DV-Hop 算法的定位精度，而无需增加硬件系统的复杂度和成本。这是由于改进的DV-Hop 算法采用了更优的误差矫正和双曲线定位算法，从而减少了经典算法中多跳过程中积累的定位误差。仿真结果证明了改进DV-Hop算法比原算法更具应用价值。在本文设定的 100 m×100 m范围内，改进DV-Hop 算法其定位平均误差率约为0.3，而经典DV-Hop 算法的定位平均误差率约为0.6，可见改进DV-Hop 算法将经典DV-Hop 算法的定位精度提高了约50%。

本文没有考虑锚节点占总节点个数的比例、节点通信半径、总节点个数、锚节点的分布等因素对未知节点定位误差的影响。因此，以后的研究可以从上述几方面进行。

[1] 史龙,王福豹,段渭军,等.无线传感器网络Range-Free 自身定位机制与算法[J].计算机工程与应用,2004(6):11-13.

[2] 马祖长,孙怡宁.无线传感器网络节点的定位算法[J].计算机工程,2004(6):23-25.

[3] Chen Hongyang, Kaoru Sezaki, Ping Deng, et al.An improved DV-Hop localization algorithm for wireless sensor networks [J]. Eiectronics Optics & Control, 2008(9):2232-2236.

[4] 张震,闫连山,刘江涛,等.基于DV-Hop 的无线传感器网络定位算法研究[J]. 传感技术学报， 2011(8):1469-1472.

[5] Chen Xiao,Zhang Benliang.Improved DV-Hop node localization algorithm in wireless sensor networks[J].International Journal of Distributed Sensor Networks,2012(6):111-113.

[6] 刘乃安.无线局域网(WLAN)原理、技术与应用[M]. 西安：西安电子科技大学出版社,2004.

[7] 张攀东,闵娟娟. WLAN规划和设计时需要考虑的问题[J].福建电脑, 2011(6): 76-77.

[8] 王振亚. WLAN优化系统的设计与实现[D].武汉：华中师范大学,2014.

[9] 杨宁. WLAN规划检测优化系统的设计与实现[J].计算机时代, 2013(9): 11-14.

Improved DV-Hop Node Localization Algorithm for Wireless Sensor Networks

The DV-Hop algorithm is a classical algorithm for node localization in wireless sensor networks. In this paper, an improved algorithm is proposed based on the classical DV-Hop algorithm to reduce the positioning error accumulated in the multi hop process by introducing a better error correction and the hyperbolic location algorithm. After comparing and analyzing the classical DV-Hop algorithm and the improved algorithm, the simulation results show that the improved DV-Hop algorithm can improve the positioning accuracy significantly, with the positioning error reduced by about 50% under the given conditions.

wireless sensor networks; DV-Hop; error correction; hyperbolic location algorithm

2016- 01- 06

全国大学生科技创新重点基金资助项目(201310252012)

纪杰(1992-)，男，硕士研究生。研究方向：通信技术等。

10.16180/j.cnki.issn1007-7820.2016.10.025

TN926

A

1007-7820(2016)10-086-04