基于核函数与卡尔曼滤波的室内定位方法

张　旭,　张　裕,2,　郑正奇,,　陈　雯

(1.华东师范大学 信息科学技术学院,上海　200241;2.上海市计量测试技术研究院,上海　200120;3.空间信息和定位导航上海高校工程中心,上海　200241)



基于核函数与卡尔曼滤波的室内定位方法

张旭1,张裕1,2,郑正奇1,3,陈雯3

(1.华东师范大学 信息科学技术学院,上海200241;2.上海市计量测试技术研究院,上海200120;3.空间信息和定位导航上海高校工程中心,上海200241)

摘要：针对室内定位中存在的定位精度不高、定位稳定性较差的问题,提出了一种基于核函数与卡尔曼滤波结合的室内定位算法.首先利用核函数作为匹配算法进行初步定位,高斯核函数可以充分捕获参考点指纹与测试点RSS之间的非线性相关性,取得比K最近邻算法更好的匹配效果,再利用卡尔曼滤波对核函数的定位结果作滤波处理.实验结果表明,在真实无线局域网环境下,对核函数定位的结果作卡尔曼滤波处理后,均方根误差降低了25%,2 m以内的定位准确度由75%提高到90%,定位稳定性提高了29%.

关键词：室内定位; 定位准确度; 高斯核函数; 卡尔曼滤波

随着当今社会的发展,基于位置的服务变得越来越重要.室外定位技术以全球定位系统为基础,包括美国的GPS定位系统,俄罗斯的GLONASS定位系统以及我国自主研制的北斗卫星导航定位系统,利用这些定位系统可以实现室外全天候的实时定位.然而,卫星信号在室内环境中强度较弱,如果在室内仍采用卫星信号进行定位,定位误差可达几十米甚至上百米,这显然无法满足在室内3m以内定位精度的需求.考虑到目前室内环境中普遍存在的WLAN信号[1-3],人们开始考虑采用WLAN信号来实现室内定位.

室内定位的研究始于20世纪90年代末,其中也涌现出一批优质的定位系统和定位算法.美国微软研究院于2000年首次提出了基于WLAN的室内定位系统RADAR[4],在空旷的室内环境下,定位精度可达2～5m,但在复杂的室内环境,定位精度并不理想.文献[5]提出了Horus系统,该系统采用概率统计模型,并首次将聚类分块运用于指纹库的建立中,与RADAR系统相比,既提高了定位精度,同时也降低了系统的计算复杂度.在算法优化方面,研究人员将人工神经网络[6](artificialneuralnetwork,ANN)、支持向量回归[7](supportvectorregression,SVR),以及核函数[8]等算法应用于室内定位中,进一步提高了定位精度.虽然上述定位系统和定位算法在室内定位领域都取得了一定的成果,但仍存在定位精度不够理想、定位稳定性较差等问题[9].

为了进一步提高定位精度,本文提出了基于核函数和卡尔曼滤波的室内定位方法.首先采用核函数法进行初步定位,针对实时定位过程中用户移动位置不平缓、定位稳定性较差的问题,再利用卡尔曼滤波算法对核函数定位结果作滤波修正,实验结果表明滤波以后定位精度和定位稳定性均有明显改善.

1Kernel函数定位

(1)

如果定义在X×X上的函数K满足:∀x,z∈X,都有

(2)

则称函数K(x,z)为核函数,其中〈·〉为高维空间H中的内积.核函数可以将低维空间线性不可分的模式映射到高维特征空间,从而在高维特征空间中挖掘出数据间的非线性相关性.

传统的定位算法如K最近邻(Knearestneighbor,KNN)算法[10],仅通过度量参考点和测试点间的接收信号强度(receivedsignalstrength,RSS)的欧式距离来实现定位,而未考虑到RSS之间可能存在的非线性相关性,虽然定位算法较简单,但定位精度并不理想.

利用核函数可以度量在测试点采集的接入点(accesspoint,AP)的RSS样本向量同每个参考点指纹的相似性,从中找出相似度最高的若干个指纹,再将这若干个指纹的位置坐标进行加权平均即可估算出待定位点的位置坐标.由于高斯核函数平滑性能较好,而且具有能够逼近任意非线性函数的能力,故本文采用高斯核函数进行定位,对应的相似性权重系数为

(3)

