基于零先验知识的室内指纹定位优化算法

于　丹，王　泽，陈永乐

(太原理工大学 计算机科学与技术学院，太原 030024)



基于零先验知识的室内指纹定位优化算法

于丹，王泽，陈永乐

(太原理工大学 计算机科学与技术学院，太原 030024)

摘要:针对众包方法构建指纹库数据质量低和指纹模糊相似性等问题,提出了一种基于SLAM技术的指纹数据质量优化和指纹唯一性增强的算法。利用ICNN算法完成数据关联优化,并在指纹向量中加入可信度指标来优化指纹更新过程；随后针对指纹模糊相似性设计了基于高斯插值的指纹唯一性增强优化算法,保证了指纹数据质量,从本质上提高了指纹定位的性能。实验表明，该算法能够将指纹定位的中位数误差从原始指纹的3 m提高到2 m,最大定位误差从8 m左右下降到4 m以内。

关键词:WiFi信号强度；众包方法；指纹定位

人们日常生活中,绝大多数的时间都停留在室内环境中,因此,室内位置服务在商业应用、医疗卫生和智能家居等众多领域有着广泛的需求。然而,每个提供定位服务的室内环境通常需要单独部署一套室内定位设备才能提供位置服务,重复的部署开销限制了室内定位的大规模推广应用。依赖于现有基础设施的室内指纹定位，为室内定位技术迈向商用提供了新的解决思路。尤其是随着WiFi热点在公共室内环境中的普及,使得基于WiFi信号的指纹定位得到广泛的研究。但是,指纹定位需要对环境中WiFi信号进行先期采样来构建庞大指纹库,此工作费时耗力,非人力所能及。目前,基于众包思想(Crowdsourcing)的零先验知识条件下的指纹库构建方法成为新的突破技术[1-2],即用户在使用定位服务的同时也为系统完成环境信号的采样工作,避免人工先期采样的高额开销,但是引入了定位精度下降的新问题。

指纹定位分为离线采集和在线匹配两个阶段。在离线采集阶段,基于零先验知识的指纹库构建方法主要分为两类：一类是基于信号衰减模型构建指纹库[3-4]，但是室内环境的复杂性和时变特性使建模估计的指纹数据极不准确,定位的精度也严重偏低；另一类是基于众包思想构建指纹库，针对工作繁重的指纹库构建,通过大型的商场、机场和超市等环境中每个手机用户的无意识参与来共同完成指纹库的构建。本文正是基于此思想,但是难点在于如何将指纹与相应的物理位置进行关联[2],而且这两类指纹库构建方法均以室内地图已知为前提。近年来，有些研究者提出利用机器人领域的即时定位与构图(Simultaneous Localization and Mapping,SLAM)技术来同时构建指纹库和室内地图；但是室内人员的移动更具复杂性和不确定性,致使指纹库采集数据的质量明显下降。其中文献[5]和文献[6]分别提出在人脚的部位安装惯性传感器测量人的移动,以此绘制室内地图和完成定位；但是脚部安装惯性传感器的方法会干扰人们的日常生活。尽管鉴于智能手机的零先验知识条件下的即时定位与构图技术得到了一定的研究[7],但是目前仍缺少针对离线构建指纹库数据质量的优化研究。

在线匹配方面,分为确定性和概率性算法两类，其中,确定性策略是通过计算采集信号的平均值,根据指纹之间的相似性距离进行匹配(如KNN算法、加权KNN算法等)。受室内环境变化因素的影响,信号的波动范围较大,平均值往往无法准确描述信号变化。概率性策略能够在每个采集点保存信号的分布,然后通过贝叶斯估计、顺序蒙特卡罗等概率方法获得较准确的位置估计,定位精度有所改善,然而在采样信号波动较大时,概率性匹配精度反而低于确定性匹配精度。通过现有无线射频信号特征研究(以WiFi为例)发现，室内指纹信号存在模糊相似性问题,即相近的位置存在相似指纹,距离较远的位置也可能存在相似指纹,这表明了指纹库中指纹本身不具有唯一性,致使现有的指纹定位算法均具有较大的误差下限[8],这将给指纹定位性能带来极大挑战。

