0 概述

随着低功率广域(Low Power Wide Area, LPWA)技术的快速发展, 预计至2020年, 物联网(Internet of Things, IoT)中物与物(Machine-to-Machine, M2M)的连接数量将达32亿^[1]。其中, 窄带物联网(Narrow Band IoT, NB-IoT)以安全性高、覆盖能力强而得到研究者的广泛关注^[2]。机器类型通信设备(Machine Type Communication Devices, MTCD)产生的海量M2M业务主要由上行链路方向小型突发载荷构成, 包括特定服务质量(Quality of Service, QoS)、功耗以及传输期限等要求^[3], 其对有限信道资源下的调度提出了挑战, 而以NB-IoT为代表的基于LTE的M2M上行调度作为缓解信道资源紧张的关键技术, 成为当前的研究热点之一。

M2M上行调度的难点在于如何利用有限的无线资源来满足海量终端数据传输的要求, 并适应由其业务特征多样性带来的各类约束, 包括时延、功耗、吞吐量及系统容量等。文献[4-6]对经典的轮询调度算法RR和比例公平调度算法PF进行改进, 使其适合于M2M业务。但由于未改变调度原理, 导致算法不能充分利用M2M时延容忍特性来满足海量终端调度的要求。文献[7]同时考虑功率、延迟和网络容量, 提出一种基于负载的多时隙调度算法, 其能较好地满足业务的特定需求, 但优化过程中所作出的某些假设在实际应用中难以实现。文献[8]研究M2M系统在过载情况下的混合资源分配问题, 提出一种最大化准入MTCD下解决非线性规划问题的方法。

在无线资源有限时, 应尽可能权衡不同业务数据的紧急程度。相关研究表明, 满足数据传输期限需求的调度用于M2M时较为有效^[9]。文献[10]提出基于类的优先级(Class Based Priority, CBP)算法, 其依据业务QoS参数确定数据优先级并进行分类, 为解决由多业务需求引发的调度问题提供了思路。但是, 在M2M流量突发时, 该算法静态优先级分配方式中某些优先级较低但仍具备传输期限的业务极有可能因高优先级业务的突发而错过传输期限。针对该不足, 文献[11]提出平衡交替技术, 在信道和延迟之间实现动态自适应平衡, 通过非直接方式(降低误码率)来保障延迟性能。文献[12]在CBP算法的基础上, 提出一种基于类的总体优先级调度算法(Class Based Overall Priority, CBOP), 但该算法仅能调节各类优先级的顺序, 并未对业务所属的类别进行动态调整。

为克服静态优先级分配方式在上行业务高并发下的不足, 以及CBOP算法业务所属分组不可调的问题, 本文在CBP算法的基础上, 以业务延迟容忍剩余时长(Delay Tolerance Remaining Time, DTRT)为度量依据对M2M业务进行动态分组, 提出一种上行优先级调度算法(Priority Scheduling Algorithm, PSA), 以满足业务的时延约束, 在此基础上, 设计一种混合机制来解决优先级算法的调度不公平问题。

1 系统模型 1.1 问题分析

本文以满足数据的时延约束为目标, 赋予时延容忍程度低、紧急性强的业务以更高的调度优先级。延迟约束下的分组问题表述如下:当前时刻请求服务的业务集合定义为{1, 2, …, m, …, M}, 各业务所属分组集合定义为{G₁, G₂, …, G_x, …, G_g}, 以业务的延迟容忍时长(Delay Tolerance Time, DTT)为指标进行业务分组, 如下:

$ DT{T_{{G_{x - }}\min }} < DT{T_{m \in {G_x}}} \le DT{T_{{G_{x - }}\max }} $

(1)

其中, DTT值即业务传输时延期限值, 其代表业务的时延敏感程度。在式(1)中, 属于分组G_x的业务m, 其DTT值处于分组G_x的DTT范围之内。根据DTT值对业务进行分组, 对应n个优先级{P₁, P₂, …, P_n}。由于DTT是一个静态参数, 为实现动态分组, 本文采用动态的业务指标参数DTRT代替DTT。

