李 楠，陳家斌，袁 燕

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

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

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

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

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

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

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

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

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

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

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

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

下面介紹基于行人運(yùn)動(dòng)約束的改進(jìn)的KNN（Improved K-Nearest Neighbor，IKNN）：

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

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

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

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

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

2 改進(jìn)的PDR定位方法

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

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

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

在進(jìn)行行人步態(tài)檢測(cè)時(shí)，需要使用行人行走過(guò)程中三個(gè)方向上的總加速度Acc，

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

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

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

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

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

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

圖1 加速度信號(hào)Fig.1 The acceleration signal

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

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

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

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

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

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

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

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

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

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

具體算法流程如下：

1）初始化

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

2）粒子傳播

利用改進(jìn)的PDR算法輸出的步長(zhǎng)、航向信息對(duì)粒子位置進(jìn)行更新：

3）權(quán)值更新

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

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

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

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

歸一化權(quán)值：

5）重采樣

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

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

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

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

4 實(shí)驗(yàn)與結(jié)果分析

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

圖2 實(shí)驗(yàn)場(chǎng)地示意圖Fig.2 Test environment

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

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

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

圖4 IKNN、改進(jìn)的PDR算法、自適應(yīng)粒子濾波算法累積誤差對(duì)比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)粒子濾波在組合定位時(shí)的定位誤差?；谧赃m應(yīng)粒子濾波的方法能夠根據(jù) WiFi定位的波動(dòng)性大小，對(duì)粒子權(quán)值進(jìn)行調(diào)整，從而達(dá)到提高組合定位精度的目的。從圖5～6中可以看出，普通粒子濾波的最大定位誤差為1.18 m，自適應(yīng)粒子濾波的最大定位誤

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

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

5 結(jié) 論

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

本文提出的組合定位算法可以利用一般的智能手機(jī)實(shí)現(xiàn)，無(wú)需額外的硬件設(shè)備，算法運(yùn)行速度快，實(shí)現(xiàn)簡(jiǎ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]. 中國(guó)慣性技術(shù)學(xué)報(bào), 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

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

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

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