基于iBeacon的环形定位优化算法研究

林信川， 林宏基

(1. 福建商学院 信息管理工程系， 福建 福州 350012； 2. 福州大学 数学与计算机科学学院， 福建 福州 350108)

0 引 言

随着通信技术和数据业务的飞速发展， 如何利用无线传感器网络(Wireless Sensor Networks， WSNs)[1]完成室内精确定位， 已成为当前的一个重要研究领域. 室内环境的复杂性往往会对定位精度产生较大的干扰， 是导致定位结果不准确或无法定位的主要原因. 基于测距(Range-based)算法和测距无关(Range-free)[2]算法是当前比较常见的两类定位算法， 二者的主要区别在于， 是否关注测量过程中不同节点间的角度或距离数据的关联性. RSSI， TOA， TDOA和AOA[3]等都是基于测距算法的代表， 其实现思路是在收集节点间距离或角度数据的基础上， 通过三边测量法、 三角测量法或极大似然估计法[4]等计算待测节点的位置. 此类算法虽对硬件有一定要求， 但定位精度较高. 测距无关算法中常见的有质心算法[5]、 Amorphous算法和DV-Hop算法[6]等， 此类算法在定位过程中通常利用网络对通性数据进行分析. 虽然此类算法对硬件的要求较低， 但因反射、 散射和绕射现象的存在， 往往造成较大的定位误差.

iBeacon[7]是由苹果公司于2013年发布的基于低功耗蓝牙4.0(BLE 4.0)[8]的技术， 在降低功耗和提升通信效率方面相较传统蓝牙技术存在明显优势. 支持低功耗蓝牙的iBeacon锚节点在无线传感网络中将通过既定的频率持续对外广播其UUID及位置信息， 所有支持BLE 4.0的设备均可接收到附近iBeacon锚节点的UUID， 并获取其推送的信息. iBeacon技术作为一种连接线下场景的短距离低功耗无线传输技术， 以其在低成本、 低功耗和高可移动性方面的优势， 被普遍用于各类室内定位场景.

目前， 国内外学者针对如何利用WSNs进行室内精确定位开展了大量研究， 但针对iBeacon锚节点进行定位的研究成果还比较有限. 文献[9]以距离倒数作为权重系数提出了定位模型， 并通过针对多点采集样本并进行样本去噪来建立基于iBeacon的无线指纹数据库， 给出了图书馆的位置服务示例. 文献[10]对信号环境与用户行为建模， 提出了一种基于iBeacon和Wi-Fi的位置空间模型定位技术和算法. 通过iBeacon、 空间位置及POI构建位置空间模型索引， 并根据用户的常态行为特征， 对空间位置和POI分别设置不同权重， 最后通过位置空间模型索引计算终端的具体位置. 该算法必须同时通过Wi-Fi设备和iBeacon设备进行定位， 误差范围基本能够控制在10 m以内. 文献[11] 技术方案中， 通过在室内空间均匀部署一定数量的iBeacon基站， 以距离倒数作为权重系数并利用加权的三环定位算法， 通过简化部分三环重叠相交的计算结果完成室内定位分析， 仿真误差控制在2.5 m以内.

本文在对目前系统中采用的常规环形定位算法进行分析的基础上， 针对三环定位可能出现的重叠情况和加权质心计算思路进行了比较完整的探讨， 通过提升与待测节点欧式距离较近的锚节点在定位过程中的作用， 结合基于测距的RSSI算法、 与距离无关质心算法和加权质心算法， 提出了一种新的定位算法思路， 并通过仿真环境对比验证了改进算法在定位精度和收敛速度方面的提升效果.

1 系统概述