式中:F(Pi)是一个L×n的矩阵,代表第i个参考点Pi的指纹信息,i=1,2,3,…,L;t为扫描次数,t=1,2,3,…,n;r是一个L×1的矩阵,表示在测试点采集到的来自于L个AP的RSS;σ为核函数的宽度.由式(3)计算得出相似性权重最大的前k个指纹,则待定位点坐标为

(4)

相较于KNN算法中取某个AP若干次扫描所得信号强度的平均值,核函数可以充分利用每个参考点上所有的RSS样本信息,在核函数空间中可以较好地捕获信号RSS的非线性相关性,因此可以获得比KNN算法更好的定位效果.

2Kalman滤波

Kalman滤波[9,11-14]是一种线性最小方差估计,算法采用状态空间方法在时域内设计滤波器,适用于对多维随机过程进行滤波,而且具有递推性.当模型足够准确且系统状态和参数较为稳定时,滤波性能较好.利用卡尔曼滤波可以减少噪声对系统的影响,从而达到提高定位精度的目的.

由于在实时定位过程中,一般要求在较短的时间内计算出用户的位置.然而较短的信号采集时间会导致采集到的信号样本偏少,从而定位偏差较大,用户移动位置不平缓.本文提出一种基于Kernel-Kalman(KK)的室内定位方法,首先利用核函数法对待测点进行定位计算,再利用卡尔曼滤波对核函数定位结果作滤波修正,以此进一步减小核函数定位的偏差,提高定位精度.

卡尔曼滤波的预测方程和观测方程分别为

(5)

zk=Hkxk+mkk≥1

(6)

式中:xk为状态向量;zk为观测向量;Φk,k-1为状态转移矩阵;Hk为观测矩阵;Γk-1为系统噪声矩阵;wk-1与mk分别是过程噪声和观测噪声,一般为高斯白噪声,且它们满足

式中:Q与R分别代表过程噪声和观测噪声的方程矩阵；δ为冲激函数.

初始条件为

(7)

(8)

卡尔曼滤波的时间更新方程为

(9)

测量更新方程为

(11)

式中,K为滤波增益.

定义用户行走的二维模型如下:

(12)

(13)

3实验结果与分析

分别利用仿真场景和真实场景将提出的KK算法与Kernel算法以及室内定位中较常用的KNN算法进行对比,通过定位结果的RMSE(均方根误差)、定位误差的CDF(累积分布函数)及定位误差的Std.(标准差)这3个方面的对比来验证本文所提出算法的有效性.

3.1仿真场景

3.1.1仿真场景的建立

首先利用Matlab仿真对本文提出的定位方法进行了详细的性能分析.定位区域面积为40m×40m,周围共分布12个AP.参考点个数共计1 600个,间距为1m.按照行走路径选取测试点个数为200个.仿真实验场景如图1所示(图中未标出行走路径).

图1　仿真场景示意图

对于某一位置Q处,第i个接入点APi在点Q处的信号RSS平均损耗为

(14)

式中:dAPi,Q表示接入点APi与采样点位置Q间的距离;P(d0)表示在参考距离d0=1m处RSS信号传播的路径损耗;α表示路径损耗系数.若以Pt表示接入点的发射功率,则APi在采样位置Q处的信号强度为

(15)

仿真实验的基本参数设置[15]如表1所示(见下页).

为了与真实环境相接近,在本仿真实验中测试点所接收到的平均信号强度加入了均值为0,方差为1的高斯白噪声.

3.1.2仿真实验结果

仿真实验结果如图2所示(见下页).其中,图2(a)给出了3种算法定位结果的均方根误差.当选择200个测试点时,KNN,Kernel及KK的RMSE分别为1.21,0.95,0.72m.核函数法相比于KNN算法定位精度提高了22%,卡尔曼滤波可以进一步将核函数法定位精度提高24%.

表1　基本参数

图2　仿真场景下实验结果

图2(b)展示了3种定位算法定位误差的累积概率分布.可以看出核函数法定位性能要明显优于KNN算法,经过卡尔曼滤波进行滤波修正后,可以将核函数法1m以内定位准确率由69%提高至84%.

定位标准差可以反映定位算法的稳定性,如图2(c)所示.在定位的稳定性方面,Kernel算法优于KNN算法.经过卡尔曼滤波以后,核函数的定位稳定性有明显改善,定位标准差由0.476m降为0.355m,定位稳定性提高了25%.

