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

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

(1.浙江工業(yè)大學(xué)通信網(wǎng)應(yīng)用技術(shù)研究省重點(diǎn)實(shí)驗(yàn)室,杭州 310023;2.東南大學(xué)移動(dòng)通信國(guó)家重點(diǎn)實(shí)驗(yàn)室,南京 210096)

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

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

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

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

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

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

(1)

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

ri=αidi

(2)

在NLOS傳輸環(huán)境中,αi總落在0和1之間,這是因?yàn)樾盘?hào)無(wú)論被折射或者反射都會(huì)使得測(cè)量距離大于真實(shí)距離。即使不考慮NLOS影響,在測(cè)量距離中還包含測(cè)量誤差,它一般遠(yuǎn)小于NLOS誤差。

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

(3)

對(duì)方程組(3)化簡(jiǎn)得到

(4)

Y=AX

(5)

式中

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

(6)

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

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

2.1 面積殘差原理

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

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

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

(7)

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

(8)

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

(9)

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

(10)

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

(11)

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

(12)

定義權(quán)值向量v如下:

(13)

(14)

式中

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

(15)

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

(16)

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

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

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

(17)

與文獻(xiàn)[12,14]類似,向量v的下限vmin為:

(18)

3 仿真結(jié)果

3.1 測(cè)距噪聲與NLOS誤差強(qiáng)度的影響

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

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

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

圖3 不同MAX值對(duì)性能的影響

圖4給出測(cè)距噪聲標(biāo)準(zhǔn)差不同取值對(duì)于定位性能的影響,其中MAX=35 m。可以看到所有算法對(duì)于測(cè)距噪聲標(biāo)準(zhǔn)差的敏感性都不強(qiáng),但是本文算法具有最小的平均定位誤差,定位誤差的性能優(yōu)勢(shì)超過5 m。

圖4 不同噪聲標(biāo)準(zhǔn)差對(duì)性能的影響

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

圖5 3個(gè)SN時(shí)的算法性能對(duì)比

圖6 7個(gè)SN時(shí)的算法性能對(duì)比

5 結(jié)論

非視距誤差是無(wú)線定位中的一個(gè)重要影響因素,它顯著降低了定位的準(zhǔn)確性。因此本文在傳統(tǒng)最優(yōu)化定位基礎(chǔ)上,利用海倫公式構(gòu)建了面積殘差和代價(jià)函數(shù),綜合運(yùn)用約束二次規(guī)劃和最小二乘方法抑制非視距誤差的影響。仿真結(jié)果表明,在不同強(qiáng)度的非視距誤差和測(cè)距噪聲下,文中所提出的算法都要優(yōu)于對(duì)比算法,且本文算法對(duì)于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] 嚴(yán)長(zhǎng)虹,馬靜,三維傳感網(wǎng)空間RSS與AOA混合測(cè)量的精確定位方法[J]. 傳感技術(shù)學(xué)報(bào),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ùn)用最優(yōu)化原理的新型非視距抑制無(wú)線定位算法[J]. 傳感技術(shù)學(xué)報(bào),2013,26(05):722-727.

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