混沌粒子群和差分进化优化的RSSI质心定位算法

孙 谋，曾子维，王 刚

（辽宁科技大学 计算机与软件工程学院，辽宁 鞍山 114051）

无线传感器网络（Wireless sensor network，WSN）是由大量传感器以自组织或者多跳的方式构成的无线网络，具有低功耗、可扩张性强等优点。传感器类型众多，在军事作战、环境监测、室内监控等领域具有广阔的应用前景。然而在真实环境中抛洒大量带有GPS定位的节点会导致成本过高，并且传感器的使用环境大多较为苛刻，无法保证所有的传感器都带有GPS 定位。因此，节点的定位技术成为WSN领域的关键技术之一，而提高节点的定位精度则成为WSN 领域中的一大热点。

无线传感器网络定位大致分为两类，基于测距的range-based 定位与无需测距的range-free 定位［1］。range-based定位要测量节点间的绝对距离，再利用三边测量、极大似然估计［2］等方法来计算未知节点的位置，包括 TOA［3］、TDOA［4］、AOA 等算法，算法的定位精度较高，但相应的功耗和成本也较大。range-free定位利用节点的估计距离实现定位，主要包括质心、DV-HOP［5］、Amorphous、MDSMAP［6］等定位算法。range-free定位算法虽然在定位精度上不如range-based定位算法，但成本较低，且定位精度已经能够满足大部分应用的需求。

目前，国内外学者对于传感器网络中的节点定位问题已经取得了诸多研究成果。Singh等［7］提出一种新的接收信号强度（Received signal strength indicator，RSSI）方法，通过引入噪声因子进行参数模型构建，来减小定位误差。Hyunmin Cho 等［8］将 PDR（Pedestrian dead reckoning，PDR）定位与无线传感器网络室内定位方法结合，来降低非直瞄定位误差。国内许多学者将智能优化算法引入节点定位技术中，并与range-free 定位方法结合，进一步提高了节点定位精度。王改云等［9］将粒子群算法与模拟退火算法结合，并应用到基于RSSI 的质心算法中，具有较高的定位精度。李腾宇等［10］将基于RSSI的加权质心算法与遗传模拟退火方法结合，降低了传感器网络中的平均定位误差。

传统的质心定位算法的定位原理是将多个锚节点连接起来组成一个多边形，多边形质心的位置即为估算的未知节点的位置，即未知节点的坐标为多个锚节点坐标求和取平均值。质心算法实现容易，耗费成本较低，但定位精度也较低。所以在现有研究的基础上，本文将混合粒子群（Particle swarm optimization，PSO）与差分进化算法（Diffe-rence algorithm，DE）以及基于RSSI 测距的质心算法相结合，建立以未知节点坐标为参数的适应度函数；并利用混沌搜索的随机性、遍历性以及动态变化的惯性权重来提高算法的搜索能力，进一步减小节点的定位误差。

1 RSSI加权质心定位算法

1.1 RSSI测距模型

无线传感器网络中的信号传播模型主要包括3 种：自由空间传输模型（Free space propagation model）［11］、对数-距离损耗模型（Log-distance path loss model）［12］、哈他模型（Hata model）［13］。自由空间传输模型主要应用于理想环境，发射信号端与接收信号端之间不存在路径损耗。哈他模型应用于城市环境，频率也有所限制。所以本文采用更接近真实环境的对数-距离损耗模型，该模型将RSSI（Received signal strength indication）值转化为距离。RSSI 值越大，代表两个节点间的距离越近。对数距离损耗模型表达式

式中：PL(dab)代表距离ab之间的路径损耗；d0是锚节点间的参考距离，通常取1 m；λ是路径损耗因子，根据环境的不同，取值不同；σ是正态分布因子。

1.2 加权质心定位原理

传统的质心算法是由距离未知节点最近的几个锚节点（xi，yi）组成一个多边形，多边形的质心即为估算所得的未知节点的位置

质心算法实现简单，但未知节点的定位容易受到周围锚节点数量的影响。周围的锚节点越多，定位精度越高。反之，定位精度则较低。

