基于天牛須搜索優(yōu)化的TDOA三維節(jié)點(diǎn)定位算法*

茍平章, 孫夢(mèng)源, 劉學(xué)治, 何 博

(西北師范大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,甘肅 蘭州 730070)

0 引 言

精確高效的節(jié)點(diǎn)定位是無線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)的研究熱點(diǎn)之一[1]。為了進(jìn)一步提高WSNs三維空間中節(jié)點(diǎn)的定位精度和性能,研究者通過填充矩陣推斷未測(cè)量的距離信息,可過濾外部環(huán)境引起的噪聲和異常,來提高定位的穩(wěn)定性和準(zhǔn)確性[2]。文獻(xiàn)[3]通過MeanShift算法迭代計(jì)算出概率密度的最優(yōu)解,達(dá)到對(duì)節(jié)點(diǎn)的精確定位。文獻(xiàn)[4]采用向量化克拉美羅下界(Cramér-Rao lower bound,CRLB)作為布設(shè)優(yōu)化策略,利用功效系數(shù)法優(yōu)化布設(shè)策略,通過天牛須搜索(beetle antennae search,BAS)實(shí)現(xiàn)錨節(jié)點(diǎn)最優(yōu)布設(shè)；文獻(xiàn)[5]通過對(duì)測(cè)量到的接收信號(hào)強(qiáng)度(received signal strength,RSS)值進(jìn)行擬合獲取信號(hào),計(jì)算出未知節(jié)點(diǎn)與接入點(diǎn)的距離,利用BAS算法實(shí)現(xiàn)未知節(jié)點(diǎn)定位。文獻(xiàn)[6]通過減少未知節(jié)點(diǎn)距特定錨節(jié)點(diǎn)過遠(yuǎn)而造成的累積誤差,利用已定位的未知節(jié)點(diǎn),平衡網(wǎng)絡(luò)的能量消耗。徐耀松等人采用改進(jìn)擬牛頓—K最近鄰(K-nearest neighbor,KNN)方法,在三維空間中減少系統(tǒng)定位的時(shí)間,提高定位求解速度[7]。

本文提出基于BAS優(yōu)化的到達(dá)時(shí)間差(time difference of arrival,TDOA)三維節(jié)點(diǎn)定位算法(BASTDOA-3D)。以TDOA測(cè)距模型為基礎(chǔ),將計(jì)算未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的距離時(shí)得到的數(shù)據(jù)通過Kalman濾波進(jìn)行數(shù)據(jù)預(yù)處理；通過引入步長(zhǎng)因子,在迭代計(jì)算時(shí)改變步長(zhǎng)；采用BAS算法,利用最小適應(yīng)度函數(shù)值計(jì)算未知節(jié)點(diǎn)的位置坐標(biāo),實(shí)現(xiàn)定位的快速精確收斂,提高定位精度和性能。

1 相關(guān)知識(shí)

1.1 TDOA測(cè)距模型

TDOA定位是一種利用時(shí)間差進(jìn)行定位的方法[8],其思想為：首先獲取TDOA所測(cè)不同傳播速度的無線信號(hào)。通過獲取的TDOA所測(cè)的時(shí)間差值確定基站間距離。發(fā)射節(jié)點(diǎn)同時(shí)發(fā)射無線射頻信號(hào)和超聲波信號(hào),接收節(jié)點(diǎn)記錄兩種信號(hào)到達(dá)的時(shí)間t1,t2,已知無線射頻信號(hào)和超聲波的傳播速度為c1,c2,則兩點(diǎn)之間的距離為

d=(t2-t1)s

(1)

1.2 BAS算法

BAS算法仿照天牛的行為,設(shè)計(jì)該智能優(yōu)化算法進(jìn)行函數(shù)最優(yōu)化求解[9～11]。BAS算法屬于全局優(yōu)化,迭代次數(shù)少。天牛在三維空間中采用如下模型搜索目標(biāo)：

Step1 建立天牛須朝向的隨機(jī)向量并做歸一化處理

(2)

式中 rad(m,1)為m維空間隨機(jī)函數(shù),c為常數(shù)。

Step2 確定天牛左右須的坐標(biāo)為

(3)

式中t=0,1,2,3,…,n,xr為天牛右須坐標(biāo),xl為天牛左須坐標(biāo),xt為天牛在第t次迭代質(zhì)心坐標(biāo),d0為兩須之間的距離。

