基于自适应罚函数优化粒子群的WSN定位算法*

1 PSOAPF定位算法

1.1 经典粒子群算法

粒子群优化算法是一种基于群体智能理论的模拟计算技术,该算法首先产生初始种群,种群中每个粒子均视为可行解之一,这些粒子都在可行解空间运动,由自身的运动速度决定其方向和距离,每一粒子紧跟当前最优粒子运动,从而得到最优解[10-11]。

在粒子群算法中,假设选择N个粒子作为初始化随机粒子,在一个D维空间中,每个粒子代表一个解,这一粒子均包含有位置信息和速度信息,通过不断重复迭代,更新自己的位置,趋向于最优粒子[12]。在群体中,假设第i个粒子的位置坐标为xi=[xi1,xi2,…,xiD],速度为vi=[vi1,vi2,…,viD],在迭代过程中粒子不断通过跟踪个体最优值pbest和全局最优值gbest来更新自己的速度与位置信息[13],如式(1)、式(2)所示。

vij(k+1)=ω·vij(k)+c1r1[pbest(ij)-xij(k)]+c2r2[gbest(ij)-xij(k)]

(1)

xij(k+1)=xij(k)+vij(k+1)

(2)

式中:i=1,2,…,N;j=1,2,…,D;k为迭代次数;ω为惯性权重,用来调整粒子的多样性;c1,c2为学习因子,分别表示粒子的自身学习能力和全局学习能力;r1与r2为[0,1]区间任意的随机数。

1.2 传统罚函数法

罚函数作为目前主要的约束优化处理方法之一,其思想是对对违反约束条件的非可行点或者试图穿越边界而逃离可行域的点给予惩罚,使其靠近可行域[14]。其构造思想是在原目标函数中加入某障碍函数,从而得到一个增广目标函数,由此将约束优化问题转化为无约束优化问题。

优化问题的数学模型为:

(3)

式中:g(x),h(x)分别为不等式约束条件和等式约束条件。

由于不等式约束条件可以与等式约束条件互相转换[15],因此gi(x)≥0等效为min[0,gi(x)]=0。由此上述不等式约束问题转化为如式(4)所示的等式约束:

(4)

由此,罚函数p(x)可用式(5)表示:

(5)

定义:

当gi(x)≥0时,φ[gi(x)]=0;当gi(x)<0时,φ[gi(x)]>0;

当hi(x)=0时,μ[hj(x)]=0;当hi(x)≠0时,μ[hj(x)]>0。

得到函数φ和μ如式(6)、式(7)所示:

φ[gi(x)]=|[min{0,gi(x)}]|α

(6)

μ[hj(x)]=|hj(x)|β

(7)

式中:α≥1,β≥1均为常数,通常取α=β=2。由此得到增广目标函数F(x,M)如式(8)所示:

(8)

式中:M为大于0的常数,Mp(x)为惩罚项。在极小化过程中,迭代初期,迭代点x如果位于可行域外部,为了迫使迭代点不断靠近可行域并成为可行点,因此对此迭代点给予惩罚,此时定义M值很大,Mp(x)随之变大,且离可行域越远则其值越大;当点x位于可行域内时,Mp(x)值很小,当其值为0时,则F(x,M)=f(x)。从而将求解约束极值的问题转化为求解无约束极值问题。

1.3 自适应罚函数

由于传统罚函数的惩罚因子是固定不变的,罚因子大小的选取难以控制,过大或过小都将会导致算法病态发展。在优化早期,群体中可行解的数量极少甚至没有,为了使粒子能够快速进入可行域内,这时需要惩罚因子很大。随着优化进行,粒子逐渐进入群体,此时要求惩罚因子也随之减小。

因此设计自适应罚因子应具有:在优化初期,可行解比例γ=0时,此时群体没有可行解,惩罚因子为最大,使粒子能够快速进入可行域内。早期过程中罚因子应根据粒子进入可行域比例的增大而急剧下降,随着优化的不断进行则缓慢减小。使得优化重心从可行解迅速转移到目标函数上来,当可行解比例γ=1时,说明都是可行解,罚因子降为0,使非可行解进入群体。因此构建的自适应罚因子如式(9)所示:

(9)

式中:γ为群体中可行解的比例;α可取[10,15]之间的一个整数。取α=10时,其曲线如图1所示。

图1 M(γ)函数图

由此构建出自适应罚函数如式(10)所示:

(10)

1.4 PSOAPF算法描述

在无线传感器网络中,假设已知N(xi,yi)(i=1,2,…,m)为m个信标节点的坐标,X(x,y)为未知节点X的坐标。通过RSSI测距技术可测出未知节点与信标节点的测量距离di(i=1,2,…,m),如方程组(11)所示:

(11)

对方程组(11)采用极大似然估计法进行求解,得到式(12):

(12)

将式(12)中的方程组用矩阵形式表示:AX=B,其中:

由此可得到未知节点的坐标,如式(13)所示:

X=(ATA)-1ATB

(13)

根据得到的未知节点的坐标,便得到未知节点与各信标节点的计算距离,如式(14)所示:

(14)

根据式(14)所得的计算距离与RSSI测量距离,可以得到计算测量误差,如式(15)所示:

εi=|Di-di|

(15)

