基于WiFi/PDR的室內(nèi)行人組合定位算法

李 楠，陳家斌，袁 燕

（1. 北京理工大學(xué) 自動化學(xué)院，北京 100081；2. 北京理工大學(xué) 計算機學(xué)院，北京 100081）

基于WiFi/PDR的室內(nèi)行人組合定位算法

李 楠1，陳家斌1，袁 燕2

（1. 北京理工大學(xué) 自動化學(xué)院，北京 100081；2. 北京理工大學(xué) 計算機學(xué)院，北京 100081）

對當(dāng)前室內(nèi)行人定位算法進行了研究。針對 WiFi定位穩(wěn)定性差的問題，提出了一種改進的 K最近鄰（Improved K-Nearest Neighbor，IKNN）算法。針對行人航位推算（Pedestrian Dead Reckoning，PDR）算法中步長模型及航向估計不準確的問題，提出了一種實時更新的步長模型及基于室內(nèi)環(huán)境特征的航向估計算法。在改進的WiFi定位算法與PDR算法的基礎(chǔ)上，提出了一種基于自適應(yīng)粒子濾波的室內(nèi)行人WiFi與PDR組合定位算法，通過自適應(yīng)因子自動調(diào)節(jié)觀測量對粒子分布的影響。通過智能手機在實際室內(nèi)環(huán)境中對定位方法進行了測試，實驗結(jié)果表明：組合定位系統(tǒng)定位精度為0.66 m，高于普通的粒子濾波算法，是一種準確高效的室內(nèi)行人定位算法。

室內(nèi)定位；WiFi；K最近鄰；行人航位推算；自適應(yīng)粒子濾波

近年來，隨著移動通信設(shè)備和普適計算的快速發(fā)展，基于室內(nèi)位置信息的服務(wù)（Location Based Service，LBS）越來越受到人們關(guān)注[1]。在無遮擋的室外環(huán)境中，GNSS（GPS、北斗、GLONASS等）導(dǎo)航系統(tǒng)可以實現(xiàn)高精度導(dǎo)航定位，但由于室內(nèi)環(huán)境的遮擋，GNSS系統(tǒng)在室內(nèi)無法得到有效的定位信息[2]。因此，如何在室內(nèi)環(huán)境中精確、可靠地提供位置信息成為學(xué)者們的研究熱點[3]。目前，常見的室內(nèi)定位技術(shù)主要有基于無線網(wǎng)絡(luò)的室內(nèi)定位，基于INS的行人航跡推算，基于射頻信號的定位以及基于地磁匹配的定位技術(shù)等。

WiFi定位通過對在目標(biāo)點采集到的信號強度與事先采集到的指紋庫數(shù)據(jù)做比對，得到目標(biāo)點的位置信息。但是，由于室內(nèi)環(huán)境的復(fù)雜性及各種干擾，WiFi指紋定位精度不高，且定位跳變較大，無法滿足人們的定位需求。目前，基于微機電系統(tǒng)（Micro Electro Mechanical System，MEMS）的微型慣性傳感器已經(jīng)成為各種智能手機的標(biāo)配，這為基于智能手機的行人航位推算（PDR）提供了可能[4]。PDR通過實時測量行人的運動信息來識別行人的步數(shù)、步長和行進方向。PDR能夠在不依賴外部信息的條件下連續(xù)自主定位，短期內(nèi)噪聲小，穩(wěn)定性好。但是，傳統(tǒng)的PDR方法受到傳感器本身特性和室內(nèi)環(huán)境的影響，很難得到精確的步長、航向信息，且存在嚴重的誤差累計問題[5]。

單一的定位方法由于其本身定位原理的制約，無法同時滿足高精度、實時性、低成本的定位需求。把WiFi定位與基于MEMS的PDR定位技術(shù)相結(jié)合，既能消除WiFi定位誤差大、不能提供連續(xù)位置信息的缺陷，又能自適應(yīng)地確定PDR算法中的步長、航向信息，避免了誤差累積現(xiàn)象。文獻[6]利用擴展卡爾曼濾波融合了PDR與WiFi的定位信息，并用零速修正算法提高了 PDR的定位精度；文獻[7]采用最大似然算法根據(jù)前幾步的位置信息確定定位的初始位置，并采用卡爾曼濾波與網(wǎng)格濾波估計位置；文獻[8]先利用AP聚類提高WiFi定位速度與精度，再使用自適應(yīng)的擴展卡爾曼濾波算法估計位置，取得了較好的定位效果。

