基于粒子濾波的WiFi行人航位推算融合室內定位

周瑞 李志強 羅磊

摘要：為提高室內定位的精度和穩定性，提出使用粒子濾波融合WiFi指紋定位和行人航位推算的室內定位算法。為減少復雜室內環境對WiFi指紋定位的影響，提出將支持向量機分類與回歸相結合的兩級WiFi指紋定位算法。在基于智能手持設備慣性傳感器的行人航位推算中，為減少慣性傳感器的誤差以及人隨意行走帶來的影響，采用狀態轉換的方法識別行走周期并進行步數統計，提出根據實時加速度數據動態設置狀態轉換的參數，利用步長和垂直加速度之間的關系以及相鄰步長之間的關系，應用卡爾曼濾波進行步長計算。仿真實驗中，基于支持向量機的WiFi指紋定位的平均誤差比最近鄰居（NN）算法降低34.4%，比K最近鄰居（KNN）算法降低27.7%。改進的行人航位推算的性能優于常用代表性計步軟件和步長計算算法，而經過粒子濾波融合后估計的行走軌跡更加接近真實軌跡：直線行走平均誤差為1.21m，優于WiFi的3.18m和航位推算的2.76m； 曲線行走平均誤差為2.75m，優于WiFi的3.77m和航位推算的2.87m。

關鍵詞：室內定位；多傳感器融合；粒子濾波；行人航位推算；WiFi指紋；支持向量機

中圖分類號：TP393.1 文獻標志碼：A

Abstract：In order to improve the accuracy and stability of indoor positioning， an indoor localization algorithm using particle filtering to fuse WiFi fingerprinting and Pedestrian Dead Reckoning （PDR） was proposed. To reduce the negative influence of complex indoor environment on WiFi fingerprinting， a Support Vector Machine （SVM）based WiFi fingerprinting algorithm using SVM classification and regression for more accurate location estimation was proposed. For smartphone based PDR， in order to reduce the error of inertial sensor， and the effects of random walk， the method of state transition was used to recognize the gait cycles and count the steps， the parameters of state transition were set dynamically using realtime acceleration data， the step length was calculated with Kalman filtering by making use of the relationship between vertical acceleration and step size， and the relationship between adjacent step sizes. The experimental results show that SVMbased WiFi fingerprinting outperformed Nearest Neighbor （NN） algorithm by 34.4% and KNearest Neighbors （KNN） algorithm by 27.7% in average error distance， the enhanced PDR performed better than typical step detection software and step length estimation algorithms. After particle filtering， the trajectory of the fused solution is closer to the real trajectory than WiFi fingerprinting and PDR. The average error distance of linear walking is 1.21m， better than 3.18m of WiFi and 2.76m of PDR； the average error distance of a walking through several rooms is 2.75m， better than 3.77m of WiFi and 2.87m of PDR.

Key words：indoor positioning； multisensor fusion； particle filtering； Pedestrian Dead Reckoning （PDR）； WiFi fingerprinting； Support Vector Machine （SVM）

0 引言

無線定位是工業、科研、醫療和日常生活中不可缺少的技術。由于不需要搭建專門的設施，僅依賴于已經廣泛部署的WiFi熱點，基于WiFi的定位獲得了較廣泛的應用。WiFi定位通常采用指紋定位算法，通過在目標點采集來自無線接入器（Access Point， AP）的信號強度（稱為信號指紋）來確定目標點的位置坐標。由于室內環境的復雜性，WiFi指紋定位精度不高且不穩定。Brunato等[1]提出將分類和回歸應用于室內定位，通過比較支持向量機（Support Vector Machine， SVM）、加權K最近鄰居（Weighted K Nearest Neighbors， WKNN）、K最近鄰居（K Nearest Neighbors， KNN）、貝葉斯（Bayesian， BAY）和多層感知器（MultiLayer Perceptron， MLP）算法說明了SVM應用于室內定位的優越性，但他們的實驗是在小范圍內進行的，參考點數量較少，SVM分類和回歸是分開進行的。

