一种改进的布谷鸟搜索移动信标节点定位方法

荆夏磊,乔学工

(太原理工大学 信息工程学院,山西 晋中 030600)

0 引言

无线传感器网络由成百上千传感器节点组成,这些传感器节点可以通过飞机播撒或炮弹射击等方式进行部署。研究传感器节点定位问题具有重要意义,如在战场实时监测[1],林业数据采集[2]等应用中,往往需要获取相关物体的位置信息。

传统静态信标节点定位方式容易受到节点布置数量、分布状态等因素影响。一旦网络中节点的拓扑结构发生变化,定位效果不佳。许多研究者提出利用移动信标节点辅助未知节点定位[3-5]。Srinath[6]提出让信标节点按照随机移动模型移动,采用分布式算法定位;陈娟[7]等提出单一信标节点采用Gauss-Markov的方式尽量遍历传感器节点分布区域,再通过加权质心与扩展卡尔曼滤波算法计算未知节点坐标;文献[8]用接收信号强度法(RSSI)测量距离,用Bayes推论估算未知节点位置,比较了两种确定路径下的移动信标节点定位性能;文献[9]提出一种基于移动信标节点功率控制的智能定位方法。上述文献研究了移动信标节点按照某种路径移动时的节点定位问题。当移动信标节点在运动中距离未知节点较近时,定位精度较高;距离较远时定位精度低,甚至不能定位。节点定位覆盖率是指可定位未知节点数目与全部未知节点数目之比。在移动信标节点辅助定位的情况下,研究节点定位覆盖率具有现实意义。

近年来,国内外的专家学者受到仿生学启发而提出许多智能算法,如粒子群算法,人工鱼群算法,遗传算法等。智能算法具有很强的收敛性,布谷鸟搜索算法(Cuckoo Search,CS)是其中之一,该算法在梯形水库优化调度[10]、结构损伤无损检测[11]等应用中有良好的实效。本文将布谷鸟搜索算法用到移动信标节点定位问题中,针对算法在迭代后期陷入局部最优问题提出一种基于改进布谷鸟搜索算法(Artificial Fish-Cuckoo Search,AF-CS)的移动信标节点定位算法。该算法将移动信标节点定位问题转化为求解目标函数——定位覆盖率最优解问题,将人工鱼群算法(Artificial Fish Swarm Algorithm,AFSA)觅食行为引入布谷鸟搜索算法以增强算法的全局收敛能力。仿真结果表明:该算法能够在一定条件下达到对未知节点的较高定位覆盖率,同时提高了算法的收敛速度。

1 算法模型

1.1 RSSI信号衰减模型

由于节点布置在现实空间中,信号会受到障碍物或其他环境因素的干扰而产生损耗。本文采用的无线信号传输模型为对数-常态分布模型(Log-Normal Distribution Model)。节点接收信号时的路径损耗如下:

(1)

公式(1)中,d为未知节点到移动信标节点的距离,d0=1 m为参考距离;PL(d)、PL(d0)分别表示经过d和d0的路径损耗,单位为dBm。当d0=1 m时,PL(d0)=55 dBm;n是路径损耗因子,取值范围为[2,5],本文取4;Xσ是均值为0,标准差为σ的高斯随机变量,表示环境因素对测距误差的影响,本文σ设定为8。可以通过公式(2)计算未知节点到移动信标节点的距离:

(2)

1.2 信标节点移动目标函数

在一定区域中,多个移动信标节点选择合适的位置对未知节点进行定位。本文将移动信标节点运动中的停留点视为移动信标节点的目标位置。信标节点移动至目标位置向周围广播自身位置信息。一般情况下,当未知节点收到3个或3个以上不同信标节点位置信息时,通过定位算法可对该未知节点定位。在上述过程中,将对未知节点的定位覆盖率作为目标函数,具体设计如下:

(3)

(4)

(5)

公式(3)-(5)中,A(t)为第t次迭代中可定位未知节点的数量,B是区域内未知节点总数。at(i)表示第t次迭代中第i个未知节点,在每次迭代中遍历区域内所有未知节点并将可定位的未知节点数量求和。Sj表示未知节点通信半径R内信标节点数量,当未知节点接收信标节点信息数量达到3个或3个以上时,将该未知节点记为“1”,否则记为“0”。目标函数f(t)即为对未知节点的定位覆盖率。

