引用本文
钱志鸿, 周策, 程超, 厉茜. 蓝牙微微网内多优先级业务动态带宽分配算法. 吉林大学学报: 工学版, 2016, 46(1): 284-289
QIAN Zhi-hong, ZHOU Ce, CHENG Chao, LI Qian. Dynamic bandwidth allocation algorithm for multi-priority business of Bluetooth piconet. Journal of Jilin University Engineering and Technology Edition, 2016, 46(1): 284-289  
Permissions
Copyright©2016, 吉林大学学报编辑部
版权所有.吉林大学学报编辑部
蓝牙微微网内多优先级业务动态带宽分配算法
钱志鸿, 周策, 程超, 厉茜
吉林大学 通信工程学院,长春 130012

作者简介:钱志鸿(1957-),男,教授,博士生导师.研究方向:无线网络技术.E-mail:dr.qzh@163.com

基金:国家自然科学基金项目(61371092,61071073)
摘要

针对蓝牙网内存在多种类型业务的调度问题,提出了一种蓝牙微微网内多优先级业务动态带宽分配(Multi-priority bandwidth allocation,MPBA)算法。MPBA算法通过估计高优先级链路的数据到达速率和所选择发送分组的类型推导出每条链路的最佳轮询间隔,通过比较每条高优先级链路的时隙计数器是否达到自身的最佳轮询间隔决定是否调度该链路。仿真结果表明,MPBA算法能够很好地保证高优先级业务的带宽需求,而且有较高的信道资源利用率和较低的调度时延。

关键词: 通信技术; 蓝牙微微网; 调度; 多优先级; 实时业务
中图分类号:TN92 文献标志码:A 文章编号:1671-5497(2016)01-0284-06
Dynamic bandwidth allocation algorithm for multi-priority business of Bluetooth piconet
QIAN Zhi-hong, ZHOU Ce, CHENG Chao, LI Qian
College of Communication Engineering, Jilin University, Changchun 130012, China
Abstract

To solve the scheduling problem of various businesses existing in Bluetooth Piconet, a dynamic bandwidth allocation algorithm for multi-priority business of Bluetooth Piconet was presented, namely MPBA scheduling algorithm. In MPBA, the optimal polling interval can be derived by estimating data arrival rate and packet type for each link with high priority. By comparing the value of the optimal polling interval and the slot counter of a link MPBA decides whether to schedule this link. Simulation results indicate that the MPBA scheduling algorithm can provide better bandwidth requirement for high priority links with higher bandwidth utilization and lower scheduling delay than existing algorisms.

Keyword: communication; bluetooth piconet; scheduling; multipriority; realtime business
0 引 言

随着物联网应用的日益广泛, 物联网底层接入技术之一的蓝牙技术的应用空间也越来越大[1]。无线多媒体网络和实时多媒体业务的广泛应用, 使得蓝牙网内所传送的信息类型已不仅仅局限于普通的数据文件, 也包括视频、高保真音频等多媒体业务。蓝牙2.0+EDR规范提高了数据传输速率, 就是为了实现基于多媒体的中高速率PAN应用[2], 即能够支持多媒体业务。多媒体业务对带宽和时延有着较为严格的要求[3], 如何在蓝牙技术中同时支持普通业务和多媒体业务, 实现区分服务, 满足不同QoS要求, 是今后蓝牙技术的研究重点, 也是本文的研究重点。

传统的蓝牙微微网调度算法无法提供QoS保证和区分服务, 不能满足多媒体业务和普通数据业务共存时的服务质量需求, 这就需要设计一种新的蓝牙微微网MAC层调度算法, 有效调度实时业务和非实时业务并存的链路, 保证实时业务的带宽和时延需求。蓝牙QoS保障和区分服务方面, 目前存在以下两个问题:

