基于RSSI技术的DV-Hop算法优化

郑州大学信息工程学院 孔 川 邢庆翔

中国人民解放军72433部队 徐宣军

基于RSSI技术的DV-Hop算法优化

郑州大学信息工程学院 孔 川 邢庆翔

中国人民解放军72433部队 徐宣军

一、DV-Hop算法

DV-Hop算法是APS分布式定位系统中的一种。该算法的基本思想是将未知节点到信标节点之间的距离用网络中节点平均每跳距离和到信标节点间的跳数乘积来标识，再使用极大似然估计法来获得节点的位置信息。DV-Hop算法的定位过程可以分为以下3个阶段：计算未知节点与每个信标节点的最小跳数；计算未知节点与信标节点的实际跳段距离，每个信标节点根据第1个阶段中记录的其他信标节点的位置信息和相距跳段数估算平均每跳的实际距离；当未知节点获得与3个或更多锚节点的距离之后，利用极大似然估计法实现节点定位。

二、RSSI测距技术

RSSI接收信号强度指示器是一种利用信号强度衰减推测距离的测距技术。典型的定位系统有RADARD等。本文引入RSSI测距技术的目的，是为了计算未知节点到信标节点之间的通信距离。自由空间的无线电传播路径损耗模型由下式给出：

式中，d为发射端与接收端的距离（km），f为无线电传播频率（Mhz），n为路径衰减因子，一般取值2～5。在实际的应用环境中，由于多径、绕射、障碍物等因素的影响，无线电传播路径损耗与理论值相比有些变化，常采用对数常态分布模型。模型的数学表达式如下：

式中，PL(d)为经过距离d后的路径损耗（dbm），d0为参考距离，Xσ是平均值为0的高斯分布随机变数，其标准差一般为4～10，PL0是经过参考距离d0后的路径损耗。由式（1）和式（2）可以得到接收端的信号强度表达式为：Pr(d)=Pt-PL(d)。其中，Pr(d)为接收信号强度（dbm），Pt的值为32.44（dbm）。

三、改进算法方案

1. DV-Hop算法的不足。在DV-Hop算法中，由于在实际网络中信标节点到未知节点的距离往往不是直线路径，使用DV-Hop算法会带来较大的误差。如图1所示，设节点1为信标节点，信标节点的平均每跳距离为20m。对于未知节点4，由DV-Hop算法计算出，信标节点1到未知节点4的距离为60m。然而，这一估算距离远大于实际两点之间的距离，因为节点1到节点4并非是直线连接。

图1 节点路径示意

2. DV-Hop算法改进。为了减少估算距离与实际距离之间的误差，改进算法利用RSSI技术估算出未知节点到信标节点一跳的距离。当整个网络部署完之后，信标节点在网络中广播数据包，其他节点解析接收过来的数据包，并计算出两节点之间的距离。一旦某个未知节点接收到3个或3个以上从不同信标节点发送的数据包时，就可利用极大似然估计法计算出自己的位置信息，然后将自己提升为信标节点，依次类推，直到所有节点计算出位置信息为止。改进后的算法分为多“轮”，每“轮”中根据网络已有的信标节点计算出未知节点的坐标，如果一“轮”结束，所有未知节点并未估算出结果，则将已计算的未知节点提升为信标节点继续估算未知节点坐标，直到所有节点估算出为止。算法过程如下所示：

（1）首先根据是否为信标节点，将节点标识table设为1或0，然后信标节点在网络中广播带有节点标识符的数据包，其他节点接收相邻节点的数据包；

（2）节点解析接收过来的数据包，分析获得发送和接收信号的强度，由衰减模型计算出两节点之间的距离；

（3）利用极大似然估计法计算出自己的位置。

具体流程如图2所示：

图2 改进算法流程

四、仿真结果分析

采用MATLAB对DV-Hop算法和改进的算法进行试验仿真，并对结果进行分析。仿真环境假设如下：100个网络节点随机均匀分布在100×100的区域内，设置信标节点数为8，其中信标节点和未知节点随机产生。节点的通信模型都是以自身为中心的圆形，通信半径R为50，信标节点与未知节点的通信能力相同，且都为R。节点间具有对称的通信能力，以及相同的发送和接收能力。为便于仿真，假设网络中并未存在障碍物或干扰。

主要对传统的DV-Hop和改进的DV-Hop在定位精度、稳定性、定位覆盖率等方面进行比较。每种算法执行20次，并绘制出曲线图。DV-Hop和改进的DV-Hop算法仿真结果如图3所示。

图3 仿真结果对比

从仿真图中可以看出，DV-Hop 的定位精度平均值约为32.45%，而改进的DV-Hop算法的定位精度平均值为22.73%，因此改进后的算法定位精度较原算法有明显的提高，而且发现在仿真过程中随着信标节点密度的降低原DV-Hop算法定位误差变大，但改进后的DV-Hop算法定位误差变化并不大。另外从仿真中还可以看出，DV-Hop得出的未知节点的坐标容易重叠在一起，而改进后的算法定位出的节点则很少会重叠在一起。

在稳定性方面可以从定位精度的统计方差方面考虑，改进后的DV-Hop算法在信标节点比例为0.08时，定位精度的统计方差为0.0544，而传统的DV-Hop算法方差为0.0972，因此改进后的DVHop算法比原DV-Hop算法的稳定性略优。

在定位覆盖率上，改进后的算法在信标节点中的比例为0.08时，定位覆盖率为98%，原DV-Hop的定位覆盖率为92%，传统的DVHop算法的覆盖率达到98%时需信标节点的比例为0.25，因此改进后的DV-Hop算法在定位覆盖率上有明显的提高。

从以上仿真结果分析可以看出，改进后的DV-Hop算法在定位精度、稳定性以及定位覆盖率上的效果都要好于传统的DV-Hop算法。

五、结论

本文针对DV-Hop算法存在的不足，利用RSSI技术测量一跳节点之间的距离，并将已经定位出的未知节点提升为信标节点，经过仿真验证，改进后的算法在定位精度上明显优于DV-Hop，并且具有较好的稳定性。然而改进后的算法仍有一些不足，比如将定位出的未知节点提升为信标节点时容易产生误差累积，因此该算法还有不少需要改进的地方。