本文提出了一種基于自適應(yīng)粒子濾波的WiFi/PDR組合定位算法，利用PDR信息改進了WiFi定位算法，有效地提高了WiFi的定位精度，改進了行人步長的估計方法，根據(jù)組合定位結(jié)果反饋調(diào)節(jié)行人行走步長參數(shù)。為了減少室內(nèi)環(huán)境對磁傳感器航向估計結(jié)果的影響，利用電子地圖的約束對航向估計進行了修正。最后，提出使用自適應(yīng)的粒子濾波器將WiFi與PDR兩種方法的定位信息進行融合。

1 改進的室內(nèi)WiFi定位算法

基于 WiFi的室內(nèi)定位指紋算法一般分為離線勘測和在線定位兩個階段。K最近鄰法（KNN）是最常用的指紋匹配算法，它是一種簡單的機器學(xué)習(xí)算法，其基本思想是：在特征空間中，選取與目標(biāo)距離最近的k個鄰居樣本，將它們的平均值作為目標(biāo)的估計位置。

下面介紹基于行人運動約束的改進的KNN（Improved K-Nearest Neighbor，IKNN）：

由于室內(nèi)復(fù)雜環(huán)境對無線信號的干擾，WiFi信號在采集的過程中會有一定程度的波動，使得同一位置連續(xù)兩次定位結(jié)果相差較大的情況。

為了減小傳統(tǒng)KNN算法帶來的定位誤差與跳變，IKNN使用了PDR定位算法的運動信息對KNN算法進行加權(quán)，減少了因信號波動帶來的位置跳變。具體的定位流程如下：

1）離線階段采集RSS指紋庫，采集過程與傳統(tǒng)的KNN相同；

3）計算每一條指紋的方向加權(quán)系數(shù)：

4）根據(jù)兩相鄰時刻行人運動距離約束確定距離加權(quán)系數(shù)：

2 改進的PDR定位方法

基于MEMS的行人航位推算PDR定位方法是基于行人步態(tài)的運動生理學(xué)特征，利用加速度計測量行走時的步數(shù)和估計步長，聯(lián)合從陀螺儀和磁傳感器獲得的航向信息，利用式(7)推算出行人的當(dāng)前位置。所以，PDR定位算法的定位精度主要取決于步頻的探測準確度、步長和航向信息的估算精度。

2.1 行人步數(shù)檢測算法

目前，基于MEMS的步態(tài)檢測主要是利用人體行走時加速度的周期性變化，采用峰值探測法來尋找固定時間窗口加速度的極值。本文通過對行人行走過程中加速度計輸出值的大量研究、分析，采用了一種基于波峰-波谷的步數(shù)檢測算法，其具體實現(xiàn)如下。

在進行行人步態(tài)檢測時，需要使用行人行走過程中三個方向上的總加速度Acc，

由于手機內(nèi)置的 MEMS在測量過程中存在較大的量測噪聲，因此在使用加速度測量值測量行人步數(shù)時，必須要進行信號預(yù)處理，減小噪聲對測量結(jié)果的影響。本文首先將加速度值通過一個FIR濾波器，得到信號。

由于行人行走每一步加速度值均經(jīng)過先上升，再下降的過程，即每一步的加速度信號波形都應(yīng)包括一個完整的波峰、波谷，因此在得到信號后，本文通過下述規(guī)則判斷行人行走步數(shù)：

2）判斷相鄰波峰的間隔時間，如果間隔時間小于0.3 s，則只保留其中絕對值較大的波峰；

3）判斷相鄰波谷的間隔時間，如果間隔時間小于0.3 s，則只保留其中絕對值較大的波谷；

4）判斷每一個波峰前是否有唯一的波谷，如果有，則行人步數(shù)+1。

如圖1所示，圖中黑色實線為行人步行20步時，通過兩次濾波后的信號波形，圓圈為根據(jù)上述規(guī)則判斷檢測到的行人行走步數(shù)。

圖1 加速度信號Fig.1 The acceleration signal

2.2 自適應(yīng)行人步長估計算法

