基于天牛须搜索优化的TDOA三维节点定位算法*

苟平章, 孙梦源, 刘学治, 何 博

(西北师范大学 计算机科学与工程学院,甘肃 兰州 730070)

0 引 言

精确高效的节点定位是无线传感器网络(wireless sensor networks,WSNs)的研究热点之一[1]。为了进一步提高WSNs三维空间中节点的定位精度和性能,研究者通过填充矩阵推断未测量的距离信息,可过滤外部环境引起的噪声和异常,来提高定位的稳定性和准确性[2]。文献[3]通过MeanShift算法迭代计算出概率密度的最优解,达到对节点的精确定位。文献[4]采用向量化克拉美罗下界(Cramér-Rao lower bound,CRLB)作为布设优化策略,利用功效系数法优化布设策略,通过天牛须搜索(beetle antennae search,BAS)实现锚节点最优布设；文献[5]通过对测量到的接收信号强度(received signal strength,RSS)值进行拟合获取信号,计算出未知节点与接入点的距离,利用BAS算法实现未知节点定位。文献[6]通过减少未知节点距特定锚节点过远而造成的累积误差,利用已定位的未知节点,平衡网络的能量消耗。徐耀松等人采用改进拟牛顿—K最近邻(K-nearest neighbor,KNN)方法,在三维空间中减少系统定位的时间,提高定位求解速度[7]。

本文提出基于BAS优化的到达时间差(time difference of arrival,TDOA)三维节点定位算法(BASTDOA-3D)。以TDOA测距模型为基础,将计算未知节点与锚节点的距离时得到的数据通过Kalman滤波进行数据预处理；通过引入步长因子,在迭代计算时改变步长；采用BAS算法,利用最小适应度函数值计算未知节点的位置坐标,实现定位的快速精确收敛,提高定位精度和性能。

1 相关知识

1.1 TDOA测距模型

TDOA定位是一种利用时间差进行定位的方法[8],其思想为：首先获取TDOA所测不同传播速度的无线信号。通过获取的TDOA所测的时间差值确定基站间距离。发射节点同时发射无线射频信号和超声波信号,接收节点记录两种信号到达的时间t1,t2,已知无线射频信号和超声波的传播速度为c1,c2,则两点之间的距离为

d=(t2-t1)s

(1)

1.2 BAS算法

BAS算法仿照天牛的行为,设计该智能优化算法进行函数最优化求解[9～11]。BAS算法属于全局优化,迭代次数少。天牛在三维空间中采用如下模型搜索目标：

Step1 建立天牛须朝向的随机向量并做归一化处理

(2)

式中 rad(m,1)为m维空间随机函数,c为常数。

Step2 确定天牛左右须的坐标为

(3)

式中t=0,1,2,3,…,n,xr为天牛右须坐标,xl为天牛左须坐标,xt为天牛在第t次迭代质心坐标,d0为两须之间的距离。

Step3 通过适应度函数f(x)获取左右两须函数值,比较f(xl)与f(xr)的大小。

若f(xl)

xt+1=xt+j×normal(xl-xr)

(4)

若f(xl)>f(xr),则天牛向着右须方向行进步长j,此时天牛坐标为

xt+1=xt-j×normal(xl-xr)

(5)

式中t为迭代次数,xt为第t次迭代质心坐标,j为在第t次迭代的步长因子,normal(xl-xr)为归一化函数。

由式(4)和式(5)得出天牛的行进方向,同时更新天牛的位置

xt+1=xt-j×C×sign(f(xl)-f(xr))

(6)

式中 sign(f(xl)-f(xr))为符号函数。

2 BASTDOA-3D定位算法

2.1 TDOA数据预处理

在TDOA距离估计过程中,为了减小噪声的存在对时延估计精度的影响,本文选用Kalman滤波对接收到的数据进行预处理,从而减小测距误差。模型如下

X(t)=AX(t-1)+BU(t)+W(t)

(7)

Z(t)=HX(t)+V(t)

(8)

式中A和B为系统参数,X(t)为t时刻系统状态,Z(t)为t时刻的测量值,H为测量系统的参数,W和V分别为过程和测量的噪声。

根据Kalman滤波原理,计算出未知节点的实际TDOA步骤如下：

Step1 计算TDOA当前状态预估值y(t|t-1)

y(t|t-1)=Ay(t-1|t-1)+BU(t)+W(t)

(9)

Step2 更新估计误差协方差

P(t|t-1)=AP(t-1|t-1)A′+Q

(10)

式中A′为A的转置矩阵,Q为过程噪声的协方差。

Step3 更新Kalman增益Kg

(11)

式中H′为H的转置矩阵,R为观测噪声的协方差。

Step4 计算t时刻TDOA最优估计值

