基于RSSI修正的改进DV-Hop测距算法

方海涛， 雷 菁， 胡昆明， 龚政辉

（①国防科学技术大学 电子科学与工程学院，湖南 长沙 410073；②空军装备研究院 通信导航与指挥自动化研究所，北京 100843）

0 引言

在多数无线传感器网络（WSN，Wireless Sensor Networks）的应用中，传感器节点是随机分布的,除了少数锚节点外,绝大多数节点的位置是未知的。如何获取所有节点的位置信息是应用无线传感器网络前首先需要解决的问题[1]。DV-Hop算法是WSN节点定位中的一种经典算法，其基本思想是将未知节点到锚节点之间的距离用平均每跳距离和两者之间跳数的乘积表示[2]。针对DV-Hop算法改进的研究有很多，如文献[3]是通过提高平均跳距的精度来提升定位精度；文献[4]通过提高平均跳距计算精度和优化节点位置计算方程来提高定位精度；文献[5-6]也在定位方程和计算方法方面进行了改进；文献[7]引入优先级方法，提高测距误差小的锚节点的影响度，并使优先定位的未知节点参与其他未知节点的定位计算，由此降低定位误差；文献[8]采用了RSSI与DV-Hop结合的方法提高定位精度，但只是简单地使用RSSI测距值代替锚节点一跳范围内的节点距离，对于距锚节点一跳范围外的节点测距没有做修正。这些方法虽然在一定程度上提高了定位精度，然而都没有修正因网络节点分布不均所导致的误差。

1 DV-Hop算法及误差分析

DV-Hop算法通过获取未知节点到锚节点的最小跳数，用平均跳距与最小跳数的乘积来估算未知节点到锚节点的距离。平均跳距的获得是通过两已知锚节点的距离除以其间最小跳数而得到。这种计算平均跳距的方法虽然不受地形、地貌和天气等环境因素的影响，但它不能反映出由节点分布不均引起的实际跳距（指相邻节点间的实际距离）之间的差异，某些实际跳距与平均跳距往往相差甚远。因此，当节点分布不均时DV-Hop算法会引起较大的测距误差，进而影响定位精度。

如图1示，假设L1、L2和L3分别为锚节点，L1到L2的距离为D12=30，L1到a的实际距离为17，L2到a的实际距离为13，L1与L2之间跳数为Hops12=5跳；L2到L3的距离为D23=18，其间跳数为Hops23= 3跳。根据DV-Hop算法，得到平均跳距为Hopsize=(D12+D23)/(Hops12+Hops23)=6。再由L1、L2到未知节点a的跳数分别为2跳和3跳，得到未知节点a到锚节点L1、L2的距离分别为d1=12、d2=18。此距离与真实距离相差较大，这种误差是由于网络节点分布不均匀导致的，L1到未知节点a只有2跳，但节点分布稀疏，实际距离较大；而L2到未知节点a的跳数虽然有3跳，但由于节点分布密集，因而实际距离较小。

图1 DV-Hop误差示意

2 基于RSSI修正的DV-Hop算法改进

已知发射节点的发射信号强度，接收节点根据收到的信号强度，计算出信号的传播损耗，再利用损耗模型将传输损耗转化为距离，这种方式就是RSSI测距[9]。虽然RSSI所采用的测距方法能够反映出由节点分布不均而引起的实际跳距之间的差异，但这种用传播功率损耗来推算距离的做法往往受地形、地貌和天气等环境因素影响很大。为避免这个问题，文中不直接用RSSI算法得到的路径长度作为两节点间距离，而是用每一跳的两节点间RSSI路径长度与平均每跳的RSSI路径长度的比值作为修正系数——该系数由于是“比值”因而不再受环境因素的影响——然后再用修正系数与DV-Hop算得的平均跳距相乘来修正每跳的跳距。该所得跳距既能反映由节点分布不均引起的实际跳距之间的差异，还能不受环境因素的影响。

算法具体过程描述如下：第一步与DV-Hop一样，锚节点以固定功率泛洪广播自身位置信息，自身ID、跳数字段Hops，初始为0，接收到该数据的节点将Hops+1并记录到数据包中，与DV-Hop不同的是该数据包中加入了由RSSI理论模型测得的路径长度值，记为RSSID(n)，这样该节点数据包中记录的信息如下:

ID 坐标 Hops1RSSID(1)

节点再以固定功率继续向邻居节点转发该数据包，邻居节点收到该节点转发的信息后，将跳数字段Hpos+1，并将自身收到的RSSI所测得的路径长度值与数据包中上一跳的路径长度值相加，并加入数据包，如下：

当第n跳到达某节点时，该节数据包中数据为：

