基于跳数与跳距优化的三维DV-Hop 定位算法研究*

时雨农，刘海隆

(电子科技大学资源与环境学院，四川 成都 611731)

近年来，随着无线传感器技术的不断发展，无线传感器网络(Wireless Sensor Network，WSN)在生态环境监测中也得到了大量应用[1]。 其中野外生态环境要素的位置信息是重要的参数之一，因经典的二维WSN 定位方法无法反映地形、植株高度等空间上的差异，会产生较大的误差，因此针对WSN 的三维定位算法也就成为重要的研究方向[2-4]。

WSN 三维定位算法可以分为测距(rangebased)的和非测距(range-free)两种[5]。 测距定位算法包括基于信号强度(RSS， Received Signal Strength)来进行距离测量的RSSI 定位算法[6]、利用信号传输时延测距的TOA(Time of Arrival)定位算法[7]、基于到达时间差的TDOA(Time Difference of Arrival)定位算法[8]和综合信号发射和接收角度与时延的AOA(Angle of Arrival)定位算法[9]等。 测距定位算法在精确度上有一定优势，但是因为对设备有所要求，定位成本相对较高，且测量结果易受到WSN 节点所处环境的影响[10]，因此适用于室内或者环境均匀分布的室外WSN 三维定位。 非测距定位算法包括基于三角形内点测试法的APIT 算法[11]、基于网络连通性的质心定位算法[12]和基于距离矢量路由和GPS 定位思想的DV-Hop 定位算法[13]等。 非测距定位算法功耗较小，受环境影响不大，但是精度相对较低，适合用于低功耗、低成本的室外无线传感器网络定位[14]。

DV-Hop 定位算法是由Dragos Niculescu 等人提出的一种非测距定位算法[15]，其工作过程简单、易实现、并且不需要测距设备，但精度相对较差，有不少学者对其进行了改进[16-20]。 本文针对环境监测中对于户外复杂地形WSN 三维定位的需要，分析了传统DV-Hop 算法误差产生的原因，并在此基础上以优化跳数和跳距为核心改进了传统算法，得到了一种更精确的DV-Hop 改进三维定位算法。

1 三维DV-Hop 算法原理

传统三维DV-Hop 定位算法主要分为以下三个步骤[21-28]:

①计算信标节点与未知节点间的最小跳数

首先网络中的信标节点(锚节点)广播自身信息，节点每接收到一个信息就更新它到该节点的最小跳数并处理后转发；若该信息来自自身，则忽略，以确保所有节点都能保存自身与其他任一信标节点间的最小跳数。

②估算未知节点的平均每跳距离

每个信标节点确定自身位置之后，位于(xi，yi，zi)的信标节点i就可根据以下公式确定自身的平均每跳距离:

式中:(xj，yj，zj)为锚节点j的位置，hopi，j为i、j两个信标节点之间的最短跳数。 得到平均每跳距离后，信标节点将其广播出去，而每个未知节点会记录自己所接受的第一个数值，并将其作为自己的平均跳距。

③计算未知节点的位置

设未知节点U的位置为(x，y，z)，平均跳距为Hopsize，与其能直接通信的信标节点位置和跳数分别为(x1，y1，z1)、(x2，y2，z2)、(x3，y3，z3)、…、(xn，yn，zn)，hop1、hop2、hop3、…、hopn。 则此点到相应的信标节点的预测距离分别为d1、d2、d3、…、dn，其中

根据四边定位计算法则，可列出以下方程组:

误差e为

根据最小二乘估计的优化规则min(B-AX)T(B-AX)，对X求偏导，并令其值为0，则可以得到X的估计值:

2 三维DV-Hop 算法定位误差成因分析

2.1 仿真参数设计

利用MATLAB R2020a 软件根据以上步骤对经典三维DV-Hop 算法进行仿真，仿真具体数据如表1所示。 仿真结果如图1(a)所示，图中点号“·”代表未知节点，星号“*”代表信标节点。

