＊基于相似指纹特征的室内定位机制研究

陈永乐，于 丹，王 泽（太原理工大学计算机科学与技术学院，太原030024）



＊基于相似指纹特征的室内定位机制研究

陈永乐，于 丹，王 泽
（太原理工大学计算机科学与技术学院，太原030024）

摘 要：针对指纹定位结果中存在较大定位误差问题，分析了离线相似指纹对应采集点的分布特征，发现存在部分相似指纹对应的采集点位置距离较远的特征，这导致了较大定位误差的出现。据此提出了一种基于阈值的Dynamic－kNN的算法来实现指纹的匹配，并进一步针对相似指纹的聚类特征设计了基于K－Means的聚类优化算法，从而大大减少了定位结果中较大误差的存在。实验表明，该算法能够将最大定位误差缩小到5m以内，同时4m以上的较大定位误差所占比例也明显下降。本研究与其他算法相比，在定位性能和算法开销上具有明显优势。

关键词：WiFi信号；信号强度；指纹定位

（2014124）；太原理工大学校青年基金（2013Z060）；太原理工大学校基金项目（2014TD054）

室内定位是提供室内位置服务的关键支撑，由于GPS在室内的不可用性和蜂窝定位的粗粒度特征，使得室内定位亟需寻求细粒度的高效定位方法。指纹定位是指利用室内不同位置的无线信号特征存在的唯一性，将位置和其对应的无线信号特征进行关联，从而将无线信号特征形象的称为指纹，并将位置作为需要识别的目标进行匹配的过程。由于公共环境中无线基础设施的普及，尤其是公共WiFi网络的覆盖，使得指纹定位能够依赖于现有设施完成部署。指纹定位通常分为离线采集和在线匹配两个步骤：离线采集是指通过对定位区域的所有位置进行信号强度指纹的采集，构建无线信号指纹数据库；在线匹配是指在实时定位阶段能够将现场采集的信号指纹与数据库中的指纹进行匹配，选择最优匹配指纹对应的位置为定位结果。因此，只要无线WiFi网络覆盖的地方就很容易实现指纹定位算法，这使得指纹定位算法已经成为室内定位的理想之选。

定位精度是室内定位算法追求的主要指标之一，已有许多研究者设计各种在线匹配算法来提高定位的精度，从确定性kNN算法［1］到概率性贝叶斯估计算法［2］和顺序蒙特卡罗算法［3］，再到支持向量机［4］以及神经网络算法均先后被用于提高指纹定位算法的定位精度。目前多数指纹定位算法基本能够在室内达到2m左右的中位数误差，但是总存在少量6m以上的较大定位误差，这是定位精度提高的一个关键瓶颈［5］。同时，人身体使WiFi信号产生的多径和阴影将导致信号强度严重衰减［7］。本文通过实验分析了人员不同朝向和手持设备不同位置对WiFi指纹定位的影响，发现身体遮挡产生的多径和阴影导致指纹出现了8m左右的更大定位误差，说明多径和阴影会进一步加剧较大定位误差的存在，目前很少有研究考虑降低这些较大定位误差。文献［5］提出了一种基于手机辅助的Peer Assisted算法，利用手机上自带的麦克风和扬声器测量手机与手机之间的距离，根据手机用户之间的距离关系来约束指纹定位的结果，从而防止出现较大的定位误差。尽管该方法能够避免较大定位误差的产生，但是该方法需要采用额外的声音测距算法，会大幅增加定位服务产生的能量消耗，更重要的是声音测距在多数室内环境中，尤其是嘈杂的公共环境中受到严重制约而不能使用。

针对存在的较大定位误差问题，对离线相似指纹的位置分布进行了分析，发现离线指纹库中的指纹之间存在“相似指纹对应位置却相距较远”的特征，这是导致出现较大定位误差的根本原因。而多径和阴影也会进一步加剧这一问题的产生，从而导致更多的较大定位误差，为此，设计了一种基于阈值的Dynamic－kNN算法来实现指纹的匹配，并对匹配出的候选指纹设计了K－Means的聚类优化算法以实现细粒度的精确指纹定位。

1　无线信号指纹粒度与定位性能分析

1．1 人身遮挡对指纹粒度和定位性能的影响

为了深入分析WiFi指纹定位的性能，针对人员朝向和手持手机的位置两方面的遮挡因素设计了两组实验，分别与无人为遮挡干扰的实验结果作对比。由于智能手机中基于位置应用的广泛普及，采用了GALAXY Note3手机作为实验测量平台，本实验集中考虑人为遮挡产生的多径和阴影对指纹信号的影响，暂不考虑设备差异性带来的指纹误差。

