室內定位中移動目標軌跡跟蹤研究

王福偉，黃智剛

(北京航空航天大學 電子信息工程學院，北京　100191)

?

室內定位中移動目標軌跡跟蹤研究

王福偉，黃智剛

(北京航空航天大學 電子信息工程學院，北京100191)

摘要：針對基于WiFi的室內定位系統由于WiFi信號的不穩定造成定位軌跡跳躍波動性大的問題，本文提出一種HMM-KFMC算法，該算法針對室內環境下人的運動特征建立隱藏馬爾科夫模型(HMM)，并基于概率型算法改進了解碼定位算法，通過含地圖修正的卡爾曼濾波器(KFMC)降低解碼定位造成的量化誤差并用濾波所得速度分量修正HMM的轉移概率。實際環境中的測試結果表明，與概率型定位算法相比，所提出的算法可以優化定位軌跡，并將定位平均誤差降低了約42.46%。

關鍵詞：室內定位；軌跡優化；卡爾曼濾波；HMM；地圖修正

0引言

近年來，隨著人們對定位的需求越來越多，基于位置信息提供服務這方面的應用變得越來越廣泛。在室外，全球定位系統(global positioning system，GPS)等全球衛星導航系統可以為人們提供精確的定位信息。而在室內，由于建筑物的遮擋，用戶很難接收到GPS信號，因而無法獲取自己在室內的定位信息。因此，室內定位技術的研究受到人們的關注。隨著手機等移動無線設備和無線保真(wireless fidelity，WiFi)技術等的普及，人們可以在不增加額外硬件資源的前提下通過已有的WiFi網絡實現室內定位，從而可以大大節省資源。

基于接收信號強度(received signal strength indication，RSSI)的WiFi室內定位技術，只要求WiFi接入點(access points，APs)發射信號，移動用戶接收和測量信號，對硬件設備要求很低，成為室內定位的趨勢。文獻[1]中，通過建立信號的傳播模型，利用接收到的信號強度計算距離，并且已知APs的位置，通過三邊法計算出用戶的位置。但是這種基于信號傳播模型的定位技術有兩個主要缺點：一是需要知道APs的位置坐標；二是室內環境復雜，信號傳播過程中存在反射、折射、散射和多徑等現象，利用信號傳播模型計算的距離誤差很大，定位結果很不理想。文獻[2-4]提出對于分布有APs的待定位區域，將其劃分為若干個柵格點，在各柵格點中采集各個AP的信號強度建立無線指紋數據庫，對于在任意位置接收到的APs信號強度，通過匹配無線指紋數據庫中最接近的柵格點來估計用戶位置坐標。基于WiFi信號指紋匹配的室內定位技術由于其良好的性能成為人們研究的主要方向。但是，該方法唯一可以利用的有效信息就是離線階段采集的信號強度建成的RSSI數據庫，而在線匹配階段采集的RSSI由于室內環境的復雜多變和WiFi信號本身的不穩定性使得在單點連續定位的過程中產生嚴重的跳動現象，嚴重影響定位精度和用戶體驗。本文通過建立隱藏馬爾科夫模型(hidden Markov model，HMM)，改進適用于室內定位的Viterbi算法，將人在室內的活動規律信息和地圖信息進行有效利用，可以大大提高定位精度。為了減小該算法帶來的量化定位誤差，本文使用卡爾曼濾波器(Kalman filtering，KF)對定位軌跡進行了優化處理，并且提高了定位精度。

1指紋定位技術

基于WiFi的指紋定位技術分為兩個階段：離線建庫階段和在線匹配階段。離線建庫階段，將待定位的區域劃分為若干個柵格RPi(i∈1,…,N)，N為總的柵格數。在每個柵格RPi處進行M次采樣，得到RSSIij=(rij1,rij2,…,rijk)，j∈1,2,…,M為第j次采樣，rijk為第i個柵格第j次采樣得到的APk的信號強度，若無法測得該AP信號強度，則用C=-100 dBm填充 。分別計算信號強度的平均值和標準差存入數據庫中：

