非視距環境中的無線網絡殘差加權定位算法*

尹燁佳,華驚宇,李 楓,張 昱,余旭濤

(1. 浙江工業大學信息工程學院,杭州 310023;2.浙江工商大學信息與電子工程學院,杭州 310018;3.東南大學移動通信國家重點實驗室,南京 210096)

近十幾年以來,無線通信網絡中目標節點的精確定位已成為人們關注的熱點。目前,主要的定位技術可以分為基于衛星定位以及基于地面無線定位兩大類。前者主要用于戶外環境中,例如基于GPS的導航,其中非軍用用戶可以實現大約幾十米的定位誤差。但是GPS很難應用于室內定位以及那些無法獲取GPS位置的環境中。因此,我們的研究將關注于地面無線定位問題,例如基于WSN的無線定位。

地面無線定位按照是否基于測距又可分為range-free和range-based兩大類。前者往往需要高密度的節點分布作為條件[1],但是,現實環境中網絡規模和節點密度差異性非常大,因此,本文主要研究基于range-based的定位方法,這類方法主要取決于選擇何種定位參數。現有定位技術中主要有基于到達時間(TOA)估計[2-3],基于到達時間差(TDOA)估計[4-5],基于信號場強(RSSI)估計[6],基于到達方向(AOA)估計[7],以及基于混合參量估計,比如TOA/AOA,TDOA/AOA和RSS/AOA[8-9]。此外,這類range-based的定位方法存在兩種非理想因素,一種是測量誤差,另一種是由信號傳播過程中折射和反射等現象引起的非視距NLOS(Non-Line Of Sight)誤差。前者一般被定義為均值為零的高斯變量,相對而言,這種誤差的標準差一般很小[10];而后者NLOS誤差則是無線定位中最為主要的誤差,NLOS傳播會導致較大的時延和角度偏差,因此會大大降低無線定位算法的精度。在實際的無線網絡中,它的誤差值可以到達通信半徑的20%～50%[11],而且由于實際環境中無線網絡的復雜性無法對其進行精確建模,所以NLOS誤差的抑制和消除已成為無線定位算法能否實際應用的關鍵。

為提高非視距環境下的定位精度,目前主要存在以下幾類誤差抑制的算法:第一類叫模型法,就是利用類似訓練的方法對非視距誤差先進行精確建模,然后根據建立的模型來估計目標節點的位置[12-13]。但是由于實際環境的復雜性和動態性很難得到一個精確的模型,因此該類算法很難得到廣泛應用。第二類叫檢測法,首先利用LOS節點與NLOS節點的參數差異,識別出基于視距傳輸的靜態節點(LOS-SN),剔除非視距傳輸的靜態節點(NLOS-SN),最后只利用LOS傳輸的靜態節點進行位置估計[14-15]。如果能夠正確識別出所有的視距傳輸的靜態節點,且LOS-SN節點數足夠多的條件下,那么該算法的定位精度將會非常高,但是由于虛警率的存在很難做到檢測的正確性,因此該類算法的實際定位精度往往很難滿足實際需求。第三類算法是應用所有的SN信息,包括LOS節點和NLOS節點,然后利用優化算法得到目標節點位置,這種方法雖然能得到較高的定位精度,但是計算復雜度比較高[3-4],如半正定規劃SDP算法,其利用的是半正定規劃的內點法,這類方法屬于多項式時間算法,迭代復雜性較高。第四類算法叫權重法,就是對節點進行分組,并給每一組的臨時位置估計分配合適的權重并求和以提高目標節點位置的估計精度。我們往往利用幾何關系和代數關系,最典型的就是利用殘差參數構建加權函數[16-18]。這類算法的優點是能區別利用LOS及NLOS節點的信息,對于LOS節點的信息給予比較大的權重值,對于NLOS節點就給予較小的權重值,最終科學充分地利用LOS節點信息,提高定位精度。傳統權重類定位算法的缺點是權重的選擇設計不夠科學,往往不能充分利用LOS節點信息,所以本文提出了一種改進的權重定位算法。

本文在傳統的權重算法上進行改進,主要方法如下,首先對所有靜態節點(SN)進行分組,由于選用的參數不同,每組都可得到3個目標節點估計位置。同時因為存在測距誤差和NLOS誤差,得到的目標位置估計之間必然存在位置差,將該差值定義為臨時定位殘差。區別于傳統的殘差加權定位算法,本文根據所選殘差特點,提出用殘差的高次冪作為加權函數,并通過仿真尋找最優的加權函數。最后給每個目標估計位置分配相應的權值并加權求和得到最終的TN估計位置。主要貢獻有①采用了一種新的殘差定義,即臨時定位殘差;②結合該殘差值的特點提出了新的權重函數,并根據殘差值對權重函數做了優化搜索。計算機仿真結果表明本文提出的算法要優于其他對比的抗NLOS定位算法,尤其是對比傳統的殘差加權定位算法,定位精度得到了較大的提高。同時本文提出的算法屬于線性類算法,其計算復雜度與輸入的數據規模成正比,計算復雜度較優化類算法低。

