一種基于行人航位推算、地圖匹配和WIFI指紋的室內融合定位算法

摘要：室內位置信息在人們日常生活和工作中發揮著十分重要的作用。與室外環境相比，室內環境一般為封閉或半封閉空間，存在著信號變弱、障礙物多、干擾源多等特點。為了解決室內復雜環境下的定位問題，提出了一種基于行人航位推算（PDR）、地圖匹配和WIFI指紋的室內定位算法。該算法首先利用WIFI指紋進行行人位置的初始化定位，然后通過航位推算算法推算行人行走軌跡，并利用地圖匹配算法對行人航位推算誤差進行實時修正，最后使用卡爾曼濾波算法對行人軌跡進行進一步的修正。初步研究表明，該算法具有較好的實用價值，可在博物館、超市、機場等場所為消費者提供精確的導航與定位。

關鍵詞：行人航位推算；地圖匹配；WIFI指紋；卡爾曼濾波

一、前言

室內位置信息在人們日常生活和工作中發揮著十分重要的作用，據統計，人每天在室內環境中活動時間占每天活動時間的80%。隨著社會、經濟和科技的飛速發展及生活水平的提高，人們對室內環境中實時定位與導航技術的需求越來越大[1-5]。高精度、低成本、快速及時的室內定位技術可以在商場、博物館、機場、高鐵站等場所為行人和消費者提供快速的購物引導和路線規劃，在礦井、火災現場等場所為工人、救援人員提供精確的位置導航與人員定位，從而加速改變零售、安防、救援、制造等傳統領域的物品生產、數據流通和商務運作方式，并真正實現人工智能、萬物互聯和智慧城市。在龐大的市場需求驅動下，室內定位技術逐漸成為學術界的研究熱點和工業界的投資熱點，具有高精度、低成本、高可用性的室內融合定位技術對人們未來的生活起著舉足輕重的作用，將擁有廣闊的發展空間。

在全球衛星導航系統（Global Navigation Satellite System，GNSS）的衛星廣域增強服務支撐下，目前室外定位已經形成了較為成熟的技術應用和商業化服務，可實現室外寬闊區域優于1米的定位精度[6-7]。然而，雖然衛星定位技術較為成熟，實時性、精度都很高，但是衛星定位信號在穿透建筑物時會出現信號衰減的現象，因而GNSS在室內定位的定位效果并不理想。考慮到室內環境通常是建筑物內部的封閉或半封閉空間，相比戶外要復雜的多，在室內環境進行定位主要存在信號變弱、障礙物多、干擾源多、多層建筑、未知環境等特點。考慮到復雜的室內環境、應用和需求，可用于室內定位導航服務解決方案的技術主要有WIFI、紅外、計算機視覺、磁場、藍牙、5G等[8-13]，但上述技術路線均不同程度存在著成本高、實時性差、精度低、可靠性低等問題。高精度、低成本、高實時、廣域覆蓋的室內定位技術仍然是實現室內外定位無縫服務的最大阻礙之一。

為了解決復雜室內環境下的定位導航問題，本文介紹了一種基于行人航位推算（PDR）、地圖匹配和WIFI指紋的室內融合定位新算法。該算法首先利用WIFI指紋進行行人位置的初始化定位。然后，利用行人航位推算來估算行人的實時行走軌跡，并利用地圖匹配算法將行人行走軌跡與室內地圖相匹配以降低PDR算法的累積計算偏差。最后，使用卡爾曼濾波器將修正后的PDR計算結果與WIFI指紋定位結果相融合，以獲得更準確的行人室內定位計算結果。本技術具有較好的實用價值，可為行人和消費者提供精確的室內導航與定位結果。

二、總體技術框架

本節介紹基于行人航位推算、地圖匹配和WIFI指紋的室內融合定位算法的總體技術框架。該算法主要使用PDR算法估計行人的行走軌跡，使用的傳感器信息包括慣性測量信息（加速度計和陀螺儀）、磁場強度信息和氣壓信息，并利用了室內路徑地圖信息來實時修正行人的位置和方向。室內融合定位算法的總體技術框架如圖1所示。

同時，該算法也采用了WIFI RSSI信息構建WIFI指紋數據庫，用于提供行人初始位置和WIFI指紋定位結果，通過卡爾曼濾波器融合以后可以顯著提高本算法的精度和穩定性。

三、行人航位推算（PDR）