y(t|t)=y(t|t-1)+Kg(t)(Z(t)-Hy(t|t-1))

(12)

将式(9)代入式(12)中,得到

y(t|t)=y(t-1|t-1)+Kg(t)(Z(t)-

Hy(t-1|t-1))

(13)

Step5 计算t时刻的误差协方差

P(t|t)=(1-Kg(t)H)P(t|t-1)

(14)

根据以上步骤进行迭代,直至得到TDOA的最优值。

2.2 BAS算法优化

由于BAS算法求解精度对步长变化较为敏感,步长固定则会影响寻优结果的精度,甚至结果不收敛,因此,迭代时对步长加以改变。初始时,天牛飞行距离(步长)较大,较快地飞向目标点,加快收敛速度,此后逐渐减小步长,保证寻优精度。所以,在每一次迭代时,引入小于1的步长系数w,下一次迭代时的步长如下

jstep,next=j*w

(15)

式中j*为当前行进时的步长。

由式(15)可知,天牛飞行步长以一定比例不断减小。为了将步长系数调整平衡,采用如下线性递减策略

(16)

式中wmax,wmin分别为w的最大值和最小值；t,tmax分别为当前迭代次数和最大迭代次数。w设置为0.9～0.4的线性下降,使得BAS算法在开始时搜索较大的区域,较快地定位最优解的大致位置,随着w减小,步长速度减慢,开始精细的局部搜索。最后,将式(15)、式(16)代入式(6)中,得出天牛迭代改进后的行进方向,同时更新天牛的位置,得到式(17)

xt+1=xt-j*w(t)C×sign(f(xl)-f(xr))

(17)

2.3 节点坐标优化

将改进后的BAS算法引入节点定位中,未知节点通过收集邻居锚节点的位置信息,根据TDOA算法计算出未知节点与锚节点之间的距离,利用计算出的距离构造目标函数,然后使用BAS算法搜索目标函数最优解,即为未知节点的坐标值。若搜索空间是三维,假设未知节点P的估计坐标为(x,y,z),锚节点U1(x1,y1,z1),U2(x2,y2,z2),…,Un(xn,yn,zn)与未知节点通过TDOA测距计算出的距离为

di=(d1,d2,…,dn)

(18)

未知节点P与n(n≥3)个锚节点之间的误差为Ri

(19)

(20)

为了减小在计算过程中产生的累积误差,将方程变换为

(21)

式中 fitness(x,y)为BAS算法适应度函数,适应度函数值越小则定位误差越小。

定位算法流程如图1所示。

图1 BAS优化的定位算法流程

3 仿真实验与结果分析

3.1 仿真环境

为测试本文BASTDOA-3D算法的性能,将BASTDOA-3D算法与传统TDOA中的Chan和Taylor[12]算法的性能进行比较,通过不同的基站个数、区域半径、测量误差进行仿真。在MATLAB 2014中设定仿真区域半径R为3 km、测量误差标准差取80 m、迭代次数为80、且假设测量误差服从零均值高斯分布。定位结果根均方误差(root mean squared error,RMSE)计算公式为

(22)

式中 (x,y,z)为未知节点的实际位置,(X,Y,Z)为未知节点的测量位置。

3.2 仿真结果与分析

Chan算法在视距(line of sight,LOS)条件下,各方面性能优越；在非视距(non line of sight,NLOS)条件下,Chan算法定位精度稍低于Taylor级数展开法,但是稳定性更强[13]。

图2所示,基站数目为4时,Chan和Taylor算法均方根误差分别为90和80左右,BASTDOA-3D算法为55左右。随着基站数量的增加,Chan和Taylor算法的均方根误差趋于相近,而BASTDOA-3D算法一直明显低于Chan和Taylor算法,定位性能较好。

图2 不同基站个数下的定位性能

图3所示,当区域半径增大时,Chan和Taylor两种算法曲线稳定,均方根误差在60～70之间,而BASTDOA-3D算法定位误差从40增长到近50,低于Chan和Taylor算法。

图3 区域半径对定位性能影响

图4所示,在测量误差较小时三种算法性能相当,当测量误差从90增长到120时,Taylor算法误差稍微高于Chan算法,误差接近100,而BASTDOA-3D算法不仅将测量数据进行了预处理,还对定位算法进行了步长改进,所以测量误差一直增长稍慢,性能优于Chan和Taylor算法。

图4 测量误差对定位性能影响

4 结束语

本文对TDOA测得的数据经过Kalman滤波进行预处理的基础上,利用BAS算法的适应度函数计算未知节点,采用线性递减策略调整步长系数平衡,优化位置计算。仿真结果表明,BASTDOA-3D算法在定位精度和性能方面明显好于Chan算法和Taylor算法。