王福偉，黃智剛

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

?

室內(nèi)定位中移動(dòng)目標(biāo)軌跡跟蹤研究

王福偉，黃智剛

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

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

關(guān)鍵詞：室內(nèi)定位；軌跡優(yōu)化；卡爾曼濾波；HMM；地圖修正

0引言

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

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

1指紋定位技術(shù)

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

(1)

(2)

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

(3)

選取匹配概率最大的個(gè)柵格點(diǎn)，進(jìn)行位置加權(quán)平均，則目標(biāo)的估計(jì)位置為

(4)

式(4)中，pi為選取的K個(gè)柵格點(diǎn)中第i個(gè)柵格點(diǎn)的位置坐標(biāo)。

在同一柵格點(diǎn)處，WiFi信號(hào)隨時(shí)間變化波動(dòng)性很大，文獻(xiàn)[6]分析了造成WiFi信號(hào)不穩(wěn)定性的因素。由于WiFi信號(hào)的不穩(wěn)定性，當(dāng)進(jìn)行單點(diǎn)連續(xù)定位時(shí)，在相同柵格點(diǎn)或相鄰柵格點(diǎn)處WiFi信號(hào)的變化遠(yuǎn)大于用戶運(yùn)動(dòng)引起的變化，造成用戶前后兩時(shí)刻位置跳躍很大，明顯不符合人的運(yùn)動(dòng)規(guī)律，大大降低了用戶體驗(yàn)。

2改進(jìn)HMM軌跡跟蹤算法

2.1HMM建立

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

2.1.1初始化概率向量π

2.1.2狀態(tài)轉(zhuǎn)移矩陣A

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

(5)

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

(6)

2.1.3觀測(cè)概率B

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

(7)

2.2HMM的定位解碼算法

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

(1)計(jì)算t=1時(shí)的局部概率及隱藏狀態(tài)

使用t=1時(shí)的初始概率及相應(yīng)的觀測(cè)狀態(tài)O1的觀測(cè)概率計(jì)算：

δ(i,1)=πibiO1

(8)

(9)

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

使用上一時(shí)刻的隱藏狀態(tài)及此刻的觀測(cè)狀態(tài)Ot的觀測(cè)概率計(jì)算：

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

(10)

(11)

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

本文提出的解碼定位算法并沒有從上一時(shí)刻所有的狀態(tài)出發(fā)通過計(jì)算局部最佳概率得到局部概率，而是直接由上一時(shí)刻解碼得到的隱藏狀態(tài)出發(fā)計(jì)算得到局部概率，保證在上一時(shí)刻定位柵格點(diǎn)的相鄰柵格點(diǎn)中解算得到當(dāng)前時(shí)刻的隱藏狀態(tài)。

2.3卡爾曼濾波及地圖結(jié)點(diǎn)修正

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

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

(12)

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

(13)

卡爾曼濾波過程為

(1)初始化

(2)更新

(3)地圖結(jié)點(diǎn)修正

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

(4)預(yù)測(cè)

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

k++，轉(zhuǎn)到步驟(2)

上述卡爾曼濾波器中的運(yùn)動(dòng)狀態(tài)方程為勻速直線運(yùn)動(dòng)，因此在運(yùn)動(dòng)狀態(tài)發(fā)生明顯變化的情況下對(duì)下一點(diǎn)的預(yù)測(cè)會(huì)出現(xiàn)很大誤差，有必要進(jìn)行修正，因此本文提出在濾波過程中進(jìn)行實(shí)時(shí)修正。室內(nèi)地圖中，房間的門和走廊的轉(zhuǎn)彎處等都是人運(yùn)動(dòng)狀態(tài)可能發(fā)生變化的地方，因此將這些點(diǎn)的坐標(biāo)進(jìn)行統(tǒng)計(jì)，得到所有的地圖修正結(jié)點(diǎn)M={m1,m2,…,mn}。

地圖結(jié)點(diǎn)處修正的過程為

(1)判斷

(2)修正

3實(shí)驗(yàn)結(jié)果及分析

3.1實(shí)驗(yàn)環(huán)境

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

圖1　柵格點(diǎn)采樣示意圖及真實(shí)行走軌跡

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

本文從兩方面對(duì)所提出算法的性能進(jìn)行分析：一是軌跡效果；二是誤差及標(biāo)準(zhǔn)差。

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

圖2　定位軌跡示意圖

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

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

圖3　算法誤差CDF對(duì)比圖

表1給出了幾種算法定位平均誤差及標(biāo)準(zhǔn)差。

表1　算法定位性能比較

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

4結(jié)束語

本文針對(duì)室內(nèi)定位中出現(xiàn)的定位軌跡跳躍波動(dòng)大的問題，提出用環(huán)境地圖信息輔助建立HMM，并對(duì)HMM的解碼定位結(jié)果進(jìn)行卡爾曼濾波處理以減小量化誤差，利用地圖信息對(duì)卡爾曼濾波器實(shí)時(shí)修正。通過在實(shí)際環(huán)境中測(cè)試證明，本文提出的優(yōu)化算法不僅可以優(yōu)化定位軌跡，而且將定位誤差降低了約42.76%，大大提高定位性能，有利于室內(nèi)定位的實(shí)際應(yīng)用推廣。

參考文獻(xiàn)

[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]張言哲，陳國良，張儷文，等.卡爾曼濾波在無線信號(hào)定位中的應(yīng)用[J].導(dǎo)航定位學(xué)報(bào)，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]趙永翔，周懷北，陳淼，等.卡爾曼濾波在室內(nèi)定位系統(tǒng)實(shí)時(shí)跟蹤中的應(yīng)用[J].武漢大學(xué)學(xué)報(bào)(理學(xué)版)，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

中圖分類號(hào)：P228

文獻(xiàn)標(biāo)識(shí)碼：A

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

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

收稿日期：2015-08-23

引文格式：王福偉，黃智剛.室內(nèi)定位中移動(dòng)目標(biāo)軌跡跟蹤研究[J].導(dǎo)航定位學(xué)報(bào)，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.