DV-Hop定位算法的研究与改进

刘 超 李海鹏

(西安电子工程研究所 西安 710100)

0 引言

无线传感器网络[1-2](Wireless Sensor Networks, WSN)通信系统由大量传感器组成，用于对监测区域的目标进行检测、定位和跟踪等，目标定位算法尤为重要。DV-Hop算法不需要进行角度测量或信号强度测量的设备，具有低成本[3]的优势，因而获得了较多研究。DV-Hop算法仅着眼于欲求坐标节点和已知锚节点的平均跳数距离，这种计算方式令节点间距与实际距离存在出入。为了减小误差值，人们对DV-Hop 算法做出了许多的改进尝试，如文献[4]引入的优化均跳距优化和优化位置的改善思路，文献[5]引入了灰狼算法和极大似然估计的改善思路。就DV-Hop算法中的不足，分析研究后，本文引入了细化半径的通信方式的方法，以期改善定位精度。

1 DV-Hop定位算法

1.1 无线传感器网络技术

如今，不可计数的产品、技术伴随着无线传感器网络的进步走进了人们的视野。其中，在定位技术方面，研究人员把在节点定位阶段是否需要进行距离的测量作为评判依据，归为距离式和无距离式两种节点定位思路[6-7]。其中，距离式定位技术是通过测量节点间的角度信息或者信号强度信息进行未知节点的坐标估算的,主要包括有AOA算法(Angle of Arrival)、TOA[8]算法(Time of Arrival)、TDOA算法(Time Difference on Arrival)和RSSI算法(Received Signal Strength Indicator)等，上述前三种方法对硬件设备要求较高,这无疑增加了成本;而RSSI算法在信号传播过程中,信号强度会被障碍物影响而减弱,抗干扰性能较差。典型的无需测距的定位算法主要有DV-Hop算法(Distance Vector-Hop)、质心算法(CentroidAlgorithm)、APIT(Approximate PIT Test)算法等。此类算法不需要测量角度或者测量信号强度的设备，大大降低了成本，因而受到研究人员的欢迎。

1.2 传统DV-Hop定位算法组成

DV-Hop算法源于美国学者Dragos Niculescu等。其主旨是：首先,获取未知节点与锚节点的最小跳数、所有锚节点间的平均跳距；其次,未知节点选取周围任意锚节点的平均跳距作为自身平均跳距值，与自身最小跳数相乘而得锚节点和未知节点间的距离；最后,将距离代入最小二乘法求解欲求节点坐标值。

组成DV-Hop算法的部分有如下文三个阶段[9]。

图1 DV-Hop算法流程图

1)最小跳数获取

DV-Hop算法采用距离矢量路由协议的方法，把网络中每个锚节点的位置坐标信息向周边的节点进行广播，每个节点用{xi,yi,hi}表示,其中(xi,yi)就是锚节点i的位置坐标信息；hi表示这个节点到锚节点i的跳数值，初始值均设置成0。

首先，每个锚节点将自身坐标值和跳数值向邻近节点广而告之。邻近节点处于接收到发出消息的状态后，数据中的跳跃值就会增加1跳，紧接着将更新后的数据转发给别的邻居节点，将信息使用泛洪方式传播。

其次，进行跳数选择操作：各接收节点将来自同一锚节点跳数值中的最小值保留，其他数值全部舍去。保持网络的畅通，就能让全部节点处于获取每个锚节点最小跳数的状态。

2)平均跳距的计算

全部节点获取每个锚节点最小跳数后，可从式(1)获悉全部锚节点的平均跳距。

(1)

式(1)中，i、j代表锚节点；(xi,yi)、(xj,yj)表示锚节点的坐标；hj表示在i与j不等时锚节点i、j之间的最小跳数；HopSizei表示锚节点i的平均每跳距离。

在网络中，将获得的每个锚节点平均跳距进行广播，当未知节点处于获悉信息状态时，选择一个锚节点平均跳距作为自身的平均每跳距离。此时，全部未知节点u使用式(2)计算距锚节点i的近似距离dui。式(2)中，hui是锚节点i和未知节点u之间的最小跳数。

dui=hui×HopSizeij(i≠j)

(2)

3)未知节点坐标的解算

当获得的锚节点与未知节点的间距在3个或3个以上时,就能按照最小二乘法进行推理解算获取所求未知节点的估计坐标值[10]。

利用锚节点i和未知节点u的坐标(xu,yu) 和(xi,yi)可以得到方程(3)为

(3)

未知节点的坐标用公式(4)求得。

(4)

方程(4)可改写成Ax=B的形式，可得

(5)

(6)

由此可得未知节点u的坐标为

Xu=(ATA)-1ATB

(7)

1.3 传统DV-Hop定位算法举例

图2展示了4个节点的位置关系：A、B、C三个节点是坐标已知的锚节点，N节点作为未知坐标节点。

图2 网络拓扑结构

由勾股定理得节点A、B的直线距离为20 m，节点A、C的直线距离为40 m，节点B、C的直线距离为50 m。

从图中跳步路径可得，2为节点A、B间的最小跳数值，3为节点A、C间的最小跳数值，4为节点B、C间的最小跳数值。

式(8)表示A、B、C三个节点的平均跳距值，对应为

(8)