小型慣性傳感器已經成為各種智能手持設備的標配，為基于手持移動設備的行人航位推算（Pedestrian Dead Reckoning， PDR）提供了可能。PDR能夠在不依賴于外部信息的條件下連續自主定位，短期內噪聲小、穩定性好。目前大多數行人航位推算方法是把慣性傳感器固定在人的軀干[2]或者腳部[3]。這種方法的最大問題是不靈活?；谥悄苁殖衷O備的行人航位推算能夠提供這種靈活性，但是人行走的隨意性，以及智能手持設備內置傳感器的非精確性，會給航位推算帶來明顯誤差，且誤差隨時間累積。研究人員提出各種算法[4-6]來應對這些問題，但是目前仍然沒有一種精確的基于智能手持設備的行人航位推算算法。

每種定位方法在其精度、成本、適用性等方面各不相同，目前還沒有一種單一的定位技術能夠同時滿足定位準確、實時、適應性強和成本低的特點。多傳感器融合定位通過對各種獨立的傳感器信息進行融合，達到信息互補和協同工作的效果，提高整個系統的有效性。Chen等[7]采用極大似然（Maximum Likelihood， ML）融合算法將WiFi定位和PDR進行融合，確定初始位置和方向后，使用WiFi位置矯正PDR軌跡；Chen等[8]提出根據慣性傳感器數據和WiFi信號模式的變化確定室內重要標志，使用這些標志矯正WiFi和PDR的基于卡爾曼濾波的融合定位結果；Li等[9]采用序貫蒙特卡羅卡爾曼濾波（Sequential Monte Carlo Kalman Filtering， SMCKF）融合WiFi定位和PDR，方向估計采用粒子濾波，位置和速度估計采用卡爾曼濾波；Wang等[10]采用擴展卡爾曼濾波（Extended Kalman Filtering， EKF）融合WiFi定位和PDR，使用粒子濾波集成室內地圖以解決穿墻問題。

本文改進了WiFi定位算法，采用基于SVM的WiFi定位算法，提出將SVM分類與回歸分析相結合進行兩級精確定位；改進了PDR算法，根據實時加速度曲線對行走周期進行狀態劃分，使用狀態轉換來檢測行走周期，進行行走計數和步長計算。為了減少傳感器噪聲和人行走的隨意性對PDR的影響，提出對原始加速度數據進行預處理和根據實時加速度數據動態設置狀態轉換參數，并利用相鄰兩步步長差別不大的關系，將卡爾曼濾波（Kalman Filtering）應用在步長計算中提高步長計算的精度。在基于SVM的WiFi定位和改進的PDR的基礎上，使用粒子濾波（Particle Filtering）將兩種方法進行融合。實驗表明：基于SVM的WiFi定位算法能夠有效提高定位精度；改進的PDR算法能夠更加準確地統計出步數和步長；經過粒子濾波的融合后，定位系統的精度和穩定性得到明顯提高，估計的行走軌跡更加接近于真實軌跡。

1 定位子系統

1.1 基于SVM的WiFi指紋定位

WiFi定位是室內定位的常用方法，通常采用指紋定位算法[11]。由于WiFi信號穿越墻體后強度會明顯衰減，導致室內不同子區域（如不同房間）的信號指紋模式明顯不同。借助于支持向量分類（Support Vector Classification， SVC），通過對不同子區域的信號指紋進行采集和訓練，建立針對不同子區域的SVM分類器，就能夠確定信號指紋所屬的子區域。WiFi指紋定位根據信號指紋確定目標點的具體位置，可以認為目標點的位置是信號指紋的函數。借助支持向量回歸（Support Vector Regression， SVR），通過對采集的信號指紋進行訓練，可以獲得代表位置和信號強度之間非線性關系的統計模型，從而根據該統計模型和信號強度獲得目標點的位置。