(1)Hassan[4], Khan[5], Sewook[6]等学者研究了语音和视频等多媒体业务流在蓝牙网络ACL链路上的传输性能。这些研究分析了视频以及高保真音频流等实时业务在蓝牙网内传输的可能性, 但仅考虑了点到点的视频传输或者蓝牙网络中只存在单一实时多媒体业务的情况, 没有考虑到蓝牙网络中既存在音视频流链路又存在数据传输链路时蓝牙调度的情况。

(2)目前的蓝牙微微网MAC层调度算法, 比较经典的有Gil等[7]提出的PRR算法, Miorandi等[8]提出的改进算法GRR, Fan等[9]提出的按需轮询的调度算法, Bakhsh等[10]提出的一种动态延迟管理协议等。但是这些调度算法都只是针对蓝牙网络中存在数据业务, 没有存在实时业务的情况。如果仍然按照这些轮询算法轮询有实时业务的链路, 可能会由于实时业务流量没有其他数据业务链路的流量大而较少被调度, 从而造成实时业务带宽难以得到满足, 调度时延变长的问题。

本文针对这些问题, 提出了一种蓝牙微微网内多优先级业务动态带宽分配(Multipriority bandwidth allocation, MPBA)算法, 用来解决蓝牙微微网内既存在多媒体实时业务又存在数据业务时的调度问题, 并保证带宽和时延需求。MPBA算法通过估计高优先级链路的数据到达速率和所选择的发送分组类型来推导出每条链路的最佳轮询间隔, 并比较每条高优先级链路的时隙计数器是否达到自身的最佳轮询间隔来决定是否调度该链路。仿真结果表明, MPBA调度算法能够很好地保证高优先级业务的带宽需求, 而且有较高的信道资源利用率和较低的调度时延。

1 算法框架

为了满足蓝牙微微网对于多媒体实时业务和数据业务并存时的数据传输要求, 首先需要考虑网络的吞吐量指标。要使网络整体吞吐量达到最大化需要满足两个条件:①根据不同的信道质量选择合适的数据分组进行传输; ②在数据分组的每次传送过程中, 使数据分组的数据净荷达到满载。对条件①, 使用文献[11]提出的针对实时业务在蓝牙微微网内传输时的自适应分组选择策略来选出合适的发送分组; 对条件②, 本文提出了MPBA分配算法, 定义了“ 最佳轮询间隔” , 当主节点调度完某一链路后再经过最佳轮询间隔时间, 理论上该链路的数据缓冲区到达的数据量能够使得所发送的类型分组达到满载。MPBA算法整体流程如图1所示。

图1 蓝牙微微网内多优先级业务动态带宽分配算法Fig.1 Bluetooth piconets in multi priority traffic dynamic bandwidth allocation algorithm

2 MPBA调度算法的实现
2.1 参数设置

设定一个微微网由1个主节点和M(0≤ M≤ 7)个活动的从节点构成。设该微微网中存在N条实时业务流链路, 为高优先级业务; M-N条数据类业务链路, 为低优先级业务。对于绝大多数实时流媒体的应用来说, 用户只是接收流媒体并播放, 这个过程流量是不对称的, 用户需要大量的下行带宽[12]。因此使主节点的调度器只维护M个下行链路即可。记第i条高优先级链路为HP(i), 其中0≤ i≤ N。

设高优先级链路HP(i)中实时流媒体业务码率为BR(i), 单位是kbit/s, 由文献[13]的分析可知, 在高斯信道下, 在不同的信噪比区间中选择合适的分组可以使得在满足实时业务带宽需求的条件下, 使用该分组进行传输时所需消耗的时隙数最少, 因此, 根据信道质量选择到达基带的数据分组3-DH5、3-DH3和2-DH5来传送实时业务数据时分别占用5、3、5个时隙, 最大净荷分别为8168、4416、5432 bit。

2.2 初始化过程

主调度器首先通过二阶四阶矩信道估计方法估计出每条链路的信道质量[14], 然后根据自适应分组选择策略选择出合适的发送分组类型。主调度器根据收集到的分组信息计算每条链路的分组到达速率, 最后通过所选的分组类型以及每条链路的分组到达速率计算出每条链路的最佳轮询间隔。

