基于半定規(guī)劃的惡劣環(huán)境下定位修正算法*

劉 栓,劉直良

(黃淮學(xué)院信息工程學(xué)院,河南 駐馬店 463000)

?

基于半定規(guī)劃的惡劣環(huán)境下定位修正算法*

劉 栓*,劉直良

(黃淮學(xué)院信息工程學(xué)院,河南 駐馬店 463000)

無線傳感網(wǎng)絡(luò)WSNs(Wireless Sensor Networks)的定位精度嚴(yán)重受到環(huán)境的影響,尤其是高噪聲電平和非視距連接的惡劣環(huán)境,定位精度急劇下降。為此,提出基于半定規(guī)劃的惡劣環(huán)境下定位修正算法,記為ESDP_O算法。該修正算法以半定規(guī)劃 ESDP(Edge-Semi-Definite Programming)算法為基礎(chǔ),旨在提高定位精度,并降低算法復(fù)雜性,進(jìn)而減少定位時(shí)間。ESDP_O算法通過引用抖動(dòng)矩陣,對(duì)ESDP算法進(jìn)行修改,提高了算法在惡劣環(huán)境的健壯性。同時(shí),ESDP_O算法通過尋找低秩解,減少高噪聲和非視距偏差。仿真結(jié)果表明,在高噪聲和非視距NLOS(Non Line of Sight)的惡劣環(huán)境下,ESDP_O算法的定位精度優(yōu)于基于同類算法,并且降低了定位的復(fù)雜度。

無線傳感網(wǎng)絡(luò);定位;半定規(guī)劃;非視距;抖動(dòng)矩陣

傳感節(jié)點(diǎn)的位置在無線傳感網(wǎng)絡(luò)應(yīng)用中扮演了重要的作用[-3],如異常事件檢測、火災(zāi)感應(yīng)、目標(biāo)跟蹤等,這些應(yīng)用均需要獲取節(jié)點(diǎn)的位置信息[4-5]。為了獲取未知節(jié)點(diǎn)的位置信息,未知節(jié)點(diǎn)利用已知位置的節(jié)點(diǎn)(錨節(jié)點(diǎn))與自己距離,再結(jié)合定位算法,進(jìn)而估計(jì)自己的位置,其中測距是傳感網(wǎng)絡(luò)定位問題的關(guān)鍵。

針對(duì)傳感網(wǎng)絡(luò)定位問題,研究人員提出了許多不同方案[6-7]。文獻(xiàn)[6]中,作者提出了一種基于二階錐規(guī)劃的時(shí)差定位算法,該算法將位置估計(jì)轉(zhuǎn)化為二階錐規(guī)劃問題,再利用泰勒級(jí)數(shù)展開法估計(jì)節(jié)點(diǎn)位置。不少的研究人員也引用基于凸優(yōu)松弛技術(shù),將定位的非凸優(yōu)問題轉(zhuǎn)化為凸優(yōu)化問題,然后運(yùn)用凸優(yōu)化理論中的二階錐規(guī)劃SOCP(Second Order Cone Programming)[8-9]、半定規(guī)劃SDP(Semi-Definite Programming)松馳方法求解節(jié)點(diǎn)的位置。

然而,這些定位算法均假設(shè)測距是可視距LOS(Line Of Sight)環(huán)境,即節(jié)點(diǎn)間通信路徑為LOS連接。但是,在多數(shù)實(shí)際環(huán)境中,這個(gè)假設(shè)難以成立。由于障礙物的影響,多數(shù)連接是屬非視距NLOS(Non Line Of Sight)環(huán)境,并且也無法估計(jì)哪些連接是NLOS,哪些是LOS,這給傳感節(jié)點(diǎn)定位提出了挑戰(zhàn)。