Step3 通過適應(yīng)度函數(shù)f(x)獲取左右兩須函數(shù)值,比較f(xl)與f(xr)的大小。

若f(xl)

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

(4)

若f(xl)>f(xr),則天牛向著右須方向行進(jìn)步長(zhǎng)j,此時(shí)天牛坐標(biāo)為

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

(5)

式中t為迭代次數(shù),xt為第t次迭代質(zhì)心坐標(biāo),j為在第t次迭代的步長(zhǎng)因子,normal(xl-xr)為歸一化函數(shù)。

由式(4)和式(5)得出天牛的行進(jìn)方向,同時(shí)更新天牛的位置

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

(6)

式中 sign(f(xl)-f(xr))為符號(hào)函數(shù)。

2 BASTDOA-3D定位算法

2.1 TDOA數(shù)據(jù)預(yù)處理

在TDOA距離估計(jì)過程中,為了減小噪聲的存在對(duì)時(shí)延估計(jì)精度的影響,本文選用Kalman濾波對(duì)接收到的數(shù)據(jù)進(jìn)行預(yù)處理,從而減小測(cè)距誤差。模型如下

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

(7)

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

(8)

式中A和B為系統(tǒng)參數(shù),X(t)為t時(shí)刻系統(tǒng)狀態(tài),Z(t)為t時(shí)刻的測(cè)量值,H為測(cè)量系統(tǒng)的參數(shù),W和V分別為過程和測(cè)量的噪聲。

根據(jù)Kalman濾波原理,計(jì)算出未知節(jié)點(diǎn)的實(shí)際TDOA步驟如下：

Step1 計(jì)算TDOA當(dāng)前狀態(tài)預(yù)估值y(t|t-1)

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

(9)

Step2 更新估計(jì)誤差協(xié)方差

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

(10)

式中A′為A的轉(zhuǎn)置矩陣,Q為過程噪聲的協(xié)方差。

Step3 更新Kalman增益Kg

(11)

式中H′為H的轉(zhuǎn)置矩陣,R為觀測(cè)噪聲的協(xié)方差。

Step4 計(jì)算t時(shí)刻TDOA最優(yōu)估計(jì)值

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 計(jì)算t時(shí)刻的誤差協(xié)方差

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

(14)

根據(jù)以上步驟進(jìn)行迭代,直至得到TDOA的最優(yōu)值。

2.2 BAS算法優(yōu)化

由于BAS算法求解精度對(duì)步長(zhǎng)變化較為敏感,步長(zhǎng)固定則會(huì)影響尋優(yōu)結(jié)果的精度,甚至結(jié)果不收斂,因此,迭代時(shí)對(duì)步長(zhǎng)加以改變。初始時(shí),天牛飛行距離(步長(zhǎng))較大,較快地飛向目標(biāo)點(diǎn),加快收斂速度,此后逐漸減小步長(zhǎng),保證尋優(yōu)精度。所以,在每一次迭代時(shí),引入小于1的步長(zhǎng)系數(shù)w,下一次迭代時(shí)的步長(zhǎng)如下

jstep,next=j*w

(15)

式中j*為當(dāng)前行進(jìn)時(shí)的步長(zhǎng)。

由式(15)可知,天牛飛行步長(zhǎng)以一定比例不斷減小。為了將步長(zhǎng)系數(shù)調(diào)整平衡,采用如下線性遞減策略

(16)

式中wmax,wmin分別為w的最大值和最小值；t,tmax分別為當(dāng)前迭代次數(shù)和最大迭代次數(shù)。w設(shè)置為0.9～0.4的線性下降,使得BAS算法在開始時(shí)搜索較大的區(qū)域,較快地定位最優(yōu)解的大致位置,隨著w減小,步長(zhǎng)速度減慢,開始精細(xì)的局部搜索。最后,將式(15)、式(16)代入式(6)中,得出天牛迭代改進(jìn)后的行進(jìn)方向,同時(shí)更新天牛的位置,得到式(17)

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

(17)

2.3 節(jié)點(diǎn)坐標(biāo)優(yōu)化

