基于改进型KNN算法和Android平台的室内定位技术研究

李昂　肖甫　李雷

摘 要：通过分析基于WiFi定位的传统位置指纹算法的不足之处，文中提出了一种旨在提高精度并减小计算复杂度的改进型KNN算法。通过Android平台对该算法进行实现和测试，分析比较K的取值、AP的位置及数量等因素对定位精度的影响。测试结果表明，该算法不但能够保证位置指纹室内定位的精度，还能有效减小计算复杂度，具有一定的可行性。

关键词：精度；计算复杂度；改进型KNN算法；Android平台

中图分类号：TP301；TN92 文献标识码：A 文章编号：2095-1302（2018）03-00-05

0 引 言

伴随着互联网应用的快速发展，人们在室内停留的时间越来越多，室内位置信息对人们的日常生活愈加重要，因此人们对室内定位有着愈发强烈的需求[1-3]。由于利用GPS和AGPS这两种定位方式进行室内定位时，信号会受到各种障碍物的遮挡[4]，因此亟待出现新型的室内定位方式。

随着无线局域网络（Wireless Local Area Networks，WLAN）遍布各地，智能手机和平板电脑等个人电子设备发展迅速，这些设备几乎都使用WiFi连接网络，用户可使用WiFi進行定位[5-7]。iOS，Android和WP是目前三大主流移动操作系统。其中，Android系统所占的市场份额日益增大，因此完全可以选择Android系统作为载体，设计基于WiFi的室内定位系统[8-11]。本文基于Android平台设计了一种基于改进的位置指纹算法，首先收集采样点的信号强度值信息，并将其保存到数据库中，然后将定位时的数据和数据库相互对比进行估算，得到所要定位的坐标信息。

1 基于WiFi的室内定位技术简介

虽然目前实现WiFi室内定位的方法有很多，但主要使用基于测距的定位方法。其中基于RSSI的定位方法最受关注[12-16]。基于RSSI的定位算法流程如图1所示。

2 传统位置指纹定位技术

目前，在研究基于WiFi的室内定位时，位置指纹定位技术使用较多[17-21]，受到了广泛关注。

2.1 技术原理

基于位置指纹定位算法的原理图如图2所示。

从图2可以看出，位置指纹定位算法主要包括离线工作阶段和在线工作阶段。离线阶段即数据收集阶段，首先选择一个区域，从中选取多个采样点，然后收集这些点WiFi信号的强度值RSSI，并将其作为位置指纹保存到指纹数据库中。在这个指纹数据库中，每个指纹都由一组RSSI值组成，且对应一个位置坐标。在线阶段即定位阶段，将待测目标定位的信息与指纹库进行匹配，最后估算出当前位置坐标，完成定位[22]。在WiFi环境下，使用位置指纹定位算法RSSI定位工作过程如图3所示。

在选取的定位区域中，l个采样点可以收集n个RSSI值来表示一个指纹，遍历所有采样点并获得各自的RSSI值，保存于指纹库中。指纹库内容如式（1）所示：

其中：RSSIji表示在第i个采样点所测的WiFi信号的第j个RSSI值；FPi=（RSSI1i，RSSI2i，…，RSSImi）表示任意一个位置的指纹数据，同时该指纹数据也可用坐标（x，y）表示。因此，指纹数据与坐标相互对应，其坐标如式（2）所示：

位置指纹数据库由式（1）和式（2）共同组成。

除了在离线阶段创建一个比较准确的指纹数据库，在线阶段指纹库的匹配算法也十分重要[23]。常用的匹配算法有最近邻法、K近邻法和加权K近邻法。

（1）最近邻算法（NN）

最近邻算法是一种比较常用的匹配算法，当待测目标进入定位所选区域时，可获得一个相关的指纹信息lf=（RSSI1，RSSI2，…，RSSIn），然后将这个指纹信息与指纹数据库中的信息相匹配，再算出它们之间的距离，其距离如式（3）所示[24，25]，其中距离最小也就是相似度最大指纹信息min（d（lf，FPi）），即待测目标的位置。

