基于测距和灰狼优化的无线传感器网络定位算法*

段亚青,王华倩,乔学工*

(1.太原理工大学信息与计算机学院,太原 030024;2.华北电力大学电气与电子工程学院,北京 102206)

无线传感器网络[1]WSN(Wireless Sensor Networks)是一种由大量部署在预定区域内的传感器节点组成的自组织网络,可以对部署区域进行监控,实时给用户传回有效信息。节点定位技术是WSN的关键基础技术之一[2],广泛的应用在医疗卫生、火灾监控、环境检测等方面,越来越多的应用对定位精度提出了更高的要求。位置信息是对网络中突发事件进行事前预警、事中决策以及事后处理的前提。

节点定位技术分类标准有很多种方法,其中基于测距定位技术和非测距定位技术是最常用的分类标准。接收信号强度指标RSSI(Received Signal Strength Indicator)是一种基于测量距离的定位算法,它利用信号在传播过程中的衰减强度来计算未知节点和信标节点之间的距离,再利用三边测量法计算未知节点的坐标,RSSI测距无需额外硬件[3],成本低、能耗低、实现简单,所以基于RSSI的节点定位算法是一个研究热门。智能算法为许多无法直接使用数学方法求解的优化问题提供了新的解决思路,为了提高定位精度,研究学者将智能算法应用在节点定位算法中。在文献[4]中,提出了模拟退火定位算法,即将模拟退火算法用于节点定位算法当中,这是在早期尝试把定位问题转化为优化问题的研究之一,但该方法计算量大且定位精度不高。文献[5]中提出了IRSSI测距方法,对未知节点进行定位,为了使节点坐标更加准确,采用粒子群算法进行后期优化。文献[6]中针对经典DV-Hop定位算法第3 阶段计算未知节点位置存在较大误差的问题,提出一种基于改进粒子群优化算法的无线传感器网络定位方法,将定位问题转化成未知节点坐标的优化问题,采用改进粒子群算法进行坐标优化。文献[7]提出了一种基于带有动态扰动项粒子群的无线传感器网络定位算法,一定程度上加快了算法收敛速度,提高了节点定位精度。将群体智能算法应用于无线传感器网络节点定位中,可以提高定位精度[8-9],较为著名的有粒子群算法、遗传算法、蚁群算法等,但群体智能算法存在易陷入局部最优的缺陷,Mirjalili等人提出了一种新的群体智能算法——灰狼优化算法(GWO)[10],GWO算法已被证明在求解精度和稳定性上明显优于粒子群算法、差分进化算法、引力搜索算法。因此本文提出一种基于测距和改进灰狼优化的无线传感器网络定位算法。定位分为两个阶段,粗略定位阶段和精确定位阶段。在粗略定位阶段建立了基于3个信标节点的定位数学模型,本文对未知节点进行初步定位估计时应用了公边比例定理,该方法相比三边测量法,降低了计算阶数,二次式变为一次式,简化了计算;在精确定位阶段使用改进灰狼算法优化未知节点坐标值,灰狼优化算法在搜索过程中是非线性变化的,基本灰狼优化算法中收敛因子a是随迭代次数线性递减的,不符合实际优化搜索过程,因此本文提出一种基于对数递减策略的非线性动态变化收敛因子。仿真表明,本文算法具有较高的定位精度,并且具有对测距误差鲁棒性强的优点。

1 定位算法模型建立

1.1 RSSI信号衰减模型

采用对数-常态分布[5]无线信号传播模型:

PL(d)=PL(d0)-10nlg(d/d0)+Xσ

(1)

式中:d为未知节点与参考节点之间的距离;d0为参考距离,通常取值为1m。PL(d)、PL(d0)分别为在传播距离为d和d0时的接收信号功率;当d0=1m时,PL(d0)=55 dBm。n为路径损耗系,一般与环境相关,取值为2～5;Xσ为均值为0,标准差为σ的高斯随机变量,表示环境等因素对测距误差的影响。n和Xσ的值是适应本实验环境下通过多次实验选取确定的,在不同的实验环境下需要重新设定。对式(1)两边同时取对数,可以得到RSSI值与距离d之间的关系,可以表述为RSSI(d)=δ0-10nlgd+Xσ其中,RSSI(d)为未知节点收到的距离为d的信标节点的RSSI信号强度,δ0=10lgPr(d0)表示信号传播距离为d0时接收信号功率。根据式(2)将信号强度值转化成距离值:

(2)

1.2 未知节点初步定位估计

建立定位数学模型,利用该模型对未知节点进行初步定位估计,计算未知节点的坐标,通过距离差判别法获取未知节点坐标。

