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

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

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

一、前言

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

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

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

二、總體技術(shù)框架

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

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

三、行人航位推算（PDR）

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

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

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

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

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

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

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

四、地圖匹配

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

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

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

（1）觀測概率矩陣：

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

（2）狀態(tài)轉(zhuǎn)移矩陣：

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

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

五、WIFI指紋匹配

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

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

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

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

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

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

六、卡爾曼濾波

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

七、結(jié)語

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

參考文獻

[1] 汪少初.基于PDR 的定位與跟蹤技術(shù)研究及系統(tǒng)設計[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] 張勝軍，林若琳.淺談室內(nèi)定位技術(shù)現(xiàn)狀[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] 張瑞峰，張忠娟，呂辰剛.基于質(zhì)心-Taylor 的 UWB 室內(nèi)定位算法研究[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] 陳國通，王小娜，張曉旭，等.基于慣性導航的室內(nèi)定位誤差修正算法[J].河北工業(yè)科技，2018， 35（3）： 185-190.

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

[17]王銳.基于行人航位推算（PDR）技術(shù)的室內(nèi)導航系統(tǒng)[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、磁場特征的移動智能終端室內(nèi)行人導航算法[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] 劉慶， 關(guān)維國， 李順康， 等. 基于擴展 Kalman 濾波的室內(nèi)WiFi-PDR 融合定位算法[J].計算機工程，2019，45（4） ： 66-71．

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

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