非同步網(wǎng)絡(luò)中基于TOA的魯棒非視距目標(biāo)自定位算法*

朱偉辰,王 剛

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

近年來,各種定位技術(shù)在我們的日常生活中發(fā)揮了重要作用。目標(biāo)定位的應(yīng)用包括導(dǎo)航,目標(biāo)跟蹤,救援,航空航天等[1-4]。基于到達(dá)時(shí)間(Time-of-Arrival,TOA)的定位方法具有較高的定位精度,在實(shí)際環(huán)境中十分常用。本文考慮構(gòu)造目標(biāo)源自定位問題[5],錨節(jié)點(diǎn)在同一未知時(shí)間向目標(biāo)源發(fā)送信號(hào),目標(biāo)源依靠接收信號(hào)測(cè)量TOA[6]。在這個(gè)問題中,目標(biāo)源不向錨節(jié)點(diǎn)發(fā)送信號(hào),因而節(jié)省了能量并延長(zhǎng)了目標(biāo)源的電池壽命。而且,本方法不要求目標(biāo)源和錨節(jié)點(diǎn)之間保持時(shí)間同步[7]。

傳感器網(wǎng)絡(luò)中的時(shí)間同步問題對(duì)目標(biāo)定位的精度有著不可忽略的影響,近些年來該問題已經(jīng)得到了學(xué)界的廣泛研究[6-11]。在文獻(xiàn)[6]中通過目標(biāo)源接收來自其他錨節(jié)點(diǎn)的信號(hào),可以節(jié)省目標(biāo)源的一些能量,并且目標(biāo)源不需要與其他錨節(jié)點(diǎn)保持嚴(yán)格的時(shí)間同步。通過使用文獻(xiàn)[6]類似的信號(hào)收發(fā)方式并將時(shí)鐘偏差當(dāng)成噪聲的一部分進(jìn)行處理,文獻(xiàn)[7]提出一種有效的分式規(guī)劃(Fractional Programming,FP)方法用于估計(jì)目標(biāo)源的位置。由文獻(xiàn)[8]可知,目標(biāo)源存在的時(shí)鐘偏差(Clock Skew)和時(shí)鐘漂移(Clock Offset)是難以處理的參數(shù)。最近,文獻(xiàn)[9]通過將時(shí)鐘偏差視為隱藏變量,為異步接收器提出了一種集中的基于期望最大化的被動(dòng)定位方法,提升了算法性能且可以達(dá)到克拉美羅下界。文獻(xiàn)[10]采用合作的方式同時(shí)完成傳感器網(wǎng)絡(luò)同步和目標(biāo)源定位的工作,其中目標(biāo)源之間的協(xié)作顯著提高了同步和定位的性能。文獻(xiàn)[11]提出了一種基于飛行時(shí)間(Time-of-Flight,TOF)的方法,該方法通過估計(jì)傳感器對(duì)的相關(guān)時(shí)鐘偏差用于修正TOF測(cè)量信息,并引入補(bǔ)償因子來消除多組傳感器對(duì)之間的相關(guān)時(shí)鐘偏差從而提高算法的性能。

