基于DV-Hop的大规模WSN定位方法研究

摘 要：DV-Hop是大规模无线传感器网络（WSN）典型定位算法，通过测量节点之间的信号传输距离和经过的中继节点数，实现节点的位置估计。针对传统DV-Hop算法中存在的平均跳距误差较大和最小跳数难以确定等问题，通过引入加权平均跳距和基于节点分布的最小跳数，改进了传统DV-Hop算法。仿真结果表明，改进的DV-Hop算法在提高定位精度方面优于传统DV-Hop算法。

关键词：无线传感器网络；节点定位；DV-Hop；平均跳距；最小跳数；定位误差

中图分类号：TP393 文献标识码：A 文章编号：2095-1302（2024）03-00-04

0 引 言

随着传感器技术的快速发展，无线传感器网络已经广泛应用于农业数据采集、工业控制、森林火灾控制和医疗等领域[1]。在无线传感器网络中，节点的位置信息对于网络性能和应用效果具有至关重要的作用。因此，无线传感器网络的定位问题一直是研究热点之一。

目前，无线传感器网络定位算法主要分为基于距离测量和无需距离测量两类。基于距离测量的算法主要包括接收信号强度（RSSI）、到达时间（TOA）、到达时差（TDOA）和到达角测量（AOA）。无需距离测量的算法主要包括质心定位算法（CL）、凸规划方法、近似三角形内点算法（APIT）、网络多跳路由算法（DV-Hop）等[2]。其中DV-Hop算法是一种典型的基于节点距离的定位算法，其利用节点间的跳数和跳距信息进行节点的定位。因其简单易实现、适用于大规模网络和低成本等优点，被广泛应用于无线传感器网络中。因此有许多国内外学者对DV-Hop算法进行研究与改进。文献[3]提出了一种细化半径的节点通信思路，进而细化最小跳数值，大幅降低了传感器的定位误差。文献[4]利用改进鲸鱼优化算法替代最小二乘法求未知节点坐标，以提高定位精度。文献[5]提出了一种质心和DV-Hop混合定位算法MCDA，通过设置TTL值来限制信标节点广播数据的范围以及提高邻居信标节点的比例来改进质心定位算法。

然而，传统的DV-Hop算法存在平均跳距误差较大和最小跳数难以确定等问题，这些问题严重影响了算法的定位精度和鲁棒性。因此本文针对传统DV-Hop算法存在的问题，提出了改进的DV-Hop算法。该算法通过引入加权平均跳距和基于节点分布的最小跳数，能够有效地提高定位精度和鲁棒性[6]。

1 DV-Hop算法概述

1.1 算法原理

DV-Hop算法是由Niculescu提出的一种定位方法，是一种基于跳数的无线传感器网络定位算法，其基本思想是通过节点之间的跳数关系来计算节点之间的距离，从而实现节点的定位。具体来说，DV-Hop算法分为三个阶段，分别是跳数计算阶段、距离计算阶段和未知节点计算阶段[7]。

（1）跳数计算阶段：信标节点An通过网络广播包含An位置和跳数字段hn初始值0的消息。节点记录跳数计数值表示未知节点u和An之间的最小跳数hun。重复接收到消息时，节点更新跳数计数值，停止信息获取。该机制使得所有节点都能获得每个信标节点中的最小跳数。

（2）距离计算阶段：根据在跳数计算阶段得到的每个信标节点的最小跳数计算每个跳跃的平均实际距离，如式（1）所示：

（1）

式中：HSizen表示信标节点An的平均跳距；（xn， yn）、（xm， ym）是信标节点An、Am的坐标；hnm是两个信标节点n与m（n≠m）之间的最小跳数。该算法保证了大部分的未知节点都能得到最近的信标节点之间的平均距离。

（3）未知节点计算阶段：通过三方测量或最大似然估计方法，对每个信标节点采用距离计算阶段的固定间隔计算其坐标。

1.2 算法的不足

虽然传统DV-Hop算法具有一定的定位精度和可靠性，但其也存在一些局限性。主要包括以下几点：

（1）定位精度受到节点部署密度和网络拓扑结构的影响。当节点部署密度不足或网络拓扑结构较为复杂时，DV-Hop算法的定位精度会受到较大的影响。

（2）DV-Hop算法的准确度受到节点测距误差的影响。在实际应用中，由于环境干扰等因素的存在，节点之间的跳距测量误差较大，从而影响了DV-Hop算法的准确度。

（3）算法的计算复杂度较高。由于DV-Hop算法需要计算每个节点到已知节点的跳数和跳距信息，因此其计算复杂度较高，对于大规模的无线传感器网络，计算时间较长，从而影响了算法的实用性。

2 DV-Hop定位算法的改进

针对DV-Hop算法的不足，为了进一步提高DV-Hop算法的定位精度，本文主要从两个方面进行改进：基于加权平均跳距和基于节点分布的最小跳数。