本文提出將SVM分類和SVM回歸相結合進行兩級精確定位。在訓練階段，根據建筑內部結構將整個定位區域劃分成若干個子區域，在各個子區域內采集信號指紋并進行分類和回歸訓練。實際定位時，算法根據在目標點實時采集的信號指紋，通過SVM分類器確定目標點所在的子區域，然后在該子區域應用SVM回歸，確定目標點的位置坐標。假設在某個位置點采集的信號指紋樣本為（di，（x，y），ri），其中di為子區域，（x，y）為采樣點位置坐標，ri為信號指紋。對于SVM分類，在訓練階段需要樣本的子區域標識和信號指紋兩種信息，即（di，ri）。假設樣本集合為{（di，ri）|i=1，2，…，n}，對于某一個子區域，這些樣本可以分成兩類：第一類是在這個子區域采集的樣本，標志為1；第二類是不在這個子區域采集的樣本，標志為-1。針對每個子區域，建立一個SVM分類器，其用于分類的樣本可表示為{（ci，ri）|i=1，2，…，n}，ci∈{-1，1}。實際定位時，根據在目標點采集的信號指紋，使用SVM分類器確定該目標點是否屬于某個子區域。為確定目標點的位置坐標，需要在訓練階段對訓練樣本在該子區域進行回歸分析，獲得非線性函數fx（·）和fy（·），它們可以將目標點的信號指紋近似映射成該點的位置坐標x和y。

1.2 改進的PDR

對人體行走模型和加速度傳感器數據的分析可知，加速度曲線隨著人的行走以類似正弦波的規律延伸，曲線中每個正弦波對應一個行走周期，因此對步數的統計實際上就是從加速度曲線中識別行走周期并進行計數，并基于此進行步長計算。方向可以通過磁力計結合加速度傳感器獲得。手持移動設備內置的加速度傳感器精度不高，人在行走過程中存在不規律的身體晃動，這些使得加速度傳感器數據具有明顯的噪聲，導致行走周期識別的誤差。為降低加速度數據中的噪聲，本文采用簡單移動平均（Simple Moving Average， SMA）算法對加速度數據進行平滑。對于加速度曲線中行走周期的識別，可以將一個行走周期劃分成靜止狀態、波峰狀態和波谷狀態，使用狀態轉換的方法來識別行走周期。由于人在行走過程中存在速度變化，加速度曲線會出現上下偏移的情況，為降低行走周期識別的誤差，本文提出根據加速度曲線的實時變化動態設定狀態轉換的參數，包括狀態閾值、狀態分界參考值和零參考值。狀態閾值用來進行靜止狀態、波峰狀態和波谷狀態的判斷。狀態分界參考值是表示各個狀態開始和結束的數據點，某個狀態只要突破其分界參考值即可認為這個狀態結束和下一個狀態開始。由于人行走過程中速度的變化會導致加速度曲線的上下偏移，使用零或其他固定值作為零參考值，識別出的行走周期的起始和結束時間誤差很大。動態設置零參考值可以降低加速度曲線上下偏移帶來的誤差，保證計算出的行走周期的精確性。識別出完整的行走周期后，采用卡爾曼濾波結合步長和垂直加速度的關系以及相鄰兩步步長之間的關系對步長進行估計。本文采用Scarlett[2]提出的步長計算算法作為基礎算法，其根據步長和行走過程中軀干的垂直位移之間的關系，通過行走周期中z軸加速度數據計算得到基礎步長。由于人行走速度的變化是一個逐漸變化的過程，在這個過程中相鄰兩步之間的步長會不同，但差異不大，因此本文將卡爾曼濾波應用于基礎步長，進而得到更加精確的步長估計。

2 基于粒子濾波的融合定位

本文采用粒子濾波來融合WiFi定位和PDR。系統狀態是用戶位置，將基于SVM的WiFi指紋定位獲得的用戶位置作為觀測數據，而PDR用于對用戶的運動行為進行建模。

3 實驗及結果分析

3.1 基于SVM的WiFi定位實驗分析

