基于GWO和PSO协同优化的DV-Hop定位算法

朱子行 陈辉

摘  要：无线传感器网络具有感知和处理信息的能力，只有当被测网络内节点的位置已知时，节点传递给用户的信息才有意义。针对DV-Hop定位中传统最小二乘法不可避免的精度低的缺点，引入粒子群算法（PSO）和灰狼优化器（GWO）来估计未知节点位置。粒子群算法具有个体记忆的特点，采用粒子位置更新代替灰狼个体位置更新，使灰狼算法在优化上具有可记忆性。仿真数据表明，改进后的算法可以有效降低节点定位误差，实现更高的定位精度。

关键词：无线传感器网络;DV-Hop;灰狼优化器;粒子群算法

中图分类号：TN934       文献标识码：A文章编号：2096-4706（2022）03-0088-04

DV-Hop Positioning Algorithm Based on GWO and PSO Collaborative Optimization

ZHU Zihang， CHEN Hui

（Anhui University of Science & Technology， Huainan  232001， China）

Abstract： Wireless sensor networks have the ability to sense and process information， and the information passed by the nodes to the user is meaningful only when the location of the nodes within the network under test is known. In view of the inevitable shortcoming of low precision of the traditional least squares method in DV-Hop （distance vector-hop） localization， the Particle Swarm optimization （PSO） and the Gray Wolf Optimizer （GWO） are introduced to estimate unknown node positions. The Particle Swarm optimization has the characteristics of individual memory， and the particle position update is used to replace the gray wolf individual position update， so that the gray wolf algorithm has memory in optimization. The simulation data show that the improved algorithm can effectively reduce the node positioning error and achieve higher positioning accuracy.

Keywords： wireless sensor network; DV-Hop; Grey Wolf Optimizer; Particle Swarm optimization

0  引  言

无线传感器网络（Wireless Sensor Network， WSN）作为信息获取的重要技术随着网络信息的快速发展得到了广泛使用[1]。近些年来，WSN在城市建筑，路况交通，医疗军事，森林农田[2]等领域具有广阔的应用前景。识别网络节点的位置是无线传感器网络中的一个重要步骤，在不知道节点位置的情况下收集的信息大多是无意义的。在应用WSN时，传感器节点通常采用随机部署，特别是对于大规模网络。因此，每个节点的位置信息是不可或缺的。一种解决方案是在每个节点上安装一个GPS或北斗定位模块来获取它们的位置信息，这不仅成本高，而且不实用，因为传感器节点的功耗会大大增加，每个节点的生命周期显著缩短。此外，在室内或者密集环境中，定位模块的性能会下降。另一种解决方案是使一部分节点装有定位模块（锚节点）和利用一些定位技术来估计未知节点的位置。

目前，WSN定位技术根据是否需要硬件辅助测量节点间的距离分为基于测距和非测距两大类[3]。基于测距的定位算法主要包括AOA、TOA、TDOA和RSSI等。非测距的经典定位算法主要包括质心定位、APIT、DV-Hop等。非测距算法对相邻锚节点的最小数量有严格的要求，锚节点数目越多越容易获得更高的定位精度[4]。DV-Hop（Distance Vector-Hop）由于它的算法实现简单，不需要提供额外硬件设备，引起了国内外众多厂商、学者的关注。该算法的核心原理是通过平均跳距和最小跳数的乘积来近似传感器节点之间的距离，因此难以达到某些应用所要求的定位精度。本文提出一种改进的DV-hop定位算法，引入粒子群協同灰狼算法代替最小二乘法对未知节点坐标进行估计，实验结果证明可以有效降低定位误差，提高定位稳定性。

1  传统DV-Hop定位算法

1.1  未知节点定位过程

DV-Hop定位是一种基于距离矢量路由机制的非测距定位算法[5]。该算法是由NICULESCU D.和NATH B在2003年提出的，根据节点间的距离选择最佳路径进行定位。无线传感器网络包含两种节点：信标节点（Anchor Node， AN）和未知节点（Unknown Node， UN）。DV-Hop算法步骤为：

（1）求节点之间的最小跳数。每个节点通过距离矢量路由交换原理接收到从ANi发送的数据包。在数据包广播过程中，邻居节点收到数据包时，包内跳数值增加1并转发出去。如果节点接收到来自同一个信标节点的数据包，保留较小跳数值的数据包。

（2）计算ANi的平均每跳距离：

（1）