本文针对零先验知识条件下指纹定位精度面临的挑战,提出了一种面向多用户协同感知的指纹定位性能优化机制,主要从多用户协同感知构建指纹库的质量优化和指纹信号唯一性特征增强两个方面进行了定位精度的优化改进,实验结果表明本文提出的基于零先验知识条件下的指纹定位的中位数误差从原始指纹的3 m提高到2 m,最大定位误差从8 m左右下降到4 m以内,指纹定位性能得到明显改善。

1零先验知识下指纹定位优化框架

综合考虑了离线采集和在线匹配两个过程中的指纹信号质量问题。首先，对零先验知识条件下的基于SLAM方法的指纹库构建数据质量进行优化,保障指纹库数据的准确性；同时,在离线阶段对采集的指纹间的粒度进行插值扩展,提高指纹库中指纹信号的唯一性特征。优化算法的总体框架如图1所示。针对智能手机的WiFi信号和陀螺仪等传感器感知信息,利用SLAM技术进行指纹库和地图的同时构建,并通过数据关联和指纹更新等策略对指纹库数据质量进行优化。随后,对构建指纹库中的指纹数据进行高斯插值,保障指纹在线匹配的唯一性,从离线采集和在线匹配两个阶段保障了指纹质量,从而有效的提高定位精度。

图1　零先验知识下指纹定位优化框架Fig.1　Zero prior knowledge-based fingerprint positioning optimization framework

2基于零先验知识的定位性能优化算法

目前,许多指纹定位性能研究聚焦于设计在线匹配算法和滤波优化算法来提高指纹定位的精度；然而在线匹配算法和对定位结果的滤波优化算法,能够对定位误差进行一定程度的矫正,但是无法从根本上提高定位系统的精度。只有对指纹数据质量进行优化处理,才能做到标本兼治,本文提出从指纹库数据质量和指纹唯一性特征两个方面进行优化,既解决了离线指纹采集质量低的问题,同时也兼顾了在线匹配存在模糊相似性的问题,从而有效提高指纹定位的精度。

2.1众包策略中指纹库数据质量优化算法

传统的众包思想能够提供一种群体无意识感知的解决思路,然而多用户协同产生感知数据也为目标的分析处理带来新的难题。在室内多用户无意识的移动情况下,感知数据存在明显的关联特征。例如,用户在同一位置测量的指纹具有相似或重叠特性,据此能够推断用户的重叠轨迹,从而优化已构建的指纹库和室内地图。因此,高效准确的数据关联算法是保证多用户协同感知的前提。为此,本文提出了一种多用户协同感知的指纹库与室内地图同时构建框架,在构建指纹库与室内地图的同时优化数据关联和指纹更新过程。如图2所示,该框架以多用户的无意识协同感知数据为基础,依靠基于图优化理论的平滑SLAM方法,集成了感知数据的聚类优化和去噪处理,通过数据关联优化和指纹更新优化,综合展现了零先验知识条件下对利用众包思想获得的指纹库数据质量进行的优化改进。

图2　多用户协同感知的指纹库与地图同时构建框架Fig.2　Multi-user collaborative sensing SLAM framework

2.1.1数据关联优化