本實驗將SVM分類和回歸結合在一起（稱其為SVC+SVR）進行定位，選擇SVM回歸（SVR）、最近鄰居（Nearest Neighbor， NN）和KNN算法（參數K=4）作為對比實驗。圖1顯示了實驗中各算法的定位結果對比?？梢钥闯觯罕疚幕赟VC和SVR的WiFi指紋算法精度優于只使用SVM回歸分析的SVR算法、NN算法和KNN算法，是幾種定位算法中精度最高的；SVR算法優于NN算法和KNN算法。本文算法的平均定位誤差為2.58m，而SVR算法是3m，NN算法是3.93m，KNN算法是3.57m。和NN算法相比，本文算法將平均定位誤差減少了34.4%；和KNN算法相比，其將平均定位誤差減少了27.7%。

3.2 改進的PDR實驗分析

將本文算法即改進的PDR計步算法同幾種代表性的PDR計步軟件Runtastic Pedometer[12]、Moves[13]和Noom Walk[14]進行了實驗對比。對比實驗包含人在正常行走、快速行走、跑動和變速行走下的情況，每組實驗都是三次實驗的平均值，每次走或跑100步。結果如表1所示。正常行走時4種算法的計步誤差都不大，但隨著行走速度加快或者變速頻繁，4種算法的計步誤差都隨之增加，但本文改進的PDR算法的計步效果最好最穩定，錯誤率不超過2%且對人的速度變化不敏感，計步效果明顯優于其他三組。

結合改進的PDR計步算法，實驗比較了步長計算的基礎算法（即Scarlett算法）和改進的步長算法（即采用卡爾曼濾波改進的Scarlett算法）的誤差率。實驗中以接近勻速和變速各行走40m，采用基礎步長算法和改進步長算法分別估算出行走距離，計算它們和實際距離的誤差。實驗結果如表2所示，改進步長算法對基礎步長算法的精度提高30%左右。

3.3 基于粒子濾波的WiFiPDR融合定位實驗分析

將基于粒子濾波的WiFiPDR融合定位、基于SVM的WiFi定位、改進的PDR三種方法在同樣環境中進行定位實驗，粒子個數100，分別進行了兩組實驗：第一組的真實軌跡是沿著走廊的直線；第二組的真實軌跡是從走廊開始穿過4間教室的曲線。圖2和圖4為三種算法針對直線行走的實驗結果對比，圖3和圖5為三種算法針對曲線行走的實驗結果對比。在直線行走實驗中，WiFi的平均定位誤差為3.18m，PDR為2.76m，而經過粒子濾波融合后平均定位誤差降低為1.21m。曲線行走實驗中，WiFi的平均定位誤差為3.77m，PDR為2.87m，融合后平均定位誤差降低到2.75m。

圖4中點線表示真實軌跡，最左側是起點位置，到走廊盡頭結束，接近勻速行走。圖5中點線表示真實軌跡，最右側是起點位置，經過走廊和4個房間，最后停在左下角房間內，整個過程也是接近勻速。兩圖中的小圓點為基于SVM的WiFi定位繪制的軌跡，它和真實軌跡的重合度較差。WiFi定位是單點定位，沒有利用歷史信息，定位結果很難成為連續的軌跡，會出現位置跳變的現象。兩圖中的點劃線本文改進的PDR方法繪制的軌跡。它和真實路徑的重合度比WiFi高，但存在明顯的誤差累積的現象，前面的誤差會進一步導致后面的定位結果不準確，而系統無法動態調整。圖中的實線是使用基于粒子濾波的WiFiPDR融合定位算法繪制出的行走軌跡。盡管和真實軌跡仍有不符，但總體上它是和真實軌跡重合度最高的曲線。特別是圖4實驗中的直線行走，由于運動軌跡比較簡單，融合定位的結果非常接近實際結果，而圖5實驗中的行走軌跡比較復雜，融合結果和真實結果存在不符，但明顯優于WiFi定位和PDR。

4 結語

