基于区域分割的快速KNN定位算法

赵建国，王杰贵

（国防科技大学电子对抗学院，合肥 230037）

0 引言

近年来，人们对室内位置信息服务的需求越来越强烈[1]。由于GPS信号在多数室内环境中都接受不到，而蜂窝网定位技术又无法满足用户对室内定位的应用要求，人们开始广泛关注基于接收信号强度（Received Signal Strength，RSS）的无线局域网（Wireless Local Area Networks，WLAN）室内定位系统[2]。目前，大部分室内定位的方法受复杂的室内环境的影响，定位精度普遍不高[3]。其中，位置指纹算法是将未知目标与指纹数据库数据进行特征匹配，获取定位结果，室内复杂的信号传播模型对其定位精度的影响较小。因此，位置指纹定位算法在室内定位中得到了广泛的应用[4-6]。指纹定位分为离线建库和在线定位两个阶段。离线阶段，采集来自参考点处的各个接入点（Access Point，AP）的RSS值，建立位置指纹库；在线阶段，将实时采集的RSS信号与位置指纹库进行匹配，得出用户位置。

指纹匹配是在线定位阶段的工作，即将在线采集的待定位目标的RSS向量与指纹库中的位置指纹一一对比、匹配的过程。因此，当离线建立的指纹数据库较大时，指纹匹配的工作量和时间将会变大，影响定位的实时性和匹配效率。针对这一问题，很多研究者已经提出了不同的改进算法。文献[7]提出了用聚类的方法对位置指纹进行划分，以能否接收到无线信号作为聚类的依据，但是当大多数采样节点在待定位区域都能接收到无线信号，这样并不能减少位置指纹匹配的时间。文献[8]提出将压缩感知理论和仿射传播聚类理论应用到定位机制，在一定程度上提高了定位精度，但算法复杂，运算量大。文献[9]提出了采用精定位和粗定位相结合的算法，算法的时间复杂度得到了减小，但定位精度较低，不太符合用户对位置精确度的要求。

针对上述问题，本文对位置指纹算法中在线指纹匹配进行了深入的研究，提出了一种基于KNN的快速定位算法，该算法采用区域分割的思想进行位置估计。在保证定位精度与传统KNN算法相似的情况下，快速KNN算法有效地减少了定位的时间。从仿真的结果可以看出，改进后的算法可以对目标进行快速定位，减小了定位系统的压力。

1 基于位置指纹的KNN定位算法

位置指纹定位分为离线建库和在线定位两个阶段。其中，在线定位阶段主要是进行指纹匹配的过程。目前最常用的指纹匹配算法有朴素贝叶斯法、最大似然概率法、核函数法和最近邻法[10-11]。

最近邻（Nearest Neighborhood，NN）法实现定位的过程是计算实时采集的RSS向量与指纹库中的每个指纹对应的RSS均值的欧式距离，然后找出与实时采集的RSS向量距离最近的一个或多个指纹，将其对应的位置坐标进行平均或加权平均，从而得到位置估计坐标。计算欧式距离的公式为：

NN算法实际上是寻找最小的di的过程，假设选取K（K≥2）个值较小的参考点作为最后定位到的参考点，并计算其对应的坐标的平均值作为位置估计的结果，即为KNN算法。计算公式如下：

与NN算法相比，KNN算法纳入更多的位置坐标来完成最后的定位，定位精度得到了提高。

根据NN算法和KNN算法可知，随着数据库的增大，采样点的增加，其定位的时间及指纹匹配的功耗将线性增加。因此，在类似商场这种定位环境比较大的情况下，需要离线采集的参考点数目将会很多，这时指纹匹配的时间将会增加，定位的实时性较差，从而影响用户的体验。此时定位的结果也将失去现实的意义。针对此问题，本文在传统的KNN算法的基础上，采用区域分割的方法对定位区域进行一定程度上的缩小，从而减小定位所需要的时间，达到用户的需求。

2 基于区域分割的快速KNN算法

该算法的主要思想是先将定位区域进行等块的划分，然后选取每块区域的中心作为参考点，分别与实时采集的RSS向量进行欧式距离匹配，从而得到待定位目标所在的区域；然后对该子区域进行进一步的等块划分和欧式距离匹配，直到最后得到的子区域面积小于一定的阈值时，停止区域分割，在此子区域内利用KNN算法进行指纹匹配，得到最后的位置估计。该定位算法整个过程的结构如图1所示。

图1 快速定位算法流程图

快速KNN算法主要采用区域划分的思想，对待定位目标进行逐步的搜索，其定位的具体步骤如下：

1）选定定位区域，布置采样点；在指纹定位的离线阶段，首先选定N*N m2的正方形区域作为定位区域，由于正方形区域的边缘也需要布置采样点，因此，将该定位区域划分为边长为1 m的（N+1）2个正方形网格，以每个网格的中心作为需要采样的参考点，每个采样点之间间距1 m。

2）定位区域划分；对已选定的定位区域进行等块的划分，以每块区域的中心A-D（当遇到小数时，向下取整）以及它们的交点E作为优先匹配的参考点，分别与实时采集的RSS向量进行欧式距离匹配，如图2所示。

图2 定位区域划分