数据关联是指确定不同用户或者同一用户在不同时间获得的观测指纹之间是否存在相似关系,以判断观测值是否源于同一物理位置。它是闭环检测和地图是否需要更新校正的基础,对提高海量室内环境下SLAM方法的准确性有重大意义。在多用户协同感知的条件下,感知数据融合也同样依靠观测指纹之间的数据关联来完成,通过指纹匹配来判断多用户移动轨迹是否存在重叠或者闭环,从而更新移动轨迹的预测,提高地图构建和定位的准确性。常用的数据关联方法有单一兼容最邻近算法(ICNN)、联合兼容分支定界(JCBB)和多假设数据关联法。其中JCBB算法和多假设数据关联算法能够结合观测值的累积和其他先验知识进行较准确的关联匹配,然而对运算和存储具有较高的要求。ICNN算法具有计算量小且支持唯一性增强后指纹测距的马氏距离方法,本文采用传统的ICNN算法来匹配唯一性增强后的指纹。

2.1.2指纹更新优化

多用户协同感知条件下,指纹重叠更加频繁,对地图进行更新校正的同时也应该对指纹库进行更新,以选择更加准确的指纹和位置映射作为新的指纹。在指纹更新过程中,采取在指纹向量中添加一维可信度标量值的方法来描述指纹与位置的准确匹配程度,根据可信度的高低来选择指纹进行更新。主要思路是通过用户协同更新次数(匹配次数)和距离最近的完全可信位置(房间门口等已知位置)的远近来确定可信度,一方面当指纹向量被用户匹配次数越多指纹的可信度越高;另一方面用户指纹匹配时距离最近完全可信位置越远可信度越低。综合以上两方面因素,指纹向量与可信度的形式化描述如下:

(1)

式中：C是指指纹被匹配的次数；B是统计用户距离最近完全可信位置的步数。

在实际环境中,尽管选择较高可信度的指纹进行更新,可能仍无法改变指纹库中数据的不对称性特征。在指纹库中,通常距离较近的位置具有近似指纹,然而也存在少数较远距离的位置具有相似的指纹。这给指纹的数据关联带来了较大的匹配误差,尽管相似指纹之间存在微小的匹配误差,也可能导致两个较远位置的匹配结果。为消除这一问题,进一步在离线指纹库中采用K-Means聚类分簇方法,以保证相似的指纹尽可能分布在较近的位置,消除较远位置的相似指纹。主要思想是根据信号指纹测量的固有误差设定相似指纹的判定标准,并以该标准为半径对指纹进行分簇,同时利用位置间的步数设定远近判断的上限,对相同簇中位置距离较远的近似指纹进行删除,减小指纹库中数据的不对称性。

2.2指纹库中指纹间的唯一性特征增强算法

不同室内空间的环境各异,WiFi信号覆盖情况存在差异,为满足室内指纹定位在不同室内环境中的精确性,需要保障指纹与室内位置的对应关系在整个指纹库中具有唯一性。受环境中基础设施和人员移动的影响,充当指纹的多种信号存在不稳定性,严重降低了指纹库中数据的唯一性。当室内AP分布稀疏时,将会有较多的位置存在指纹相似性。如图3所示,在自由空间Log-Normal衰减模型下,左图中的位置A，B，C和D具有相同信号强度,右图中的位置A和B也具有相同信号强度。在室内环境中将存在许多位置在AP分布稀疏时出现相似指纹。此时,通过哈希、插值和高维映射等方法加大WiFi信号指纹差异性将是增强指纹唯一性的有效途径。

图3　AP稀疏分布情况下的指纹相似问题Fig.3　Fingerprintsimilarityunder the sparse distribution of APs

针对WiFi信号在小范围的自由空间中具有近乎相同的信号强度,但是在室内较大范围空间中,相似信号强度的位置关系更加依赖于室内环境结构。在没有室内建筑结构蓝图的情况下,可以对小范围自由空间信号强度进行插值以增强相近位置测得信号强度的差异性。本文采用高斯权值插值方法,假设某个室内采集的指纹库向量集合为ZWiFi,可将指纹库中的第i个指纹向量描述为:

(2)

