随着基于位置服务(location based service, LBS)的快速发展,导致人们对定位服务的需求与日俱增。在全球定位系统 (global positioning system,GPS)等室外定位技术完善的情况下,人们对室内定位的需求也得到了进一步的提升。特殊人群的监护、大型馆场的管理、商场人流的统计、火灾时的救援行动等,都需要用到用户准确的室内位置信息。现如今最常用的几种室内定位技术有WiFi定位[1]、蓝牙定位[2]、超宽带定位[3]、射频识别定位等。本文的主要目的是利用WiFi信号强度实现高精度的室内定位。通常,WiFi室内定位方法可以分为2类:一类是基于信号衰减的传播模型,它根据WiFi传播信号时的衰减模型,利用基于到达时间(time of arrival,TOA)[4]或基于到达角(angle of arrival,AOA)[5]的方法来估计目标的位置;另一类是基于WiFi指纹的室内定位方法,它的特点是要建立WiFi指纹库。通过将参考点(reference point,RP)处的指纹信息存储起来,再根据待定位点处采集到的指纹数据,通过指纹匹配算法在指纹库中估计目标的位置。由于WiFi信号在室内空间中传播时有强烈的多径效应,导致很难获得精确的信号衰减传播模型。因此指纹识别方法更适合基于WiFi的室内定位。但是传统的基于WiFi指纹库的 K近邻(K-nearest neighbor,KNN)室内定位算法,在定位时因为误差的波动较大,所以该方法并不能满足定位精度的需求。本文提出基于位置范围限定的WiFi-KNN室内定位算法,该算法可以很好地减小传统WiFi室内定位方法误差大的问题。
1 WiFi指纹的室内定位方法基于WiFi指纹的室内定位方法又可以分为确定性方法和概率性方法[6-7]。确定性方法是利用相似性度量来区分测量的信号数据和数据库中的指纹数据,然后将指纹数据库中最接近的指纹数据所处的位置估计为用户的位置。这一类室内定位方法的典型代表有人工神经网络[8-9](artificial neural networks, ANN), 支持向量机[10](support vector machine,SVM)和K近邻[11-12](KNN),上述所有的定位方法都需要在离线阶段收集指纹信息,然后将其与测试阶段的测量数据进行比较来达到定位的目的。
在这些算法中,ANN可以选择激活函数,通过调整权重来对数据进行非线性估计,以达到对目标的位置估计。尽管该方法能获得最高的精确度,但是它本质上是复杂的,并且在训练阶段需要极高的计算复杂度[13]。与之相反的是SVM,虽然SVM比ANN更简单,但算法复杂度仍然相对较高。与SVM和ANN相比,KNN具有最低的复杂度,同时它的精确度却可与SVM相提并论。
概率性方法都是利用贝叶斯法则,然后根据指纹库中的指纹数据和待定位点处测量到的指纹数据来推断位置信息。一些概率性方法将接收信号强度(received signal strength,RSS)的概率密度函数假定为经验参数分布[14-15](例如高斯、双峰高斯等)。这有可能因为没有很好地模拟实际情况而导致大量的本地化错误。
本文针对KNN算法进行了进一步的研究,因为它具有较低的复杂度,更适合于实际生活中的使用。通常,KNN算法需要计算当前测量的指纹数据与数据库中的各个指纹数据之间的距离,然后通过排序来确定K个距离最近的参考点,然后通过加权平均估算待定位点的位置。在KNN中计算指纹距离时可以使用不同的距离度量,例如欧几里得距离、曼哈顿距离和马哈拉诺比斯距离等[16]。
尽管KNN算法已在各类文献中进行了广泛研究,但KNN仍然面临以下挑战:
1)空间歧义性:与当前位置相比,某些物理上遥远的位置可能具有相似的指纹或相似的指纹距离。这可能会误导KNN算法,从而提高定位误差。
2) RSS不稳定性:运动的物体、周围环境中电磁波等的不断变化,天线的方向性和射频干扰等,都会导致WiFi信号的大幅波动。因此,在测试阶段采集到的某个位置的指纹可能与训练阶段中收集到的指纹不匹配。
3)待定位点处数据采集时间短:通常可以通过采集某个待定位点处大量的RSS数据,然后利用这些数据来获得较稳定的指纹数据。但是,由于定位目标在定位时处于移动状态,该目标在某一定位点处停留的时间较短,这就导致在测量阶段,每个待定位点处的RSS数据采集通常少于2 s。在这段时间内,只能收集到少量的RSS数据,这会影响定位的精度。
4)繁重的初始训练阶段:良好的指纹数据库可以大大提升定位的精确度。构建高精度的指纹数据库,需要大量的RP[17]和大量的数据,这既费时又费力。
由于用户在室内环境中的移动速度和移动范围是有限制的,基于距离范围限定的KNN算法(location range limit K-nearest neighbor,LRL-KNN)是通过利用参考点和锚点(用户的先前位置)之间的物理距离组成的惩罚函数,在计算指纹距离时加入该惩罚函数,从而达到目标位置的估计。该方法可以减小空间歧义性问题。
此外,本文通过使用直方图和多个指纹的组合,例如均值、RSS的差异、RSS的等级等,以降低RSS数据的不稳定性并提高定位精度。
2 室内定位系统模型 2.1 WiFi室内定位场景WiFi指纹定位系统通常分为2个阶段:训练阶段(离线阶段)和测试阶段(在线阶段)。在训练阶段,将收集到的每个RP位置处的WiFi信号强度和这些RP对应的位置坐标存储到数据库中。在这里,假设采样区域有P个接入点(access point,AP)和M个RP。对于第
利用式(1)计算当前测试点
$D_l^i = \sqrt {\sum\limits_{j = 1}^N {{{({f_j} - f_j^i)}^2}} } $ | (1) |
式中:
由于用户的移动速度受到限制,并且在连续的测量时间内,用户无法从一个位置移动到另一个距离该位置很远的位置。故此,最简单的形式就是通过利用用户先前的位置信息,以该位置坐标为原点画圆,以期将最近邻数据限制在该圆内,该限制圆的半径可由用户2次连续测量之间的移动速度和持续时间确定。本文没有使用该硬性的范围限制条件,而是在指纹距离计算中设计了一种新颖的距离范围限制因素,在该距离范围内用户先前位置附近的位置被赋予更高的可选择性,使其可以成为K个最近邻的候选对象之一。为此,可以将式(1)修改为
${\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个方面进行了改进:
1) 指纹组合:WiFi指纹方法中,指纹越稳定,定位精度越好。然而,由于动态变化的环境(例如人为阻挡和移动、来自其他设备的干扰、接收器天线方向等),客户端设备收集的RSS经常会经历较大的波动。因此,本文提出使用一组不同指纹的组合来确保每个位置具有足够的稳定性和独特的值。最常用的指纹是RSS的平均值,该平均值由于前面提到的影响而显出波动。相反,更可靠的指纹之一是一对AP之间RSS的平均差。Dong等[18]使用2个设备,即笔记本电脑和智能手机,在固定位置收集RSS。
2) RSS直方图:如上所述,某个位置的原始RSS读数不稳定,波动幅度最大可达10 dB[19]。因此,它们可能无法很好地代表每个位置的RSS数据。为了降低这个问题带来的影响,可以在指纹距离计算中加入RSS的直方图,该直方图定义了第
$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} }}$ |
实验选择的位置是一个
Download:
|
|
在测试阶段,对行人移动时的数据进行采集,当人在该区域环境内移动时,设备可以记录该行人在室内某位置处的AP指纹以及其他相关信息。
KNN在位置指纹定位中需要确定最优的K值,因为不同的K值对定位的结果也有影响,最优的K值往往能降低定位误差。找到最优的K值后,选取K个最近邻指纹,并对这K个指纹的位置坐标求平均,以获得定位结果。如何选择最优超参数K是降低算法计算效率的关键。通过对数据进行预处理和交叉验证,可以绘制超参数K和评分之间的关系曲线。如图2所示,可以看出,K通常取小于20的整数。在本文的实验中,K取14。
Download:
|
|
在图3中,对比了KNN算法、SVM算法、聚类的KNN(cluster K-nearest neighbor,CKNN)算法[20]和本文提出的LRL-KNN算法在定位时的误差累计曲线,所有算法均使用RSS的平均值作为指纹,连续采样时间间隔t=1 s。
Download:
|
|
从图中可以看出,LRL-KNN算法的误差累计曲线的曲率相比其它三者表现得更好。新算法的平均定位误差为1.80 m,而KNN算法的平均定位误差为2.13 m,SVM的平均定位误差为2.36 m,CKNN算法的平均定位误差为2.20 m。
从表1中可以看出,LRL-KNN定位算法的平均定位误差为1.80 m,相比于KNN算法,平均定位精度提升了15.6%;相比于SVM算法,平均定位精度提升了23.7%;相比于CKNN算法,平均定位精度提升了17.4%。误差≤2 m所占比误差≤3 m所占比率都高于其它3种方法。从定位时间上看,LRL-KNN算法虽然在定位时间上略逊于CKNN,但是它的定位精度却比CNN高很多。
通过上面的分析与论证,得出如下结论:
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) |