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

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

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

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

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

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

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

0 引言

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

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

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

無線傳感器網絡基本定位方法主要包括：基于到達時間（TOA）的定位方法、基于到達時間差（TDOA）的定位方法、基于方位角（AOA）定位方法和混合定位方法。基于TOA的定位方法原理簡單，故該定位方法是目前基于網絡定位應用最廣泛的定位方法。

1.1 TOA測距模型

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

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

圖1 多項式擬合示意圖

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

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

2.1 NLOS識別算法原理

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

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

圖2 算法流程圖

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

其具體步驟如下：

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

2.2 NLOS抑制算法原理

通過NLOS識別算法判別是否是NLOS節點，如果該節點是LOS節點，則將該測距值進行卡爾曼濾波處理，得到濾波后的值為NLOS抑制算法的輸出值；如果該節點是NLOS節點，則將該測距值進行卡爾曼濾波處理，然后將通過多項式預測的測距值與卡爾曼濾波后的測距值加權，加權后的預測值即為NLOS抑制算法的輸出。

2.2.1 基于卡爾曼濾波的數據處理

卡爾曼濾波可以總結為：

2.2.2 加權重構測距值

2.3 最小二乘定位算法

3 仿真結果

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

圖3 整體算法流程圖

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

表1 參數表

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

圖4 移動節點的真實軌跡及信標節點

3.1 仿真結果

通過圖5可以看出，由于改進算法NLOS誤差的判決門檻的動態變化，可以發現提高了NLOS節點的識別率。

圖5 NLOS誤差識別率

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

按照表1的參數設置，固定其他參數，變化信標節點的個數，從而得到圖6。

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

圖6 RMSE（均方根誤差）隨信標節點變化

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

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

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

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

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

圖9 RMSE（均方根誤差）隨NLOS誤差標準差變化

4 結語

多項式擬合的NLOS識別算法基于最小二乘算法原理，容易受異常值影響，對后續預測值產生影響；NLOS節點的判決門檻固定，導致NLOS節點的識別率低。本文提出了一種能有效識別NLOS誤差的多項式擬合改進算法，利用部分歷史時刻的測距值進行多項式擬合來預測測量距離，有效地降低異常值對預測模型的影響；利用中值與方差的線性關系，自適應調整NLOS節點判決門檻，提高了NLOS誤差的識別率。仿真結果表明，在NLOS誤差嚴重的環境下，本算法性能較基于多項式擬合的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原理的交通信息獲取系統與車輛定位方法[J]. 電子與信息學報, 2010, 32(11): 2612-2617.

[4] 田孝華, 廖桂生. 一種有效減小非視距傳播影響的TOA定位方法[J]. 電子學報, 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系統中的測試[J]. 信息工程大學學報, 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] 蔡利棟, 傅瑜. 穩健的孤立點檢測—從中位數求方差[C]//中國計算機學會理論計算機科學專業委員會, 長春: 2006年全國理論計算機科學學術年會, 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

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

2020-07-14；

2020-09-16

載人航天創新性預研資助項目（17680601）