為此,針對(duì)噪聲和存在NLOS的惡劣環(huán)境,提出基于邊半定規(guī)劃ESDP(Edge-Semi-Definite Programming)松馳優(yōu)化的定位修正算法ESDP_O。ESDP_O算法以ESDP算法為基礎(chǔ),再引用拉動(dòng)矩陣,求解低秩解,提高了在惡劣環(huán)境下定位的魯棒性,并降低算法的復(fù)雜度。仿真數(shù)據(jù)表明,提出的ESDP_O算法在惡劣的環(huán)境下,能夠較準(zhǔn)確地估計(jì)節(jié)點(diǎn)的位置,并降低定位復(fù)雜度。

1 定位模型及問題描述

假定傳感網(wǎng)絡(luò)由一系列的錨節(jié)點(diǎn)和普通傳感節(jié)點(diǎn)組成,其中n個(gè)傳感節(jié)點(diǎn),它們的位置未知,且分別表示為x1,…,xn;m個(gè)錨節(jié)點(diǎn),它們的位置已知,且分別表示為a1,…,am。傳感節(jié)點(diǎn)xi與xj間的距離表示為ds,ij,類似地,傳感節(jié)點(diǎn)xj與錨節(jié)點(diǎn)ak間歐式距離表示為da,jk。

無線傳感網(wǎng)絡(luò)二維定位問題可簡化為:

FindX∈R2×n

(1a)

(1b)

(1c)

Y=XTX

(1d)

