朱偉辰,王 剛

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

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

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

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

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

1 系統(tǒng)模型

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

(1)

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

(2)

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

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

(3)

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

通常時鐘偏差ω的值約為1,故本文做出與[6]中相同的假設(shè)ω=1+δ,且采用相同的方法來處理δ,即假設(shè)δ是隨機變量并且服從區(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可以被視為測量噪聲i的一部分。

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

(5)

(6)

(7)

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

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

(8)

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

(9)

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

(10)

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

i=1,…,N,

i=1,…,N,

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

(11)

式中:η=[η1,…,ηN]T。由式(10)可以看出,問題的目標(biāo)函數(shù)中只有一個絕對值符號從而會產(chǎn)生兩個不等式約束,所以該問題的約束數(shù)量少于[15]中問題的約束數(shù)量,但引入了更多的變量又會增加計算復(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òu)成的子向量,而Y(k,k)和y(k)則分別代表矩陣和向量對應(yīng)位置的元素。其余符號定義如下:

(13)

在文獻[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)大于測量噪聲[14-15]并且δ很小的事實[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)

進一步,利用y和Y中對應(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)源的位置估計,為直觀展現(xiàn)算法推導(dǎo)遞進的過程,本節(jié)最后以圖表的形式介紹算法的具體實施步驟,內(nèi)容見表1。

表1 算法流程

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

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

(20)

表2 算法復(fù)雜度

4 仿真結(jié)果

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

表3 錨節(jié)點位置

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

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

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

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

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

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

5 總結(jié)

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