2. 北京邮电大学 信息与通信工程学院, 北京 100876
针对密集物联网环境下的信号碰撞问题，提出了一种分组及时应答多个节点、降低碰撞率的广播协议.通过多周期迭代分析碰撞概率，建立了理论模型，有效地解决了大规模传感器节点并发广播信道碰撞严重的问题.使用蒙特卡洛法仿真评估延迟、容量指标，分析了影响性能的关键参数，模型计算结果与仿真结果一致.与无应答式的广播协议相比，所采用的广播应答机制可以高效确认，降低了23%的网络延迟和90%的广播碰撞，并使系统容量提升1倍.
2. School of Information and Communications Engineering, Beijing University of Posts and Telecommunications, Beijing 100876, China
Aiming at the problem of signal collision in the dense Internet of Things environment, an anti-collision broadcasting scheme was proposed which can group respond to multiple nodes in time and reduce the collision rate. The collision probability was analyzed by multi-period iteration, and a theoretical model was established which effectively solves the serious channel collision in concurrent broadcasting of large-scale sensor nodes. Monte Carlo simulation was created to evaluate indicators such as latency, capacity, and power consumption. The key parameters affecting the performance were analyzed. The model calculation results are consistent with the simulation results. Compared with the unresponsive broadcasting protocol, the broadcast response mechanism can effectively confirm, reduce 23% network delay and 90% broadcast collision, and increase the system capacity by 100%.
iBeacon技术解决了设备和设备间自动发现和协作的困难，具有低功耗、定位精确、较大距离覆盖等优点[1].基于BLE(the Bluetooth low energy)技术广播数据，智能移动终端等设备能够快速发现信息点，触发特定的应用，实现100 m内的无线通信、定位和交互[2].在商城、图书馆、博物馆、会议场馆、医院等开放区域有丰富的应用前景.研究防碰撞广播协议，可减少网络延迟和提高节点容量，对密集并发的投票、签到等物联网应用有重要意义.
提出了一种基于iBeacon的防碰撞广播协议方案，主节点分组并行广播应答多个从节点信息，从节点及时确认停止广播，可以有效降低广播碰撞率.可划分不同网段，支持多区域重叠网络划分，相互隔离和识别.采用低功耗蓝牙技术无连接模式的网络设备，包含广播扫描2个状态，针对节点状态切换过程，进行多个时间周期迭代分析，建立防碰撞广播网络的理论分析模型，推导出系统的关键参数和指标.给出仿真结果和分析，论证理论模型.
1 iBeacon技术现状和研究进展低功耗蓝牙技术得到了IOS、安卓等主流手机操作系统的支持，智能手机可全面支持低功耗蓝牙，庞大的生态系统将推进低功耗蓝牙在生活中普及.
He等[1]针对BLE和iBeacon技术的工作过程和协议格式，设计博物馆交互系统，游客可获得导航并与收藏品交互. Vochin等[2]设计的智能显示和报警系统，简化室内定位，实现基于位置的内容的广告和分发. Chen等[3-4]结合iBeacon和惯性传感器研究辅助室内定位和精确室内定位，发现低功耗蓝牙比wifi定位更省电. Vy等[5]提出了可信距离法，实现了客户流量、轨迹等分析，通过实验对比蓝牙技术和wifi技术，发现蓝牙技术能减少65%以上多节点的扫描时间. Varela等[6]研究了基于接近度的服务机制，可高精度识别同一地方的用户群.
应用推广也促进了BLE技术的研究，不断提升硬件和协议层面的性能. Bak等[7]使用3个BLE硬件同时扫描，将理论扫描能力提高3倍. Shan等[8-9]针对密集物联网环境下的BLE设备广播碰撞进行分析，提出了BLE广播碰撞仿真模型，仿真结果显示，随着广播节点数量增多，广播碰撞的概率急剧增长，造成蓝牙微微网吞吐量下降与节点功耗增长. Cho[10]从设备发现可能性与延迟角度对M:N BLE广播网络建立理论分析通用模型，模型考虑了广播信道碰撞因素对设备发现的影响，但模型对BLE广播扫描做了一些简化，导致精度有所下降. Jeon[11]对BLE周围设备发现过程提出了一个通用理论模型，模型基于孙子剩余定理推导分析了邻居发现过程的延迟与功耗.以上理论模型与仿真结果具有一定的通用性，可指导在密集BLE设备环境下的网络参数设定，但只适用于单一角色的BLE环境中，无法应用在同时实现主从角色的复杂网络环境中.
针对密集BLE节点下的广播碰撞问题，Seo等[12-13]从广播节点角度出发提出了载波监听随机退避(CSscheme)协议与载波监听动态广播间隔(CS-DAI)协议，能够有效避免低功耗蓝牙广播碰撞. Zhang等[14]从扫描节点角度出发针对当前网络环境提出动态扫描时间协议，减少了邻居节点发现时间.但是这些无应答广播协议方案，由于节点无法及时停止广播，信道占用率高.
提出的支持主从角色的广播碰撞概率模型，可应用到主从角色的复杂网络环境，准确分析碰撞导致的延迟和节点最大容量，仿真结果论证了模型的正确性.并提出应答确认方式，可以高效退出广播状态，减少一轮信息交换过程的广播次数.
2 防碰撞广播方案 2.1 无连接通信模式低功耗蓝牙协议规定低功耗蓝牙设备存在无连接与连接模式2种运行模式[15].无连接模式网络中存在扫描设备与广播设备2种设备，广播设备在广播信道(index为37、38、39)上周期性地广播数据，相同信道上的扫描设备可以监听广播数据，以完成设备间的信息交互.
广播设备的一个最重要的参数为广播间隔，由固定AdvInerval和伪随机数AdvDelay(< 10 ms)组成，广播设备在每个广播间隔打开发射机，在3个广播信道上分别发射一次广播数据包.扫描设备在每个扫描间隔(ScanInerval)中只扫描一个固定信道，接收机打开时间称为扫描窗口(ScanWindow)，扫描窗口不大于扫描间隔且都不大于10.24 s，当扫描窗口等于扫描间隔为连续扫描模式.
iBeacon协议于2013年被苹果公司首次提出并开发，协议的实现基于低功耗蓝牙的特有的广播工作模式. iBeacon设备相当于一座小型基站，可以通过周期广播发送iBeacon协议特有ID信息，进入到iBeacon基站区域内的设备可以扫描到ID信息并精确测算与基站的距离.一个iBeacon广播基站和使用被动扫描的扫描设备工作模式如图 1所示.
|
图 1 广播设备和扫描设备的非连接无向广播事件时序 |
防碰撞广播协议基于低功耗蓝牙无连接数据传输方式与iBeacon非连接不可扫描广播包格式.协议网络中包含一个中心节点与M个边缘节点，所有节点都以不同的周期切换广播与扫描态，以发送与响应数据.边缘节点可以发现中心节点广播并进行应答确认.网络协议通过Major的最高位标志节点类型，中心节点为1，边缘节点为0，Major的后15位与Minor用于传输数据，同时边缘节点通过通用唯一识别码(UUID，universally unique identifier)标识自身，中心节点通过UUID应答边缘节点.
在网络中，中心节点广播主题信息，边缘节点要选择确认，并广播应答中心节点，中心节点扫描确认信息并登记新的边缘节点UUID，以在下次广播时应答网络中的边缘节点.处理流程如图 2(a).
|
图 2 中心节点和边缘节点的广播、扫描切换过程 |
边缘节点在扫描发现中心节点的广播主题存在后，由用户确认需要发送传感器数据，边缘节点发起广播，中心节点扫描登记并在后续广播中写入对应边缘节点的UUID进行应答，边缘节点扫描中心节点应答后，主动进入空闲态.处理流程如图 2(b).
2.2.2 应答策略边缘节点接收主节点应答、退出网络的策略，能够减轻网络负荷.当网络中边缘节点数量较多时，中心节点无法针对边缘节点一一应答.基于iBeacon数据包定义，提出了一种高效的应答方式，中心节点通过将UUID数据段划分为多个相同的n bit(n为128的因数)区域段，以队列形式装载边缘节点UUID标识字段.而边缘节点的UUID分为(128-n)比特的网段字段与n bit的节点标识字段.边缘节点将接收到中心节点广播UUID分段与自身UUID特定字段比较，相同则为本网段的应答.此方法可以一次应答128/n个边缘节点，而同一网段可以容纳(2n-1)个不同边缘节点.中心节点和边缘节点UUID格式如图 3所示.
|
图 3 中心节点和边缘节点的UUID网段划分格式 |
边缘节点在进入网络之前，会随机生成一个扫描时间tST，后续每次切换到扫描状态时，都会持续使用这个时间进行扫描.当边缘节点数量较多时，边缘节点间可能生成相同的扫描时间，因此2个节点每次进入广播态会持续发生碰撞.提出一个随机扫描时间方案，边缘节点进入扫描态时，在原先的扫描时间基础上，叠加零均值的均匀分布子扫描时间，减少边缘节点进入下一次广播发生碰撞的几率.
2.3 协议分析与Cho和Jeon提出的单一角色BLE环境下的协议分析模型[10-11]不同，考虑了低功耗蓝牙广播扫描2种模式的切换，从而能适应更广泛的物联网应用.方案采用的iBeacon协议，具有良好的适应性与可扩展性.同时由于网络节点采用非连接不可扫描的广播模式与被动扫描的扫描方式，可以避免多个扫描节点同时向广播节点发送扫描请求包造成的广播碰撞问题，这也是低功耗蓝牙广播碰撞的主要原因[16-17].针对节点数量较多时随机生成的扫描时间同步碰撞问题提出了子随机扫描时间方案，进一步缓解边缘节点广播碰撞.针对网络中心节点提出基于广播的高效应答方式一次最多可应答128/n(n为128的因数)个边缘节点，边缘节点接收应答及时退出网络, 可扩大一倍以上网络容量.
3 模型分析针对上述的协议设计，建立防碰撞广播的理论模型，用于研究系统的关键参数和指标.模型由一个中心节点S和M个边缘节点(V)组成，首先建立了中心节点成功发现边缘节点和边缘节点成功发现中心节点的概率模型；然后通过该概率模型导出网络数据传输成功期望延迟、成功率和节点容量.
低功耗蓝牙无连接网络设备包含广播态和扫描态2个状态，而模型中的2种节点都周期性的切换广播和扫描态，一个周期T中广播态时间为tAT，扫描态时间为tST，扫描间隔TSI，由于模型中的节点需要尽快完成数据发现，节点扫描为连续扫描模式.用ρ=tAT/tST表示广播时间与扫描时间比率，参数中上标为S代表中心节点参数，如
在一个只有M个边缘节点和一个中心节点的网络中，所有网络节点都相互独立，并周期性地切换广播态和扫描态，中心节点为了成功接收边缘节点广播，在边缘节点开启广播时中心节点应与边缘节点处于同一广播信道(37, 38, 39)，同时中心节点处于扫描态、并有足够时间接收边缘节点的iBeacon广播包，此时间为TAD，即在一个广播信道发送完整iBeacon广播包时间. 图 4为中心节点与边缘节点的状态与数据交互过程.
|
图 4 网络节点状态与数据交互 |
中心节点在边缘节点发送广播时与边缘节点处于同一信道的可能性为
| $ \begin{array}{c} {p_{\rm V}}(i) = \\ C_3^1{\left( {\frac{1}{3}} \right)^2}\frac{1}{{1 + {\rho ^{\rm S}}}}\left( {1 - \frac{{{T_{\rm AD}}}}{{T_{\rm SI}^{\rm S}}}} \right){\left( {1 - \frac{{{\rho ^{\rm V}}}}{{1 + {\rho ^{\rm V}}}}\frac{{2{T_{\rm AD}}}}{{t_{\rm AT}^{\rm V}}}} \right)^{M - 1}} \end{array} $ | (1) |
则边缘节点每次广播被接收的可能性PV为3个广播通道成功被接收可能性之和：
| $ \begin{array}{c} {P_{\rm V}} = \sum\limits_{i = 37}^{39} {{p_{\rm V}}(i) = } \\ \frac{1}{{1 + {\rho ^{\rm S}}}}\left( {1 - \frac{{{T_{{\rm{AD}}}}}}{{T_{{\rm{SI}}}^{\rm{S}}}}} \right){\left( {1 - \frac{{{\rho ^{\rm{V}}}}}{{1 + {\rho ^{\rm{V}}}}}\frac{{2{T_{{\rm{AD}}}}}}{{t_{{\rm{AT}}}^{\rm{V}}}}} \right)^{M - 1}} \end{array} $ | (2) |
当中心节点处于广播态，边缘节点为了成功接收中心节点存在或应答广播包，在中心节点开启广播时，边缘节点应与中心节点处于同一广播信道，并且处于扫描态，此概率为
| $ {P_{\rm{S}}} = \frac{1}{{1 + {\rho ^{\rm{V}}}}}\left( {1 - \frac{{{T_{{\rm{AD}}}}}}{{T_{{\rm{SI}}}^{\rm{V}}}}} \right){\rm{ }}{\left( {1 - \frac{{{\rho ^{\rm{V}}}}}{{1 + {\rho ^{\rm{V}}}}}\frac{{2{T_{{\rm{AD}}}}}}{{t_{{\rm{AT}}}^{\rm{V}}}}} \right)^{M - 1}} $ | (3) |
网络延迟定义为边缘节点进入激活状态到接收中心节点应答广播包的时间间隔.网络进程分为数据传输阶段和应答阶段2个阶段.数据传输阶段时间
|
图 5 网络节点数据交互延迟 |
表 1显示了边缘节点在第N(N=1, 2…)个周期后接收到中心节点应答的概率与网络中剩余边缘节点数量.
|
表 1 边缘节点数据传输成功概率与延迟 |
网络平均延迟代表网络中所有边缘节点完成数据传输的平均时间，可以衡量边缘节点的平均功耗.在M个边缘节点与1个中心节点组成的网络中数据传输成功平均延迟公式如下：
| $ {\pi _{\rm D}} = \sum\limits_{i = 1}^\infty {{P_i}\left[ {(t_{{\rm{ST}}}^{\rm{V}} + t_{{\rm{AT}}}^{\rm{V}})i + \frac{1}{2}t_{{\rm{ST}}}^{\rm{V}}} \right]} $ | (4) |
而网络最大延迟定义为所有边缘节点都完成数据传输后的整个时间段，公式如下：
| $ \begin{array}{c} {\pi _{\rm D_M}} = (t_{{\rm{ST}}}^{\rm{V}} + t_{{\rm{AT}}}^{\rm{V}})i + \\ \frac{1}{2}t_{{\rm{ST}}}^{\rm{V}}\left\{ {i|{\rm round}\left( {M\left( {1 - \sum\limits_{j = 1}^{i - 1} {{P_i}} } \right)} \right) = 0} \right\} \end{array} $ | (5) |
网络最大延迟能够有效的衡量中心节点成功收集所有边缘节点应答所需的最大延迟.
3.3 容量网络数据传输成功率定义为限制时间Tlim内，网络中所有边缘节点发送数据给中心节点并成功收到中心节点应答的概率P.
在限制时间Tlim内，每个边缘节点平均数据传输成功概率为p.
| $ p = \sum\limits_{i = 1}^n {{P_i}\left\{ {n = {\rm floor}\left( {\frac{{{T_{\rm \lim }} - \frac{1}{2}t_{{\rm{ST}}}^{\rm{V}}}}{{{T^{\rm{V}}}}}} \right)} \right\}} $ | (6) |
网络数据传输成功率P为所有M个边缘节点都传输数据成功的并集.
| $ P = {p^M} $ | (7) |
为满足工程实际应用需要，限定网络数据传输成功率P至少需要达到99.9%，网络能够承载的最大设备数量Mc计算公式化为
| $ {M_{\rm c}} = \frac{{{\rm \lg} 0.999}}{{{\rm \lg} p}} $ | (8) |
为了验证提出的网络成功率和延迟模型，在MATLAB软件中建立了一个模拟低功耗蓝牙广播扫描过程的仿真器，该仿真器与仿真参数设定完全符合低功耗蓝牙协议(v4.2).构建一个主节点、最大200个从节点的分布式广播仿真环境，实现了延迟、成功率、广播碰撞、容量4种仿真实验.针对BLE标准无应答广播(Standard)[15]、载波监听动态广播间隔(CS-DAI)[13]、本文提出的高效应答广播(ASR)3种方案进行对比分析.为了使仿真结果完全收敛，对每种场景都进行了1 000次仿真并取平均值.仿真参数设定如表 2所示.
|
|
表 2 仿真参数设定 |
图 6显示了网络在不同的参数设置下平均延迟和最大延迟的变化曲线，这些参数包括边缘节点数量M与中心节点扫描时间
|
图 6 网络延迟与中心节点扫描时间、边缘节点数量关系 |
图 6中还对比了中心节点扫描时间
在不同的应用场景中，完成数据传输的过程有不同的时间限制要求，针对3 s、4 s、5 s这3种限制时间进行了仿真实验(
|
图 7 网络应答成功率随限制时间与节点数量变化 |
在网络数据传输成功条件下3种网络的广播碰撞次数与网络平均延迟如图 8所示. 图(a)显示随着网络节点数量增加，高效应答广播策略(ASR)更加有效地减少了网络的碰撞数量. ASR应答网络中，随着边缘节点接收应答退出网络，信道占用率骤减，节点广播碰撞率持续下降.当节点数量超过100个时，高效应答策略减少了90%以上的广播碰撞.网络节点平均延迟如图(b)所示，节点数量较少时无应答网络性能较好，但随着边缘节点增加，有应答网络性能快速超越无应答网络，节点数量达到200时，有应答策略相比其他策略降低了约23%延迟.
|
图 8 网络碰撞与延迟与节点数量关系 |
图 9为3种网络协议在网络限制时间为5 s时的数据传输成功率情况.根据之前仿真结果，扫描时间比例采用最优的
|
图 9 网络数据传输成功率与节点数量关系 |
提出了一种基于iBeacon的防碰撞有应答广播协议，所提协议采用了分组高效应答和子随机扫描时间等方案，降低了广播碰撞率.此外，基于协议框架，建立了一个物理容量和延迟计算的数学模型，并对有应答网络和无应答网络进行大规模仿真，分析了网络延迟、碰撞、容量、传输成功率，验证了模型的准确性和有应答协议的高效性.与无应答式的广播协议相比，该协议可以高效确认，降低23%延迟与90%的广播碰撞，并提升一倍系统容量.
| [1] |
He Zhiqiang, Cui Binyue, Zhou Wei, et al. A proposal of interaction system between visitor and collection in museum hall by iBeacon[C]//2015 10th International Conference on Computer Science & Education (ICCSE). New York: IEEE Press, 2015: 427-430. https://ieeexplore.ieee.org/document/7250283
|
| [2] |
Vochin M, Vulpe A, Boicescu L, et al. An intelligent low-power displaying system withr integrated emergency alerting capability[J]. Sensors, 2019, 19(3): 666. DOI:10.3390/s19030666 |
| [3] |
Chen Zhenghua, Zhu Qingchang, Soh Y C. Smartphone inertial sensor-based indoor localization and tracking with iBeacon corrections[J]. IEEE Transactions on Industrial Informatics, 2016, 12(4): 1540-1549. DOI:10.1109/TII.2016.2579265 |
| [4] |
Wu Xudong, Shen Ruofei, Fu Luoyi, et al. iBILL:using iBeacon and inertial sensors for accurate indoor localization in large open areas[J]. IEEE Access, 2017, 5: 14589-14599. DOI:10.1109/ACCESS.2017.2726088 |
| [5] |
Vy T D, Shin Y. iBeacon indoor localization using trusted-Ranges model[J]. International Journal of Distributed Sensor Networks, 2019, 15(1): 155014771882430. DOI:10.1177/1550147718824304 |
| [6] |
Varela P M, Otsuki Ohtsuki T. Discovering Co-located walking groups of people using iBeacon technology[J]. IEEE Access, 2016, 4: 6591-6601. DOI:10.1109/ACCESS.2016.2615863 |
| [7] |
Bak S, Suh Y J. Designing and implementing an enhanced bluetooth low energy scanner with user-level channel awareness and simultaneous channel scanning[J]. IEICE Transactions on Information and Systems, 2019, E102(3): 640-644. DOI:10.1587/transinf.2018edl8205 |
| [8] |
Shan Gaoyang, Im S Y, Roh B H. Optimal AdvInterval for BLE scanning in different number of BLE devices environment[C]//2016 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS). New York: IEEE Press, 2016: 1031-1032. 10.1109/INFCOMW.2016.7562238
|
| [9] |
Shan Gaoyang, Lee B U, Shin S H, et al. Design and implementation of simulator for analysis of BLE broadcast signal collision[C]//2017 International Conference on Information Networking (ICOIN). New York: IEEE Press, 2017: 448-452. 10.1109/ICOIN.2017.7899533
|
| [10] |
Cho K, Park W, Hong M, et al. Analysis of latency performance of bluetooth low energy (BLE) networks[J]. Sensors, 2014, 15(1): 59-78. DOI:10.3390/s150100059 |
| [11] |
Jeon W S, Dwijaksara M H, Jeong D G. Performance analysis of neighbor discovery process in bluetooth low-energy networks[J]. IEEE Transactions on Vehicular Technology, 2017, 66(2): 1865-1871. DOI:10.1109/TVT.2016.2558194 |
| [12] |
Seo J, Cho K, Cho W, et al. A discovery scheme based on carrier sensing in self-organizing Bluetooth Low Energy networks[J]. Journal of Network and Computer Applications, 2016, 65: 72-83. DOI:10.1016/j.jnca.2015.09.015 |
| [13] |
Silva B N, Han K, Seo J, et al. A dynamic advertisement interval strategy in Bluetooth low energy networks[J]. International Journal of Sensor Networks, 2018, 27(1): 52. DOI:10.1504/IJSNET.2018.092130 |
| [14] |
Zhang Yan, Song Zheng, Wang Wendong, et al. An optimized algorithm for device discovery using BLE[C]//Proceedings of the 20164th International Conference on Machinery, Materials and Information Technology Applications. Paris, France: Atlantis Press, 2016: 115-120. 10.2991/icmmita-16.2016.23
|
| [15] |
Bluetooth Special Interest Group (SIG). Bluetooth core specification v4.2[S/OL]. 2014. http://www.bluetooth.com/specifications/bluetooth-core-specification.
|
| [16] |
Kim J, Han K. Backoff scheme for crowded Bluetooth low energy networks[J]. IET Communications, 2017, 11(4): 548-557. DOI:10.1049/iet-com.2016.0462 |
| [17] |
Hernandez-Solana A, Perez-Diaz-de-cerio D, Valdovinos A, et al. Anti-collision adaptations of BLE active scanning for dense IoT tracking applications[J]. IEEE Access, 2018, 6: 53620-53637. DOI:10.1109/ACCESS.2018.2870691 |