式中:X=[x1,…,xn]、Ns={(j,i)|‖xj-xi‖

凸松弛技術(shù)是解決傳感網(wǎng)絡(luò)定位問題的有效方法。文獻(xiàn)[4]提出了半定規(guī)劃SDP松弛算法,將式(1)的非凸問題轉(zhuǎn)化為凸問題。為了獲取低秩(low rank)解,文獻(xiàn)[5]修改SDP。但是,與SDP相比,它并不能改善定位的準(zhǔn)確性。這些方案是將受限的式(1d)轉(zhuǎn)發(fā)為線性不等式LMI(Linear Matrix Inequality),如式(2)所示:

(2)

式中:In表示單位矩陣。

此外,與SDP相比,基于邊半定規(guī)劃ESDP松弛算法的復(fù)雜度下降,并且具有與SDP相同的定位準(zhǔn)確性[10]。利用ESDP松馳算法可解決式(1),因此可將式(1)轉(zhuǎn)化為式(3):

(3a)

s.t.Z(1,2),(1,2)=I2

(3b)

(3c)

(3d)

Z(1,2,i,j),(1,2,i,j)>0, ?(j,i)∈Ns

(3e)

α+,α-,β+,β-≥0

(3f)

式中:α+,α-,β+,β-分別為平方距離誤差。

Z(1,2,i,j),(1,2,i,j)是Z是子矩陣。文獻(xiàn)[11]提出基于邊的最大似然EML(Edge-based Maximum Likelihood)松馳算法,提高了ESDP松馳算法的性能。然而,文獻(xiàn)[4-11]所提出的方案均是基于所有節(jié)點(diǎn)均有可視距離LOS(Line of Sight)連接。然而,特別是室內(nèi)網(wǎng)絡(luò)的連接,多數(shù)是非視線距離NLOS(Non LOS)。

文獻(xiàn)[12-13]采用了基于SDP方案對(duì)傳感節(jié)點(diǎn)進(jìn)行定位。文獻(xiàn)[12]采用了SDP-M方案解決NLOS連接下的節(jié)點(diǎn)定位問題,也提高了定位的準(zhǔn)確性。但是,它是以假定NLOS連接是可識(shí)別的為前提。而這個(gè)假設(shè)在文獻(xiàn)[13]所提的情況是不合理的。文獻(xiàn)[13]針對(duì)無NLOS先前信息的情況下,提出了定位算法,并且不區(qū)分NLOS和LOS連接。文獻(xiàn)[13]采用式(4)所示的含有誤差的距離測量模型:

(4)

為此,本文針對(duì)高噪聲和NLOS偏差的環(huán)境下,提出基于ESDP的優(yōu)化魯棒定位算法ESDP_O。ESDP_O能夠獲取低秩解,并且引用新的基于SDP松馳算法,提高算法的魯棒性。同時(shí),ESDP_O算法是假定NLOS連接是未知的,并且考慮{bij}的統(tǒng)計(jì)也是未知,這更符合真實(shí)環(huán)境,旨在拓展ESDP_O算法的應(yīng)用場景,提高在惡劣環(huán)境下的定位精度。

2 ESDP_O算法

ESDP_O算法整合了SDP松馳技術(shù),旨在提高基于SDP定位方案在惡劣環(huán)境下的定位性能。測距是定位算法的關(guān)鍵。首先假定無誤差測距:

(5a)

(5b)

式中:Z(true)表示矩陣Z中無誤差的矩陣,ei為零列向量。

若存在測距噪聲的環(huán)境中,結(jié)合式(3c)和(3d),將式(5a)和(5b)轉(zhuǎn)換成式(6)所示:

(6a)

(6b)

(6c)

(6d)

式中:nij、δjk分別表示與ds,ij、da,jk相對(duì)應(yīng)的噪聲。Z(n)為Z的噪聲矩陣。

(7a)

(7b)

依據(jù)式(5)～式(7)可知,測距誤差容易引起矩陣Z的抖動(dòng),降低了定位的準(zhǔn)確性。因此,矩陣Z可表述為:

Z(n)=Z(true)+Δ

(8)

將式(7a)和(7b)求解式(3),可得:

(9a)

(9b)

ωs,ij≤0,?(j,i)∈NLs,ωa,jk≤0,?(j,k)∈NLa

(9c)

(9d)

(9e)

式中:S、u和ω分別表示式(3)問題的變量。NLs和NLa包含滿足式(7)的所有節(jié)點(diǎn)對(duì)。據(jù)于抖動(dòng)和靈敏性分析,依據(jù)文獻(xiàn)[14],可得:

(10)

(11a)

s.t. (3b),(3c),(3d),(3f),(7a),(7b)

(11b)

Z(1,2,i,j),(1,2,i,j)+P(1,2,i,j),(1,2,i,j)>0

?(i,j)∈Ns∪NLs

(11c)

注意到式(11)的對(duì)偶問題的約束與式(9)的約束相同。那么目標(biāo)函數(shù)如式(12)所示:

(12)

對(duì)式(11c)進(jìn)行松馳化,就能獲取式(3)的解,抵御Z(n)中的抖動(dòng)。注意到Z中的特征值是正數(shù),而式(11)中Z(1,2,i,j),(1,2,i,j)特征值是負(fù)數(shù)。擴(kuò)展定位問題的求解空間是為了獲取低秩解。

WSN定位所耗的時(shí)間取決于Z的秩。而低秩解有助于降低求解時(shí)間。因此,建立抖動(dòng)矩陣P的目的就是獲取低秩解。假定Z和{S(i,j)}是式(11)的解,且呈對(duì)偶性。據(jù)此可得:

(13)

式(13)的證明過程如下:

(14)

然后,構(gòu)建舒爾補(bǔ)(Schur complement)矩陣:

(15)

引用引理[12]:給定矩陣U∈Rm×n,且rank(U)≤q,有且只存在矩陣V=VT∈Rm×m、W=WT∈Rn×n,則:

(16)

證明完畢。

P(1,2,i,j),(1,2,i,j)=pijI4,?(j,i)∈Ns∪NLs

(17)

因此,式(12)可轉(zhuǎn)變?yōu)?

(18)