实验环境如图1所示，在38m×26m的实验室开放空间，由于办公桌椅覆盖的地方无人经过，本实验选择在走廊等人员可移动区域中的76个位置进行WiFi指纹采集，共有8个AP被部署用于信号测量，部署位置如图1中星号所示。分别手持被定位手机的底部和上部位置，在每个采集点，按照用户朝向0°，90°，180°和270°这4个方向进行采集，每个朝向采集15组信号强度取平均值，这样在离线指纹库中生成指纹记录共608条，其中每条指纹记录可描述为

f＝〈rssi1，rssi2，…，rssin〉，

rssii的值为信号强度的平均值，n值为AP的数量。

图1　实验环境中指纹采集点分布图

通常情况下，无线信号强度的测量随时间变化也会有一定的误差［6］，假设这一测量误差符合零均值正态分布，方差为ε。指纹的匹配采用指纹向量的欧氏距离测量相似性，那么n个AP所得的指纹欧式距离的最大误差能够通过如下公式来计算：

只有当两个指纹向量的距离大于emax时，才会有明显的指纹相异性，这种指纹的相异性在本文中被称为指纹粒度。由于误差ε是信号测量的固有误差，因此称emax为最大固有指纹粒度误差。

图2　朝向和手持位置对指纹的影响

为分析人员朝向和手持手机位置对指纹粒度和定位精度的影响，对采集的608条指纹记录分朝向和手持位置进行了4组实验，如图2所示。其中分朝向实验采用手持底部条件下的两组数据：分别是0°朝向采集的76条指纹自身之间的指纹粒度，0°朝向与90°朝向采集的76条指纹之间的指纹粒度；分手持位置采用180°朝向条件下的两组数据：分别是手持底部采集76条指纹自身之间的指纹粒度，手持底部与上部采集76条指纹之间的指纹粒度。

图2－a和2－b给出了分朝向和手持位置的指纹粒度累积分布。假设通常信号测量误差的方差为5db［6］，按照式（1）计算得到最大固有指纹粒度误差为28db。图2－a中指纹粒度小于28dB的指纹（即相似指纹）所占比例分别为13%和19%，其中不同朝向间比同朝向间指纹的相似比例更大。图2－b中指纹粒度小于28dB的指纹所占比例分别为18% 和23%，其中手持底部与上部之间比手持底部自身的相似比更大，并且手持位置比朝向对相似指纹比例的影响更大，这主要由于手比身体更靠近手机所致。图2－c和2－d在室内随机抽选了30个采样位置，并在30个位置分别定位5次对指纹定位的精度进行分朝向和手持位置的比较，发现指纹粒度比较中的相似指纹所占比例越高对应的定位精度越低，而且无论采用何种方式比较，定位结果中总是存在少量误差，甚至超过6～8m。这些较大的误差是造成定位精度下降的主要因素，为了分析较大误差出现的原因，对指纹库中的相似指纹做了进一步分析。

1．2 较大定位误差的原因分析

图3　四个采集点的相似指纹分布

为了分析出现较大误差的原因，比较了分朝向影响下相似指纹的位置分布。将相似指纹按照指纹对应的采集点位置进行分组显示，为76个采集点分朝向选择相似指纹以及确定相似指纹对应的位置。指纹相似的判定阈值为最大固有指纹粒度误差。如图3所示，分别对73号采集点的0°朝向、42号采集点的90°朝向、51号采集点的270°朝向以及59号节点的180°朝向做了相似指纹的位置分布显示。其中与42号采集点90°朝向的指纹相似的位置如图中实心圆点所示，这些位置除了多数与42号采集点位置相近外，还有少数与42号采集点的位置距离较远，这些少量的离群点将会导致相似指纹对应的位置较远，这势必造成指纹定位结果出现较大误差。此外，具有相似指纹的采集点位置之间具有明显的区域成簇特征，即多数相似指纹的采集位置相近。从其它采集点的相似指纹位置分布来看，也具有类似特征。因此，指纹库中存在的少数具有相似指纹对应的离群采集点是造成指纹定位出现较大误差的根源。针对相似指纹对应位置的簇分布特征，本文尝试通过聚类优化方法来解决较大定位误差问题。

2　基于相似指纹特征的聚类优化

目前，许多研究聚焦于设计在线匹配算法和滤波优化算法来提高指纹定位的精度。其中对定位结果的滤波优化，能够根据前期的定位结果进行平滑拟合，防止出现较大的定位偏差，但是如果定位结果经常存在较大定位误差，即使对结果进行滤波拟合，也无法从根本上提高定位系统的精度。因此，对指纹定位结果的优化预处理，能够从数据质量上提高单次定位的性能。

