蓝牙微微网内多优先级业务动态带宽分配算法

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

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分组来判断该链路是否已经将业务数据传输完毕, 如果数据发送完毕, 主调度器将该链路从高优先级链路队列中清除, 以免在调度过程中影响其他的高优先级链路业务的性能指标。