式中：RSSIj和RSSIji分别为定位点和指纹点的强度值；n是WiFi信号的个数。

最近邻算法操作十分简单，且容易实现，但是其可选择的参考点较为单一，定位时容易产生误差，精度不高。

（2）K近邻算法（KNN）

相较于最近邻算法，K近邻算法可选择的参考点有所增多。匹配待测目标的指纹信息，并找出与指纹数据库中最近邻的K（K>2）个指纹信息，通过计算坐标的平均值就可以估算出待测目标的位置，其位置如式（4）所示[26，27]：

式中：（xi，yi）是被选择的第i个指纹数据库中的信息所对应的坐标。

（3）加权K 近邻法（WKNN）

加权K近邻法是对K近邻法的一种改进。K近邻法选取的K个最小距离对最后的定位结果贡献相同，取平均值，但距离越小对定位结果坐标的贡献越大。因此，对所取的K个最小距离进行权值分配，距离越小，权值越大。K个权值ωk之和为1。ωk可自行设定，也可由式（5）计算得出[28，29]：

2.2 技术性能与存在的问题

当前的位置指纹算法虽然可以实现室内定位，但该算法依然存在一些问题，主要体现在以下方面：

（1）算法模型过于简单，仅能满足较为简单的室内环境的定位要求。当室内环境较为复杂，如家具等陈设较多、有移动物体或人走动时，该传统算法的定位精度无法满足要求。

（2）该算法在线工作阶段的运算量较大，尤其当AP个数较多或K取值较大时，运算量急剧增长，无疑增加了该算法的运行成本和复杂度。

3 一种改进的KNN算法

考虑到上述传统位置指纹算法存在的问题，对传统位置指纹算法作如下改进：

（1）面对更复杂的室内环境，应当建立更加符合实际的模型。传统位置指纹算法的模型主要采用MK模型，如式（6）所示：

L（d）=L+10nlgd+NωLω+NfLf （6）

其中：L表示距离发射端1 m处的传播损耗；n是路径传播损耗系数；d是发射端到接收端的距离；Nω和Nf分别是传播路径上穿过的墙壁和地板个数；Lω和Lf 分别是墙壁和地板的损耗系数。可见，传统模型对于室内环境只考虑了墙壁和地板，而对于更复杂的情况没有考虑。

因此提出一种新的更符合实际的模型，充分考虑了除墙壁和地板外包括人在内的其他障碍物，如式（7）所示：

式（7）与式（6）的不同之处在于最后一项，假设共有m种障碍物，Pi表示遇到第i种障碍物的概率，可以通过最小二乘法计算得出；Ni表示穿过第i种障碍物的个数，Li表示第i种障碍物的损耗系数。

（2）针对运算量较大的问题，提出一种减少运算复杂度的新方法。经试验证明，在RSSI算法中，信号强度的衰减速度与传输距离成指数关系，即距离小时衰减快，距离大时衰减慢。尤其当到达一定距离后，其衰减速度趋于平缓，即信号强度变化较小。因此，如果按照传统KNN算法让所有的RSSI值都参与到计算中，势必会造成较大的冗余开销。

基于上述现象，需确定一个距离阈值，大于该距離时RSSI变化较小，可以舍弃，而小于该距离时则为有效点，应予以采纳。由此可较大程度地减小运算量。在实际仿真中发现，该门限距离取8 m和10 m时定位精度差距不大，但运算量减小了约50%。

对于运算和精度有同样重要影响的还有AP的个数与算法中K的取值。仿真试验表明，AP的个数对于精度和运算量影响巨大。当AP数量增加且分布较均匀时，定位的精度较高，但同时运算量较大。而K的取值对于精度和运算量的影响则呈现出不同的规律，并非K的取值越大精度越高。因此，AP的个数与K的取值应当在精度和运算量之间权衡。

综合上述两个方面的改进，本文提出了一种用于室内定位的改进KNN算法。

4 改进KNN算法的Android实现与测试