与DV-Hop相同，当收到同一个ID的信息包中跳数小于已有跳数时，则替换，否则丢弃。当一个锚节点的数据包经n跳被另一个锚节点接收后，即可按照DV-Hop的方法计算平均跳距，同时计算平均每跳的RSSI路径平均长度值，如式（1）：

然后按DV-Hop方式广播平均跳距Hopsize和平均RSSI路径长度RSSIDavg。

第二步，建立跳距修正系，用每一跳的RSSI路径长度RSSID( i)与平均路径长度RSSIDavg相除，作为该跳跳距的修正系数iε：

以跳距修正系数乘以平均跳距，即得修正后的每跳跳距。例如未知节点到锚节点之间的跳数为n，求两节点之间的距离如下：

由式（2）和式（3）得：

由此，各未知节点可用自身信息表中存储的RSSIDN的值和平均跳距、平均路径长度，方便地算出到锚节点的距离。

第三步，与DV-Hop算法一样，可利用三边测量法或极大似然估计法等计算出未知节点的位置坐标。

3 仿真实验

在Matlab环境下对文中提出的改进型DV-Hop算法进行仿真，同时与传统DV-Hop算法或其他DV-Hop改进算法进行比较，蒙特卡洛计算次数为500次。

3.1 测距误差

设定总数为100的节点随机分布在100 m×100 m的正方形内，未知节点和锚节点具有相同的通信半径。图2给出了节点通信半径分别为15 m、20 m和25 m时文中改进的算法与原DV-Hop算法测距误差比较。

图2 3种不同通信半径时的测距误差曲线

从图2可以看出，在3种不同的通信半径下，锚节点数从10到50，文中改进算法的测距误差曲线始终低于DV-Hop算法的误差曲线。其中通信半径为15 m、20 m和25 m时，平均误差分别降低0.57 m、1.78 m和2.33 m。通信半径越大，文中算法的测距误差降低越明显，这是因为随着通信半径的增大，平均跳距也会增大，因而文中算法通过修正系数与平均跳距相乘所获得的修正效果也就越明显。

3.2 定位误差

设定总数200个节点随机分布在150 m×150 m正方形的区域内，锚节点和未知节点通信半径均设为50 m。用估计坐标与真实坐标的距离差值相对于节点通信半径之比表示定位误差。对文中改进型DV-Hop算法进行仿真，并与原始DV-Hop算法、文献[3，4，8]中算法的定位误差进行对比，如图3所示。

图3 4种算法定位误差曲线

从图3可以看出，锚节点数从10到60，文中算法定位误差始终低于另外3种算法。与误差最小的文献[8]算法相比，在相同锚节点数量的情况下，文中改进算法的定位误差平均降低3.42%，定位性能有效改善。

4 结语

文中对DV-Hop算法产生误差的原因进行了分析，针对DV-Hop算法测距误差受节点分布均匀程度影响较大的问题，提出了一种基于RSSI修正的改进型DV-Hop测距算法。该算法以RSSI值为基础建立修正系数，用来修正DV-Hop算法中的每跳跳距。由于RSSI修正系数是一个比值，因此不会受到应用环境变动的影响，该算法在提高测距精度同时保持了DV-Hop算法环境适应性强的优点。仿真实验证明该算法有效地降低了由于节点分布不均而引起的测距误差，提高了定位精度。

文中的仿真实验是在原DV-Hop算法基础上，通过加入RSSI修正值以提高测距和定位精度，下一步的工作是将文中的修正算法与其他的改进型DV-Hop算法相结合进行仿真验证，另外如何降低算法的能量开销也将是下一步的研究内容。

[1] 苏凯峰，雷菁，吴晓光.基于DV-Hop算法的地质灾害预警应用研究[J].通信技术，2011,44（04）：152-154.

[2] 蔡玲，周力.定位算法在传感器网络中的改进策略[J].通信技术，2011，44（04）：93-96.

[3] 林金朝，刘海波，李国军.无线传感器网络中DV-Hop节点定位改进算法研究[J].计算机应用研究，2009,26（04）：1272-1275.

[4] 张佳,吴延海,石峰.基于DV-Hop的无线传感器网络定位算法[J].计算机应用，2010，30（02）：323-326.

[5] 吕睿,阳宪惠．减少无线传感器网络节点定位误差的方法[J].清华大学学报：自然科学版，2008，48（S2）：30-36.

[6] 林玮,陈传峰.基于Rssi的无线传感器网络三角形质心定位算法[J].传感器技术，2009,289(02):180-182.

[7] 白凤娥,姜晓荣,牟汇慧.无线传感器网络DV-Hop定位算法的研究[J].计算机与数字工程，2010,38(03):34-36.

[8] 张品，孙岩.一种新的无线传感器网络DV-Hop算法[J].电子器件，2010,33(01):117-120.