行人航位推算（PDR）技術是一種慣性導航技術，其優點是可以在不需要預先在建筑物內設置信標的條件下，利用慣性傳感器（加速度計、陀螺儀、磁力計等）數據來計算行人的步長和方向[14-16]，繼而推算行人的實時位置和行動軌跡。PDR算法中使用的初始位置由WIFI指紋匹配結果給出，并利用氣壓計獲取行人所處的高度和樓層信息。

PDR算法的計算步驟包含步長檢測、步長和方向估計，其基本原理如圖3所示。

PDR算法的計算過程如下所示：

1）利用WIFI RSSI指紋計算行人初始位置，利用氣壓計算行人的初始高度和樓層。

2）利用加速度計和陀螺儀得到行人方位角和步長后（計算方法見參考文獻[14][15]），計算下一時刻的行人位置，計算公式如下：

其中，和分別表示第i步的方位角和步長。

3）重復上述步驟計算行人的行走軌跡。

四、地圖匹配

考慮到PDR算法是慣性導航算法，其計算結果往往包含累積誤差。在這種情況下，在得到行人位置后，需要使用地圖匹配算法將當前行人位置與室內地圖進行匹配，將行人的軌跡引導到室內路網上[17-18]。

本文利用ST-matching算法作為地圖匹配算法來校正行人的實時位置。ST-matching算法綜合利用了行人運動軌跡的時間速度約束和室內幾何地圖空間特征，從而借助室內路網將行人位置信息映射到室內地圖上。

ST-matching算法使用觀測概率矩陣和狀態轉移矩陣來判斷行人位置觀察點和室內路徑真實點之間的偏差。其計算原理如下：

（1）觀測概率矩陣：

行人位置觀測點與其室內路徑候選點之間的測量誤差可以描述為均值為0和標準差為2米的高斯分布。該測量誤差可以通過計算公式計算，它表示行人位置觀測點是否可以匹配到真實道路的候選點。行人位置觀測點與室內路徑候選點的距離越小，候選點越有可能是真實的實際點。

（2）狀態轉移矩陣：

其中，是考慮到室內路網幾何拓撲結構的空間分析函數。該函數利用觀測點及其候選點的速度信息來推斷路徑（到）是最短路徑（到 ）的可能性，避免行人走彎路或錯路。是路徑點和之間的歐幾里得距離，是候選路徑節點和之間最短長度。

是一個時間分析函數，它考慮了兩個相鄰點之間的速度信息，用于判斷到的平均速度與該路段行人平均速度的相似度。其中，到的最短路徑被定義為段列表，每個段與其有限的最大速度相關聯。是這些最短路徑段的平均速度。

五、WIFI指紋匹配

本算法使用WIFI接收信號強度（Received Signal Strength Indicator，RSSI）來構建WIFI指紋，并使用余弦相似度算法提供行人的初始和實時位置[19-21]。

本文采用對數法線陰影模型測量WIFI RSSI信號參數，建立WIFI指紋數據庫。對數法線陰影模型的數學表達式如下：

其中，是參考距離處的RSS值，N=1.6是路徑損耗系數。

在利用對數法線陰影模型建立WIFI指紋數據庫后，可以使用三邊測量方法計算行人位置。計算方程如下：

是行人所處位置最強信號的WIFI基站坐標，是行人的坐標，是WIFI基站到行人的距離，是除最強信號基站外其它WIFI基站的坐標。

使用最小二乘法得到方程（7）的解算結果：

六、卡爾曼濾波

本算法設計了卡爾曼濾波器[22-23]，將經過地圖匹配后的PDR計算結果和WIFI指紋匹配結果相結合，從而提供更為準確的室內融合定位結果。

七、結語

本文設計了一種基于行人航位推算（PDR）、地圖匹配和WIFI指紋的室內融合定位新算法。該算法利用PDR算法實時估計行人的行走軌跡，使用的傳感器包括加速度計陀螺儀、磁力計和氣壓計，同時利用了室內地圖信息來實時修正行人的位置和方向。算法還使用了卡爾曼濾波器將PDR計算結果與WIFI指紋匹配結果進行融合，從而提供更為準確的室內定位結果。初步研究表明，該方法的計算結果較為準確，可為行人和消費者提供博物館、超市、機場等場所的精確室內導航與定位能力。

參考文獻

[1] 汪少初.基于PDR 的定位與跟蹤技術研究及系統設計[D].天津：天津大學，2014.

[2] Basiri A， Lohan E S， Moore T， et al. Indoor location based services challenges， requirements and usability of current solutions[J]. Computer Science Review， 2017.

[3] 張勝軍，林若琳.淺談室內定位技術現狀[J].測繪與空間地理信息，2018，41（7）：128-131.

