聯(lián)合TDOA-AOA無線傳感器網(wǎng)絡(luò)半定規(guī)劃定位算法研究*

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

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

聯(lián)合TDOA-AOA無線傳感器網(wǎng)絡(luò)半定規(guī)劃定位算法研究*

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

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

在無線傳感器網(wǎng)絡(luò)定位中,TDOA和AOA聯(lián)合定位可有效利用多種位置信息提高定位精度。由于傳統(tǒng)聯(lián)合加權(quán)最小二乘(WLS)的目標(biāo)函數(shù)非線性,在應(yīng)用于無線傳感器網(wǎng)絡(luò)定位時,會產(chǎn)生多個局部最優(yōu)解。因此,針對該問題本文將約束加權(quán)最小二乘問題轉(zhuǎn)化為二次約束二次規(guī)劃問題,之后通過引入半定松弛(SDR)方法將聯(lián)合定位問題轉(zhuǎn)換為低復(fù)雜度的半定規(guī)劃問題(SDP),進(jìn)而尋找全局最優(yōu)解。并且針對實際應(yīng)用中參考節(jié)點帶誤差的情形分析和推導(dǎo)了定位算法。與已有算法相比,提出的算法在參考節(jié)點無誤差和有誤差時都有更高的精度。此外,提出的SDP算法還能夠?qū)崿F(xiàn)只有兩個參考節(jié)點下的目標(biāo)定位。

無線傳感器網(wǎng)絡(luò);目標(biāo)定位;到達(dá)時間差;到達(dá)角度;半定規(guī)劃

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

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

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

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

1 定位場景及加權(quán)最小二乘算法

1.1TDOA分析

不失一般性的,將第1個節(jié)點作為到達(dá)時間差的參考節(jié)點,其他節(jié)點測量的相應(yīng)距離差可以表示為:

(1)

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

(2)

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

(3)

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

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

(4)

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

(5)

1.2AOA分析

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

(6)

式中:nθi為測量噪聲,相應(yīng)的真實測量角度為:

(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 聯(lián)合TDOA-AOA加權(quán)最小二乘法

考慮帶測量噪聲的全部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。此時未知節(jié)點的坐標(biāo)可以由加權(quán)最小二乘求解:

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

(18)

而:

W=E[eeT]=BQBT

(19)

(20)

Q為噪聲的協(xié)方差矩陣。

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

2 參考節(jié)點無誤差時的半定規(guī)劃(SDP)定位算法2.1 WLS算法的重構(gòu)

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

(21)

(22)

在對(22)中的目標(biāo)函數(shù)和約束條件即2范數(shù)進(jìn)行分解后,可以得到一個二次約束二次規(guī)劃問題:

(23)

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

2.2 聯(lián)合定位的半定規(guī)劃(SDP)算法

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

(24)

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

(25)

Z=zzT

(26)

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

(27)

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

式(27)將加權(quán)最小二乘轉(zhuǎn)換為一個帶線性等式約束和線性不等式約束的半定規(guī)劃問題。可以通過使用凸優(yōu)化中的內(nèi)點法IP(Interior Point)如SeDuMi[15]進(jìn)行求解,進(jìn)而得到聯(lián)合TDOA-AOA的凸優(yōu)化問題的最優(yōu)解,從而完成對目標(biāo)節(jié)點的定位。

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

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

設(shè)第i個帶誤差的參考節(jié)點位置為

(28)

ΔXi=(nxi,nyi)T

(29)

根據(jù)近似等價條件[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)

權(quán)矩陣可以表示為

(34)

(35)

(36)

(37)

(38)

(39)

(40)

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

(41)

(42)

(43)

4 SDP算法的仿真分析

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

(44)

4.1 參考節(jié)點無誤差的定位結(jié)果分析

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

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

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

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

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

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

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

4.2 參考節(jié)點有誤差的定位結(jié)果分析

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

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

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

5 結(jié)束語

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

[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定位算法非線性優(yōu)化問題研究[J]. 傳感技術(shù)學(xué)報,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] 駱吉安,譚智文,郭云飛. 聲納陣列網(wǎng)絡(luò)基于移動信標(biāo)到達(dá)角的漸進(jìn)最優(yōu)節(jié)點自定位算法[J]. 傳感技術(shù)學(xué)報,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-),男,碩士研究生,天津大學(xué)電氣自動化與信息學(xué)院,主要研究方向為無線傳感器網(wǎng)絡(luò)定位,zhangwenhua@tju.edu.cn;

于潔瀟(1981-),女,副教授,博士,天津大學(xué)電氣自動化與信息工程學(xué)院,主要研究方向為陣列信號處理,無線傳感器網(wǎng)絡(luò)定位技術(shù)等,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

項目來源:國家自然科學(xué)基金項目(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