行人航跡推算的定位精度與步長的估計精度有很大的聯(lián)系，因此，為了提高PDR的定位精度，需要一個較精確的步長估計算法。本文采用了非線性步長模型對步長進行估算，并針對該模型進行了改進，以適應(yīng)不同行人個體的步長差異。其公式如下：

2）經(jīng)過4次組合定位后，利用這4次的組合定位結(jié)果，用最小二乘法對兩個參數(shù)進行擬合；

2.3 室內(nèi)行人航向算法

基于智能手機的 PDR定位算法的定位精度與其對行人航向的估計精度有著很大的關(guān)系。尤其對于低成本的MEMS傳感器，由于陀螺的漂移和室內(nèi)環(huán)境對磁場的干擾，很難精確地估計出行人行走的方向。

根據(jù)文獻[9][10]所述，大多數(shù)建筑內(nèi)的走廊都與建筑本身的朝向平行、垂直或以一定角度相交，本文根據(jù)這一特性提出了一種行人室內(nèi)航向修正方法。這一方法依賴于一個較強的假設(shè)，即大多數(shù)時間里，行人在這些建筑內(nèi)行走時均沿建筑物方向進行直線行走，那么可以通過檢測行人是否進行直線行走（未發(fā)生轉(zhuǎn)向）來對估計的行人航向進行修正。根據(jù)這一假設(shè)，在PDR算法中，我們將行人航向估計作如下規(guī)定：

時，則判斷行人沿直線行走，行走方向未發(fā)生變化。

2）如果行人連續(xù)3個時刻行走方向未發(fā)生變化，且其航向均值與建筑物內(nèi)墻壁方向之差小于閾值則認為行人航向與建筑物方向保持一致。

3 基于自適應(yīng)粒子濾波的組合定位算法

本文利用自適應(yīng)粒子濾波算法對室內(nèi)行人進行定位，利用PDR中得到的步長、航向來約束行人位置隨時間的變化，再利用WiFi定位結(jié)果作為觀測量對行人位置進行修正。由于 WiFi定位結(jié)果存在較大的波動性，本文提出使用IKNN算法中k個匹配點坐標(biāo)距離的均方差作為反映WiFi定位波動性的參數(shù)，自適應(yīng)地對粒子權(quán)重進行調(diào)整，以減小WiFi定位波動對濾波結(jié)果的影響。該算法可直接運行在智能手機上，無需額外的硬件設(shè)備，提高了系統(tǒng)的可用性。

具體算法流程如下：

1）初始化

確定行人的初始位置，由WiFi定位給出，設(shè)為(x0,y0)。然后根據(jù)正態(tài)分布初始化一個包含行人位置信息和粒子權(quán)重的粒子集：

2）粒子傳播

利用改進的PDR算法輸出的步長、航向信息對粒子位置進行更新：

3）權(quán)值更新

各個粒子進行傳播后根據(jù)觀測量來判斷粒子的傳播是否合理，將粒子所代表的位置與行人的真實位置相似程度大的粒子賦予較大的權(quán)值，反之相似程度小的粒子賦予較小的權(quán)值，用粒子權(quán)值來代表粒子位置與真實位置之間的相似程度。

4）自適應(yīng)權(quán)值改進

在行人定位系統(tǒng)中，本文將WiFi定位結(jié)果作為對當(dāng)前環(huán)境的觀測量。由于WiFi定位受到室內(nèi)復(fù)雜環(huán)境的影響，在某些位置可能出現(xiàn)較大的波動，即存在較大的定位誤差。因此，本文將WiFi定位中k個匹配點的位置均方差作為參數(shù)，帶入粒子濾波權(quán)值更新中，自適應(yīng)地對粒子權(quán)重進行調(diào)整，以減小WiFi定位波動對濾波結(jié)果的影響。

更新粒子權(quán)值為

歸一化權(quán)值：

5）重采樣

隨著濾波時間的增加，粒子會出現(xiàn)退化現(xiàn)象，需要對其進行重采樣。通過對粒子以及它們的權(quán)值所對應(yīng)的概率密度函數(shù)重采樣，來提高權(quán)值較大的粒子的比值。本文采用隨機重采樣的方式對粒子進行重采樣。

6）系統(tǒng)狀態(tài)估計與時間更新