本文上行采用峰均比更低的单载波频分多址(Single-Carrier Frequency-Division Multiple Access, SC-FDMA)技术, 因此, 动态分组后的用户资源块(Resource Block, RB)分配存在限制, 不能将离散的RB分配给用户。SC-FDMA下RB分配算法的性能

通常用有效容量进行衡量^[13]。业务m的有效容量指为保障由θ_m指定的业务m的QoS要求, 调度算法可支持的最大业务到达速率, 其计算如下:

$ E_C^m\left( {{\theta _m}} \right) = - \frac{1}{{{\theta _m}}}\ln \mathit{\Psi }\left( {{{\rm{e}}^{{\theta _m}{R_m}}}} \right) $

(2)

其中, E_C为有效容量, Ψ(·)表示期望操作, θ_m是业务m的QoS参数, R_m是业务m的数据速率。考虑常数到达率λ, 业务m超出延迟容忍的概率为:

$ \delta = \mathit{Prob}\left\{ {{D_m} > DTT} \right\} \approx {\varphi _m}{{\rm{e}}^{ - {\theta _m}DTT}} $

(3)

$ E_C^m\left( {{\theta _m}} \right) \ge {\lambda _m} $

(4)

其中, D_m是业务m数据包经历的延迟, φ_m是设备缓冲区非空的概率。为保证业务的QoS需求, 需满足约束条件式(4)。为获得θ_m, 本文采用香农容量公式, 将业务m的最大可传输速率表示为:

$ {R_m} = B\;{\rm{lb}}\left( {1 + \frac{{{P_m}{{\left| {{h_m}} \right|}^2}}}{{{\sigma ^2}}}} \right) $

(5)

其中, B是每个RB的带宽, P_m是业务m所对应设备的发射功率, h_m是信道增益, σ²代表加性高斯白噪声(Additive White Gaussian Noise, AWGN)的功率, $\frac{{{P_m}|{h_m}{|^2}}}{{{\sigma ^2}}} = SNR $为业务m对应MTCD的信噪比。在RB连续分配的约束条件下, 最大化式(5)并不容易, 其已被证明是一个NP难题^[14], 为获得最优解, 需详尽地搜索所有可行的RB分配方案, 该过程具有指数复杂度O(M^K), 在实际应用中, 通常采用启发式算法提供接近最佳的解决方案^[15]。

最低优先级业务的时延容忍占M2M通信总量的绝大部分, 需要利用此特性简化调度以减小开销。但高优先级业务持续突发时低优先级业务长期得不到调度而“饿死”的情况时有发生, 因此, 还需解决优先级算法的调度不公平性问题。

1.2 业务分组模型

设所有MTCD均匀分布于LTE单蜂窝小区, 对业务(1, 2, …, m, …, M)进行分组。分组数g过大会降低调度效率, 过小则不能很好地区分业务时延敏感程度。参考文献[16], 本文设置g=4, 将业务分为4组, 如图 1所示。其中, G₁为发送数据量少但DTT很低的时延不容忍型业务, 如各类警报业务, 其随机突发性强, 需立即上报; G₂为人为干预下发生的M2M通信业务, 如通过国网采集终端后台查询电表信息等, 其数据量大小不等, 由于涉及H2M通信, 因此时延敏感程度较高; G₃为具有最低传输速率要求的业务, 如视频监控等, 其具有一定的时延容忍性, 但必须在DTT内调度一定量的数据以满足其最低传输比特率; G₄为发送量小且时延容忍的业务, 如环境监测, 此类业务占比最大, 对实时性要求较低, 优先级低于上述3种类型, 若无线资源紧张, 可适当推迟该类流的调度。

2 SC-FDMA技术下的动态优先级调度算法 2.1 基于SC-FDMA的资源分配算法

由于RB的邻接约束, 需将K个RB划分为Y个有序的集合, 每个集合具有k_a个相邻RB, 使得K=k₁+k₂+…+k_Y。将分配给业务的RB用1表示, 未分配的RB用0表示, 可得到业务m的RB分配矩阵R_{k, j}^m。以K=4为例, 对于业务m, 其所有的可行RB分配模式用分配矩阵表示如下:

$ \mathit{\boldsymbol{R}}_{k,j}^m = \left( {\begin{array}{*{20}{c}} 0&1&0&0&0&1&0&0&1&0&1\\ 0&0&1&0&0&1&1&0&1&1&1\\ 0&0&0&1&0&0&1&1&1&1&1\\ 0&0&0&0&1&0&0&1&0&1&1 \end{array}} \right) $

(6)

其中, 分配矩阵的列对应可行的4个RB分配模式, 行对应RB的索引。例如, 式(6)的第2列表示RB1分配给m, 而RB2~RB4则未分配给m, 第11列表示RB1~RB4全都分配给m。邻接约束体现在多个RB被分配给某一M2M业务时, 这些RB必须彼此相邻。RB分配矩阵的阶数为K×J, J=1/2×(K²+K)+1代表所有可行的分配模式总数, 在式(6)中, J=11。基于RB邻接约束的RB大小可变分配算法考虑不同业务所需RB数不同, 以N表示未被分配且连续的RB组, R表示二维分配矩阵, R_j^m表示业务m所需的RB数(即块大小), j是所有可用RB中分配给业务m的R_j^m个连续RB中的首个RB索引值, 通过索引j和RB数量R_j^m, 即能确定业务m所使用的资源位置。在每个调度周期, 即传输时间间隔(TTI)中, 算法通过R_j^m的值来确定一个最小且满足要求的块, 从而为业务m提供服务, 然后将此块标记为已被分配, 并按该步骤继续为业务m+1安排RB块。邻接约束启发式算法描述如下。

算法1  基于邻接约束的块大小可变RB分配算法

输入  二维分配矩阵R

输出  业务的RB分配方案

1.N←空闲RB数U_RB

2.R_j^m←业务m从第j个RB开始所需的RB总数

3.while N未被分配完do

4.在R中寻找满足R_j^m要求的最小块

5.分配N中的第j个~第(j+R_j^m-1)个RB给业务m

6.将二维分配矩阵R中的第j列~第(j+R_j^m-1)列的元素置∞(标记为不可被选择)

7.标记N中的第j个~第(j+R_j^m-1)个RB已被分配

8.为业务m+1分配RB

9.end while

2.2 业务动态分组算法

在式(1)中, 以业务的动态DTRT值代替静态DTT值作为指标对所有流进行分组, 每个TTI通过式(7)动态更新不同业务的DTRT值。

$ DTR{T_m} = DT{T_m} - {n_m} \times {t_{{\rm{TTI}}}} $

(7)

其中, n_m是业务m到达后经过的TTI数, t_TTI是调度周期TTI的时长, 本文设为1 ms。以业务DTRT值代入1.2节提出的业务分组模型中, 得到表 1所示的分组。各业务在其DTRT值减小到0之前必须被调度, 否则将超出其时延容忍范围。业务刚到达时, 其DTRT值等于DTT值, 根据该DTRT值所属范围确定一个初始组以及该组对应的优先级。

优先级1为最高优先级, 所有延迟不容忍的业务都保存在此组中, 在每个TTI内将被优先调度。对于初始所属分组为G₂和G₃的业务, 若在一个调度周期内未被调度, 则每经过一个TTI, DTRT值就会减少1 ms, 如果属于低优先级的业务未在该分组的DTRT值范围内被服务, 将自动转移到上一个高优先级组中, 从而拥有更高的调度优先级。假设某业务的DTT值为180 ms, 其最初DTRT值为180 ms, 分组G₃优先级为3, 若经过30 ms后仍未得到调度, 其DTRT值减小为150 ms, 自动转到优先级为2的分组G₂中, 完成动态分组。G₄业务由于占比大且延迟容忍程度高, 为提高调度效率, 算法不考虑提升其优先级, 即G₄的流始终处于最低优先级。

2.3 混合自动轮询机制