kNN算法是一种常用的分类算法，能够从离线采集的指纹数据库中选择与实时采集到的指纹向量距离最近的k个指纹向量，将这k个指纹向量对应位置的质心位置作为指纹定位的结果。通常，kNN算法也包括2个步骤。第一步是计算离线指纹库中与在线指纹距离最邻近的k条指纹对应的采集点，其中k值的选择将直接关系到最终定位的精度。第二步需要通过k各候选的采集点位置利用质心算法来估计待测指纹对应的位置，针对这2个步骤，分别给出了相应的解决策略。

2．1 设定最邻近k值

kNN算法是通常采用指纹向量之间的欧式距离来衡量指纹邻接，其中指纹向量的维数为环境中AP的个数。在kNN算法中最邻近的选择准确性依赖于k值的选择，如果k值选择太小，那么被选择的最邻近采集点就会很少，假如采集点的选择存在误差，会使得出现较大定位误差。如果k值选择过大，不仅增加算法执行开销，更容易引入许多距离较远采集点，这也会导致定位误差的增大。本文通过优化设定阈值来保证kNN算法的性能，通过阈值的设定来保证既不会有太多物理距离相对较远的采集点被选择，也要保证尽可能多的采集点被选择。因此，采用指纹误差的临界值（即最大固有指纹粒度误差emax）作为kNN最邻近的判定阈值，在固有误差导致的指纹距离误差以内的指纹均被认为是与待测指纹是临近的，k值的选择将不再固定，会根据阈值的设定而动态变化，被称为Dynamic－kNN算法。该方法能够防止实际距离较远的采集点被选择为最邻近所导致的定位性能下降。

2．2 估计最佳位置

Dynamic－kNN算法将所有的最邻近采集点选择完之后，需要利用质心算法求得目标的位置坐标。以二维空间为例，质心算法的估计位置坐标求解公式如下：

式中，（X1，Y1），…，（Xk，Yk）为k个被选择采集点的位置坐标。

该算法操作方便，计算简单，然而无法解决指纹相似而实际距离较远的采集点带来的定位误差。尽管有些现有工作也提出基于加权的质心算法来改进指纹算法的定位估计，然而都是从指纹欧式距离远近的角度来考虑，根据指纹距离的大小来估计位置的匹配准确程度，这同样无法解决较远距离采集点存在相似指纹问题。

根据前面的实验结论，已经发现相似指纹的采集点存在实际距离较远的可能，但是距离较近的明显占多数，且具有显著的簇特征。因此设计了一种簇中心选择策略来估计最佳定位位置。首先，计算k个候选采集点间的平均距离Td，公式如下：然后，以平均距离Td作为候选采集点的分簇判定阈值，并利用K－Means聚类算法选择簇的中心采集点位置作为定位结果。其主要步骤如下：

1）所有k个候选采集点为一个初始簇，计算其质心作为簇的中心点；

2）计算每个采集点到簇中心点的欧式距离，将欧式距离小于簇判定阈值Td的采集点添加到簇中；

3）重新计算质心作为最终定位结果。

该算法通过分簇判定阈值的设定，避免了KMeans聚类算法的多次迭代，大幅提高了算法的执行效率。同时该算法能够消除指纹近似而实际距离较远的异常采集点，最终以所有最邻近采集点的分布最密集的质心位置为圆心，以簇判定阈值为半径形成一个圆形的簇，圆心位置就是定位的结果。这样，距离较远的采集点变为孤立点也均被剔除出簇，

这将进一步提高定位的精度。

3　实验验证与结果

3．1 实验设计

为了验证算法的有效性，本文仍采用图1中38m×26m开放办公室场景和对应的608条指纹记录进行实验验证。首先分析指纹距离阈值设定对k值的影响，其次分析了分簇阈值设定对定位结果的影响，最后，从整体上衡量本文提出的DynamickNN算法对指纹定位性能的提高程度。

3．2 性能评价

本实验仍以信号测量误差的方差为5db为参考标准，计算得到最大固有指纹粒度误差为28db，如图4所示。据此计算在20个位置进行了10次指纹测量和kNN定位后，综合统计k值的变化，发现k均值呈现明显的起伏，这说明不同位置的k邻近指纹数量不尽相同，这是因为有些位置处于室内边角处，周边没有相邻的指纹采集点，导致相似指纹偏少，而居于室内中间位置的采集点周围都可以采集指纹，其相似指纹偏多，从而出现各采集位置的k值明显不同。

