基于KNN算法的室内定位系统的设计与实现

吴雅琴，轩兴栋，张玉婷，秦龙斌，王雨豪，吴 桐，吴 彤

（中国矿业大学（北京） 机电与信息工程学院，北京 100083）

0 引 言

随着科技水平的快速发展，人们生活水平的提高，人们对于位置服务的需求不断增长[1]。室外定位技术有着GPS定位系统的帮助，已经非常成熟，其广泛应用于交通、救援、农业、军事等领域。GPS是当前定位精度最稳定、应用最广泛而且呈现市场垄断状态的卫星导航系统[2]。近年来，中国自行研制的北斗卫星导航系统（BDS）也成为继GPS、GLONASS之后成熟的卫星导航系统。在室外定位方面，北斗卫星导航系统已经广泛应用于交通运输、测绘地理信息、应急搜救等领域，逐步渗透到人们生活的方方面面，为全球经济和社会发展注入了新的活力。但由于卫星信号容易受到障碍物的遮挡，与室外相比，室内复杂多变的建筑墙体会极大削弱室外的卫星信号，使卫星定位技术无法在室内准确可靠地工作。室外定位导航技术无法直接应用于室内环境，而随着物联网技术的发展和普及，室内定位技术不可或缺。

室内定位的研究起步较早，目前的室内定位技术主要有射频标签、超宽带、ZigBee、蓝牙、WiFi、红外线、超声波和可见光等技术[3]。其中，WiFi指纹定位技术有着广泛运用。在室内环境下，WiFi普及率较高，易部署，而且利用智能手机就能得到WiFi的RSSI信息，采集方便。该定位技术定位成本较低，能满足大多数室内场景的定位精度需求，所以基于WiFi指纹的室内定位技术将成为主流的室内定位方案。

目前，在苹果、微软、华为等国际互联网巨头的引领之下，WiFi室内定位技术发展迅速，其发展方向和目标为高定位准确度和低功耗[4]。

现今，移动设备的计算能力和存储能力已有跨越式提升，如何有效降低WiFi室内定位的功耗也是当前研究的热点问题。一方面，通过改进WiFi室内定位算法，在保证定位准确度的前提下，减少信号采集频率并降低算法的复杂度[5]；另一方面，通过使用低功耗蓝牙和运动检测传感器等有助于定位的其他低功耗设备，研究多技术结合的融合算法，来达到降低功耗的目的。

本文对基于WiFi指纹的室内定位系统进行了研究，并开发了基于Android平台的室内定位系统。本研究共分为三个部分，第一部分为指纹数据库的创建过程，主要采集WiFi信号的接收信号强度指标（Received Signal Strength Indication, RSSI）[6]，该指标反映了当前位置收集的WiFi信号强度值，通过WiFi信号的获取与划定采集区域来生成WiFi信号指纹数据库[7]；第二部分为室内定位算法的实现，我们使用K-近邻位置指纹算法[8]，通过取得实时在线位置数据，在离线指纹库中的指纹中找到多个与在线数据相近的数据[9]，将在线数据与数据库中挑选的数据进行匹配，最终确定在线用户的位置；第三部分为安卓客户端的开发过程。

本文旨在根据已有的基于WiFi指纹的室内定位技术思路，借助WiFi指纹数据库构建算法、室内定位算法，搭建一套个人安卓客户端的室内定位系统。

1 算法的设计与实现

指纹技术的定位过程分为两个阶段，分别为离线采集阶段和在线定位阶段。在离线采集阶段，需要获取定位区域内的信息并存储到相应数据库中，以完成指纹库的构建。使用的采集设备为安卓手机，将数据库直接部署在SQLite中，高效利用安卓资源。

在采集过程中，首先创建需要采集的区域信息（通过区域信息区分不同区域，以此正确匹配不同区域的WiFi指纹数据库）；接着创建AP信息，采用录入mac的方式进行；采集WiFi强度时只采集WiFi信号强度。根据确定的区域，确定原点坐标，再将此区域人工划分为多个小部分，每个小部分对应一个坐标点。在采集时，需要输入该位置的坐标点；然后到相应坐标点输入信息进行采集，数据存入SQLite数据库。一次测量的点的信息作为一组数据，最终通过多次测量得出平均值，即得到该点的WiFi指纹点。指纹采集流程如图1所示。

图1 指纹采集流程

