复杂环境下基于RSSI 指纹匹配的室内定位改进算法

周骁健，王运锋

（四川大学计算机学院，成都610065）

0 引言

随着无线通讯技术的发展，越来越多的人开始关注室内外环境中移动目标的追踪定位。就室外环境而言，全球卫星导航系统（Global Navigation Satellite System，GNSS）为用户提供精确的位置服务。但由于卫星信号无法穿透障碍物，使得室内定位成为另一个研究方向。

Wi-Fi 网络的广泛普及，使得基于Wi-Fi 的室内定位技术，目前应用最为广泛。

相较于空旷无遮挡的室内环境，密集的人员流动和复杂的装修布局，会使得定位结果出现较大的误差。本文针对复杂的室内环境，对定位算法进行了改进，并以实验证明了改进算法的有效性。

1 主流算法与局限性

1.1 主流算法

目前主流的基于RSSI 的定位算法有两种：①基于RSSI 测距模型的位置估计；②基于RSSI 指纹库匹配的位置估计。

1.2 算法局限性与选择

基于RSSI 测距模型的定位算法，受RSSI 测量误差影响，实际距离与理论测算值存在较大偏差。由于这种方法在交点定位时，完全依赖距离计算结果，因此在复杂实验环境下，定位交点不确定性非常大。

传统基于RSSI 指纹匹配的定位算法，在人员流动、物品遮挡和同频干扰等多种因素影响下，使得实时报告值的随机性误差明显增大且不可忽略，如何提高实时数据与指纹库的匹配一致性，是该类算法的关键。

本文实验采用了一种改进后的指纹匹配算法。

2 实验算法改进

2.1 指纹数据采集改进

本文在实验过程中，发现并验证了采集点的垂直高度对数据采集准确性的影响。当实际定位的垂直高度与前期采集的高度不一致时，会因为空间遮挡存在较大差异，直接影响数据质量与匹配的一致性。

2.2 指纹库噪点滤除

一般而言，接入设备（Access Point，AP）采集到的RSSI 值是一组离散数据，符合正态分布，其概率密度函数为：

对大量离散数据进行高斯滤波，可以减小其中的奇异值对采集结果整体的影响。

本文在数据采集时发现，指纹数据的质量，还可能受到发射与采集设备性能的影响。实验现象为：在某一段时间内，采集设备的报告值普遍异常，且偏离趋势与信号在该传播路径上的衰减趋势不符。实验对比了两款不同采集设备：小辣椒-20150718 和华为CAZAL10，均有这种现象发生，此时高斯滤波修正效果不明显。

针对这种指纹库的噪点，本文改进了基于邻域均值的滤波方法，在考虑到各分区的相对独立性后，只在各分区内，采用线性插值进行噪点滤除，并不遍历整个指纹库。后续实验结果，验证了插值修正对定位准确性的改进效果。

2.3 定位算法改进

本文在定位阶段，从提高定位准确性与减小匹配计算量的角度出发，改进的整体思路为：先分区，后定位。

分区的思想基于K-means 聚类算法，即每一个区域都是一个独立的聚类中心，且质心的各维AP，相对强弱特征唯一。当待定位设备进入时，分配欧氏距离最近的聚类中心，实现分类。

分类完成后，在局部区域内，进一步实现准确定位。

2.3.1 算法流程

算法流程如图1。

图1 算法流程

2.3.2 具体步骤

（1）确定所有聚类中心的质心，即该区域内所有采集点的加权平均：

其中：n 表示划分的区域数。以第i 个区域为例，其质心的特征量组为：

其中，m 表示区域特征量组的维度，即需要计算m个接入设备（Access Point，AP）的特征量。

以该区域第k 个AP 为例，其加权平均值为：

其中，q 表示该区域共有q 个参考节点（Reference Point，RP）。

（2）对实际报告值做滤波修正。

对比两种不同的限幅滤波算法，方法一：用前一周期的报告值滤波；方法二：用前期全部值的均值滤波。文本在后续，以实验结果作为选择依据，并探讨了可能的原因。

（3）对步骤（2）修正后的报告值进行区域分类。

（4）局部分区实现准确定位。

采用加权K 值最近邻（WKNN）算法进行定位，对加权方法做了对比实验的选择，并提出了方法中的参数获取的改进。假设匹配结果满足条件的RP 个数为K’，最终定位结果取决于这K’个RP 的加权平均，具体坐标为：

公式（5）中，关于权值ωi的算法选择，本文对比试验了两种主要方法：

方法一：基于指纹库的方差加权。

方差δi越大，认为该参考节点（RP）的信号波动越大，权值应当越小。加权公式：

其中：

方法二：基于指纹库的欧氏距离加权。

对于区域内每一维度的AP，与实际报告值欧氏距离越近的AP，权值应该越大。基于此思想，引入带欧氏距离di的加权公式：

其中，c 为常数。公式（8）中：

可知：

通常ωi的公式为

引入常数c 的原因在于，当某一AP 的报告值与指纹数据相同时，di值为0，此时使用加权会使该维度权值无限大。后续实验讨论了c 在特定环境下的适应性取值，并通过多个定位结果的拟合曲线，确定了本实验环境下，常数c 的最佳值。

3 实验设计与结果分析

3.1 本文实验环境及设备

实验环境为6m×8m 写字楼办公室，室内人员流动性较大，桌椅布局密集，房间隔断墙材料不统一。另外写字楼内其他Wi-Fi 信号杂多。具体情况见图2。

