基于位置范围限定的WiFi-KNN 室内定位算法

哈尔滨工程大学 信息与通信工程学院，黑龙江 哈尔滨 150001

随着基于位置服务(location based service,LBS)的快速发展，导致人们对定位服务的需求与日俱增。在全球定位系统(global positioning system，GPS)等室外定位技术完善的情况下，人们对室内定位的需求也得到了进一步的提升。特殊人群的监护、大型馆场的管理、商场人流的统计、火灾时的救援行动等，都需要用到用户准确的室内位置信息。现如今最常用的几种室内定位技术有WiFi 定位[1]、蓝牙定位[2]、超宽带定位[3]、射频识别定位等。本文的主要目的是利用WiFi 信号强度实现高精度的室内定位。通常，WiFi 室内定位方法可以分为2 类：一类是基于信号衰减的传播模型，它根据WiFi 传播信号时的衰减模型，利用基于到达时间（time of arrival，TOA）[4]或基于到达角（angle of arrival，AOA）[5]的方法来估计目标的位置；另一类是基于WiFi 指纹的室内定位方法，它的特点是要建立WiFi 指纹库。通过将参考点(reference point，RP)处的指纹信息存储起来，再根据待定位点处采集到的指纹数据，通过指纹匹配算法在指纹库中估计目标的位置。由于WiFi 信号在室内空间中传播时有强烈的多径效应，导致很难获得精确的信号衰减传播模型。因此指纹识别方法更适合基于WiFi 的室内定位。但是传统的基于WiFi 指纹库的K近邻（K-nearest neighbor，KNN）室内定位算法，在定位时因为误差的波动较大，所以该方法并不能满足定位精度的需求。本文提出基于位置范围限定的WiFi-KNN 室内定位算法，该算法可以很好地减小传统WiFi 室内定位方法误差大的问题。

1 WiFi 指纹的室内定位方法

基于WiFi 指纹的室内定位方法又可以分为确定性方法和概率性方法[6−7]。确定性方法是利用相似性度量来区分测量的信号数据和数据库中的指纹数据，然后将指纹数据库中最接近的指纹数据所处的位置估计为用户的位置。这一类室内定位方法的典型代表有人工神经网络[8−9]（artificial neural networks,ANN）,支持向量机[10]（support vector machine，SVM）和K近邻[11−12](KNN)，上述所有的定位方法都需要在离线阶段收集指纹信息，然后将其与测试阶段的测量数据进行比较来达到定位的目的。

在这些算法中，ANN 可以选择激活函数，通过调整权重来对数据进行非线性估计，以达到对目标的位置估计。尽管该方法能获得最高的精确度，但是它本质上是复杂的，并且在训练阶段需要极高的计算复杂度[13]。与之相反的是SVM，虽然SVM 比ANN 更简单，但算法复杂度仍然相对较高。与SVM 和ANN 相比，KNN 具有最低的复杂度，同时它的精确度却可与SVM 相提并论。

概率性方法都是利用贝叶斯法则，然后根据指纹库中的指纹数据和待定位点处测量到的指纹数据来推断位置信息。一些概率性方法将接收信号强度（received signal strength，RSS）的概率密度函数假定为经验参数分布[14−15](例如高斯、双峰高斯等)。这有可能因为没有很好地模拟实际情况而导致大量的本地化错误。

本文针对KNN 算法进行了进一步的研究，因为它具有较低的复杂度，更适合于实际生活中的使用。通常，KNN 算法需要计算当前测量的指纹数据与数据库中的各个指纹数据之间的距离，然后通过排序来确定K个距离最近的参考点，然后通过加权平均估算待定位点的位置。在KNN 中计算指纹距离时可以使用不同的距离度量，例如欧几里得距离、曼哈顿距离和马哈拉诺比斯距离等[16]。

尽管KNN 算法已在各类文献中进行了广泛研究，但KNN 仍然面临以下挑战：

1)空间歧义性：与当前位置相比，某些物理上遥远的位置可能具有相似的指纹或相似的指纹距离。这可能会误导KNN 算法，从而提高定位误差。

