基于改进WKNN 的室内定位算法

王修驹，姚善化

（安徽理工大学 电气与信息工程学院，安徽 淮南 232000）

无线设备和移动通信的快速发展给室内定位服务带来了广泛的发展空间。随着全球定位系统多年的发展与完善，中国北斗导航定位系统的组网应用，室外定位技术已经非常完善并能够解决遇到的各种室外定位问题。室内定位技术相对薄弱，如今的室内定位技术包括Wi-Fi, UWB[1], RFID[2], ZigBee, 蓝牙定位技术，依据定位精度，硬件设备成本各有其优缺点，在这些室内定位技术中，其中基于Wi-Fi 指纹的室内定位技术最易实现。在Wi-Fi 指纹库确立下来之后，应对环境的变化只需进行相应的参数测试便可完成适配。因Wi-Fi 网络传播范围广、定位精度高、成本低等优点广泛应用于室内定位。

Wi-Fi 的室内定位主要有两大方向，即基于测距和指纹。其中基于测距的定位技术又分为到达时间法（TOA）[3]和到达时间差法（TDOA）[4]两种方法，但是考虑到环境空间繁琐的结构及多径效应带来的干扰，基于指纹的方法不需要太多的硬件设施故受到更为广泛的研究。通过接收信号强度指示（RSSI）[5]来替代物理位置，结合位置指纹匹配算法进行定位。左仲亮[6]采用均值滤波对RSSI 进行预处理来减少噪声等因素对定位精度的影响，通过改进加权K 近邻（Weighted K-Nearest Neighbor，WKNN）[7]算法来提升定位效果，冯涛等[8]为了提高基于WKNN[9]的Wi-Fi 指纹定位算法的定位精度，将原始的定位特征不相关的RSSI，通过数学的手段将其相关，提出归一化结合高斯滤波的定位算法大大提高了定位精度。以上算法主要在AP 选择、RSSI 滤波及K 值的选择上做出了改进与创新。但他们基于近邻算法的定位坐标相似度距离度量上多采用欧氏距离的方法，信号特征的距离无法表征真实的物理距离。在复杂的室内环境里信号的传播易受噪声、多径等不确定性因素的影响，对RSSI 进行滤波处理能够减低其波动性，但是会造成RSSI 信号失真。本文在RSSI 信号特征获取上也进行了改进使定位更为精确。

1 算法描述

通常，K 近邻（K-Nearest Neighbor，KNN）算法需要计算当前测量的指纹数据与数据库中的各个指纹数据之间的距离，然后通过排序来确定k 个距离最近的参考点，WKNN 算法通过加权平均估算进一步来精确待定位点的位置。

算法主要涉及3 个方面因素的影响即训练集、距离、相似度的衡量参数k 的大小。实际环境下，采集的信号具有波动性，采集设备、采集时间和环境的变化等因素都会影响到算法的精度与稳定性。所以对于RSSI 的获取与处理需要提前处理，通常的方法是对RSSI 做均值滤波处理，尽可能地减少外界因素的影响。接入点AP 承担Wi-Fi 的覆盖和通信工作，类似于无线蜂窝网络中的基站作用。指纹采集到不同AP 的RSS组成，分为TP 指纹和RP 指纹。TP 指纹在在线阶段的测试获得用以估计TP 的位置。RP 指纹在离线阶段获得用以存储在数据库当中，并与坐标一起来组成离线指纹数据库。

对于AP 点的选择，首先是要测量采集到那些受环境干扰小且其出现的概率高的AP 点，这样会在一定程度上减少外在的定位精度误差。另一方面虽然指纹定位的精度会随着AP 的数量增加而升高，但考虑环境因素和计算量因素，AP 的数量不宜选的太大或太小，综合考虑两方面的因素通过实验得到相应的数值。指纹相似度函数：

式中，erri代表定位坐标误差。

1.1 选取k 值以及它的影响

若选取的k 值很小，则模型复杂且难以实现，环境中的噪声很容易干扰导致算法的功能得不到实现。若选取较大的k 值，即实验区域进行预测，那么输入实例较远的会起同样的作用，从而预测发生错误，k值的增大使得整体模型简单，同样实现不了算法的功能。因此，需要依据实验参数进行k 值的选取，调整超参数来得到一个符合实际情况的结果。

1.2 定位相似距离的度量

指纹定位的关键是测试指纹与参考指纹间信号域距离的表达。而较为常用的表征方法有欧式距离、曼哈顿距离、马氏距离等。在二维坐标系下，假设两点坐标分别为（ x1,y1）和（ x2,y2）。

欧氏距离表达为

曼哈顿距离表达为

采用哪种距离度量方法会获取到不同的定位精度及误差。欧氏距离相较于曼哈顿距离会有这种情况的发生，即当计算得到的欧氏距离相等时，此时欧氏距离作为度量无法衡量出指纹的相似程度，那么此时曼哈顿距离就可以衡量指纹的相似度。曼哈顿距离的优点是具有更高的稳定性且能够使信号的波动较为平缓，这样使得最大程度上减小对于定位误差的增长。应该注意的是曼哈顿距离需要保证特征值差别不可以很大。若通过曼哈顿距离作为距离的度量过大，会导致掩盖其他特征间的邻近关系。因为复杂的环境，采集到的信号会受到多种因素的干扰，一般情况下都会进行指纹特征值归一化处理。信号中的特征优先级应该保持一致，否则会导致定位精度衰减甚至误判。由于本文选取的区域较小且指纹特征值可控，故这些因素可以忽略。

