基于BL4.0 iBeacon技术的室内定位算法研究
2016-10-27蔡文郁周展业
蔡文郁,周展业,张 栋
(杭州电子科技大学电子信息学院,浙江 杭州 310018)
基于BL4.0 iBeacon技术的室内定位算法研究
蔡文郁,周展业,张栋
(杭州电子科技大学电子信息学院,浙江 杭州 310018)
通过BL4.0 iBeacon技术进行室内定位,分析了最邻近值算法和贝叶斯算法的不足,提出一种将上述两者优点进行融合的算法.首先,使用最邻近值算法的优选区域限定,缩小贝叶斯算法对指纹库的搜索范围,然后,采用贝叶斯概率法计算各个iBeacon节点的信号强度值集合在指纹库中每一位置参考点对应的条件概率值,概率最大的点就是待测点的预测位置.实验结果表明,使用该算法计算的坐标准确度比较高,坐标误差较小,能明显提高室内定位的精度.
室内定位;指纹库;蓝牙4.0;iBeacon
0 引 言
近年来,随着人们对位置服务需求的与日俱增,室内定位技术受到广泛的关注.目前应用于室内定位的技术主要有蓝牙、WiFi、超声波、Zigbee等.2014年,苹果公司推出了iBeacon技术,利用蓝牙4.0进行室内定位成了研究的热点之一.基于蓝牙4.0技术的蓝牙芯片凭借其功耗低、反应快、性能好、价格低廉而在众定位芯片中脱颖而出.另外iBeacon传播距离可达到100 m,使得基于蓝牙4.0室内定位范围得到了进一步的拓展.本文基于蓝牙4.0的室内定位方法,在分析现有指纹库室内定位算法的基础上提出了一种将距离确定型算法和概率分布型算法[1]融合的室内定位新方法,既能提高定位精度,又能降低算法复杂度.
1 iBeacon节点设计
iBeacon技术是苹果公司在IOS7系统之上所支持的移动设备室内定位新技术[2],基于iBeacon技术的室内定位原理示意如图1所示.本文研制的iBeacon节点采用TI公司的CC2541芯片方案[3],CC2541是TI公司推出的一款解决最新BLE 4.0的芯片,具有集成性高、功耗低等优点.
2 指纹库定位算法
指纹库定位算法是通过对室内多个iBeacon节点的信号强度进行实际测量,将得到的多个节点信号质量RSSI记录下来,建立该环境下的一个位置指纹库,然后在某一位置部署iBeacon接收设备,将实际接收到的RSSI数据与指纹库中数据进行比对,从而确认该设备所在的具体位置[4].指纹库定位原理如图2所示,分为算法训练阶段和位置定位阶段.
算法训练阶段也就是数据采集阶段,目的就是为了建立某一室内环境的信号强度“指纹库”,训练阶段采集的数据如表1所示.
图1 iBeacon室内定位原理示意图
图2 基于指纹库技术的蓝牙定位技术原理
位置对应坐标该点接收到的各个iBeacon节点的信号强度值S1(x1,y1)RSSI11,RSSI12,RSSI13,…,RSSI1i,…,RSSI1nS2(x2,y2)RSSI21,RSSI22,RSSI23,…,RSSI2i,…,RSSI2n…………Sj(xi,yi)RSSIj1,RSSIj2,RSSIj3,…,RSSIji,…,RSSIjn…………Sm(xm,ym)RSSIm1,RSSIm2,RSSIm3,…,RSSImi,…,RSSImn
位置定位阶段[5]就是通过在某一参考位置采集各个iBeacon节点的信号强度数据,利用相应的匹配算法,与“指纹库”进行对比和匹配,进而得到所需定位点的估计位置.
最近邻值算法是目前使用较成熟的距离确定性算法,原理如下:移动接收端在定位点获取各个iBeacon节点的信号强度,记作MUi={mui1,mui2,…,muin},其中n为iBeacon节点的个数,将此信号强度MUi与指纹库信号强度RSSIj={RSSIj1,RSSIj2,…,RSSIjn}进行匹配,从而确定该移动接收端所在的位置数据[6].再通过计算MU与RSSIij之间的距离,获取与移动接收端MU距离最短的指纹数据RSSIj,MU的估计位置即为指纹库中对应接收端所在的置信RSSIj的坐标.计算MU与RSSIj之间的距离如下:
(1)
其中,Di为移动接收端接收各个iBeacon节点的信号强度MU与指纹库中第i个指纹坐标的距离;mui为移动接收端接收第j个iBeacon节点发射的信号强度;RSSIij为指纹库中第i个指纹坐标点上接收到第j个iBeacon节点发射的信号强度;l是指纹库中参考点的个数,当q=1时,D为曼哈顿距离,当q=2时,D为欧几里得距离,本文设计中q值选择为2.
在概率性分布算法中,采用贝叶斯概率法计算各个iBeacon节点的信号强度值集合MU在指纹库中每一位置参考点对应的条件概率值,记作p(Li|MU),如下:
(2)
其中,L为指纹库中参考点的数目,p(Li)为移动接收端在该参考点Li上的概率大小,可认为p(Li)是均匀分布的,即p(Li)=1/L.由于在某一参考位置上,接收来自每一个iBeacon节点的信号强度是互不相关的,根据事件独立性可得出p(Li|MU)的表达式如下:
p(MU|Li)=p(mu1|Li)p(mu2|Li)…p(mun|Li).
(3)
根据概率分布可知,在同一位置上接收的不同信号强度的分布可以用高斯分布来表示,所以在该点的概率分布函数如下:
(4)
其中,μ为信号强度的平均值,σ为信号强度的标准差,x为实际接收到的强度值.最后根据选取条件概率最大的参考点作为待定位点的最终估计位置:
(5)
最近邻法的优选区域限定是根据和n个iBeacon节点距离的远近把需定位区域划分为n个区域.位置定位阶段中,当需定位节点进入定位区域后,可以实时获得RSSI位置指纹样例G,包含来自m个参考节点接收信号的强度值,即G=(G1,G2,…,Gm).将这m个RSSI值从大到小排序,找出最大RSSI值的Gm,从而确定出此最大值Gm所对应的参考节点,由此指纹数据库的查询范围缩小到了第m个参考节点附近的整个定位空间的1/n范围内.在算法训练阶段此范围内选取一系列采样点记作Si∈{S1,S2,…,Sn},通过把实时信号的位置指纹G和位置指纹库中的样例Si的距离进行比较,把最邻近的位置指纹所对应的点确定为定位点.利用欧几里德距离来度量两者的邻近性:
(6)
取其最小的欧氏距离,即定位节点的估计位置L=minD(S,Fi).算法步骤如图3所示.
最近邻值算法实现简单,但是误差较大;贝叶斯概率算法定位精度较高,但是算法复杂度较大,尤其在指纹库中参考点比较多的情况下.为了既能降低算法复杂度,又能提高算法的精度,本文将最近邻值算法和贝叶斯算法融合,使用最邻近值算法获取到与待测量位置点距离较小位置点的集合S,缩小贝叶斯算法对指纹库的搜索范围,然后利用贝叶斯概率算法对选取的集合S分别计算匹配概率,匹配概率最大的点就是待测点的预测位置.
图3 算法步骤
3 实验仿真
本文算法的测试实验环境选择在杭州电子科技大学第2教学楼中楼3楼走廊中进行,测试环境如图4所示,本文使用4个蓝牙iBeacon节点,分别为iBeacon节点1(UUID为XXXA0)、iBeacon节点2(UUID为XXXB0)、iBeacon节点3(UUID为XXXC0)、iBeacon节点4(UUID为XXXE0),定位接收信号设备使用的是红米手机定位终端界面,如图5所示.
图4 测试环境
图5 定位终端界面
测试环境选用实验室走廊,选取一段2.4 m×12 m的环境,并在墙壁上放置4个iBeacon节点,每块瓷砖的边长为60 cm.首先算法训练阶段,将所选区域坐标化,以每一块瓷砖作为一个单位进行坐标化,所选区域将转换成横坐标(0~20),纵坐标(0~4)的一个平面坐标系,同时选择20个位置作为参考点,如图6坐标系中黑色标记,用手机在每一个参考点上接收来自4个iBeacon节点的信号强度,将信号强度加上参考点的坐标来建立本文所需要的位置指纹库.
在固定位置同时连续接收来自4个iBeacon节点的信号强度,时间持续20 s,结果如图7所示.前8~10 s的时间中,信号接收波动很大,10 s之后波形趋于稳定,所以延长接收时间求均值的方法,可以减小信号波形的波动,提高数据准确性.完成指纹库的建立之后,根据指纹库中的数据分别计算出iBeacon 4个节点的信号强度平均值μ以及标准差σ,测得的指纹库如表2所示.
图6 测试环境坐标转换图
图7 同一位置接收到4个iBeacon节点的信号强度
参考点序号坐标iBeacon节点1iBeacon节点2iBeacon节点3iBeacon节点41(1,1)-68.5-83.4-87.2-73.22(1,3)-71.4-86.2-84.9-76.03(3,1)-63.1-82.4-85.1-70.34(3,3)-69.4-81.8-82.4-65.85(5,1)-68.1-77.4-81.9-69.46(5,3)-65.2-78.2-77.2-59.47(7,1)-67.4-73.4-80.4-71.28(7,3)-66.2-75.1-76.2-69.89(9,1)-75.2-73.2-79.8-73.110(9,3)-72.3-74.4-75.7-73.411(11,1)-76.2-67.4-77.4-74.212(11,3)-77.4-67.5-74.5-75.113(13,1)-81.2-62.4-74.3-77.014(13,3)-82.4-60.2-69.4-80.215(15,1)-83.5-68.2-68.3-83.516(15,3)-81.4-64.2-72.1-82.617(17,1)-85.2-72.1-65.2-84.118(17,3)-83.2-77.2-68.3-84.919(19,1)-87.8-76.6-72.1-85.320(19,3)-85.5-78.1-69.2-86.2平均值μ-75.5-74.0-76.1-75.7标准差σ7.27.26.37.2
本文选取10个非参考位置进行测量,测量结果如表3所示.通过式(1-5)的计算可得出融合算法坐标.其中偏差为实际坐标与融合算法所得坐标的距离差.
(7)
表3 待测位置点的坐标偏差
本文的融合算法是基于最临界为约束条件的概率分布求解待测位置的坐标,传统的概率分布算法中,如果使用数目为M的参考点获取N个iBeacon节点的信号强度时,传统的概率分布算法的复杂度为O(MN),本文的融合算法根据最临界条件选出K(K≪M)个符合临界条件的参考点,复杂度降低为O(KN).
4 结束语
本文基于BL4.0iBeacon室内定位技术,将最近邻值算法和贝叶斯理论算法融合起来,提出了一种新的指纹库定位方法.与传统概率分布算法相比,融合算法提高了定位准确度,减小了定位误差,同时也降低了算法的复杂度.在研究过程中发现,建立指纹库的过程比较复杂,如何更加简便地建立指纹库以及进一步提高定位的精度和实时性将是今后研究的方向.
[1]WARDA,JONESA,HOPPERA.Anewlocationtechniquefortheactiveoffice[J].PersonalCommunications,IEEE, 1997, 4(5): 42-47.
[2]尹贺.利用iBeacon技术实现签到和投票功能应用研究[J].福建电脑,2014 5:137-138.
[3]陈银溢.基于CC2541和LIS3DSH的计步器设计[J].机械工程与自动化,2014(6):96-98.
[4]齐双,王奇,黎海涛,等.传感器辅助的WiFi指纹室内定位方法[J].中国电子科学研究院学报,2015,10(1):102-106.
[5]YANGZ,ZHOUZ,LIUY.FromRSSItoCSI:Indoorlocalizationviachannelresponse[J].ACMComputingSurveys, 2013, 46(2): 25:1-25.
[6]FANGSH,LINTN.PrincipalcomponentlocalizationinindoorWLANenvironments[J].MobileComputing,IEEETransactionson, 2012, 11(1): 100-110.
Research on Indoor Positioning Algorithm Based on BL4.0 iBeacon Technology
CAI Wenyu, ZHOU Zhanye, ZHANG Dong
(SchoolofElectronicInformation,HangzhouDianziUniversity,HangzhouZhejiang310018,China)
BL4.0 iBeacon technology is introduced for indoor positioning. This paper analyzes the shortcoming of two traditional positioning algorithms: KNN algorithm and Bayesian algorithm, then proposes a combined algorithm of these two algorithms. First KNN algorithm is used to obtain the position set of which the distance to the position to be measured is smaller, and thus narrow search range of fingerprint database for Bayesian algorithm. After that match probability is calculated using Bayesian probabilistic algorithms for the selected position set. The biggest probability of matching point is exactly the predicted position of the target point. The experiment results verify that the accuracy of coordinate with the proposed algorithm is relatively high, and coordinate error is small, so as to improve indoor positioning accuracy significantly.
indoor positioning; fingerprint database; bluetooth 4.0; iBeacon
10.13954/j.cnki.hdu.2016.05.001
2016-01-07
浙江省自然科学基金资助项目(LY15F030018,LY16F030004)
蔡文郁(1979-),男,浙江慈溪人,副教授,电子系统集成.
TN925
A
1001-9146(2016)05-0001-05