基于粒子群的DV_Hop算法优化

周 涛 蒋占军 路宇挺 杨永红

(兰州交通大学电子与信息工程学院 甘肃 兰州 730070)

0 引 言

节点定位技术是无线传感器网络(Wireless Sensor Networks，WSN)的关键支撑技术之一，其基本思想是在目标区域内已知信标节点信息的基础上，通过一定的定位算法获取未知节点的信息[1]。该技术广泛应用于军事侦查、石油管道泄露监测、地震救灾等诸多领域的事件监测系统中，是社会生产信息化进程中重要的组成部分。

WSN中的节点定位算法通常分为两类，分别是基于测距(range-based)和非测距(range-free)[2]。其中，基于测距的定位算法是利用工具仪器测量得到已知节点与待测节点之间的位置与角度信息，进而通过距离运算预测出未知节点的位置；非测距的定位算法是利用WSN内部信标节点与邻居节点之间的连通性实现对未知节点的定位预测。基于测距的定位算法虽然定位精度高，但是对节点本身的硬件设备性能要求较高，不易于在WSN环境中广泛部署；非测距的定位算法相较测距的定位算法来讲，无需硬件设备支持且成本较低，适于大规模在WSN环境中部署，但缺点是定位精度较低。

常见的非测距类算法有质心定位算法、APIT算法、DV_Hop算法等。其中，质心算法是通过计算多边形的所有顶点的平均值坐标来估算未知节点的坐标，其主要优点是无需知道未知节点与信标节点之间的距离，缺点是定位精度易受到节点分布和密度影响。APIT算法是将未知节点相邻的信标节点任选三个构成一个三角形，这样将构成多个三角形；然后，利用数学公式求解这些三角形交叉区域的质心坐标，得到该质心坐标当作待测节点的估计坐标。该算法的优点是定位精度较高，但实现复杂且易受节点分布密度的影响。

DV_Hop算法的基本思想是在取得信标节点最小跳数与平均跳距的情况下，通过计算得出未知节点的估计坐标。DV_Hop算法最大优势是部署简单且硬件设备要求低，易于广泛部署[3]，但是节点定位精度较差。目前对该算法的研究主要从优化距未知节点最近的信标节点的最小跳数值和校正锚节点平均跳距两个方面来减小定位误差。其中双通信半径DV_Hop算法就是通过优化节点间最小跳数，得出较为精确的跳数值，提高了对未知节点的定位精度。然而，当双通信半径DV_Hop采用三角测量法或者极大似然估计法计算待测节点坐标值时，还具有定位精度不高的缺陷。

为了提高待测节点的定位精度，同时节约WSN节点部署的成本。近年来有学者将遗传算法(Genetic Algorithm)、模拟退火法(Simulated Annealing)、粒子群优化算法(Particle Swarm Optimization,PSO)、蚁群算法(Ant Colony)等生物智能优化算法应用到对待测节点定位精度的优化中。其中，遗传算法具有强容错性和并行性，但计算复杂不易大规模部署[4]；模拟退火算法虽然具有计算简单，能够优化多维数据的优势，但不易收敛容易陷入局部最优解[5]；蚁群算法能够实现对最优路径的探索，具有节约节点能量、平衡网络负载的效果，故经常用在WSN路由协议中，但在WSN节点定位方面较少[6]。相比于其他算法，粒子群算法更易实现、收敛速度快、计算量较小，且易于大规模部署，所以受到大多数研究者青睐[7]。

本文主要研究在原DV_Hop算法的基础上，信标节点在平均跳距的计算与广播阶段先后使用两个不同的通信半径广播自身位置，形成双通信半径DV_Hop算法，接着引进一个修正因子来校正平均跳距，精确节点间最小跳数值；然后利用基于惯性权重的线性优化和学习因子的线性加权改进的粒子群算法代替三角测量法或者极大似然估计法，对校正后的双通信半径DV_Hop算法中待测节点产生的误差进行优化使其达到最小值，从而提高待测节点的定位精度。

1 DV_Hop算法误差分析及其改进

1.1 DV_Hop算法原理及误差分析

DV_Hop算法实现分为距离矢量交换、平均跳距的计算与广播、定位计算3个阶段。在距离矢量交换阶段中，当信标节点的邻居节点在通信半径R之内时，就记该邻居节点与信标节点的跳数为1[8]。然而，这样不管信标节点与邻居节点之间的实际距离，将它们之间的跳数值取为1，会导致DV_Hop算法的定位精度下降，同时也使算法的稳定性下降。除此之外，由于两节点之间所求出的估计距离是若干个连续跳段的距离，并不是直线距离，存在跳距误差。在两节点跳数不断增加的情况下，节点之间的累计误差将逐渐增大。