本文所设计的定位系统包括收集部分和定位部分，客户端为Android移动端APP，在运行时用户首先通过收集模块将采样点信号的信息提交给数据库，然后定位时将定位信息与数据库进行匹配，即可估算出位置。这款软件的理论设计内容如图4所示。

4.1 实现

（1）收集模块设计

当位置指纹定位算法处于离线收集阶段时，首先需要选取合适的区域进行信息收集，理论上需要在选取的区域内放置4个无线路由器，其WiFi信号的强度值RSSI比较稳定，测试结果误差较小，但本文的收集模块选用4个随机WiFi信号以及各自对应的强度值作为参考点。然后在区域内选取若干个采样点，其位置已知，将检测到的每个采样点的4种信号强度值均放入创建的指纹数据库中，此时指纹库中的每个采样点将由一系列RSSI值组成[30]。如果此时的室内环境发生变化，那么RSSI值也将发生变化且定位出现误差[31]。收集模块流程如图5所示。

（2）定位模块设计

当位置指纹定位算法处于在线定位阶段时，首先获取待测目标位置的RSSI值，然后使用本文提出的改进KNN算法即可估算出待测目标的位置。定位模块流程如图6所示。

（3）指纹数据库设计

考虑到数据量并不庞大，因此选择SQLite数据库。创建的数据库如图7所示。

4.2 测试方案与结果分析

（1）测试方案

在本次测试中选取了C104，C108，C112三间教室和大厅作为测试场地。

在这三间教室中，C112面积最大，约10 m×10 m；C104与C108面积较小且相近，约7 m×7 m；而大厅面积与C112相近，但较为空旷，如图8、图9所示。计划每间教室分别选取4个角落位置作为采样点，三间教室共12个采样点；而大厅内计划选取6个采样点，如图10所示。本测试主要检测在面积大小、AP个数、K取值和室内环境均不相同的条件下，所提出的改进KNN算法的性能。

（2）测试结果

教室C104，C108和C112测试结果见表1所列。

从表1可知，由教室C104和C108所测得的4组数据的误差系数明显小于C112的数据。

教室C108内有人时的测试结果见表2所列。

由表2可知，相较于无干扰时的结果，有干扰时得出的定位误差系数大，即误差较大。大厅测试结果见表3所列。

由表3可知，相较于环境复杂的教室，在较为空旷的大厅所获得的误差系数较小，较准确。

（3）测试结果分析

a.同一间教室有无干扰时的结果对比分析

根据在教室C108测得的两组数据，对采样点的真实位置和定位结果进行对比分析，如图11所示。

在图11中，实心圆表示采样点的真实位置，空心圆表示教室内无干扰时定位的结果，空心三角形表示教室内有干扰时定位的结果。真实位置和定位结果两点相连，其连线直观地显示了两点间的差距，这种差距即定位误差。相较于教室内有干扰时的定位结果，无干扰时产生的误差明显较小。

b.大小相近的教室与空旷空间的结果对比分析

在教室测试的数据里随机抽取6组并与在大厅测试的数据进行对比分析，如图12所示。

在图12中，折线1表示教室内采样点的测试误差系数，折线2表示大厅内采样点的测试误差系数。可以很明显地看出，折线1的误差系数整体比折线2大，因此，在大厅内产生的误差较小。

5 结 语

本文针对基于WiFi的室内定位常用的传统KNN算法中存在的问题，提出了一种改进型KNN算法，在面对更复杂的室内环境时可以保证精度，并有效降低运算复杂度。基于Android平台对这一改进算法进行了实现和测试，测试结果表明，该算法达到了预期效果，具有一定的可行性。

参考文献

[1] 姜乐水.浅谈无线局域网（WLAN）技术[J].信息技术与信息化，2012（5）：64-67.

[2] 潘焱，田华，魏安全.无线通信系统与技术[M].北京：人民邮电出版社，2011：147-148.

[3] 张瑞生，刘晓辉.无线局域网搭建与管理[M].电北京：子工业出版社，2011：14.