2.3 主调度过程

在信道质量估计完成后即开始主调度过程, 主节点依次轮流调度每一个高优先级链路, 然后主节点将按照下述的子过程与规则选择出最需要轮询的从节点, 完成数据传输与更新并计算出下一条链路是否需要被调度。

Step1 计算最佳轮询间隔

为了使带宽利用率达到最大化[15], 数据分组的净荷应尽可能地达到满载, 提出了最佳轮询间隔的概念。最佳轮询间隔是指链路被主调度器调度后再经过若干个时隙, 其数据缓冲区的数据量能达到最大净荷数。经过最佳轮询间隔的时隙数后, 该链路可以再次被主调度器调度。记第i条高优先级链路的最佳轮询间隔为PI(i)个时隙, 其承载的CBR实时业务流码率为BR(i)kbit/s, 蓝牙的跳频速率为1600 次/s。因此每个时隙内到达高优先级链路数据缓冲区的数据量BPS(i)为:

BPS(i)=BR(i)×1000/1600(1)

假设第i条高优先级链路在某一信道质量下根据自适应分组选择策略选择出合适的发送分组, 分组最大净荷数为PL(i), 分组所占时隙数为x(i), 所选的分组类型只有3种:2-DH3分组、2-DH5分组以及3-DH5分组, 3种分组的净荷数分别为2936、5432和8168 bit, 所占的时隙数分别为3、5和5。因此一次调度过程中发送一个分组所能携带的最大数据量为PL(i), 为了避免带宽的浪费, 调度时分组应携带尽可能多的数据, 因此有式(2)成立:

(PI(i)+x(i)+1)×BPS(i)≤PL(i)(2)

得出每条高优先级链路的最佳轮询间隔为:

PI(i)=floor(PL(i)/BPS(i)-x(i)-1) (3)

式中:floor表示向下取整。最佳轮询间隔的计算与分组数据到达率以及所选择的发送数据包类型有直接关系。主调度器为每条链路都维护一个最佳轮询间隔PI(i), 该参数能够兼顾各条高优先级链路的带宽需求和调度时延, 使得主调度器不会长时间的只为某几条链路服务而闲置其他链路。最佳轮询间隔也是主调度器最终决定调度哪条链路的唯一判定依据。

Step2 高优先级链路的调度

由于实时流媒体业务传输模式通常是非对称单流量模式, 因此本文在高优先级链路中以只存在上行链路为例分析MPBA算法。定义轮询周期PC是从调度第一条链路开始到调度完所有链路后再进行下一次轮询前所消耗的时隙数。

主节点为每个高优先级链路维护一个时隙计数器。将第i条计数值记为SC(i), 初始值为0。在调度开始时, 主节点使用POLL分组依次轮询各个存在高优先级业务的从节点一次, 被轮询的每个从节点只返回一个数据分组, 此时更新各个高优先级链路的时隙计数器:

SC(i)=(x(i)+1)×(N-i)(4)

之后主节点开始重新依次轮询各个高优先级链路。在进行数据调度之前, 主节点首先判断第i条高优先级链路的SC(i)值是否大于该链路的PI(i)值, 如果是, 则调度该链路, 并将该链路的SC(i)值更新为:

SC(i)=SC(i)-PI(i)(5)

在式(5)中, 之所以没有将SC(i)值归0, 是因为当第i条高优先级链路已经达到最佳轮询间隔时, 主调度器可能正在调度其他的高优先级链路。等到主调度器再次轮询第i条高优先级链路时, SC(i)值可能远远大于PI(i)值。此时将SC(i)值按式(5)更新, 更新后的SC(i)值能够间接表示第i条高优先级链路数据缓冲区内剩余的数据量。

调度第i条高优先级链路发送一个数据分组占用了x(i)+1个时隙, 因此其他高优先级链路的SC(i)值更新为:

SC(i)=SC(i)+x(i)+1(6)