WiFi定位和PDR是基于智能手持移動設備的室內定位方法，但是WiFi定位精度不高且定位不穩定，而PDR會出現誤差的累積。本文在改進WiFi定位算法和PDR算法的基礎上，提出通過粒子濾波將其進行融合，從而得到更穩定和更精確的融合定位結果。本文的貢獻包括：1）改進WiFi定位算法，提出將SVM分類和回歸分析相結合進行兩級精確定位；2）改進PDR算法，對原始加速度數據進行預處理，提出根據實時加速度數據動態設定狀態轉換參數識別行走周期的算法，將卡爾曼濾波應用到步長計算中；3）提出通過粒子濾波融合基于SVM的WiFi定位和改進的PDR。通過和幾種代表性WiFi定位算法和PDR方法的對比實驗表明：基于SVM的WiFi定位能夠獲得更高的定位精度，改進的PDR能夠更精確地統計步數和步長，而融合定位算法充分發揮各子系統的優勢，使它無論在精度還是穩定性方面都優于子系統。但是融合定位算法仍然會估計出不合理的行走軌跡，例如穿墻，因此下一步研究會結合室內地圖信息來約束定位結果。

參考文獻：

[1]BRUNATO M， BATTITI R. Statistical learning theory for location fingerprinting in wireless LANs[J]. Computer Networks： the International Journal of Computer and Telecommunications Networking， 2005， 47（6）：825-845.

[2]SCARLETT J. Enhancing the performance of pedometers using a single accelerometer[EB/OL]. [2015-11-20].http：//www.analog.com/media/en/technicaldocumentation/applicationnotes/47076299220991AN_900.pdf.

[3]PARK S K， SUH Y S. A zero velocity detection algorithm using inertial sensors for pedestrian navigation systems[J]. Sensors， 2010， 10（10）：9163-9178.

[4]ALZANTOT M， YOUSSEF M. UPTIME： ubiquitous pedestrian tracking using mobile phones[C]// WCNC2012： IEEE Wireless Communications and Networking Conference. Piscataway， NJ： IEEE， 2012：3204-3209.

[5]SUSI M， RENAUDIN V， LACHAPELLE G. Motion mode recognition and step detection algorithms for mobile phone users[J]. Sensors， 2013， 13（2）：1539-1562.

[6]NIU X， LI M， CUI X， et al. WTrack： HMMbased walk pattern recognition and indoor pedestrian tracking using phone inertial sensors[J]. Personal and Ubiquitous Computing， 2014， 18（8）：1901-1915.

[7]CHEN L H， WU E H K， JIN M H， et al. Intelligent fusion of WiFi and inertial sensorbased positioning systems for indoor pedestrian navigation[J]. IEEE Sensors Journal， 2014，14（11）：4034-4042.

[8]CHEN Z， ZOU H， JIANG H， et al. Fusion of WiFi， smartphone sensors and landmarks using the Kalman filter for indoor localization[J]. Sensors， 2015， 15（1）：715-732.

[9]LI W W L， ILTIS R A， WIN M Z. A smartphone localization algorithm using RSSI and inertial sensor measurement fusion[C]// GLOBECOM2013： IEEE Global Communications Conference. Piscataway， NJ： IEEE， 2013：3335-3340.

[10]WANG J， HU A， LIU C， et al. A floormapaided WiFi/pseudoodometry integration algorithm for an indoor positioning system[J]. Sensors， 2015， 15（4）：7096-7124.

[11]BAHL P， PADMANABHAN V N. RADAR： an inbuilding RFbased user location and tracking system[C]// Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies. Piscataway， NJ： IEEE， 2000：775-784.

[12]Runtastic pedometer[EB/OL]. [2015-08-20]. https：//www.runtastic.com/zh/apps/pedometer.

[13]Moves[EB/OL]. [2015-08-20]. https：//www.movesapp.com/.

[14]Noom Walk[EB/OL]. [2015-08-20]. http：//www.noom.com/walk.php.