﻿ 基于位置范围限定的WiFi-KNN室内定位算法
«上一篇
 文章快速检索 高级检索

 应用科技  2020, Vol. 47 Issue (4): 66-70  DOI: 10.11991/yykj.201912002 0

引用本文

XI Zhihong, ZHAN Mengqi. WiFi-KNN indoor positioning algorithm based on location range limitation[J]. Applied Science and Technology, 2020, 47(4): 66-70. DOI: 10.11991/yykj.201912002.

文章历史

WiFi-KNN indoor positioning algorithm based on location range limitation
XI Zhihong, ZHAN Mengqi
College of Information and Communication Engineering, Harbin Engineering University, Harbin 150001, China
Abstract: In order to solve the problem that the accuracy of traditional WiFi-KNN indoor location algorithm cannot meet the requirements of accurate location, a K-nearest neighbor based on the location range limit (LRL-KNN) indoor positioning algorithm is proposed in this paper. The traditional KNN algorithm calculates the matching distance between the user’s fingerprint at this location and the fingerprint at the reference point in the database, and then sorts the nearest neighbor reference points by the fingerprint distance. However, LRL-KNN algorithm uses a range factor composed of the physical distance between the user’s previous position and the reference point position in the WiFi fingerprint database to scale the fingerprint distance, so as to reduce the spatial ambiguity of location. Although using the previous position, the LRL-KNN algorithm does not need to know the exact moving speed and direction of the user. Meanwhile, considering the time fluctuation of the received signal strength of WiFi, the RSS histogram is incorporated into the distance calculation to reduce the impact of time fluctuation. The experimental results show that the average positioning error of the traditional KNN algorithm is 2.13 m, and that of the new algorithm is 1.80 m, and the former is 15% higher than the latter in the same test environment.
Keywords: WiFi fingerprint database    received signal strength    K-nearest neighbor algorithm(KNN)    RSS histogram    range factor    time fluctuation    cumulative distribution function

1 WiFi指纹的室内定位方法

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

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

2 室内定位系统模型 2.1 WiFi室内定位场景

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

2.2 经典KNN算法

 $D_l^i = \sqrt {\sum\limits_{j = 1}^N {{{({f_j} - f_j^i)}^2}} }$ (1)

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

 ${\overline {{D}^i _l}} = \frac{{W_l^i \times D_l^i}}{{\displaystyle\sum\limits_{i = 1}^M {W_l^i} }}$ (2)
 $W_l^i = \exp \Bigg(\frac{{{{({x_i} - {x_{{\rm{pre}}}})}^2} + {{({y_i} - {y_{{\rm{pre}}}})}^2}}}{{4{\sigma ^2}}}\Bigg)$

 $l = \frac{{\displaystyle\sum\limits_{j = 1}^K {\displaystyle\frac{{{l_j}}}{{{\overline {{{{D}} ^j_l}}}}}} }}{{\displaystyle\sum\limits_{j = 1}^K {\displaystyle\frac{1}{{\overline {{{D}} ^j_l}}}} }}$

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

 $p_R^{i,j} = \dfrac{{n_{{R_j}}^i}}{{n_{{\rm{total}}}^{i,j}}}$

 $D_{l,{\rm{new}}}^i = \sqrt {\sum\limits_{j = 1}^N {\sum\limits_{{R_j} = R_L^j}^{R_U^j} {p_R^{i,j}{{({f_j} - {R_j})}^2}} } }$

 $\overline {d _l^i} = \frac{{W_l^i \times d_{l,{\rm{new}}}^i}}{{\displaystyle\sum\limits_{i = 1}^M {W_l^i} }}$
3 实验与分析

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

