室内定位中移动目标轨迹跟踪研究

王福伟，黄智刚

(北京航空航天大学 电子信息工程学院，北京　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.