[4] Harle R. A Survey of Indoor Inertial Positioning Systems for Pedestrians[J]. IEEE Communications Surveys amp; Tutorials， 2013， 15（3）：1281-1293.

[5] Sch?fer， Martin， Knapp， et al. Automatic Generation of Topological Indoor Maps for Real-Time Map-Based Localization and Tracking[C] International Conference on Indoor Positioning amp; Indoor Navigation. IEEE， 2011.

[6] United Nations. Current and planed global and regional navigation satellite system and satellite-based augmentation systems[EB/OL]. [2019-05-26]. http：//www. unoosa. org/pdf/publications/icg_ebook. pdf.

[7] Department of Defense and GPS NAVSTAR. Global positioning system standard positioning service performance standard[EB/OL]. [2019-05-26]. https：//www. gps. gov/technical/ps/2008-SPS-performance-standard. pdf.

[8] 張瑞峰，張忠娟，呂辰剛.基于質心-Taylor 的 UWB 室內定位算法研究[J].重慶郵電大學學報（自然科學版），2011，23（6）： 717-721.

[9] MARTIN-GOROSTIZA E，GARCIA-GARRIDO M A， PIZARRO D，et al． An indoor positioning approach based on fusion of cameras and infrared sensors［J］.Sensorsm， 2019，19（11），DOI：10.3390 /s19112519．

[10] ZHANG K，SHEN C，ZHOU Q，et al． A combined GPS UWB and MARG locationing algorithm for indoor and outdoor mixed scenario［J］.Cluster Computing，2019，22 （4） ： 5965-5974．

[11] KALBANDHE A A，PATIL S C． Indoor positioning system using Bluetooth low energy［C］/ / Proceedings of the 2016 International Conference on Computing，Analytics and Security Trends，2016：451-455．

[12] HUO Y M，DONG X D，XU W，et al． Cellular and WiFi co-design for 5G user equipment［C］/ / Proceedings of the 2018 IEEE 5G World Forum （ 5GWF） ． 2018： 256-261．

[13] TIAN Z S，TANG X M，ZHOU M，et al． Fingerprint indoor positioning algorithm based on affinity propagation clustering［J］． EURASIP Journal on Wireless Communications and Networking，2013，2013 （ 1） ： Article No． 272， DOI： 10． 1186 /1687-1499-2013-272．

[14] Diez L E， Bahillo A， Bataineh S， et al. Enhancing improved heuristic drift elimination for step-and-heading based pedestrian dead-reckoning systems[C]， 2016 38th Annual International Conference of the IEEE Engineering in Medicine and Biology Society （EMBC）. IEEE， 2016.

[15] 陳國通，王小娜，張曉旭，等.基于慣性導航的室內定位誤差修正算法[J].河北工業科技，2018， 35（3）： 185-190.

[16] 賈浩男，賈瑞才，王博遠.基于慣性傳感器的行人室內定位算法研究[J].無線電工程，2018， 48（8）： 619-623.

[17]王銳.基于行人航位推算（PDR）技術的室內導航系統[D].南京：南京郵電大學，2019.

[18] Lou Y， Zhang C， Zheng Y， Wang W， Huang Y. Map-Matching for low-sampling-rate GPS trajectories. In： Proc. of the ACM-GIS. 2009. 352?361.

[19] 李由.基于 MEMS 慣性傳感器、WiFi、磁場特征的移動智能終端室內行人導航算法[D].武漢：武漢大學，2015.

[20] KIM N，JO U，YUN K，et al. A hybrid positioning scheme exploiting sensors and RSS of Wi - Fi signals [ J]. Wireless Personal Communications，2015，85（3）：1111-1121. [4] TALVITIE J，RENFORS M，LOHAN E S. Distance-based interpolation and extrapolation methods for RSS-based localization with indoor wireless signals [ J]. IEEE Transactions on Vehicular Technology，2015，64（4）：1340-1353.

[21] Ismail A H， Kitagawa H， Tasaki R， et al. WiFi RSS fingerprint database construction for mobile robot indoor positioning system[C]. IEEE International Conference on Systems. IEEE， 2017.

[22] 劉慶， 關維國， 李順康， 等. 基于擴展 Kalman 濾波的室內WiFi-PDR 融合定位算法[J].計算機工程，2019，45（4） ： 66-71．

[23] 陳國良， 張言哲， 汪云甲， 等.WiFi-PDR 室內組合 定位的無跡卡爾曼濾波算法[J].測繪學報，2015，44（12）：1314-1321.

（作者單位：國家信息中心）