1.2.1 定位数学模型建立

未知节点接收到至少3个不共线信标节点的位置信息才能通过三边测量法进行自身位置估计。借鉴此思想建立通过3个信标节点的坐标,获取未知节点坐标的定位数学模型。

如图1所示,A、B、C是3个信标节点,P是未知节点,其位置均随机分布,P点相对3个信标节点构成的△ABC其分布存在4种情况:

区域1:P位于3个信标节点A、B、C构成的三角形△ABC区域内;

区域2:P位于∠BAC包含的区域除去△ABC区域剩余的区域及∠BAC对顶角包含的区域内;

区域3:P位于∠ACB包含的区域除去△ABC区域剩余的区域及∠ACB对顶角包含的区域内;

区域4:P位于∠ABC包含的区域除去△ABC区域剩余的区域及∠ABC对顶角包含的区域内。

图1 节点区域分布图

3个信标节点求未知节点坐标的解法示意图,如图2所示。

图2 节点定位模型示意图

设A、B、C是3个信标节点,P为未知节点,设P的坐标是(xp,yp),A′是直线PA与直线BC的交点、B′是直线AC与直线BP的交点、C′是直线BC与直线PC的交点。3个信标节点到P的测量距离分别是LAP、LBP、LCP。kBC是直线BC的斜率。下列式子中的G1、G2、G3为区域系数,与P点所在区域有关。

①当P位于区域1时,公边比例定理可得:

由直线PA与直线BC交于A′,有:

(3)

则A′点的坐标可以表示为:

(4)

直线PB与直线AC交与B′,有:

(5)

则B′点的坐标可以表示为:

(6)

直线PC与直线AB交于C′,有:

(7)

则C′点的坐标可以表示为:

(8)

②当P位于区域2时,公边比例定理可得:

直线PA与直线BC交于A′,有:

(9)

则A′点的坐标可以表示为:

(10)

同理直线PB与直线AC交与B′,有:

(11)

则B′点的坐标可以表示为:

(12)

同理直线PC与直线AB交于C′,有:

(13)

则C′点的坐标可以表示为:

(14)

区域3即将区域2的A换成C,B换成A,C换成B。区域4即将区域2的A换成B,B换成C,C换成A。即区域3和区域4的求法和区域2相同。设直线AA′与直线BB′的交点为(xp1,yp1),直线AA′和直线CC′的交点为(xp2,yp2),直线BB′和直线CC′的交点为(xp3,yp3)。

1.2.2 距离差判别法

(15)

分别计算(xp1,yp1)、(xp2,yp2) 、(xp3,yp3)、(xp4,yp4)的距离差值d,取d(i)的最小值对应的坐标作为改进灰狼算法的初始值,i的取值为1～4。

(16)

2 改进灰狼优化算法

为了从数学上对狼的社会等级进行建模,在设计GWO时,将最佳的解决方案视为alpha(α),因此,第2个和第3个最佳解决方案被分别视为beta(β)和delta(δ),剩下的候选方案视为omega(ω),在GWO算法中狩猎(优化)是由α、β和δ引导的,ω跟随其他3种狼。

灰狼群狩猎过程的第1步是灰狼群接近并包围猎物。其数学表达为:

D=|C·XP(t)-X(t)|

(17)

X(t+1)=XP(t)-A·D

(18)

式中:t表示当前迭代的次数,XP是猎物的位置,X(t)是灰狼的位置。D表示包围步长。A和C为系数向量,分别由式(19)和式(20)计算得出:

A=2a·r1-a

(19)

C=2·r2

(20)

r1和r2是[0,1]之间的随机向量;收敛因子a为控制参数,随着迭代次数从2线性递减到0。

在猎捕阶段,其他ω灰狼个体根据α的当前位置Xα、β的当前位置Xβ和δ的当前位置Xδ来更新各自的位置,由式(21)和式(22)表示,式(21)表示ω灰狼朝向α、β、δ灰狼的前进步长和方向:

(21)

X(t+1)=(X1+X2+X3)/3

(22)

最后,攻击阶段,在此阶段根据A和C的值来控制探索和开发过程。在迭代过程中,收敛因子a是逐渐减小的,A的波动范围随着a的减小而减小,A是[-a,a]内的一个随机值,当|A|≤1时,灰狼群向着猎物攻击,以实现局部搜索,当|A|>1,灰狼群体远离猎物,以加强算法的探索能力实现全局搜索。从式(20)可以看出C在整个迭代过程中都是一个随机量,C的随机性是为了随机的强化或弱化猎物在定义的距离方程中的影响,并且在最后的迭代过程中一直加强搜索,可以避免陷入局部最优。

