基于改进粒子群优化的WSN定位算法

邴晓瑛，徐保国

（1.江南大学轻工过程先进控制教育部重点实验室，江苏无锡214122；2.江南大学物联网工程学院，江苏无锡214122）

基于改进粒子群优化的WSN定位算法

邴晓瑛1，徐保国2

（1.江南大学轻工过程先进控制教育部重点实验室，江苏无锡214122；2.江南大学物联网工程学院，江苏无锡214122）

针对无线传感器网络中经典DV-Hop定位算法第3阶段利用多边测量法计算未知节点位置存在较大误差的问题，提出了一种改进的粒子群算法来优化求解未知节点坐标。应用粒子群算法，引入自适应惯性权重，并对粒子速度差分变异，继续维持群体多样性，保证前期搜索的速度和后期搜索的精度，减小陷入局部最优的可能，寻得全局最优未知节点坐标。仿真结果表明，该算法在不增加网络成本的前提下，有效的提高了传感器节点的定位精度，拓宽了定位算法的应用范围。

无线传感器网络；DV-Hop定位；自适应惯性权重；粒子群；差分变异

无线传感器网络（Wireless Sensor Network，WSN）现已广泛应用于很多领域，而传感器节点的位置特别重要，是WSN应用的基础。现阶段定位算法主要分为两类，基于测距（Range-based）［1］的定位算法和基于非测距（Range-free）［2］的定位算法。其中DV-Hop［3］算法是典型的基于非测距的定位算法，该算法硬件成本较低、能耗较小，传输的信号受外界影响较小，并且能满足大部分实际应用对定位精度要求。

美国Rutgers University的Dragos Niculescu等利用GPS和距离矢量路由思想提出了DV-Hop算法［4］，定位精度较低。随着社会的发展需要，对许多应用的定位精度要求愈来愈高。许多学者对经典的DV-Hop算法进行了深入研究并改进，文献［5］利用粒子群算法改进了经典算法对未知节点坐标的求解过程，校正了未知节点的位置，减小了定位误差；文献［6］采用差分进化算法优化适应度函数，得到最优解，减小了定位误差；文献［7～8］分别用遗传算法、人工蜂群算法等寻求未知节点坐标，使其更接近实际坐标。

文中针对DV-Hop第3阶段计算未知节点位置产生较大误差的问题，结合粒子群算法和差分进化算法的特点，提出了一种带动态惯性权重，并利用差分进化算法变异粒子群速度的速度差分变异粒子群算法——PD-DV-Hop。实验结果证明，PD-DV-Hop能有效的减小定位误差，提高定位精度。

1　问题分析

1.1DV-Hop定位算法

根据DV-Hop定位算法第一、二阶段得到的未知节点D（x，y）与信标节点（x1，y1），（x2，y2），…，（x2，yn）最小跳数与平均每跳距离，求得相应节点间距离为d1，d2，…dn则

可表示为线性方程组AL+ε=b，ε为n-1维随机误差向量，其中L=（x，y）T，则最小二乘法求得方程的解为L=（ATA）-1ATb。

1.2误差分析

在经典DV-Hop定位算法中，dn是由未知节点到信标节点的估算平均跳距与最小跳数乘积等效替代，包含很大的误差，因此根据最小二乘法求得的未知节点坐标精度相对较低，为提高定位精度，我们将问题转化为优化估算距离dn的问题［9］。

设未知节点D（x，y）到信标节点A1，A2，…，An的实际距离为r1，r2，…，rn，相应的测距误差为ε1，ε2，…，εn，应满足式（2）可转换为

问题可化解为求解

当式（3）取得最小值时，未知节点的估计坐标最接近真实坐标，定位误差最小，本文采用改进粒子算法对式（3）进行寻优求解。

2　基于改进粒子群的DV-Hop定位算法

2.1粒子群算法

粒子群算法（Particle Swarm Optimization，PSO）是在鸟类捕食行为的基础上，在1995年由Kennedy和Eberhart提出的一种群体智能优化算法［10］。

假设D维搜索空间，粒子种群X=（X1，X2，…，Xn）数量为n，粒子速度和位置更新如下，

2.2DE算法

DE算法是对种群进行并行进化，是一种贪婪遗传算法，具有保优思想［11］。随机产生初始种群后，进行如下操作：

1）变异操作：

随机数r1，r2r3∈（1，2，…，n），n为种群数量，F为交叉因子。

2）交叉操作：

随机randb（j）∈［0，1］，randr（i）∈｛1，2，…D｝，交叉因子CR∈［0，1］。

3）选择操作：

f（x）为适应度函数。

DE算法原理非常简单，只有少量调整参数，鲁棒性较强，全局搜索能力较好［12］。

2.3粒子群算法改进

