一种基于iBeacon改进型KNN位置指纹室内定位算法

韩非 千博

摘 要：iBeacon有着体积小、功耗低、覆盖范围广等特点，因此其在室内定位领域有着非常明显的优势。文章提出了一种基于iBeacon的以定位点RSSI与参考点RSSI的欧氏距离倒数的归一化值作为权值的改进型KNN算法，同时提出了一种空间滤波算法，提升了算法效率。仿真实验结果表明，文章提出的改进型KNN算法在定位精度上相比原KNN算法提升了43.6%。此外，文章提出的空间滤波算法提高算法的运算速度约34%，使得在保证定位精度的同时，保证了定位的实时性。

关键词：iBeacon；室内定位；K近邻算法；位置指纹

室内定位技术被称为定位领域的“最后一公里”问题，有着非常广泛的应用前景，高精度的室内定位技术成为了近年来的热点问题。蓝牙是一种短距离的无线通信技术，利用短距离、低成本的无线连接替代电缆连接，从而为现存的数据网络和小型的外围设备接口提供统一的连接[1]。目前，蓝牙技术已经在日常生活中随处可见了，已经被广泛应用到了手机、平板电脑、笔记本电脑、蓝牙耳机等各种终端上。本文采用了使用蓝牙4.0规范的iBeacon作为定位的节点。iBeacon有着体积小、功耗低、覆盖范围广等特点，因此，其在室内定位领域有着非常明显的优势。

自从蓝牙标准规范颁布以来，利用蓝牙技术实现室内定位的研究一直都在进行，并且提出了很多基于蓝牙的定位方法，比较典型的有基于路径损耗模型的方法[2]、基于Cell-ID的方法[3]和基于指纹标定的方法[4]等。基于蓝牙的典型室内定位算法对比如表1所示。

以上3种基于蓝牙的典型室内算法的定位精度还不足以满足室内环境下基于位置服务的各种需求。本文针对基于指纹标定方法中常用的KNN算法进行了改进，提出了一种W-KNN算法。在最终确定定位点位置时，使用定位点RSSI与参考点RSSI的欧氏距离倒数的归一化值作为权值。仿真实验结果表明，与传统基于邻近算法（ K-Nearest Neighbor，KNN）的指纹标定室内定位算法相比，定位精度提升了37. 6%。同时，本文还提出了一种空间过滤的算法，将与定位点信号强度差距较大的参考节点进行滤除，将本文提出的W-KNN计算速度提升了34.5%。

1 基于iBeacon的位置指纹室内定位技术方案

综合考虑蓝牙4.0标准的覆盖范围和一般楼房室内的基本布局和形状，本文采用了如图1所示的室内定位拓扑结构。本文中进行室内定位区域的形状为长10.6 m，宽6m的矩形，在室内的4个角以及对角线交点上分别放置一个iBeacon节点，iBeacon使用的是蓝牙4.0标准规范其覆盖范围达到100 m以上，能够保证每个节点的信号都能覆盖整个室内定位区域。综合考虑定位精度和资源开销，在室内定位区域范围内每隔0.6 m设置一个参考节点，用于离线指纹库的建立。

位置指纹室内定位算法的过程分为离线指纹库的建立和在线实时定位两个阶段。离线阶段：在参考节点出采集每个Beacon基站的接收信号强度指示数据，得到的数据结合参考点的坐标信息组合成一组数据，作为这个参考点的指纹数据。按照相同的步骤采集其他参考点的指纹数据，建立指纹库。在线定位阶段：终端用户在定位区域内，实时接收每个iBeacon基站的接收的信号强度指示（Received SignalStrength Indication，RSSI）值，采用合适的匹配算法与指纹数据库中的数据比较，得到用户的位置估算坐标，最终完成对手机客户端位置的确定。

2 基于位置指纹的室内定位改进算法

通常在使用KNN算法进行指纹比对和筛选时，选出K个临近位置指纹后，将K个位置指纹的位置的均值作为最终的定位结果。这种计算方法忽略了K个位置指纹在最终位置计算中的贡献度问题。本文将终端实时定位到RSSI向量和KNN算法计算出的K个位置指纹的RSSI向量的欧式距离的倒数的归一化值作为最终确定位置的权值。同时，提出了一种基于RSSI距离特征，简单且易于計算的参考点过滤算法，提升改进型算法的计算速度。

2.1离线阶段指纹库的建立

室内定位区域内中选择K个参考点，在每个参考点出采集信号覆盖范围内的各个Beacon基站的RSSI，并将该参考点的地理坐标一起存入矩阵H：

其中：K为参考点的总个数；BKj为在参考点K处采集到第，个Beacon基站的RSSI；xk为参考点K处的横坐标；yK为参考点K处的纵坐标。

2.2线上实时定位阶段

用户处于定位区域内接收每个Beacon基站发出的RSSI并保存数据到向量h1：

hi=[bi b2 …bj …bn]

