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

(1.四川水利職業技術學院信息工程系， 四川崇州 611231; 2.重慶大學計算機學院， 重慶 400044)

0 引言

如今，多類應用需要目標定位算法，如無線傳感網絡[1-2]、雷達系統[3-4]。常利用測量技術實現目標定位，如接收信號強度(Received Signal Strength, RSS)、到達時間(Time of Arrival, TOA)和到達角度(Angle of Arrival, AOA)，其中基于TOA測量是常用的測距技術。在基于TOA測量的測距技術中，每個基站以自己離目標節點的距離為半徑以自己為圓心構建一個圓。理論上，由多個基站所形成的多個圓的共同交點就是目標節點位置。

如果TOA信號是沿直線傳輸，則可較準確地測量基站離目標節點的距離。然而，噪聲會影響TOA信號，降低了測距準確性。換言之，如果TOA信號是通過反射達到的，測量距離將超過真實距離。這種情況也稱為非視距(Non Line of Sight, NLOS)問題，其能引起較大的測距誤差。NLOS誤差也總會加大測距值，而不是縮小測距值。

通常，可通過使用大量傳感節點提高定位精度。如文獻[5]引用大量傳感節點測量電脈沖信號的始端。在大量傳感節點系統中，NLOS問題也稱為源誤差。然而，基于測量數據識別NLOS情況是非常耗時，且耗時量隨基站數呈指數關系。因此，如何識別NLOS情況成為無線傳感網絡的研究熱點。

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

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

1 問題描述

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

在NLOS的環境下，第i個BS獲取的觀測數據：

(1)

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

(2)

當無NLOS存在時，就可利用最小二乘法(Least Square, LS)算法估計MS位置：

(3)

從式(3)可知，式(3)是MS位置的非線性函數。因此，任何非NLOS模型的求解均會導致較大的估計誤差。而識別NLOS位置，并處理相關的測距值是處理NLOS問題的有效方式。

2 E-NIL算法

2.1 尋找NLOS誤差

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

(4)

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

再計算ρ的自相關值Rρ，如式(5)所示：

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

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

(5)

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

Rρ=nnH+σ2I

(6)

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

(7)

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

(8)

比較式(7)和式(8)，不難發現Rρ的最大特征值所對應的特征向量是n。因此，如果確定Rρ，則可通過尋找最大特征值和相應的特征向量，識別NLOS。

為此，對ρ進行M次測量，并進行近似求解，便可計算Rρ：

(9)

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

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

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

(10)

式中，γ表示觀察數與抽樣率，其控制Marceko分布統一特性，且

(11)

此定理的證明過程可參見文獻[10]。

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

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

(12)

式中，α為控制參數。

假定λi為Rρ的特征值，且i=1,2,…,N。對N個特征值進行排序，可建立離散函數：

(13)

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

依據式(12)可知，通過控制參數α調整式(12)函數。為此，最初，先對控制參數α進行猜測，然后，再采用梯度下降算法優化控制參數α。據此，最初，令控制參數α的初始值為零，然后，定義式(14)和式(15)的變量：

(14)

(15)

假定δ表示猜測參數α所導致的誤差，其定義如式(16)所示：

δ=[hTh]-1hTz

(16)

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

α←α+δ

(17)

接下來，定義σ2小于預定閾值Γ的概率τ：

(18)

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

(19)

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

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

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

輸入：λ,τ,υ

輸出：NSN

過程NLOS 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

結束過程

2.2 基于NLOS識別的定位

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

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

返回過程

3 性能仿真

3.1 仿真環境

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

(20)

在仿真實驗中，總運行的Monte Carlo次數Mc=3 000。移動基站MS位于10 000 m×10 000 m內，且基站MS的位置為(200 m,-400 m)，且τ=0.95。

3.2 實驗一

首先分析噪聲標準方差對RMSE的影響，且σ從0至100 m變化，步長為10 m，假定第一個NLOS誤差為500 m。基站數N=15，實驗數據如圖1所示。

圖1 RMSE隨σ的變化曲線

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

3.3 實驗二

實驗二分析存在NLOS誤差的基站數m對RMSE的影響。σ=10，基站數N=20，且m從1至12變化。實驗數據如圖2所示。

圖2 RMSE隨存在NLOS誤差的基站數的影響

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

3.4 實驗三

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

圖3 算法的復雜度

從圖3可知，LS算法的計算時間最低，遠低于E-NIL和SRNI算法。其原因在于：LS算法簡單，其低的復雜度換來的是低的定位精度。而提出的 E-NIL算法的復雜度較高。隨著基站數的增加，E-NIL算法的執行時間也迅速增加。

4 結束語

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