双通信半径DV_Hop算法采用R、0.5R两种通信半径广播来优化节点间的最小跳数。如图1所示，记N个节点为si，i=1,2,…,N，其中sp为信标节点，在平均跳距的计算与广播阶段sp先以半径R进行广播，将在R范围内的节点与sp间的跳数记为1；然后再以通信半径0.5R进行广播，将0.5R内的节点与sp间的跳数更新为0.5，记节点si与信标节点sp之间的跳数为hip，距离为rip，则：

图1 DV_Hop算法节点分布图

通过该方法能够减小相同跳数实际距离相差较大而存在的误差，使信标节点与未知节点之间的跳距更加接近真实值，优化了信标节点间的跳数，使得到的最小跳数值更加精准。

1.2 基于修正跳距的双通信半径DV_Hop算法

双通信半径DV_Hop算法在计算未知节点与信标节点之间估计距离时，在目标区域内待测节点与距其环境条件和位置关系最近的信标节点相似。从理论上讲，待测节点将与其所处环境条件与位置关系最近的信标节点的平均跳距作为自身平均跳距，来估算与目标信标节点之间的距离是可行的。但是WSN节点分布不均匀且位置关系复杂多样、节点灵活性低。如果仅仅使用距待测节点最近的信标节点的平均跳距，来估算与目标信标节点之间的距离，会存在较大误差，获取的待测节点位置精度较低。

在WSN中，除了利用信标节点的坐标计算出不同信标节点之间的真实距离外，还可以利用信标节点的真实距离与平均跳数之间的关系，在信标节点计算完自身平均跳距之后，根据平均跳距计算出与其他信标节点之间的估计距离。基于此考虑，如图2所示，假设sm是与待测节点si距离最接近的信标节点，Dip和Dmp分别为sm和si与sp之间的平均距离，hmp为sm和sp之间的最小跳数值。在双通信半径DV_Hop算法的第二阶段中引入修正因子Dmp/hmp来校正优化待测节点与目标信标节点间的平均跳距，即：

(1)

从而使待测节点与信标节点的平均跳距根据距其最近的信标节点的平均跳距进行自适应性调整。

图2 跳距修正原理

将校正优化后的平均跳距用于估算待测节点与其他信标节点之间的距离，与原DV_Hop算法相比，基于修正跳距的双通信半径DV_Hop算法除了优化节点间的最小跳数外，引入的修正因子使待测节点根据距离它位置与环境条件最近的信标节点进行自适应性调整，可以提高DV_Hop算法的定位精度。

2 DV_Hop算法优化设计

2.1 粒子群算法原理

粒子群算法是一种智能优化算法，其基本原理是使用一群一定数量的粒子，在目标区域内通过彼此间的协作和信息资源共享，在具体问题的可行解中搜索满足条件的解，并选择最优的或者相对最优的解作为问题的解[9]。

在粒子群算法中，粒子在目标区域内寻找最优解的过程中，需要控制粒子的移动方向和快慢以及最优位置，分别用速度矢量和位置矢量表示。其中，位置矢量分为局部最优位置pbest和全局最优位置gbest。

粒子之间除了时刻更新自己的位置之外，在迭代寻优的空间中用一个相关的适应度函数来衡量一个粒子位置的好坏以及控制算法在寻优过程中粒子的运动基准。

基本PSO算法具体过程如下：

假设某粒子群中有N个粒子，寻优空间是一个D维空间。该粒子在目标区域中寻找pbest和gbest的过程中，第i个粒子的位置向量记为：

Xi=(xi1,xi2,…,xiD)i=1,2,…,N

(2)

第i个粒子在初始寻找pbest的过程中运动速度矢量记为：

Vi=(vi1,vi2,…,viD)i=1,2,…,N

(3)

第i个粒子在目标区域迭代寻优过程中截止到某个时间，达到的局部最优位置记为：

pbest=(pi1,pi2,…,piD)i=1,2,…,N

(4)

整个寻优过程中，所有粒子在某一时刻达到的全局最优位置记为：

gbest=(pg1,pg2,…,pgD)i=1,2,…,N

(5)

每个粒子在迭代寻优过程中不同时刻的速度和位置更新表示为：

(6)

(7)

