無線傳感器網絡中基于TDOA/FDOA的增強半正定松弛定位算法研究*

張 杰,王 剛

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

無線傳感器網絡是由具有無線通信能力的傳感器組成的以通信為中心的網絡。隨著國內外的無線技術的發展,無線傳感器網絡在軍事、智能交通、環境監控、醫療衛生等領域得到了廣泛應用[1]。其中,基于無線傳感器網絡的定位技術有著重要的研究價值,因此,基于無線傳感器網絡的定位技術成為了一個熱門的研究課題[2]。

根據無線傳感器接收到信號的不同特征,基于測距的定位方法主要有到達時間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定位是利用信號到達兩個無線傳感器上的時間差,不需要無線傳感器與目標之間有精確的時間同步,并且定位精度較高,因而本文采用基于TDOA的定位方法。然而,從TDOA的定位模型來看,其只包含未知目標的位置信息,因此只能用于精確定位靜止的未知目標。當目標和無線傳感器之間有相對移動時,通過加入FDOA信息也可以估計目標速度,并能進一步提高目標位置估計,這是由于FDOA定位模型中既包含位置信息又包含速度信息,因此,在移動無線傳感器定位環境中,可將TDOA與FDOA聯合起來共同估計未知目標的位置和速度,從而進一步提高定位精度。

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

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

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 優化問題

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

(6)

(7)

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

(8a)

(8b)

(8c)

(8d)

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

2.1 增強半正定松弛方法

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

命題 若在問題(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)

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

(13)

2.2 克拉美-羅下界(CRLB)

(14)

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

(15)

式中:

(16)

(17)

(18)

(19)

(20)

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

3 仿真結果

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

(21)

(22)

(23)

(24)

表1 傳感器的位置和速度

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

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

圖2 位置估計的偏差

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

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

圖4 速度估計的偏差

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

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

4 結論

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