表1 经典三维DV-Hop 算法仿真参数设置

根据经典DV-Hop 定位算法，可计算出未知节点的具体位置，称为测算位置。 图1(b)表示的是经过经典DV-Hop 算法计算后各未知节点的预测位置，图中加号“+”节点表示预测的未知节点位置，图中将各未知节点与其对应的预测位置连接起来以表示对应关系。

图1 节点分布与定位结果图

2.2 通信距离与信标节点占比对定位误差的影响

本文通过改变信标节点占比和最大通信半径的方法来测算误差大小并寻找误差规律。 由于无线传感器网络节点分布具有随机性，为保证实验结果的代表性，每次实验结果均为1 000 次重复仿真结果的平均值。 图2(a)是在保持信标节点占比(60%)不变的情况下，改变通信半径，得到的节点定位平均相对误差；图2(b)是保持最大通信半径(40 m)不变，改变信标节点占比，得到的节点定位平均相对误差。

图2 通信距离与信标节点占比对定位误差的影响

分析图3 可知，在达到一定的信标节点占比和通信半径后，经典DV-Hop 算法可以进行较为精确的定位。 在信标节点占比不变的情况下，最大通信半径越大，定位的相对误差越小，最低接近20%；同样的，在最大通信半径不变的情况下，信标节点占比越大，相对定位误差越小，最低接近34%。

2.3 跳数对定位误差的影响

图3 为未知节点与信标节点之间测算距离与实际距离的误差值仿真结果。 实验中将信标节点占比设为40%，通信距离设为30 m，并重复1 000 次求得平均值。 由图可得，相隔跳数较少的节点距离估算误差较小。

图3 相隔跳数对测距误差的影响

2.4 误差成因总结

结合仿真结果与理论分析，可以得出传统DVHop 定位算法的主要误差来源:

①最小跳数计算

在经典DV-Hop 算法中，如果两个节点互在对方的最大通信范围内，就将这两个节点间跳数记为1跳。 但是由于通信距离是一个较大的区间，节点间的实际距离却可以有相当大的差别。 如图4 所示。

图4 节点A 周边节点示意图

对于节点A 来说，最外圈的圆表示最大通信半径，而其他三个节点B、C、D 都处于这一半径之内，在跳数统计上这三点与节点A 的跳数都是1 跳，但是这三者与A 的距离却有着不同差别，代入计算后会造成误差。

②平均跳距计算

经典DV-Hop 算法中，未知节点选择与自己跳数最少的信标节点的平均跳距作为自身的平均跳距。 而在实际网络中，不同节点在不同区域内的分布并不是完全均匀的，节点分布密集的区域平均跳距较小，反之则平均跳距较大，若以单一跳距作为所有节点的计算要素，就不能正确反映整体网络分布状况。

③计算方法

由于DV-Hop 算法中最后的距离估算采用的是直接相乘方法，这在相关节点共线的情况下误差较小。 但是实际情况中节点的布设较为随机，不同节点间的网络拓扑图并不是直线，直接相乘会造成较大误差。

3 三维DV-Hop 定位算法的改进与精度验证

3.1 算法改进

针对上述对DV-Hop 算法误差的分析，本文提出了以下几点优化方案:

①细化跳数

针对跳数计算的问题，本文提出细化跳数的方法。 由于1 跳的代表范围较大，可将一跳细分为更小的区间。 对节点来说，设其周围某邻居节点与其的距离为d，最大通信半径为R，跳数hop 则为:

细分跳数后，跳数和距离之间的比值更接近正比关系。 进而在之后的运算中更加精确地计算节点与其邻居节点间的距离。 显然，m的取值越大，跳数细分程度越高，计算结果就会更加精确。 但是，实际使用中，更细分的跳数会带来两个问题:第一，更细分的跳数意味着节点需要更多次地按照不同通信半径洪泛广播信号，导致无线传感器节点耗能过多，这与无线传感器需要长期存活的要求相违背；第二，实际应用中，较高的细分系数需要无线传感器对信号强度有极高的灵敏度，在实地试验中由于电磁环境复杂，多种无线信号混杂干扰，无线传感器难以分辨更细的跳数，因此可能会产生新的误差。 综合能耗、性能与实际情况，本文将采用m=2 的细分系数。