除了傳感器間的時(shí)鐘同步問題,信號(hào)在傳播過程中可能被一些障礙阻擋,這種現(xiàn)象被稱為非視距(Non-Line-of-Sight,NLOS)信號(hào)傳播。非視距傳播導(dǎo)致信號(hào)TOA測(cè)量值中存在NLOS誤差。各種研究表明,NLOS誤差通常遠(yuǎn)大于測(cè)量噪聲,這種誤差會(huì)對(duì)算法定位性能有著顯著的負(fù)面影響[12-16]。一些方法使用非視距誤差的分布或統(tǒng)計(jì)信息來提升定位精度[12-13]。然而,在時(shí)變的實(shí)際環(huán)境中很難獲得這種統(tǒng)計(jì)信息。文獻(xiàn)[14]提出了一個(gè)魯棒的半正定規(guī)劃(SDP)方法,無需NLOS誤差的統(tǒng)計(jì)信息。在文獻(xiàn)[15]中,兩種對(duì)非視距誤差具有魯棒性的方法被提出,即二階錐松弛(SOCR)和半正定松弛(SDR)方法。這兩種方法既不需要路徑狀態(tài)信息也不需要NLOS誤差的統(tǒng)計(jì)信息,它們只需要實(shí)際環(huán)境中是較易獲得的NLOS誤差的上界,并且表現(xiàn)出優(yōu)于之前非魯棒方法的性能。通過給定信號(hào)到達(dá)參考錨節(jié)點(diǎn)的時(shí)間戳,文獻(xiàn)[16]將到達(dá)時(shí)間差(Time-Difference-Of-Arrival,TDOA)測(cè)量模型轉(zhuǎn)化為TOA測(cè)量模型,并聯(lián)合估計(jì)目標(biāo)源發(fā)出信號(hào)的時(shí)間和位置,但該方法在非視距密集環(huán)境下定位效果較差。然而,上述文章中研究的定位問題是基于傳感器網(wǎng)絡(luò)完全同步這一條件,并且它們大多不具備目標(biāo)源自定位的功能。因此,可以看出非同步傳感器網(wǎng)絡(luò)中存在NLOS誤差時(shí)的目標(biāo)源自定位問題是一個(gè)全新的研究領(lǐng)域。

本文在NLOS條件下解決非同步傳感器網(wǎng)絡(luò)中基于TOA的目標(biāo)源自定位問題,采用文獻(xiàn)[8]和[10]中的測(cè)量模型并加入了NLOS誤差。模型中存在影響問題求解的參數(shù),例如錨節(jié)點(diǎn)開始傳輸信號(hào)的起始傳輸時(shí)間,時(shí)鐘偏差和時(shí)鐘漂移。通常,有兩種方法可以處理這些參數(shù)。一種是聯(lián)合估計(jì)這些參數(shù)和目標(biāo)源位置,另一種是通過模型的轉(zhuǎn)換來消除它們。本文采用后者,通過使用其他測(cè)量值減去一個(gè)選定的參考測(cè)量值,可以消除起始傳輸時(shí)間和時(shí)鐘漂移而只剩下時(shí)鐘偏差。經(jīng)此種處理后,TOA測(cè)量值被轉(zhuǎn)換成TDOA測(cè)量值。同時(shí)經(jīng)理論分析,可以驗(yàn)證文獻(xiàn)[15]中使用的NLOS誤差的上界過大,降低了定位性能。為克服該弊端,本文提出了一種新的魯棒最小二乘(Robust Least Square,RLS)方法,該方法聯(lián)合估計(jì)目標(biāo)源位置和參考測(cè)量值中的NLOS誤差,與[15]一樣,同樣不需要路徑狀態(tài)信息或NLOS誤差的統(tǒng)計(jì)信息。這種做法將NLOS誤差的上界縮小至合理的范圍,從而提高了定位性能,然后根據(jù)所提出的RLS方法構(gòu)造了一個(gè)非凸最小最大化優(yōu)化問題。為了求解這個(gè)問題,首先應(yīng)用了三角不等式來消除目標(biāo)函數(shù)中的最大化部分,然后應(yīng)用半正定松弛(Semidefinite Relaxation,SDR)技術(shù)將其松弛為半正定規(guī)劃(Semidefinite Programming,SDP)問題并進(jìn)行求解。

1 系統(tǒng)模型

考慮使用k(k=2或3)維定位場(chǎng)景,假設(shè)傳感器網(wǎng)絡(luò)中存在N+1個(gè)錨節(jié)點(diǎn)和一個(gè)目標(biāo)源,其中第i個(gè)錨節(jié)點(diǎn)和目標(biāo)源的位置分別由si(i=0,1,…,N)和x表示,x和si都是k維列向量。所有錨節(jié)點(diǎn)在同一起始傳輸時(shí)間T0向目標(biāo)源發(fā)送信號(hào),目標(biāo)源測(cè)量并記錄各個(gè)錨節(jié)點(diǎn)發(fā)送信號(hào)的TOA。假設(shè)錨節(jié)點(diǎn)之間是時(shí)間同步的(目標(biāo)與錨節(jié)點(diǎn)之間不必保持時(shí)間同步),且錨節(jié)點(diǎn)和目標(biāo)源之間的傳播路徑可能是NLOS的?；谏鲜黾僭O(shè),可將TOA測(cè)量模型寫為[8]:

