基于改进花授粉算法的RSSI定位方法*

刘国繁， 肖 勇

(1.湖南工程学院 电气信息学院，湖南 湘潭 411104； 2.湘潭大学 信息工程学院，湖南 湘潭 411105)

0 引 言

在测距误差客观存在情况下，如何获得更接近实际未知节点位置的估计位置坐标并提高定位算法的稳定性，是无线传感器网络节点定位算法的主要考虑点。接收信号强度指示(received signal strength indication,RSSI)定位算法大致可分为两个阶段，第一阶段，获得未知节点和锚节点之间的RSSI距离测量值，第二阶段，通过节点之间的距离约束关系求解未知节点位置。大多数RSSI定位算法在第二阶段通常使用最小二乘法[1]进行未知节点坐标求解。然而，在实际应用中发现，测距误差对最小二乘解的精度影响很大，当测距误差较大时，其定位精度较低，不能满足定位要求。近年来，学者们考虑将定位问题转化为约束优化问题，采用群智能优化算法进行优化求解，如粒子群优化(particle swarm optimization,PSO)算法[2]、蚁群算法[3]、蝙蝠算法[4]等，将求解的最优值作为未知节点位置坐标的估算值。花授粉算法(flower pollination algorithm,FPA)算法[5]是2012年由英国剑桥大学杨新社学者提出一种新型启发式群智能优化算法，该算法结构简单、参数较少、无需梯度信息，具有较好的全局搜索和局部搜索平衡性。在2013年，杨学者利用该算法求解多目标求解问题[6]，验证了花授粉算法相较于粒子群算法、遗传算法等其他群智能算法拥有更好寻优性能。但同时花授粉算法存在易陷入局部最优值、后期收敛速度慢等不足。为获得更精确和更稳定的定位结果，本文提出一种基于改进花授粉算法的RSSI定位方法。

1 RSSI优化问题描述[7]

1)根据信号传播衰减模型即可估算出两节点之间RSSI距离测量值。本文采用对数—常态分布模型[8]

(1)

(2)

式中Pr(d)为信号接收强度；单位距离d0的信号接收强度为P(d0)，一般取d0=1 m；np为信道衰减指数，不同环境下np不同，dij为节点i和j之间通信距离；Xσ为高斯分布噪声，通常采用正态分布Xσ～N(0,σ2)表示。

2)利用极大似然法构建RSSI求解约束条件。假设在网络中存在N个锚节点，坐标分别表示为B1(x1,y1)，B2(x2,y2)，…，BN(xN,yN)，未知节点为P(x,y)，锚节点与未知节点P之间的RSSI距离测量值，分别表示为d1，d2，d3，…，dN，假设锚节点与未知节点之间实际距离分别为r1，r2，…，rN，测距误差分别为e1，e2，…，eN，则满足。|ri-di|

(3)

3)估算未知节点位置坐标。采用群智能算法进行未知节点位置求解，通过个体的适应度值判断个体所在位置的优劣并不断调整搜索方向进行迭代求精

(4)

式中m为锚节点个数。花粉位置坐标为(x，y)，锚节点坐标为(xi，yi)，di为未知节点到锚节点的RSSI距离测量值。当求得最优解使得fitness(x,y)取得最小值时，节点定位总误差最小，此时的坐标(x,y)则为最优值，即最接近未知节点真实位置坐标。

将RSSI定位问题转换为RSSI优化求解问题，在一定程度上可抑制测距误差对定位精度的影响。如式(4)所示，RSSI约束优化求解问题为非线性问题，采用传统数学方法难以求解，本文考虑采用改进后的花授粉算法求解。

2 改进花授粉定位算法

2.1 花授粉算法

为更好模拟全局授粉和局部授粉过程，做出假设[9]：1)生物异花授粉视为全局授粉过程，其中携带花粉的传粉生物通过Levy飞行[10]进行传播；2)非生物自花授粉是局部授粉过程；3)花的常性被认为是繁衍概率，其中繁衍概率与参与授粉的两朵花之间的相似性成比例关系；4)转换概率p∈[0,1]控制全局授粉和局部授粉之间的转换。考虑实际环境中花授粉的临近性及其它因素影响，p值设定需略偏向于局部授粉，因此p值一般设定在[0.6,1]区间。在文献[10]中提出，p值设置为0.8时花授粉算法取得较好表现性能。

根据假设(1)和假设(3),全局授粉过程可表示为

(5)

(6)

式中Γ(λ)为标准的伽马函数[11]。

根据假设(2)和假设(3),局部授粉过程可表示为

(7)

针对花授粉算法易陷入局部最优值、在迭代后期收敛速度慢、缺乏变异机制的问题，分别从步长权重、局部变异两方面进行改进，增加种群的多样性，提高算法的全局寻优能力并避免种群个体陷入局部最优。

2.2 步长的改进

花授粉算法在全局授粉部分虽然因Levy飞行机制的随机性和较大移动步长能够在一定程度上避免个体陷入局部最优，但是缺乏自适应性。通过优化算法原理分析可知，在算法初期，需求较大的步长使算法快速收敛到最优位置附近，同时避免个体陷入局部最优；算法后期，需求较小步长进行精准迭代以获得更高收敛精度，并加快收敛速度。本文对步长因子加以一个根据迭代次数变动的动态权重w进行合理分配。w设计公式如下

w=wmax-(wmax-wmin)t/T

(8)

