朱雯婷，鄒德財(cái)1,,4，尹婷

室內(nèi)無線定位場景下改進(jìn)多項(xiàng)式擬合的非視距誤差識(shí)別算法

朱雯婷1,2,3，鄒德財(cái)1,3,4，尹婷1,2,3

（1. 中國科學(xué)院 國家授時(shí)中心，西安 710600；2. 中國科學(xué)院大學(xué) 電子電氣與通信工程學(xué)院，北京 101048；3. 中國科學(xué)院 精密導(dǎo)航定位與定時(shí)技術(shù)重點(diǎn)實(shí)驗(yàn)室，西安 710600；4. 中國科學(xué)院大學(xué) 天文與空間科學(xué)學(xué)院，北京 101048）

由于全球?qū)Ш叫l(wèi)星系統(tǒng)（GNSS）無法解決在室內(nèi)場景下定位問題，室內(nèi)定位技術(shù)應(yīng)運(yùn)而生，UWB、WiFi等室內(nèi)定位技術(shù)在許多領(lǐng)域得到廣泛應(yīng)用。雖然這些技術(shù)在視距傳播時(shí)能滿足室內(nèi)定位需求，但是由于墻體等障礙物而產(chǎn)生的非視距誤差，使得定位性能急劇下降，從而無法達(dá)到室內(nèi)定位需求的精度。為克服非視距傳播帶來的定位誤差和現(xiàn)有識(shí)別算法實(shí)時(shí)性低的問題，本文提出了基于改進(jìn)的多項(xiàng)式擬合的非視距誤差識(shí)別算法。首先利用多項(xiàng)式擬合鑒別測量值中的非視距誤差并且預(yù)測距離，通過擬合曲線和測量值之間的偏差來識(shí)別非視距誤差，檢測閾值可以根據(jù)測量值自適應(yīng)的調(diào)整。然后利用卡爾曼濾波器處理測量值，在非視距傳播下，對測量值進(jìn)行加權(quán)重構(gòu)。實(shí)驗(yàn)結(jié)果表明，在非視距環(huán)境下，該算法的復(fù)雜度低，并且該算法的均方誤差較傳統(tǒng)多項(xiàng)式擬合的非視距識(shí)別算法降低了13.65%，有效抑制了非視距誤差的影響。

室內(nèi)定位；非視距誤差識(shí)別；多項(xiàng)式擬合；卡爾曼濾波

0 引言

隨著移動(dòng)通信技術(shù)的發(fā)展，利用移動(dòng)通信網(wǎng)對移動(dòng)用戶進(jìn)行定位引起了廣泛關(guān)注，各種無線定位服務(wù)業(yè)務(wù)應(yīng)運(yùn)而生[1]。雖然無線定位服務(wù)得到了很大的發(fā)展，但無線定位領(lǐng)域仍存在許多亟待解決的問題，消除測距中非視距因素導(dǎo)致的定位誤差是目前存在的問題之一。在很多場景下，電波信號(hào)的傳播為非視距傳播，會(huì)使基于到達(dá)時(shí)間（timeof arrival，TOA）測量值產(chǎn)生一個(gè)正的附加超量時(shí)延[2]，從而導(dǎo)致對未知節(jié)點(diǎn)的位置估計(jì)存在較大偏差。非視距（non-line-of-sight，NLOS）誤差是無線傳感器網(wǎng)絡(luò)定位時(shí)最主要的誤差來源[3-4]。因此，在無線傳感器網(wǎng)絡(luò)定位中，如何消除TOA測量值中NLOS誤差，提高定位精度成為關(guān)鍵問題。