(1)

本文的目標(biāo)是根據(jù)模型(1)估計(jì)未知目標(biāo)源位置x,其中ω,T0和θ也是未知的。一種可能的方法是聯(lián)合估計(jì)目標(biāo)源位置這些未知參數(shù),但太多的優(yōu)化變量降低了算法的性能[10]。在本文中,我們采用與文獻(xiàn)[7]中相同的方法:減去參考測(cè)量值并形成TDOA測(cè)量值,并通過將編號(hào)為0的錨節(jié)點(diǎn)指定為參考錨節(jié)點(diǎn),可以將變換后的TDOA測(cè)量值表示為:

(2)

式(2)又可改寫為如下形式:

di=ω(‖x-si‖-‖x-s0‖+wi-w0+ni),i=1,…,N

(3)

2 魯棒半正定規(guī)劃問題的推導(dǎo)

通常時(shí)鐘偏差ω的值約為1,故本文做出與[6]中相同的假設(shè)ω=1+δ,且采用相同的方法來處理δ,即假設(shè)δ是隨機(jī)變量并且服從區(qū)間為(-δmax,δmax)的均勻分布,其中δmax是已知常數(shù)。通常δ的值遠(yuǎn)小于1。據(jù)此,做出以下近似1/ω=1-δ,模型(3)可近似改寫為:

di≈ri-r0+wi-w0+ni+δdi=ri-r0+wi-w0+i,i=1,…,N

(4)

式中:‖x-s0‖=r0,‖x-si‖=ri,i=ni+δdi(i=1,…,N),通過轉(zhuǎn)換δdi可以被視為測(cè)量噪聲i的一部分。

NLOS誤差會(huì)對(duì)定位性能造成非常顯著的負(fù)面影響。解決該問題的難點(diǎn)在于NLOS誤差的統(tǒng)計(jì)信息和信號(hào)傳播的路徑信息通常是未知的,這意味著不能通過將NLOS誤差與背景噪聲組合從而將式(3)轉(zhuǎn)換為視距(Line-Of-Sight,LOS)模型。文獻(xiàn)[15]提出了一種處理NLOS誤差方法,該方法僅需要NLOS誤差的上界。通?？杉僭O(shè)NLOS誤差的上界為已知常數(shù),即0≤wi≤i(i=0,…,N),并令ei=wi-w0,可以得到ei的上界為|ei|≤max{0,i}ρi,在[15]文中即對(duì)非視距誤差ei進(jìn)行處理。但是,經(jīng)對(duì)該種非視距誤差的結(jié)構(gòu)分析,可以得出其上界過大的結(jié)論。當(dāng)參考路徑上的非視距誤差w0值固定時(shí),分析可得ei實(shí)際上落在[-w0,i-w0]的區(qū)間內(nèi),其區(qū)間長(zhǎng)度為i。相比之下,[15]中使用的非視距誤差區(qū)間[-ρi,ρi]的長(zhǎng)度是2ρi,明顯大于i,故導(dǎo)致了其算法存在額外的性能損失。由此促使本文將未知參考路徑非視距誤差w0作為變量與目標(biāo)源位置進(jìn)行聯(lián)合估計(jì)。

(5)

(6)

(7)

式中:ai和y是N+k+4維列向量,由此可以構(gòu)造一個(gè)最壞情況下RLS問題:

s.t. ‖x-si‖=ri,i=0,…,N

(8)

為求解問題(8),本文使用三角不等式來處理式(8)中的最大化部分:

(9)

s.t. ‖x-si‖=ri,i=0,…,N

(10)

將問題(10)用上鏡圖的形式等價(jià)表述為:

i=1,…,N,

i=1,…,N,

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

(11)

