運用海倫公式的最優(yōu)化非視距抑制定位算法*

李溯南,華驚宇,*,李佳珉,盧為黨,陳芳妮,余旭濤

(1.浙江工業(yè)大學通信網(wǎng)應用技術研究省重點實驗室,杭州 310023;2.東南大學移動通信國家重點實驗室,南京 210096)

自從1996年美國聯(lián)邦通信委員會公布E-911定位精度的標準以來,無線定位技術與基于位置的服務已經(jīng)成為研究熱點,在目前的無線傳感網(wǎng)和物聯(lián)網(wǎng)應用中具有廣泛的應用[1]。在無線傳感網(wǎng)中,通常包括3個以上固定節(jié)點SN(Static Node)和若干移動節(jié)點MN(Mobile Node),而SN的地理位置是已知的,定位主要針對MN。另一方面,三邊定位方法從節(jié)點的幾何關系出發(fā),采用某個定位參量建立方程組并求解獲取MN位置估計。其中算法采用的定位參量包括到達時間(TOA)[2]、到達時間差(TDOA)[3-4]、接收信號強度(RSS)[5]、信號到達角(AOA)[6]以及其他一些混合參數(shù)[1,7-8]。

在實際的定位應用中,定位算法會受到兩類誤差的影響。一是測量噪聲,通常建模為零均值的高斯變量[9]。在視距LOS(Line of Sight)傳輸條件下,測量噪聲是影響定位精度的主要因素。而在非視距NLOS(Non-Line of Sight)傳輸環(huán)境中,信號傳輸路徑中障礙物阻擋產(chǎn)生的非視距誤差是影響定位精度的主要因素。例如,在蜂窩網(wǎng)絡中非視距誤差可以達到數(shù)百米[10]。遺憾的是,非視距誤差的概率分布模型往往無法得到,所以很難消除非視距誤差對定位精度的影響。

在定位算法中對NLOS誤差的處理主要有三類方法。第1類就是對NLOS誤差進行參數(shù)化建模[11],但是如前所述,實際環(huán)境中的NLOS誤差多變以致無法精確建立概率模型,因此這一類方法的使用十分受限。第2類方法就是從大量SN中識別出受非視距誤差影響的SN并將其剔除,僅使用LOS傳輸?shù)腟N進行定位[12],但是這類方法首先要求SN的數(shù)量必須達到要求,同時必須有至少3個SN滿足視距內(nèi)傳輸?shù)臈l件,因此在NLOS誤差影響比較嚴重的環(huán)境中無法使用。第3類方法就是從SN與MN之間的幾何關系出發(fā),對得到的距離測量值進行加權和最優(yōu)化搜索,之后再根據(jù)加權后的距離測量值估計MN位置[13-15]。

本文主要研究第3類最優(yōu)化方法,利用SN與MN之間的定位幾何關系提出了面積殘差的定義,進而建立二次規(guī)劃問題并求解以實現(xiàn)測量距離的有效加權,最終得到MN的位置估計。算法中的面積殘差基于海倫公式和兩類測量距離構建,最優(yōu)化的代價函數(shù)則同時包含面積殘差和圓交點懲罰函數(shù)的影響。仿真分析表明,在消除非視距誤差對于定位精度的影響上,本文提出的算法優(yōu)于對比算法,且可以在SN數(shù)量較少時工作良好。同時仿真中還發(fā)現(xiàn)在NLOS誤差較大或者SN數(shù)目增加時,本文算法將有更好的性能。

1 非視距傳輸環(huán)境下的測距模型與定位方法

MN與SN之間的距離可以表示為:

(1)

式中:(xi,yi)代表第i個SN的位置,而(x,y)代表需要定位的MN的位置。假設測量距離為di,則有

ri=αidi

(2)

在NLOS傳輸環(huán)境中,αi總落在0和1之間,這是因為信號無論被折射或者反射都會使得測量距離大于真實距離。即使不考慮NLOS影響,在測量距離中還包含測量誤差,它一般遠小于NLOS誤差。

類似于文獻[13,15],聯(lián)合(1)和(2),易得

(3)

對方程組(3)化簡得到

(4)

Y=AX

(5)

式中

根據(jù)最小二乘原理,可以得到向量X的解為

(6)

通過上面的公式可知,如果距離的加權向量已知,或者可以精確的獲取,就可以精確地計算出SN與MN之間的實際距離,進而得到最終的位置估計[15]。

2 最優(yōu)化定位算法

2.1 面積殘差原理

圖1中第1個SN(SN1)和第2個SN(SN2)的測距可以得到一個MN坐標估計,它與SN1/SN2構成一個三角形,而真實的MN位置與兩個SN同樣構成一個三角形。這兩個三角形的面積可以由海倫公式計算得到。如果測距是精確的,那么這兩個三角形面積應該是相等的,否則面積差值大于零。因此對于N個SN,我們可以將它們分成若干組,每組兩個SN。每一組都可以根據(jù)圖1原理計算面積差值,而所有分組的面積差值之和將與權值向量的精確性有關,可以用于定義面積殘差,具體在下一小節(jié)論述。

圖1 NLOS環(huán)境中面積殘差原理圖

2.2 面積殘差與代價函數(shù)定義

(7)

以及使用原始測距作為自變量的MN—SN三角形面積表達式

(8)

如2.1所述,如果不存在任何誤差這兩個面積表達式的結(jié)果應該是相同的,即:

(9)

將式(9)兩端平方并化簡得到

(10)

考慮所有的SN分組,我們可以得到N-1條方程:

(11)

方程組(11)左邊減去右邊可以等效表征圖1中三角形面積表達式的差值,則我們可以構建面積殘差代價函數(shù)[16]:

(12)