本文对灰狼优化算法的改进如下:

①灰狼优化算法的初始化种群个体是随机产生的,在一定程度上不能保证初始化种群的多样性,导致优化结果精度不高。本文算法的初始点是由定位数学模型计算出的初步定位结果以及离未知节点最近的信标节点的坐标产生,缩小了可行解空间,减小了计算量,同时加快了收敛速度。

②针对收敛因子进行改进。灰狼优化算法在搜索过程中是非线性变化的,收敛因子a随迭代次数线性递减策略不符合实际优化搜索过程。

文献[11]提出了基于余弦函数(记为COSGWO)和二次函数(记为2GWO)的非线性动态变化收敛因子更新方法,更新公式为式(23)、式(24),仿真结果表明优于基本GWO,且基于余弦函数和二次函数的收敛因子非线性动态变化效果接近。

at=(ainitial-afinal)×cos(t/tmax)

(23)

at=ainitial-(ainitial-afinal)×(t/tmax)2

(24)

式中:ainitial和afinal分别是a的初始值和终值,t为当前迭代次数,tmax为最大迭代次数。

算法要求:在前期有较高的全局搜索能力以得到合适的位置,找到合适的位置后,a值能迅速减小进入局部搜索以加快收敛速度,在后期要求有较高的局部开发能力,以提高算法收敛精度。本文提出一种基于对数递减策略的非线性动态变化收敛因子更新公式:

at=ainitial-μ×(ainitial-afinal)×logtmaxt

(25)

式中:ainitial和afinal分别是a的初始值和终值。μ是对数调整因子,0<μ<1称为对数压缩因子,算法的搜索范围相对上移;μ>1称为对数膨胀因子,算法的搜索范围相对下移。μ=1,最后a收敛于afinal,本文中μ=1。μ越小,a递减越慢,在算法的后期可以进行更精细的局部搜索。在实际应用中,对不同的优化问题可以适当的调整μ的值。

3 基于改进灰狼优化(LOGGWO)的定位算法

设P点可以接收到m个信标节点的信号,将m个信标节点以3个不共线的为一组分组,假设一共有k组。通过第1部分的数学模型可以计算出k个P点的坐标值,分别是(xP1,yP1),…,(xPk,yPk)。这k个坐标值即LOGGWO算法的部分初始值,通过算法寻优得到未知节点P的优化坐标。设改进灰狼优化算法的种群大小为N。若k≥N,则选用根据适应度值从小到大选取前N个作为初始值;若k

(26)

利用改进灰狼算法对未知节点P的估计坐标值优化的方法是:

步骤1:初始化,t=0,t为当前迭代次数,N为种群大小。若k≥N,则根据适应度值从小到大选取前N个作为初始值将(xP1,yP1),(xP2,yP2),…,(xPi,yPi),…,(xPN,yPN)赋值给(xW1(t),yW1(t)),…,(xWi(t),yWi(t)),…,(xWN(t),yWN(t)),i的取值为1～N;若k

步骤2:计算每个位置的适应度函数值。

(27)

式中:(xj,yj)是第j个信标节点的坐标,dij是灰狼i与信标节点j之间的距离,m是可以与i相互通信的信标节点数,所以j的取值是1～m。将个体按适应函数值从小到大排序,排在第1位的个体设为alpha(α),排在第2位的个体设为beta(β),排在第3位的个体设为delta(δ)。

步骤3:搜索位置更新。灰狼的猎捕阶段。根据式(19)～式(22)、式(25)更新位置。

步骤4:计算适应度函数,更新α、β、δ个体的位置,令t=t+1。

步骤5:若t>tmax,tmax为最大迭代次数,停止搜索,否则转至步骤2.

LOGGWO算法的时间复杂度计算如下:计算种群中每个个体的适应度值的时间复杂度为O(N),N为种群规模;个体位置更新操作的时间复杂度为O(N2+klogn);群体循环迭代的时间复杂度为O(N2),所以,LOGGWO算法的时间复杂度为O(N2)。

基于LOGGWO的定位步骤如下:

步骤1:在网络拓扑中随机分布100个传感器节点,包含信标节点和n个未知节点;

步骤2:将未知节点接收到的信标节点的信号强度转化成距离值;

步骤3:计算第i(i的取值为1～n)个未知节点可以接收到信标节点的个数,记作m,若m<1,则此未知节点无法定位,跳转至步骤6;若0

步骤4:将第i个未知节点可以接收到的m个信标节点分组,每3个不共线的信标节点为一组,假设一共有k组,运用本文提出的数学模型计算出该未知节点的坐标:(xW1,yW1),…,(xWk,yWk)。