主调度器在调度完该链路之后开始进行下一条高优先级链路的调度判断, 此时i=i+1, 转向下一条链路。如果SC(i)小于PI(i), 则不对该链路进行调度, 直接进行下一条高优先级链路的调度判断, 直至所有的高优先级链路都被轮询过为止, 这时一个轮询周期结束, 主调度器开始对高优先级链路进行下一个周期的轮询调度过程。从整个调度过程可知, 在一个轮询调度周期内, 所有的高优先级链路都会被判断一次, 满足式(2)的高优先级链路能够被调度。

Step3 低优先级链路的调度

低优先级链路的调度规则如下:如果在一个轮询周期内, 没有任何高优先级链路依据轮询规则被调度时, 主节点对低优先级链路进行一次调度, 并且只能发送一个数据分组, 分组类型按照杨帆等[16]提出的分组选择策略选择。如果网内存在多条低优先级链路, 那么主节点会在每个调度低优先级链路的机会中依次调度每一条低优先级链路, 以保证每条低优先级链路都有机会被调度。

Step4 轮询周期的更新

在低优先级链路发送完数据分组后, 主调度器马上开始进行新一轮的高优先级链路轮询调度周期。由于调度低优先级链路耗费x(i)+1个时隙, 因此, 主节点调度器中维护的每条高优先级链路时隙计数器值SC(i)更新为:

SC(i)=SC(i)+x(i)+1(7)

从算法的调度流程中可以得知一次轮询周期的表达式如式(8)所示:

PC=∑NpNp×(x(i)+1), Np≠0x(i)+1, Np=08

式中:Np为一个轮询周期内被调度的高优先级链路数量。如果一个轮询周期内有高优先级链路被调度时, 低优先级链路将不会被调度, 轮询周期即为所有被调度的高优先级链路所消耗的时隙数; 如果一个轮询周期内没有高优先级链路被调度, 轮询周期即为调度一条低优先级链路所消耗的时隙数量。

每当有新的高优先级链路加入网络或者有高优先级链路离开网络时, 主节点将重新整理所维护的高优先级链路队列, 然后再进行调度, 另外, 算法通过每条链路是否出现POLL-NULL分组来判断该链路是否已经将业务数据传输完毕, 如果数据发送完毕, 主调度器将该链路从高优先级链路队列中清除, 以免在调度过程中影响其他的高优先级链路业务的性能指标。

3 仿真结果与比较
3.1 性能指标定义

对于存在实时流媒体业务的蓝牙微微网, 传统的传输数据业务时的性能指标不再适用。本文对一些传统网络调度算法以及流媒体业务传输的评估指标进行调整与重新定义, 主要使用了以下3种性能指标。

带宽:最小传输带宽是实时流媒体需保证的最基本的要求。每条高优先级链路实际分配的带宽为:

BWallot(i)=Num(i)×PL/1000(9)

式中:Num(i)是第i条高优先级链路被调度的次数。

带宽利用率:链路带宽资源的利用率可表示为:

η(i)=BWused(i)/BWallot(i)(10)

式中:BWused(i)为链路i实际使用的带宽, 单位为kbit/s, 计算公式为:

BWused(i)=Num(i)×[PC(i)+x(i)+1]×BPS(i)/1000(11)

调度时延:定义为第i条链路在某一时刻被主节点调度完毕后直到下次该链路被主节点调度的时间间隔:

Interval(i)=T_current(i)-T_last(i)(12)

式中:T_last(i)代表第i条链路上次被调度时的时间; T_current(i)代表该链路当前被调度时的时间。

3.2 仿真结果与分析

本文使用MATLAB进行仿真, 以一个蓝牙微微网内存在3条实时业务链路和2条非实时业务链路的情景下对MPBA算法进行仿真验证, 使用PRR算法和Gated算法作为对比, 分析MPBA算法的网络性能。

设置每条链路的到达速率都不相同。实时链路对应于i=1, 2, 3, 非实时业务对应于i=4, 5。第i条链路到达速率为:

2(N-i+1)×DR/(N×(N+1))(13)

式中:DR为整个微微网总的数据到达速率, 单位为kbit/s。

假设此时由自适应分组选择策略选出的分组类型为3-DH5数据包, 此时的数据分组类型的净荷为PL=8168 bit, 发送一个分组消耗的时隙数量为slot=6, 蓝牙系统将1 s划分为1600个时隙, 也即1 s内可以传送1600/6个3-DH5分组, 可知当选用3-DH5分组作为发送分组类型时, 整个蓝牙微微网在非对称模式下所能提供的最大传输带宽为2178.1 kbit/s。

PL×1600/(slot×1000)=2178.1kbit/s14

图2所示MPBA算法随着数据到达率的变化所需带宽的变化情况。可以看出, MPBA算法会对高优先级实时业务分配较多带宽。当蓝牙网内的数据达到速率超过系统的传输能力(2178.1 kbit/s)时, MPBA算法会牺牲低优先级链路的带宽, 保证高优先级链路的带宽。当所有高优先级链路的数据到达率之和达到系统的传输能力时, 主节点不会对低优先级链路进行调度。若网内数据到达速率超过系统的传输能力, 即占用所有的低优先级链路带宽也不能满足所有高优先级链路的带宽需求, 调度算法会牺牲拥有最高数据到达速率的高优先级链路带宽。

图2 MPBA调度算法所需的带宽Fig.2 MPBA scheduling algorithm for bandwidth required

从图3可以看出, 随着网内数据到达率的增加, MPBA、PRR和Gated算法的系统平均带宽利用率都在增加, 但是由于MPBA算法通过计算每条链路的最佳轮询间隔来预知何时进行调度才能够使得发送数据包到达满载, 使得MPBA算法的带宽利用率高于其他两种算法。

图3 不同调度算法下系统的带宽利用率Fig.3 Different scheduling algorithms under system bandwidth utilization

不同调度算法下各链路调度时延随网内数据到达率的变化情况如图4所示。在网内数据到达速率较低时, MPBA算法的高优先级链路平均调度时延较高, 而数据到达速率较大时, 高优先级链路平均调度时延降低, 低优先级链路整体平均调度时延增大。当高优先级链路的数据到达速率已经超过了系统的传输能力的时候, 主调度器在判断下一次的调度时, 都会有高优先级链路需要被调度, 低优先级链路将得不到被调度的机会, 使得低优先级链路的调度时延无限增加。

图4 调度时延随网内数据到达率的变化Fig.4 Scheduling delay arrival rate with change of network data

4 结束语

针对蓝牙网内存在多条实时业务和非实时业务的情况, 本文提出了MPBA算法, 为不同优先级的链路提供动态带宽分配机制及区分服务的调度机制。算法首先对当前的信道质量进行估计, 根据自适应分组选择出合适的分组类型进行数据传输, 根据分组类型以及当前链路上的实时业务带宽需求计算每条链路的最佳轮询间隔, 并用于判定是否调度该链路, 提供区分服务机制。仿真验证表明, MPBA算法能够为不同QoS要求的链路提供区分服务, 在系统传输能力范围内能够保证高优先级业务的带宽需求, 低优先级链路数量的变化不会影响到高优先级业务的业务质量, 能实现较高的信道资源利用率和较低的调度时延。

The authors have declared that no competing interests exist.