某高校已构建了由iBeacon锚节点组成的课堂云考勤系统， 所有锚节点均基于BLE 4.0并配备DA 14850芯片， 均匀分布在所需定位的室内空间各处. 待考勤者通过在Android或iOS移动设备端安装该考勤APP应用， 并启用蓝牙和网络访问权限， 在iBeacon设备通信范围内即可由APP自动完成考勤并上传数据到云端. 云端的考勤数据可通过移动端APP、 微信公众号和Web浏览器进行查询和分享. 目前， 系统定位待考勤人员位置使用常规环形定位算法， 在定位精度和效率方面还存在优化空间， 如在待考勤者进入考勤区域30 s内定位平均误差达到3.1 m， 由此可能导致对待考勤者位置的误判， 从而生成误考勤数据.

2 iBeacon测距技术

每个iBeacon基站均可创建一个广播区域， 当支持BLE 4.0的设备进入该广播区域时， 通过设备端APP即可接收到iBeacon基站的UUID和位置信息.

iBeacon的通信过程即为无线信号传输过程. 自由空间传播模型[12]、 对数距离路径损耗模型[13]和对数-常态分布模型[14]是常见的无线信号传输损耗模型， 对数-常态分布模型相较前两者， 增加了一个随机变量用于评估不同环境对信号损耗的影响. 因此， 本文将使用对数-常态分布模型进行研究， 该模型可描述为

PL(d) =PL(d0)+10nlg(d/d0)+ε,(1)

式中：d和d0为待测节点位于不同位置时与锚节点间的欧式距离；PL(d)和PL(d0)分别为传输距离为d和d0时的信号强度， 单位为dBm；n为信号的衰减因子， 作为一个经验值， 其取值依赖于室内环境和建筑物的类型；ε为一个均值为0， 且同时服从高斯分布的随机变量.

若在定位过程中将d0固定为1 m， 那么PL(d0)即为距离iBeacon锚节点1 m处的接收功率， 对于采用确定芯片的iBeacon锚节点， 其值将为固定值. 可将以上传播模型简化为iBeacon在室内环境下的信号传播模型， 为

RSSI=T-10nlnd+ε,(2)

式中：T表示距离iBeacon锚节点1 m处的无线信号强度RSSI值，T和n需要通过对大量样本数据进行拟合后得到. 当前位置与不同锚节点间的RSSI值可通过蓝牙终端测得，d为通过计算得到欧氏距离.

3 环形定位优化算法

本文提出的IAWC(Improved Annular Weighted Centroid)算法指在与待测节点近邻的四个锚节点中， 任意选取三个分别构成定位分组. 与常规环形定位算法不同， 本算法将第三个环形圆心对应的锚节点也作为计算加权质心[15]坐标的一个要素， 利用三个相交环形圆心共同确定三环重叠区域的加权质心坐标. 利用三环圆心锚节点与待测节点间距离的倒数之和作为权重系数， 能够有效提升与待测节点较近的锚节点在定位过程中的重要性， 避免了传统算法中非关键锚节点对计算过程产生的干扰. 锚节点较待测节点距离越近， 路径传播损耗就越小， 对定位精度的影响就越明显. IAWC算法过程描述如下.

1) 首先确定与待测节点M(x,y)之间RSSI平均值最大的4个位置坐标已知的iBeacon锚节点， 假设按照距离由近至远分别为A(xA,yA)，B(xB,yB)，C(xC,yC)，D(xD,yD). 锚节点A,B,C,D到待测节点M间通过式(2)计算的欧式距离分别为dAM,dBM,dCM和dDM. 理想情况下4个锚节点与待测节点之间的关系可描述为

K=A,B,C,D.(3)

在实际环境中， 可假设锚节点A,B,C,D到待测节点M间的欧式距离与实际值间存在的误差为Δd， 即待测节点M到4个锚节点的距离分别位于[dAM-Δd,dAM+Δd], [dBM-Δd,dBM+Δd], [dCM-Δd,dCM+Δd]和[dDM-Δd,dDM+Δd]范围内. 若所有iBeacon锚节点均采用相同型号的硬件芯片， 则通过对大量的样本数据进行分析和去噪， 可以确定并显著减小Δd的值.