步骤5:初始化种群,对未知节点寻优定位。

步骤6:若i=n,算法结束,计算定位误差:其中EROi表示每个未知节点的定位误差;平均定位误差用节点通信半径归一化后的相对定位误差表示,EROAVE表示平均定位误差,(xR(i),yR(i))和(xE(i),yE(i))分别表示第i个未知节点的实际坐标和估计坐标,n表示未知节点总数。

(28)

(29)

若i≠n,i=i+1,跳转至步骤3。

4 仿真

为了验证算法的有效性,本文采用MATLAB进行仿真。在边长为100 m的正方形区域随机分布100个传感器节点,其中包含信标节点,本文所用算法的种群规模均为30,最大迭代次数均为300,通信半径为30 m,信标节点所占比例为30%,RSSI信号衰减模型中的Xσ的标准差取值为8。与同类COSGWO算法[11]、GWO算法相比较来验证本文对灰狼算法改进方法的有效性,并与已有的定位算法DPSO[12]和基于测距的三边定位算法相比较,验证本文定位算法的有效性。

从图3可以看出,随着信标节点数的增加,平均定位误差降低,这是因为信标节点数目增加使网络中未知节点的邻居信标节点数目增加,未知节点可以获得更多的位置参考信息,定位误差减小。本文定位算法平均定位误差始终保持最小,表明本文改进算法优于其他定位算法,验证了本文灰狼算法改进方法的有效性以及本文定位算法的有效性。信标节点的成本比较高,信标节点的数量直接影响整个网络的成本。本文定位算法当信标节点所占比例大于30%以后,平均定位误差变化趋于平缓,在相同定位误差下,本文算法需要的信标节点的数目较少,能有效的节省网络成本。

图3 通信半径R=30 m时,平均定位误差 与信标节点比例关系比较图

从图4可以看出,随着通信半径的增加,网络连通性提高,所以各算法的平均定位误差均降低,本文定位算法平均定位误差始终保持最小,优于其他算法。可以看出在相同的定位误差下,本文算法所需要的通信半径最小,通信半径越小,能耗越小,在同等条件下,本文算法可以节约能耗,延长网络寿命,降低网络维护成本。

图4 信标节点所占比例为30%时,平均定位误差 与通信半径关系比较图

图5 未知节点定位误差比较图

图5和图6是基于改进灰狼优化定位算法、基于COSGWO定位算法、基于GWO定位算法的未知节点定位误差对比图。仿真条件是:图5中RSSI的Xσ的标准差取值为4,图6中RSSI的Xσ的标准差取值为8,信标节点所占比例为30%,通信半径为30 m。图5和图6都是由仿真50次后的平均值得到的结果图。可以看出,本文定位算法相比基于COSGWO的定位算法和基于GWO的定位算法定位精度更高。Xσ高斯随机噪声,表示环境等因素对测距误差的影响,均值为0,标准差为σ,测距误差会随着标准差σ的增加而增大,对比图5和图6可以看出随着σ增大(测距误差的增大),未知节点定位误差整体增大,但本文算法未知节点定位误差整体依旧保持最小,精度依然很高,可见本文定位算法对测距误差的抗干扰能力更强,具有更高的实用性。

图6 未知节点定位误差比较图

图7是本文定位算法与已有的文献[12]提出的DPSO定位算法和基于测距的三边定位算法的未知节点定位误差对比图。仿真条件是:RSSI的Xσ的标准差取值为8,信标节点所占比例为30%,通信半径为30 m。图7是由仿真50次后的平均值得到的结果图。从图中可以看出本文定位算法未知节点的平均定位误差最低,优于DPSO定位算法和基于测距的三边定位算法。本文定位算法在粗略定位阶段建立定位数学模型,是一种基于测距的未知节点坐标估计方法,本文定位数学模型均为一次等式,和三边测量法相比,降低了计算阶数,简化了计算。

图7 未知节点定位误差比较图

5 结束语

本文提出了一种基于测距和改进灰狼优化的无线传感器网络定位算法,在初步定位阶段提出了一种定位数学模型,实现对未知节点的初步定位估计;在精确定位阶段用具有较强平衡局部搜索和全局搜索能力的灰狼优化算法进行寻优定位。本文中灰狼算法的初始化搜索种群是初步定位估计值,缩小了可行解空间,减小了计算量,同时加快了收敛速度;并将收敛因子a非线性化,更符合实际优化搜索过程,能动态平衡局部搜索和全局搜索能力。仿真实验表明,本文算法相比一些已有定位算法,有效提高了定位精度,同等条件下,降低了网络成本,节省能耗,可延长网络寿命,并且具有对测距误差鲁棒性强的优点。