3.2实际场景

3.2.1实际场景的搭建

图3为实验真实环境的示意图,位于上海市计量测试技术研究院某实验楼的4楼.实验场景的面积为50m×20m,场景内包含13个AP,相邻AP间的距离约为20m.参考点和测试点均位于走廊及两侧的楼厅.图中黑色圆点代表参考点,红色圆点代表测试点.黑色连线连接各个测试点,表示测试者的行走轨迹,测试者从S点出发,按箭头所示路线行走至D点停止.

图3　实际场景示意图

本次实验选取了116个参考点,60个测试点.采集设备为一台联想e450笔记本电脑,配置为i5-4210U,8GBDDR3内存,WiFi信号扫描软件为inSSIDer,扫描频率约为1次/s.实验者在参考点的采样时间为180s,在线测试阶段,每个测试点的采样时间为30s,即每个测试点读取信号强度约30次.数据处理平台仍采用Matlab,包含数据文件解析、位置指纹库的建立以及在线匹配运算等模块.

3.2.2实际场景的实验结果

图4展示了真实场景下的实验结果,从图4(a)中可以看出,随着测试样本的增多,定位算法的RMSE趋于稳定.当样本个数为60时,KK算法的均方根误差为1.37m,而核函数法和KNN算法的RSME分别为1.83m和1.94m.核函数法的定位误差低于KNN算法.卡尔曼滤波可以将核函数法的定位精度提高25%.

图4　实际场景下实验结果

图4(b)给出了KK算法、核函数法以及KNN算法三者的定位误差累积概率分布.以2m以内定位误差百分比作为评价指标,卡尔曼滤波可以将核函数法定位准确度由75%提高至90%,且由图中可以看出,经过卡尔曼滤波以后,定位的误差可以基本保证在3m以内.

图4(c)为实际场景中3种方法定位标准差的对比结果,随着测试样本数的增多,定位标准差趋向于稳定.当测试样本数为60个时,KNN和核函数法的定位标准差分别为1.12m和1.08m,而KK算法的定位标准差为0.76m.相比于KNN定位法,核函数法的定位稳定性改善不够明显,猜想可能的原因是测试点个数较少,且实验场景只包含了走廊和楼厅的空白区域,所以测试数据无法完整地展现定位性能.但可以明显看出,经过卡尔曼滤波以后,核函数法的定位稳定性提高了29%,定位性能有较大的改善.

4结论

提出了一种基于核函数与卡尔曼滤波结合的室内定位算法,首先采用核函数对待测点作初步定位,再利用卡尔曼滤波对定位结果作滤波处理.核函数可以充分利用参考点的所有RSS样本信息,较好地捕获了信号RSS的非线性模式,能够获得比KNN算法更好的定位性能.针对室内定位中用户移动位置不平缓、定位稳定性较差的问题,卡尔曼滤波可以显著降低定位位置波动,提高定位的稳定性.实验结果表明,在对核函数定位的结果做卡尔曼滤波处理后,均方根误差降低了25%,2m以内的定位准确度由75%提高到90%,定位稳定性提高了29%.

随着具有WiFi连接功能的智能手机的大量普及,本文提出的算法可以在基于智能移动设备的室内定位系统中广泛运用.未来的工作主要有:a.针对室内WiFi信号波动较大的问题,考虑用卡尔曼滤波对设备采集到的RSS作滤波处理,提高扫描的WiFi信号的稳定性;b.从减少移动设备定位计算量的角度出发,采用K-means聚类及其改进算法对位置指纹库进行聚类分析,从而降低系统的匹配计算量,提高定位系统的响应速率.

参考文献：

[1]BISIOI,CERRUTIM,LAVAGETTOF,etal.AtraininglessWiFifingerprintpositioningapproachovermobiledevices[J].IEEEAntennasandWirelessPropagationLetters,2014,13:832-835.

[2]CHONY,CHAH.LifeMap:asmartphone-basedcontextproviderforlocation-basedservices[J].IEEEPervasiveComputing,2011,10(2):58-67.

[3]LIUH,DARABIH,BANERJEEP,etal.Surveyofwirelessindoorpositioningtechniquesandsystems[J].IEEETransactionsonSystems,Man,andCybernetics,PartC(ApplicationsandReviews),2007,37(6):1067-1080.