NLOS識(shí)別的基本思想是選取適當(dāng)?shù)呐袥Q變量并進(jìn)行假設(shè)檢驗(yàn)，判決變量必須在LOS和NLOS環(huán)境下有明顯區(qū)分。常用的識(shí)別方法有Wylie識(shí)別算法[5]、殘差分析判決法[6]、假設(shè)檢驗(yàn)判決法[7]以及基于三階累積量的NLOS誤差識(shí)別算法[8]等。除上所述方法，基于不同的思想，國內(nèi)外學(xué)者提出了很多富有意義的NLOS定位算法。文獻(xiàn)[9]提出了一種具有魯棒性質(zhì)的移動(dòng)目標(biāo)定位算法，該算法利用測量樣本的概率密度函數(shù)估計(jì)與有偏卡爾曼濾波算法實(shí)現(xiàn)NLOS環(huán)境下的移動(dòng)目標(biāo)定位計(jì)算。文獻(xiàn)[10]提出利用NLOS誤差分布及其參數(shù)己知這一先驗(yàn)知識(shí)，通過計(jì)算得出測量值中所包含的NLOS誤差大小從而實(shí)現(xiàn)對NLOS距離測量值的校正。文獻(xiàn)[11]提出利用殘差檢驗(yàn)鑒別出NLOS測量值，然后利用LOS距離測量值完成定位計(jì)算。文獻(xiàn)[12]提出了一種線性規(guī)劃算法削弱NLOS誤差對定位的影響。文獻(xiàn)[13]利用定位基站的幾何關(guān)系，提出了一種具有約束條件的非線性最優(yōu)化算法解決NLOS定位問題。文獻(xiàn)[14]將LOS環(huán)境下的定位問題視為無約束的最優(yōu)化問題，并將NLOS環(huán)境下的定位問題轉(zhuǎn)化為具有約束條件的最優(yōu)化問題并進(jìn)行求解，在NLOS環(huán)境下具有較好的定位精度。文獻(xiàn)[15]提出了一種基于半定規(guī)劃的非視距定位算法，該算法利用半定規(guī)劃轉(zhuǎn)換方法，將NLOS環(huán)境下的定位問題轉(zhuǎn)化為凸優(yōu)化問題從而進(jìn)行求解。H. Chen提出應(yīng)用交互式多模型對LOS或者NLOS距離測量值進(jìn)行交互濾波，之后便可應(yīng)用經(jīng)典定位算法對目標(biāo)進(jìn)行定位。上述方法雖然能有效識(shí)別NLOS節(jié)點(diǎn)，但是缺乏實(shí)時(shí)性。相較于上述方法，本文提出的基于改進(jìn)多項(xiàng)式擬合的NLOS識(shí)別算法可以實(shí)時(shí)檢測出NLOS節(jié)點(diǎn)，自適應(yīng)的調(diào)整NLOS節(jié)點(diǎn)的判決門檻，提高NLOS節(jié)點(diǎn)的識(shí)別率。

1 基于多項(xiàng)式擬合的NLOS識(shí)別算法

無線傳感器網(wǎng)絡(luò)基本定位方法主要包括：基于到達(dá)時(shí)間（TOA）的定位方法、基于到達(dá)時(shí)間差（TDOA）的定位方法、基于方位角（AOA）定位方法和混合定位方法?；赥OA的定位方法原理簡單，故該定位方法是目前基于網(wǎng)絡(luò)定位應(yīng)用最廣泛的定位方法。

1.1 TOA測距模型

1.2 基于多項(xiàng)式擬合的NLOS識(shí)別算法

文獻(xiàn)[17]中NLOS檢測通過二次多項(xiàng)式擬合實(shí)現(xiàn)，該二次多項(xiàng)式擬合基于當(dāng)前測量時(shí)間對最后個(gè)歷史測量數(shù)據(jù)執(zhí)行。然后，通過從先前的多項(xiàng)式擬合得到的曲線獲得移動(dòng)節(jié)點(diǎn)的距離預(yù)測，如圖1所示。從預(yù)測值和下一個(gè)測量時(shí)間的距離測量獲得殘差。最后，將殘差用作標(biāo)識(shí)信標(biāo)節(jié)點(diǎn)與移動(dòng)節(jié)點(diǎn)之間的信號(hào)傳播條件是LOS還是NLOS的閾值。但是多項(xiàng)式擬合基于最小二乘算法原理，容易受異常值影響，所以本文提出了基于改進(jìn)的多項(xiàng)式擬合的NLOS識(shí)別算法。

