聯合TDOA-AOA無線傳感器網絡半定規劃定位算法研究*

張文華,于潔瀟*,劉開華,趙 宇

(1.天津大學電氣自動化與信息工程學院,天津 300072;2.天津大學微電子學院,天津 300072)

聯合TDOA-AOA無線傳感器網絡半定規劃定位算法研究*

張文華1,于潔瀟1*,劉開華2,趙 宇1

(1.天津大學電氣自動化與信息工程學院,天津 300072;2.天津大學微電子學院,天津 300072)

在無線傳感器網絡定位中,TDOA和AOA聯合定位可有效利用多種位置信息提高定位精度。由于傳統聯合加權最小二乘(WLS)的目標函數非線性,在應用于無線傳感器網絡定位時,會產生多個局部最優解。因此,針對該問題本文將約束加權最小二乘問題轉化為二次約束二次規劃問題,之后通過引入半定松弛(SDR)方法將聯合定位問題轉換為低復雜度的半定規劃問題(SDP),進而尋找全局最優解。并且針對實際應用中參考節點帶誤差的情形分析和推導了定位算法。與已有算法相比,提出的算法在參考節點無誤差和有誤差時都有更高的精度。此外,提出的SDP算法還能夠實現只有兩個參考節點下的目標定位。

無線傳感器網絡;目標定位;到達時間差;到達角度;半定規劃

由于無線傳感器網絡(WSNs)在無線通信,室內定位和水聲傳感器網絡(UASN)[1]等領域的重要應用,精確的無線傳感器網絡定位算法近年來受到了廣泛的關注。針對接收信號的不同特征參數,基于測距的定位方法主要有RSS(Received Signal Strength)[2],TOA(Time Of Arrival)[3],TDOA(Time Difference Of Arrival)[4]和AOA(Angle Of Arrival)[5-6]4種方法。對于不同的定位場景和精度要求可以選擇相應的定位算法。然而,在非視距(NLOS)或參考節點有限的復雜環境下,使用上述算法之一與精確定位的要求相去甚遠。因此,聯合定位算法的研究逐漸受到重視。

為了提高復雜環境下的定位精度,相應的聯合定位算法有TOA-AOA[7]、AOA-RSS[8]以及TDOA-AOA。在上述算法中,相對于TDOA-AOA,TOA-AOA算法需要高精度的時間同步,而AOA-RSS易受到衰落效應的影響[9]。本文研究TDOA-AOA聯合定位算法。為了提高TDOA-AOA聯合定位的精度,Li等[10]提出了二維空間中聯合TDOA-AOA兩步加權最小二乘(Two-Step LS)定位算法,其算法精度高于單獨使用TDOA的定位精度。Cheung等[11]通過使用聯合TDOA-AOA約束加權最小二乘法(CWLS)定位移動基站,但是當參考基站少于4個時其定位性能急劇下降甚至算法失效。Yin等[12]提出了兩基站下基于TDOA-AOA的定位閉式解,然而,該方法只能用于三維空間的定位,且受限于權矩陣的秩和條件數,其定位魯棒特性較差。上述算法都只是局部優化算法,并不能保證找到全局最優解。

由于目標位置與測量值之間的非線性和非凸性關系,無線傳感器網絡定位問題的求解較為復雜。而用于求解定位的最小二乘(LS)和最大似然(ML)估計方法并不能保證獲得全局最優解。凸優化(Convex Optimization)是數學最優化的一個子領域,研究定義于凸集中的凸函數最小化的問題,能用于尋找全局最優解。因此,可以通過引入凸松弛(SDR)方法,將NLS或ML問題松弛為等效的半定規劃(SDP)問題,進而獲取全局最優解。近年來,SDP算法開始用于基于測距的定位問題中[13]。但是在TDOA-AOA聯合定位算法中還缺乏探索。

本文通過研究二維空間的聯合TDOA-AOA加權最小二乘算法,提出一種新的基于半定規劃(SDP)的凸優化算法。第2節建立了定位場景,并推導了聯合WLS算法;第3節將其轉化為等效的二次規劃問題,之后通過引入冗余變量和SDR技術將二次規劃問題轉換成SDP凸優化問題。第4節對參考節點帶誤差的定位進行了推導,并提出了相應的凸優化算法。通過第5節的仿真結果可以證明本文SDP定位算法的優越性。

1 定位場景及加權最小二乘算法