根據(jù)粒子的位置信息和權(quán)值，當(dāng)前時刻行人位置的估計值為

進行下一時刻的計算，t=t+1，重復(fù)步驟 2）至步驟 6）。

4 實驗與結(jié)果分析

為驗證本文提出的上述算法，選取了北京理工大學(xué)自動化學(xué)院教學(xué)樓一處20m×50m的區(qū)域作為實驗場地（見圖2），使用了基于Android平臺的三星9006手機作為實驗設(shè)備。

圖2 實驗場地示意圖Fig.2 Test environment

本次實驗將基于WiFi的IKNN算法、改進的PDR算法以及自適應(yīng)粒子濾波組合定位算法進行了比較，結(jié)果如圖3所示。從圖3可以看出：基于WiFi的定位算法定位波動較大，定位結(jié)果在個別點上嚴重偏離了真實位置；基于PDR的定位算法與真實路徑的重合度比WiFi定位高，但在定位過程中無法消除由初始位置引起的定位誤差和累積誤差；基于自適應(yīng)粒子濾波的組合定位總體上與真實軌跡重合度較高，即使在WiFi定位誤差較大的位置也能保持較高的定位精度，且能夠根據(jù)WiFi定位結(jié)果對PDR的誤差進行修正。

圖3 IKNN、改進的PDR算法、自適應(yīng)粒子濾波算法行走軌跡對比Fig.3 Comparison on walking trajectories by IKNN,improved PDR, and self-adaptive particle filter algorithms

從圖4和表1中可以看出：基于PDR的方法誤差均方差較小，但由于誤差不斷累積，導(dǎo)致定位誤差較大；WiFi定位能夠提供絕對位置信息，但定位結(jié)果有明顯的波動；當(dāng)使用自適應(yīng)粒子濾波進行組合定位時，誤差和誤差均方差僅為0.66 m和0.18 m，該方法有效地提高了定位精度與穩(wěn)定性。差為 1 m，即本文提出的自適應(yīng)粒子濾波算法能夠有效抑制組合定位的最大定位誤差，提高定位精度。

圖4 IKNN、改進的PDR算法、自適應(yīng)粒子濾波算法累積誤差對比Fig.4 Cumulative errors of IKNN, improved PDR, and self-adaptive particle filter algorithms

表1 幾種定位方法誤差與均方差Tab.1 Location errors and mean square errors of different solutions

圖5和圖6比較了普通粒子濾波算法和本文提出的自適應(yīng)粒子濾波在組合定位時的定位誤差。基于自適應(yīng)粒子濾波的方法能夠根據(jù) WiFi定位的波動性大小，對粒子權(quán)值進行調(diào)整，從而達到提高組合定位精度的目的。從圖5～6中可以看出，普通粒子濾波的最大定位誤差為1.18 m，自適應(yīng)粒子濾波的最大定位誤

圖5 粒子濾波與自適應(yīng)粒子濾波算法定位誤差對比Fig.5 Location errors of particle filter and self-adaptive particle filter algorithms

圖6 粒子濾波與自適應(yīng)粒子濾波算法定位累積誤差對比Fig.6 Cumulative location errors of particle filter and self-adaptive particle filter algorithms

5 結(jié) 論

本文對室內(nèi)行人定位技術(shù)進行了研究，提出了一種基于IKNN的WiFi定位算法與改進的PDR算法，并通過自適應(yīng)粒子濾波將二者進行融合，以得到更加精確、穩(wěn)定的定位結(jié)果。實驗結(jié)果表明：IKNN算法通過加入行人運動約束，有效地提高了指紋匹配的匹配精度，減小了室內(nèi)復(fù)雜環(huán)境對定位的影響；改進的PDR算法通過對步長模型的自適應(yīng)調(diào)整以及加入了建筑朝向?qū)较虻募s束，使步長和航向估計更加準確。本文提出了一種基于自適應(yīng)粒子濾波的組合定位方法，根據(jù)自適應(yīng)因子動態(tài)調(diào)節(jié)WiFi定位觀測量對粒子運動分布的影響，使組合定位結(jié)果更加準確、穩(wěn)定。

本文提出的組合定位算法可以利用一般的智能手機實現(xiàn)，無需額外的硬件設(shè)備，算法運行速度快，實現(xiàn)簡單，可以作為室內(nèi)環(huán)境下行人定位使用。

