«上一篇
文章快速检索     高级检索
下一篇»
  应用科技  2020, Vol. 47 Issue (4): 66-70  DOI: 10.11991/yykj.201912002
0

引用本文  

席志红, 占梦奇. 基于位置范围限定的WiFi-KNN室内定位算法[J]. 应用科技, 2020, 47(4): 66-70. DOI: 10.11991/yykj.201912002.
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.

通信作者

占梦奇,E-mail:17745164032@163.com

作者简介

席志红,女,教授,博士生导师;
占梦奇,男,硕士研究生

文章历史

收稿日期:2019-12-02
网络出版日期:2020-07-24
基于位置范围限定的WiFi-KNN室内定位算法
席志红, 占梦奇    
哈尔滨工程大学 信息与通信工程学院,黑龙江 哈尔滨 150001
摘要:针对传统的基于WiFi的最近邻(K-nearest neighbor algorithm, WiFi-KNN)室内定位算法精确度不能达到精准定位的需求的问题,本文提出了一种基于位置范围限定的K近邻(K-nearest neighbor based on the location range limit , LRL-KNN)室内定位算法。LRL-KNN算法通过利用用户的先前位置与WiFi指纹数据库中的参考点位置之间的物理距离组成的相关范围因子来缩放指纹距离,以此来减少定位的空间歧义性。尽管利用了先前的位置,但是该算法并不需要知道用户的确切移动速度和方向。与此同时,考虑到WiFi接收信号强度的时间波动性,将RSS直方图合并到距离计算中来减小时间波动带来的影响。实验结果表明:传统KNN算法的平均定位误差为2.13 m,新算法的平均定位误差为1.80 m,该误差在相同的测试环境下比传统的KNN算法减少15%。
关键词WiFi指纹数据库    接收信号强度    K-近邻算法    RSS直方图    范围因子    时间波动    累积分布函数    
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    

随着基于位置服务(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。对于第 $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算法

利用式(1)计算当前测试点 $l$ 的指纹数据与数据库中每个RP数据之间的指纹距离:

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

式中: ${f_j}$ 是测试位置 $i$ 处的第 $j$ 个指纹特征; $N$ 是可用指纹特征的数量。然后选择距离最小的 $K$ 个位置作为该位置的最近邻位置数据。最后,通过取所有 $K$ 个最近邻位置的平均值来确定用户的位置 $l$

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

由于用户的移动速度受到限制,并且在连续的测量时间内,用户无法从一个位置移动到另一个距离该位置很远的位置。故此,最简单的形式就是通过利用用户先前的位置信息,以该位置坐标为原点画圆,以期将最近邻数据限制在该圆内,该限制圆的半径可由用户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)$

式中: $W_l^i$ 是位置 $i$ 处的惩罚函数;M是数据库中RP的总数; $({x_{{\rm{pre}}}},{y_{{\rm{pre}}}})$ 是用户上一位置的坐标; $\sigma $ 是用户在连续的采样时间间隔 $t$ 里面可以移动的最大距离。例如,人们倾向于在室内环境中以0.4 ~2 m/s的速度行走(最大速度),并且用户位置每1 s更新一次(连续采样时间间隔 $t = 1s$ )。因此, $\sigma {\rm{ = }}{\nu _{\max }}\Delta t= {\rm{ 2}}$ m/s。惩罚函数具有高斯分布的形式,均值是前一位置坐标,标准差是 $\sigma $ 。在上述介绍中,仅仅需要获取用户最大的移动速度,而并不需要知道用户的确切移动速度和方向。用户的位置 $l$ 通过K个最近邻居的加权平均值 ${l_j}$ 确定,为

$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}}}} }}$

式中 $\overline{{D} _l^j}$ 是在式(2)中给出的修正欧几里得指纹距离。

为了进一步提升定位精度,本文在如下2个方面进行了改进:

1) 指纹组合:WiFi指纹方法中,指纹越稳定,定位精度越好。然而,由于动态变化的环境(例如人为阻挡和移动、来自其他设备的干扰、接收器天线方向等),客户端设备收集的RSS经常会经历较大的波动。因此,本文提出使用一组不同指纹的组合来确保每个位置具有足够的稳定性和独特的值。最常用的指纹是RSS的平均值,该平均值由于前面提到的影响而显出波动。相反,更可靠的指纹之一是一对AP之间RSS的平均差。Dong等[18]使用2个设备,即笔记本电脑和智能手机,在固定位置收集RSS。

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}}}$

式中: $n_{{\rm{total}}}^{i,j}$ 是在位置 $i$ 处第 $j$ 个AP的RSS扫描的总数; $n_{R{}_j}^i$ 是第 $j$ 个AP里,RSS的读数落入 ${R_j} - 0.5$ dBm和 ${{{R_j}}} + 0.5$ dBm( $R_{\min }^j \leqslant {R_j} \leqslant R_{\max }^j$ )区间的数量; $R_{\min }^j$ $R_{\max }^j$ 分别是第 $j$ 个AP的RSS值在该区间的最小值和最大值。因此,可以根据上述分析将式(1)改写为

$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 实验与分析

实验选择的位置是一个 $15\;{\rm{m}} \times 25\;{\rm{m}}$ 的矩形实验室。房间的西南角作为坐标原点。东方向是x轴的正方向,北方向是y轴的正方向,在房间的外围边缘部署了6个无线路由器组成6个AP。这6个AP节点的坐标分别为:(0,0),(12.5,0),(25,0),(0,15),(12.5,15),(25,15)。6个AP的SSID用于区分在同一位置处接收到的信号强度。房间被分成 $1 \times1$ 的网格,并且信号在采样设备上被接收。信号强度采样软件可在每个网格的顶点(共375个RP)上采样RSS值,每个RP持续3 min,然后在此期间将每个AP的RSS平均值作为AP在RP的信号强度值。在每个RP分别采集各个AP发射的RSS值。需要注意的是,实验人员在每个RP采集RSS信号强度时,由于工作人员在实验环境中测量时会干扰信号强度,所以采集数据时需要在每一个RP分别采集东南西北4个方向的信号强度,然后对其取平均值,最后将处理后的数据及RP位置坐标存入指纹数据库。室内RP的分布情况如图1所示。

Download:
图 1 室内RP分布情况

在测试阶段,对行人移动时的数据进行采集,当人在该区域环境内移动时,设备可以记录该行人在室内某位置处的AP指纹以及其他相关信息。

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

Download:
图 2 超参数K的曲线

图3中,对比了KNN算法、SVM算法、聚类的KNN(cluster K-nearest neighbor,CKNN)算法[20]和本文提出的LRL-KNN算法在定位时的误差累计曲线,所有算法均使用RSS的平均值作为指纹,连续采样时间间隔t=1 s。

Download:
图 3 距离的误差累计曲线

从图中可以看出,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 各个算法的误差比
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)