②信标节点平均跳距计算修正

DV-Hop 算法中对于信标节点平均跳距的计算都是基于无偏估计准则。 即通过令式(11)为0 来计算平均跳距Hopsizei:

式中:N为信标节点的个数。 但在实验中，根据误差分布的高斯特性，使用均方误差比只使用方差要更为合理。 因此本文将式(12)进行等值变换得

根据无偏估计计算法则，对式(12)进行一阶求导，并令其为0，可得符合最小均方误差的平均跳距:

③未知节点平均跳距选择

传统DV-Hop 算法中未知节点直接采用离自己最为接近的信标节点的平均跳距作为自身的跳距。根据图3 仿真结果可以发现，信标节点与未知节点的跳数越大，测算出来的距离误差就越大；直接取用离自身最近的信标节点的数据确实可以避免更远节点对应跳数所造成的误差影响，但却无法完全代表节点周围的所有网络分布状况。 因此，可将离与未知节点一定跳数t内的信标节点的平均跳距纳入未知节点平均跳距计算之中，以权重的形式加入计算。由于距离越远节点的距离误差越大，综合考虑后设定信标节点i的权系数wi为:

式中:跳数限制t，根据仿真实验结果，与环境大小l与通信半径R有关，即

最终求得未知节点的加权平均跳距为:

3.2 仿真精度验证

3.2.1 实验环境设置

实验采用MATLAB R2020a 软件进行仿真，详细数据如表2 所示。

表2 仿真参数设置

3.2.2 仿真结果分析

①信标节点比例对定位精度的影响

图5(a)表示了在固定通信半径为40 m 的情况下，优化算法与经典DV-Hop 算法之间的精度差距。由结果可得，在固定通信距离的情况下，信标节点占比较小时，经典算法和优化算法精度比较接近，这是因为信标节点数量过少，大部分的未知节点与信标节点的跳数都较大，测算的距离误差较大，进而导致最终定位的误差率较高；但是当信标节点数量增多后，优化效果逐渐得到体现，定位误差大幅下降，并且下降趋势逐渐趋缓。 比起传统定位算法，优化后的定位算法定位精度平均提高25%左右。

图5 经典算法与优化算法精度比较

②节点通信半径对定位精度的影响

图5(b)表示了在固定信标节点比例为60%的情况下，优化算法与经典DV-Hop 算法之间的精度差距。 由结果可知，在通信距离较近的情况下，很多节点无法与信标节点直接通信，或者相距跳数较大，这种情况下经典DV-Hop 算法和改进后的算法的定位精度都受到较大影响。 相对于经典算法，优化后的DV-Hop 算法精度得到大幅提高。 在最大通信半径较小的情况下，优化后的算法与经典算法差距不大；但在最大通信半径超过一定值后，优化算法精度显著提高，并随着通信距离的增大逐渐稳定，这是由于在较大的通信距离下细化的跳数所能带来的优化效应慢慢降低，并趋向于稳定。 相较于传统DV-Hop算法，改进算法将定位精度平均提高约30%。

4 结束语

本文通过仿真和理论分析的方法研究传统DVHop 算法的误差，并基于传统DV-Hop 算法的缺陷，提出了一种改进后的DV-Hop 算法。 通过多通信半径的方式来细分节点跳数，以达到提高节点间距离估计的精确度；通过调整平均跳距计算公式的方式改进了信标节点的平均跳距计算；利用传统DVHop 算法得出的规律以权重的形式改进了未知节点平均跳距的选取。 仿真结果说明，本文提出的改进算法相对于传统算法，在相同WSN 网络中，具有更高的定位精度。