1 基于臨時定位的殘差定義

圖1 定位幾何模型

假設目標節點TN的坐標為(x,y),靜態節點SN的坐標為(xi,yi),那么TN和SN之間的距離可以表示成:

(1)

θi=arctan[(y-yi)/(x-xi)]

(2)

利用靜態節點SN1和SN2所得的測距,可以得到如下方程組:

(3)

(4)

(5)

類似地,點B坐標的求解方程為:

(6)

如用矩陣形式表示,以點A為例:

Y=AXA

(7)

如果傳輸環境中不存在NLOS,那么目標節點TN的位置即可通過最小二乘算法求解,即

(8)

同樣地,點B的坐標也是可以通過解類似于(8)的方程組得到。因此可以定義點A和B之間距離即為臨時定位殘差:

(9)

從圖1中我們可知,兩個定位圓的交點有2個,為簡便,我們可以簡單地將殘差定義為

(10)

那么臨時定位殘差就可以表示成:

(11)

上式中的C′表示在C,F兩點中找出距離A點或B點更近的點,將其記為C′。從上述殘差的定義中我們可以看出,如果僅存在測距噪聲,那么上述得到的三個TN位置估計都是相對較精確的,那么所對應的臨時殘差值也很小。如果存在NLOS傳輸的靜態節點,那么由于利用的定位參數本身存在很大偏差,據此得到的估計位置就會遠遠偏離真實位置,而且偏離的趨勢也會有所不同,這就導致了殘差值的上升。據上圖1所示,雖然理論上F點也可作為目標節點的臨時估計位置,但是所有的臨時估計位置應該集中在一個小范圍內,由于F點距離其余的幾個臨時估計位置較遠,所以本文拋棄了F點。

2 臨時定位殘差加權算法

圖2 算法流程圖

得到每個分組的TN臨時位置估計以及相應的權重值后,確定最終目標位置估計,如下所示:

(12)

式中:Wi(Δ)表示和臨時定位殘差相關的加權函數,ETNi表示第i個靜態節點組對TN的估計位置,它可以表示為

(13)

經過分析可知,臨時定位殘差較小的靜態節點組得到的中間位置估計應當獲取較大的權重,這就說明選擇的權重函數應該是一個減函數。在傳統RWGH算法中,直接利用殘差的倒數作為權值,這就可能導致在靜態節點數目較少的情況下對NLOS誤差的抑制不足,我們的仿真結果也印證了這一點。分析造成上述現象的原因,主要還是因為RWGH這種算法的加權函數選擇過于平庸,以及所采用的殘差定義對于NLOS誤差也不夠敏感,因此我們考慮使用函數值變動更加劇烈的高冪次方作為加權函數,并通過實際仿真驗證我們的假設。

Wi(Δ)=(1/Δ)n,n≥2

(14)

如圖3所示,對比各條曲線可知,權重函數(即臨時定位殘差的n次方)的n值越大,其對應曲線越陡,表示對應的權重函數越靈敏。如此一來,我們就可充分利用LOS-SN的信息,大大提高了最終的定位估計精度。另外,對比n=5和n=10的曲線可知兩者趨于重合,所以不再研究n>5的權重函數。

圖3 不同權重函數的數值變化

3 計算機仿真與分析

本文的仿真全都是在MATLAB中完成,其中靜態節點坐標如下:(0,0),(100,100),(-100,100),(-100,-100),(100,-100),單位是米。并且假設測距和AOA測量值的誤差均為零均值的高斯變量,假設NLOS傳輸對距離測量帶來的誤差為0和max之間服從均勻分布的變量[16],而AOA的NLOS誤差則為零均值的高斯變量,但其標準差相對較大[19]。

3.1 加權函數的確定

假設測量距離標準差MDSD(Measuring Distance Standard Deviation)為1 m,測量角度標準差MASD(Measuring Angle Standard Deviation)為1°,NLOS的最大值max為40 m。

通過對比圖3中的1次方,2次方和5次方加權函數的曲線,可知殘差的冪次方所對應的數值對定位精度的影響非常顯著,為進一步提高定位精度,接下來我們以5次方加權為基準對冪次方進行小數搜索。

從圖4可知,冪指數值選在5附近時性能差別不大,從仿真結果看,我們選取最優值n=4.8。

圖4 不同冪指數的CDF圖

接下來我們選取不同的算法殘差進行比較。其中posWk代表以臨時定位殘差倒數的k次方作為加權系數,同時我們引入最小二乘方法作為對比算法。