式中：ω称为粒子的惯性权重，主要作用是通过控制迭代过程中粒子向最优解靠拢的快慢、均衡迭代效率和寻优精度，增强粒子在下一时刻的搜索能力；c1、c2称为学习因子，主要作用是控制粒子的寻优路径，体现了粒子对速度更新的影响；λ1、λ2取[0,1]范围内的均匀随机数。

最后，所有粒子在经历过pbest后整体最终达到的gbest为：

(8)

2.2 优化惯性权重和改进学习因子的PSO

DV_Hop算法求未知节点在监控区域中的坐标问题，从数学的角度，可以转化为在目标区域中求坐标最优解的优化问题。PSO的主要优势就是在目标区域内寻找最优位置时，粒子通过不断的速度和位置迭代的更新，迫使大量的粒子能够达到最优化的全局位置或者相对的局部最优位置。

然而，PSO的缺点就是在目标区域内迭代收敛速度不能动态调整，在运算搜索中会陷入搜索速度慢、全局最优解位置变化很小的过程中[10]；在搜索后期寻优粒子极易陷入局部极小值、迭代循环和出现多峰函数早熟收敛等问题，这些会给求解待定位节点最优坐标带来误差，导致最优解不准确等问题。针对PSO自身存在的局限性问题，本文采用一种基于线性优化惯性权重与改进学习因子使两者同步变化的PSO优化修正跳距的双通信半径DV_Hop算法[11-13]。从决定PSO性能的3个关键参数ω、c1、c2对PSO进行优化和改进，避免粒子过早地陷入局部最优位置和多峰函数早熟收敛，从而提高粒子全局寻优的能力，提高粒子的寻优精度。

(1) 惯性权重ω的线性优化。为增强粒子在寻优过程中的速度，在较短时间内寻找到最佳的最优解，引入如下的线性优化权重公式：

(9)

式中：f表示节点的适应度，favg表示监控区域内平均适应度，fmin表示最小适应度。通过仿真实验表明，当ωmax=0.9，ωmin=0.4时，PSO算法的寻优精度较高。即，线性优化的惯性权重ω取值为：

(10)

(2) 学习因子的线性加权改进。从控制粒子在目标区域内寻找最优位置对当前迭代速度影响的角度出发。本文提出通过改进学习因子即增加一个逃逸因子来控制局部迭代循环，通过粒子进行中心学习，生成中心学习解，来提高种群多样性。

(11)

式中：cend为线性加权改进的学习因子，用于控制局部迭代循环：

(12)

(3) 适应度函数。为了更好地度量PSO算法优化双通信半径DV_Hop改进算法粒子在寻找最优解过程中位置的好坏，引入适应度函数。同时，为了减少待测节点到目标信标节点之间距离的累计误差给适应度函数带来的影响，引入一个权重因子ωip。

本文采用如下适应度函数：

(13)

2.3 算法优化步骤

基于粒子群的DV_Hop算法优化的流程如图3所示。

图3 基于粒子群的DV_Hop算法优化流程图

具体步骤如下：

(1) 网络初始化阶段。在待定位区域内，将WSN中的各节点随机部署，并启动定位过程。

(2) 启动双通信半径DV_Hop法。信标节点先以通信半径R进行广播，将位于R内的信标节点与邻居节点之间的跳数记为1，生成邻居节点组1。然后，信标节点以通信半径0.5R广播，将位于0.5R内的信标节点与邻居节点之间的跳数记为0.5，生成邻居节点2。

(3) 更新计算阶段。由于生成的邻居节点组2是邻居节点组1的子集。将组2中与组1中相同的邻居节点的最小跳数更新为0.5，其他邻居节点的最小跳数仍旧保持为1。

(4) 通过步骤(2)和步骤(3)，计算得到最小跳数hi与估算距离di。

(5) 设定粒子群的数目，并且初始化迭代过程中的各类参数。

(6) 根据式(10)和式(12)更新粒子的ω、c1、c2。

(7) 根据式(2)和式(3)更新粒子的寻优区域中位置xi和迭代速度vi。

(8) 根据式(13)计算粒子的fitness值，更新粒子的最优值pbest与gbest。检查算法是否达到迭代次数上限值，如果达到，算法退出；否则返回步骤(6)。

3 仿真及结果分析

3.1 仿真环境及分析

仿真参数设置为：粒子群个体数量为20个，粒子在100 m×100 m区域的2维区域迭代优化；最大迭代次数20次，ω根据式(10)进行动态变化，学习因子c1=c2=c3=2，各算法的最终定位误差都取50次重复仿真的平均值。

