無線傳感器網(wǎng)絡(luò)中基于TDOA/FDOA的增強半正定松弛定位算法研究*

張 杰,王 剛

(寧波大學(xué)信息科學(xué)與工程學(xué)院,浙江 寧波 315211)

無線傳感器網(wǎng)絡(luò)是由具有無線通信能力的傳感器組成的以通信為中心的網(wǎng)絡(luò)。隨著國內(nèi)外的無線技術(shù)的發(fā)展,無線傳感器網(wǎng)絡(luò)在軍事、智能交通、環(huán)境監(jiān)控、醫(yī)療衛(wèi)生等領(lǐng)域得到了廣泛應(yīng)用[1]。其中,基于無線傳感器網(wǎng)絡(luò)的定位技術(shù)有著重要的研究價值,因此,基于無線傳感器網(wǎng)絡(luò)的定位技術(shù)成為了一個熱門的研究課題[2]。

根據(jù)無線傳感器接收到信號的不同特征,基于測距的定位方法主要有到達時間TOA(Time-Of-Arrival)[3]、到達時間差TDOA(Time-Difference-Of-Arrival)[4]、接收信號強度(Receives-Signal-Strength)[5]、到達角度(Angle-of-Arrival)[6]、到達頻率差FDOA(Frequency-Difference-Of-Arrival)[7]等方法。由于TDOA定位是利用信號到達兩個無線傳感器上的時間差,不需要無線傳感器與目標(biāo)之間有精確的時間同步,并且定位精度較高,因而本文采用基于TDOA的定位方法。然而,從TDOA的定位模型來看,其只包含未知目標(biāo)的位置信息,因此只能用于精確定位靜止的未知目標(biāo)。當(dāng)目標(biāo)和無線傳感器之間有相對移動時,通過加入FDOA信息也可以估計目標(biāo)速度,并能進一步提高目標(biāo)位置估計,這是由于FDOA定位模型中既包含位置信息又包含速度信息,因此,在移動無線傳感器定位環(huán)境中,可將TDOA與FDOA聯(lián)合起來共同估計未知目標(biāo)的位置和速度,從而進一步提高定位精度。

在無線傳感器網(wǎng)絡(luò)定位問題中,基于TDOA/FDOA定位的難點在于其最大似然ML(Maximum Likelihood)估計問題是高度非線性和非凸的,而且未知目標(biāo)的位置和速度相互耦合,很難直接求解。對于該非線性、非凸問題,傳統(tǒng)的求解方法是通過泰勒展開式進行一階泰勒展開近似[8],該方法需要精確地初始估計值,若初始估計不夠精確,則該方法可能發(fā)散或者收斂到局部極小點。針對這個問題,人們提出了一些能獲得閉式解的方法[9-11]。在基于TDOA的兩步加權(quán)最小二乘Two-Stage WLS(Two-Stage Weighted Least Squares)方法[9]的基礎(chǔ)上,文獻[10]將此方法推廣到基于TDOA/FDOA的定位問題中,它在第1步中引入一個中間變量并忽略中間變量與目標(biāo)位置之間的關(guān)系來線性化非線性方程組,在第2步中考慮了上述中間變量與目標(biāo)位置之間已知的關(guān)系進一步提高第1步的定位精度。以上兩步都構(gòu)造求解了線性加權(quán)最小二乘WLS(Weighted Least Squares)問題。文獻[11]為文獻[10]的進一步推廣,理論分析了傳感器位置誤差對定位精度的影響,并提出了解決存在傳感器位置誤差時基于TDOA/FDOA定位的兩步加權(quán)最小二乘方法。上述閉式解方法雖然不存在發(fā)散問題,但在大噪聲時會出現(xiàn)定位性能急劇下降的現(xiàn)象,即“門限效應(yīng)”。為解決這一問題,文獻[12]提出了一種半正定松弛SDR(Semidefinite Relaxation)方法,它首先將初始ML問題近似為WLS問題,然后將WLS問題通過半正定松弛技術(shù)松弛為容易求解的半正定規(guī)劃SDP(Semidefinite Programming)問題。SDP問題是一個凸問題,理論上可以獲得全局最優(yōu)解,從而避免了局部收斂的問題。同時,由于半正定規(guī)劃問題為原問題的非線性近似,因此在大噪聲時仍然能獲得較高的定位精度。文獻[13]提出了兩種偏差減小的方法,即“Bias-Sub”方法和“Bias-Red”方法,其目的是減小上述兩步加權(quán)最小二乘方法的偏差,從而使“門限效應(yīng)”的噪聲方差門限值更大。文獻[14]提出了一種針對非線性加權(quán)最小二乘方法的偏差減小方法,由于非線性加權(quán)最小二乘方法的性能通常優(yōu)于兩步加權(quán)最小二乘方法,因此這種方法在大噪聲時獲得了更好的性能。最近,文獻[15]提出一種迭代約束加權(quán)最小二乘ICWLS(Iterative Constrained Weighted Least Squares)方法,其通過利用二次約束二次問題QCQP(Quadratically Constrained Quadratic Problem)公式的特殊結(jié)構(gòu)(目標(biāo)函數(shù)是凸的并且兩個約束條件是同樣形式的二次等式約束),將先前的估計代入二次等式約束二次項的一側(cè),近似得到兩個凸的線性等式約束,進而推導(dǎo)出了該近似問題的封閉形式解,并通過迭代不斷更新目標(biāo)的位置和速度,如此反復(fù)直至收斂。該方法能在收斂時收斂于全局最優(yōu)解,但其不能保證每一次蒙特卡洛運行時均收斂。