3）将优先匹配的参考点A～E与待测点进行欧式距离的计算，寻找欧式距离最小的点M。若M为E，则将定位区域的4个顶点分别向中心缩小一半；否则将M所在的正方形区域作为定位区域，继续执行步骤（2）。

4）重复2）和3）的过程，直到最后参与匹配的欧式距离最小的参考点所在区域的面积小于设定的阈值，查询结束。

5）提取指纹库中在此区域内的所有参考点，然后利用KNN算法选取欧式距离最小的K个点，得出最终的位置坐标（x，y）。

其中，该快速定位算法进行区域划分的流程可用图3进行表示。针对不同大小的网格，区域划分的次数也会不同。以网格大小为31 m*31 m的网络环境为例，图3为优先参与匹配的参考点的选取以及区域划分的过程。图3（a）中，灰色三角形为待测点；图3（b）和图3（c）中，蓝色点为已等块划分的区域的中心点位置，红色点为整个定位区域的中心点位置。图3（b）～（d）为区域划分的过程。

3 仿真测试和结果分析

图3 区域划分流程图

为验证所提出的算法的有效性，本文在主频为2.30 GHz的Intel i5双核CPU及3.8GB内存的PC机上利用Matlab软件进行定位仿真实验。同时，为了验证已提出的算法相比于传统的KNN算法的优势，本文分别对快速KNN定位算法和KNN算法在不同大小的定位区域内进行仿真比较。其中仿真实验采取对传统的传播损耗经验模型进行仿真，即

式中，d为AP热点与参考点的实际物理距离，d0为预设参考距离，P（d0）为预设距离处的 RSSI值，n为路径损耗因子，Xσ为环境因子，P（d）为距离d处的RSSI值。设距离为2 m时的信号强度值为-35 dB，n=3.5，为模拟室内环境，环境因子Xσ设为强度为4 dB的高斯白噪声。针对所提出的算法，随机选择60个待测点，分别对两种算法进行定位仿真实验。

3.1 仿真测试和结果分析

在网格大小为10 m*10 m、30 m*30 m和50 m*50 m中分别对两种算法进行定位误差和定位消耗时间的性能仿真分析。其中对定位消耗时间的比较如表1所示。

表1 不同网格下的平均定位消耗时间

从表1中可以看出，在不同的网格下，快速KNN算法定位消耗时间要远远小于传统的KNN算法。在11 m*11 m的网格中，快速KNN算法的定位消耗时间比KNN算法节省了78.73%；在31 m*31 m的网格中，快速KNN算法比KNN算法的定位消耗时间比KNN算法节省了96.30%；在51 m*51 m的网格中，快速KNN算法比KNN算法的定位消耗时间节省了98.54%。通过比较可以看出，网格越大，快速KNN算法在节省时间功耗方面上的优势体现的越明显。随着网格的增大，参考点数目的增加，KNN算法的定位消耗时间呈0线性增加；而快速KNN算法的定位消耗时间增加缓慢。因此，当数据库中的指纹数目较多时，快速KNN算法对定位的实时性具有重要意义。

图4 10 m*10 m网格中的定位误差

图5 30 m*30 m网格中的定位误差

图6 50 m*50 m网格中的定位误差

从图4～图6中可以看出，在网格大小相同的情况下，快速KNN算法和传统KNN算法定位误差相近。而且随着网格数目的增加，KNN算法和快速KNN算法的误差大于1 m的点数和最大误差都在增加。从整体上来看，快速KNN算法在个别点的定位误差稍稍大于传统KNN算法，尤其是在定位误差较大的部分待测点上。这是由于快速KNN算法采用的是区域分割的思想，在逐渐缩小定位区域的过程中，有些待测点错过了数据库中最优的参考点，从而误差较大。但在快速KNN算法中，这些误差较大的点只占总体的6%，在误差可控的范围内，且大部分位置的定位误差与传统KNN算法相近。

在仿真的过程中，已设定采样距离为1 m，但在网格较大的情况下，部分待测点的定位误差已大于1m。这是因为在仿真实验中采用的是传统的传播损耗经验模型。在这个对数模型中，距离和信号强度之间并不是线性关系，随着距离的增加，信号强度减小的很快，在寻找参与匹配的参考点时，采用的是信号强度的欧式距离进行匹配。因此，在较大的网格中，有些位置距离变化后，信号强度改变的基本很小，就造成该位置待测点的定位误差较大，但误差在可控的范围内。

综上所述，快速KNN算法在保证定位精度的情况下，对目标定位的速度明显快于传统KNN算法，定位的实时性较好。

4 结论

本文分析了基于位置指纹定位的KNN算法，在考虑怎样提高指纹匹配效率和定位实时性的问题上提出了快速KNN算法。该算法在定位阶段采用区域分割的思想，对定位区域进行等块划分，通过计算待测点与优先参与匹配的参考点的欧式距离，逐步缩小待测点的定位区域范围，当待测点的定位区域小于已设定的阈值时，利用KNN算法进行最终的位置估计。在对所提出算法的仿真结果分析可知，该算法在保证定位精度的同时，大大提高了定位的实时性。在指纹数据库较大的情况下，本文所提出的算法可大大减小KNN算法的指纹匹配功耗，实时性较好。如在大型商场中，利用快速KNN算法可对人员进行迅速定位，实现对目标的搜索和跟踪。