張 晨，王 剛

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

目標(biāo)定位在近幾年來一直是研究熱點，也是無線傳感網(wǎng)絡(luò)(Wireless Sensor Networks，WSN)的重要任務(wù)。移動目標(biāo)定位作為其中的一部分，在物流管理、車輛導(dǎo)航和緊急救援等領(lǐng)域都有著重要的應(yīng)用[1-4]。

在移動目標(biāo)定位場景中，傳感器采集目標(biāo)發(fā)射電磁波的時間信息或頻率信息。常見的時間測量信息有:到達(dá)時間(Time-of-Arrival，TOA)[5-6]和到達(dá)時間差(Time-Difference-of-Arrival，TDOA)[7-10]；常見的頻率測量信息有:到達(dá)頻率(Frequency-of-Arrival，F(xiàn)OA)[5-6]和到達(dá)頻率差(Frequency-Difference-of-Arrival，F(xiàn)DOA)[7-8]。其中頻率測量依賴于物體的位置，加上物體移動速度未知，頻率測量比時間測量更加復(fù)雜[11]，因此本文采用時間測量的方法，它比頻率測量更加直接。定位的精度是需要關(guān)心問題，已有文獻(xiàn)討論基于時間測量的移動目標(biāo)定位問題[12-14]，且取得了良好性能。但在實際的定位環(huán)境中，如城市中心，由于障礙物的遮擋，移動目標(biāo)發(fā)射的電磁波往往需要經(jīng)過多次反射或衍射才能到達(dá)錨節(jié)點，即傳播路徑是非視距的(Non-Line-of-Sight，NLOS)。在這種情況下，非視距傳播所引起的誤差對定位精度會產(chǎn)生很大的負(fù)面影響，而且已有文獻(xiàn)表明，非視距誤差通常遠(yuǎn)大于測量噪聲[15]。此外，由于定位環(huán)境的不斷變化，所以非視距誤差的統(tǒng)計信息難以獲得，因此減少非視距誤差的影響在移動定位中就顯得格外重要。

對于非視距誤差的處理，已有很多文獻(xiàn)對其進(jìn)行了研討。例如文獻(xiàn)[16-17]使用非視距誤差的統(tǒng)計信息來提高定位精度，但是在實際環(huán)境中，統(tǒng)計信息往往難以獲得。針對這種情況，文獻(xiàn)[15，18-21]提出了不需要已知非視距誤差的統(tǒng)計信息和路徑狀態(tài)的方法。一種是采用魯棒處理的方法，文獻(xiàn)[18]提出對非視距誤差做魯棒處理，將其轉(zhuǎn)化為最大最小問題，再利用二階錐松弛(Second-Order Cone Relaxation，SOCR) 和半正定松弛(Semidefinite Relaxation，SDR)技術(shù)對其進(jìn)行處理。這種方法僅要求已知非視距的誤差上界。然而，當(dāng)測量環(huán)境為視距時，已知的上界通常太大，導(dǎo)致這種方法在稀疏非視距環(huán)境中沒有很好的性能。另一種是采用估計處理的方法，文獻(xiàn)[15]提出了聯(lián)合估計源位置和與非視距誤差有關(guān)的平衡參數(shù)的方法，并通過SOCR和SDR 對問題進(jìn)行松弛，從而緩解了非視距誤差的影響。文獻(xiàn)[19]提出了非視距環(huán)境下協(xié)作定位，對源位置和非視距差的二次多項式進(jìn)行估計，并通過SDR 對問題進(jìn)行松弛。而文獻(xiàn)[20-21]采用估計處理和魯棒處理結(jié)合的方法，聯(lián)合估計源位置和與非視距誤差有關(guān)平衡參數(shù)，同時對新的變量做魯棒性處理。在估計的方法中，若直接對所有的非視距誤差進(jìn)行估計，會涉及到大量的優(yōu)化變量，意味著需要大量的精確測量來估計所有的參數(shù)，這在密集的非視距環(huán)境下，會由于測量不精確導(dǎo)致性能下降[20]。