顯然,正確地選擇規(guī)范項(xiàng)是ESDP_O算法的關(guān)鍵。如果規(guī)范項(xiàng)過小,ESDP的解不受抖動(dòng)矩陣的影響。反之,若過大,tr(Y-XTX)的值也隨之增大,致使定位準(zhǔn)確度下降。因此,應(yīng)結(jié)合網(wǎng)絡(luò)尺寸和噪聲等級(jí)信息優(yōu)化參數(shù)pij的選擇。仿真結(jié)果表明,在測距存在誤差的環(huán)境下,規(guī)范項(xiàng)的選擇隨測距誤差變化,同時(shí),定位準(zhǔn)確度不隨節(jié)點(diǎn)數(shù)的變化而變化。

3 性能分析

3.1 仿真環(huán)境

本節(jié),通過仿真分析ESDP_O定位算法的性能,并利用MATLAB軟件內(nèi)凸優(yōu)化工具箱CVX[15]求解定位問題(式11)。采用3.07GHz的處理器、8GRAM的計(jì)算機(jī)實(shí)施仿真。

采用平均定位誤差A(yù)PE(Average Position Error)衡量算法的定位性能,定義如式(19)所示。

(19)

(20)

為了充分分析ESDP_O定位算法的性能,選用ESDP[10]、EML[11]、SDP-NLOS[12]進(jìn)行同步仿真,并進(jìn)行性能比較。

3.2 仿真結(jié)果分析

仿真過程中考慮不同的應(yīng)用場景,其中場景一、二考慮了NLOS環(huán)境,場景三、四考慮LOS環(huán)境。

3.2.1 場景1

本次仿真主要考查NLOS連接數(shù)占總的測距數(shù)的比率μN(yùn)對(duì)定位誤差和誤差的標(biāo)準(zhǔn)方差影響。仿真參數(shù)KE、無線傳輸半徑以及NLOS偏差的均值分別為0.1、6.0m以及5.0m。仿真結(jié)果如圖1所示。

圖1 μN(yùn)對(duì)定位性能的影響

由圖1(a)可知,平均定位誤差隨μN(yùn)的增加而上升,進(jìn)一步表明NLOS對(duì)測距存在負(fù)面影響。NLOS連接的存在,降低了測距的準(zhǔn)確性,進(jìn)而影響了定位的精度。與ESDP、EML和SDP-NLOS算法相比,ESDP_O算法的平均定位誤差得到明顯的下降,原因在于ESDP_O算法充分考慮了NLOS環(huán)境的存在,并且引用抖動(dòng)矩陣,提高算法應(yīng)對(duì)惡劣環(huán)境的能力。圖1(b)反映了各算法的平均標(biāo)準(zhǔn)方差,與圖1(a)數(shù)據(jù)相似,ESDP_O算法的平均標(biāo)準(zhǔn)方差最低,ESDP算法的平均標(biāo)準(zhǔn)方差最高。

3.2.2 場景2

本次仿真考查KE對(duì)定位誤差和誤差的標(biāo)準(zhǔn)方差影響。如式(4)所示,KE決定了測距誤差。噪聲值n=100,μN(yùn)=0.4。5個(gè)錨節(jié)點(diǎn)、無線傳播距離為4m,仿真結(jié)果如圖2所示。

由圖2(a)可知,KE的增加,降低定位精度。然而,與ESDP、EML和SDP-NLOS算法相比,ESDP_O算法受KE的波動(dòng)甚少,這也進(jìn)一步說明KE能夠應(yīng)對(duì)NLOS和大噪聲環(huán)境,具有魯棒性。圖2(b)描繪了平均標(biāo)準(zhǔn)方差隨KE的變化曲線。ESDP_O算法的平均標(biāo)準(zhǔn)方差最低,且在KE變化范圍內(nèi),波動(dòng)甚小。而ESDP、EML和SDP-NLOS算法隨KE呈增加趨勢,均高于ESDP_O算法。例如,在KE=10-1時(shí),ESDP算法的平均標(biāo)準(zhǔn)方差高達(dá)3.25m,EML、SDP-NLOS算法的平均標(biāo)準(zhǔn)方差分別2.5m、2.23m,而ESDP_O算法的平均標(biāo)準(zhǔn)方差僅為1.9m。