文献[13]指出, 在低优先级的业务量明显大于高优先级的业务量时, 应尽量确保高优先级业务得到服务; 反之, 则应确保低优先级数据包不会“饿死”。优先级算法保障了业务时延性能, 提高了传输效率, 但和其他分组相比, 分组4的业务获得的调度机会较低。此外, MTCD呈现出集群特性, 即在某些eNB覆盖范围内, 产生高优先级业务的MTCD数可能很高。当网络容量较小或大量设备连接到网络时, 为避免G₄业务长时间得不到调度而“饿死”, 本文对上述动态调度进行改进, 提出一种混合自动轮询(Hybrid Automatic Round Robin, HARR)机制。将动态调度与轮询调度2种策略相结合, 每隔一段动态调度周期就进入一次轮询周期, 轮询调度周期可避免资源紧张时最低优先级业务始终得不到调度的现象。根据非时延容忍(G₁、G₂和G₃)与时延容忍(G₄)的业务量比例, 确定动态调度周期数与轮询调度周期数(固定为1)的配比α为:

$ \alpha = \mu \mathit{\Theta }\left( {1 - \frac{{{N_4}}}{{{N_{1,2,3,4}}}}} \right) $

(8)

其中, N₄为已到达的G₄业务量, N_{1, 2, 3, 4}为当前到达的总业务量, Θ(·)是α更新公式, 可为分段或阶梯函数。α用于控制调度过程中DTRT动态调度周期数与轮询调度周期数的比例, 即每2个轮询周期的间隔。N₄越大, 时延容忍业务所占比重越高, α越大, 2个轮询调度周期之间的间隔越大。α值不宜太小, 其仅为最低优先级业务提供传输机会, 不能对系统吞吐量造成太大影响。本文基于HARR机制的动态优先级调度算法描述如下:

算法2   HARR机制下的动态优先级调度算法

输入  上一TTI剩余业务集合S₁, 当前TTI新到达业务集合S₂, S₁、S₂内的流DTRT值, α

输出  业务的RB分配方案, 剩余未被调度的业务集合

1.U_RB←空闲RB数

2.if β < α then

3.业务所属分组G₁/G₂/G₃/G₄←业务DTRT值

4.while U_RB>0 do

5.根据DTRT值将RB分配给G₁的所有M2M流

6.根据DTRT值将RB分配给G₂的所有M2M流

7.根据DTRT值将RB分配给G₃的所有M2M流

8.将RB分配给G₄的所有M2M流

9.end while

10.β←β+1

11.else

12.while U_RB>0 do

13.对所有M2M流执行RR算法

14.end while

15.β←0

16.更新α值

17.end if

18.更新未被调度业务的DTRT值(G₄除外)

在算法2中, 步骤5~步骤8、步骤13中的RB分配均采用算法1。在优先级调度阶段, 每经过一个TTI, 距离上一次轮询阶段的周期数(β)加1。此阶段调度器首先服务于G₁的所有流, 无线资源根据DTRT值升序的方向进行分配, 以同样的方式依次将RB分配给G₂、G₃和G₄的M2M流, G₄在其他优先级业务都已满足时才被调度。经过α个优先级调度周期后, β=α, 进入一次轮询调度周期, 此时根据当前业务情况更新α值。

在每个TTI结束时, 对G₁、G₂、G₃中未被调度的流DTRT值进行更新, 其中, DTRT值减小至0的数据包意味着超时, 其将视为传输失败而丢弃, G₄中的业务无需更新。一个TTI中要分配给所有M2M请求的RB数量满足如下约束:

$ \sum\limits_{g = 1}^G {R{B_{mg}}} < {L_m} $

(9)

其中, RB_mg是TTI中分配给g组M2M业务的RB总数, L_m是可分配的RB最大数量。更新DTRT时的执行次数随G₁、G₂和G₃的业务量增长而线性增长, 算法2的时间复杂度为O(n)。

3 仿真结果与分析

本文采用Matlab作为平台, 对算法进行系统仿真与评估。将表 1中的数据作为M2M业务源的模拟参数, 主要包括业务DTRT值、优先级及流量占比情况。系统仿真参数设置如表 2所示。

