室内定位系统中指纹库的优化方法

马鑫迪,马建峰,高 胜

(西安电子科技大学计算机学院,陕西西安 710071)

室内定位系统中指纹库的优化方法

马鑫迪,马建峰,高 胜

(西安电子科技大学计算机学院,陕西西安 710071)

指纹库的好坏直接影响到室内定位的定位精度,而现有的室内定位算法大都是建立在原始指纹库的基础之上的,缺乏对指纹库的优化处理.笔者利用k-means算法优化指纹库的构建过程,通过聚类的思想剔除已采集指纹库中的“噪点”,从而为室内定位算法提供较好的数据样本源.实验结果表明,与现有的室内定位系统相比,利用优化后的指纹库进行定位能够明显提高室内定位的精度.

智能终端;k-means方法;指纹库优化;去噪

近年来,基于位置的服务（Location-Based Services,LBSs)得到广泛的应用.作为LBSs的核心支撑技术,移动定位技术受到广泛的关注.现有的移动定位技术可分为:室外定位和室内定位,其中室外定位已有成熟的系统,如全球定位系统（Global Position System,GPS)、北斗等,并且已经达到较高的定位精度,能够有效地满足用户在室外环境中对精确性的需求.在室内环境下,用户通常也需要定位自己所在的位置,例如,在大型商场中,用户利用定位系统定位当前的位置,然后按照地图寻找自己需要的商品.然而,在室内环境中,卫星信号穿透建筑物墙壁后,信号衰减非常严重,并且室内障碍物较多,环境比较复杂,进一步引起信号的衰落.因此,室外定位技术无法应用于室内环境中,所以,如何实现高效精确的室内定位已成为研究热点和难点之一.

目前,研究人员致力于部署更加灵敏且精确的室内定位系统[1-3].与此同时,用于定位过程中的定位感知技术也在不断丰富,如蓝牙技术、超声波定位感知技术、射频识别技术及基于无线局域网（Wireless Local Area Network,WLAN)的室内定位技术等.Laoudias等[4]利用指纹库匹配的方法开发了Airplace系统,其定位精度可达到2～4 m;Yang等[5]总结了现有的室内定位算法,并利用终端上的传感器开发了基于Wi-Fi（Wireless-Fidelity)信号且可在三维空间上实时定位的LIFS定位系统;Ozdenizci等[6]则提出采用NFC标签辅助定位的方法,利用终端具有的NFC扫描功能来扫描附近的NFC标签进行辅助定位;Yang等[7]提出通过监听物理层信道的状态来提高精度;Liu等[8]采用多用户协同定位的方法,使用户定位更准确;Fang等[9]则通过从已测得的RSS信号值中提取特征性较强的信号,从而降低室内环境中无线网络的多径效应,使得定位精度提高约40%.

另外,在某些研究工作中,部分学者利用k-means聚类算法[10]和主成分分析（Principal Component Analysis,PCA)[11]的思想对指纹库进行处理,从而降低计算的复杂度并提高定位的精度;而Fang等[12]通过研究,提出动态混合投影（Dynamic Hybrid Projection,DHP)方法对主成分分析和多重判别分析（Multiple Discriminant Analysis,MDA)进行优势互补,使定位精度得到进一步提升.

利用指纹库中存储的信号值与当前扫描到的信号值进行匹配定位是目前室内定位算法的主要思路之一.但是,在采集指纹数据的过程中,由于信号源功率不稳定或者室内环境的变化,会使终端采集到的信号数据波动比较大,笔者将这些波动比较大的数据称为信号“噪点”.现有的室内定位算法在进行定位时大都没有考虑到对指纹库的优化,而指纹库的好坏又直接影响到定位的精度,所以,采用未优化的指纹库会在一定程度上影响到定位精度.因此,如何优化指纹库,剔除指纹库中的信号“噪点”,提高定位精度是要解决的主要问题.

文中采用k-means聚类算法[13]对指纹库进行优化处理,把在每一个位置采集到的每个AP的一组信号值作为一个类进行计算,将这组信号值中不属于该类的数据剔除掉,即将采集的信号“噪点”剔除.通过部署实验环境,采集实验数据,并将优化后的指纹库和未优化的指纹库用于同一定位算法进行定位结果对比,结果表明对指纹库进行优化后,定位误差小于1 m的概率相比于优化前有明显提高.