本文研究了非視距環(huán)境下基于TOA 的移動目標(biāo)定位問題。WSN 中的錨節(jié)點對移動目標(biāo)進(jìn)行多次采樣得到多組TOA 測量值，每組均含有測量噪聲和非視距誤差。對測量數(shù)據(jù)采用估計的方法，但如果直接估計移動目標(biāo)的初始位置、移動速度和所有的非視距誤差，在采樣點多的情況下，模型會涉及到大量的優(yōu)化變量，從而導(dǎo)致精度下降。因此對于非視距誤差不進(jìn)行直接估計，參考文獻(xiàn)[19]的方法，將非視距誤差的一次項和二次項進(jìn)行組合，再加上合理的近似，對其整體進(jìn)行估計，這樣優(yōu)化變量的數(shù)目便可減少。接著在此基礎(chǔ)上，推導(dǎo)出約束最小二乘(Least Squares，LS)問題，這是一個非凸的問題，通過SDR 將其松弛為凸的SDP 問題，該方法不需要知道非視距誤差上限和路徑狀態(tài)。通過對算法的仿真與分析，發(fā)現(xiàn)在密集和稀疏的非視距的環(huán)境下，本文提出的方法都取得了良好的性能，從而有效減輕了非視距誤差產(chǎn)生的負(fù)面影響。

本文的章節(jié)內(nèi)容組織如下。第一節(jié)描述了基于TOA 的移動目標(biāo)定位場景；第二節(jié)詳細(xì)闡述了構(gòu)造約束LS 問題并將其松弛為凸的SDP 問題的推導(dǎo)過程；第三節(jié)通過仿真給出了算法的性能分析并探究了懲罰因子對算法敏感度的影響；第四節(jié)給出結(jié)論。

文本采用的符號說明如下。向量和矩陣分別用粗體小寫字母和粗體大寫字母表示。ai表示向量a中第i個元素；A(i，j)表示矩陣A中第(i，j)個元素。a(1:i)表示向量a中第1 到第i個元素所構(gòu)成的子向量；A(1:i，1:j)表示矩陣A中第1 到第i行，第1 到第j列所構(gòu)成的子矩陣。0k×l代表k行l(wèi)列的全零矩陣。tr(A)和rank(A)分別表示矩陣A的跡和秩；A≥0表示矩陣A是半正定的。?k表示k維實空間。

1 問題描述

考慮一個k(k＝2 或3)維場景上的移動目標(biāo)定位問題。如圖1 所示，設(shè)WSN 中有N個已知的錨節(jié)點和1 個未知的移動目標(biāo)，其中第i個錨節(jié)點的坐標(biāo)用si∈?k(i＝1，2，…，N)表示，移動目標(biāo)初始位置的坐標(biāo)用x∈?k表示，移動速度用v∈?k表示，每個錨節(jié)點對移動目標(biāo)的采樣點數(shù)為M，且采樣周期為T。假設(shè)T的數(shù)值很小，則可以認(rèn)為移動目標(biāo)在整個過程中速度保持不變[21]。

圖1 移動目標(biāo)定位場景

設(shè)錨節(jié)點和移動目標(biāo)之間存在著測量噪聲和非視距誤差，則相應(yīng)的TOA 測量模型如下所示:

式中:c是光速，nij/c是第i條路徑上進(jìn)行第j次采樣時的測量噪聲。假設(shè)T的數(shù)值很小，則錨節(jié)點和移動目標(biāo)之間的信號傳播路徑基本不變，于是可以認(rèn)為錨節(jié)點M次采樣時的非視距誤差均相等，于是用ei/c來代表第i條路徑上每次采樣到的非視距誤差。將式(1)兩端同時乘以c，則相應(yīng)的測量模型轉(zhuǎn)化為如下所示:

通常假設(shè)nij是服從均值為零，方差為的高斯分布。ei是取值為正的非視距誤差，由于真實環(huán)境在不斷變化，所以它的分布往往難以獲得，通常只假設(shè)它的上限為ρi，即0≤ei≤ρi。這里還要指出，測量噪聲往往比非視距誤差小很多，即ei?nij，從而非視距誤差在移動目標(biāo)定位中需要格外關(guān)注[15]。

