基于特征矢量的NLOS誤差檢測(cè)的定位算法

(1.四川水利職業(yè)技術(shù)學(xué)院信息工程系， 四川崇州 611231; 2.重慶大學(xué)計(jì)算機(jī)學(xué)院， 重慶 400044)

0 引言

如今，多類應(yīng)用需要目標(biāo)定位算法，如無(wú)線傳感網(wǎng)絡(luò)[1-2]、雷達(dá)系統(tǒng)[3-4]。常利用測(cè)量技術(shù)實(shí)現(xiàn)目標(biāo)定位，如接收信號(hào)強(qiáng)度(Received Signal Strength, RSS)、到達(dá)時(shí)間(Time of Arrival, TOA)和到達(dá)角度(Angle of Arrival, AOA)，其中基于TOA測(cè)量是常用的測(cè)距技術(shù)。在基于TOA測(cè)量的測(cè)距技術(shù)中，每個(gè)基站以自己離目標(biāo)節(jié)點(diǎn)的距離為半徑以自己為圓心構(gòu)建一個(gè)圓。理論上，由多個(gè)基站所形成的多個(gè)圓的共同交點(diǎn)就是目標(biāo)節(jié)點(diǎn)位置。

如果TOA信號(hào)是沿直線傳輸，則可較準(zhǔn)確地測(cè)量基站離目標(biāo)節(jié)點(diǎn)的距離。然而，噪聲會(huì)影響TOA信號(hào)，降低了測(cè)距準(zhǔn)確性。換言之，如果TOA信號(hào)是通過(guò)反射達(dá)到的，測(cè)量距離將超過(guò)真實(shí)距離。這種情況也稱為非視距(Non Line of Sight, NLOS)問(wèn)題，其能引起較大的測(cè)距誤差。NLOS誤差也總會(huì)加大測(cè)距值，而不是縮小測(cè)距值。

通常，可通過(guò)使用大量傳感節(jié)點(diǎn)提高定位精度。如文獻(xiàn)[5]引用大量傳感節(jié)點(diǎn)測(cè)量電脈沖信號(hào)的始端。在大量傳感節(jié)點(diǎn)系統(tǒng)中，NLOS問(wèn)題也稱為源誤差。然而，基于測(cè)量數(shù)據(jù)識(shí)別NLOS情況是非常耗時(shí)，且耗時(shí)量隨基站數(shù)呈指數(shù)關(guān)系。因此，如何識(shí)別NLOS情況成為無(wú)線傳感網(wǎng)絡(luò)的研究熱點(diǎn)。

近期，研究人員提出不同的算法消除或識(shí)別NLOS誤差[6]。如文獻(xiàn)[6]提出殘差加權(quán)算法(RWGH)。RWGH算法能夠有效地處理大型定位系統(tǒng)中的節(jié)點(diǎn)定位問(wèn)題。然而，節(jié)點(diǎn)數(shù)的增加，不僅增加了計(jì)算復(fù)雜度，但定位誤差也會(huì)增加。此外，文獻(xiàn)[7]采用環(huán)境掃描算法消除NLOS誤差。類似地，文獻(xiàn)[8]采用SRNI算法降低復(fù)雜度，并采用稀疏恢復(fù)技術(shù)[9]消除NLOS問(wèn)題。

為此，提出基于特征矢量的NLOS誤差檢測(cè)的定位(Eigenvector-Based NLOS Error Identification Localization, E-NIL)算法。E-NIL算法先利用測(cè)距數(shù)據(jù)的統(tǒng)計(jì)特性建立測(cè)距模型，再通過(guò)尋找相關(guān)值的特征向量識(shí)別NLOS誤差。然后，將NLOS誤差值從觀察數(shù)據(jù)中刪除。最后，依據(jù)這些無(wú)NLOS誤差的觀察數(shù)據(jù)估計(jì)移動(dòng)基站位置。實(shí)驗(yàn)數(shù)據(jù)表明，提出的E-NIL算法有效地提高定位精度，并降低定位誤差。

1 問(wèn)題描述

考慮一個(gè)二維(Two-Dimensional, 2-D)定位場(chǎng)景，N個(gè)基站(Base Station, BS)隨機(jī)分布于區(qū)域內(nèi)。利用N個(gè)BS估計(jì)一個(gè)移動(dòng)基站(Mobile Station, MS)的位置，且N個(gè)BS的位置表示為si=[xi,yi]T,i=1,…,N。而MS的真實(shí)位置表示為u=[x,y]。

在NLOS的環(huán)境下，第i個(gè)BS獲取的觀測(cè)數(shù)據(jù)：

(1)

式中:ωi為測(cè)量噪聲，假定ωi為獨(dú)立零均值的高斯分布變量，且方差為σ2；ni為非零常數(shù)，表示NLOS值；ri為MS離第i個(gè)BS間的真實(shí)距離，其定義如式(2)所示：

(2)

當(dāng)無(wú)NLOS存在時(shí)，就可利用最小二乘法(Least Square, LS)算法估計(jì)MS位置：