4 结论

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

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

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

 [1] WANG Bin , ZHAO Yingqun , ZHANG Tong , et al. An improved integrated fingerprint location algorithm based on WKNN[C]// 2017 29th Chinese Control And Decision Conference. Chongqing China, 2017:129-133. (0) [2] 孙纬民, 杜庆治. 基于WiFi与蓝牙的室内定位技术探究[J]. 软件导刊, 2018, 17(3): 169-171. (0) [3] 付俊. 一种精密实时无线定位系统-Ubisense7000定位系统[J]. 仪器仪表标准化与计量, 2008(4): 28-30. DOI:10.3969/j.issn.1672-5611.2008.04.010 (0) [4] SUN Jiping, LI Chenxin. Tunnel personnel positioning method based on TOA and modified location-fingerprint positioning[J]. International journal of mining science and technology, 2016, 26(3): 429-436. DOI:10.1016/j.ijmst.2016.02.010 (0) [5] TOMIC SLAVISA, BEKO MARKO, DINIS RUI, et al. On target localization using combined RSS and AoA measurements[J]. Sensors, 2018, 18(4): 1266. DOI:10.3390/s18041266 (0) [6] HE Suiming, CHAN S H G. Wi-Fi fingerprint-based indoor posi-tioning: recent advances and comparisons[J]. IEEE communications surveys and tutorials, 2016, 18(1): 466-490. (0) [7] BRUNATO M, BATTITI R. Statistical learning theory for location fingerprinting in wireless LANs[J]. Computer networks, 2005, 47(6): 825-845. DOI:10.1016/j.comnet.2004.09.004 (0) [8] FANG S H, LIN T N. Indoor location system based on discriminant-adaptive neural network in IEEE 802.11 environments[J]. IEEE transactions on neural networks, 2008, 19(11): 1973-1978. DOI:10.1109/TNN.2008.2005494 (0) [9] 刘宏刚. 基于神经网络的室内定位算法的研究与实现[D]. 北京: 北京工业大学, 2017. (0) [10] SHI Ke, MA Zhenjie, ZHANG Rentong, et al. Support vector regression based indoor location in IEEE 802.11 environments[J]. Mobile information systems, 2015:1-14. (0) [11] 张文学. 基于WiFi的RSSI指纹定位算法研究[D]. 成都: 电子科技大学, 2015. (0) [12] 杨帆. 基于改进KNN算法的室内WIFI定位技术研究[D]. 西安: 西北工业大学, 2016. (0) [13] LIU Zhenyu, DAI Bin, WAN Xiang, et al. Hybrid wireless fingerprint indoor localization method based on a convolutional neural network[J]. Sensors, 2005, 19(20): 4597. DOI:10.1016/j.comnet.2004.09.004 (0) [14] 陈祥. 基于 WIFI与移动智能终端的室内定位技术研究[D]. 哈尔滨: 哈尔滨理工大学, 2017. (0) [15] CAI Minmin. Research on sampling and matching algorithm in indoor location system based on WiFi fingerprint[D]. Nanjing: Nanjing University of Posts and Telecommuni- cations, 2016. (0) [16] XU Yaqian, SIAN LUN LAU, KUSBER R, et al. Autonomous indoor localization using unsupe rvised Wi-Fi fingerprinting[C]//International and Interdisciplinary Conference on Modeling and Using Context. Springer Berlin Heidelberg, 2013. (0) [17] JUN J , HE L , GU Y , et al. Low-overhead WiFi fingerprinting[J]. IEEE transactions on mobile computing, 2018, 17(3): 590-603. DOI:10.1109/TMC.2017.2737426 (0) [18] DONG F, CHEN Y, LIU J, et al. A calibration-free localization solution for handling signal strength variance[C]//International Conference on Mobile Entity Localization and Tracking in Gps-less Environments. Springer, Berlin, Heidelberg, 2009: 79–90. (0) [19] YOGITA CHAPRE, PRASANT MOHAPATRA, SANJAY JHA. Received signal strength indicator and its analysis in a typical WLAN system (short paper)[C]// IEEE Conference on Local Computer Networks. Sydney, Australia, 2013. (0) [20] 吴泽泰, 蔡仁钦, 徐书燕, 等. 基于K近邻法的Wi Fi定位研究与改进 [J]. 计算机工程, 2017, 43(3): 289-293. DOI:10.3969/j.issn.1000-3428.2017.03.048 (0)