在节点随机部署的情况下，从总节点数、锚节点数、通信半径三个方面，对原DV_Hop算法、双通信半径DV_Hop算法与加修正因子的改进算法以及本文改进算法进行对比和分析。定义待测节点Si的误差公式为：

(14)

3.2 节点个数对定位误差的影响

设置锚节点的通信半径R为25 m，总节点个数从50开始，每50个节点线性地递增到300，锚节点比例为20%。变化曲线如图4所示。

图4 不同节点个数的平均定位误差

从图4可以看出，在WSN监测区域内总节点个数线性地增加情况下，平均定位误差都在不断降低。出现这种情况的主要原因是节点数量的不断增多，使得WSN环境中孤立的节点减少，锚节点与未知节点之间连通的节点增多，未知节点的平均定位误差降低。

从整体上看，在节点数量一定的条件下，这三种改进算法与原DV_Hop算法相比都有很大的改进。双通信半径DV_Hop改进算法与未加修正因子之前，定位精度更加准确，误差更小。本文改进算法比其他两种改进算法的平均定位误差都要低。这就说明本文改进算法对提高目标未知节点的定位精度方面作用还是比较明显。同时，当总节点个数增加到一定程度时，平均定位误差变化幅度很小，表明本文改进算法的鲁棒性较好[12]。

3.3 锚节点个数对定位误差的影响

设置总节点数为100个，通信半径R为25 m，锚节点个数从5%开始，每5%个锚节点线性地逐渐递增到50%，这4种算法的平均定位误差变化曲线如图5所示。

图5 不同锚节点定位误差

从图5能够看出，在监控区域内不断增加锚节点比例地情况下，这4种算法的平均定位误差不断减小。当锚节点在目标区域内达到某一程度时，待测节点的定位幅度偏差变化都比较小，并且逐渐趋于稳定。由于在WSN环境中，当锚节点数量较少时，孤立节点个数较多，节点彼此之间连通的数量较少，并且估算距离存在较大的误差累计等，影响了节点的定位精度；当锚节点个数增多时，网络环境中节点之间连通的个数较多，估算距离误差累计较低，节点偏差逐渐减小，节点定位精度较高。

特别地，当锚节点比例为25%时，双通信半径DV_Hop改进算法相比未加修正因子的双通信半径DV_Hop算法在未知节点的平均定位误差精度上提升了11%左右；与原DV_Hop算法的平均定位误差相比增加了14%左右。而本文改进算法相比双通信半径DV_Hop改进算法与未加修正因子的双通信半径DV_Hop算法的定位误差分别提升了18%、29%左右。从整体上来看，本文对于采用的粒子群算法对加修正因子的双通半径DV_Hop算法的优化使锚节点在数量达到一定的程度的情况下，对于待测节点的定位更加准确，效果也更加明显，同时能够减少无线传感器节点定位成本[14]。

3.4 通信半径对节点定位误差的影响

设置WSN监控区域内节点个数为100，锚节点的通信半径R从15 m开始，规则地递增到40 m，锚节点为20，这4种算法的平均定位误差变化曲线如图6所示。

图6 不同通信半径节点误差

从图6可以看出，在通信半径R规则地增大的情况下，这4种算法的平均定位误差也降低，只不过降低的幅度有的大、有的小。特别地，当通信半径大于30 m时，信号辐射半径地增大，增加了节点之间的通信跳数和节点之间的累计误差，导致原DV_Hop算法的平均定位误差逐渐上升，节点定位精度下降。同时，在该仿真试验中，可以看出双通信半径 DV_Hop改进算法与未加修正因子的该算法，平均定位误差变化趋势基本相同。而当通信半径大于30 m时，本文改进算法变化趋势相对稳定，增减幅度比较小，说明粒子群优化算法对此时节点的定位误差敏感度降低。

4 结 语

本文首先对DV_Hop算法的定位原理及误差产生的原因进行了分析，针对DV_Hop算法在计算节点跳距时，随着节点数目的递增节点间的误差累计增大的问题，在平均跳距的计算与广播阶段信标节点，让信标节点先后使用两个通信半径广播自身位置信息，同时加入了一个修正因子来校正平均跳距，精确了节点间的最小跳数值，得到更精确的未知节点坐标。接着对校正后的DV_Hop算法在求解待测节点坐标时存在误差等问题，采用基于线性优化惯性权重与线性加权改进的学习因子同步变化的粒子群算法优化待测节点产生的累计误差，减小了节点的平均定位误差。最后，通过选取合适的参数变量，对本文提出的改进算法从三个方面进行仿真验证。结果表明，本文优化算法的定位精度及鲁棒性更加良好。