2) RSS 不稳定性：运动的物体、周围环境中电磁波等的不断变化，天线的方向性和射频干扰等，都会导致WiFi 信号的大幅波动。因此，在测试阶段采集到的某个位置的指纹可能与训练阶段中收集到的指纹不匹配。

3)待定位点处数据采集时间短：通常可以通过采集某个待定位点处大量的RSS 数据，然后利用这些数据来获得较稳定的指纹数据。但是，由于定位目标在定位时处于移动状态，该目标在某一定位点处停留的时间较短，这就导致在测量阶段，每个待定位点处的RSS 数据采集通常少于2 s。在这段时间内，只能收集到少量的RSS 数据，这会影响定位的精度。

4)繁重的初始训练阶段：良好的指纹数据库可以大大提升定位的精确度。构建高精度的指纹数据库，需要大量的RP[17]和大量的数据，这既费时又费力。

由于用户在室内环境中的移动速度和移动范围是有限制的，基于距离范围限定的KNN 算法(location range limitK-nearest neighbor，LRLKNN)是通过利用参考点和锚点(用户的先前位置)之间的物理距离组成的惩罚函数，在计算指纹距离时加入该惩罚函数，从而达到目标位置的估计。该方法可以减小空间歧义性问题。

此外，本文通过使用直方图和多个指纹的组合，例如均值、RSS 的差异、RSS 的等级等，以降低RSS 数据的不稳定性并提高定位精度。

2 室内定位系统模型

2.1 WiFi 室内定位场景

WiFi 指纹定位系统通常分为2 个阶段：训练阶段(离线阶段)和测试阶段(在线阶段)。在训练阶段，将收集到的每个RP 位置处的WiFi 信号强度和这些RP 对应的位置坐标存储到数据库中。在这里，假设采样区域有P个接入点(access point，AP)和M个RP。对于第i个RP，其位置坐标li(xi,yi)处对应的指纹数据矢量可以表示为是位置i处的第j个RSS。在训练阶段，可以在每个参考点处采集多组RSS 指纹数据，以此来提高指纹库的稳定性。测试阶段，利用待定位点处采集到的指纹数据，通过指纹匹配算法，来实现位置的推算。

2.2 经典KNN 算法

利用式(1)计算当前测试点l的指纹数据与数据库中每个RP 数据之间的指纹距离：

式中：fj是测试位置i处的第j个指纹特征；N是可用指纹特征的数量。然后选择距离最小的K个位置作为该位置的最近邻位置数据。最后，通过取所有K个最近邻位置的平均值来确定用户的位置l。

2.3 基于位置范围限定的KNN 算法(LRL-KNN)

由于用户的移动速度受到限制，并且在连续的测量时间内，用户无法从一个位置移动到另一个距离该位置很远的位置。故此，最简单的形式就是通过利用用户先前的位置信息，以该位置坐标为原点画圆，以期将最近邻数据限制在该圆内，该限制圆的半径可由用户2 次连续测量之间的移动速度和持续时间确定。本文没有使用该硬性的范围限制条件，而是在指纹距离计算中设计了一种新颖的距离范围限制因素，在该距离范围内用户先前位置附近的位置被赋予更高的可选择性，使其可以成为K个最近邻的候选对象之一。为此，可以将式(1)修改为

为了进一步提升定位精度，本文在如下2 个方面进行了改进：

1)指纹组合：WiFi 指纹方法中，指纹越稳定，定位精度越好。然而，由于动态变化的环境(例如人为阻挡和移动、来自其他设备的干扰、接收器天线方向等)，客户端设备收集的RSS 经常会经历较大的波动。因此，本文提出使用一组不同指纹的组合来确保每个位置具有足够的稳定性和独特的值。最常用的指纹是RSS 的平均值，该平均值由于前面提到的影响而显出波动。相反，更可靠的指纹之一是一对AP 之间RSS 的平均差。Dong等[18]使用2 个设备，即笔记本电脑和智能手机，在固定位置收集RSS。