1.1TDOA分析

不失一般性的,將第1個節點作為到達時間差的參考節點,其他節點測量的相應距離差可以表示為:

(1)

式中:ndi表示測量噪聲。則真實距離差可以表示為:

(2)

而測量所得的時間差可以表示為:

(3)

式中:c為信號傳播速度。為了簡化公式,全文使用式(1)中的距離差進行推導。

不考慮測量誤差,(1)中的ri可以表示為:

(4)

式(4)兩邊平方并作等價代換x-xi=(x-x1)-(xi-x1),可以得到

(5)

1.2AOA分析

角度測量值可以表示為式(6):

(6)

式中:nθi為測量噪聲,相應的真實測量角度為:

(7)

不考慮測量噪聲,(6)可表示為:

xsinθi-ycosθi=xisinθi-yicosθi

(8)

兩端同時加y1cosθi-x1sinθi可得[11]

(x-x1)sinθi-(y-y1)cosθi=(xi-x1)sinθi-(yi-y1)cosθi

(9)

1.3 聯合TDOA-AOA加權最小二乘法

考慮帶測量噪聲的全部TDOA和AOA測量值,可以得到[11]

Gdz=hd-ed

(10)

Gθz=hθ-eθ

(11)

式中

(12)

(13)

(14)

(15)

(16)

通過將式(2)、式(7)分別代入式(10)、式(11),忽略噪聲二次項,可以分別得到edi≈dindi和eθi=disinnθi≈dinθi。

將式(10)和式(11)合并可得

Gz=h-e

(17)

式中:G=[GdGθ]T,h=[hdhθ]T,e=[edeθ]T。此時未知節點的坐標可以由加權最小二乘求解:

z=(GTW-1G)-1GTW-1h

(18)

而:

W=E[eeT]=BQBT

(19)

(20)

Q為噪聲的協方差矩陣。

在實際定位中,式(18)中的權矩陣W未知,其具體數值需要由未知節點的真實位置確定。在這里我們可以先使用單位矩陣代替W進行初始位置估計,之后使用初始化的位置信息通過(19)計算權矩陣。仿真結果顯示一次迭代就能實現定位,多次迭代并不會有實質性提升。

2 參考節點無誤差時的半定規劃(SDP)定位算法2.1 WLS算法的重構

式(18)的加權最小二乘估計可以等效地寫為:

(21)

(22)

在對(22)中的目標函數和約束條件即2范數進行分解后,可以得到一個二次約束二次規劃問題:

(23)

式中:Σ=diag(1,1,-1,0)。

2.2 聯合定位的半定規劃(SDP)算法

式(23)中:目標函數和約束條件都是非線性的,這里可以通過引入冗余變量Z=zzT,其中

(24)

使用基本性質xTAx=tr{xxTA},式(23)可以被等效為新的約束優化問題:

(25)

Z=zzT

(26)

式(26)的約束條件非凸,可以使用半定松弛(SDR)技術,即等效為兩個條件:rank(Z)=1和Z為對稱半正定(PSD)矩陣,通過松弛秩約束,可以獲得如下SDP凸優化問題[14]

(27)

式中:±表示半正定運算符。

式(27)將加權最小二乘轉換為一個帶線性等式約束和線性不等式約束的半定規劃問題。可以通過使用凸優化中的內點法IP(Interior Point)如SeDuMi[15]進行求解,進而得到聯合TDOA-AOA的凸優化問題的最優解,從而完成對目標節點的定位。

3 參考節點有誤差時的半定規劃(SDP)定位算法

在無線傳感器網絡的構建和應用中,參考節點的真實位置不一定已知,為了節約能量消耗,其位置也是由測量或者其他定位方案獲得,存在一定的誤差,因而會對未知節點的定位精度產生影響。本節通過分析誤差項并引入SDP算法減小位置誤差對定位精度的影響。

設第i個帶誤差的參考節點位置為

(28)

ΔXi=(nxi,nyi)T

(29)

根據近似等價條件[16],可得

(30)

式中:ρa,b=(a-b)/‖a-b‖表示從b指向a的單位向量。將(28)、(30)代入(10),保留Δxi的線性項,有

(31)

(32)

式中:εθi=[sinθicosθi]ΔXi,(i=1,…,N)

合并式(31)和式(32)得

(33)

權矩陣可以表示為

(34)

(35)

(36)

(37)