本文在無線傳感器網(wǎng)絡(luò)與未知目標(biāo)之間有相對移動的情況下研究了聯(lián)合TDOA/FDOA定位方法,在文獻[12]提出的半正定松弛方法的基礎(chǔ)上提出了一種增強型的半正定松弛方法,利用增強型的優(yōu)化方法有效改善了定位的精度。本文通過深度挖掘優(yōu)化變量之間的內(nèi)在聯(lián)系,并將這些聯(lián)系構(gòu)造成合理的約束條件,進而將這些非凸約束松弛成凸約束對半正定規(guī)劃問題進行收緊,求得了全局最優(yōu)解。文章理論證明了這些約束條件是有效的,起到了收緊半正定松弛規(guī)劃問題的作用。增強半正定規(guī)劃問題是一個凸優(yōu)化問題,它能找到近似WLS問題的全局最優(yōu)解,進而避免了收斂于局部極小點的情況。

1 半正定松弛方法

1.1 TDOA/FDOA定位模型

(1)

式中:c是信號傳播的速度,f0是載波的頻率,并且:

di=‖x-si‖-‖x-s0‖+ni,i=1,…,N

(2)

(3)

ri=‖x-si‖,i=0,…,N

(4)

(5)

1.2 優(yōu)化問題

在文獻[12]中,通過轉(zhuǎn)化測量模型(2)和(3),可以得到以下非線性加權(quán)最小二乘問題:

(6)

(7)

改寫式(7)中的目標(biāo)函數(shù),并對約束條件進行松弛,可得到半正定規(guī)劃問題[12]:

(8a)

(8b)

(8c)

(8d)

2 增強半正定松弛方法及克拉美-羅下界

2.1 增強半正定松弛方法

問題(8)即為文獻[12]中提出的半正定規(guī)劃問題,文獻[12]已經(jīng)理論證明了該問題中最優(yōu)解Y的秩最高為2,而近似WLS問題的最優(yōu)解的秩應(yīng)為1。顯然,由于松弛的影響,半正定規(guī)劃的解并不一定是近似WLS問題的最優(yōu)解。若要得到秩為1的解,一種自然的想法是通過加入其他有效約束來收緊該問題。觀察約束‖x-s0‖=r0(即y(2k+1)=‖y(1:k)-s0‖),其經(jīng)過松弛可變?yōu)椤瑇-s0‖≤r0,它涉及到優(yōu)化變量y之間的內(nèi)在聯(lián)系。一個自然的問題是,若在現(xiàn)有半正定規(guī)劃問題中加入此約束,能否起到收緊約束集的作用?下面的命題回答了這個問題。

命題 若在問題(8)中加入二階錐約束‖x-s0‖≤r0,能減小可行域。

(9)

另外,約束‖x-s0‖≤r0等價于:

y(2k+1)≥‖y(1:k)-s0‖

(10)

Y(2k+1,2k+1)≥‖Y(1:k,2k+1)-y(2k+1)s0‖

(11)

(12a)

(12b)

將挖掘到的隱含約束全部加入現(xiàn)有半正定規(guī)劃問題中,可得到增強半正定規(guī)劃問題:

(13)

2.2 克拉美-羅下界(CRLB)

(14)

式中:θo表示目標(biāo)的位置和速度的真實值。

(15)

式中:

(16)

(17)

(18)

(19)

(20)

將式(17)～式(20)帶入式(16)中,再將式(16)帶入式(15)中即可得到目標(biāo)的位置估計和速度估計的克拉美-羅下界。

3 仿真結(jié)果

為驗證本文所提出方法的性能,將本文的估計結(jié)果與迭代約束加權(quán)最小二乘法[15]、半正定松弛法[12]以及CRLB進行比較。在下文中,用“ICWLS”表示迭代約束加權(quán)最小二乘方法,用“ICWLS without SDP”表示迭代約束加權(quán)最小二乘方法在發(fā)散時未作任何處理的結(jié)果值,并用“SDP”表示現(xiàn)有半正定松弛方法。本文方法和SDP方法均由MATLAB工具箱CVX[16]求解。

(21)

(22)

(23)

(24)

表1 傳感器的位置和速度

圖1 位置估計的均方根誤差