其中：b，为用户所在位置处采集到第，个Beacon基站的接收信号强度指示。本文在在线匹配阶段采用了经典的K最近邻匹配算法（ K-Nearest Neighbor，KNN）算法。KNN算法应用在基于指纹库的室内定位算法中，位置指纹法可以看作是分类或回归问题（特征是RSS向量，标签是位置），从数据中训练出一个从特征到标签的映射关系模型。在线阶段采集的RSSI数据向量h1，针对每一个元素分别计算各元素与指纹库中每个参考点的RSSI向量s1，s2…，SM的欧氏距离，并对欧氏距离进行排序，选取较小的K个位置指纹（一个指纹是指一个参考点对应一个RSSI向量）。将K个位置指纹的坐标均值作为最终的定位结果。 直接使用位置指纹的坐标的均值作为定位结果，虽然计算方便，但是却没有区分出KAI位置指纹在位置定位中的贡献度。本文在选取K个位置指纹后，引入在线阶段的RSSI数据向量h1与每个选取的位置指纹RSSI向量Sk的欧式距离的倒数作为计算最终定位位置的权重w：

其中，d为向量欧式距离的倒数。此处将权值做了归一化处理。最终定位位置的计算公式为

2.3空间滤波算法

本文针对现有KNN匹配算法带来的计算量较大进行了改进，缩短了定位时间，提高了定位的实时性。基于空间滤波的KNN算法的步骤如下：

首先对每一个参考点设置空间滤波阈值。

RSSI×（1- 10%）≤/3u≤RSSI×（1+10%）

其中：RSSL，表示在參考点i处收集到Beacon基站j处的RSSI；

i表示第i个参考点，j表示第l个Beacon基站。

（2）实时定位阶段用户收到的来自第，个Beacon基站的接收信号强度指示6与阂值比较。如果bj在此阈值范围内，将认为此值没有产生畸变，现场临时环境变化少，则保留接收此基站RSSI的参考点。如果接收信号强度指示6，不在此阈值范围内，则说明第j个Beacon基站此时受现场环境突变影响较大，即滤掉接收此基站RSSI的参考点，不参与后期的KNN处理。

经过Beacon基站的过滤，由步骤（2）得，若第，个Beacon基站被过滤掉，则指纹库中在任意一个参考点处采集到第，个Beacon基站的指纹数据也不参与KNN算法匹配。计算时将减少KXN个公式的平方计算。K是参考点的数量，N是被过滤掉的Beacon基站总数量。同时也是把相应参考点向量中和这个基站有关的元素过滤掉，可避免实际场景中突发事件下各个Beacon基站产生的负面影响，滤掉没有起到定位作用的基站。同时减少了KNN算法的计算量，加速数据的处理过程，缩短定位时间。现场环境突变条件下，提高了基于指纹库室内定位算法的定位精度和实时性。

3算法仿真

本文的仿真以验证算法为主，且只验证算法层面的有效性与合理性，使用MATLAB建立仿真环境平台。设置室内区域大小为6 mX10.8 m的实验室环境，部署5个Beacon基站分别位于实验室的4个角落和中心位置。5个Beacon基站分别为Beacon 9454 （0，0），Beacon～9556 （6，0），Beacon一9102（3， 5.4）， Beacon一7063 （0， 10.8）， Beacon一8C79 （6，10.8）。参考点的选择要求是每隔0.6 m的长度标定一个参考点，共标定180个参考点。分别在每个参考点处采集5个Beacon基站RSSI值。实验室实际场景下设置参考点和Beacon基站的分布，如图l所示。

模拟实验室环境，在定位区域内随机分布一个待定位点，使用KNN算法、W-KNN算法、基于空间滤波的WKNN匹配算法进行100次仿真实验，结果如图2所示。

基于空间滤波的改进型KNN算法定位误差如图3所示。分析实验所得数据，基于空间滤波的改进型KNN算法的平均定位误差为0.101 0 m，相比传统KNN算法定位精度提升了43.6%。同时，空间滤波WKNN算法运算速度相比WKNN算法提升了约34%。

4结语

基于iBeacon平台，本研究提出了一种精度高，实时性好的基于空间滤波的改进型KNN算法。主要改进了KNN中K近邻对最终计算结果的贡献度区分问题，以及提升了算法的效率，增强了算法的实时性。本研究在Matlab2016平台上验证了算法的有效性。仿真实验结果表明，本文提出的改进型KNN算法在定位精度上相比原KNN算法提升了43.6%。此外，本文提出的空间滤波算法提高算法的运算速度约34%，使得在保证定位精度的同时，保证了定位的实时性。

[参考文献]

[1]BHAGWAT P.Bluetooth： technology for short-range wireless apps [J].IEEE Internet Computing， 2001 （3） ： 96-103.

[2]ANASTASI G. BANDELLONI R. CONTI M. et aI.Experimenting an indoor bluetooth-based positioning service[C].Distributed

Computing Systems Workshops. 2003. Proceedings. 23rd International Conference on. IEEE. 2003 ： 480-483.

[3]RODAS J， ESCUDERO C J. IGLESIA D LBayesian filtering for a bluetooth positioning system[C].Wireless Conununication Systems.

2008. ISWCS'08. IEEE International Symposium on. IEEE. 2008 ： 618-622.

[4]SUBHAN F. HASBULLAH H. ROZYYEV A. et al.lndoor positioning in bluetooth networks using fingerprinting and lateration

approach[C].lnformation Science and Applications （ ICISA ）， 2011 International Conference on. IEEE. 2011： 1-9.