N取A的平均跳距值，式(9)获得N节点的估计距离为

(9)

最后，将上述数值代入最小二乘法中推导解算就可以取得未知节点N的预计坐标信息。

2 校正算法

2.1 DV-Hop算法存在的不足

1)跳数信息

通信半径R内的全部跳数值统一用1表示，与实际情况会产生偏差。比如，把0.3跳的实际跳数笼统的记为1，那么估计距离就会大于实际距离，生出误差。

2)平均跳距

未知节点的平均跳距值是随锚节点选取而发生着变化的，不是固定值。这种情况下，生出误差是在所难免的。

3)计算未知节点坐标的方法

在最小二乘法的推导计算过程中，不能排除得不到(ATA)-1的情况，一旦发生这种情况，就无法成对欲求坐标值的解算，更无定位精度可言。

2.2 改进算法的主旨思想

在DV-Hop 算法跳数获取环节，只要邻近节点出现在锚节点半径为R的通信范围之内(或等于R)，就统一认为它们间的跳数为1跳。

当图3所示的情况出现时：已知坐标的3个锚节点，按DV-Hop算法跳数判定方法，统一认为节点O、A与节点O、B的最小跳数值是1跳。实际情况与之不符，最小跳数值统一记为1跳，定会产生有误差的结果。

图3 锚节点分布示意图

因此，将节点间的跳数细化非常必要，本文利用细化通信半径的方式达到跳数细化的目的。改进算法将通信半径细分为0.1R、0.2R、0.3R、0.4R、0.5R、0.6R、0.7R、0.8R、0.9R和R共十种，也就是把通信面积分为了十种，R代表通信半径。

2.3 改进算法的具体步骤

第一步：最小跳数获取。

1)初始化网络，网络中所有锚节点首次广播的通信半径是0.1R，在0到0.1R的圆形区域内通过广播向范围内的节点发送自身信息。

当信息传播范围内的节点处于接收到信息的状态后，接收节点获悉与锚节点的最小跳数值是0.1跳。

2)所有锚节点以0.2R作为广播的通信半径，在0到0.2R的圆形区域内通过广播向影响范围内的节点发送自身信息。

如果是首次获得锚节点信息的节点，该节点获悉与锚节点的最小跳数值是0.2跳。若该节点之前就获取过信息，仍保留0.1跳的数值。

3)以此类推，在之前通信半径的基础上每次增加0.1R进行锚节点的第三、四、五、六、七、八、九和十次广播，得到最小跳数值。在通信半径变化的情况下，通过改变传感器的发射功率来实现传感器广播范围的变化。

第二步：平均跳距的计算。

使用勾股定理求取锚节点间的直线距离，再使用式(1)获取全部锚节点的平均每跳距离值。

第三步：解算未知节点坐标。

任意选取一个锚节点的平均每跳距离作为未知节点平均跳距进行节点间距离计算。

最后，按照最小二乘法解算获取未知节点的坐标值。

3 仿真实验的结果与分析

3.1 仿真环境

使用计算机中Matlab R2016a软件形成边长100 m的正方形，并在其中任意分布100个节点。在锚节点数目一致的情况下，设计进行多组实验,利用蒙特卡洛方法得到定位误差平均值。本文选取相对定位误差作为评价标准，如式(5)为

(5)

其中，N为节点总数；u为锚节点数目；R为节点的通信半径；(xi,yi)，(Xi,Yi)分别表示未知节点i的估算坐标与实际坐标。

仿真参数如表1所示。

表1 实验仿真参数

节点随机分布图如图4所示。

图4 节点随机分布图

3.2 仿真结果分析

仿真结果如图5所示。

图5 4种半径对应的原算法相对定位误差与锚节点百分比的关联示意图

由图4与图5分析可得：

1)通信半径统一的前提下，随锚节点百分比的变大，原算法的相对定位误差呈减小的趋势。

2)锚节点百分比统一的基础上，当通信半径逐步变大时，原算法的定位误差也呈下降态势，但是降幅在逐步趋小。

3)实际的工程应用时，通信半径不是越大就越好的，因为随着通信半径变大，就需要更大的能量，会增加相应的成本。

4)仔细观察可得个别点的相对定位误差会略高于前边的点，这是网络拓扑造成随机产生的缘故。

图6至图9说明：在以上4种半径下进行节点定位，改进算法的相对定位误差值有大幅的减少。这说明节点间的跳数细化对降低相对定位误差的效果是积极的。

图6 R=20m

图7 R=30m

图8 R=40m

图9 R=50m

误差降低值如表2所示，改进算法相较于原算法削减了16%～39%的相对定位误差。

表2 改进算法在差别半径下的误差降低值

4 结束语

本文首先研究了经典DV-Hop算法，经分析发现了存在的缺陷，以跳数信息的不足为切入点，引入通信半径细化的改善算法，获得了细化的跳数和较为准确的节点间距值。

经由Matlab仿真实验，结果说明：在平等仿真前提下，改进算法在没有大幅度增加算法复杂度的背景下有效降低了定位误差，实现了提高定位精度的目的。

然而本文提出的改进算法的优势只是对定位精度的改善，对多次通信半径的广播和泛洪中能耗所产生的花销没有考虑在内。未来应着重研究在不影响定位精度的前提下，降低改进算法的成本。