圖1 多項(xiàng)式擬合示意圖

2 基于改進(jìn)的多項(xiàng)式擬合的NLOS識(shí)別算法

基于改進(jìn)的多項(xiàng)式擬合的NLOS識(shí)別算法原理主要包括3個(gè)部分：①NLOS節(jié)點(diǎn)的識(shí)別；②NLOS節(jié)點(diǎn)的抑制；③最小二乘定位算法。

2.1 NLOS識(shí)別算法原理

NLOS識(shí)別的目的是判斷測量數(shù)據(jù)是否受到NLOS傳播的影響，即信號(hào)傳播是否為NLOS傳播，以便進(jìn)行下一步處理。

基于改進(jìn)的多項(xiàng)式擬合的NLOS識(shí)別算法的一次循環(huán)流程圖如圖2所示。

圖2 算法流程圖

在本文將NLOS誤差視為異常值。

其具體步驟如下：

基于以上方法求出多項(xiàng)式系數(shù)之后，可以使用中位數(shù)法找到異常值，從而識(shí)別NLOS路徑。步驟如下：

2.2 NLOS抑制算法原理

通過NLOS識(shí)別算法判別是否是NLOS節(jié)點(diǎn)，如果該節(jié)點(diǎn)是LOS節(jié)點(diǎn)，則將該測距值進(jìn)行卡爾曼濾波處理，得到濾波后的值為NLOS抑制算法的輸出值；如果該節(jié)點(diǎn)是NLOS節(jié)點(diǎn)，則將該測距值進(jìn)行卡爾曼濾波處理，然后將通過多項(xiàng)式預(yù)測的測距值與卡爾曼濾波后的測距值加權(quán)，加權(quán)后的預(yù)測值即為NLOS抑制算法的輸出。

2.2.1 基于卡爾曼濾波的數(shù)據(jù)處理

卡爾曼濾波可以總結(jié)為：

2.2.2 加權(quán)重構(gòu)測距值

2.3 最小二乘定位算法

3 仿真結(jié)果

整體算法的流程圖如圖3所示。首先利用多項(xiàng)式擬合鑒別測量值中的非視距誤差并且預(yù)測距離，通過擬合曲線和測量值之間的偏差來識(shí)別非視距誤差，檢測閾值可以根據(jù)測量值自適應(yīng)的調(diào)整。然后利用卡爾曼濾波器處理測量值，在非視距傳播下，對測量值進(jìn)行加權(quán)重構(gòu)。按照圖3所示的流程進(jìn)行仿真實(shí)驗(yàn)。

圖3 整體算法流程圖

將信標(biāo)節(jié)點(diǎn)隨機(jī)部署在120×100m的正方形空間中，并以NLOS概率隨機(jī)生成移動(dòng)節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間的傳播條件。在仿真中，每次執(zhí)行1 000次蒙特卡洛操作時(shí)，只有一個(gè)參數(shù)以固定的增量變化，其他參數(shù)保持默認(rèn)值。均方根誤差（RMSE）被認(rèn)為是衡量算法好壞的性能指標(biāo)，從得到的定位結(jié)果出發(fā)，間接衡量了NLOS誤差識(shí)別算法的性能。由

表1 參數(shù)表

按照表1所示的參數(shù)值，信標(biāo)節(jié)點(diǎn)的個(gè)數(shù)為6個(gè)，位置分布如圖4所示。在仿真實(shí)驗(yàn)中，隨機(jī)加入NLOS誤差，對一個(gè)信標(biāo)節(jié)點(diǎn)而言，NLOS節(jié)點(diǎn)的個(gè)數(shù)為采樣點(diǎn)數(shù)乘以NLOS節(jié)點(diǎn)比率，NLOS誤差的分布如表1所示。圖4為移動(dòng)節(jié)點(diǎn)在時(shí)刻的真實(shí)位置即沒有測量噪聲和NLOS誤差。在每次模擬中，移動(dòng)節(jié)點(diǎn)的軌跡是固定的。