(1)

(2)

文獻[2，5]通過測量WiFi信號特征提出可以假設各個AP在每個柵格點處的RSSI服從高斯分布，且相互獨立。給定觀測信號強度RSSI=(s1,s2,…,sk)， 則各個柵格點的匹配概率為

(3)

選取匹配概率最大的個柵格點，進行位置加權平均，則目標的估計位置為

(4)

式(4)中，pi為選取的K個柵格點中第i個柵格點的位置坐標。

在同一柵格點處，WiFi信號隨時間變化波動性很大，文獻[6]分析了造成WiFi信號不穩定性的因素。由于WiFi信號的不穩定性，當進行單點連續定位時，在相同柵格點或相鄰柵格點處WiFi信號的變化遠大于用戶運動引起的變化，造成用戶前后兩時刻位置跳躍很大，明顯不符合人的運動規律，大大降低了用戶體驗。

2改進HMM軌跡跟蹤算法

2.1HMM建立

一個HMM包含兩組狀態集合：隱藏狀態S=[S1,S2,…,St]和觀測狀態O=[O1,O2,…,Ot]。 把劃分好的柵格點序號i作為隱藏狀態，每次測量得到的信號強度向量RSSI=(r1,r2,…,rk)作為觀測狀態。在該HMM中，當前時刻的位置即隱藏狀態St只與前一時刻的隱藏狀態St-1有關，因此它是一階的。那么軌跡跟蹤過程即為已知HMM和觀測狀態O解碼得到隱藏狀態S的過程。HMM可以表示為Η=[π,A,B]。

2.1.1初始化概率向量π

2.1.2狀態轉移矩陣A

A={aij}， 其中aij表示用戶從柵格點i運動到柵格點j的概率，即aij=Pr(St=j|St-1=i)1≤i,j≤N。 由于人在行走過程中速度一般不會大于2m/s，因此只有在柵格點i和柵格點j相互連通的情況下，aij才會為非零值，否則為零。假設柵格點i的相鄰柵格點有Ki個，分別為j1,…,jKi， 則非零的轉移概率為。

(5)

通過這種建立矩陣的方法，相應的地圖信息被包含在HMM中。此外本文提出用卡爾曼濾波計算得到的用戶運動狀態vt對轉移概率進行修正。文獻[7]中提出移動用戶的運動矢量服從高斯分布，均值為μij=pi-pj，pi和pj為柵格坐標，方差為對角經驗矩陣∑v， 則修正因子為

(6)

2.1.3觀測概率B

本文所建立的HMM中，觀測概率B=[b1,…,bN]。 其中，

(7)

2.2HMM的定位解碼算法

為了保證定位的實時性，每次得到一個觀測量Ot后都需要計算此刻的局部最大概率，將該局部最大概率所在的隱藏狀態作為此刻的估計值。改進的具體算法過程為

(1)計算t=1時的局部概率及隱藏狀態

使用t=1時的初始概率及相應的觀測狀態O1的觀測概率計算：

δ(i,1)=πibiO1

(8)

(9)

(2)計算t>1時刻的局部概率δ(i,t)及隱藏狀態

使用上一時刻的隱藏狀態及此刻的觀測狀態Ot的觀測概率計算：

δ(i,t)=qψt-1i·aψt-1i·biOt

(10)

(11)

式(10)中，qψt-1i為轉移概率的修正因子，由式(6)計算所得，其速度分量由卡爾曼濾波器計算得到。

本文提出的解碼定位算法并沒有從上一時刻所有的狀態出發通過計算局部最佳概率得到局部概率，而是直接由上一時刻解碼得到的隱藏狀態出發計算得到局部概率，保證在上一時刻定位柵格點的相鄰柵格點中解算得到當前時刻的隱藏狀態。

2.3卡爾曼濾波及地圖結點修正