粒子群算法调整参数少，结构简单，但优化过程中得到的最优解被种群所有粒子共享，导致在某些特定位置容易发生粒子聚集现象，种群多样性在算法进化后期降低，易陷入局部最优。

因此，本文引入自适应惯性权重，并用差分进化算法变异粒子速度，提出了一种改进粒子群算法，既维持种群多样性，又保证全局最优解。

2.3.1自适应惯性权重的改进

式（4）中，粒子继承先前速度的能力受惯性权重ω影响。ω越大，全局搜索能力越强；ω越小，局部搜索能力越强。标准粒子群算法中惯性权重ω不变，算法收敛速度较快，但易在进化后期陷入局部最优，本文采用下式动态调整ω。

其中，ωmax，ωmin分别为ω初始值和最终值；k为当前迭代次数；Tmax为最大迭代次数。

由式（11）可以看出，粒子群算法进化前期ω变化较慢，取值较大，保证了全局搜索能力；后期ω变化较快，取值较小，提高了局部搜索能力。

2.3.2粒子群速度差分变异

综合考虑PSO算法和DE算法的优缺点，将差分变异的思想引入到PSO算法中，在PSO算法后期进化停滞时，差分变异粒子速度。粒子的变异时机由粒子的进化停滞步数t0确定，当t0＞T0（停滞阈值）时，粒子速度开始变异，并随机改变差分向量振幅，继续维持种群多样性。对粒子速度差分变异操作如下：

其中：Fmax，Fmin∈［0，2］为变异因子F的上下边界；k表示粒子的任一维度，以保证粒子至少有一个维度的速度发生了变异；r表示［0，1］间的随机数；CR为粒子变异概率即变异交叉因子。vid，v1d，v2d为v中随机选取的3个互不相同粒子的速度。

改进的粒子群算法既保证了进化前期的收敛速度，又提高了后期搜索准确性，增强了算法邻域搜索能力，有效的提升了算法进化后期的寻优速度和寻优能力，保证全局最优解的获取。

2.4PD-DV-Hop算法设计

改进粒子群算法通过对式（3）所示的适应度函数进行优化，得到最优解，具体实现过程如下：

1）初始化种群，规模为n；

2）计算粒子适应度值f（x，y），找到并记录Pi，Pg；

3）根据式（4）、（5）更新粒子位置和速度，比较更新前后的适应度值，更新个体极值和群体极值；

4）当粒子进化停滞次数t0＜T0（阈值）时，执行步骤3）；否则执行步骤5）；

5）产生一个随机数rand，若rand≤CR（交叉因子），根据式（8）、（9）更新粒子位置和速度；否则执行步骤6）；

6）随机选择群体粒子的任一维度进行变异交叉操作；

7）比较更新前后粒子适应度值，更新个体极值和群体极值；

8）判断当前迭代次数t＜Tmax（最大迭代次数）是否成立，若成立，则执行步骤5）；否则，输出最优解，结束。

3　仿真实验及结果分析

3.1仿真环境及参数设定

本文采用MATLAB仿真软件实现传感器节点定位算法。假设所有传感器节点均匀随机分布100 m×100 m在的正方形区域内。

为了能更直观的评价PD-DV-Hop算法的性能，将其分别与传统的DV-Hop算法，PSO改进的DV-Hop算法（PSODV-Hop），DE改进的DV-Hop算法（DE-DV-Hop）进行对比仿真实验，并比较分析实验数据。为确保结果的准确性，在每种测试条件下，对上述4种算法分别进行50次随机分布测试，取算术平均值。定位算法性能评价标准为归一化定位误差，其计算公式为：

其中，（xir，yir），（xie，yie）代表第i个未知节点的实际坐标和通过定位算法得出的估计坐标，R为网络通信半径，N为未知节点总数。

3.2仿真结果分析

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

图2表示了节点总数N=100，通信半径R=30 m，信标节点比例在5%～30%变化时，4种算法的节点定位误差图。由图可知，4种算法定位误差与信标节点比例整体上成反比。PDDV-Hop定位误差在信标节点各种比例下均小于其他3种算法，比传统DV-Hop算法的平均定位误差平均减少了约27%，比PSO-DV-Hop算法平均减少了约7%，比DE-DVHop算法平均减少了约5%。

3.2.2通信半径对定位精度的影响

图3表示了节点总数N=100，信标节点数为30，通信半径在15～40 m变化时，4种算法的节点定位误差图。由图可知，在节点总数及信标节点数一定的条件下，4种算法定位误差与通信半径整体上成反比。PD-DV-Hop定位误差在各通信半径下均小于其它3种算法，其平均误差相较于传统DVHop算法、PSO-DV-Hop算法、DE-DV-Hop算法分别减少了约18%、7%、6%。

图1　信标节点比例不同时的定位误差Fig.1Localization error with different beacon node ratio