综合考虑到欧式距离在度量指纹相似度上带来的误差，本文通过实验来验证曼哈顿距离度量的优势。

2 Wi-Fi 定位与RSSI 信号特征处理

将定位技术应用到室内环境会存在很大的误差，定位环境的复杂变化会导致定位系统的不稳定运行，所以在进行定位信息收集前需要对周围环境噪声干扰进行处理。本文的做法是在信号滤波之前进行高斯拟合的预处理之后采用KF 滤波对Wi-Fi 定位环境噪声处理，高斯拟合与KF 滤波减少了环境因素带来的误判提高了算法的定位精度和稳定性。

2.1 Wi-Fi 指纹定位模块

首先在实验区域内设置一定数量的AP（AccessPoint, AP）点,并根据实际的计算力和数据存储力选择参考点（Reference Point, RP）。通过软件设备离线采集信号强度（Received Signal Strength, RSS），RSS 一般为-150～0 dBm，本文通过数学的方法将RSS 转化为便于计算的RSSI，依据式(4)得到RP 的位置坐标，通过多次测试计算将坐标数据取均值得到位置坐标，作为指纹数据库的一部分。在线定位时，通过模拟机器人移动来获取测试指纹，通过离线阶段RP 获得的RSSI 与真实物理位置的映射关系对比来得出在线测试阶段的位置坐标，即实时位置坐标( x , y) 。这些是Wi-Fi 指纹定位模块的主要内容。

2.2 RSSI 信号特征处理模块

高斯拟合（GF）作为卡尔曼滤波阶段之前的步骤，其要求获得的RSSI 分布特性符合高斯分布。对其进行总体分布类高斯拟合可以得到较为真实的RSSI 信号特征。其GF 公式如下：

3 算法总体流程

离线阶段和在线阶段两个阶段组成了该算法。图1 为定位算法的整体流程。

离线阶段：指纹数据采集、GF 与KF 预处理、指纹库优化、离线指纹库。

在线阶段：待测点RSS 采集、二次滤波、定位匹配算法、累计误差比较、输出定位坐标。

本文的指纹定位算法主要由上面的两个阶段来实现，其中离线阶段经过GF 与KF 处理采用已知的指纹库等方法，在线阶段通过改进的WKNN算法来实现进而减少了误差与提升了定位精度。

4 实验仿真

假设选取20m×15m的区域作为实验的区域如图2 所示，区域中有个9 个AP 点、9 个房间，按照所规划的区域分配AP 点坐标分别为(1,1), (10,1), (19,1), (1,7), (10,7), (19,7), (19,14),(10,14), (19,14)，各AP 点分布在各个房间的门口发射设备上，图2 中的圆点为测试点。

图1 算法的整体流程

图2 实验的模拟平面图

由前文可知K 的取值对定位精度产生重要的影响，下面通过实验来获取本文的K 值。

表1 不同K 值下的定位误差对比

由表1 不同K 值下的定位误差可以看出，改进WKNN 算法在K 值为4 时发生了拐点为误差的最小值，同理WKNN 算法在K 值为4 时定位误差也为最小。故本文的AP 的个数为4 即K=4。

K 值确定后实验分3 组进行仿真，首先是KNN 算法在没有应用滤波处理的定位跟踪与应用卡尔曼滤波的定位跟踪的对比仿真，第2 组是NN, KNN, WKNN 定位仿真对比，第3 组是WKNN，改进WKNN 定位仿真对比。

如图3 经过卡尔曼滤波与未经过卡尔曼滤波的定位跟踪对比可以看出，滤波对于环境的噪声的消除有很大的作用。未经过滤波处理的行迹路线是杂乱无章的，经过滤波处理过后，环境的主要噪声被过滤掉，在一定程度上消除了环境因素的影响。

由图4 仿真实验可知相较于NN 算法，KNN 算法误差有较大的改善；WKNN 算法与KNN 算法相比，WKNN 算法稍好于KNN 算法。由图5 仿真实验可以得出改进的WKNN 算法较WKNN 算法有了明显的提升，相较于经典的应用欧氏距离的度量方法曼哈顿距离度量有更大的改进，响应速度更快更加趋于平稳。

图3 KNN 算法经过卡尔曼滤波与否的对比

图4 NN, KNN, WKNN 定位误差比较

图5 WKNN 与改进WKNN 定位误差比较

5 结束语

相较于传统的定位方法，K-近邻算法有其独特的优势，简单便于操作，易于其他算法的融合。通过结合Wi-Fi 指纹定位和卡尔曼滤波，高斯拟合算法来减少环境的干扰，进而提升算法的定位精度减少误差。通过改进WKNN 算法的距离测量的方法，即应用曼哈顿距离来代替欧式距离为算法距离的度量，应用曼哈顿距离的优点弥补了欧氏距离存在的缺点，在定位误差的改进上有了很大的提升，符合预期的要求。

综合来看本算法仍然有许多需要改进和攻克的难点，比如环境及周边障碍物的反射阻隔等因素依然是干扰RSSI 的主要因素，当实验区域足够大的时候，选取的距离度量就会产生很大的误差，此时的度量就不可用了，因此在实验区域上也有很大的局限性。