1 k-means聚类算法

聚类思想[13]是指将一组特征数据分为一个一个的类,在一个类之内的数据相似度比较高,而类之间的数据相似度比较低.

笔者采用k-means聚类算法[13]实现对指纹库的优化过程.在聚类问题中,给定训练样本{x（1),x（2),…,x（n)}.然后,利用k-means算法将样本聚类成k个簇.例如,将太空中的星星进行聚类计算,最终将所有的星星聚集成k个星团.首先,需要随机地选取太空中的k个点（或者k个星星)作为k个星团的质心,并对每颗星星计算其到每一个星团质心的距离,选择距离最近的那个星团作为这颗星星所属的类.经计算后,每一颗星星都有了自己的星团.最后,对于每个星团,重新计算其质心.重复以上步骤,直到质心不变或者变化很小.

在利用k-means算法进行指纹库优化时,可以把指纹库里的信号值看作太空中的星星进行聚类计算,首先,计算每个类的质心,然后,判断该类中的每一个元素是否满足聚类条件属于这个类,如果不属于,则删除元素并重新计算其质心;重复以上步骤直到所有的元素均满足条件为止.

2 指纹库优化算法及定位算法

首先设计了指纹库的优化算法;然后,对定位系统中的定位算法进行了描述,并解释了指纹库优化算法在定位算法中的执行过程.

2.1 指纹库优化算法

采用k-means聚类算法对指纹库进行优化处理.在优化处理过程中,可以把每个位置采集到的每个无线接入点（Access Point,AP)的一组信号值作为一个聚类,共有mn个聚类.其中,m为采集的位置个数,n为采集数据过程中采集到的所有AP数.

利用k-means聚类算法剔除信号“噪点”的具体实现算法描述如下:

X集合为mn组信号值,xij为第i个聚类中第j个信号值,x[i][].length为第i个聚类中元素的个数,i∈1,2,…,mn,质心μi表示第i个聚类的中心,Φ为阈值,当信号值满足时,认为信号值xij为“噪点”,将其删除.

假设x[i][]集合为终端在位置（a,b)处采集到的某个AP的信号集合,则首先计算集合x[i][]的平均信号值,作为第1轮的中心μi,然后再判断集合x[i][]中的每个元素是否满足条件属于这个聚类,如果不属于,则直接作为坏点删除,否则会对构建的指纹库影响比较大,最终会影响到定位的精度.重复以上步骤,直到集合x[i][]中所有的元素均满足条件属于这个聚类为止.利用优化算法对数据库中的数据进行优化处理,最终计算出mn个聚类的中心作为构建指纹库的元素.

2.2 定位算法

将优化后的指纹库应用于加权k最邻域（Weighted K-Nearest Neighbor,WKNN)算法[4]进行定位测试.WKNN算法的执行流程如图1所示.

图1 WKNN算法执行流程

WKNN算法执行过程中,首先需要根据式（1)计算出Si,（Xi,Yi),Ri1,Ri2,Ri3,…,Rin为存储在指纹库中第i个样本点对应的坐标及n个AP的信号强度,R′1,R′2,R′3,…,R′n为用户在当前位置采集到的对应AP的信号强度,这样就会求出集合S={S1,S2,S3,…,Sm}.集合S与指纹库中的m个样本点坐标相对应,然后,系统将集合S按从大到小的顺序排序为集合S′,根据参数k从集合S′中选择出前k个S′i对应的坐标进行定位计算.由于Si表示当前位置扫描到的信号值与指纹库中处理后的信号值的欧氏距离的倒数,所以,可以将集合S的元素作为每个坐标的权重,并利用选择出的k个点进行用户位置的计算.

文中所采用的k-means算法将用于计算指纹库中的坐标（Xi,Yi)处的元素Ri1,Ri2,Ri3,…,Rin,其计算流程如图2所示.

图2 k-means算法流程图

假设系统在一个坐标处采集了z组数据,并且每组数据有n个AP信号值.首先,系统从数据库中导出采集的原始数据（Xi,Yi),Rj1,Rj2,Rj3,…,Rjn,然后利用k-means算法进行优化计算,将筛选出的“噪点”删除,如图2中黑色方格所示,最后将删选后的数据进行求中心得到Ri1,Ri2,Ri3,…,Rin作为终端在坐标（Xi,Yi)处的特征值.而没有通过k-means算法优化的数据,如图2中（Xi,Yi),R′i1,R′i2,…,R′in数据所示,由于存在信号“噪点”,所以,得出的R′i1,R′i2,…,R′in特征值与正常值存在明显偏差,最终导致定位不准确.