2 半正定規(guī)劃問題的構(gòu)造

在本節(jié)中，首先在式(2)的基礎(chǔ)上推導(dǎo)并構(gòu)造出約束LS 問題，然后對其進(jìn)行松弛，轉(zhuǎn)化為易于處理的凸的SDP 問題，從而完成對移動目標(biāo)的初始位置和移動速度的估計。

首先將式(2)中的ei移到等式左邊，并對等式兩端進(jìn)行平方，得到的結(jié)果如下所示:

對式(3)的兩端展開并移項，可得:

式中:測量噪聲的二次平方項被忽略，因為其數(shù)值上遠(yuǎn)小于‖x+jTv-si‖2[15]，而非視距誤差的二次項不能被忽略。

對于非視距誤差的處理，采用估計的方法。式(4)中含有非視距誤差的一次項2dijei和二次項。為了減少優(yōu)化變量的數(shù)目，在T不大的情況下，非視距誤差一次項中的dij可以近似用第i條路徑M次采樣的平均值來代替:

令ci＝2ei-(i＝1，2，…，N)，即用ci代替非視距誤差一次項和二次項的整體，則對非視距誤差的估計轉(zhuǎn)化為了對ci(i＝1，2，…，N)的估計。本文將ci作為變量與移動目標(biāo)初始位置x和移動速度v進(jìn)行聯(lián)合估計。由此定義，式(4)可轉(zhuǎn)化為:

進(jìn)一步，令u＝‖x‖2，w＝‖v‖2，z＝xTv。并且令c＝[c1，c2，…，cN]T，則式(6)可寫為:

根據(jù)式(8)，可以構(gòu)造如下約束LS 問題:

問題(10)仍是一個非凸問題，難以求解。本文通過SDR 將其松弛為SDP 問題。為此，引入矩陣Y并令Y＝y(tǒng)yT，則約束(10a)-(10c)分別可以表示成如下形式:

則問題(10)可以轉(zhuǎn)化為:

通過引入:

再結(jié)合如下的等價變換:

則問題(12)可以轉(zhuǎn)化為:

在問題(15)中，唯一的非凸約束是rank(Y)＝1這一項，將其舍棄，則問題(15)可以轉(zhuǎn)化為如下凸的SDP 問題:

為了使松弛后的SDP 問題更加收緊于原問題，需要引入一些額外的約束項。注意到:

因為nij?‖x+jTv-si‖，且ei≥0，所以容易得到ci≥0，并且有如下的等價表示:

于是本文在問題(16)中引入約束(18)來進(jìn)行收緊。而且為了避免問題(16)中ci的解太大，我們對其增加一個懲罰項來抑制ci的值。于是得到最終凸的SDP 問題:

式中:λ為懲罰因子。求解問題(19)，便可以得到移動目標(biāo)的初始位置估計和移動速度估計。本節(jié)最后給出算法的偽代碼，用來總結(jié)所提出的方法，具體如算法1 所示。

算法1 移動目標(biāo)定位的SDP 算法

3 仿真與分析

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

通常解決混合SDP/SOCP 問題的復(fù)雜度為:

式中:m是等式約束的個數(shù)，NSD和NSOC分別是半正定錐約束和二階錐約束的個數(shù)，分別是第i個半正定錐和二階錐的維度，μ＝為壁壘參數(shù)，用來測量所涉及錐的幾何復(fù)雜度，ε＞0是解的精確度。下文用“SDP-NLOS”來指代本文所提出的方法，該方法有4 個等式約束[(11a) -(11c)，(18)]，有1 個維度為2k+N+4 的半正定錐約束[(15a)]，二階錐約束的個數(shù)和維度均為零，所以SDP-NLOS 最壞情況下的復(fù)雜度為O[4(2k+N+4)3.5ln(1/ε)]。為了和文本提出的方法形成對比，文章綜合文獻(xiàn)[20-21]對非視距誤差的處理方法:魯棒處理和估計處理結(jié)合的方法，并將其拓展到移動目標(biāo)定位問題上，且將其命名為“RSDP”(魯棒SDP)，具體推導(dǎo)過程見附錄。該方法有NM+4 個等式約束[(34b)，(38e)，(38f)]，有3 個半正定約束[(33)，(38a)，(38b)]，維度分別為NM+1、2k+1 和NM+2，二階錐約束的個數(shù)和維度均為零，所以RSDP 最壞情況下的復(fù)雜度為O[(NM+2)4.5ln(1/ε)]，可以發(fā)現(xiàn)，本文提出算法的復(fù)雜度明顯低于RSDP，且隨著采樣點數(shù)的增加，這種效果更加明顯。