[4]CHENLN,LIBH,ZHAOK,etal.AnimprovedalgorithmtogenerateaWiFifingerprintdatabaseforindoorpositioning[J].Sensors,2013,13(8):11085-11096.

[5]REHIMM.Horus:aWLAN-basedindoorlocationdeterminationsystem[M].Maryland:UniversityofMarylandatCollegePark,2004.

[6]FANGSH,LINTN.Indoorlocationsystembasedondiscriminant-adaptiveneuralnetworkinIEEE802.11environments[J].IEEETransactionsonNeuralNetworks,2008,19(11):1973-1978.

[7]WUZL,LICH,NGJKY,etal.Locationestimationviasupportvectorregression[J].IEEETransactionsonMobileComputing,2007,6(3):311-321.[8]KUSHKIA,PLATANIOTISKN,VENETSANOPOULOSAN.Kernel-basedpositioninginwirelesslocalareanetworks[J].IEEETransactionsonMobileComputing,2007,6(6):689-705.

[9]赵永翔,周怀北,陈淼,等.卡尔曼滤波在室内定位系统实时跟踪中的应用[J].武汉大学学报(理学版),2009,55(6):696-700.

[10]FANGSH,LINT.PrincipalcomponentlocalizationinindoorWLANenvironments[J].IEEETransactionsonMobileComputing,2012,11(1):100-110.

[11]OUTEMZABETS,NERGUIZIANC.Accuracyenhance-mentofanindoorANN-basedfingerprintinglocationsystemusingKalmanfiltering[C]∥ProceedingsoftheIEEE19thInternationalSymposiumonPersonal,IndoorandMobileRadioCommunications.Cannes:IEEE,2008:1-5.

[12]CHIJN,QIANCF,ZHANGPY,etal.AnovelELMbasedadaptiveKalmanfiltertrackingalgorithm[J].Neurocomputing,2014,128:42-49.

[13]NGUYENHN,ZHOUJ,KANGHJ.AcalibrationmethodforenhancingrobotaccuracythroughintegrationofanextendedKalmanfilteralgorithmandanartificialneuralnetwork[J].Neurocomputing,2015,151:996-1005.

[14]CHENZ,ZOUH,JIANGH,etal.FusionofWiFi,smartphonesensorsandlandmarksusingtheKalmanfilterforindoorlocalization[J].Sensors,2015,15(1):715-732.

[15]张明华,张申生,曹健.基于无线局域网定位的误差关键因素分析与仿真[J].系统仿真学报,2009,21(15):4866-4869.

(编辑:丁红艺)

Indoor Positioning Method Based on Kernel Function and Kalman Filtering

ZHANG Xu1,ZHANG Yu1,2,ZHENG Zhengqi1,3,CHEN Wen3

(1.SchoolofInformationScienceTechnology,EastChinaNormalUniversity,Shanghai200241,China;2.ShanghaiInstituteofMeasurementandTestingTechnology,Shanghai200120,China;3.EngineeringCenterofSHMECforSpaceInformationandGNSS,Shanghai200241,China)

Abstract：Against the problems that indoor positioning suffers from low accuracy and poor stability,an indoor positioning method based on kernel function and Kalman filtering was presented.The Gaussian kernel function was adopted for initial positioning,which can measure the nonlinear similarity between reference points’ fingerprint and test points’ RSS(received signal strength),so it will get better accuracy and stability than the K nearest neighbor algorithm.Then the Kalman filtering was used for filtering the positioning results.The experimental results show that in the real WLAN(wireless local area networks)environment,the RMSE(root mean square error)of kernel function positioning results processed by Kalman filtering is decreased by 25%,the positioning accuracy within 2 meters is increased from 75% to 90%,and the positioning stability is increased by 29%.

Keywords：indoor positioning; positioning accuracy; Gaussian kernel; Kalman filtering

文章编号：1007-6735(2016)03-0287-06

DOI：10.13255/j.cnki.jusst.2016.03.013

收稿日期：2015-11-20

基金项目：国家自然科学基金资助项目(61372086,41201380);上海市科委科技创新计划项目(13511500300);国家质检总局科技计划项目(2014QK140)

通信作者：张裕(1978-),男,博士后.研究方向:室内定位.E-mail:zhangyu95900@163.com

中图分类号：TP 393

文献标志码：A

第一作者： 张旭(1991-),男,硕士研究生.研究方向:室内定位.E-mail:zhangxuhs@163.com