圖4 移動(dòng)節(jié)點(diǎn)的真實(shí)軌跡及信標(biāo)節(jié)點(diǎn)

3.1 仿真結(jié)果

通過圖5可以看出，由于改進(jìn)算法NLOS誤差的判決門檻的動(dòng)態(tài)變化，可以發(fā)現(xiàn)提高了NLOS節(jié)點(diǎn)的識(shí)別率。

圖5 NLOS誤差識(shí)別率

與文獻(xiàn)[16]相比，本文算法僅僅改變了NLOS誤差識(shí)別算法，通過RMSE數(shù)值間接判斷NLOS誤差識(shí)別算法的性能，因此從下面幾個(gè)圖表中就可以得出改進(jìn)的NLOS誤差識(shí)別算法的性能。

按照表1的參數(shù)設(shè)置，固定其他參數(shù)，變化信標(biāo)節(jié)點(diǎn)的個(gè)數(shù)，從而得到圖6。

圖6表示信標(biāo)節(jié)點(diǎn)數(shù)量與RMSE的關(guān)系。隨著信標(biāo)節(jié)點(diǎn)個(gè)數(shù)的增加，所得到的測量值增多，可利用的信息增多，因此定位精度提高，從而RMSE逐漸減小。從圖6可以看出與卡爾曼濾波算法和基于多項(xiàng)式擬合的NLOS識(shí)別算法相比，本文提出的識(shí)別算法有較好的性能，較于前兩個(gè)算法來說提升了13.65%。

圖6 RMSE（均方根誤差）隨信標(biāo)節(jié)點(diǎn)變化

圖7表示NLOS節(jié)點(diǎn)數(shù)量與RMSE的關(guān)系。由圖7可知，隨著NLOS節(jié)點(diǎn)比率的增大即非視距測量值的個(gè)數(shù)增多，因此影響多項(xiàng)式擬合的系數(shù)，造成預(yù)測的測距值誤差增大，從而影響NLOS誤差的識(shí)別率以及定位結(jié)果，按照公式（20）所示，文獻(xiàn)[16]和本文的算法的RMSE逐步增大。文獻(xiàn)[16]采用的是對所有歷史時(shí)刻的距離進(jìn)行擬合，而本文采用的算法是對部分歷史時(shí)刻的距離進(jìn)行擬合，當(dāng)NLOS節(jié)點(diǎn)比率為0.1和0.2時(shí)，測量距離受NLOS誤差影響不大，采用本文的算法就會(huì)丟失一些距離信息，從而導(dǎo)致算法性能比文獻(xiàn)[16]差。

圖7 RMSE（均方根誤差）隨NLOS比率變化

圖8表示NLOS誤差均值與RMSE的關(guān)系。隨著NLOS誤差均值的增加，非視距測距值誤差增大，因此影響多項(xiàng)式擬合的系數(shù)，造成預(yù)測的測距值誤差增大，從而影響NLOS誤差的識(shí)別率以及定位結(jié)果。與卡爾曼濾波算法和基于多項(xiàng)式擬合的NLOS識(shí)別算法相比，本文提出的算法自適應(yīng)的變換NLOS節(jié)點(diǎn)的判決門檻，對NLOS誤差有較高的識(shí)別率，算法性能提升了10.34%。

圖8 RMSE（均方根誤差）隨NLOS誤差均值變化

