接收信号强度指示测距模型修正与粒子群算法权重优化的节点定位算法
2020-12-16任克强温晓珍
任克强, 温晓珍
(江西理工大学信息工程学院, 赣州 341000)
无线传感器网络(wireless sensor network,WSN)是由大量成本低廉、体积微小、分布密集的传感器节点组成的网络系统,这些传感器节点耗能低,能够收集特定事件的信息送到监测人员处进行进一步的处理[1]。WSN由于能获取客观的物理信息被广泛运用于军事、工业及环境监测等诸多领域[2]。在实际的应用中,准确的位置信息在WSN监测活动中必不可少,没有位置信息的监测活动无实际价值可言[3]。节点定位作为WSN中的一项重要应用,是监测事件的前提,在定位算法中,通常可分为基于距离和距离无关两大类[4]。质心算法、APIT(approximate point-in-triangulation test)和DV-Hop(distance vector-hop)等是较常用的距离无关的定位算法[5-6],无需实际测量节点间距离,硬件开销较小。相较于距离无关的算法,基于距离的定位算法可实现更高的精度[7-8]。
接收信号强度指示(received signal strength indicator,RSSI)作为一种较为常用的距离估计方法,因其较低的设备部署开销,在WSN的定位算法中得到了广泛的应用与研究[9]。然而RSSI测距具有一定的局限性,易受环境干扰,影响定位的准确性。在一些文献中,定位问题视作是一个非线性无约束的优化问题。粒子群算法(particle swarm optimization, PSO)因其参数少、计算简便、收敛快速等优点受到相关学者关注,以离散粒子群算法(DPSO)为基础,一些相关改进算法相继被提出。在粒子群算法中,当搜索空间较大时,自适应差的权重难以在搜索速度和搜索精度之间达到平衡,因此中外学者提出了相应的改进策略。文献[10]提出一种基于粒子群优化的自定位算法,该算法将学习因子设置为线性递减模式,利用分量变异法跳出自定位搜索停滞时的局部最优,该方法虽然提高了定位性能,但计算复杂度也显著提高。文献[11]提出一种贝叶斯概率模型,提高了RSSI测量的精度,但在复杂的实际环境中,所选模型的经验参数作用不大。文献[12]提出一种基于混合粒子群优化算法的室内和室外轨道自行车无线传感器精确定位技术,利用对数正态阴影模型进行参数估计并测距,然后结合混合粒子群优化-人工神经网络(PSO-ANN)算法降低测距误差,与传统对数正态阴影模型相比,定位准确度更高。文献[13]提出一种基于节点间测距的改进PSO算法,该算法在基本PSO算法中引入了动态干扰因子和罚函数,提高了算法的收敛性,避免了在无效的搜索空间中耗费时间。文献[14]提出一种优化罚函数的改进粒子群定位算法,根据种群密度改变惩罚因子用于提升收敛速度,然后对误差进行加权处理,进一步提高定位算法准确度。文献[15]提出一种自适应优化粒子群算法,根据适应度函数确定的粒子适应值调节惯性权重与学习因子的取值,并用异步变化法改进学习因子,但该算法难以跳出局部极值点,较难改善测试点定位精度。
针对复杂环境下RSSI波动较大及标准PSO算法易陷入局部极值点的问题,采用两种优化策略对定位算法进行改进:一是考虑RSSI测距误差易积累至定位阶段,利用最小化误差平方和原则,修正RSSI的模型参数;二在PSO算法中引入非线性惯性权重,平衡算法的全局与局部探索能力,减少寻优过程中的不必要消耗,防止算法收敛于局部极值点,实现定位性能的优化。
1 RSSI定位及误差分析
1.1 RSSI定位
基于接收信号强度指示(RSSI)的测距理论为:依据无线电波或声波在介质中传播,信号功率随距离衰减的原理,将信号的损耗通过衰减模型转变成距离,一般分成经验模型和理论模型两类[16]。
(1)信号传播的经验模型。首先设置一个关联数据库,录入并存放测试点的信号强度和它们对应的坐标(x,y,s1,s2,s3),然后在定位时,将测试点所测得的信号强度(s′1,s′2,s′3)与之前数据库中保存的记录值进行对比,所测信号强度与数据库记录值之间的均方差sqrt[(s1-s′1)2+(s2-s′2)2+(s3-s′3)2]最小的点即为所求未知节点的坐标,可进行多次测量以减小误差。
(2)信号传播的理论模型。考虑实际复杂环境对信号传输的干扰,确定信号衰减与传输距离间的关系式,根据测量的信号强度,利用对数正态阴影模型(log-normal shadowing model,LNSM)计算未知节点与发射节点间的距离:
(1)
式(1)中:pd为传输距离d的信号强度;pd0为传输距离d0的信号强度;n为路径损耗指数;d0为参考距离,取d0=1 m;Xσ为均值是0的高斯随机变量。
1.2 RSSI测距存在的问题
在基于RSSI的定位中,通常选用对数正态阴影模型来描述信号强度与节点距离的关系,但由于实际应用中外在因素的影响,信号强度与节点距离之间并没有明确的对应关系,这使得基于测距的RSSI定位算法存在一定的局限性[17]。RSSI测距过程受环境影响较大,理论上信号强度值进行有规律的变化,距离增大,强度值不断衰减,而事实上由于存在温度、反射及障碍物的干扰,这些环境的不稳定因素会导致获取的信号强度值波动较大,随着环境的改变,信号强度测量的不稳定性增大,所得测量值的准确度随之降低。若针对不同的实际特定环境仍选用传统模型,而不考虑环境干扰,则易造成测距误差。
因此,在原有的对数正态阴影模型基础上,针对环境变化时RSSI理论测距模型导致的定位精度不高的问题,对测距的模型参数进行修正,可有效改善以上问题,减小定位误差,提高定位精度。
2 粒子群算法分析
2.1 PSO算法原理
粒子群算法是一种启发式的优化技术[18]。因参数少、收敛快、计算简便而被广泛应用。该算法依靠粒子间相互传递信息来改变自身的飞行状态,能够产生自组织行为从而进行快速有效的收敛。标准PSO算法种群中的每个成员被量化为一个粒子,粒子的速度根据本身的历史信息以及群体的共享信息进行动态地调整。在n维空间中,第i个粒子的位置和速度分别描述为xi=(xi,1,xi,2,…,xi,n)、v=(vi,1,vi,2,…,vi,n),粒子个体与粒子种群所经历的历史最佳位置分别描述为pbi=(pi,1,pi,2,…,pi,n)、gb=(g1,g2,…,gn)。PSO算法是一种基于迭代的优化技术,在二维搜索范围中,第t+1次搜索时粒子将由pb、gb和扰动产生新的飞行速度和位置,其更新公式分别为
(2)
(3)
式中:w为惯性权重;c1、c2为学习因子;r1、r2为服从均匀分布的随机数,取值范围为0~1。
2.2 PSO算法存在的问题
目前,粒子群算法面临的一个主要问题是算法在进行优化定位的过程中不能有效实现对目标空间的全局搜索,对于有多个局部极值点的函数,容易导致算法陷入这些点中,得不到正确的结果,从而降低算法的优化性能。在标准PSO算法中,最优粒子的位置信息向其他成员进行分享,强调了一个共同最优信息的处理,而忽略了个体间信息的传递。随着迭代的进行,种群中每个成员间的距离逐渐缩小,粒子急速收敛到所获得的最优位置处,造成算法早熟失效。如何引入相应策略处理这类问题,将是提高算法适应性的关键。
针对以上RSSI在复杂环境中测距误差较大及标准PSO算法易陷入局部最优的问题,利用不同参考点的差值对RSSI测距模型的参数进行修正,并对粒子群算法的权重进行非线性化,提出一种RSSI测距模型修正及PSO权重优化的定位算法。
3 本文算法
3.1 LNSM参数估计及修正
基于RSSI测距的定位方法往往受到环境因素的影响,如果在不同环境中仍按照给定的经验值设置传播模型参数,节点间距离越大,误差越大。对数正态阴影模型的理想曲线在距离较小时接近实际测量的RSSI值,在距离较远时,由于穿透损失和阻塞效应,RSSI的测量值通常比LNSM所对应的理想值更小。因此,通过对测距模型参数进行修正,来减小环境因素对测距误差的影响。
在本文算法中,L个参考点的RSSI值是在已知坐标的m个测试点上测量的,式(1)的可测量pd设为Y,已知量-10lgd设为x,传播模型参数pd0和n分别设为a和b,则测距模型可拟合为
Y=a+bX+Xσ
(4)
LNSM的参数估计是基于最大限度地最小化误差平方和原则,使得所拟合的函数值与实际测量数据之间的误差最小化:
(5)
要使每个偏差都尽可能小,可令R最小来实现,即求函数R=R(a,b)在所测数据处取得最小值。
(6)
由此计算出a、b的表达式为
(7)
考虑L个不同参考节点之间的差异,修正公式(1)中的传播模型参数pd0和n为
(8)
根据LNSM参数估计,确定了本文算法的RSSI测距模型参数,利用RSSI修正模型进行测距,得出信标与未知节点之间的距离。
假设A、B和C3个信标节点的坐标分别为(xa,ya)、(xb,yb)和(xc,yc),以及它们到未知节点D(x,y)的距离为da、db和dc,则可通过三边测量法来求出(x,y)的取值:
(9)
由此可得出未知节点D的坐标为
(10)
3.2 非线性递减权重优化
惯性权重w的取值大小对PSO算法的寻优过程起着关键的控制作用,粒子飞行速度的升降依赖于权重的取值。若给定较高的w,粒子可提速向更大范围寻找最优目标,使粒子群体得到发散,加快算法运行的速度,有利于在前期搜索中探测最优目标所在的区域。但若整个迭代过程均赋予较高的w值,粒子飞行速度过快,极易飞越过所寻找的目标,不利于在后期靠近目标时,降低速度进行细致的探索。由此可见,w参数大小的取值十分关键。目前,采用较多的经典线性递减惯性权重为
w(k)=wmax-k(wmax-wmin)/Tmax
(11)
式(11)中:wmax、wmin分别为惯性权重的最高与最低值;Tmax为最大迭代次数。
线性递减权重难以避免带来一些问题,粒子在后期搜索中与最优目标的距离逐渐缩小,需赋予持续较小的惯性权重值w来减缓粒子的飞行速度,使粒子不断靠近最优目标所在位置,而线性递减权重的下降趋势过于陡峭,粒子容易飞越过最优解。
(12)
式(12)中:wmax、wmin为惯性权重的最高与最低值,取wmax=0.9、wmin=0.4;t为当前迭代次数;Tmax为最大迭代次数;λ为收敛因子,当λ取值较大时,粒子速度减小,有助于粒子的探索在极值点附近进行;当λ取值较小,惯性权重值增大,粒子速度加快,能够扩大搜索范围。当迭代次数t=0时,函数值为初始权重值wmax=0.9,随着搜索的进行,权重值呈非线性递减趋势,当达到最大迭代次数Tmax时,权重降为0.4,有利于局部搜索。本文所提出的非线性递减权重策略符合寻优过程,具有较理想的寻优性能。
已知未知节点D(x,y)周围有N个信标节点,第q个信标节点坐标为(xq,yq),本文优化粒子群算法的适应度函数取为
(13)
4 仿真结果与分析
为测试本文定位算法的性能,采用MATLAB R2016b仿真平台对本文定位算法的测距模型参数pd0和n进行确定;分析不同的惯性权重对算法的影响;并从测距误差、信标节点密度、迭代次数3个方面对DPSO算法、文献[14]的PSOAPF算法和本文算法的性能进行仿真实验对比。仿真的空间取100 m×100 m的二维区域,节点总数为100,信标节点占30%,通信半径为R=30 m,粒子群各参数设为M=30,c1=1.5,c2=1.2,各实验分别进行100次测试,结果取平均值。
以节点平均定位误差Eave作为算法的评价标准:
(14)
首先通过实验建立RSSI的测距模型,在本文实验环境中,在距离为di=0.2i(i=1,2,…,50)的4个参考点和40个测试点间对RSSI值测量100次,得到各个间距di处的RSSI值,取测试的平均值与di进行拟合,得出校正的pd0值和n值,图1为通过MATLAB平台得到的拟合曲线。
图1 RSSI测试值的拟合曲线Fig.1 The fitting curve of the RSSI test value
在实验测试中,RSSI测距模型参数修正为pd0=-37.02;n=2.04。如果干扰因素发生改变,可重新调整参数值。
图2为迭代过程中两种惯性权重取值大小的变化情况,wa为线性权重,wb为本文提出的非线性权重。
图2 惯性权重的变化比较Fig.2 Comparison of performance changes of w
由图2可见,随着迭代的进行,两种惯性权重值均不断降低,在迭代次数0≤t≤15时,wb的下降速度大于wa,随着搜索的进行,迭代后期wb曲线逐渐趋向水平,在15
图3通过仿真实验测试在信标节点密度为15%时,测距误差变化情形下DPSO算法、文献[14]的PSOAPF算法及本文算法的平均定位误差情况。
图3 测距误差与平均定位误差的关系Fig.3 The relationship between the ranging error and the mean positioning error
由图3可见,测距误差越大,3种算法的平均定位误差也越大,表明测距误差的积累容易对定位阶段产生不利影响。其中,DPSO算法的整体平均定位误差最大,PSOAPF算法次之,本文算法的平均定位误差最低。在测距阶段产生20%的误差时,实验得出DPSO与PSOAPF两种算法的平均定位误差为31.3%和26.2%,而本文算法低至19.8%,在相同测距误差下,本文算法的平均定位误差低于DPSO算法与PSOAPF算法,定位性能更佳。
图4通过仿真实验比较DPSO算法、文献[14]的PSOAPF算法以及本文算法在不同的信标节点密度下的性能表现。
图4 不同信标节点密度的平均定位误差Fig.4 Mean positioning error of different beacon node density
图4表明,3种算法在仿真空间信标节点数目越多时,所获未知节点的信息越全面,定位越精确。其中,当控制仿真区域内信标节点占比为14%时,DPSO的平均定位误差最高,达到28.01%,相比之下,PSOAPF和本文算法的平均定位误差值下降明显,分别为23.3%和20.01%。由此可知,DPSO算法的平均定位误差虽有下降趋势,但误差值整体较高,效果最差;PSOAPF算法次之,本文算法的平均定位误差最小,表现的性能最好。
图5表示在不同迭代次数下,当测距误差为20%时,DPSO算法、文献[14]的PSOAPF算法以及本文算法的适应值比较情况。由图5可见,迭代至10~20次时,3种算法相继收敛。其中DPSO算法的收敛性能最差,在迭代约18次才趋于收敛,PSOAPF算法则在迭代约12次适应度值曲线就呈水平状态,出现收敛趋势,比DPSO算法收敛性能更良好,而本文算法在迭代大约10次则迅速收敛,在3种算法中收敛性能最优。
图5 不同迭代次数的适应度比较Fig.5 Fitness comparison of different iterations
5 结论
提出一种融合RSSI测距模型参数修正与PSO权重优化的改进定位算法,采用不同参考点的差值对RSSI测距模型的参数进行修正以及对粒子群算法的权重进行非线性化两种策略来提升改善算法性能。为了测试验证本文改进策略的成效,在不同条件下对算法进行了仿真测试比较。仿真结果显示,在硬件条件不变的情况下,本文定位算法的表现优于DPSO算法与PSOAPF算法,具有更好的收敛性能及更高的节点定位精度。如何进一步改善提升算法的性能,是后期要重点研究的工作。