圖2 KE對(duì)定位性能的影響

3.2.3 場景3

本次場景是針對(duì)LOS環(huán)境,仿真區(qū)域?yàn)?0m×40m,錨節(jié)點(diǎn)數(shù)為15,本次仿真考慮兩類環(huán)境:一類(Case1)為噪聲值n=100、無線傳播距離r=6m、KE=0.005;另一類(Case2)為n=400、r=4 m、KE=0.5。Case2比Case1環(huán)境惡劣。各類算法的定位誤差如表1所示。

表1 LOS環(huán)境下的平均定位誤差

由表1可知,在Case1環(huán)境下,與ESDP、EML和SDP-NLOS相比,ESDP_O算法的定位性能并沒有得到改善,甚至略高于EML和SDP-NLOS。而在Case2環(huán)境下,ESDP_O算法的定位誤差低于ESDP、EML和SDP-NLOS算法。這些數(shù)據(jù)表明,提出的ESDP_O算法更適應(yīng)于惡劣環(huán)境。

3.2.4 場景4

本次實(shí)驗(yàn)旨在分析各類算法的復(fù)雜度,用算法的運(yùn)行時(shí)間表述。實(shí)驗(yàn)參數(shù):KE、r=6分別為0.1 m、6 m。錨節(jié)點(diǎn)數(shù)為5,所有連接均在LOS環(huán)境下,在n=100、200、300、400時(shí),各算法的運(yùn)行時(shí)間如表2所示。

表2 算法的運(yùn)行時(shí)間

由表2可知,在n從100變化至400區(qū)間,提出的ESDP_O算法的運(yùn)行時(shí)間最少,說明其復(fù)雜度比其他算法的低。換而言之,ESDP_O算法在提高惡劣環(huán)境下的定位精度的同時(shí),并沒有增加算法的復(fù)雜度。此外,由表2可知,n的增加提高了算法的運(yùn)行時(shí)間,增加定位的難度。

4 總結(jié)

針對(duì)無線傳感網(wǎng)絡(luò)的節(jié)點(diǎn)定位問題,提出了基于邊半定規(guī)劃ESDP(Edge-Semi-Definite Programming)松馳優(yōu)化的定位修正算法ESDP_O。ESDP_O算法著重考慮了非視距和噪聲的惡劣環(huán)境,以ESDP定位算法為基礎(chǔ),通過構(gòu)建抖動(dòng)矩陣,獲取低秩解,降低算法的復(fù)雜度,提高在惡劣環(huán)境下的定位精度,增強(qiáng)算法的魯棒性。針對(duì)不同的場景仿真,仿真結(jié)果表明,在惡劣環(huán)境下,提出的ESDP_O算法的復(fù)雜度和定位精度優(yōu)于SDP-NLOS、ESDP算法。

[1] 金家保,張頌,楊景曙. 一種基于二階錐規(guī)劃的新時(shí)差定位算法[J]. 電訊技術(shù),2012,52(6):887-893.

[2] 陶為戈,朱昳華,賈子彥. 基于RSSI混合濾波和最小二乘參數(shù)估計(jì)的測距算法[J]. 傳感技術(shù)學(xué)報(bào),2012,25(12):1748-1753.

[3] 程秀芝,朱達(dá)榮,張申,等. 基于RSSI差分校正的最小二乘法-擬牛頓定位算法[J]. 傳感技術(shù)學(xué)報(bào),2014,27(1):123-128.

[4] Biswas P,Ye Y.Semidefinite Programming for ad hoc Wireless Sensor Network Localization[C]//Proc 3rd Int Symp Inf Process Sens Netw(ITPN’04),Apr. 2004:46-54.

[5] Ji S,Sze K F,Zhou Z,et al. Beyond Convex Relaxation:A Polynomial-Time Non-Convex Optimization Approach to Network Localization[C]//Proc IEEE INFOCOM,Apr. 2013:2499-2507.