由于HMM的隱藏狀態是定位區域劃分成的柵格，因此存在最小量化誤差，即柵格大小。那么就存在如下問題：如果柵格間距過小，就會大大增加離線采樣時的工作量；如果柵格間距過大，則量化誤差過大，導致定位精度降低，實時定位跳躍過大。為了解決上述問題，并且提供計算式(6)中修正轉移概率修正因子的移動用戶運動向量vt=(vx,vy)， 本文采用卡爾曼濾波器對定位軌跡進行優化。

Xk=AXk-1+Wk, Wk～N(0,Qk)

(12)

Zk=HXk+Vk, Vk～N(0,Rk)

(13)

卡爾曼濾波過程為

(1)初始化

(2)更新

(3)地圖結點修正

若滿足修正條件，則初始化濾波器并更新定位位置坐標；

(4)預測

(5)輸出位置坐標并迭代

k++，轉到步驟(2)

上述卡爾曼濾波器中的運動狀態方程為勻速直線運動，因此在運動狀態發生明顯變化的情況下對下一點的預測會出現很大誤差，有必要進行修正，因此本文提出在濾波過程中進行實時修正。室內地圖中，房間的門和走廊的轉彎處等都是人運動狀態可能發生變化的地方，因此將這些點的坐標進行統計，得到所有的地圖修正結點M={m1,m2,…,mn}。

地圖結點處修正的過程為

(1)判斷

(2)修正

3實驗結果及分析

3.1實驗環境

為了驗證所提出算法的性能，在中關村天創科技大廈12層北京金坤科創有限公司的辦公環境進行測試驗證。如圖1所示，將辦公環境的走廊和研發室進行柵格劃分，柵格間距為2.4 m，定位區域大小約為55 m×30 m。在每個柵格點，采用自己開發的手機軟件直接對定位區域中的WiFi熱點采樣60次建立指紋數據庫，采樣間隔為1s，不需要知道AP的具體位置信息。指紋數據庫建立完成后，手持手機沿如圖1所示軌跡勻速行走，手機中采樣軟件設置為每隔1 s對所有AP掃描一次，得到用戶行進過程中的采樣數據以便進行定位解算。記錄每次轉彎時間，以計算每一時刻用戶的真實位置。

圖1　柵格點采樣示意圖及真實行走軌跡

3.2實驗結果與性能分析

本文從兩方面對所提出算法的性能進行分析：一是軌跡效果；二是誤差及標準差。

幾種算法的軌跡效果圖如圖2所示。

圖2　定位軌跡示意圖

由圖2可以看出，概率法直接生成的定位軌跡點非常不均勻，跳躍性很大，會出現直接穿過墻跳到房間的情況；改進HMM算法可以對定位軌跡點進行優化，變得非常均勻，但是由于存在量化誤差，每次跳動距離至少為柵格大小；對改進HMM算法進行卡爾曼濾波，雖然定位軌跡點跳躍問題得到改善，但是在轉彎的時候，速度分量得不到及時修正，造成慣性穿墻現象；對改進HMM算法進行加有地圖修正的卡爾曼濾波(KFMC)后(圓圈為地圖結點)，慣性穿墻問題得到解決，定位軌跡得到極大優化。

圖3給出了幾種算法的定位軌跡點與真實行走軌跡點之間誤差距離的累積分布圖。

圖3　算法誤差CDF對比圖

表1給出了幾種算法定位平均誤差及標準差。

表1　算法定位性能比較

由圖3及表1可以看出，相對于概率型算法，本文提出的基于HMM建模的軌跡優化算法將定位平均誤差降低了約42.76%，且定位波動大大降低，將小于2 m定位誤差的百分比由52.10%提高到80.67%。

4結束語

本文針對室內定位中出現的定位軌跡跳躍波動大的問題，提出用環境地圖信息輔助建立HMM，并對HMM的解碼定位結果進行卡爾曼濾波處理以減小量化誤差，利用地圖信息對卡爾曼濾波器實時修正。通過在實際環境中測試證明，本文提出的優化算法不僅可以優化定位軌跡，而且將定位誤差降低了約42.76%，大大提高定位性能，有利于室內定位的實際應用推廣。