3.2 仿真結(jié)果

在本小節(jié)中，通過軟件仿真對本文所提出的方法進(jìn)行性能測試與分析。為了進(jìn)一步體現(xiàn)SDPNLOS 對非視距誤差的緩解作用，本文在問題(19)的基礎(chǔ)上舍棄非視距誤差的一次項2dijei和二次項，得到不考慮非視距誤差的SDP 問題:

矩陣A、B和常數(shù)r的形式同(13a)-(13c)，下文將該算法命名為“SDP”。

為了對比分析SDP-NLOS、SDP 和RSDP 的定位性能。本文通過MATLAB R2017a 軟件進(jìn)行仿真，求解工具箱采用CVX，求解器為Sedumi。首先設(shè)置維數(shù)k＝2，采樣周期T＝0.6 s，SDP-NLOS 中懲罰因子λ＝0.1，并且根據(jù)文獻(xiàn)[20-21]，設(shè)置RSDP 中的取ρij平均值的一半，即:

然后在表1 中給出各個錨節(jié)點的坐標(biāo)。

表1 錨節(jié)點坐標(biāo)

移動目標(biāo)在[-25 m，25 m]×[-25 m，25 m]的正方形區(qū)域內(nèi)隨機產(chǎn)生50 個，而且每個移動目標(biāo)x軸方向的移動速度vx和y軸方向的移動速度vy均在-2 m/s～2 m/s 之間隨機產(chǎn)生。最后根據(jù)式(2)生成含噪聲的TOA 測量值，其中測量噪聲由高斯分布產(chǎn)生，令＝σ2，則nij～N(0，σ2)，其中非視距誤差由均勻分布產(chǎn)生，令ρi＝ρ，則ei～U(0，ρ)。

移動目標(biāo)的定位性能用均方根誤差(Root Mean Square Error，RMSE)來衡量。對初始位置x估計的RMSE 和對移動速度v估計的RMSE 分別定義為:

式中:和分別是估計出的初始位置和移動速度，xi和vi分別是真實的初始位置和移動速度，M為蒙特卡洛仿真次數(shù)，設(shè)置每個移動目標(biāo)仿真500次，又因為有50 個移動目標(biāo)，所以M＝25 000。下文考慮五種仿真場景，在場景一到四中，每條路徑狀態(tài)(視距或非視距)都是隨機選取的，且每條路徑屬于非視距的概率均設(shè)置為50%[20-21]。需要指出的是，RSDP 需要知道非視距誤差的上限，而SDP-NLOS和SDP 不需要知道誤差的上限。

場景一:改變非視距誤差上限ρ＝1，2，…，6，考慮非視距誤差對移動目標(biāo)定位的影響。設(shè)置錨節(jié)點的個數(shù)N＝5，編號為1～5，每個錨節(jié)點的采樣點數(shù)M＝4，測量噪聲的標(biāo)準(zhǔn)差σ＝0.1。初始位置估計的仿真結(jié)果如圖2(a)所示，移動速度估計的仿真結(jié)果如2(b)所示。能夠發(fā)現(xiàn)隨著非視距誤差上限的增加，三種方法對于移動目標(biāo)的定位性能均有所下降，其中SDP-NLOS 與RSDP 相比，在移動速度的估計上沒有明顯的差異，但在初始位置的估計上有著明顯的優(yōu)勢。具體地，當(dāng)ρ＝6 時，SDP-NLOS 和RSDP相比在初始位置的估計上有0.3 m 左右的優(yōu)勢。由于SDP 未考慮非視距誤差的影響，因此SDP 對于位置和速度的估計均是最差的。綜合分析，本文提出的方法SDP-NLOS 更有優(yōu)勢。