式中：wi是插值的权值向量；βi是指从wi中抛除第i个元素的向量,其向量1-范数值为1；[wi]i是指向量wi的第i个元素；ei是除第i个元素外全为零的单位向量。直观上,[wi]j可以作为位置i和位置j对应WiFi指纹之间被插值权值。在没有其他先验条件的前提下,选择如式(3)描述的高斯插值权值作为核函数,该方法也在机器学习领域的相似条件下得到较好的验证。

(3)

式中：l为尺度参数,可测得经验值；|xi-xj|2代表位置i和位置j之间的距离。此时,位置i的指纹向量将被建模为一个高斯分布,WiFi指纹的度量标准变为马氏(Mahalanobis)距离。为了控制高斯分布的计算规模,需设定指纹库的大小,通常依据室内环境(如楼层、房间等)进行子指纹库的划分。

3实验验证与结果

3.1实验设计

为了验证算法的有效性,针对设计算法对指纹库中指纹相似性和信号变化特征的影响效果进行了实验验证。由于智能手机中基于位置应用的广泛普及,采用了GALAXYNote3作为实验测量平台,本实验集中指纹信号自身特性,暂不考虑设备差异性带来的指纹间误差。

实验环境为700m2左右的实验室开放空间,由于办公桌椅覆盖的地方无人经过,本实验选择3位实验人员以右侧电梯口处为开始位置(初始位置指纹可信度为1),在走廊和房间中人员可移动区域中进行自由行走,每两步指纹采样一次,对经过的360个位置进行WiFi指纹的采集,共有10个AP被部署用于信号测量。每个位置采样10次取平均值,这样在离线指纹库中生成指纹记录共360条,其中每条指纹记录描述为f=〈ri,r2,…,rn〉,ri的值为信号强度的平均值,n值为AP的数量。

3.2性能评价

图4　数据关联性能与指纹可信度关系比较Fig.4　Comparisonbetweendata association performance and fingerprint confidence

本实验将对指纹库构建质量优化算法进行评价,分析经过数据关联优化和基于可信度指纹更新后的指纹数据质量情况。由于可信度的计算依赖于匹配次数和距离完全可信位置的步数,其最大数值并非为1 .本实验首先将指纹可信度进行归一化,选择所有统计可信度值最大除所有其他可信度值,楼梯入口的初始位置指纹可信度为1 .如图5所示,发现大多数情况下,指纹可信度越高,ICNN匹配算法的准确率越高。然而存在少量指纹可信度偏高,ICNN匹配准确率低的情景(如图4中的位置点7和9),这是由于可信度还受距离完全可信点的步数的影响。此外,从整体上看,ICNN数据关联的匹配概率均在50%以上,并有少部分位置能够获得100%的匹配准确率。

图5　高斯插值前后指纹间欧氏距离对比Fig.5　Comparison of Euclidean distance between fingerprints by Gauss interpolation

经过SLAM过程数据优化和指纹唯一性增强处理后,对指纹数据进行了定位性能评价实验,对实验环境中的随机30个位置点通过kNN指纹匹配算法进行定位结果测量。如图6所示,发现传统SLAM技术获得的指纹能够获的接近3m的中位数误差,而对指纹数据库中数据质量进行优化后,能够将中位数误差提高到2.3m,高斯插值后的中位数误差更是接近2m,最大定位误差也从传统SLAM技术获得指纹的8m左右下降到4m以内,定位性能获得明显提升。

图6　算法优化后的指纹定位性能Fig.6　Fingerprint positioning performance after algorithmoptimization

4结束语

通过对指纹自身的数据质量进行优化来提高指纹定位的精度,提出了一种基于SLAM技术的指纹数据质量优化和指纹唯一性增强的综合优化算法,能够从本质上解决指纹数据质量低的问题,远远优于传统的依赖于指纹匹配算法提高定位精度的做法,实验结果也进一步验证了本文设计算法的有效性。

参考文献：

[1]WUC,YANGZ,LIUY,etal.WILL:Wirelessindoorlocalizationwithoutsitesurvey[J].IEEETransactionsonParallelandDistributedSystems,2013,24(4):839-848.