为了防止单个锚节点对未知节点的位置测量影响较大，加权质心算法［14］以锚节点与未知节点的距离的倒数为权值，距离未知节点越远的锚节点对于未知节点的定位影响越小。pi是锚节点的权值，未知节点的坐标为

2 PSO-DE-RSSI优化算法

2.1 适应度函数

适应度函数是节点定位技术中的误差评价标准。为了减小定位误差，需要多次进行循环迭代求出适应度函数的最小值。本文适应度函数的构建选取距离未知节点最近的三个锚节点（xi，yi）（i=1,2,3），未知节点的估计位置为（x，y），锚节点与未知节点的距离为

根据RSSI测距得到的三个锚节点与未知节点的真实距离为da、db、dc，则适应度函数的定义为

f值越小，节点定位精度越高。

2.2 优化算法步骤

粒子群算法参数设置简单，搜索速度快，但在种群规模大，搜索空间维度高时，种群中个体的差异会随着时间的推移而减小，从而陷入局部最优解无法跳出。差分进化算法会随机选择种群中的个体来构造差分向量，将产生的变异个体与原始种群中的个体进行交叉操作构造后代，并选择种群中适应度较好的个体来更新种群。粒子群算法进行快速寻优后，可以通过差分进化算法继续进行优化，使得陷入局部最优的个体快速跳出当前区域，进而探索全局最优解。

本文采用的PSO-DE-RSSI 算法，先通过RSSI测距找到与未知节点最近的三个锚节点，利用三个锚节点构造三角形，并设置群粒子在三角形的质心位置；再将粒子群与差分进化算法相结合并进行混沌搜索，去计算未知节点的位置。PSO-DERSSI算法的步骤：

步骤1：初始化种群，设置种群规模与最大迭代次数，初始化粒子的位置x(t)与速度v(t)，计算种群中每个粒子的适应度值。

步骤2：更新粒子的速度与位置

步骤3：计算种群的平均适应度，将种群中适应度值较高的个体执行差分进化算法中的变异、交叉、选择操作。

变异：在每次迭代中随机生成三个染色体xa(t)、xb(t)、xc(t)，将其中两个染色体的差值乘以加权因子F，再加到第三个染色体上，产生变异个体Vi(t)

交叉：将第t代的种群个体xij(t)与变异个体按照式（8）产生交叉个体，CR是交叉概率

选择：选择父代个体与交叉后的种群中适应度较小的个体

步骤4：将原始种群中低于平均适应度的个体，与经过差分进化算法更新后的种群进行合并。

步骤5：在每代的最优解附近进行混沌搜索，将混沌搜索后得到的个体与每代最优解进行适应度比较，取适应度最优的个体。

步骤6：判断算法是否满足最大迭代次数，如果满足则比较每代最优解的适应度值，取适应度值最低的个体作为全局最优解输出，否则返回步骤2继续进行迭代。

算法流程如图1所示。

3 算法的改进

3.1 惯性权重的修改

惯性权重是粒子群算法中评价粒子速度的重要参数，惯性权重越大，粒子的速度越快，粒子的全局搜索能力就会越强。惯性权重越小，粒子的速度越小，粒子就会具有较强的局部搜索能力。

惯性权重不变的粒子群算法虽然具有较快的收敛速度，但后期容易陷入局部最优。Shi等提出了惯性权重线性递减的策略［15］

式中：ωmax和ωmin分别代表惯性权重的最大值和最小值，一般分别取0.9和0.4；k是当前迭代次数；N是最大迭代次数。

本文在惯性权重的递减公式中加入正态函数，对式（10）进行改进，让惯性权重按照正态函数递减的方式进行变化，使前期的惯性权重变化较快，算法的收敛速度降低，容易获得局部最优解；使后期惯性权重变化较慢，提高算法的收敛速度。

式中：a，b为常数，可根据算法的迭代次数选择不同的值。

加入ωmin可以保证惯性权重取值为正数，并在0.4～0.9 之间变化。设置均值为0，将标准正态函数的右半部分作为惯性权重的变化趋势，如图2所示。曲线前期是凸函数，后期是凹函数，从而保证算法前期的局部收敛能力与后期的全局收敛能力。