(38)

(39)

(40)

與上一節類似,我們可以推導出參考節點有誤差時的半定規劃(SDP)定位算法:

(41)

(42)

(43)

4 SDP算法的仿真分析

本節中我們將通過MATLAB對提出的聯合定位算法進行2 000次蒙特卡洛仿真試驗,并與已有的二維空間TDOA-AOA聯合定位算法進行對比。使用位置均方根誤差(RMSE)來對算法進行對比評價。RMSE的表達式如下。

(44)

4.1 參考節點無誤差的定位結果分析

首先考慮有5個參考節點,其坐標分別是(0,0)m,(260,150)m,(0,300)m,(-260,150)m 和(200,-150)m。待定位目標節點位于(50,100)m。圖1為3種算法隨TDOA測量距離方差σd的變化曲線圖,其中AOA角度方差固定為σθ=1°。從圖1可以看出,在TDOA方差較小時,SDP算法明顯好于CWLS算法,與two-step LS基本一致,而在TDOA方差較大時,本文中的算法定位性能明顯優于其他兩種算法。圖2中固定σd=3 m,3種算法隨AOA測量角度方差σθ的變化情況。可以很直觀地看出本文提出的算法定位效果最好。

圖1 角度方差為1°時不同算法的定位性能比較

圖2 距離方差為3 m時不同算法的定位性能比較

為了更有效地說明本文算法定位特性優于其他算法,我們進行了CDF曲線對比,如圖3所示,其中設定σθ=1°,σd=3 m。從圖中可以看出,在進行的2 000次仿真實驗中,本文所提算法定位誤差在2 m以內的概率接近80%,高于其他算法的60%,因此可以證明本文定位算法魯棒性更好。

圖3 不同算法估計誤差的CDF曲線圖

接著我們分析SDP算法在節點通信性能下降時的定位效果,考慮兩參考節點下對目標節點的定位,參考節點位置設在(0,0)m和(260,150)m,待定位節點位置不變。此時,由于CWLS中拉格朗日乘子法在兩節點下無法求得實根,算法失效;而Two-Step LS不能解出待定位節點坐標。圖4為本文算法分別在角度測量方差為σθ=1°和σθ=3°時,隨TDOA方差的變化曲線圖。從中可以看出在即使在測量誤差較大時,本文算法的RMSE也能控制在10 m內。

圖4 兩參考節點下所提算法的定位性能

4.2 參考節點有誤差的定位結果分析

為了對參考節點有位置誤差的定位效果進行分析,在參考節點真實位置加高斯白噪聲,假設TDOA和AOA測量誤差分別為σd=1 m和σθ=1°。

圖5 不同算法隨參考節點誤差變化的定位性能比較

圖6 兩帶誤差參考節點下所提算法的定位性能

5 結束語

本文針對TDOA-AOA聯合定位中傳統加權最小二乘算法的非線性,通過閉式法求解會產生多個局部最優值的問題,提出一種基于SDP的凸優化定位方法。首先分析了傳統的WLS聯合定位算法;接著,通過推導將問題轉化為非凸二次優化問題,之后引入冗余變量和SDR技術將問題轉化為SDP凸優化問題,通過求解從而實現精確定位;同時,分析和推導了實際應用中參考節點有位置誤差的情形。從仿真結果圖中可以看出,本文算法在參考節點數目較多時定位精度高于已有算法,在僅有兩個參考節點提供位置信息時,經典算法如Two-step LS和CWLS都失效,而本文算法還能夠實現較高精度下的定位。

[1] Emokpae L E,DiBenedetto S,Potteiger B,et al. UREAL:Underwater Reflection-Enabled Acoustic-Based Localization[J]. IEEE Sensors Journal,2014,14(11):3915-3925.

[2] Tomic S,Beko M,Dinis R. RSS-Based Localization in Wireless Sensor Networks Using Convex Relaxation:Noncooperative and Cooperative Schemes[J]. IEEE Transactions on Vehicular Technology,2015,64(5):2037-2050.

[3] 姜志鵬,陳正宇,劉影,等. TOA定位算法非線性優化問題研究[J]. 傳感技術學報,2015(11):1716-1719.

[4] Qiao T,Redfield S,Abbasi A,et al. Robust Coarse Position Estimation for TDOA Localization[J]. IEEE Wireless Communication Letters,2013,2(6):623-626.