本文算法的目的在于满足不同类型M2M流量的QoS需求, 仿真主要侧重算法时延和吞吐量的性能评估。首先对无HARR机制下的动态算法与PF算法进行分析, 其中, 发送消息的平均时延代表调度程序提供的服务质量, 图 2所示为MTCD数目分别为100和400时2种算法下数据发送的平均时延情况。

从图 2可以看出, 当MTCD数较小时, 2种调度算法时延性能相差不大, 当MTCD数较大时, PF算法下各优先级数据的发送时延分布相对均匀, 而本文动态算法的平均时延则表现出很好的区分度。对于G₁、G₂和G₃的流, 动态算法的平均延迟明显优于PF算法, 对于G₄的流, 动态算法的平均时延则较高, 原因是PF算法未考虑不同M2M优先级, RB资源在各组业务之间被共享, 而动态算法依据优先级确定传输顺序, 降低了高优先级业务的时延, 但同时会增加低优先级业务的时延。

本文算法在MTCD数为200~1 000时针对不同分组业务的吞吐量情况如图 3所示。

从图 3可以看出, G₁、G₂和G₃的吞吐量随着MTCD数量的增加而增大。G₁分组业务由于占比较低, 且每次发送的数据量都很小, 因此其吞吐量的变化不明显, 但该组业务最早被服务。G₄业务的吞吐量在MTCD数较少时逐渐增加, 在MTCD数增加到600之后开始下降, 原因是MTCD数较多时前3个高优先级的业务量变大, 算法将RB资源优先分配给更高优先级的业务, 对于G₄则采取“尽力而为”的方式提供服务。

在无线资源无法满足大规模业务需求的情况下, 到达业务中高优先级业务所占比例越大, 低优先级业务“饿死”的情况越普遍。在MTCD=1 000、不改变各组业务量配比时对动态算法引入HARR机制, 将α=5、α=20时各组业务的吞吐量与不添加HARR机制的算法业务吞吐量进行对比, 结果如图 4所示。

从图 4可以看出, 以不添加HARR机制时的吞吐量为参照, 当α=5时, G₂和G₃分组的吞吐量均有一定下降, G₄吞吐量上升, 原因是每隔5个动态周期就执行一次轮询算法周期, 轮询时G₄业务占用了一部分原来分配给G₁、G₂和G₃的RB资源, 提升了算法对G₄的公平性。α=20时, G₂和G₃分组的吞吐量下降量、G₄吞吐量的上升量以及总吞吐量的下降量均比α=5时要小。鉴于设置α的目的是根据高低优先级业务实时比例动态地为最低优先级业务提供一定数据传输机会, 而非提高低优先级业务的吞吐量, 且不能对动态算法下的系统吞吐量造成太大影响, 因此, α的值可设置为20以上。

图 5所示为本文改进动态算法、CBP算法、PF算法、RR算法下的系统总吞吐量对比结果。

从图 5可以看出, 在PF算法和RR算法下, 为确保RB的连续性, 业务分配到的资源块大小不变, 某些数据量小的业务分配到多余的RB, 造成了资源浪费。本文动态算法分配可变大小的块以确保RB的连续性, 发送相同量的数据时所需RB更少, 且与静态CBP算法、PF算法和RR算法相比, 本文算法中业务因错过最终期限而传输失败的可能性大幅降低, 最终算法在提高系统吞吐量的同时也保证了紧急信息更快更有效地被送达。在当前仿真条件下, 本文算法的系统吞吐量比PF算法提高约15%, 比RR算法提高约41%。添加HARR机制的动态算法在α较大时对系统吞吐量影响很小, 但此机制可有效避免网络拥挤时低优先级业务长期得不到服务的现象。

4 结束语

本文提出一种基于延迟容忍剩余时长的M2M业务优先级调度算法。每个TTI结束时动态更新业务所属分组, 引入混合自动轮询机制解决算法对低优先级业务的调度不公平问题。仿真结果表明, 与传统静态算法相比, 该算法能充分利用M2M业务多QoS等级的特性, 且在网络容量较小时可有效避免低优先级业务长期得不到调度的现象。下一步将结合半静态调度思想对动态调度方案中较高的信令开销进行优化, 使其更适用于M2M的海量业务调度。