圖5顯示的是選擇不同權重函數時的CDF圖,從圖5(a)和圖5(b)可以發現,posW1的定位誤差小于10 m的概率在2個LOS-SN條件下達到了87%,當LOS-SN數量達到3個時,概率更是達到了100%,而且其RMSE曲線在2個LOS-SN以及3個LOS-SN的情況下均要明顯優于傳統的LS算法,但是和posW4.8相比,后者的定位誤差即使是在2個LOS-SN的條件下,定位誤差值小于5 m的概率也高達94%,在3個LOS-SN的條件下誤差值小于5 m的概率更是達到了99%,其定位性能顯然要優于posW1算法。這就表明,對于利用定位殘差的加權定位算法而言,要根據選擇的殘差定義,選擇函數值變化較為劇烈的函數作為加權函數,從而使LOS估計位置可以得到充分的加權。

圖5 選擇不同權重函數的CDF圖

圖6 選擇不同權重函數的RMSE圖

3.2 不同算法的綜合比較

接下來我們將分別研究測量距離標準差MDSD,測量距離標準差MASD,以及非視距NLOS誤差對以下不同算法精度的影響,仿真條件為:在 2個LOS靜態節點和3個LOS靜態節點的環境中進行,其中NLOS誤差在0～max之間均勻分布。

表1 對比算法描述

①測量距離標準差的影響

圖7給出的是MDSD對各算法精度的影響。從圖中可以看出,CLS,opt-LLOP,RWG以及HFOP這四種算法產生的估計誤差較大,相比而言,SDP的定位性能較前四者有了顯著的改進,特別是當環境中只有2個LOS-SN的條件下,但是跟本文提出的算法相比還是存在明顯的差距。顯然,我們可以發現本文提出的算法的定位性能要明顯優于其他幾種對比算法。雖然隨著MDSD的增加,該算法的定位誤差有所上升,但依然低于其他的對比算法。這是因為隨著MDSD的增加,利用LOS-SN求得的目標估計位置所獲得的權重值也隨之降低,從而造成定位性能有所下降。此外從仿真結果可以看出,隨著LOS-SN數量的增加posW4.8曲線接近于克拉美羅下界,也就是說本文提出的算法隨著LOS-SN數量的增多,定位性能更好。

圖7 MDSD對算法精度的影響

②測量角度標準差的影響

如圖8所示是測量角度標準差MASD與定位均方根誤差之間的關系,我們可以發現,隨著橫坐標MASD值的變大,除TOA/AOA-LS算法外,其余對比算法所對應的曲線基本持平,這是因為這些算法定位過程中沒有利用角度信息。但是觀之本文提出的posW4.8和對比算法TOA/AOA-LS,其對應的曲線隨著橫坐標的增大有明顯的上升趨勢,這是因為測角誤差的增加造成了分配給精度較高的臨時位置估計的權值下降了,使得定位精度也隨之降低。圖8表明本文提出的算法其定位精度遠高于TOA/AOA-LS算法,這主要得益于新的權重函數和殘差的良好適配,同時對比其他算法,本文所提算法的性能保持著明顯的優勢。

③不同max值的影響

圖9 NLOS誤差最大值max對各算法定位精度影響

圖9的橫坐標表示測量距離的NLOS誤差最大值,縱坐標是定位均方根誤差(RMSE)。對比圖中各曲線可知,傳統的殘差權重算法(RWGH),線性最優化算法(opt-LLOP),約束最小二乘算法(CLS)以及運用海倫公式最優化算法(HFOP)的定位誤差隨著max的增加上升趨勢都很明顯。觀之SDP算法,隨著max值的增加,其上升幅度雖然沒有前四者明顯,但還是高于本文提出的posW4.8算法。從圖中可知本文提出算法的精度隨著NLOS誤差的增大只是略有起伏,基本呈平緩趨勢,也就是說本文提出的算法即使在NLOS誤差較大的惡劣環境下也能具有較高的定位精度。

④角度域NLOS誤差的影響

圖10是非視距傳輸的角度測量誤差值與定位均方根誤差之間的關系。觀察圖中的曲線可知,隨著角度NLOS誤差的增加,各算法的RMSE值的變化并不顯著。因為所有的對比算法都未利用到測角信息。而對于posW4.8算法,雖然從理論上分析,角度誤差的增大會降低該算法的定位性能。但是從上述仿真結果可知,本文提出的算法的定位精度隨著角度誤差的增加基本趨于平緩,特別是在LOS靜態節點數目為3時。這是因為隨著角度NLOS誤差的增加,雖然使得目標臨時位置估計的定位誤差值變大,但是由于其對應的權重函數值較小,所以最終對定位性能影響并不大。

圖10 AOA的NLOS誤差對各算法精度的影響

4 結論

為提高非視距環境下的定位精度,本文提出用目標臨時位置估計之間的差值構建新的權重函數,并以臨時位置估計加權和改善了定位性能。對比RWGH算法,本文算法不僅在定位精度上有了很大的提高,而且還降低了對LOS靜態節點數目的要求。對比SDP類優化算法,本文提出的算法大大降低了計算復雜度同時也依然保持了性能優勢。