2 多移动信标节点定位算法

2.1 初步定位

Fig.1 Method of maximum likelihood estimation图1 极大似然估计法

采用RSSI信号衰减模型和DV-Hop算法,对未知节点进行定位,用于确定信标节点移动的目标位置,为精确定位做准备。

2.1.1 RSSI定位

采用RSSI[12]测距方法,对能够定位的未知节点(该未知节点通信半径内的信标节点个数大于等于3)进行定位,再利用极大似然估计法求解未知节点的坐标估计值。

如图1所示,已知信标节点S1，S2，…，Sn的坐标(xS1,yS1)，(xS2,yS2)，…，(xSn,ySn),及他们到未知节点P的距离分别为d1，d2，…，dn.

可得以下的方程组:

(6)

化简为线性方程的形式:AX=b

(7)

通过极大似然估计法得到P的坐标估计值(xP,yP):

X*=(ATA)-1ATb

(8)

上述方法即利用极大似然估计法求解能够定位的未知节点坐标。

2.1.2DVHop定位

经过第一步的定位后,将求解出的未知节点升级为临时性信标节点,与原有的信标节点组成新的信标节点集合。采用DV-Hop算法对其余的未知节点进行粗略定位。

DV-Hop算法[13]根据节点间的最小跳数、平均每跳距离来估算未知节点坐标。节点间的最小跳数通过距离矢量路由协议确定,平均每跳距离可由公式(9)求得。

(9)

其中i、j为信标节点,(xi,yi)、(xj,yj)为这两个节点的坐标,hij为这两个节点间的跳段数,hopsizei表示信标节点i到其他信标节点的平均每跳的距离。

2.2 精确定位

经过第一步的初步定位,再利用改进布谷鸟搜索算法求解信标节点移动的目标位置,从而提高未知节点的定位覆盖率。

2.2.1 布谷鸟搜索算法

布谷鸟的Levy Flight随机搜索路径和鸟巢的位置更新公式如下:

⨁L(λ) ，

(10)

(11)

2.2.2 基于鱼群觅食因子的AF-CS算法

布谷鸟搜索算法采用Levy Flight随机搜索方式和偏差随机搜索方式生成新解,这使得算法在迭代过程中具有均衡的局部寻优和全局寻优能力[16]。布谷鸟搜索算法虽然有上述优点,但也同样存在算法后期容易陷入局部最优,收敛速度慢的问题。人工鱼群算法[17-18]是李晓磊博士受鱼群行为启发而提出的一种基于动物行为的群体智能优化算法。算法中觅食人工鱼个体的状态可表示为向量Xi=(x1,x2,…,xn),其中xi(i=1,2,…,n)为欲寻优变量;人工鱼个体当前所在位置的浓度为Y=f(X),其中Y为目标函数值;人工鱼个体之间的距离表示为dij=‖Xi-Yi‖;Visual表示人工鱼的感知距离;Step表示人工鱼移动的最大步长。尝试次数Try-number。

文中阐述了折臂式铁钻工底座回转机构工作原理为：电动机通过驱动轮带动行星轮将扭转力传递到回转轴承上进而实现了铁钻工整体的旋转运动，完成钻井上卸钻柱丝扣的工艺要求，并得出了以下结论：

鱼群觅食因子可以在解的感知范围内,通过当前解与前一位置解的比较,在尝试次数范围内筛选出最佳目标函数值,避免算法后期迭代陷入局部最优;同时,在保证感应位置比当前位置和前一位置优秀的共同前提下进行更新,减少了重复解或劣质解的无效迭代,提高了算法的收敛速度。

AF-CS算法步骤如下:

步骤1:将随机生成的初始目标位置作为输入种群的个体位置Xi(i=1,2,…,n),初始化参数,发现概率pa,最大迭代次数T,尝试次数Try-number,感知距离Visual。

步骤4:产生随机数r,让随机数r与发现概率pa做比较,若r>pa,则丢弃当前较差位置,利用公式(11)偏差随机搜索产生新解,并比较更新前后的目标函数值,保留目标函数值较好的鸟巢位置;否则保留当前最优位置。

步骤6:对筛选后的鸟巢位置与当前目标函数值最优的鸟巢位置进行比较,保留目标函数值最优的鸟巢位置。

