相关性匹配蓝牙信标位置指纹库的室内定位*

王艳丽，杨如民，余成波，孔庆达

(重庆理工大学 远程测试与控制研究所，重庆 400054)

相关性匹配蓝牙信标位置指纹库的室内定位*

王艳丽*，杨如民，余成波，孔庆达

(重庆理工大学 远程测试与控制研究所，重庆 400054)

针对K近邻算法(KNN)在对偏向于某个样本点的未知点进行三角质心定位时定位精度变差的情况,提出了应用相关系数去匹配蓝牙信标iBeacon位置指纹库的室内定位算法。通过比较待定位点和位置指纹库中参考样点的相似程度，并进行数据差异显著性检验，来检验采集的待定位点数据与指纹库数据是否显著相关，然后取相关性较高的样本点进行加权平均匹配定位。实验结果显示，相关系数匹配位置指纹库算法可将2 m以内的定位精度从65%提高到92%，相较于传统的KNN匹配定位算法有着定位精度高、计算量小、定位时间短等优势。

室内定位；蓝牙信标；位置指纹库；相关系数；显著性检验

1 引 言

近年来，无线通信网络、移动互联网及智能终端的广泛应用，带动了基于地理位置信息服务(Location Based Service，LBS)产业的快速发展。虽然室外使用较多的是GPS定位，但在室内、地下、高楼林立的市区等场景中，GPS定位性能变差，不再适用。在低功耗、长距离、低成本定位上，基于蓝牙信标iBeacon的定位系统相比GPS存在优势，且大多智能设备中都有蓝牙功能，故蓝牙信标iBeacon室内定位技术受到极大推崇。

目前的室内定位算法主要是基于接收信号强度指示(Received Signal Strength Indication，RSSI)的测距室内定位[1]和基于信号指纹库的匹配定位[2]。然而，简单的RSSI测距定位无法满足室内环境较复杂的情况[3-4]，故大多采用基于信号指纹库的匹配定位。典型算法[5-7]有K近邻算法(K-Nearest Neighbor,KNN)、贝叶斯法、神经网络算法(Artificial Neural Networks,ANNs)、支持向量机(Support Vector Machine,SVM)等，但容易实现的是KNN算法。

文献[8]结合RSSI路径损耗特征进行了限定区域的KNN定位，然而此方法前期需对数据进行大量处理分析，定位精度依赖于区域的划分。文献[9-10]都用了聚类分析，不同在于一个是主分量分析，然后进行模糊C均值处理，主成分提取和C均值处理比较繁琐；一个是利用最邻近点的几何特性建立约束条件进行聚类，约束准则的选取需要不断验证，定位精度也不是很高。上述几种算法均比较复杂，耗时长，定位的精度也依赖于各自的分类标准，并且利用KNN进行相似取平均处理，都忽略了未知点偏向于某个样本点时定位精度变差的情况，所以总体定位精度不高。

本文直接从从未知点与参考样点RSSI向量相似度出发，选择了算法较为简单且易实现的相关性分析来进行iBeacon信号RSSI指纹库的匹配，并用显著性检验再一次验证，以此避免分类标准的制约以及未知点偏向于某个样本点时KNN算法带来的误差，提高匹配准确度，进而提高定位精度。

2 基于iBeacon的室内定位系统设计

本系统包括一定数量的iBeacon基站(蓝牙4.0低功耗模块)、带有蓝牙的终端设备(智能手机)、服务器Web端(地图定位)以及数据存储中心，模型如图1所示。

图1 基于iBeacon的室内定位系统Fig.1 The indoor positioning system based on iBeacon

在室内空间均匀部署一定数量的蓝牙4.0低功耗模块，当智能手机端进入室内时便可接收到其对应的iBeacon信息，包括蓝牙4.0模块对应的通用唯一标识符(Universally Unique Identifier，UUID)、识别某个定位区域的区域号Major、识别区域内各个iBeacon的单号Minor以及RSSI值，并对接收到的RSSI进行滤波去噪处理。

本文采用RSSI位置指纹数据库相关性匹配定位技术，需建立RSSI位置指纹库，主要分为以下两个阶段：

(1)离线阶段(也称训练阶段)