圖2 非視距誤差上限變化時的性能比較

場景二:改變測量噪聲的標(biāo)準(zhǔn)差σ＝0.1，0.2，…，0.6，考慮測量噪聲標(biāo)準(zhǔn)差對移動目標(biāo)定位的影響。設(shè)置錨節(jié)點的個數(shù)N＝5，編號為1～5，非視距誤差上限ρ＝5，每個錨節(jié)點的采樣點數(shù)M＝4。初始位置估計的仿真結(jié)果如圖3(a)所示，移動速度估計的仿真結(jié)果如圖3(b)所示。能夠發(fā)現(xiàn)，隨著噪聲標(biāo)準(zhǔn)差的增加，三種方法對于移動目標(biāo)的定位性能均有所下降，SDP-NLOS 與RSDP 相比，在移動速度的估計上有平均0.03 m/s 的劣勢，但在初始位置的估計上有平均0.23 m 的優(yōu)勢。而SDP 對于兩者的估計是最差的。綜合位置和速度的分析，本文提出的方法SDP-NLOS 更具有優(yōu)勢。

圖3 噪聲標(biāo)準(zhǔn)差變化時的性能比較

場景三:改變錨節(jié)點個數(shù)N＝4，5，…，9，考慮錨節(jié)點個數(shù)對移動目標(biāo)定位的影響。設(shè)置非視距誤差上限ρ＝5，測量噪聲的標(biāo)準(zhǔn)差σ＝0.1，每個錨節(jié)點的采樣點數(shù)M＝4。初始位置估計的仿真結(jié)果如圖4(a)所示，移動速度估計的仿真結(jié)果如圖4(b)所示。能夠發(fā)現(xiàn)，隨著錨節(jié)點個數(shù)的增加，三種方法對于初始位置和移動速度估計的RMSE 均有所下降，這是因為隨著錨節(jié)點個數(shù)的增多，獲取到的信息會增多，對位置和速度估計的精度就會提高。其中SDP-NLOS 對兩者估計的性能最優(yōu)，RSDP 的性能次之，SDP 的性能最差。

圖4 錨節(jié)點個數(shù)變化時的性能比較

場景四:改變采樣點數(shù)M＝2，3，…，7，考慮采樣點數(shù)對移動目標(biāo)定位的影響。設(shè)置錨節(jié)點的個數(shù)N＝5，編號為1～5，非視距誤差上限ρ＝5，測量噪聲的標(biāo)準(zhǔn)差σ＝0.1。初始位置估計的仿真結(jié)果如圖5(a)所示，移動速度估計的仿真結(jié)果如圖5(b)所示。能夠發(fā)現(xiàn)，隨著采樣點數(shù)的增加，提出的方法對于移動目標(biāo)的定位性能提高，這是由于當(dāng)采樣點數(shù)增加時，相應(yīng)得到的方程數(shù)就會增加，對位置和速度估計的精度就會提高。其中SDP-NLOS 更占有優(yōu)勢。具體地，SDP-NLOS 和RSDP 相比，在初始位置的估計上有平均0.32 m 的優(yōu)勢，在移動速度的估計上兩者無明顯差別。同樣地，SDP 對于兩者的估計是最差的。

圖5 采樣點數(shù)變化時的性能比較

