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

朱雯婷，鄒德財1,,4，尹婷

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

朱雯婷1,2,3，鄒德財1,3,4，尹婷1,2,3

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

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

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

0 引言

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

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

1 基于多項式擬合的NLOS識別算法

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

1.1 TOA測距模型

1.2 基于多項式擬合的NLOS識別算法

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

圖1 多項式擬合示意圖

2 基于改進的多項式擬合的NLOS識別算法

基于改進的多項式擬合的NLOS識別算法原理主要包括3個部分：①NLOS節(jié)點的識別；②NLOS節(jié)點的抑制；③最小二乘定位算法。

2.1 NLOS識別算法原理

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

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

圖2 算法流程圖

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

其具體步驟如下：

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

2.2 NLOS抑制算法原理

通過NLOS識別算法判別是否是NLOS節(jié)點，如果該節(jié)點是LOS節(jié)點，則將該測距值進行卡爾曼濾波處理，得到濾波后的值為NLOS抑制算法的輸出值；如果該節(jié)點是NLOS節(jié)點，則將該測距值進行卡爾曼濾波處理，然后將通過多項式預(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所示。首先利用多項式擬合鑒別測量值中的非視距誤差并且預(yù)測距離，通過擬合曲線和測量值之間的偏差來識別非視距誤差，檢測閾值可以根據(jù)測量值自適應(yīng)的調(diào)整。然后利用卡爾曼濾波器處理測量值，在非視距傳播下，對測量值進行加權(quán)重構(gòu)。按照圖3所示的流程進行仿真實驗。

圖3 整體算法流程圖

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

表1 參數(shù)表

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

圖4 移動節(jié)點的真實軌跡及信標(biāo)節(jié)點

3.1 仿真結(jié)果

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

圖5 NLOS誤差識別率

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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

[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é)報, 2010, 32(11): 2612-2617.

[4] 田孝華, 廖桂生. 一種有效減小非視距傳播影響的TOA定位方法[J]. 電子學(xué)報, 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é)報, 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)健的孤立點檢測—從中位數(shù)求方差[C]//中國計算機學(xué)會理論計算機科學(xué)專業(yè)委員會, 長春: 2006年全國理論計算機科學(xué)學(xué)術(shù)年會, 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

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

2020-07-14；

2020-09-16

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