式中:η=[η1,…,ηN]T。由式(10)可以看出,問題的目標(biāo)函數(shù)中只有一個(gè)絕對(duì)值符號(hào)從而會(huì)產(chǎn)生兩個(gè)不等式約束,所以該問題的約束數(shù)量少于[15]中問題的約束數(shù)量,但引入了更多的變量又會(huì)增加計(jì)算復(fù)雜度,具體見后文分析。問題(11)仍是非凸問題,難以求解。利用SDR技術(shù)將其放松為以下SDP問題:

(12a)

(12b)

(12c)

i=0,…,N

(12d)

式中:Y(1:k,1:k)表示矩陣Y的第1到k行和1到k列構(gòu)成的子矩陣,y(1:k)表示y向量的第1到k個(gè)元素構(gòu)成的子向量,而Y(k,k)和y(k)則分別代表矩陣和向量對(duì)應(yīng)位置的元素。其余符號(hào)定義如下:

(13)

在文獻(xiàn)[15]中已經(jīng)證明,添加以下二階錐約束可以改善SDP問題的精確性:

‖x-s0‖≤r0?‖x-s0‖≤y(N+k+1)‖x-si‖≤ri?‖x-si‖≤y(k+i)i=1,…,N

(14)

此外,根據(jù)已知條件0≤w0≤0并通過利用y和Y元素之間的內(nèi)部關(guān)系,我們可以向問題(12)中添加如下約束:

0≤y(N+k+3)≤0y(N+k+2),0≤y(N+k+4)≤0y(N+k+1)Y(N+k+2,N+k+2)=y(N+k+3),Y(N+k+1,N+k+2)=y(N+k+4)

(15)

此外,由于NLOS誤差遠(yuǎn)大于測(cè)量噪聲[14-15]并且δ很小的事實(shí)[6-8],使得條件|i|?wi成立,并結(jié)合式(4),可得如下不等式:

di-ri+r0+w0≥0

(16)

該結(jié)果與已知條件0≤w0≤0相結(jié)合,可以通過應(yīng)用重構(gòu)線性化技術(shù)(Reformulation-Linearization Technique,RLT)[17]以構(gòu)成以下額外約束:

(di-ri+r0+w0)(w0-0)≤0

(di-ri+r0+w0)w0≥0

(17)

進(jìn)一步,利用y和Y中對(duì)應(yīng)元素重新表示約束(17)為:

diy(N+k+2)-Y(2+i,N+k+2)+y(N+k+4)+y(N+k+3)≤0(di-y(2+i)+y(N+k+1)+y(N+k+2))

(18a)

diy(N+k+2)-Y(2+i,N+k+2)+y(N+k+4)+y(N+k+3)≥0

(18b)

將約束(14),(15),(18)添加到問題(12)中,可得最終SDP問題:

(19)

至此,求解問題(19)即可得目標(biāo)源的位置估計(jì),為直觀展現(xiàn)算法推導(dǎo)遞進(jìn)的過程,本節(jié)最后以圖表的形式介紹算法的具體實(shí)施步驟,內(nèi)容見表1。

表1 算法流程

3 算法復(fù)雜度分析

通?；旌蟂D/SOCP問題的復(fù)雜度可通過下式求得[15]:

(20)

表2 算法復(fù)雜度

4 仿真結(jié)果

在本節(jié)中,通過仿真實(shí)驗(yàn)對(duì)所提出方法與其他方法的定位性能進(jìn)行比較驗(yàn)證。各錨節(jié)點(diǎn)位置在表3中給出,目標(biāo)源位置從[-50,50]×[-50,50]的正方形區(qū)域中隨機(jī)產(chǎn)生。

表3 錨節(jié)點(diǎn)位置