RSSI测距技术中两个节点间的距离越近,测距精度越高,相反则精度越低。为减少测距误差,提高定位精度,防止测距时出现一组或者几组较大的测距误差带来的定位精度的下降,对计算测距误差进行加权求和,如式(16)所示:

(16)

为了减少算法中,粒子的活动范围,限制粒子的活动空间,加快收敛速度,对自适应罚函数的惩罚项作如式(17)、式(18)处理,将算法中种群的活动范围限制在此区域中,并根据区域中种群密度的大小,自适应调节惩罚因子的大小。

(17)

(18)

故可根据式(19)将节点定位问题转化为模型优化问题,最优解就是未知节点X到信标节点的距离:

(19)

在定义权值δ和粒子群种群活动区域基础上,可得到PSOAPF算法的定位模型的约束条件,如式(20)所示:

(20)

由此可得到适应度函数,如式(21)所示:

(21)

确定了约束条件和适应度函数后,可根据如图2所示得出基于自适应罚函数优化粒子群的无线传感器网络定位算法步骤流程。

图2 算法流程图

2 仿真实验

2.1 实验设计

实验用MATLAB2015b仿真软件。仿真的空间为100 m×100 m的二维区域,设定节点总数为100个,信标节点的通信半径为R=30 m,信标节点个数30个,仿真分别与PSO算法、DPSO算法、RQ-PSO算法与PSOAPF算法进行比较,粒子群种群大小为30,c1=1.5,c2=1.2。每种不同的实验各进行100次,取平均值作为最后结果。以节点平均定位误差和PSOAPF算法迭代次数作为算法的评价标准,节点平均定位误差定义如式(22)所示:

(22)

2.2 实验结果分析

2.2.1 惯性权重对定位误差的影响

惯性权重W是粒子保持原来速度的系数,当W的值较小时,粒子的局部搜索能力较强,有利于粒子找到局部最优解,当W的值较大时,则粒子有更大的搜索空间,有利于粒子发现全局最优解。仿真如图3可知,当0

图3 惯性权重对定位误差的影响

2.2.2 PSOAPF算法与PSO算法收敛性能对比

在测距误差为20%的情况下,PSOAPF算法与PSO算法在收敛性能方面进行比较,仿真结果如图4所示。由图4可以看出:随着迭代次数的增加,初始时刻PSOAPF算法与PSO两种算法的适应度值都迅速下降,大约在10次迭代后慢慢趋于稳定,这表明了PSOAPF算法与PSO两种算法都是收敛的。然而PSOAPF算法在大约12次时就开始收敛,表现了更好的收敛性能,而PSO算法在大约18次才开始收敛。说明了PSOAPF算法的收敛性能要优于PSO算法。

图4 PSOAPF算法与PSO算法收敛性能对比

2.2.3 不同迭代次数与定位误差的关系

仿真PSOAPF算法与RQ-PSO算法、DPSO算法3种算法的迭代次数与定位误差的关系如图5所示。从仿真图中可以看出,3种算法的定位误差都随着迭代次数的增加而减少,其中PSOAPF算法曲线斜率最大,RQ-PSO 算法次之,DPSO算法最小,PSOAPF算法大约在14次后趋于稳定,定位误差基本保持不变,而RQ-PSO算法大约在18次迭代后保持稳定,DPSO算法大约在20次迭代后定位误差保持不变。由此表明PSOAPF算法的收敛速度大于RQ-PSO算法、DPSO算法,且保持较好的定位误差。

图5 不同迭代次数与定位误差的关系

2.2.4 信标节点密度与定位精度的关系

比较3种算法在不同的信标节点密度环境下的平均定位误差,仿真如图6所示。从仿真图中可以看出:3种算法的平均定位误差随着信标节点密度的增加而下降。当信标节点密度为15%,PSOAPF算法与RQ-PSO算法、DPSO算法的平均定位误差分别为20.76%、23.62%、26.78%;当信标节点密度为40%时,平均定位误差则下降为14.06%、15.13%、17.68%。由此看出PSOAPF算法平均定位误差最小,且下降幅度更为平缓,对网络中信标节点的数量要求更低,RQ-PSO 算法次之,DPSO算法最差。

图6 信标节点密度与定位精度的关系

2.2.5 测距误差与平均定位误差的关系

设定信标节点的密度为20%,仿真不同的测距误差下3种定位算法的平均误差曲线如图7所示。由仿真结果可以看出,3种算法的定位误差都会随着测距误差的增大而增大,PSOAPF算法曲线斜率最低,RQ-PSO算法次之,DPSO算法最差。当测距误差为20%时,DPSO算法比RQ-PSO算法大9.84%,RQ-PSO算法比PSOAPF算法大8.27%,且随着测距误差的变化,差值不断扩大,说明PSOAPF算法具有更强的抗干扰能力。

图7 测距误差与平均定位误差的关系

3 结束语

针对无线传感器网络定位问题,本文在传统粒子群算法定位技术研究的基础上,提出了一种自适应罚函数优化粒子群算法,并将其应用于无线传感器网络节点定位中。仿真结果表明:本算法可以较好克服传统粒子群算法收敛速度慢,易陷入局部极小点等问题。与同类粒子群算法对比,具有较好的定位精度和更快的收敛速度,且算法具有较强的稳定性。