参考文献
[1] 钱志鸿, 王义君. 物联网技术与应用研究[J]. 电子学报, 2012(5): 1023-1029.
Qian Zhi-hong, Wang Yi-jun. Research on internet of things technology and application[J]. Chinese Journal of Electronics, 2012(5): 1023-1029. [本文引用:1]
[2] 钱志鸿, 刘丹. 蓝牙技术数据传输综述[J]. 通信学报, 2012, 33(4): 143-151.
Qian Zhi-hong, Liu Dan. Overview of bluetooth data transmission[J]. Journal of China Institute of Communications, 2012, 33(4): 143-151. [本文引用:1]
[3] Donmez Mehmet Yunus, Sinan Isik, Cem Ersoy. Analysis of a prioritized contention model for multimedia wireless sensor networks[J]. ACM Transactions on Sensor Networks, 2014, 10(2): 36. [本文引用:1]
[4] Hassan B, Remy Guillaume F. Supervised neural fuzzy schemes in video transmission over Bluetooth[C]∥The 20th International Conference on Artificial Neural Networks, Berlin, Springer, 2010: 378-386. [本文引用:1]
[5] Khan M S, Ahmad R, Ahmad T, et al. Real time streaming video over Bluetooth network[C]∥Multimedia, Signal Processing and Communication Technologies, United States, IEEE, 2009: 181-184. [本文引用:1]
[6] Sewook Jung, Chang Alexand er, Gerla Mario. Peer to peer video streaming in Bluetooth overlays[J]. Multimedia Tools and Applications, 2008, 37(3): 263-292. [本文引用:1]
[7] Gil Zussman, Uri Yechiali, Adrian Segall. Exact probabilistic analysis of the limited scheduling algorithm for symmetrical bluetooth piconets[J]. Personal Wireless Communications, 2003, 2775: 276-290. [本文引用:1]
[8] Miorand i D, Zanella A, Pierobon G. Performance evaluation of bluetooth polling schemes: an analytical approach[J]. ACM Mobile Networks and Applications, 2004, 9(1): 63-72. [本文引用:1]
[9] Fan Yang, Wang Ke, Qian Zhi-Hong. Polling-on-demand scheduling algorithm for bluetooth piconet and performance evaluation[J]. Acta Electronica Sinica, 2007, 35(4): 647-652. [本文引用:1]
[10] Bakhsh S T, Hasbullah H, Tahir S. Dynamic relay management protocol for efficient inter-piconet scheduling in bluetooth scatternet[J]. Computers and Electrical Engineering, 2012, 38(3): 626-642. [本文引用:1]
[11] Liu B Q, Qian Z H, Zhang X, et al. A study of video transmission performance in bluetooth sensor networks based on slots analysis[J]. Advanced Materials Research, 2013, 765: 2878-2881. [本文引用:1]
[12] 聂伟. WiMAX无线网络QoS测量及优化研究[D]. 成都: 电子科技大学自动化工程学院, 2011.
Nie Wei. Research on measurement and optimization of WiMAX wireless network QoS[D]. Chengdu: School of Automation Engineering, University of Electronic Science and Technology, 2011. [本文引用:1]
[13] Chan K L, Misic V B, Misic J. Efficient polling schemes for bluetooth picocells revisited[C]∥Proceedings of the 37th Annual Hawaii International Conference on System Sciences, Big Island , Hawaii, 2004: 307-314. [本文引用:1]
[14] Yuan F, Zhang Y, Gao C, et al. SNR estimation of LFM signal for the underwater acoustic channel based on improved M2M4[J]. Journal of Computational Information Systems, 2013, 9(11): 4379-4385. [本文引用:1]
[15] 陈赓, 夏玮玮, 沈连丰. 基于传输速率自适应的动态带宽分配算法[J]. 通信学报, 2014, 35(5): 25-32.
Chen Geng, Xia Wei-wei, Shen Lian-feng. Dynamic band width allocation algorithm based on transmission rate adaptation[J]. Journal of China Institute of Communications, 2014, 35(5): 25-32. [本文引用:1]
[16] 杨帆, 王珂, 钱志鸿. 蓝牙分组传输性能分析与自适应分组选择策略[J]. 通信学报, 2005, 26(9): 97-102.
Yang Fan, Wang Ke, Qian Zhi-hong. Performance analysis of bluetooth packet transmission and adaptive packet selection strategy[J]. Journal of China Institute of Communications, 2005, 26(9): 97-102. [本文引用:1]