自适应K-近邻算法提高WiFi指纹定位精度的研究

⃝⃝可在www.sciencedirect.com上在线ScienceDirectICT Express 4（2018）91www.elsevier.com/locate/icteWiFi指纹定位的自适应K-近邻算法吴钟泽a，金志秀ba大韩民国汉城大学电子工程系b接收日期：2018年2月6日;接受日期：2018年在线提供2018年摘要K近邻算法是室内定位系统中应用最广泛的算法之一然而，每个估计位置的误差显著地根据用于算法的K因此，如果K是固定值，则不能进一步减小位置的估计误差。在这封信中，我提出了一种算法，通过分析K值和接收到的WiFi信号强度之间的相关性，为每个位置调整K与K值固定的算法相比，该算法的定位精度提高了30%以上c2018韩国通信与信息科学研究所（KICS）。Elsevier B.V.的出版服务。这是一个开放获取CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。关键词：KNN;定位;指纹1. 介绍已经提出了各种室内位置估计技术。具体而言，WiFi指纹识别被广泛用于估计连接终端的室内坐标，而不需要额外的基础设施[1，2]。该方法测量区域内的若干参考点（RP）周围的WiFi路由器的接收信号强度（RSS），并将测量结果存储为WiFi指纹数据。然后，该方法通过测量对应的RSS来估计该区域中的任何测试点（TP）处的终端位置，该RSS与所存储的WiFi指纹数据进行比较。位置估计通常基于比较的数据点之间的欧几里德距离（ED）。因此，诸如k-最近邻（KNN）的算法可以用于通过考虑其最接近的K个数据点的平均值来估计TP位置。类似地，比KNN更复杂的算法已经用于WiFi指纹识别，例如主成分算法。通信地址：116 16 gil，Samsungyo-ro，Sungbuk-gu，Seoul 02876，Republic of Korea。电子邮件地址：jtoh@hansung.ac.kr（J. Oh），kimjs324@hansung.ac.kr（J.Kim）。同行评审由韩国通信和信息科学研究所（KICS）负责https://doi.org/10.1016/j.icte.2018.04.004分析和支持向量机[3，4]。然而，这种算法的估计精度与KNN相当，KNN相对简单，因此使用更广泛。KNN算法的估计精度可以通过在平均过程中对每个数据点使用加权ED来进一步提高[5，6]。另一方面，还研究了用于对最近数据点进行分组的算法，以提高KNN然而，在聚类过滤KNN [7]和模糊C均值聚类[8]中只有很小的性能改进，并且这些方法的缺点是RP数据的预处理时间消耗很大。在所有情况下，精度都容易受到KNN算法所选K值的影响，并且它会根据终端位置而变化[9，10]。因此，固定的K值不能保证在每个位置处的准确估计。在这封信中，我提出了一个自适应KNN算法，以防止固定的K值的缺点。实验结果证实了改进后的估计精度。2. 不同温点K首先，为了分析KNN算法在真实环境下WiFi指纹定位中的应用，我收集了2405-9595/c2018韩国通信和信息科学研究所（KICS）。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。∑1===Pt==EDl+EDPl92J. 哦，J。Kim/ICT Express 4（2018）91表1根据K. (Unit：m.）KTP位置（六、三）（9，2）(15（4）(18（2）Avg. 9 TP13.02.20.00.01.631.71.91.50.01.550.92.40.71.01.770.61.81.51.41.690.82.41.01.21.6111.22.81.01.41.7131.52.71.21.41.7WiFi路由器RSS信号在1m间隔使用智能手机应用程序。3 h后，测量9个TP并分析其估计值。为了尽量减少来自人体的干扰，我将智能手机安装在指向北方的三脚架上。另外，我用（1）比较了第i个RP和TP的RSS相似度，其中N是WiFi路由器的数量在TP处测量，RSSr、RSSt是J J分别在第i个RP和TP处的WiFi路由器j此外，通过对K个最接近的RP的坐标P1求平均值，我使用ED_i逆作为权重来估计TP位置P1，如（2）中所表示的，其中P1是小的正实数[5，6]。NE Di=N（RSSr−RSSt）2（一）（∑KJj=11J）/（∑K第一章E Dl+Fig. 1. RP和两个TP位置之间的RSS的ED。(a)（6，3）米。(b)（15，4）m.表1列出了根据实施例的位置估计误差。相对于参考位置，位于坐标（6，3）m等处的几个TP的K值。可以看出，根据K的位置估计误差模式对于每个TP是非常不同在该示例中，9个TP的平均定位误差是相似的，而与K无关，但是通常对于小K或大K，位置估计误差增加[10]。下表显示了两种典型的估计误差模式。对于（6，3）m处的TP，仅考虑K1）大，并且可以确认当考虑更多RP时误差减小然而，如果K高于特定值，则远距离RP的位置（即，大ED）也包括在平均值中，并且误差相应地增加。相反，对于（15，4）m处的TP，检索K1的精确值，即具有最小ED的RP对应于TP。因此，位置估计误差随着其他错位的RP（K>1）被包括在平均值中而增大图1将与两个TP的RSS相对应的ED图示为3D等高线图，并且允许执行更详细的分析。图1a示出了在（6，3）m处的TP的曲线图，其中小ED用比大ED更亮的颜色表示，并且数字以ED小的顺序示出了RP。有几个区域显示出小的ED，但都偏离了（6，3）m处的实际TP位置。然而，七个位置的平均值（K7）将位置误差减小到0.6m。相反，图1b中的（15，4）m处的TP的曲线图示出了在区域中存在具有明显最小ED的单个区域的情况。此外，包含最小ED的区域对应于真实TP位置。因此，与其他相邻位置的平均增加了估计误差，而对于K1获得精确的TP位置。当考虑位于不同位置的不同数量的TP和RP时，上述行为是类似的。因此，如果一个位置的估计ED远小于相邻区域的估计ED（图1b），则很可能它对应于真实的TP位置。另一方面，如果不同位置处的ED小于其周围的ED（图1a），则当对示出小ED的几个邻居进行平均时，位置估计误差可以减小。这种行为代表了所提出的算法的基础，如下节所述。3. 自适应KNN算法所提出的算法的目的是减少在所有的TP出现时，使用一个固定的K值的整体位置估计误差。具体地，K值根据TP位置而变化，并且它由所提出的自适应KNN算法确定。因此，RP邻居的适当数量为l=0l=0（二）===√=-J. Oh，J. Kim / ICT Express 4（2018）91表2固定K=5和11时的位置估计误差为λ，并提出了自适应KNN算法。（单位：米）1.9（K=3）2.5（K=4）0.0（K=1）0.0（K=1）Place B（28，6）0.4 0.7 0.0（K=1）0.0（K=1）(30，8）1.7 2.1 1.5（K=3）1.5（K=4）(36，6）1.6 1.7 0.0（K=1）0.9（K=2）18个TP的平均值1.7 1.6 0.3（K平均值= 3。第三章0.9（K平均值= 2。（二）为每个TP选择最小化位置估计误差。基于前一节中分析的行为，该算法仅考虑ED在特定值范围内（例如，比最小ED值高出12%）的RP，以有助于估计。这个范围是明确确定的，它显示了一个适当的估计精度的评价情况。另一方面，如果具有小ED值的几个RP被聚类，如果考虑聚类中的所有RP，则它们可能在估计中引入偏差，这可能增加位置估计误差。因此，在平均值中仅考虑集群中的一个RP。排除的区域对应于RP的间隔的2，以避免包括具有小ED的紧邻和对角RP。所提出的自适应KNN算法详细如下：4. 估计精度表2列出了三种算法的位置估计误差，即，固定K5，其是根据[10]中的结果检索最小误差的值，固定K11用于附加比较，最小估计误差（KNN），以及在不同TP部分的K值效应中考虑的几个TP处的所提出的自适应KNN这种情况在表中表示为位置A此外，平均位置估计计算位置A的9个TP的误差，平均K值表示为Kavg。通过应用所提出的自适应KNN算法，多达五个邻居（即， K5）包括在（6，3）m处的TP位置估计中，仅一个在（15，4）m处的估计中。虽然该方法的位置估计误差大于参考算法的位置估计误差，但可以确认，相对于固定K的算法，该误差减小了约30%。表2还列出了用许多墙壁分隔的地点B的示例与前面的情况一样，可以确认所提出的算法减少了估计误差，这次相对于具有固定K5的算法减少了大约47%。也可以证明，K1提供了TP在（22，4）m处的精确位置。尽管当考虑几个TP时，所提出的算法和所提出的算法之间的误差差异很小，但是对于所有TP的平均误差差异要大得多。这可能是由于来自某些RP的高噪声数据，这是由算法评估所考虑的现实场景引起的。5. 结论在这封信中，我提出了一个自适应KNN算法，调整K值根据ED模式表现出的RP相对于TP。该算法与固定K值的算法相比，具有明显的改进效果.相对简单的KNN算法提供了一个位置估计误差约为1米，没有任何额外的基础设施，室内定位。因此，该算法可以适用于室内的位置估计，并可以与行人航位推算相结合，跟踪移动终端。同样，需要进一步的研究，以通过确定每个TP的最佳K值来最小化位置估计误差。确认本研究由韩城大学为Jongtaek Oh提供资金支持此外，这项工作得到了2018年NRF研究基金（编号2017R 1D 1A1B03031244）的支持。位置方法（六、三）（9，2）地点A（15，4）(18（2）9个TP的平均值K=50.92.40.71.01.7K=111.22.81.01.41.7MEE0.6（K=7）0.0（K=1）0.7（K平均值= 3。（九）自适应K0.5（K=5）0.0（K=1）1.2（K平均值=94J. 哦，J。Kim/ICT Express 4（2018）91利益冲突作者声明，本文中不存在利益冲突引用[1] V. Honkavirta，T. Perala，S.阿利-洛伊图河Piché，WLAN位置指纹识别方法的比较调查，收录于：Proc. IEEE Work-shop Position。导航Commun. Hannover，Germany，March 2009，pp. 243-251[2] P. Bahl，V.N. Padmanabhan，雷达：一个基于RF的用户定位和跟踪系统，在：Proc.IEEE INFOCOM，特拉维夫，以色列，2000年3月，第2卷，第100页。775-784。[3] J. Schäfer，实现W-LAN位置指纹识别的机器学习算法的实际问题，在：Proc. IEEE Int. Congr. Ultra Mod. Jammun。圣彼得堡，俄罗斯，2014年10月，pp. 310-317[4] D. Madigan ， E. 作 者 声 明 ： John W. Ju ， P. Krishnan ， A.S.Krishnakumar ， Bayesian 室 内 定 位 系 统 ， 在 ： Proc. IEEE IN-FOCOM，Miami，USA，2005年3月，pp. 1217-1227[5] M.布鲁纳托河Battiti，无线局域网中位置指纹的统计学习理论，Comput。Net. 47（6）（2005）825-845。[6] K.A. Nguyen，使用共形预测和WiFi信号强度的性能保证室内定位系统，J. Inf. 1（1）（2017）41-65。[7] J. 妈，X。Li，X.Tao，J.Lu，Cluster filtered KNN：A WLAN-basedindoor positioning scheme，in：Proc.IEEE国际Sym. 世界无线、移动和多媒体网络，纽波特比奇，美国，2008年6月。[8] H. Zhou，N.N. Van，基于模糊C均值聚类的室内指纹定位，在：proc. IEEE Int. Conf. Measur. Tech.机械自动。2014年，中国张家界。pp. 337-340[9] X.丁湖，澳-地Gao，Z.王，室内定位的改进指纹算法，J. Commun.12（3）（2017）145-151。[10] A. Kushki，K.N. Plataniotis，A.N. Venetsanopoulos，无线局域网中基于内核的定位，IEEE Trans. 移动计算 6（6）（2007）689-705。