(3)

從式(3)可知，式(3)是MS位置的非線性函數(shù)。因此，任何非NLOS模型的求解均會(huì)導(dǎo)致較大的估計(jì)誤差。而識(shí)別NLOS位置，并處理相關(guān)的測(cè)距值是處理NLOS問(wèn)題的有效方式。

2 E-NIL算法

2.1 尋找NLOS誤差

本文考慮加性噪聲的NLOS，并利用統(tǒng)計(jì)特性識(shí)別NLOS。首先，將式(1)進(jìn)行矩陣化，如式(4)所示：

(4)

式中，r=[r1,r2,…,rN]T,ρ=n+ω，n=[n1,n2,…,nN]T，ω=[ω1,ω2,…,ωN]T。

再計(jì)算ρ的自相關(guān)值Rρ，如式(5)所示：

Rρ=E(n+ω)(n+ω)H=

EnnH+EnωH+EωnH+EωωH

(5)

由于ω是零均值的高斯白噪聲變量，且方差為σ2，式(5)可轉(zhuǎn)換成

Rρ=nnH+σ2I

(6)

對(duì)式(6)兩邊乘以矢量n，可得

(7)

Rρe=nnHe+σ2e=σ2e

(8)

比較式(7)和式(8)，不難發(fā)現(xiàn)Rρ的最大特征值所對(duì)應(yīng)的特征向量是n。因此，如果確定Rρ，則可通過(guò)尋找最大特征值和相應(yīng)的特征向量，識(shí)別NLOS。

為此，對(duì)ρ進(jìn)行M次測(cè)量，并進(jìn)行近似求解，便可計(jì)算Rρ：

(9)

式中，ρl為在第l次觀察中的誤差矢量。

然而，由于采用式(9)計(jì)算Rρ，而不是利用精確的數(shù)學(xué)式計(jì)算，特征值呈隨機(jī)性、非常數(shù)特性。因此，需要一個(gè)算法計(jì)算Rρ的最大特征值，并分析該特征值內(nèi)是否存在NLOS項(xiàng)。為此，先引用定理1。

定理1：可利用Marceko規(guī)則[10]描述自相關(guān)矩陣的特征值。Marceko規(guī)則定義了特征值概率密度函數(shù)(Probability Density Function, PDF):

(10)

式中，γ表示觀察數(shù)與抽樣率，其控制Marceko分布統(tǒng)一特性，且

(11)

此定理的證明過(guò)程可參見(jiàn)文獻(xiàn)[10]。

然而，直接計(jì)算式(10)的累加分布函數(shù)(Cumulative Distribution Function, CDF)是非常復(fù)雜的。當(dāng)γ接近1時(shí)，可利用式(12)計(jì)算式(11)的CDF。

Fλ(λ)=1-e-αλ

(12)

式中，α為控制參數(shù)。

假定λi為Rρ的特征值，且i=1,2,…,N。對(duì)N個(gè)特征值進(jìn)行排序，可建立離散函數(shù)：

(13)

式中，λ1<λ2<…<λN。

依據(jù)式(12)可知，通過(guò)控制參數(shù)α調(diào)整式(12)函數(shù)。為此，最初，先對(duì)控制參數(shù)α進(jìn)行猜測(cè)，然后，再采用梯度下降算法優(yōu)化控制參數(shù)α。據(jù)此，最初，令控制參數(shù)α的初始值為零，然后，定義式(14)和式(15)的變量：

(14)

(15)

假定δ表示猜測(cè)參數(shù)α所導(dǎo)致的誤差，其定義如式(16)所示：

δ=[hTh]-1hTz

(16)

然后，將此誤差加入控制參數(shù)α，再代入式(15)，重復(fù)此過(guò)程，直到控制參數(shù)α收斂于最終值：

α←α+δ

(17)

接下來(lái)，定義σ2小于預(yù)定閾值Γ的概率τ：

(18)

將式(12)代入式(18)，便可計(jì)算預(yù)定閾值Γ，如式(19)所示：

(19)

E-NIL算法的目的就是識(shí)別NLOS誤差。具體過(guò)程如下：先計(jì)算Rρ的特征值，并依據(jù)式(13)進(jìn)行排序，然后調(diào)整式(12)，再針對(duì)任意τ值，并依據(jù)式(19)計(jì)算預(yù)定閾值Γ。最后，判斷如果最大特征值大于Γ，則存在NLOS的概率為τ。

綜上所述，從N個(gè)基站中分辨哪些基站與MS間通信存在NLOS誤差的過(guò)程，如算法1偽代碼所示，本文將其命名NLOS Finder算法。假定λ是包含Rρ矩陣的所有特征值矢量、υ是最大特征值所對(duì)應(yīng)的特征矢量，而引用τ表示檢測(cè)NLOS誤差的概率。

算法1的步驟為：第一步，對(duì)所有特征值進(jìn)行排序，形成式(13)，然后依據(jù)式(12)計(jì)算α值；第二步，依據(jù)式(19)計(jì)算閾值Γ；第三步，將閾值Γ與λN值進(jìn)行比較，如果Γ小于λN，則將最大特征值的下標(biāo)數(shù)賦予NSN,否則為零。由此得到算法1的偽代碼為：