式中hij是ANi和ANj之间的最小跳数值。（xi，yi），（xj，yj）分别是ANi，ANj的坐标。AN依据公式（1）得到平均跳距后，把自身的平均跳距广播给其他节点。邻居节点接收信息后将跳数加1并继续广播（如果收到多个节点广播的信息，只接收第一个到达的信息），然后通过公式（2）来计算出自身和AN之间的距离：

（2）

其中hui是ANi到UNu的最小跳数，Hopsizei为ANi所在路径的平均跳距。

（3）求出UN和AN之间的距离后通过最小二乘法来估计未知节点的位置。设UNm的坐标为（x，y），ANi的位置是（xi，yi），UNm到ANi的距离为di则：

（3）

为了使方程组线性化，将式（3）转换为AX=B的方程。A，B，X由下式得出：

（4）

最后根据最小二乘法我们得到未知节点的位置为：

（5）

1.2  误差分析

1.2.1  跳数不精确问题

根据DV-Hop跳数定义规则，将信标节点与通信范围内其他节点之间视为1跳，这必然会导致较大的误差。如图1所示。信标节点a发送数据包时，未知节点a1、b、c接收到数据包并都记录为1跳。但明显能看出三个未知节点和信标节点a之间的距离并不相等，因此这种方法计算跳数时会累积更多的误差。

1.2.2  未知节点坐标的计算方法不合理

采用最小二乘法或最大似然估计求解矩阵形式的方程组，可能导致无解或逆矩阵的情况，影响定位结果。

2  改进算法

2.1  PSO算法

粒子群优化算法是一种智能计算领域的群优化算法，该算法通过模拟鸟群捕食过程中每只鸟的活动来达到函数优化的目的[6]。PSO算法的本质是粒子在空间中不断地向特定方向变速运动，并通过自身的记忆和群体通信找到下一个位置，从而找到最优解。速度和位置的更新公式为：

vi（t+1）=vi（t）+c1×rand（）×（pbesti-xi（t））

+c2×rand（）×（gbestj-xi（t））（6）

xi（t+1）=xi（t）+vi（t+1）  （7）

2.2  GWO算法

灰狼优化器（Grey Wolf Optimizer， GWO）模拟自然界中灰狼的领导水平和狩猎机制[7]。灰狼通常被称为顶级掠食者，也就意味着它们在食物链中处于首位。它们通常以5～12只成群生存，具有严格的社会等级地位。四种类型的灰狼α、β、δ、ω，在设计GWO时需要将狼的社会等级抽象为合适的数学模型。默认第一等级（最优解）为α，第二和第三等级分别为β和δ，剩余的候选解为ω。在GWO算法中，搜索时由（α，β，δ）引导，ω跟随前三等级的狼。灰狼狩猎方法涉及三个阶段，接近受害者、包围受害者和攻击受害者。A>1表示灰狼与猎物分离以确定最佳攻击目标。确定攻击目标后，狼群包围猎物可表示为：

（8）

t为当前迭代次数，X为狼的位置，Xp为猎物的位置，D为猎物与狼之间的距离，r1，r2∈[0，1]，a∈[0，2]。包围猎物后，我们认为（α，β，δ）是三种可能的解，它们的位置随着猎物的移动而变化。狼群追逐行为可以表示为：

（9）

2.3  混合策略

单一的群体智能算法会受到自身搜索能力的限制，在处理一些复杂的问题时，会出现求解精度低，容易陷入局部最优等问题[8]。而混合优化算法可以通过不同种群之间的信息交换来达到提高算法性能的目的。现有的混合算法大多数按照使用顺序来优化目标，不能相互结合。因此，PSO-GWO更像是一种并行算法，同时工作和兼顾算法的收敛速度和准确性。本文采用粒子群算法具有个体记忆的特点，采用粒子位置更新代替灰狼个体位置更新，使灰狼算法在优化上具有可记忆性。通常调整惯性常数w来协调混合算法平衡全局搜索和局部开发能力，w的变化范围为[0.5，1]。则上式（6）变成了（10）：

（10）

公式（9）中三个狼到猎物之间的距离变为（11）：

（11）

适应度函数设置为：

（12）

其中，（x，y）为待测节点的坐标，（xi，yi）为信标节点i的坐标，di为信标节点i到未知节点的距离。

粒子群混合灰狼优化算法的具体实现流程为：

（1）初始化a、A、C的值，设置灰狼种群大小为N;

（2）初始化种群个体，同时计算灰狼的适应度;

（3）取适应度值前三位的个体α、β、δ，其对应的位置信息为Xα、Xβ、Xδ;

（4）使用公式（8）更新A和C的值，根據公式（10）更新灰狼个体位置，返回步骤2重新计算并更新α、β、δ;