3 实验及评估

首先描述系统的开发环境;然后利用系统采集数据,并对数据集进行分析,观察指纹库是否需要进行优化;最后对系统进行测试,并对测试结果进行定位精度分析.

3.1 实验环境及数据分析

由于Android终端设备处理能力有限,并且存在功耗问题,所以Laoudias等开发的AirPlace系统存在系统缺陷.笔者在Air Place系统的基础上进行改进,将主要计算中心从Android终端迁移到服务器端,使得Android终端计算量减小,从而降低功耗.系统开发环境如表1所示.

表1 系统开发环境

图3 数据采集

基于实验室环境采集数据并进行系统测试.首先,将系统设定为每个位置采集30组数据,每隔0.5 s采集一次,然后,选择当前所处的位置,并采集数据.采集结果如图3所示.

在处理样本集构建指纹库之前,先对样本集数据进行观察,随机抽取终端在某个位置扫描到的某个AP的一组信号值,观察其波动是否明显.表2描述了随机抽取数据的波动大小.

由表2可得,在14 s和25 s处,数据存在明显波动,而且如此大的波动幅度会影响系统定位的精度.所以,可以认为14 s和25 s处的数据为信号“噪点”,若不删除,必定会影响定位的精度.因此可以得出,进行信号数据“去噪”是非常有必要的.

3.2 实验结果评估

为了验证经k-means算法优化后的指纹库可以提高定位的准确率,笔者在实验室环境中多次使用设计的定位系统,分别采用优化后的指纹库和未优化的指纹库利用相同的定位算法进行定位并记录定位结果,然后对结果数据进行定位误差分析.其中一组定位结果如图4所示（黑色圆点表示当前位置,内圆表示离当前位置1 m的距离,外圆表示离当前位置2 m的距离).

表2 随机抽取数据波动大小

图4 定位结果

从多次试验中随机选取3组定位结果进行分析,并从每组结果中分别抽取30个,50个,100个误差点进行统计分析,3组统计结果分别如图5～7所示.

图5～7中横坐标表示误差分别为1 m,2 m,…,5 m,纵坐标表示误差在1 m,2 m,…,5 m内的概率.因为3组数据分别采集于不同的时间点,信号干扰程度也不同,所以完全可以表现出优化后指纹库的性能.

图5 1号数据结果分析

图6 2号数据结果分析

对图5进行分析,可以得出,当抽取30个点进行对比时,采用未优化的指纹库进行定位,误差在1 m之内的概率只有10%,而采用优化后的指纹库进行定位,误差在1 m之内的概率达到了50%;当抽取50个点进行对比时,采用未优化的指纹库进行定位的误差在1 m之内的概率只有8%,而采用优化后的指纹库进行定位的误差在1 m之内的概率为38%;当抽取100个点进行对比时,采用未优化的指纹库进行定位的误差在1 m之内的概率为11%,而采用优化后的指纹库进行定位的误差在1 m之内的概率为34%.因此,可以得出采用优化后的指纹库进行定位的误差在1 m之内的概率更大.

对图6进行分析,可以得出,在采集2号数据时,信号干扰比较大,导致定位误差比较大,但是也可以从统计的结果分析出优化后的指纹库能使定位更精确.分析结果显示采用未优化的指纹库进行定位的误差在1 m之内的概率均为0,在2 m之内的概率分别为0.07,0.02,0.03,而采用优化后的指纹库的定位误差在1 m之内的概率分别为0,0.14,0.06,在2 m之内的概率分别为0.33,0.32,0.21.因此,可同样说明采用优化后的指纹库进行定位能够提高定位的准确率.

图7 3号数据结果分析

对图7的分析同图5分析,也能得出同样的结论.

因此得出结论,采用k-means算法进行优化后的指纹库能使定位误差以更大的概率保持在较小的范围内,也就是说,优化后的指纹库与未优化的指纹库相比,可以大大提高定位的精度.

4 结束语