[2]RAIA,CHINTALAPUDIKK,PADMANABHANVN,etal.Zee:zero-effortcrowdsourcingforindoorlocalization[C]∥CM,Proceedingsofthe18thAnnualInternationalConferenceonMobileComputingandNetworking.Istanbul,Turkey,2012:293-304.

[3]VARSHAVSKYA,PANKRATOVD,KRUMMJ,etal.Calibree:calibration-freelocalizationusingrelativedistanceestimations[M]∥PervasiveComputing.BerlinHeidelberg:Springer,2008:146-161.

[4]NARZULLAEVA,PARKY,JUNGH.AccuratesignalstrengthpredictionbasedpositioningforindoorWLANsystems[C]∥IEEE,ProceedingsofPosition,LocationandNavigationSymposium(PLANS),Monterey,California,2008:685-688.

[5]ANGERMANNM,ROBERTSONP.Footslam:pedestriansimultaneouslocalizationandmappingwithoutexteroceptivesensors-hitchhikingonhumanperceptionandcognition[J].ProceedingsoftheIEEE,2012,100(SpecialCentennialIssue):1840-1848.

[6]BRUNOL,ROBERTSONP.Wislam:improvingfootslamwithwifi[C]∥IEEE,InternationalConferenceonIndoorPositioningandIndoorNavigation(IPIN),Guimaraes,Portugal,2011:1-10.

[7]FARAGHERRM,SARMOC,NEWMANM.OpportunisticradioSLAMforindoornavigationusingsmartphonesensors[C]∥IEEE,PositionLocationandNavigationSymposium(PLANS).MyrtleBeach,SouthCarolina,2012:120-128.

[8]CHENY,LIUW,XIONGY,etal.Afuzzysimilarityeliminationalgorithmforindoorfingerprintpositioning[J].InternationalJournalofDistributedSensorNetworks,2015,501:753191.

[9]陈永乐,朱红松,孙利民.一种抗多径和阴影的视距指纹定位算法[J].计算机研究与发展,2015,50(3):524-531.

(编辑：刘笑达)

Zero Prior Knowledge-based Indoor Fingerprint Positioning Optimization Algorithm

YU Dan,WANG Ze,CHEN Yongle

(CollegeofComputerScienceandTechnology,TaiyuanUniversityofTechnology,Taiyuan030024，China)

Abstract:This paper proposes an algorithm based on fingerprint data quality optimization and fingerprint uniqueness enhancement, focusing on the low quality of fingerprint database and fingerprint fuzzy similarity problem. It utilizes the ICNN algorithm to optimize data association, and adds a confidence value in the fingerprint vector to optimize the fingerprint updating process, then designs an uniqueness enhancement algorithm based on Gaussian for fingerprint fuzzy similarity, which guarantees the data quality of fingerprint,and essentially improves the performance of fingerprint positioning. Experiments show that the proposed algorithm can reduce the median error of fingerprint positioning from 3 m to 2 m,and the maximum positioning error is reduced from 8 m to 4 m.

Key words:WiFi signal strength; crowdsourcing; fingerprint positioning

文章编号:1007-9432(2016)02-0195-05

*收稿日期：2015-11-20

基金项目：国家自然科学基金资助项目：基于移动感知的室内指纹定位可通用性问题研究(61401300)；山西省教育厅科技创新基金资助项目(2014124)；太原理工大学校青年基金资助项目(2013Z060)；太原理工大学校团队基金资助项目(2014TD054)

作者简介：于丹(1983-)，女，太原人，硕士生，主要从事无线传感器网络研究，(E-mail)yudan@tyut.edu.cn通讯作者：陈永乐，副教授，硕士生导师，主要从事无线传感器网络研究，(E-mail)chenyongle@tyut.edu.cn

中图分类号:TP393

文献标识码:A

DOI：10.16355/j.cnki.issn1007-9432tyut.2016.02.014