（5）如果迭代次数t>tmax则认为灰狼已经找到最优解的位置。否则返回第三步继续寻找更好的位置。

3  实验仿真

在本节中，我们使用仿真来评估改进算法的性能。我们把无线传感器网络部署在正方形区域内，每个传感器节点的空间坐标都是随机选择的。所有节点的定位误差是整个仿真过程中唯一的判断标准，从节点总数，锚节点的占总节点数的比例，节点传输半径来分析算法的定位误差。节点定位误差公式为[9]：

（13）

其中（x，y）是未知节点的估计坐标，（xture，yture）是未知节点的真实坐标。R为节点的通信半径。仿真环境如表1所示。

如图2、图3、图4所示，分别是传统DV-Hop、基于PSO改进的DV-Hop和基于PSO-GWO改进的DV-Hop算法在100 m×100 m的正方形区域、通信半径固定为30 m、信标节点的比例为20%的环境下每个节点的误差分析图。从三幅图上面能够看出来本文改进后的未知节点的定位误差相比于其他三个算法都更加精确。

如图5所示，是信标节点不同比例的节点定位误差示意图。其中在网络中设置了200个传感器节点，节点的传输半径为30 m。x轴代表信标节点的个数，y轴表示节点的定位误差。从图中可以看出，当信标节点个数逐渐增加时，节点的定位精度也相应提高。

如图6所示，是改变节点传输半径时的定位误差示意图。其中在网络中设置了200个传感器节点，设置信标节点的比例为15%。当节点的传输半径增加时，节点的通信范围扩大，使得节点之间的最小跳数相对降低，迭代误差也会相对降低，节点误差率降低。

如图7所示，是网络节点增加时节点的定位误差示意图。设置节点的传输半径为25 m，锚节点的比例保持20%。从图中可以看出，随着传感器节点数目的增加，节点的定位精度也在不断提高。

4  结  论

文章提出了一种改进的DV-Hop方法，用于提高无线传感器网络节点的定位精确度。该算法使用粒子群优化算法和灰狼优化器协同运算估计节点位置，而不是传统DV-Hop算法中使用最小二乘法来估计。两种群优化算法的协同处理增强了跳出局部最优的能力，能够更好地找到全局最优解。实验结果证明能够有效地降低节点定位误差，而且不需要额外的硬件。但是双优化算法使得定位算法的速度有所降低，未来的工作将考虑提升定位速度。

参考文献：

[1] FAN Z，CHU H，WANG F，et al.A New Non-Line-of-Sight Localization Algorithm for Wireless Sensor Network [C]//2020 IEEE 6th International Conference on Computer and Communications （ICCC）.Chengdu：IEEE，2020：858-862.

[2] 缪祎晟，赵春江，吴华瑞.信道与能耗感知的农田WSN机会路由优化方法 [J].重庆理工大学学报（自然科学），2021，35（9）：1-7.

[3] 杨艳芳，王伟，王召巴.基于WSN室内定位的路径损耗模型参数算法研究 [J].电子测量技术，2021，44（13）：54-58.

[4] KANWAR V，KUMAR A.“Distance Vector Hop Based Range Free Localization in WSN using Genetic Algorithm” [C]//2019 6th International Conference on Computing for Sustainable Global Development （INDIACom）.New Delhi：IEEE，2019：724-728.

[5] NICULESCU D，NATH B.DV Based Positioning in Ad Hoc Networks [J]. Telecommunication Systems，2003，22（1-4）：267-280.

[6] AZAD J，KANWAR V，KUMAR A.Effect of Network Topologies on Localization using DV-Hop based PSO Algorithm [C]//2021 5th International Conference on Trends in Electronics and Informatics （ICOEI）.Tirunelveli：IEEE，2021：40-45.

[7] 石琴琴，徐強，张建平.基于距离修正及灰狼优化算法对DV-Hop定位的改进 [J].传感技术学报，2019，32（10）：1549-1555.

[8] 李真，王帆，王冉珺.一种结合灰狼算法的粒子群优化算法 [J].计算机测量与控制，2021，29（10）：217-222.

[9] 吴之舟，张玲华.基于加权和RSSI测距的DV？Hop定位算法 [J].数据采集与处理，2021，36（6）：1217-1225.

作者简介：朱子行（1998—），男，汉族，安徽淮北人，在读硕士，研究方向：无线传感器网络定位方向;通讯作者：陈辉（1973—），男，汉族，安徽庐江人，副教授，硕士生导师，博士，研究方向：无线传感器网络，机器学习、物联网技术及应用。