場(chǎng)景一:在這種場(chǎng)景下,固定錨節(jié)點(diǎn)的個(gè)數(shù)為5(N=4),同時(shí)設(shè)置0=2,i=20α(i=1,…,4)。如圖1所示,本文提出方法整體優(yōu)于其他五種方法,且優(yōu)勢(shì)隨α的增加愈加明顯。具體的,當(dāng)α=1時(shí),與SOCP-Robust和SDP-Robust相比,本文提出方法的RMSE降低了3.1 m。需要注意的是,當(dāng)α較大時(shí),SDP-Robust和SOCP-Robust方法中的非視距誤差ei大多符號(hào)為正,這意味著三角不等式中的等式基本不成立,嚴(yán)重影響了方法性能。隨著α的增大SDP-TOA方法的定位精度快速下降,因其需要估計(jì)與NLOS誤差相關(guān)的參數(shù)在較大NLOS誤差的情況下無法得到精確的估計(jì)值。

圖1 當(dāng)α變化,0=2,i=20α?xí)r各方法性能對(duì)比

場(chǎng)景二:在這種場(chǎng)景下,固定錨節(jié)點(diǎn)的個(gè)數(shù)為5個(gè)(N=4),同時(shí)設(shè)置0=20,i=20α(i=1,…,4)。由圖2可知,參考路徑上的NLOS誤差嚴(yán)重影響了FP和SDP-N方法的定位效果。根據(jù)文獻(xiàn)[15]可知,SDP-Robust和SOCP-Robust方法直接受到非視距誤差ei量級(jí)的影響。該場(chǎng)景下,隨著α的增加非視距誤差ei量級(jí)下降但三角不等式中的等式也漸漸無法滿足,故造成了SDP-Robust和SOCP-Robust方法定位效果的波動(dòng)。與其他方法不同,所提出的方法幾乎不受參考路徑上的NLOS誤差的影響。原因是本文將w0作為估計(jì)變量同時(shí)用魯棒方法處理NLOS誤差。因此,所提出的方法僅受到wi量級(jí)大小的影響,仿真結(jié)果已經(jīng)清楚地說明了這一點(diǎn)。同樣受到非視距誤差wi影響的SDP-TOA方法的定位效果則下降較快,最后在α=1甚的時(shí)候甚至比不過SDP-Robust方法,也印證了文獻(xiàn)[16]中的結(jié)果。

圖2 當(dāng)α變化,0=20,i=20α?xí)r各方法性能對(duì)比

場(chǎng)景三:在這種場(chǎng)景下,錨節(jié)點(diǎn)個(gè)數(shù)由5增加到9,即N由4增加到8,時(shí)設(shè)置0=i=20(i=1,…,N)。如圖3所示,因?yàn)槲磳?duì)非視距誤差做出有效處理,在非視距誤差較大的環(huán)境下FP和SDP-N表現(xiàn)較差。本文提出的方法定位性能隨錨節(jié)點(diǎn)個(gè)數(shù)增加而逐漸提升,且仍在定位效果上具有優(yōu)勢(shì)。尤其是與SDP-N方法相比,本文方法具有超過6 m的RMSE降低。SDP-Robust和SOCP-Robust方法表現(xiàn)出異常的仿真結(jié)果,即隨著錨節(jié)點(diǎn)個(gè)數(shù)的增加,性能可能無法穩(wěn)定提升。此現(xiàn)象可歸因于這樣的事實(shí):隨著錨節(jié)點(diǎn)個(gè)數(shù)的增加,不合適的非視距誤差上界問題將對(duì)更多測(cè)量值產(chǎn)生負(fù)面影響。

圖3 當(dāng)錨節(jié)點(diǎn)數(shù)量N變化時(shí)各方法性能對(duì)比

5 總結(jié)

本文提出了一種新的RLS方法,在非同步網(wǎng)絡(luò)中對(duì)NLOS條件下基于TOA的目標(biāo)源自定位問題的求解有較好的效果。所提出的RLS方法通過模型轉(zhuǎn)換消去了原模型中存在的一些干擾參數(shù),解決了現(xiàn)有其他方法中存在的不合適的非視距誤差上界問題,并挖掘出各優(yōu)化變量間存在的關(guān)系,將這些關(guān)系轉(zhuǎn)化為合理的凸約束,因此改善了定位性能。仿真結(jié)果證實(shí)了該方法的良好性能,并展現(xiàn)了方法對(duì)減輕NLOS誤差影響的顯著效果。