3.2 混沌机制

混沌运动是一种非随机运动，存在于非线性动力系统中，具有随机性和遍历性。混沌运动的遍历性可以帮助算法避免落入局部陷阱。目前，混沌技术已引入到优化算法中，混沌系统动力学模型种类繁多，选用较为经典的Logistic方程［16］

本文在粒子群算法中用混沌变量代替随机变量，并在算法每代最优解附近继续进行混沌搜索，利用混沌变量的随机性与遍历性来提高算法的搜索能力。原始的粒子群算法速度更新为

式中：ω是惯性权重；c1和c2是学习因子；r1和r2是（0，1）之间的随机数；pt是个体当前搜索到的最优解；pg是群体当前搜索到的最优解。

加入混沌搜索［17］后，粒子速度更新为

式中：cr根据式（12）计算。

为了提高算法的深度搜索能力，本文将粒子群与差分进化算法结合后，再在每代的最优解附近进行精细搜索

式中：n是在每代最优解附近进行混沌搜索的次数；Cn是混沌变量；xbest是每次迭代的最优解；α是方向因子，让xn在正反两个方向搜索，提高算法的随机性；rand是在（0，1）中均匀分布的随机数。

4 仿真实验与结果分析

为了验证本文提出的PSO-DE-RSSI算法的性能，将本文提出的算法与其它算法通过MATLAB仿真实验比较算法的优劣。仿真实验中，在1 000 m×1 000 m的正方形区域内随机抛洒1 000个传感器节点，包括未知节点与锚节点。节点的分布如图3所示。

锚节点周期性地向周围环境发送自身信息，其它节点根据接受的信号强度判断自身与锚节点之间的邻居关系。节点的邻居关系如图4所示。

无线传感器网络通常采用平均定位误差作为评价标准。节点的平均定位误差是传感器网络中所有未知节点的定位误差的平均值，定义为

式中：N是未知节点的个数；R是节点的通信半径；（x，y）是节点的真实位置；（xi，yi）是节点的估计位置。

改变锚节点的个数与锚节点的通信半径，对比本文PSO-DE-RSSI算法与普通的粒子群算法和基于RSSI的加权质心算法的节点定位误差。节点的参数设置：节点个数300、种群粒子个数20、惯性权重初始值0.9、学习因子2、最大迭代次数500、变异概率0.5、交叉概率0.6。

图5是锚节点半径为210 m，锚节点个数为90个时的节点定位误差图。图中的实线代表估计的未知节点的位置与节点真正所在位置的距离。实线越短，定位的误差越小。

图6 是锚节点的个数为90 时，通信半径与定位误差的关系。随着通信半径的增大，三个算法的平均定位误差都是呈下降的趋势。因为锚节点的通信半径越大，未知节点周围的锚节点也就越多，更有利于节点定位，也说明锚节点的通信半径影响着节点的定位误差。通信半径相同时，与粒子群算法与基于RSSI的加权质心算法相比，PSODE-RSSI 算法的平均定位误差最低。这是因为该算法将差分进化与粒子群算法结合，加强了算法的全局寻优能力，避免算法陷入局部最优解的陷阱，该算法可以提高节点的定位精度。

图7 为锚节点的个数与平均定位误差的关系。随着锚节点个数的增多，三个算法的平均定位误差都在减小。说明锚节点的个数越多，定位精度越高。而本文提出的算法的平均定位误差比基于RSSI的加权质心定位算法下降了10%～15%，比普通的粒子群算法下降了6%左右。

5 结 论

本文将智能优化算法与基于RSSI测距的质心算法相结合，来减小节点的定位误差。粒子群算法虽然搜索速度快、效率高，但容易陷入局部最优，将差分进化算法与粒子群算法相结合，通过不断迭代计算，保留优良个体，淘汰劣质个体，引导搜索向全局最优解逼近。并在此基础上加入动态惯性权重与混沌搜索，进一步保证算法在寻优性能较好的基础上拥有更小的定位误差。实验结果表明，与基于RSSI 的加权质心算法和粒子群算法相比，本文提出的PSO-DE-RSSI 算法可以在一定程度上提高节点的定位精度。