定義權值向量v如下:

(13)

(14)

式中

需要注意加權縮放之后的距離應該保證所有SN的定位圓交于一點,因此需要在上述代價函數(shù)中增加懲罰函數(shù),即:

(15)

式中:Xi與‖·‖分別表示第i個SN坐標以及向量模值。則最終的代價函數(shù)為

(16)

式中:D為一個足夠大的常數(shù),本文中選為1010。

2.3 約束二次規(guī)劃問題

綜合以上2小節(jié),本文定位算法可以歸結(jié)為一個二次規(guī)劃問題

(17)

與文獻[12,14]類似,向量v的下限vmin為:

(18)

3 仿真結(jié)果

3.1 測距噪聲與NLOS誤差強度的影響

圖2給出非視距誤差在10 m～35 m上均勻分布時的定位誤差累計分布函數(shù)(CDF),可以看出即使是表現(xiàn)最好的TOA CLS算法其誤差也要大于本文算法。在CDF為0.9時,本文算法的定位誤差相比其他算法至少小40%。

圖2 NLOS誤差服從10 m～35 m均勻分布時的累積分布函數(shù)

圖3給出NLOS誤差最大值不同取值對于定位性能的影響,其中MIN固定為5 m。從圖中可以發(fā)現(xiàn)本文算法具有最小的平均定位誤差,且定位誤差差距大于3m。這表明本文算法對于NLOS誤差的適應性優(yōu)于對比算法。

圖3 不同MAX值對性能的影響

圖4給出測距噪聲標準差不同取值對于定位性能的影響,其中MAX=35 m?？梢钥吹剿兴惴▽τ跍y距噪聲標準差的敏感性都不強,但是本文算法具有最小的平均定位誤差,定位誤差的性能優(yōu)勢超過5 m。

圖4 不同噪聲標準差對性能的影響

3.2 SN數(shù)目對定位精度的影響

圖5 3個SN時的算法性能對比

圖6 7個SN時的算法性能對比

5 結(jié)論

非視距誤差是無線定位中的一個重要影響因素,它顯著降低了定位的準確性。因此本文在傳統(tǒng)最優(yōu)化定位基礎上,利用海倫公式構建了面積殘差和代價函數(shù),綜合運用約束二次規(guī)劃和最小二乘方法抑制非視距誤差的影響。仿真結(jié)果表明,在不同強度的非視距誤差和測距噪聲下,文中所提出的算法都要優(yōu)于對比算法,且本文算法對于SN數(shù)目敏感性較低,可以用于SN數(shù)目較少的情形。

[1] Cheung K W,So H C,Ma W K,et al,A Constrained Least Squares Approach to Mobile Positioning:Algorithms and Optimality[J]. EURASIP Journal on Advances in Signal Processing,2006,2006(1):1-23.

[2] Wang X,Wang Z,O’Dea B,A TOA-Based Location Algorithm Reducing the Errors Due to non-Line-of-Sight(NLOS)Propagation[J]. IEEE Trans. Vehicular Technology,2003,52(1):112-116.

[3] Chan Y T,Ho K C,A simple and efficient estimator for hyperbolic location[J]. IEEE Trans Signal Processing,1994,42(8):1905-1915.

[4] Zhang H,Yu M,Cui X,et al,An improved Taylor series based location algorithm for IEEE 802.15.4a channels[C]//Proc 2011 IEEE Pacific Rim Conference on Communications,Computers and Signal Processing,2011:499-503.

[5] Yan Y,Efficient convex optimization method for underwater passive source localization based on RSS with WSN[C]//Proc 2012 IEEE International Conference on Signal Processing,Communication and Computing,2012:171-174.

[6] Lee Y S,A study on the performance of wireless localization system based on AOA in WSN environment[C]//Proc 2011 Third International Conference on Intelligent Networking and Collaborative Systems,2011:184-187.

[7] Zhaounia M,Landolsi M A,Bouallegue R,Hybrid TOA/AOA mobile localization with NLOS mitigation in ring scattering environments[C]//Proc 2008 3rd International Symposium on Wireless Pervasive Computing,2008:370-373.

[8] 嚴長虹,馬靜,三維傳感網(wǎng)空間RSS與AOA混合測量的精確定位方法[J]. 傳感技術學報,2017,30(3):450-455.

[9] Chen P,A Non-Line-of-Sight Error Mitigation Algorithm in Location Estimation[C]//Proc 1999 IEEE Wireless Communications and Networking Conference,1999:316-320.

[10] Silventoinen M,Ranralainen T,Mobile station emergency locating in GSM[C]//Proc 1996 IEEE International Conference on Personal Wireless Communication,1996:232-238.

[11] AL-JAZZAR S,Caffery I,ML and Bayesian TOA location estimators for NLOS environments[C]//Proc 2002 IEEE VTC,2002:856-860.

[12] Chan Y T,Tsui W Y,Time-of-Arrival based localization under NLOS conditions[J]. IEEE Trans. Vehicular technology,2006,55(1):17-24.

[13] Venkatraman S,Caffery J,You H R,A novel TOA location algorithm using LOS range estimation for NLOS environments[J]. IEEE Trans Vehicular technology,2004,53(5):1515-1524.

[14] Hua J Y,Zheng Z L,Jiang B,et al,A study on residual weighting algorithm for mobile localization[J]. Information Technology Journal,2013,12(5):640-647.

[15] 鄭志龍,華驚宇,江彬,等,運用最優(yōu)化原理的新型非視距抑制無線定位算法[J]. 傳感技術學報,2013,26(05):722-727.

[16] 龔純,王正林. 精通MATLAB最優(yōu)化計算[M]. 北京:電子工業(yè)出版社,2009:179-205.