2)RSS 直方图：如上所述，某个位置的原始RSS 读数不稳定，波动幅度最大可达10 dB[19]。因此，它们可能无法很好地代表每个位置的RSS 数据。为了降低这个问题带来的影响，可以在指纹距离计算中加入RSS 的直方图，该直方图定义了第j个AP 的原始RSS 读数在RP 处落入[Rj−0.5 dBm,Rj+0.5 dBm]的概率。计算方法为

最终指纹距离为

3 实验与分析

实验选择的位置是一个15 m×25 m的矩形实验室。房间的西南角作为坐标原点。东方向是x轴的正方向，北方向是y轴的正方向，在房间的外围边缘部署了6 个无线路由器组成6 个AP。这6 个AP 节点的坐标分别为：(0，0)，(12.5，0)，(25，0)，(0，15)，(12.5，15)，(25，15)。6 个AP 的SSID 用于区分在同一位置处接收到的信号强度。房间被分成1×1的网格，并且信号在采样设备上被接收。信号强度采样软件可在每个网格的顶点(共375 个RP)上采样RSS 值，每个RP 持续3 min，然后在此期间将每个AP 的RSS 平均值作为AP 在RP 的信号强度值。在每个RP 分别采集各个AP发射的RSS 值。需要注意的是，实验人员在每个RP 采集RSS 信号强度时，由于工作人员在实验环境中测量时会干扰信号强度，所以采集数据时需要在每一个RP 分别采集东南西北4 个方向的信号强度，然后对其取平均值，最后将处理后的数据及RP 位置坐标存入指纹数据库。室内RP 的分布情况如图1 所示。

图1 室内RP 分布情况

在测试阶段，对行人移动时的数据进行采集，当人在该区域环境内移动时，设备可以记录该行人在室内某位置处的AP 指纹以及其他相关信息。

KNN 在位置指纹定位中需要确定最优的K值，因为不同的K值对定位的结果也有影响，最优的K值往往能降低定位误差。找到最优的K值后，选取K个最近邻指纹，并对这K个指纹的位置坐标求平均，以获得定位结果。如何选择最优超参数K是降低算法计算效率的关键。通过对数据进行预处理和交叉验证，可以绘制超参数K和评分之间的关系曲线。如图2 所示，可以看出，K通常取小于20 的整数。在本文的实验中，K取14。

图2 超参数K 的曲线

在图3 中，对比了KNN 算法、SVM 算法、聚类的KNN（clusterK-nearest neighbor，CKNN）算法[20]和本文提出的LRL-KNN 算法在定位时的误差累计曲线，所有算法均使用RSS 的平均值作为指纹，连续采样时间间隔t=1 s。

图3 距离的误差累计曲线

从图中可以看出，LRL-KNN 算法的误差累计曲线的曲率相比其它三者表现得更好。新算法的平均定位误差为1.80 m，而KNN 算法的平均定位误差为2.13 m，SVM 的平均定位误差为2.36 m，CKNN 算法的平均定位误差为2.20 m。

从表1 中可以看出，LRL-KNN 定位算法的平均定位误差为1.80 m，相比于KNN 算法，平均定位精度提升了15.6%；相比于SVM 算法，平均定位精度提升了23.7%；相比于CKNN 算法，平均定位精度提升了17.4%。误差≤2 m 所占比误差≤3 m所占比率都高于其它3 种方法。从定位时间上看，LRL-KNN 算法虽然在定位时间上略逊于CKNN，但是它的定位精度却比CNN 高很多。

表1 各个算法的误差比

4 结论

通过上面的分析与论证，得出如下结论：

1)本文提出的基于位置范围限定的WiFi-KNN室内定位算法，在平均定位精度上优于KNN、CKNN 和SVM 算法。

2)本文提出的方法在定位时间上相较于传统的KNN 方法和SVM 方法有所缩短，但是定位的时间相比于CKNN 来说还是较长。

3)从整体定位性能上来看，LRL-KNN 定位的性能在这些方法中是最好的。虽然本文提出的方法在定位精度上是最高的，但是定位所花费的时间却不是最短的，如何在保证定位精度的情况下减小定位的时长也是值得去研究的一个方向。