[4] 刘智敏，阳凡林，独知行.卫星定位原理及应用的教学改革与实践[J].测绘工程，2010，19（3）：77-80.

[5] 袁晶.大规模轨迹数据的检索、挖掘和应用[D].合肥：中国科学技术大学，2012.

[6] 王建平，余根坚，李晓颖，等.无线网络技术[M].北京：清华大学出版社，2013：180-181.

[7] 黎连业，王安，李龙.无线网络与应用技术[M].北京：清华大学出版社，2013：104-105.

[8] 姜莉.基于WiFi室内定位关键技术的研究[D]. 大连：大连理工大学，2010.

[9] 陈典全.LBS中基于轨迹的用户行为特征分析[J].全球定位系统，2011，36（6）：58-61.

[10] 罗纪清，万恩秀.超声引导下不同定位方法在体外碎石中的应用[J].检验医学与临床，2017，14（2）：261-263.

[11] 宋伟清，周廉，白涛，等.基于逐元暗电流抑制的红外线探测器读出电路研究[J].红外，2015，36（4）：13-19.

[12] 熊永平，孙利民，牛建伟，等.机会网络[J].软件学报，2009，20（1）：124-137.

[13] 龚世雄.浅析RFID技术及其应用[J].中国科技信息，2013（3）：52-53.

[14] 高仁强，张晓盼，熊艳，等.模糊数学的WiFi室内定位算法[J].测绘科学，2016，41（10）：142-148.

[15] 卢恒惠，刘兴川，张超，等.基于三角形与位置指纹识别算法的WiFi定位比较[J].移动通信，2010，34（10）：72-76.

[16] 李扬.WiFi技术原理及应用研究[J].科技信息，2010（6）：241.

[17] 贺远华，黎洪生.距离几何的TOA无线定位算法[J].计算机工程与应用，2010，46（12）：112-114.

[18] 鲁丹宇，高春利，刘浩然.基于无线时钟同步的超宽带TDOA定位系统设计[J].节能， 2017，36（1）：66-68.

[19] S TOMIC，M BEKO， D RUI，et al. Distributed RSS-AoA based localization with unknown transmit powers[J].IEEE wireless communication letters， 2016，5（4）：1.

[20] 薛卫星，邱卫宁，花向红，等.RSSI信号特征值对WiFi室内定位精度的影响分析[J].测绘地理信息，2016，41（4）：23-26.

[21] 孙学康，刘勇.无线传输与接入技术[M].北京 ：人民邮电出版社，2010：298-301.

[22] 赵小东.Android平台下基于无线信号强度的定位系统的实现[D]. 哈尔滨：哈尔滨工业大学，2011.

[23] 王淑婷.基于位置指纹的WiFi定位算法研究[D].长春 ：吉林大学，2015.

[24] CHEN L， L? M， QIAN Y. A personal route prediction system based on trajectory data mining[J].Information sciences an international journal. 2011，181（7）：1264-1284.

[25] 王阳，叶芝慧，冯奇，等. 基于Android的室内WiFi定位系统设计与实现[J].电子测量技术，2016，39（9）：16-19.

[26] 王考杰，郑雪峰，宋一丁，等.面向轨迹数据流的KNN近似查询[J].计算机工程，2011，37（16）：17-20.

[27] 李伟.Android中人为改变程序生命周期的研究[J].计算机应用与软件，2013，30（9）：205-207.

[28] 羅利.基于Android的WiFi室内定位技术研究[D].成都：西南交通大学，2014.

[29] 卞国龙，黄海松，葛至峥，等.无线传感器网络节点定位技术的优化[J].激光杂志，2017，38（3）：69-74.

[30] 张建平.基于WiFi的室内定位系统设计和算法研究[J].自动化技术与应用，2016，35（12）：53-56.

[31] MAHAJAN R，BALASUBRAMANIAN A，VENKATARAMANI A，et al. Interactive WiFi connectivity for moving vehicles[J].Proceeding of sigcomn，2013， 38（4）：427-438.