设定每次采集数据的时间间隔和持续时间，按照每间隔1 m作为参考点，同一位置进行多次多方向采点，并通过Android手机端App将采集的iBeacon信息上传到服务器数据中心，与提前绘制好的室内环境地图结合，构建实验环境下iBeacon信号的位置指纹数据库。

(2)在线阶段(也称实时定位阶段)

智能手机端进入定位服务区的某个位置，与服务器建立Socket通信，发出定位请求并将此时采集到的待定位点的iBeacon信息按照一定的时间间隔传递给服务器(图1的过程1)，服务器从位置指纹数据库调用信号指纹库进行匹配(图1的过程2、3)，匹配算法采用本文提出的基于相关性匹配位置指纹库的算法来得到此时待定位点的位置信息(图1的过程4)，并在地图上显示出这个点。

3 相关性匹配定位算法

相关性分析一直以来都是统计信号处理领域的热潮[11]。1970年，美国地理学家Tobler的第一定律(Tobler's First Law,TFL)认为[12]，任何事物都存在空间相关，距离越近，其空间相关性越大，反之则越小。典型相关分析(Canonical Correlation Analysis)就是利用综合变量对之间的相关关系来反映两组指标之间的整体相关性的多元统计分析方法[13]。基于位置指纹库匹配的室内定位，正是探究采集的目标点数据与指纹库参考点数据之间的匹配程度，即相关程度，从而取相关性较高的参考样点的位置进行加权平均求目标点所在位置。

3.1 相关系数

相关系数是表征变量之间相关程度的量，需要计算两组变量各自的离差。先求得各变量与其本身均值的离差，然后将对应的两个离差相乘，即为相关系数， 如公式(1)所示:

(1)

式中:X、Y为两组变量序列，且序列长度相等均为m。相关系数在-1～1之间，即-1≤γ≤1，当γ=1时，两组变量是正线性相关；当γ=-1时，两组变量是负线性相关。若0<|γ|<0.3，没有相关性；若0.3≤|γ|<0.5则为低度相关；若0.5≤|γ|<0.8则为中度相关；若0.8≤|γ|<1则为高度相关。

在iBeacon位置指纹库(LocationFingerprintDataBase，LFDB)匹配定位中，每个参考点的RSSI指纹信息R都和其位置信息L对应，LFDB的组成元素DBE(DataBaseElement)即为DBE=(L,R)。假定定位服务区中均匀了布置M个iBeacon基站，则在每个参考点L(x,y)处,可采集到M个iBeacon信号的RSSI值，同时可以采集到每个iBeacon基站独有的与位置相关的信息。若采集N个参考样点，则位置指纹库具有N个iBeacon参考指纹的集{R1,R2,R3，…,RN}，每个iBeacon指纹都和位置集合{L1,L2,L3，…,LN}中的位置相对应。参考iBeacon指纹R和目标点采集信息T可用如下矩阵表示：

(2)

式中：idi是第i个iBeacon基站独有的信息，ri是参考点接收到的第i个iBeacon基站的RSSI值，dri即在待定位点处采集到的第i个iBeacon基站的RSSI值。

在定位匹配过程中，需探究采样点与参考点各自在第i个iBeacon信号下的RSSI值的相关程度，若对应的iBeacon基站下的RSSI相关程度高，则其位置坐标相关程度高，即通过变量对之间RSSI的相关关系来反映变量对之间整体的相关性。

结合公式(1)可以推出采样点与参考点相关系数

(3)

3.2 显著性检验

统计假设检验(Test of Hypothesis)，即显著性检验(Significance Test)，是一种比较样本与总体参数间存在显著差异和存在不显著差异的方法。思路是结合具体情况对未知的或不完全知道的总体参数(均值、方差、比例)或分布形式(大样本正态分布，小样本t分布)，作出某种假设，在一定概率意义下，得出接受或拒绝原假设的结论。当样本容量小于30时，为小样本，多采用t-检验；大样本则一般采用u-检验 。

t统计量如下：

(4)

其中：

(5)

假设所检测数据存在不显著差异的概率为P，设定显著水平α，即判断实验误差的概率界限。一般α取0.05，当P≤5%，利用“小概率事件实际不可能性原理”，判断存在显著差异。更精确判断时，α取0.01，即P≤1%，判定存在极显著差异。若试验中可变因素太多且难以控制，误差大，则显著水准选低些，α值取大些；反之，如果试验中耗费太大，对精确度要求比较高，则显著水准选高些，α值取小些。

在iBeacon位置指纹库采点中，影响因素较多，采样的时间、方向，天气的阴晴都会有影响，故将判断标准稍微放宽，选择α=0.05进行显著水平判断。

自由度df=M-1，实验中M取12，df取11。根据自由度查表获取理论的临界值。在tα-检验中，如果双侧检验显著，则单侧检验一定显著；反之则不然，故选择t双侧检验。

双侧：

t0.05/2(M-1)=2.201，t0.01/2(M-1)=3.106。

单侧：

t0.05(M-1)=1.796,t0.01(M-1)=2.718。

将公式(4)中得到的t统计量与理论临界值2.201比较，当|t|<2.201，这两组数据无显著差异，即待定位点与参考点接近；当|t|>2.201，这两组数据有显著差异，即待定位点与参考点相隔较远。

由于位置指纹库中具有N个iBeacon参考指纹的集合{R1,R2,R3，…,RN}，每个参考指纹中有M个RSSI值，可得N个相关系数，并对之进行显著性检验，取相关程度γ满足0.8≤|γ|<1的k个参考样点，取其位置坐标进行加权平均即可得所求点的位置，公式如下：

(6)

4 实验结果与分析

4.1 实验环境部署

在8 m×14 m的实验环境中，有一个办公隔间，20个小办公分隔区，室内环境较复杂，故按照对称方式均匀布置12个iBeacon基站(iBeacon分布如图2所示)，使得iBeacon信号覆盖整个室内环境。由于采集的RSSI在1 m内的波动不大，故以横纵方向上每间隔1 m作为参考点。实验显示时间、方向会引起RSSI的波动，故在每个参考点上的分不同方向时间采集了4次共N=438个样本指纹。

图2 实验环境下的iBeacon分布Fig.2 The arrangement of iBeacon in lab

采集信号时，需采集该位置下所接收到的iBeacon信息，包括UUID、Mac地址、Major、Minor及信号强度值RSSI。iBeacon广播功率全部设为0 dBm，UUID为FDA50693-A4E3-4FB1-AFCF-C6EB07647825，如表1所示。

表1 iBeacon节点配置表Tab.1 iBeacon nodes configuration table

在构建iBeacon位置指纹库数据时，除了接收到的各个iBeacon基站对应的RSSI外，还需添加二维位置坐标(x,y)，如表2所示。由于实际建指纹数据库时，每个测试点上的RSSI值采样了4次，故表2对应的RSSI有4次数据值。

表2 坐标为(500 cm,800 cm)的样本点采集的指纹库Tab.2 The fingerprint database of the sample point at (500 cm,800 cm)

4.2 Android手机端定位测试结果

Android手机端开发的App如图3所示。在智能手机端先安装App，将建好的位置指纹库信息导入到BLE数据库，室内环境地图导入室内定位测试，如图4所示。

图3 Android手机端的AppFig.3 The App of android phone

图4 BLE数据库和室内定位测试Fig.4 The database of BLE and indoor positioning test

在实验环境中，随机取30个测试点，将Android手机端分别放在该测试点上，可获取其对应的iBeacon信息(图4右列表中)，用相关性匹配指纹库算法与位置指纹库进行匹配，找出相关性较高的参考点加权平均得该测试的坐标，同时在定位地图上显示出此点，如图4右。

4.3 实验结果分析

同时，对其进行传统的KNN匹配定位。取两种算法下得到的坐标值，分别与实际坐标值进行定位误差分析，比较结果如图5所示。

图5 KNN匹配定位与相关性匹配定位误差分布情况Fig.5 The positioning error distribution of KNN algorithm and correlation positioning algorithm

图5显示，相关系数匹配定位误差大体上在2 m以内，很少有在3 m以外的，而传统的KNN匹配定位误差集中在1 ～3 m，还有一部分在3 m以外，具体分析如表3所示。

表3 KNN匹配定位与相关性匹配定位误差对比Tab.3 The positioning error comparison between KNN algorithm and correlation positioning algorithm

相比于常用的KNN匹配指纹库定位算法，相关系数匹配指纹库定位算法可将2 m内的定位精度从65%提高到92%，使整体定位精度得到提升，说明相关系数匹配指纹库定位算法能够有效地提升定位精度。

5 结束语

本文针对KNN算法进行信号位置指纹匹配时，自身存在的未知点与某个样本点较邻近时，取K个较邻近的进行均值定位，精度变差的情况,同时结合当前改进算法均比较复杂、耗时长、定位的精度也依赖于各自的分类标准实际情况，将相关性匹配应用到iBeacon室内定位系统中。实验结果显示，相较于传统的KNN匹配定位算法，相关性匹配定位定位精度更高，大体上在2 m内，且算法易实现，计算量小，定位时间更短，可广泛应用于室内定位领域，如机场、医院、展览馆、矿井、大型商场及智能家居等。但本系统仍有需要改进的地方以及解决的难题：一是iBeacon节点数目及布置方式对于室内定位精度的影响；二是采集iBeacon信号时，时间、方向及温度的变化都会带来信号的波动，故在建立动态性位置指纹库上还需进一步研究。

[1] 詹杰,吴伶锡,唐志军.无线传感器网络RSSI测距方法与精度分析[J].电讯技术,2010,50(4):83-87. ZHAN Jie,WU Lingxi,TANG Zhijun.Ranging method and accuracy analysis based on RSSI of wireless sensor network[J].Telecommunication Engineering,2010,50(4):83-87.(in Chinese)

[2] 卢恒惠,刘兴川,张超,等.基于三角形与位置指纹识别算法的WiFi定位比较[J].移动通信,2010(10):72-76. LU Henghui,LIU Xingchuang,ZHANG Chao，et al.Compare the triangle location algorithm and the fingerprint recognition algorithm based on WiFi positioning[J].Mobile Communication,2010(10):72-76.(in Chinese)

[3] 陈锡剑,程良伦.基于RSSI的功率匹配定位算法的研究与实现[J].传感技术学报,2013(5):709-714. CHEN Xijian,CHENG Lianglun.Study and implementationof power match algorithm based on RSSI[J].Chinese Journal of Sensors and Actuators,2013(5):709-714.(in Chinese)

[4] WANG Y,YE Q,CHENG J,et al.RSSI-based blue-tooth indoor localization[C]//Proceedings of 2015 11th International Conference on Mobile Ad-hoc and Sensor Networks(MSN).Shenzhen:IEEE,2015:165-171.

[5] FRANCE S L,CARROLL J D,XIONG H.Distance metrics for high dimensional nearest neighborhood recovery:compression and normalization[J].Information Sciences,2012,184(1):92-110.

[6] LIANG X,GOU X,LIU Y.Fingerprint-based location positoning using improved KNN[C]//Proceedings of 2012 IEEE International Conference on Networking Infrastruct.Digital Content(ICNIDC).Beijing：IEEE,2012:57-61.

[7] YE M,MING C P,LI C G.The algorithm of thinning fingerprint with BP neural network[C]//Proceedings of the 26th Chinese Control Conference.Zhangjiajie：IEEE,2007:145-148.

[8] 莫倩,熊硕.基于蓝牙4.0的接近度分类室内定位算法[J].宇航计测技术,2014,34(6):66-70. MO Qian,XIONG Shuo.Close degree classification of indoor positioning algorithm based on bluetooth 4.0[J].Journal of Astronautic Metrologry and Measurement,2014,34(6):66-70.(in Chinese)

[9] 都伊林.一种模糊聚类KNN位置指纹定位算法[J].微型机与应用,2012,31(23):55-58.

DU Yilin.A fuzzy clustering KNN location fingerprint p-ositioning algorithm[J].Microcomputer & Its Applications,2012,31(23):55-58.(in Chinese)

[10] 刘春燕,王坚. 基于几何聚类指纹库的约束KNN室内定位模型[J].武汉大学学报(信息科学版),2014,39(11):1287-1292. LIU Chunyan,WANG Jian. Based on the geometric clustering fingerprint constraints KNN indoor positioning model[J].Geomatics and Information Science of Wuhan University,2014,39(11):1287-1292.(in Chinese)

[11] 胡晖,许浩峰,包伟华.基于相关性算法的超声波回波定位[J].自动化仪表,2015(10):96-98,102. HU Hui,XU Haofeng,BAO Weihua.Ultrasonic echo location based on correlation algorithm[J].Process Automation Instrumentation,2015(10):96-98,102.(in Chinese)

[12] 李小文,曹春香,常超一.地理学第一定律与时空邻近度的提出[J].自然杂志,2007,29(2):69-71. LI Xiaowen,CAO Chunxiang,CHANG Chayi.The first law of geography and spatial temporal proximity[J].Chinese Journal of Nature,2007,29(2):69-71.(in Chinese)

[13] 樊祜广.港口与区域经济互动发展研究[D].武汉:武汉理工大学,2012. FAN Huguang.The interactive development between port with the regional economic[D].Wuhan:Wuhan University of Technology,2012.(in Chinese)

[14] 张凤菊,刘晓娟,赵丽平,等.数据差异显著性检验[J].农机使用与维修,2012(4):51-52. ZHANG Fengju,LIU Xiaojuan,ZHAO Liping,et al.Data difference significance test[J].Agricultural Mechanization Using & Maintenance,2012(4):51-52.(in Chinese)

Indoor Localization of Bluetooth Beacon Position Fingerprint Based on Correlation Algorithm

WANG Yanli，YANG Rumin，YU Chengbo，KONG Qingda
(Institute of Remote Test and Control,Chongqing University of Technology,Chongqing 400054,China)

K-Nearest Neighbor algorithm,or“KNN”for short,often simply uses triangle centroid algorithm to locate.However,once the backlog site is close to a certain sample point,the accuracy of location will be greatly affected.Therefore,this paper proposes a correlation coefficient matching iBeacon position fingerprint algorithm.Firstly,through comparing the similar degree between undetermined point and a certain sample point of received signal strength indication(RSSI) fingerprint,it uses the test of data difference significance to test whether the backlog site data and fingerprint data is significantly correlated.Then,it takes the weighted average of high correlation sample points to get the result.Experimental results show that the positioning accuracy within 2 m can be increased from 65% to 92% with the correlation coefficient matching fingerprint algorithm.Compared with traditional KNN localization algorithm,the proposed correlation matching algorithm has higher positioning precision,smaller calculation amount,and shorter positioning time.

indoor positioning;bluetooth beacon;position fingerprint;correlation coefficient;significance testing

2016-07-11；

2016-10-09 Received date:2016-07-11；Revised date：2016-10-09

国家自然科学基金资助项目(61402063)；重庆市科技人才培养计划(新产品研发团队)项目(CSJC2013KJRC-TDJS40012)；重庆市高校优秀成果转化资助项目(KJZH14213

10.3969/j.issn.1001-893x.2017.02.004

王艳丽，杨如民，余成波，等.相关性匹配蓝牙信标位置指纹库的室内定位[J].电讯技术，2017,57(2):145-150.[WANG Yanli，YANG Rumin，YU Chengbo，et a.Indoor localization of bluetooth beacon position fingerprint based on correlation algorithm[J].Telecommunication Engineering,2017,57(2):145-150.]

TN967.2

A

1001-893X(2017)02-0145-06

王艳丽(1989—)，女，湖北襄阳人，2014年获工学学士学位，现为硕士研究生，主要研究方向为室内定位算法；

Email:1476646282@qq.com

杨如民(1963—)，男，重庆人，教授、硕士生导师，主要研究方向为无线传感器网络、可再生能源的开发及利用；

Email:yangrumin@163.com

余成波(1965—)，男，江西波阳人，教授、硕士生导师，主要研究方向为远程测试与控制技术、信号与信息处理；

Email:yuchengbo@cqut.edu.cn

孔庆达(1991—)，男，山西吕梁人，2014年获工学学士学位，现为硕士研究生，主要研究方向为室内定位技术。

Email:1159754385@qq.com

*通信作者：1476646282@qq.com Corresponding author：1476646282@qq.com