2.1 改进平均跳距

加权平均跳距的改进是针对DV-Hop算法中平均跳距的问题而提出的。在DV-Hop算法中，平均跳距的计算没有考虑到节点之间跳数关系的不同，导致了节点的平均跳距具有一定的偏差，从而影响了定位精度。因此，本文研究了一种加权平均跳距的改进方法，通过对节点之间跳数关系进行加权，以降低平均跳距求值中造成的误差，优化节点之间的距离估计。

如图1所示，实心圆u表示未知节点，空心圆表示信标节点。在传感器网络中，假设信标节点An与信标节点Am之间的最小跳数为hnm，信标节点An的平均跳距为HSizen，这样可以求得信标节点An与信标节点Am之间的理论距离如

式（2）所示：

（2）

在计算信标节点An的平均跳距时，考虑信标节点的真实距离和估计距离之间的误差，实际平均跳距也可能与估计值略有偏差，其误差εn如式（3）所示：

（3）

式中，εn表示信标节点An的平均跳距误差。求得误差值后就可以利用对误差εn的优化来达到对信标节点An的平均跳距进行优化的目的，如式（4）所示：

（4）

式中，DHSizen为修正之后的信标节点An的平均跳距[8]。

2.2 改进最小跳数

基于节点分布的最小跳数的改进是针对DV-Hop算法中基于平均跳距的最小跳数问题而提出的。在DV-Hop算法中，由于节点的分布不均匀，可能会存在距离相近但跳数较大的节点，从而影响距离估计的精度。因此，本文提出了一种基于节点分布的最小跳数的改进方法。通过考虑节点分布的情况，寻找距离最近且分布相近的邻居节点，进一步优化节点之间的距离估计，进而根据信标节点之间的实际距离，对最小跳跃次数进行修正，也就是理论上的信标节点Ai的跳跃次数hμnm，如式（5）所示：

（5）

信标节点之间估算跳数和实际跳数之间存在较大差异，为了解决这一问题，可以定义一个差异系数θn，用于计算未知节点到信标节点的最小跳数，如式（6）所示：

（6）

通过差异系数可以直观体现出实际跳数hnm和理论跳数hμnm之间的偏差。差异系数越大，则说明两者之间存在的偏差越大，于是，可以定义一个优化系数wn，用于减少误差以优化节点之间的最小跳数，如式（7）所示：

（7）

式中，wn代表信标节点An的优化系数。利用所定义的系数wn来优化未知节点u到信标节点An的最小跳数hunmin，如式（8）所示：

（8）

式中，hun为未知节点u到信标节点An的实际最小跳数。通过建立权重系数来优化未知节点到信标节点的距离位置，并可以根据最小跳数和平均跳距求出在未知节点u到信标节点An的距离dun，如式（9）所示[9]：

（9）

2.3 算法流程

通过基于加权平均跳距和节点分布的最小跳数的改进，可以有效减小节点之间距离估计的误差，提高定位精度。其算法流程如图2所示。

3 仿真实验与性能分析

为验证改进的DV-Hop算法的性能，本文在MATLAB平台上进行了一系列仿真实验，并与传统DV-Hop算法进行比较。

3.1 仿真环境

仿真中使用的无线传感器网络由100个随机部署的节点组成，节点部署范围为100×100的矩形区域，其中有8个信标节点，节点通信半径值选取50 m，节点部署如图3所示。

为了验证该算法的性能，引入平均定位误差Error如式（10）所示，主要是通过定位误差进行分析，运行10次取平均值[10]。

（10）

式中：（xt， yt）是信标节点An的计算坐标值；（xn， yn）是信标节点An的真实坐标值；N为信标节点数量；K为节点总数；R为通信半径。

3.2 仿真结果

3.2.1 只改进平均跳距

理论距离为数学估计距离，不可能百分之百等同于实际距离，所以有必要对算法进行软件仿真，绘出测距误差图，以展示算法的精确性。测距误差是指未知节点间的理论距离和实际距离的相差值。

如图4所示，我们绘制了改进传统算法平均跳距的测距误差仿真图。实验结果表明，算法能够准确地估算未知节点的位置，其中最大误差为57.75 m，最小误差为2.27 m，平均误差为21.75 m。

3.2.2 只改进最小跳数

如图5所示，我们在其他条件相同的情况下进行了只改进传统算法最小跳数的误差仿真。实验结果表明，该算法能够准确地估算未知节点的位置，其中最大误差为57.75 m，最小误差为2.96 m，平均误差为21.83 m。

3.2.3 同时改进平均跳距和最小跳数

如图6所示为在其他条件都相同的情况下，对传统算法的平均跳距和最小跳数都进行优化后的误差仿真图。从实验结果中可知，算法能够准确地估算未知节点的位置，其中最大误差为48.73 m，最小定位误差为0.97 m，平均误差为19.27 m。