图2 实验环境

路由器位置为Wi-Fi 信号标识处。

根据算法描述，实验区域分为四个区块，即公式（2）中n 为4；

接下来将定位区域网格化，共确定36 个参考节点（Reference Point，RP）。每个RP 的接入设备（Access Point，AP）为3 个，即公式（2）中的m 取值为3，ID 分别为：trst、ea38、925a。每一个AP 采集数据5 分钟，共300 组。

区域划分与参考节点部署如图3。

图3 区块划分与参考节点部署

3.2 对比实验及结果

3.2.1 采集点垂直高度与区域内线性插值

指纹库的采集结果如图4（以trst 为例）。

图4 原始指纹库

图5 可以看出，在修正采集高度和分区滤噪后，指纹库的信号强度在各区域内衰减趋势更加明显，更符合实际。

实验数据结果：定位的区域误判率从40.15%降低到25.78%；正确区域内最大距离误差从1.86 米下降至1.30 米，平均误差从1.48 米下降至1.20 米。点迹如图（横纵坐标均为实验室边长，单位：米）。

图5 改进指纹库

图6 指纹库修正前后定位结果对比

实验效果的改进可以证明，在复杂环境指纹库的建立过程中，数据采集的垂直高度和指纹库的噪点，两个因素均不能忽略，前者误差在采集时需要人为规避，而后者则可能与路由器发射功率不稳定性有关。

3.2.2 滤波算法的选择与改进

实验对比的两种滤波方法，定位点迹如图7。

图7 不同滤波算法的定位结果对比

理论上分析，采用上一周期报告值滤波，可以有效克服偶然因素引起的干扰，波动幅度受到约束，结果的离散性应该更小；采用前期均值滤波，滤波效果依赖于前期多组定位结果均值，平均误差应该更小，但需要多周期数据累积，以满足计算需要，实时性牺牲较大。

数据结果如下：

（1）前一周期值滤波

定位误差标准差：0.31 米，平均误差：1.27 米。

（2）均值滤波

定位误差标准差：0.48 米，平均误差：1 米。

符合理论判断。并且，两种滤波都能使区域误判率明显下降。

考虑到室内定位的实时性要求，采用前一周期值滤波更为合适。

3.2.3 加权方法对比

分别使用算法描述中的两种加权方法，对比定位结果，点迹描述如图8。

图8 不同加权办法的定位结果对比

可以看出，基于欧氏距离的加权办法，定位结果更趋于集中，且最大误差也在1 米范围内。

原因在于，基于欧氏距离加权，对数据质量好的维度更加敏感，定位准确性更依赖于滤波后的数据质量；而方差加权对指纹库更加依赖，但前期数据的方差，受采集时的人流、噪声影响较大，与后期实际定位时的相关性更弱。

因此，本实验选择基于欧氏距离加权。

3.2.4 常数c 的确定

不同环境下，常数c 需要适应性调整。通过多次实验，对比定位误差与误差标准差两项指标，选择最佳的c 值。

（1）不同c 的定位误差与拟合曲线如表1。

表1 不同C 值下的定位误差

图9 定位误差拟合曲线

（2）不同c 的误差标准差与拟合曲线如表2。

表2 不同C 值下的误差标准差

图10 误差标准差拟合曲线

从拟合结果可以看出：

当c 过小时，欧氏距离小的训练结果权值较大，而非近邻的训练点会衰减很快。虽然这种情况是我们希望的，但有时候也会使算法对噪声数据变得更加敏感，使得多次定位结果的方差较大；

当c 过大时，加权效果不明显，定位结果更加接近于均值，导致定位误差变大。

综合上述两个结果，c 取值0.53。

3.2.5 各区域测试点定位结果

最后，在整体实验区域内选择4 个测试点，位置如图11。

图11 测试点部署

对比算法改进前后的定位结果，如图12。

图12 测试结果

原始定位结果（上图黄色点）均方根误差（RMSE）为0.94 米，算法改进后定位结果（图12 蓝色点）的RMSE 为0.35 米。可以证明，改进算法对于复杂环境下室内定位精确度的提高，具有实用性。

其中，区域三的改进效果最为明显，原因在于该测试点靠近区域三与区域四的分界点。原始报告值的波动会造成严重的区域误判，而错误区域内的加权结果，相较于真实点的位置，误差更大，因此改进效果更为明显。

4 结语

对于经典的基于指纹库匹配的室内定位算法，本文分别从指纹数据采集与噪点滤除、报告值滤波算法选择和WKNN 算法的权值ωi确定，三方面进行了改进。

首先，在实验设计上，整体采用“先定区，后定位”的思路，减少置信度低的AP 对定位结果的影响，同时能明显减少计算量，提高定位效率的同时，在准确的区域内实现更精确的定位。

其次，定位算法的三个改进方面分别为：①在数据指纹建库过程中，考虑了采集点高度和指纹库噪点两项因素，并通过实验证明其对最终定位结果的影响；②在对实际报告值的修正过程中，综合了定位离散性和实时性的需求，选择基于前一周期值的动态滤波算法；③在加权定位阶段，分析并选择最优的ωi计算方法，并通过多结果的拟合曲线，确定了本实验场景下的最佳常数c。

最后，在各分区随机选择测试点，试验并证明了本文改进的定位算法，在实际场景下的有效性与实用性。