（References）：

[1]Akyildiz I F, Su W L, Sankarasubramaniam Y, et al. A survey on sensor networks[J]. IEEE Communications Magazine, 2002, 40(8): 102-114.

[2]Yan Jun-lin, Tiberius C C J M, Janssen G J M, et al.Review of range-based positioning algorithms[J]. IEEE Aerospace & Electronic Systems Magazine, 2013, 28(8): 2-27.

[3]劉春燕. 基于多源信息融合的行人航位推算室內(nèi)定位方法[J]. 中國慣性技術(shù)學(xué)報, 2016, 24(2): 208-214.Liu Chun-yan. Indoor localization method based on pedestrian dead reckoning aided by multi-source fusion[J]. Journal of Chinese Inertial Technology, 2016, 24(2): 208-214.

[4]Li Nan, Chen Jia-bin, Yuan Yan, et al. A fast indoor tracking algorithm based on particle filter and improved fingerprinting[C]//IEEE 2016 35thChinese Control Conference. 2016: 5468-5472.

[5]Shih W Y, Chen L Y, Lan K C. Estimating walking distance with a smart phone[C]//Fifth International Symposium on Parallel Architectures, Algorithms and Programming. IEEE Computer Society, 2012: 166-171.

[6]Zhuang Yuan, Lan Hai-yu, Li You, et al. PDR/INS/WiFi Integration based on handheld devices for indoor pedestrian navigation[J]. Micromachines, 2015, 6(6): 793-812.

[7]Du Yuan-feng, Yang Dong-kai, Yang Hui-lin, et al. Flexible indoor localization and tracking system based on mobile phone[J]. Journal of Network & Computer Applications,2016, 69(C): 107-116.

[8]Li Xin, Wang Jian, Liu Chun-yan, et al. Integrated WiFi/PDR/smartphone using an adaptive system noise extended Kalman filter algorithm for indoor localization[J].ISPRS International Journal of Geo-Information, 2016,5(2): 8.

[9]Abdulrahim K, Hide C, Moore T, et al. Integrating low cost IMU with building heading in indoor pedestrian navigation[J]. Journal of Global Positioning Systems,2011, 10(1): 30-38.

[10]Abdulrahim K, Hide C, Moore T, et al. Aiding MEMS IMU with building heading for indoor pedestrian navigation[C]//Ubiquitous Positioning Indoor Navigation and Location Based Service. IEEE, 2010: 1-6.

Indoor pedestrian integrated localization strategy based on WiFi/PDR

LI Nan1, CHEN Jia-bin1, YUAN Yan2
(1. School of Automation, Beijing Institute of Technology, Beijing 100081, China;2. School of Computer Science and Technology, Beijing Institute of Technology, Beijing 100081, China)

In view that WiFi localization has poor instability in indoor pedestrian localization, an improved K-nearest neighbor algorithm is proposed to overcome this problem. A real-time updated step-length model and a heading estimation algorithm based on indoor environmental features are proposed to improve the positioning accuracy of pedestrian dead reckoning. In addition, a self-adaptive particle filtering algorithm is used to integrate the WiFi with the pedestrian dead reckoning. An adaptive factor is used to automatically adjust the influence of WiFi observations on particle movements. A series of experiments were implemented on mobile phone, and the results show that the proposed integration localization strategy achieves 0.66 m location accuracy which is better than that of the traditional particle filtering algorithm.

indoor location; WiFi; K-nearest neighbor; pedestrian dead reckoning; self-adaptive particle filter

1005-6734(2017)04-0483-05

10.13695/j.cnki.12-1222/o3.2017.04.011

U666.1

A

2017-04-19；

2017-08-17

國防預(yù)研基金項目資助（9140A09050313BQ01127）；國家自然科學(xué)基金項目資助（91120010）

李楠（1990—），男，博士研究生，從事慣性導(dǎo)航、室內(nèi)定位技術(shù)研究。E-mail: linan_beijing@126.com

聯(lián) 系 人：袁燕（1989—），女，助理實驗師，從事計算機實驗教學(xué)、深度學(xué)習(xí)技術(shù)研究。E-mail: yuanyanbeijing@126.com