輸入：λ,τ,υ

輸出：NSN

過(guò)程N(yùn)LOS Finder(λ,τ,υ)

步驟1：F←sort(λ)

步驟2：α←fit function(12) toF

步驟3：Γ←equation (19) usingα

步驟4：if(Γ>λN)

NSN←index of maximum (υ)

else

NSN←0

end if

返回NSN

結(jié)束過(guò)程

2.2 基于NLOS識(shí)別的定位

先利用LS算法估計(jì)MS位置，且初始估計(jì)的位置表示為(x′,y′)，然后依據(jù)(x′,y′)和式(9)計(jì)算Rρ。再計(jì)算λ和υ。

while ever do

步驟1：Rρ←equation (9) using (x′,y′)

步驟2：λ←Eigenvalue(Rρ)

步驟3：α←fit function (12) toF

步驟4：υ←Eigenvector(Rρ)

步驟5：NSN←NLOS finder(λ,υ,τ)

if(NSN==0) then exit while

else

eliminate theistation in S,S′←Si

end if

end while

返回過(guò)程

3 性能仿真

3.1 仿真環(huán)境

利用Matlab 7.1軟件建立仿真平臺(tái)，分析E-NIL性能，并選擇LS[11], RWGH[12]和SRNI[8]算法作為參照，比較它們的均方根誤差性能。均方根誤差(Root Mean Square Error, RMSE)定義如式(20)所示：

(20)

在仿真實(shí)驗(yàn)中，總運(yùn)行的Monte Carlo次數(shù)Mc=3 000。移動(dòng)基站MS位于10 000 m×10 000 m內(nèi)，且基站MS的位置為(200 m,-400 m)，且τ=0.95。

3.2 實(shí)驗(yàn)一

首先分析噪聲標(biāo)準(zhǔn)方差對(duì)RMSE的影響，且σ從0至100 m變化，步長(zhǎng)為10 m，假定第一個(gè)NLOS誤差為500 m。基站數(shù)N=15，實(shí)驗(yàn)數(shù)據(jù)如圖1所示。

圖1 RMSE隨σ的變化曲線

從圖1可知，σ的增加提高了RMSE值，其原因是噪聲方差值的增加，加大測(cè)距誤差。與LS算法和SRNI算法相比，提出的E-NIL算法的RMSE得到有效控制。這些數(shù)據(jù)表明：提出的E-NIL算法能夠有效地消除NLOS誤差，提高了定位精度。

3.3 實(shí)驗(yàn)二

實(shí)驗(yàn)二分析存在NLOS誤差的基站數(shù)m對(duì)RMSE的影響。σ=10，基站數(shù)N=20，且m從1至12變化。實(shí)驗(yàn)數(shù)據(jù)如圖2所示。

圖2 RMSE隨存在NLOS誤差的基站數(shù)的影響

從圖2可知，存在NLOS誤差的基站數(shù)m對(duì)RMSE存在影響。當(dāng)m較少時(shí)，SRNI和E-NIL算法的RMSE相同，但隨著m的增加(m>7)，SRNI算法的RMSE迅速增加，而E-NIL算法的RMSE并沒(méi)有提高，保持較穩(wěn)定。與SRNI和E-NIL算法相比，LS算法的RMSE并沒(méi)有得到控制，這也說(shuō)明LS算法并沒(méi)有消除NLOS誤差的影響。

3.4 實(shí)驗(yàn)三

本次實(shí)驗(yàn)分析算法的復(fù)雜度。執(zhí)行算法的電腦參數(shù)為：Inter Core i5, 2.4 GHz CPU。基站數(shù)N從5至30變化，噪聲方差σ=10 m，實(shí)驗(yàn)數(shù)據(jù)如圖3所示。

圖3 算法的復(fù)雜度

從圖3可知，LS算法的計(jì)算時(shí)間最低，遠(yuǎn)低于E-NIL和SRNI算法。其原因在于：LS算法簡(jiǎn)單，其低的復(fù)雜度換來(lái)的是低的定位精度。而提出的 E-NIL算法的復(fù)雜度較高。隨著基站數(shù)的增加，E-NIL算法的執(zhí)行時(shí)間也迅速增加。

4 結(jié)束語(yǔ)

本文考慮了NLOS誤差對(duì)測(cè)距的影響，并在正視NLOS誤差的情況下，建立測(cè)距模型，再提出特征矢量的NLOS誤差檢測(cè)的定位E-NIL算法。E-NIL算法先基于最小二乘估計(jì)建立測(cè)距模型，再分析特征矢量，并搜索NLOS誤差，進(jìn)而剔除NLOS誤差數(shù)據(jù)，從而提高定位精度。實(shí)驗(yàn)數(shù)據(jù)表明，提出的E-NIL算法有效地提高定位精度，并降低了算法復(fù)雜度。