定位算法的实现，我们选择K-近邻位置指纹算法（KNN）。基于KNN的指纹定位方法，是通过计算在线接收的RSS向量S=(s1, s2, s3, ..., sn)与数据库中各参考点采集的RSS向量Ri=(ri1, ri2, ..., rin)间的欧氏距离进行匹配。两者之间的欧式距离记为：

式中，i=1, 2, 3, ..., m, m是参考点总数。当D越小时表示S与对应参考点R之间的匹配度越高，即用户位置越接近参考点的位置。

根据以上原理，计算在线接收的向量S与每一个参考点向量的欧氏距离并根据欧氏距离进行从小到大的排序。取前k个参考点的位置信息，求得的均值即为用户当前位置：

式中，(xi, yi)表示所选出的k个欧氏距离最小的参考点对应的位置坐标。

在仿真与分析阶段，我们利用PyCharm对算法进行仿真实验，以验证该算法的有效性，并与NN算法进行对比。本文进行了误差分析实验来评价KNN的定位精度。

为避免前K个最近的“邻居”中所属类别数相同而导致算法无法判别的情况，K值只取奇数。不同K值对定位精度的影响结果如图2所示。从图2可以看出，K取偶数值时定位精度优于3 m的概率分布变化较不规则，不稳定；K取奇数值时随着K值增大，算法收敛加快，但是当K值增大到一定程度时，算法收敛又逐渐减慢。从图中可以看出，当K=11时，定位效果最佳。

图2 K值对定位精度的影响

本实验设定K值为11，对定位区域采用KNN和NN算法进行定位误差估计比较，并通过定位误差范围与误差百分率进行体现，其结果如图3所示。测试数据中每个点的定位误差情况如图4所示。

图3 定位误差范围百分率分布图

图4 测试点定位误差情况图

从图3中可以看出，KNN算法约77.8%的概率定位误差在3 m以内，而NN算法约72.57%的概率定位误差在3 m以内；从误差分布情况分析，KNN算法收敛更快，KNN算法最大误差小于NN算法。

两种算法的定位误差比较见表1所列。从定位误差来看，NN算法最小值误差为1 m，而KNN算法最小误差达到0.15 m，能较好满足室内环境的定位需求。

表1 不同方法的定位误差比较

2 客户端设计与实现

关于本论文开发的室内定位系统，我们利用WiFi进行定位，无需进行外部硬件设备的部署，方便且节约成本。我们开发的这个程序十分适合大型室内场景，此程序依靠WiFi的RSSI特征，离线阶段建立指纹数据库，在线阶段使用KNN算法进行匹配定位，可以达到不错的定位效果。我们设计的室内定位系统由数据采集系统和定位系统组成。完整功能模块设计如图5所示。

图5 室内定位系统功能模块

指纹采集系统的主要功能为采集WiFi指纹和查看周围已经录入区域的AP点。图6为该系统的主界面。

图6 指纹采集系统

我们在建立WiFi指纹数据库时，在指定区域输入x、y坐标值，提供该参考点位置。为使数据更加精确，我们进行了多次测量，减小误差。且测量时间间隔可自由设定，使用方便。WiFi指纹采集成功后会录入SQLite数据库存储，后续进行统一管理。图7所示为录入参考点信息界面。

图7 指纹采集过程示意图

在系统“查看周围已经录入区域的AP点”功能中，我们可以查看已经录入的AP点，并查看AP点的强度信号，也可以进行管理，实现区域内AP点的增加和删除。

我们还开发了定位系统。在程序中介入了建成的指纹数据库，来获取参考点坐标的指纹强度。系统会在其中录入地图，根据手机接收的信号强度与指纹数据库相匹配，实现定位，并在地图中标记当前用户位置，误差较小，可以达到较好的定位效果。为验证程序可以正确进行，我们划定了实验区域，测试了本系统，如图8所示。

图8 室内定位系统测试

3 结 语

本文首先对KNN算法与NN算法进行对比，通过误差分布情况得出KNN算法较NN算法更为精准，且收敛更快的结论。同时，又进一步确定了k值，并在实验中验证了该算法的正确性[10]。

开发设计了一套基于WiFi指纹的室内定位系统。本系统利用室内已有的WiFi路由设备，无需额外部署，系统定位精度高。相较于RFID射频识别技术和蓝牙技术，成本较低，部署量较少，使用方便。与UWB技术相比，设备部署和操作都更为简洁，能够实现更高的普及率。通过使用系统多次进行数据采集、定位实验和数据校正，取得了理想的定位准确率。