2) 将锚节点A,B和C作为一个分组， 分别以A,B为圆心，dAM±Δd和dBM±Δd为半径画环， 可得两个圆环的重叠关系如图 1 所示， 其中的重叠阴影部分即为待测节点可能位于的范围.

图 1 两环重叠情况Fig.1 Situations of two rings overlap

3) 以C为圆心，dCM±Δd为半径作第三个圆环， 可进一步缩小待测节点的定位范围. 在图 1(a) 中， 两环重叠的阴影区域为S1和S2， 第三个圆环与两环相交必与其中一块阴影区域存在重叠. 假设重叠区域为S1， 则第三个圆环与S1相交情况如图 2 所示， 待测节点即位于阴影区域的加权质心坐标处.

图 2 三环重叠情况ⅠFig.2 The first kind of situations of tricyclic overlap

4) 在图 2(a) 中阴影区域为类三角形， 其三个交点分别为E(xE,yE)，F(xF,yF)和G(xG,yG). 与常规环形定位算法将该类三角区域替换为S1的类四边形区域S1不同， 为提升算法精度， 需分别确定边界交点E，F和G的坐标值. 计算E坐标(xE,yE)的方法为

式中：dAE,dBE和dCE分别为E到锚节点A,B,C的欧式距离. 同理可得F(xF,yF)和G(xG,yG)的坐标值. 多数研究方法直接通过边界交点E,F和G的坐标， 并利用三角质心算法来计算该区域的三角质心坐标. 本文对该区域质心坐标的计算过程进行了加权系数优化[16]， 将权重系数设计为边界交点到各锚节点的倒数距离之和， 以此提升较待测节点较近的锚节点在定位过程中的作用. 优化后E的权重系数为

(5)

同理， 可得F和G的权重系数分别为

由此可得， 阴影区域的加权质心坐标即待测节点M1(x1,y1)的坐标， 为

5) 图 2(b)和(c)中阴影区域为类多边形. 当Δd值足够小时， 可将其阴影区域的质心坐标等同于图 1(a) 中类四边形区域S1的质心坐标， 如图 1(a) 所示. 假设该类四边形边界交点分别为T(xT,yT),U(xU,yU),V(xV,yV)和W(xW,yW)， 与E,F和G三点坐标的计算方式同理， 可得计算T坐标(xT,yT)的方法为

同理， 可得U(xU,yU),V(xV,yV)和W(xW,yW) 的坐标值. 根据式(5)和式(6)可得权重系数分别为ωT,ωU,ωV和ωW， 同理可得阴影区域的加权质心坐标即待测节点M1(x1,y1)的坐标为

6) 图1(b)中两环与第三个圆环重叠区域相交情况如图 3 所示.

图 3 三环重叠情况ⅡFig.3 The second kind of situations of tricyclic overlap

图 3(a)和图 3(b) 的三环重叠区域分别为类三角形和类四边形， 质心坐标的计算与图 2(a)和图 2(b)同理. 图 3(c)的三环重叠区域为横线标识区域所示的类多边形S3， 当Δd的误差值足够小时， 可将其阴影区域的质心坐标等同于加上两侧斜线阴影区域后构成的类四边形区域的质心坐标， 其计算过程与图 2(c) 同理.

7) 在图1(c)中两环与第三个圆环重叠区域相交情况如图 4 所示.

图 4 三环重叠情况ⅢFig.4 The third kind of situations of tricyclic overlap

图4(a)和图4(b)的三环重叠区域分别为类三角形和类四边形， 质心坐标的计算与图2(a)和图2(b)同理.

(10)

4 算法过程

根据如上改进定位算法的分析， 其算法步骤具体归纳为：

1) 将1个iBeacon锚节点置于测试场所中， 且在位于该锚节点0.5, 1.0, 1.5, …, 30.0 m处分别设置60个测试点， 锚节点将周期性地向待测节点广播其ID和位置信息；