參考文獻

[1]SERRANO O，RODERO MERINO L，MATELLN OLIVERA V，et al.Robot localization using WiFi signal without intensity map[J].Proceedings of V Workshop de Agentes Físicos，2004(3)：25-26.

[2]YOUSSEF M A，AGRAWALA A，SHANKAR A U.WLAN location determination via clustering and probability distributions[C]//The Institute of Electrical and Electronics Engineers(IEEE).Pervasive Computing and Communications(PerCom).Texas：IEEE，2003：143-150.

[3]FENG C，AU W S A，VALAEE S，et al.Compressive sensing based positioning using RSS of WLAN access points[EB/OL].(2009-12-01)[2015-03-12].http：//www.comm.toronto.edu/～valaee/Publications/10-Feng-Infocom.pdf.

[4]VENETSANOPOULOS A N，PLATANIOTIS K N，KUSHKI A.Kernel-based positioning in wireless local area networks[J].IEEE Transactions on Mobile Computing，2007，6(6)：689-705.

[5]ROOS T，MYLLYMAKI P，TIMI H，et al.A probabilistic approach to WLAN user location estimation[J].International Journal of Wireless Information Networks，2002，9(3)：155-164.

[6]張言哲，陳國良，張儷文，等.卡爾曼濾波在無線信號定位中的應用[J].導航定位學報，2014，2(4)：83-86.

[7]HOANG M K，SCHMALENSTROEER J，DRUEKE C，et al.A hidden Markov model for indoor user tracking based on WiFi fingerprinting and step detection[C]//The Institute of Electrical and Electronics Engineers(IEEE).Proceedings of the 21st European Signal Processing Conference (EUSIPCO).Marrakech：IEEE，2013：1-5.

[8]趙永翔，周懷北，陳淼，等.卡爾曼濾波在室內定位系統實時跟蹤中的應用[J].武漢大學學報(理學版)，2009，55(6)：696-700.

[9]KUSHKI A，PLATANIOTIS K N，VENETSANOPOULOS A N.Intelligent dynamic radio tracking in indoor wireless local area networks[J].IEEE Transactions on Mobile Computing，2010，9(3)：405-419.

Research on Moving Target Trajectory Tracking of Indoor Positioning

WANGFuwei，HUANGZhigang

(School of Electronics and Information Engineering，Beijing University of Aeronautics and Astronautics，Beijing 100191，China)

Abstract：The indoor positioning system based on WiFi signal has the problem of the leap and volatility of the positioning trajectory caused by the WiFi signal’s instability.We propose a HMM_KFMC algorithm which uses the positioning area’s map information to optimize the positioning trajectory.In this paper，a HMM model containing map information is established applying to people’s indoor dynamic characters，then we propose our decoding algorithm for the indoor positioning problem and finally use a Kalman Filtering containing map corrections to reduce the quantization error.The experimental results show that our proposed algorithm can optimize the positioning trajectory and significantly improve the positioning performance which reduces the positioning error by about 42.46%.

Key words：indoor positioning；trajectory optimization；Kalman filtering；HMM；map-correctting

中圖分類號：P228

文獻標識碼：A

文章編號：2095-4999(2016)-01-0033-05

作者簡介：第一王福偉(1989—)，男，山東濰坊人，碩士生，主要從事室內定位軌跡跟蹤研究工作。

收稿日期：2015-08-23

引文格式：王福偉，黃智剛.室內定位中移動目標軌跡跟蹤研究[J].導航定位學報，2016，4(1)：33-37.(WANG Fuwei，HUANG Zhigang.Research on Moving Target Trajectory Tracking of Indoor Positioning[J].Journal of Navigation and Positioning，2016，4(1)：33-37.)DOI：10.16547/j.cnki.10-1096.20160107.