在無線傳感器網(wǎng)絡(luò)中,對未知目標(biāo)位置估計的RMSE如圖1所示。從圖1可以看出,當(dāng)噪聲從小到中變化時,各方法的RMSE都能達到CRLB。但當(dāng)大噪聲時,SDP方法和ICWLS方法的RMSE有所增加,ICWLS without SDP方法的RMSE劇烈增加且遠遠偏離CRLB,而本文的方法在CRLB附近有輕微增長,但一直貼近CRLB。顯然,本文的方法具有最好的性能,并且ICWLS without SDP方法具有最差的性能。在高噪聲條件下,文中所提方法的RMSE略低于CRLB,說明此時定位性能受到噪聲影響,對位置的估計是有偏的。ICWLS和SDP方法的RMSE重合是因為前者在發(fā)散時運用了SDP的結(jié)果值作為最終估計值,此舉大大減小了估計誤差。在ICWLS方法中,經(jīng)統(tǒng)計,當(dāng)噪聲小于15 dB時,所有的點均收斂;當(dāng)噪聲為15 dB時,有3.63%的點發(fā)散;當(dāng)噪聲為20 dB時,有18.53%的點發(fā)散。這些發(fā)散的點運用SDP方法的估計結(jié)果作為最終的估計值,很大程度上提高了對未知目標(biāo)位置和速度的估計精度。位置估計的偏差如圖2所示,當(dāng)噪聲從低到高變化時,文中所提方法的偏差最小,而ICWLS without SDP的偏差最大。因此,本文提出的增強半正定松弛方法擁有最好的定位性能。

圖2 位置估計的偏差

圖3 速度估計的均方根誤差

對未知目標(biāo)速度估計的RMSE如圖3所示,當(dāng)噪聲低于10 dB時,各方法均能達到最優(yōu)的性能。當(dāng)噪聲高于10 dB時,本文方法的RMSE最小且最貼近CRLB,而其他方法的RMSE較大并且偏離CRLB。ICWLS without SDP方法的估計誤差最大,說明在發(fā)散時運用SDP的結(jié)果值可以極大地改善定位的性能。對未知目標(biāo)速度估計的偏差如圖4所示,當(dāng)噪聲較小時,3種方法的偏差都很小,其中,ICWLS和ICWLS without SDP方法的估計偏差最小,本文的方法和SDP方法有相同的偏差,當(dāng)噪聲逐漸增大至最大時,本文方法有最小的偏差。因此,本文的方法定位性能較好。

圖4 速度估計的偏差

噪聲大小/dB增強SDP/個數(shù)現(xiàn)有SDP/個數(shù)-203 0003 000-153 0003 000-103 0003 000-53 0003 00003 0003 00053 0003 000103 0003 000152 9602 930202 6742 530

為比較增強半正定規(guī)劃問題和現(xiàn)有的半正定規(guī)劃問題中滿足秩為1條件的解的個數(shù),我們對仿真結(jié)果作了統(tǒng)計,統(tǒng)計結(jié)果如表2所示。從表2可以看出,在小噪聲和中等噪聲時,兩種方法的解基本都滿足秩為1的條件,大噪聲時,兩方法中滿足條件的解的個數(shù)明顯有所下降,但增強半正定規(guī)劃問題滿足條件的解的個數(shù)明顯多于現(xiàn)有半正定規(guī)劃問題。其中,當(dāng)噪聲為15 dB時,增強半正定規(guī)劃問題有98.67%的解滿足條件,而現(xiàn)有半正定規(guī)劃問題只有97.67%的解滿足條件;當(dāng)噪聲為20 dB時,增強半正定規(guī)劃問題有89.13%的解滿足條件,而現(xiàn)有半正定規(guī)劃問題只有84.33%的解滿足條件。從這些統(tǒng)計數(shù)據(jù)可以看出,增強半正定規(guī)劃方法有效提高了滿足近似WLS問題的解的個數(shù),說明在增強半正定規(guī)劃方法中加入的約束條件起到了收緊原有半正定規(guī)劃問題的作用,提高了定位精度。因此,增強半正定規(guī)劃問題的估計結(jié)果比現(xiàn)有半正定規(guī)劃問題的估計結(jié)果更精確。

4 結(jié)論

本文考慮了無線傳感器網(wǎng)絡(luò)中未知目標(biāo)和傳感器之間有相對移動的目標(biāo)定位問題,提出了一種基于TDOA/FDOA的增強半正定松弛方法來估計移動未知目標(biāo)的位置和速度。在現(xiàn)有半正定規(guī)劃問題中挖掘了松弛后的半正定規(guī)劃問題中優(yōu)化變量之間的內(nèi)在聯(lián)系,并將這些聯(lián)系形成合理的凸約束,文中理論證明了這些約束是合理,能有效收緊現(xiàn)有半正定規(guī)劃問題,使得估計的未知目標(biāo)的位置和速度精度進一步提高。仿真結(jié)果和統(tǒng)計滿足秩為1的條件的解的個數(shù)均驗證了這些凸約束條件的合理性,說明本文提出的增強半正定松弛方法有最好的性能。