2) 针对待测节点接收到的来自多个固定位置的广播数据包进行滤波和拟合， 确定iBeacon环境下的信号传播模型；

3) 通过多次采样确定欧式距离与实际距离之间的误差， 从而计算得到平均误差Δd， 并在后续算法过程中利用Δd构造呈圆环状的误差区域；

4) 增加待测节点附近固定测量区域内具有相同芯片型号iBeacon锚节点的数量， 并测量待测节点分别与各iBeacon锚节点间的RSSI值；

5) 利用测得的RSSI值通过步骤2)计算出待测节点与附近锚节点之间的欧式距离， 并将其按照升序排列， 优先选取与待测节点距离最近的4个坐标已知的锚节点；

6) 取其中任意3个锚节点， 根据三者坐标及步骤3)得到的平均误差Δd确定三环的距离和重叠情况， 通过图 2， 图 3 或者图 4 中的一种定位模型， 基于本文算法求得重叠区域的加权质心坐标；

7) 选取其他任意3个锚节点的组合， 重复步骤6)， 可得另外三个重叠区域的加权质心坐标；

8) 利用优化权重系数的思路， 针对步骤6), 7)中的4个加权质心坐标利用式(10)再次进行加权优化， 以确定通过四环定位后的待测节点坐标；

9) 将步骤8)中计算所得的待测节点坐标与其实际坐标进行比较， 以确定算法的误差.

5 仿真实验

5.1 测距及拟合

选择一个30 m×30 m的空旷房间作为测试场所， 进行iBeacon传播模型的测距和拟合实验. 首先将1个iBeacon锚节点置于测试场所中， 然后设置60个测试点， 分别位于该锚节点0.5,1.0,1.5,…,30.0 m处. 使用支持BLE 4.0的蓝牙设备在每个测试点采集100组RSSI样本数据. 反复完成针对50个配备相同芯片的锚节点的样本数据采集， 并将进行高斯滤波后样本数据的平均值作为该位置的RSSI值. 最后， 使用MATLAB R2015b对样本数据进行拟合， 拟合曲线如图 5 所示， 得到的拟合函数即iBeacon在室内环境下的信号传播模型， 为

RSSI=-17.7lgd-53.2.(11)

图 5 RSSI值与距离d拟合关系图Fig.5 Fitting diagram between RSSI value and d

5.2 实验论证及分析

在相同实验环境中， 分别均匀部署5, 10, 15, 20, …, 60个iBeacon锚节点， 同时在该场所内随机选取50个点作为待测节点位置. 在使用MATLAB R2015b进行IAWC算法仿真过程中， 式(2)中的信号衰减因子由拟合曲线如式(11)可知为n=1.77， 信道中的随机高斯噪声分布在5～10之间. 常规环形定位算法与本文提出的IAWC算法的仿真结果如图 6～图 8 所示.

图 6 平均误差随时间变化图Fig.6 Diagram of average error changing with time

在测试环境中布署5个锚节点， 并设定其通信半径为20 m， 从图6不难发现常规环形定位及IAWC两种算法的平均误差随时间变化均呈现出收敛的趋势， IAWC算法的误差在25 s左右已基本收敛于1.35 m， 而常规环形定位算法在40 s左右才呈现较为明显的收敛状态， 故IAWC收敛精度和收敛时机明显优于环形定位算法.

图 7 平均误差随通信半径变化图Fig.7 Diagram of average error changing with communication radius

图 8 平均误差随锚节点数量变化图Fig.8 Diagram of average error changing with the number of anchor nodes

通过逐步增加部署锚节点的通信半径， 在锚节点数量为5个且采样频率为30 s/次的环境中， 通过图 7 可知IAWC算法较常规环形定位算法表现出更高的定位精度和更快的收敛速度. 在通信半径达到12 m时误差范围已控制在1.5 m以内， 且随着通信半径的合理增加， 其误差范围还将进一步减小. 在通信半径达到20 m时IAWC算法已表现出明显的收敛迹象， 而传统环形定位算法在通信半径增加至30 m时才逐渐表现出收敛趋势.