[6] 王其華,郭戈. 基于到達(dá)時(shí)間差的半定松馳規(guī)劃優(yōu)化的定位算法[J]. 大連海事大學(xué)學(xué)報(bào),2013,39(4):59-64.

[7] 時(shí)潔,楊德森,時(shí)勝國. 二階錐規(guī)劃在噪聲源健定位識(shí)別中的應(yīng)用[J]. 哈爾濱工程大學(xué)學(xué)報(bào),2011,32(12):1549-1558.

[8] Srirangarajan S,Tewfik A,Luo Z Q. Distributed Sensor Network Localization Using SOCP Relaxation[J]. IEEE Trans Wireless Commun,2008,7(12):4886-4895.

[9] Tseng P. Second-Order Cone Programming Relaxation of Sensor Network Localization[J]. SIAM J Optimization,2007,18(1):156-185.

[10] Wang Z,Zheng S,Ye Y,et al. Further Relaxations of the Semidefinite Programming Approach to sensor Network Localization[J]. SIAM J Optim,2008,19(2):655-673.

[11] Simonetto A,Leus G. Distributed Maximum Likelihood Sensor Network Localization[J]. IEEE Trans Signal Process,2014,62(6):1424-1437.

[12] Vaghefi R,Buehrer R. Cooperative Sensor Localization with NLOS Mitigation Using Semidefinite Programming[C]//Proc 9th Workshop Position Navigat Commun(WPNC’12),2012:13-18.

[13] Monir Vaghefi R,Buehrer M. Cooperative Localization in NLOS Environments Using Semidefinite Programming[J]. IEEE Commun Lett,2015,19(8):1382-1385.

[14] Boyd S,Vandenberghe L.Convex Optimization[M]. Cambridge,UK:Cambridge Univ Press,2004.

[15] Grant M,Boyd S,Ye Y. CVX:MATLAB Software for Disciplined Convex Programming[online]. Available:http://www.stanford.edu/～boyd/cvx. 2009.

Research on Semidefinite Programming Localization Enhancement in Complex NLOS Wireless Sensor Network Environment*

LIU Shuan*,LIU zhiliang

(College of Information Engineering,Huanghuai University,Zhumadian He’nan 463000,China)

The accuracy of localization in wireless sensor networks(WSNs)depends on noise level and the presence of nonline of sight(NLOS)connections. In this letter,a novel Edge semidefinite programming(ESDP)Robust localization algorithm is proposed and its goal is to improve the accuracy and reduce the algorithm complexity,and it reduce the required time for wireless sensor network localization in harsh environments,which is marked as ESDP_O. We modified ESDP relaxation by a perturbation matrix in order to make it robust against large errors in distance measurements. ESDP_O algorithm modified ESDP in order to find a low rank solution,and introduced a new class of ESDP-based relaxation that is robust against high level noise and NLOS biases. Simulation results confirm that our proposed method outperforms others when the majority of connections are NLOS,noise level is high,and the proposed ESDP_O algorithm can effectively reduce the computational complexity.

wireless sensor network;localization;semi-definite programming;nonline of sight;perturbation matrix

劉 栓(1978-),男,碩士,黃淮學(xué)院信息工程學(xué)院講師,主要研究方向?yàn)橹悄苄畔⑻幚?、圖像處理;

劉直良(1982-),男,碩士,黃淮學(xué)院信息工程學(xué)院講師,主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)。

項(xiàng)目來源:河南省科技廳重點(diǎn)攻關(guān)計(jì)劃項(xiàng)目(9412015Y1305);國家自然科學(xué)基金項(xiàng)目(U1404602)

2016-10-21 修改日期:2017-01-09

TPT393

A

1004-1699(2017)05-0766-06

C:7230

10.3969/j.issn.1004-1699.2017.05.022