步骤7:执行步骤3-步骤6,直到达到预先设定的迭代次数时终止,输出目标函数值最优的鸟巢位置。

2.3 定位算法步骤

具体的定位步骤如下:

步骤1:在边长为L米的正方形区域内随机部署n个未知节点与m个信标节点。

步骤2:未知节点接收周围信标节点的信号,统计接收到信号的数量,采用RSSI测距法对节点间的距离进行测量。

步骤3:采用极大似然估计法对能够定位的未知节点进行定位,并将这些未知节点升级为临时性信标节点。

步骤4:采用DV-Hop算法对其余的未知节点进行粗略定位,统计所有未知节点的坐标估计值,分别表示为(xs1,ys1) ,…,(xsn,ysn).

步骤5:调用AF-CS算法求解所有信标节点移动的目标位置。

步骤6:信标节点根据步骤5的求解结果,信标节点运动到目标位置上,对未知节点进行重定位。

步骤7:统计未知节点的定位结果,表示为(xz1,yz1),…,(xzn,yzn),算法结束。

3 仿真分析

为验证多移动信标节点定位算法的有效性,本文设计边长为100 m的正方形区域对移动前后的定位效果进行仿真实验,仿真软件是Matlab2010b。未知节点总数UN=200,最大迭代次数为T=200,发现概率pa=0.25,鱼群觅食因子尝试次数Try-number=30,人工鱼感知距离Visual=5 m。

3.1 信标节点移动对定位覆盖率的影响

3.1.1 信标节点数量与定位覆盖率

当未知节点通信半径R=30 m时,计算不同信标节点数量情况下信标节点移动前后对未知节点的定位覆盖率,对比见表1。

表1 信标节点数量与定位覆盖率

表1数据表明,信标节点对未知节点的定位覆盖率随节点布置数量的增加而增大;移动后信标节点对未知节点的精确定位覆盖率比移动前粗略定位覆盖率更高。

3.1.2 通信半径与定位覆盖率关系

当信标节点数量为25个时,计算不同通信半径情况下信标节点移动前后对未知节点的定位覆盖率,对比如图2。从图中可以看出，信标节点对未知节点的定位覆盖率随通信半径R的增大而增大;如通信半径R为25 m时,移动后信标节点对未知节点定位覆盖率为85.72%,比移动前提高了11.17%。图2表明,当通信半径相同时,移动后信标节点对未知节点的定位覆盖率比移动前定位覆盖率更高。

Fig.2 Relationship between communication radius and localization coverage图2 通信半径与定位覆盖率关系

Fig.3 Relationship between localization coverage and number of iterations图3 定位覆盖率与迭代次数关系

3.2 改进算法对定位覆盖率的影响

在信标节点数量为25个,通信半径为R=30 m时,AFCS算法与基本CS算法对未知节点的定位覆盖率对比如图3。从图中可以看出，在第190次迭代时,基本CS算法收敛的定位覆盖率为84.51%;而改进布谷鸟算法(AFCS)在第81次迭代后收敛,定位覆盖率为98.47%。改进布谷鸟算法AFCS加快了算法的收敛速度,提高了定位覆盖率。

3.3 信标节点目标位置分布

图4表示为通信半径R=15 m时,18个信标节点目标位置分布图。在此状态移动信标节点的定位覆盖率为31.22%;图5表示为通信半径R=25 m时,18个信标节点目标位置分布图,在此状态移动信标节点的定位覆盖率为80.57%。

Fig.4 Distribution of 18 target positions at R=15 m图4 R=15 m时18个目标位置分布

Fig.5 Distribution of 18 target positions at R=25 m图5 R=25 m时18个目标位置分布

4 结论

本文提出了一种基于改进布谷鸟搜索算法(AFCS)的多移动信标节点定位算法。该算法以对未知节点的定位覆盖率为目标函数,通过RSSI定位、DV-Hop算法和基于AFCS算法的移动信标节点两阶段定位过程,提高对未知节点的定位覆盖率。本文引入鱼群觅食因子改进布谷鸟搜索算法,有效改善了迭代后期因算法变异能力下降而陷入局部最优解的状态,继而提高了对未知节点的定位覆盖率,加快了算法的收敛速度。综上所述,该算法在网络拓扑结构改变时可通过信标节点的移动性保持对未知节点较高的定位覆盖率。