圖9表示NLOS誤差標(biāo)準(zhǔn)差與RMSE的關(guān)系。隨著NLOS誤差標(biāo)準(zhǔn)差的增加，非視距誤差越大，造成非視距測距值誤差增大，因此影響多項(xiàng)式擬合的系數(shù)，造成預(yù)測的測距值誤差增大，從而影響NLOS誤差的識(shí)別率以及定位結(jié)果。與卡爾曼濾波算法和基于多項(xiàng)式擬合的NLOS識(shí)別算法相比，本文提出的算法能夠更有效地識(shí)別NLOS節(jié)點(diǎn)，較基于多項(xiàng)式擬合的NLOS識(shí)別算法提升了8.18%。

圖9 RMSE（均方根誤差）隨NLOS誤差標(biāo)準(zhǔn)差變化

4 結(jié)語

多項(xiàng)式擬合的NLOS識(shí)別算法基于最小二乘算法原理，容易受異常值影響，對后續(xù)預(yù)測值產(chǎn)生影響；NLOS節(jié)點(diǎn)的判決門檻固定，導(dǎo)致NLOS節(jié)點(diǎn)的識(shí)別率低。本文提出了一種能有效識(shí)別NLOS誤差的多項(xiàng)式擬合改進(jìn)算法，利用部分歷史時(shí)刻的測距值進(jìn)行多項(xiàng)式擬合來預(yù)測測量距離，有效地降低異常值對預(yù)測模型的影響；利用中值與方差的線性關(guān)系，自適應(yīng)調(diào)整NLOS節(jié)點(diǎn)判決門檻，提高了NLOS誤差的識(shí)別率。仿真結(jié)果表明，在NLOS誤差嚴(yán)重的環(huán)境下，本算法性能較基于多項(xiàng)式擬合的NLOS識(shí)別的算法有所提升。

[1] AMUNDSON I, KOUTSOUKOS X D. A survey on localization for mobile wireless sensor networks[J]. MELT 2009: Mobile Entity Localization and Tracking in GOS Less Environments, 2009: 235-254.

[2] CAFFERY J J. A new approach to the geometry of TOA location[J]. IEEE Vehicular Technology Conference, 2000, 52(4): 1943-1949.

[3] 趙泰洋, 郭成安, 金明錄. 一種基于RFID原理的交通信息獲取系統(tǒng)與車輛定位方法[J]. 電子與信息學(xué)報(bào), 2010, 32(11): 2612-2617.

[4] 田孝華, 廖桂生. 一種有效減小非視距傳播影響的TOA定位方法[J]. 電子學(xué)報(bào), 2003, 31(9): 1429-1432.

[5] WYLIE M P, HOLTZMAN J. The non-line of sight problem in mobile location estimation[C]//Proceedings of ICUPC-5th International Conference on Universal Personal Communications, Cambridge: IEEE, 1996(2): 827-831.

[6] CONG L, ZHUANG W H. Non-line-of-sight error mitigation in TDOA mobile location[C]//GLOBECOM'01. IEEE Global Telecommunications Conference, San Antonio: IEEE, 2001(1): 680-684.

[7] BORRAS J, HATRACK P, MANDAYAM N B. Decision theoretic framework for NLOS identification[C]//VTC'98 48th IEEE Vehicular Technology Conference, Ottawa: IEEE, 1998(2): 1583-1587.

[8] 王建輝, 胡捍英, 任修坤. 基于三階累積量的NLOS誤差抑制算法及其在WCDMA系統(tǒng)中的測試[J]. 信息工程大學(xué)學(xué)報(bào), 2011, 12(4): 409-413+421.

[9] WANG J H, LI L C, HU H Y. A new approach for cellular wireless location in NLOS situations[C]//2006 First International Conference on Communications and Networking in China, Beijing: IEEE, 2006: 1-5.

[10] MAZUELAS S, LAGO F A, BLAS J. Prior NLOS measurement correction for positioning in cellular wireless networks[J]. IEEE Transactions on Vehicular Technology, 2009, 58(5): 2585-2591.