文中引入k-means算法能较好的对指纹库进行优化.实验数据分析表明,优化指纹库是有必要的.优化后的指纹库在干扰较小时,能明显提高定位误差在1 m之内的概率;在干扰较大时,可以同样使定位误差在2 m之内的概率得到明显提高.因此可得出结论,与未优化的指纹库相比,优化后的指纹库可以显著提高定位精度.

[1]Want R,Hopper A,Falcao V,et al.The Active Badge Location System[J].ACM Transactions on Information Systems,1992,10(1):91-102.

[2]Ward A,Jones A,Hopper A.A New Location Technique for the Active Office[J].IEEE Personal Communications,1997,4(5):42-47.

[3]Priyantha N B.The Cricket Indoor Location System[D].Cambridge:Massachusetts Institute of Technology,2005.

[4]Laoudias C,Constantinou G,Constantinides M,et al.The Airplace Indoor Positioning Platform for Android Smartphones[C]//Proceedings of the IEEE 13th International Conference on Mobile Data Management.Piscataway: IEEE,2012:312-315.

[5]Yang Z,Wu C,Liu Y.Locating in Fingerprint Space:Wireless Indoor Localization with Little Human Intervention [C]//Proceedings of the 18th Annual International Conference on Mobile Computing and Networking.New York: ACM,2012:269-280.

[6]Ozdenizci B,Ok K,Coskun V,et al.Development of an Indoor Navigation System Using NFC Technology[C]// Proceedings of the 4th International Conference on Information and Computing.Piscataway:IEEE,2011:11-14.

[7]Yang Z,Zhou Z,Liu Y.From RSSI to CSI:Indoor Localization via Channel Response[J].ACM Computing Surveys,2013,46(2):25.

[8]Liu H,Gan Y,Yang J,et al.Push the Limit of WiFi Based Localization for Smartphones[C]//Proceedings of the 18th Annual International Conference on Mobile Computing and Networking.New York:ACM,2012:305-316.

[9]Fang S H,Lin T N,Lee K C.A Novel Algorithm for Multipath Fingerprinting in Indoor WLAN Environments[J].IEEE Transactions on Wireless Communications,2008,7(9):3579-3588.

[10]Bai S,Wu T.Analysis of k-Means Algorithm on Fingerprint Based Indoor Localization System[C]//Proceedings of the IEEE 5th International Symposium on Microwave,Antenna,Propagation and EMC Technologies for Wireless Communications.Piscataway:IEEE,2013:44-48.

[11]Fang S H,Lin T N.Principal Component Localization in Indoor WLAN Environments[J].IEEE Transactions on Mobile Computing,2012,11(1):100-110.

[12]Fang S H,Wang C H.A Dynamic Hybrid Projection Approach for Improved Wi-Fi Location Fingerprinting[J].IEEE Transactions on Vehicular Technology,2011,60(3):1037-1044.

[13]Wagstaff K,Cardie C,Rogers S,et al.Constrained K-Means Clustering with Background Knowledge[C]//Proceedings of the Eighteenth International Conference on Machine Learning.Williamstown:IMLS,2001:577-584.

（编辑:王 瑞)

Fingerprint optimization method for the indoor localization system

MA Xindi,MA Jianfeng,GAO Sheng
(School of Computer Science and Technology,Xidian Univ.,Xi’an 710071,China)

The accuracy of the indoor localization is influenced directly by the quality of the fingerprint. But the indoor localization algorithms in existence are almost conducted based on the original fingerprint which is not optimized.The k-means is introduced to optimize the fingerprint in this paper.And deleting the collected bad-points through the theory of cluster could make the fingerprint more accurate for the indoor localization algorithm.Compared with the indoor localization systems in existence,the result of experiments shows that the optimized fingerprint can increase the accurate of indoor localization with a higher probability.

smartphone;k-means method;optimize fingerprint;delete bad-point

TP302.7

A

1001-2400（2015)06-0081-07

10.3969/j.issn.1001-2400.2015.06.015

2014-07-10

时间:2015-03-13

国家自然基金委员会-广东联合基金重点基金资助项目（U1135002);国家自然科学基金资助项目（61303221,61272398);中央高校基本科研业务费专项资金资助项目（JY10000903001)

马鑫迪（1989-),男,西安电子科技大学博士研究生,E-mail:xdma1989@163.com.

http://www.cnki.net/kcms/detail/61.1076.TN.20150313.1719.015.html