式中wmax和wmin为最大权重和最小权重，t为当前迭代次数，T为最大迭代次数。分析可知，权重系数为递减函数，当t=0时，w=wmax；反之，当t=T时，w=wmin，因此可以很好地根据迭代次数在算法的前后期进行步长的分配。经过实验对比，本文设置wmax为0.96，wmin为0.36。

改进后的全局授粉过程如下所示

(9)

2.3 局部变异改进

花授粉算法的局部授粉的位置更新过程只抽取两个随机花粉位置差的信息，在搜索最优解的过程具有盲目性和不定向性。在此，首先考虑将历史全局最优值引入到局部授粉过程中，产生一种定向位置更新，可表示如下

(10)

同时考虑到FPA缺乏变异机制，在迭代过程中难以跳出局部最优。考虑引入高斯变异策略[12]对陷入局部最优最优个体执行变异操作。高斯变异就是在原有个体上加以一个服从高斯分布的随机扰动向量来取代原先个体

xi=xi+bN(0,1)xi

(11)

式中b=(T-t)/T，t为当前迭代次数，T为最大迭代次数，N(0，1)服从μ=0，σ2=1的标准高斯分布。分析可知，在算法初期，加以较大高斯变异向量以获得更快收敛速度，在算法后期，加以较小高斯变异向量提升收敛精度，当算法后期陷入局部最优时，说明在当前值附近必有更好的全局值，通过高斯变异向量达到跳出局部最优并检测周围个体适应值的效果。

通过式(10)、式(11)改进后的局部授粉过程

(12)

2.4 改进花授粉算法的RSSI定位步骤

步骤1：通过RSSI测距方法获取目标区域内未知节点与锚节点之间的RSSI距离测量值d。

步骤2：设置初始参数：种群大小N、最大迭代次数T、参数维数D、转换因子p值、变异因子ε初始值等。在目标区域内随机产生N个D维初始花粉个体，每个花粉个体代表未知节点位置的一个候选解。

步骤3：通过式(4)计算每个花粉个体的适应值，通过比较，保存当前群体最优位置x*及最优适应值fitness(x*)。

步骤4：如果randp，根据式(12)更新个体空间位置，计算新解的适应值fitness，并与保存的最优适应值做比较，如果新解的适应值更优，则保留新解，并将新解的空间位置及适应值更新为群体最优位置x*及最优适应值fitness(x*)值，否则，仍保持原值不变。

步骤5：判断是否满足结束条件(达到迭代次数)，满足则结束；否则，转向步骤3。

步骤6：输出全局最优解对应的个体位置，即未知节点的估计位置坐标。

3 仿真分析

3.1 仿真环境设定

为验证改进花授粉算法的RSSI定位方法性能，设在100 m×100 m的二维区域内，随机部署100个节点，节点的通信半径为30 m，锚节点比例为10 %。分别对RSSI定位算法(最小二乘法)、PSO算法的定位算法、基于FPA的定位算法在不同锚节点密度、不同通信半径、不同节点数量条件下的定位精度进行仿真比较。粒子群算法参数设置为：种群大小N=20，c1=c2=2，Wmax=0.9，Wmin=0.4，Vmax=5，算法的最大迭代次数为300次。花授粉算法参数设置为：种群大小N=20，λ=1.5，p=0.8，改进花授粉算法参数设置与花授粉算法相同。每组不同条件下的算法均仿真运行100次，对结果取平均值进行分析比较。采用平均定位误差对定位算法优劣进行评价

(13)

3.2 收敛速度

PSO与FPA、本文算法的定位过程适应值迭代变化曲线如图1(a)所示。由图可知，PSO，FPA的收敛速度分别为80,150次。而本文提出的改进FPA算法只需60次左右就可收敛到更低适应度值，验证本文算法改进有效性，收敛速度提高，定位精度提升。

3.3 测距误差变化

由图1(b)可知，随着测距误差的增加，几种算法的定位误差均呈现上升状态，这是因为定位算法受RSSI距离测量值误差影响，基于群智能优化算法的定位算法相较于RSSI定位算法在一定程度上抑制测距误差对定位精度的影响。本文算法伴随测距误差的增大仍优于其他算法，拥有较好的稳定性。

3.4 锚节点数量变化

对不同的锚节点数量进行仿真对比，仿真结果如图1(c)所示。在相同锚节点数量情况下，本文算法误差最小。考虑在给定定位精度要求前提下，可利用本文算法采用较少的锚节点数量完成定位，减少定位成本。

3.5 通信半径变化

对不同通信半径进行仿真，仿真结果如图1(d)所示，当锚节点数量达到一定阈值后，网络连通度达到饱满，定位精度提升有限。相对于最小二乘法，PSO，FPA，本文算法定位更为准确，当通信半径越大时，本文算法拥有较明确的优势。

图1 仿真测试结果

3.6 总节点数变化

从图1(e)中可以看出，在节点数相同的情况下，本文算法的平均定位误差小于最小二乘法和PSO定位算法、FPA定位算法，相较于其他算法拥有更好的收敛性。

4 结 论

本文对于在测距误差存在情况下，RSSI定位算法中采用最小二乘法求解未知节点位置受测距误差影响较大这一情况，使用改进FPA算法替代最小二乘法，降低测距误差影响，获得更好的定位精度。在测距误差、锚节点所占比例、通信半径、总节点数目变化的情况下，本文算法的误差更小，对测距误差影响起到一定抑制作用，证明本文算法适用于无线传感器网络的定位算法。但在定位求解时间和能量消耗方面，对网络有一定的要求。