[5] Shao H J,Zhang X P,Wang Z. Efficient Closed-Form Algorithms for AOA Based Self-Localization of Sensor Nodes Using Auxiliary Variables[J]. IEEE Transactions on Signal Processing,2014,62(10):2580-2594.

[6] 駱吉安,譚智文,郭云飛. 聲納陣列網絡基于移動信標到達角的漸進最優節點自定位算法[J]. 傳感技術學報,2016,29(3):403-410.

[7] Liu D,Liu K,Ma Y,et al. Joint TOA and DOA Localization in Indoor Environment Using Virtual Stations[J]. IEEE Communica-tions Letters,2014,18(8):1423-1426.

[8] Yang S H,Kim H S,Son Y H,et al. Three-Dimensional Visible Light Indoor Localization Using AOA and RSS with Multiple Optical Receivers[J]. Journal of Lightwave Technology,2014,32(14):2480-2485.

[9] Chan Y T,Chan F,Read W,et al. Hybrid Localization of an Emitter by Combining Angle-of-Arrival and Received Signal Strength Measurements[C]//IEEE 27th Canadian Conference on Electrical and Computer Engineering(CCECE),Toronto,ON,2014:1-5.

[10] Li C,Weihua Z. Hybrid TDOA/AOA Mobile User Location for Wideband CDMA Cellular Systems[J]. IEEE Transactions on Wireless Communications,2002,1(3):439-447.

[11] Cheung K W,So H C,Ma W K,et al. A Constrained Least Squares Approach to Mobile Positioning:Algorithms and Optimality[J]. EURASIP Journal on Advances in Signal Processing,2006,2006:1-24.

[12] Yin J,Wan Q,Yang S,et al. A Simple and Accurate TDOA-AOA Localization Method Using Two Stations[J]. IEEE Signal Processing Letters,2016,23(1):144-148.

[13] Chan F K W,So H C,Ma W K,et al. A Flexible Semi-Definite Programming Approach for Source Localization Problems[J]. Digital Signal Processing,2013,23(2):601-609.

[14] Luo Z,Ma W,So A,et al. Semidefinite Relaxation of Quadratic Optimization Problems[J]. IEEE Signal Processing Magazine,2010,27(3):20-34.

[15] Sturm J F. Using SeDuMi 1.02,a MATLAB Toolbox for Optimization over Symmetric Cones[J]. Optimization Methods and Software,1999,11(1-4):625-653.

[16] Liu Y,Guo F,Yang L,et al. An Improved Algebraic Solution for TDOA Localization with Sensor Position Errors[J]. IEEE Communications Letters,2015,19(12):2218-2221.

張文華(1991-),男,碩士研究生,天津大學電氣自動化與信息學院,主要研究方向為無線傳感器網絡定位,zhangwenhua@tju.edu.cn;

于潔瀟(1981-),女,副教授,博士,天津大學電氣自動化與信息工程學院,主要研究方向為陣列信號處理,無線傳感器網絡定位技術等,yjx@tju.edu.cn。

JointTDOA-AOASourceLocalizationinWirelessSensorNetworksUsingSemidefiniteProgramming*

ZHANGWenhua1,YUJiexiao1*,LIUKaihua2,ZHAOYu1

(1.School of Electrical and Information Engineering,Tianjin University,Tianjin 300072,China; 2.School of Microelectronics,Tianjin University,Tianjin 300072,China)

Joint TDOA-AOA localization is able to improve location estimation accuracy through utilizing all the available information in wireless sensor networks(WSNs). Due to the non-linearity of the equations,joint weighted least square(WLS)may converge to local optimum solution when applied to wireless sensor networks localization. Therefore,by applying semidefinite relaxation(SDR)to the quadratically constrained quadratic program problem which is derived from WLS method,we transformed the joint localization problem into a low complexity semidefinite programming(SDP)problem to find the global optimum solution. Localization in the presence of sensor position errors has also been studied. Simulation results show that,compared with the existing approaches,the proposed approach has higher accuracy whether with or without sensor position errors. Furthermore,the proposed SDP method still has good performance with only two sensors offering location information.

wireless sensor networks;source localization;TDOA;AOA;semidefinite programming

項目來源:國家自然科學基金項目(61501322)

2017-02-16修改日期:2017-04-17

TP393.0

:A

:1004-1699(2017)09-1375-06

10.3969/j.issn.1004-1699.2017.09.013