图4　相似指纹阈值对k值的影响

为了本文优化算法的整体性能，以手持手机底部0°朝向和以手持手机上部90°朝向的混合指纹为基础原数据进行定位精度的分析，以分析不同朝向及不同手持位置下指纹定位精度的性能变化，如图5所示。聚类优化后（Dynamic－kNN，K－Means）的中位数误差从原数据的大于2m降低到2m以内，90%以内误差也由原数据的4m下降到3m左右。尤其是最大误差有了明显的降低，原数据的最大误差达到8m左右，而Dynamic－kNN算法执行后最大误差接近6m，进一步执行1－Means分簇后获得5m以内的最大误差，这与文献［7］中2个手机辅助的Peer Assisted算法所达到的4．3m最大定位误差性能接近。同时较大误差所占的比例也出现明显

图5　动态聚类优化指纹定位算法性能

下降，原数据4m以上的定位误差占到近10%，而Dynamic－kNN后比例下降到6%，K－Means算法进

一步使该比例下降到2%以内。

4　结束语

指纹定位因其不依赖额外部署已经得到广泛研究，本文对离线相似指纹的位置分布进行分析，发现少量相似指纹对应采集点位置较远是导致定位结果中出现较大定位误差的主要原因，而多径和阴影也会进一步加剧较大误差的出现。为此，本文设计了一种基于阈值的Dynamic－kNN算法来进行匹配，对匹配的采集点进行K－Means的聚类优化算法以实现细粒度指纹定位。实验结果表明本文聚类优化算法能够大幅减少较大定位误差的出现。

参考文献：

［1］ Prasithsangaree P，Krishnamurthy P，Chrysanthis P K．On indoor position location with wireless LANs［C］∥Proceedings of the 2002IEEE Personal，Indoor and Mobile Radio Communications，2002，2：720－724．

［2］ King T，Kopf S，Haenselmann T，et al．COMPASS：A probabilistic indoor positioning system based on 802．11and digital compasses［C］∥Proceedings of the 2006IEEE WiNTECH，LosAngeles，CA，USA，2006：34－40．

［3］ Morelli C，Nicoli M，Rampa V，et al．Particle filters for RSS－based localization in wireless sensor networks：An experimental study［C］∥Proceedings of the 2006IEEE ICASSP，Washington DC，USA，2006：957－960．

［4］ Lee C W，Lin T N，Fang S H，et al．A novel clustering－based approach of indoor location fingerprinting［C］∥Proceedings of the 2013IEEE Personal Indoor and Mobile Radio Communications（PIMRC），2013：3191－3196．

［5］ 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，2012：305－316．

［6］ 陈永乐，朱红松，孙利民．一种抗多径和阴影的视距指纹定位算法［J］．计算机研究与发展，2013（3）：524－531．

（编辑：刘笑达）

［7］ Bahland P，Padmanabhan V N．RADAR：An in－building RF－based user Location and tracking system［C］∥Proceedings of the 2000IEEE INFOCOM，Piscataway，NJ，USA，2000：775－784．

Indoor Positioning Mechanism Research Based on Similar Fingerprint Characteristics

CHEN Yongle，YU Dan，WANG Ze
（College of Computer Science and Technology，Taiyuan University of Technology，Taiyuan030024，China）

Abstract：For big errors of fingerprint positioning，we analyzed corresponding position distribution of off－line similar fingerprints and found the long distance of sampling positions of some similar fingerprints．Accordingly，we proposed a Dynamic kNN algorithm to achieve the fingerprint matching based on a setting threshold．Moreover，a clustering algorithm on K Means was proposed with the clustering characteristics of similar fingerprints，which greatly reduced larger errors in the positioning results．Experiment results show that the algorithm can reduce the maximum positioning errors to less than 5m．Meanwhile，the proportion of the large positioning errors greater than 4malso decreases，which has clear advantages in the positioning performance and overhead in comparison with other algorithms．

Key words：WiFi signal；signal strength；fingerprint positioning

作者简介：陈永乐（1983－），男，山东潍坊人，博士，讲师，主要从事无线传感器网络研究，（Tel）13994269473

基金项目：国家自然科学基金项目：基于移动感知的室内指纹定位可通用性问题研究（61401300）；山西省教育厅科技创新基金

收稿日期：＊2015－01－19

文章编号：1007－9432（2015）03－0336－05

DOI：10．16355／j．cnki．issn1007－9432tyut．2015．03．018

文献标识码：A

中图分类号：TP393