在锚节点通信半径设置为30 m且采样频率固定为30 s/次的环境中， 通过增加锚节点的部署数量， 两种算法均能有效提升定位精度. 从图 8 可知IAWC算法较传统环形定位算法收敛速度更快， 在实验环境中锚节点部署数量达到10个时平均误差已收敛至1.5 m以内， 在达到40个时已呈现明显的收敛迹象.

6 结 语

在无线传感网络中， 如何有效提升算法定位精度和收敛速度是定位算法研究的关键内容. 本文基于某高校云考勤系统的定位需求， 在研究和分析常规环形定位算法的基础上， 通过将与待测节点最近邻的4个锚节点中的任意3个进行分组， 进一步深入探讨了三环相交的各种情况及其重叠区域的加权质心定位算法. 同时通过提升与待测节点较近的锚节点在定位过程中的重要性， 避免了传统算法中非关键锚节点对计算过程产生的干扰， 进一步优化了定位过程中的权重系数， 并再次利用优化的权重系数计算待测节点的坐标， 从而提出了IAWC算法.

仿真数据证明IAWC算法较之常规环形定位算法， 尤其在适当增大锚节点通信半径和增加锚节点部署数量的情况下， 能够表现出更高的定位精度和更快的收敛速度， 体现了IAWC算法的优势. 未来计划尝试采用误差因子做误差转换处理， 以期提升环形重叠区域加权质心的定位精度， 并将算法模型应用于云考勤系统中， 通过实际室内应用环境进一步验证其精度和性能.

[1] 杨文铂, 邢鹏康, 刘彦华. 一种基于自适应RSSI测距模型的无线传感器网络定位方法[J]. 传感技术学报, 2015(1)： 137-141.

Yang Wenbo, Xing Pengkang, Liu Yanhua. A positioning method of WSN based on self-adapted RSSI distance model[J]. Chinese Journal of Sensors and Actuators, 2015(1)： 137-141. (in Chinese)

[2] 郄剑文, 贾方秀, 李兴隆, 等. 基于组合测距的无线传感器网络自定位算法[J]. 传感技术学报, 2016, 29(5)： 739-744.

Qie Jianwen, Jia Fangxiu, Li Xinglong, et al. Self-localization algorithm based on integrated ranging in wireless sensor networks[J]. Chinese Journal of Sensors and Actuators, 2016, 29(5)： 739-744. (in Chinese)

[3] 张怡, 席彦彪, 李刚伟, 等. 基于卡尔曼滤波的TDOA/AOA混合定位算法[J]. 计算机工程与应用, 2015, 51(20)： 62-66.

Zhang Yi, Xi Yanbiao, Li Gangwei, et al. TDOA/AOA hybrid positioning algorithm based on Kalman filter in NLOS environment[J]. Computer Engineering and Applications, 2015, 51(20)： 62-66. (in Chinese)

[4] 钟丽鸿, 胡成全, 金京姬. 基于RSSI极大似然估计定位算法的分析与实现[J]. 吉林大学学报(理学版), 2014(3)： 556-560.

Zhong Lihong， Hu Chengquan， Jin Jingji. Analysis and implementation of maximum likelihood estimation positioning algorithm based on RSSI[J]. Journal of Jilin University(Science Edition), 2014(3)： 556-560. (in Chinese)

[5] 沈田, 温斌. 基于RSSI-距离区间映射的加权质心定位算法[J]. 电子测量技术, 2015, 38(5)： 42-44.

Shen Tian, Wen Bin. Weighted centroid localization algorithm based on RSSI-distance interval mapping[J]. Electronic Measurement Technology, 38(5)： 42-44. (in Chinese)

[6] 邱奉美, 游晓鹏, 李怀忠. 几种无需测距定位算法定位性能仿真研究[J]. 计算机仿真, 2014, 31(4)： 285-289.