[11] CHAN Y T, TSUI W Y, SO H C, et al. Time-of-arrival based localization under NLOS conditions[J]. IEEE Transactions on Vehicular Technology, 2006, 55(1): 17-24.

[12] VENKAT S, BUEHRER R M. A linear programming approach to NLOS error mitigation in sensor networks[C]//2006 5th International Conference on Information Processing in Sensor Networks, Nashville: IEEE, 2006: 301-308.

[13] VENKATRAMAN S, CAFFERY J, YOU H R. A novel ToA location algorithm using LoS range estimation for NLoS environments[J]. IEEE Transactions on Vehicular Technology, 2004, 53(5): 1515-1524.

[14] WANG X, WANG Z X, O'DEA B. A TOA-based location algorithm reducing the errors due to non-line-of-sight(NLOS) propagation[J]. IEEE Transactions on Vehicular Technology, 2003, 52(1): 112-116.

[15] CHEN H, WANG G, WANG Z, et al. Non-line-of-sight node localization based on semi-definite programming in wireless sensor networks[J]. IEEE Transactions on Wireless Communications, 2012, 11(1): 108-116.

[16] WANG Y, YAN Y, LI Z J, et al. A mobile localization method in smart indoor environment using polynomial fitting for wireless sensor network[J]. Journal of Sensors, 2020: 1-17.

[17] 蔡利棟, 傅瑜. 穩(wěn)健的孤立點(diǎn)檢測—從中位數(shù)求方差[C]//中國計(jì)算機(jī)學(xué)會(huì)理論計(jì)算機(jī)科學(xué)專業(yè)委員會(huì), 長春: 2006年全國理論計(jì)算機(jī)科學(xué)學(xué)術(shù)年會(huì), 2006: 185-187.

Non-line-of-sight error recognition algorithm based on improved polynomial fitting in indoor wireless positioning

ZHU Wen-ting1,2,3, ZOU De-cai1,3,4, YIN Ting1,2,3

(1. National Time Service Center, Chinese Academy of Sciences, Xi’an 710600, China;2. School of Electronic, Electrical and Communication Engineering, University of Chinese Academy of Sciences, Beijing 101048, China;3. Key Laboratory of Precise Positioning and Timing Technology, Chinese Academy of Sciences, Xi’an 710600, China;4. School of Astronomy and Space Science, University of Chinese Academy of Sciences, Beijing 101048, China)

Since the Global Navigation Satellite System cannot solve the positioning problem in indoor scene, indoor positioning technology arises at the historic moment. UWB, WiFi, etc indoor positioning technologies are widely used in various fields. Although they can meet the requirements of indoor positioning during line of sight propagation, the non-line-of-sight (NLOS) error caused by obstacles such as walls brings a sharp drop in positioning performance, and the accuracy cannot meet the needs of indoor positioning. In order to alleviate NLOS error and solve the problem of low recognition rate of existing algorithms, this study proposes an improved polynomial fitting algorithm of NLOS error recognition. Firstly, the method employs polynomial fitting to accomplish both NLOS identification and distance prediction. NLOS is identified via deviation between fitted curve and measurements. Detection threshold can be adjusted adaptively according to measurements. Then, it processes the measurements with a Kalman filter (KF), conducting weighting filter in the case of NLOS condition. The experimental results show that the method with low complexity performance in NLOS and the root mean square error improves 13.65% compared with the traditional polynomial fitting approach, and effectively suppresses the NLOS error.

indoor positioning; non-line-of-sight error recognition; polynomial fitting; Kalman filter

10.13875/j.issn.1674-0637.2021-01-0055-11

朱雯婷，鄒德財(cái)，尹婷. 室內(nèi)無線定位場景下改進(jìn)多項(xiàng)式擬合的非視距誤差識(shí)別算法[J]. 時(shí)間頻率學(xué)報(bào), 2021, 44(1): 55-65.

2020-07-14；

2020-09-16

載人航天創(chuàng)新性預(yù)研資助項(xiàng)目（17680601）