图2　通信半径不同时的定位误差Fig.2Localization error with different communication radius

3.2.3节点总数对定位精度的影响

图4表示了信标节点数为30，通信半径R=30 m，节点总数分别取100，150，200，250，300，350时，4种算法的节点定位误差图。由图可知，在信标节点和通信半径一定的情况下，随节点总数的增大，4种算法的定位误差均逐渐减小。PDDV-Hop算法误差均小于其它3种算法，其平均误差相较于传统DV-Hop算法、PSO-DV-Hop算法、DE-DV-Hop算法分别减少了约28%、5%、4%。

图3　节点总数不同时的定位误差Fig.3Localization error with different total number of nodes

4　结论

文中提出了一种带自适应惯性权重的速度差分变异粒子群（PD-DV-Hop）算法来优化求解传感器未知节点坐标，较经典DV-Hop定位算法很大程度上提高了定位精度。通过对惯性权重的动态更新，以及对粒子速度的差分变异，有效的提高了种群的多样性，保证了全局最优。仿真实验结果表明，本文算法在不增加网络通信成本的前提下，有效的提高了传感器节点的定位精度。该算法是通过最小化与DV-Hop相关的适应度函数来优化定位算法，将改进粒子群算法与其他定位算法结合也是未来的一个研究方向。

［1］Chu Yan-Ling，Jau-Rong Tzeng，Cheng Yung-Pin，Sun Min-Te.Density-Adaptive Range-free Localization in Large-Scale Sensor Networks［C］//Parallel Processing Workshops（ICPPW），2012 41st International Conference on，2012：488-495，1249-1250.

［2］Maung N A M.Kawai M.Experimental evaluations of RSS threshold-based optimized DV-Hop localization for wireless ad-hoc networks［J］.2014，50（17）：1246-1248.

［3］Gayan S.Dias D.Improved DV-Hop algorithm through anchor poition re-estimation［C］//Wireless and Mobile，2014 IEEE Asia Pacific Conference on.2014：126-131.

［4］Niculescu D，NATH B.DV Based Positioning in Ad Hoc Networks［C］//Telecommunication Systems，2003：22（1/2/3/4）：267-280.

［5］黄艳，臧传治，于海斌.基于改进粒子群优化的无线传感器网络定位算法［J］.控制与决策，2012，27（1）：156-160.

［6］林雯，张烈平，王守峰.基于差分进化算法的无线传感器网络节点定位方法研究［J］.计算机测量与控制，2013，21（7）：2023-2026.

［7］刘彦隆，吕显朋，王相国.混合遗传算法在WSNs定位中的应用［J］.传感器与微系统，2014，33（2）：150-153.

［8］李牧东，熊伟，梁青.基于人工蜂群改进算法的无线传感器网络定位算法［J］.传感技术学报，2013，26（2）：241-245.

［9］周天绮，姜凤茹.基于MPSO-DV-Hop的无线传感器节点定位［J］.计算机工程与应用，2013，49（23）：52-55.

［10］Zhao Yan-Huang，Qian Zhi-Hong，Shang Xiao-Hang.PSO localization algorithm for WSN nodes based on modifying average hop distances［J］.Tongxin Xuebao/Journal on Communications，2013，34（9）：105-114.

［11］Das S，Suganthan P N.Differential evolution：A survey of the state of the art［J］.IEEE Transactions on evolutionary computation.2011，15（1）：4-28.

［12］乔俊飞，付嗣鹏，韩红桂.基于混合变异策略的改进差分进化算法及函数优化［J］.控制工程，2013，20（5）：943-947.

Localization method based on modified particle swarm optimization for wireless sensor networks

BING Xiao-ying1，XU Bao-guo2
（1.Key Laboratory of Industrial Advanced Process Control for Light Industry，Ministry of Education，Jiangnan University，Wuxi 214122，China；2.School of Internet of Things Engineering，Jiangnan University，Wuxi 214122，China）

An improved particle swarm algorithm to optimize the unknown node coordinates is proposed in order to solve the problem that when using the traditional DV-Hop algorithm the third phase error is too large.Introducing the adaptive inertia weight and difference change particle velocity in order to maintain diversity of the population，and ensure the pre-search speed and late-search accuracy to avoid falling into local optima，find out the global optimal unknown node coordinates.The simulation experimental results showed that，the proposed algorithm possesses of higher location precision without extra cost，broaden the application scope of localization algorithm.

WSN；DV-Hop localization；adaptive inertia weight；PSO algorithm；differential mutation

TN92

A

1674－6236（2015）22-0143-04

2015-02-10稿件编号：201502089

国家自然科学基金面上项目（21276111）；国家自然科学基金青年基金（21206053）；浙江省自然科学基金重大专项（2011C12033）

邴晓瑛（1989—），女，山东青岛人，硕士。研究方向：无线传感器定位算法。