Qiu Fengmei, You Xiaopeng, Li Huaizhong. Simulation study on localization performance of several range-free localization algorithms[J]. Computer Simulation, 2014, 31(4)： 285-289. (in Chinese)

[7] 张倬胜, 艾浩军, 马方方, 等. 基于iBeacon定位技术的智慧图书馆[J]. 电子产品世界, 2015(1)： 31-35.

Zhang Zhuosheng, Ai Haojun, Ma Fangfang, et al. Intelligent library system using iBeacon firmwares[J]. Electronic Engineering & Product World, 2015(1)： 31-35. (in Chinese)

[8] 卞合善. 基于蓝牙4.0低功耗室内定位研究[D]. 北京： 北京邮电大学, 2015.

[9] 张倬胜, 马方方, 薛静远, 等. 基于iBeacon的精细室内定位方法研究[J]. 地理信息世界, 2015(2)： 26-30.

Zhang Zhuosheng, Ma Fangfang, Xue Jingyuan, et al. Research on elaborate indoor positioning method based on iBeacon firmware[J]. Geomatics World, 2015(2)： 26-30. (in Chinese)

[10] 孔勇平, 钟致民, 杨广龙, 等. 一种基于iBeacon和Wi-Fi的位置空间模型定位方法[J]. 移动通信, 2015, 39(21)： 32-37.

Kong Yongping, Zhong Zhimin, Yang Guanglong, et al. A space model positioning method based on iBeacon and Wi-Fi[J]. Mobile Communications, 2015, 39(21)： 32-37. (in Chinese)

[11] 石志京, 徐铁峰, 刘太君, 等. 基于iBeacon基站的室内定位技术研究[J]. 移动通信, 2015, 39(7)： 88-91.

Shi Zhijing, Xu Tiefeng, Liu Taijun, et al. Research on indoor positioning technique based on iBeacon base station[J]. Mobile Communications, 2015, 39(7)： 88-91. (in Chinese)

[12] 陈雪冬, 陈硕红. 无线传感器网络功率控制的路由协议改进[J]. 自动化仪表, 2015, 36(1)： 66-69.

Chen Xuedong, Chen Shuohong. Improvement of routing protocol of wireless sensor networks based on power control[J]. Process Automation Instrumentation, 2015, 36(1)： 66-69. (in Chinese)

[13] 邵聪, 王磊, 李奇倚, 等. 面向车间布局的自适应LANDMARC算法[J]. 电子技术应用, 2015, 41(9)： 78-81.

Shao Cong, Wang Lei, Li Qiyi, et al. Adaptive LANDMARC algorithm for workshop layout[J]. Application of Electronic Technique, 2015, 41(9)： 78-81. (in Chinese)

[14] 李宗伟, 李起伟, 温良, 等. 井下电磁波超声联合定位方法[J]. 工矿自动化, 2016, 42(7)： 30-33.

Li Zongwei, Li Qiwei, Wen Liang. Underground joint localization method based on electromagnetic wave and ultrasonic[J]. Industry and Automation, 2016, 42(7)： 30-33. (in Chinese)

[15] 张勇, 徐小龙, 徐科宇. 基于加权质心法的WLAN室内定位系统[J]. 电子测量与仪器学报, 2015, 29(7)： 1036-1041.

Zhang Yong, Xu Xiaolong, Xu Keyu. Algorithm based on weighted centroid method for WLAN indoor positioning[J]. Journal of Electronic Measurement and Instrumentation, 2015, 29(7)： 1036-1041. (in Chinese)

[16] 林信川, 游贵荣. 基于iBeacon的室内定位算法优化研究[J]. 陕西理工大学学报： 自然科学版, 2017(3)： 67-73.

Lin Xinchuan, You Guirong. Study on optimization of indoor location algorithm based on iBeacon[J]. Journal of Shaanxi Shaanxi University of Technology(Natural Science Edition), 2017(3)： 67-73. (in Chinese)