实验结果表明，在通信半径为50 m、信标节点比例为8%的仿真环境中，无论是仅优化平均跳距、仅优化最小跳数，还是同时优化平均跳距和最小跳数，实际位置与理想位置之间的差异都不大。这说明三种优化算法在该仿真环境下的实际定位效果差别不大。因此，在实际应用中我们可以根据具体情况选取运行消耗低且计算相对简单的算法。

3.2.4 不同通信半径对定位误差的影响

为了更全面地评估四种算法的性能，本文进行了另一组误差仿真实验，分别改变通信半径和信标节点比例，选取不同参数值进行仿真并记录实验数据。在信标节点比例为8%的情况下，选取通信半径的值分别为20 m、25 m、30 m、35 m、40 m、45 m、50 m、55 m、60 m、65 m进行仿真，得出平均误差数据，并绘制误差对比折线图，如图7所示。实验结果表明，随着通信半径的增加，四种算法的误差逐渐减小，但是减小的幅度逐渐趋于平稳。在通信半径为65 m时，部分算法的误差略有增加，可能是由于节点随机分布所导致的。总体而言，改进算法的定位性能明显优于传统算法。

通过对比曲线图可以直观看出，在同一信标节点比例条件下，三种改进算法与传统算法的定位误差随通信半径增大而减小。三种优化算法定位精度明显更高，例如当通信半径为55 m时，传统算法定位精度误差为24.73%，改进算法定位精度误差都在20%以下。当通信半径大于50 m时，四种算法定位误差下降趋势减缓，但总体来说，三种优化算法定位性能明显优于传统算法。

3.2.5 不同信标节点比例对定位误差的影响

在总节点数相同的情况下，通过改变信标节点数量来控制不同的信标节点密度，以评估其对算法性能的影响。选取通信半径为20 m不变，信标节点比例从5%到50%进行实验，并得到平均误差数据图如图8所示。实验结果显示，随着信标节点比例的增加，所有算法的误差逐渐减小，但下降速率逐渐趋于平稳。当信标节点比例达到一定程度时，传统算法和改进算法的误差减小幅度明显变小，趋于稳定。只有最小跳数改进和平均跳距与最小跳数同时改进的算法在信标节点比例为50%时误差略有增加，这可能是由于随机分布引起的个别数据误差较大。

通过对比曲线图可以更加清晰地观察到第二种关系，即在相同的通信半径下，随着信标节点比例的增加，三种改进算法和传统算法的定位误差都在逐渐减少。显然，相对于传统的DV-Hop方法，本文提出的三种优化算法能够显著降低定位误差，提高定位精度。在信标节点比例超过40%时，四种算法的定位误差下降趋势逐渐变缓，但是相较于传统算法，本文提出的三种优化算法依然表现出了更好的定位性能。

4 结 语

本文针对DV-Hop算法存在的问题，提出了基于加权平均跳距和节点分布的最小跳数的方法。仿真实验研究表明，改进算法相比传统的DV-Hop算法，在定位精度和计算复杂度方面均有明显的提高，而且改进算法适用于大规模无线传感器网络的定位应用。

注：本文通讯作者为蔡立涛。

参考文献

[1]王慧.无线传感器网络DV-Hop定位算法的研究与改进[D].南京：南京邮电大学，2020.

[2] GAYANA S，DIAS D. Improved DV-Hop algorithm through anchor position re-estimation [C]// 2014 IEEE Asia Pacific Conference on Wireless and Mobile. Bali， Indonesia：IEEE，2020：126-131.

[3]刘超，李海鹏. DV-Hop定位算法的研究与改进[J].火控雷达技术，2021，50（1）：20-25.

[4]王磊，刘晶晶，齐俊艳，等.基于测距修正及改进鲸鱼优化的DV-HOP定位算法[J].仪表技术与传感器，2022，59（2）：116-121.

[5]张悦，梁建国，张浩，等.无线传感器网络质心和DV-Hop混合定位算法研究[J].仪表技术与传感器，2021，58（4）：122-126.

[6]刘芷珺，张玲华.基于邻域搜索粒子群算法的节点定位算法研究[J].电子技术应用，2022，48（9）：97-102.

[7]周凯，周培钊，付文涵，等.无线传感器网络的改进DV-hop定位算法研究[J].东北师大学报（自然科学版），2021，53（4）：137-143.

[8]刘川洲，张玲华.基于DV-Hop算法的无线传感器网络定位精度优化[J].激光与光电子学进展，2021，58（22）：498-504.

[9]祁祺.无线传感器网络中DV-Hop定位算法的研究与改进[D].南京：南京邮电大学，2021.

[10]何少尉.无线传感器网络中一种改进的DV-Hop定位算法研究[J].通信技术，2020，53（3）：648-653.