將改進(jìn)后的BAS算法引入節(jié)點(diǎn)定位中,未知節(jié)點(diǎn)通過收集鄰居錨節(jié)點(diǎn)的位置信息,根據(jù)TDOA算法計(jì)算出未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的距離,利用計(jì)算出的距離構(gòu)造目標(biāo)函數(shù),然后使用BAS算法搜索目標(biāo)函數(shù)最優(yōu)解,即為未知節(jié)點(diǎn)的坐標(biāo)值。若搜索空間是三維,假設(shè)未知節(jié)點(diǎn)P的估計(jì)坐標(biāo)為(x,y,z),錨節(jié)點(diǎn)U1(x1,y1,z1),U2(x2,y2,z2),…,Un(xn,yn,zn)與未知節(jié)點(diǎn)通過TDOA測(cè)距計(jì)算出的距離為

di=(d1,d2,…,dn)

(18)

未知節(jié)點(diǎn)P與n(n≥3)個(gè)錨節(jié)點(diǎn)之間的誤差為Ri

(19)

(20)

為了減小在計(jì)算過程中產(chǎn)生的累積誤差,將方程變換為

(21)

式中 fitness(x,y)為BAS算法適應(yīng)度函數(shù),適應(yīng)度函數(shù)值越小則定位誤差越小。

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

圖1 BAS優(yōu)化的定位算法流程

3 仿真實(shí)驗(yàn)與結(jié)果分析

3.1 仿真環(huán)境

為測(cè)試本文BASTDOA-3D算法的性能,將BASTDOA-3D算法與傳統(tǒng)TDOA中的Chan和Taylor[12]算法的性能進(jìn)行比較,通過不同的基站個(gè)數(shù)、區(qū)域半徑、測(cè)量誤差進(jìn)行仿真。在MATLAB 2014中設(shè)定仿真區(qū)域半徑R為3 km、測(cè)量誤差標(biāo)準(zhǔn)差取80 m、迭代次數(shù)為80、且假設(shè)測(cè)量誤差服從零均值高斯分布。定位結(jié)果根均方誤差(root mean squared error,RMSE)計(jì)算公式為

(22)

式中 (x,y,z)為未知節(jié)點(diǎn)的實(shí)際位置,(X,Y,Z)為未知節(jié)點(diǎn)的測(cè)量位置。

3.2 仿真結(jié)果與分析

Chan算法在視距(line of sight,LOS)條件下,各方面性能優(yōu)越；在非視距(non line of sight,NLOS)條件下,Chan算法定位精度稍低于Taylor級(jí)數(shù)展開法,但是穩(wěn)定性更強(qiáng)[13]。

圖2所示,基站數(shù)目為4時(shí),Chan和Taylor算法均方根誤差分別為90和80左右,BASTDOA-3D算法為55左右。隨著基站數(shù)量的增加,Chan和Taylor算法的均方根誤差趨于相近,而BASTDOA-3D算法一直明顯低于Chan和Taylor算法,定位性能較好。

圖2 不同基站個(gè)數(shù)下的定位性能

圖3所示,當(dāng)區(qū)域半徑增大時(shí),Chan和Taylor兩種算法曲線穩(wěn)定,均方根誤差在60～70之間,而BASTDOA-3D算法定位誤差從40增長(zhǎng)到近50,低于Chan和Taylor算法。

圖3 區(qū)域半徑對(duì)定位性能影響

圖4所示,在測(cè)量誤差較小時(shí)三種算法性能相當(dāng),當(dāng)測(cè)量誤差從90增長(zhǎng)到120時(shí),Taylor算法誤差稍微高于Chan算法,誤差接近100,而BASTDOA-3D算法不僅將測(cè)量數(shù)據(jù)進(jìn)行了預(yù)處理,還對(duì)定位算法進(jìn)行了步長(zhǎng)改進(jìn),所以測(cè)量誤差一直增長(zhǎng)稍慢,性能優(yōu)于Chan和Taylor算法。

圖4 測(cè)量誤差對(duì)定位性能影響

4 結(jié)束語

本文對(duì)TDOA測(cè)得的數(shù)據(jù)經(jīng)過Kalman濾波進(jìn)行預(yù)處理的基礎(chǔ)上,利用BAS算法的適應(yīng)度函數(shù)計(jì)算未知節(jié)點(diǎn),采用線性遞減策略調(diào)整步長(zhǎng)系數(shù)平衡,優(yōu)化位置計(jì)算。仿真結(jié)果表明,BASTDOA-3D算法在定位精度和性能方面明顯好于Chan算法和Taylor算法。