場景五:通過改變非視距路徑的個數(shù)Nnlos＝0，1，…，5，考慮路徑狀態(tài)對移動目標(biāo)定位的影響。設(shè)置錨節(jié)點的個數(shù)N＝5，編號為1～5，每個錨節(jié)點的采樣點數(shù)M＝4，非視距誤差上限ρ＝5，測量噪聲的標(biāo)準(zhǔn)差σ＝0.1。初始位置估計的仿真結(jié)果如圖6(a)所示，移動速度估計的仿真結(jié)果如圖6(b)所示。具體地，當(dāng)所有路徑均為非視距時，由于RSDP 做了魯棒性處理，因此性能優(yōu)于提出的方法SDP-NLOS，但當(dāng)視距路徑的比例大于1/5 時，SDP-NLOS 的性能優(yōu)于RSDP；由于SDP 未考慮非視距誤差的影響，因此SDP對于兩者的估計在大多數(shù)情況下是最差的?？梢园l(fā)現(xiàn)，本文提出的方法SDP-NLOS 能應(yīng)用于視距和非視距同時存在的場景，且定位效果良好。

圖6 非視距路徑的個數(shù)變化時的性能比較

3.3 懲罰因子對算法敏感度的影響

通過改變懲罰因子λ，來觀察不同的λ對SDPNLOS 敏感度的影響，這樣能在實際的場景下，為λ的選取提供參考。設(shè)置錨節(jié)點的個數(shù)N＝5，編號為1～5，每個錨節(jié)點的采樣點數(shù)M＝4，非視距誤差上限ρ＝2，測量噪聲的標(biāo)準(zhǔn)差σ＝0.1。在此場景下改變λ，得到的結(jié)果如圖7 所示。可以發(fā)現(xiàn)當(dāng)λ≥0.01時，對初始位置估計的RMSE 大約在1.23 m～1.38 m之間，波動幅度不大。而對移動速度估計的RMSE 大約穩(wěn)定在0.098 m/s 左右，基本無變化。因此該方法對λ變動的敏感度較低，從而使λ的選取有著較大的范圍。

圖7 懲罰因子λ 變化時，初始位置估計的RMSE變化和移動速度估計的RMSE 變化

4 總結(jié)

本文基于TOA 的測量方法研究了非視距環(huán)境下移動目標(biāo)的定位問題。為降低非視距誤差的影響，本文采用估計的方法，構(gòu)造了約束LS 問題，實現(xiàn)了對移動目標(biāo)的初始位置、移動速度和非視距誤差的聯(lián)合估計。并通過合理的近似，使優(yōu)化變量的數(shù)目得以減少，以增加模型求解的準(zhǔn)確程度。本文對該問題進(jìn)行松弛，轉(zhuǎn)化為了凸的SDP 問題，并通過仿真證實了該方法在稀疏和密集的非視距環(huán)境下均有著良好的性能。本文提出的方法不需要知道非視距誤差上限，且在算法復(fù)雜度上有著明顯的優(yōu)勢。

附錄 RSDP(魯棒SDP)的推導(dǎo)

文章綜合文獻(xiàn)[20-21]對非視距誤差的處理方法，并將其拓展到非合作式移動目標(biāo)定位問題上。

針對移動目標(biāo)的距離測量值可以寫成下式所示:

根據(jù)式(26)，有如下的魯棒約束最小二乘問題，其中對目標(biāo)位置x，移動速度v和平衡參數(shù)做估計處理，對產(chǎn)生新的變量做魯棒處理:

將問題(28)寫成上鏡圖的形式:

通過S-Lemma，式(30)可以轉(zhuǎn)化為存在λ≥0使得:

則問題(29)可以轉(zhuǎn)化為如下所示:

問題(34)仍是一個非凸問題，難以求解。下面通過SDR 將其松弛為SDP 問題。為此引入矩陣G并令G＝ggT，引入向量y＝[xT，vT]T∈?2k和矩陣Y，并令Y＝y(tǒng)yT，則q可以表示為:

再結(jié)合如下的等價變換:

則問題(34)可以轉(zhuǎn)化為如下的SDP 問題:

在問題(38)中，非凸約束是矩陣的秩等于1 的約束，現(xiàn)將其舍棄，則問題(38)最終可以轉(zhuǎn)化為如下凸的SDP 問題:

綜上所述，問題(39)便是綜合文獻(xiàn)[20-21]后產(chǎn)生的非合作式移動目標(biāo)定位問題，即正文中的RSDP(魯棒SDP)方法。