, 郑敏1, 谭冲1, 刘洪1 1. 中国科学院上海微系统与信息技术研究所, 上海 200050;
2. 中国科学院大学, 北京 100049
2018年5月24日 收稿; 2018年7月16日 收修改稿
基金项目: 国家自然科学基金（61401445）资助
通信作者: 金叶奇，E-mail:yeqi.jin@mail.sim.ac.cn
摘要: 针对动态调度普遍存在的高信令开销问题，结合蜂窝物联网机器业务特点应用LTE半静态调度思想，提出一种资源块（resource block，RB）的动态预分配模型并设计相应的调度算法。利用设备缓冲区结合预分配参数代替传统授权调度，在低控制信道使用率和时延约束下，为业务动态分配RB数减少了资源浪费。仿真表明，算法降低了调度信令开销，控制信道有限下的时延满意度和业务信道利用率均优于动态和半静态调度算法。
关键词: 蜂窝物联网信令开销半静态调度动态预分配
RB dynamic pre-allocation scheduling scheme for cellular Internet of Things
JIN Yeqi1,2
, ZHENG Min1, TAN Chong1, LIU Hong1 1. Shanghai Institute of Microsystem and Information Technology, Chinese Academy of Sciences, Shanghai 200050, China;
2. University of Chinese Academy of Sciences, Beijing 100049, China
Abstract: For high signaling overhead in dynamic scheduling, the LTE semi-persistent scheduling (SPS) is improved in combination with the machine traffic characteristics of cellular Internet of Things. We proposed a dynamic pre-allocation model of resource block (RB) and designed a corresponding scheduling algorithm. By using device buffers in combination with pre-allocation parameters instead of traditional grant scheduling, dynamic allocation of RBs for packets under low control channel usage rates reduces the resource waste. Simulation results show that the algorithm reduces the signaling overhead of scheduling, and the delay satisfaction and utilization of traffic channel under the limited control channel are better compared to the dynamic and semi-persistent scheduling algorithms.
Keywords: cellular Internet of Thingssignaling overheadsemi-persistent schedulingdynamic pre-allocation
得益于低功率广域(low power wide area, LPWA)物联网的发展，预计2020年机器类型通信设备(machine type communication device, MTCD)数将达32亿[1]。部署于蜂窝网络的物联网如基于LTE的窄带物联网(narrow band internet of things, NB-IoT)以其广覆盖、大连接优点得到3GPP青睐[2]，NB-IoT标准考虑机器到机器(machine to machine, M2M)业务特性降低了峰值速率并简化了空口信令[3]，但授权频谱对于大规模MTCD上行业务仍为有限，尤其表现在上行业务信道(physical uplink shared channel, PUSCH)和下行控制信道(physical downlink control channel, PDCCH)。
为更好地分配PUSCH资源，制定相应策略来满足M2M业务对时延、功耗、服务质量(quality of service, QoS)等方面需求的调度已被广泛研究[4-6]，此类动态调度方案优异的性能指标建立于频繁的信令交互上，其性能分析较少提到信令开销。
控制信道不足同样制约系统容量的提升，而此方面研究相对较少。PDCCH用于调度大量小数据包(可由1或2个RB容纳)是极大的浪费，这使得控制信道即使饱和业务信道利用率仍很低。文献[7]考虑控制信道有限提出并求解最大化准入MTCD非线性规划问题；文献[8]则采用动态信道间资源分配缓解大规模MTCD引起的信令风暴；文献[9]指出降低信令开销最具吸引力的方案是数据聚合，但不同场景下方案可行性会发生改变；文献[10]提出一种基于集群的介入管理方案，MTCD集群根据其QoS配置文件定期被调度，该方案仅仅考虑确定性流量模式的静态分配；文献[11]参考LTE标准中的半静态调度提出基于资源复用条件树结构的新型调度方案，然而它仅适用于周期性数据业务。但上述两篇文献研究结果表明“一次授权，周期使用”的思想可用于减小调度开销。
为降低调度信令开销，本文结合LTE蜂窝物联网M2M业务特性和SPS思想提出一种RB动态预分配(dynamic pre-allocation, DPA)上行调度方案。首先根据MTCD测量和流量模式，利用M2M业务时延容忍特性周期性地为设备预分配相应大小RB(即时频资源)；然后推导所提方案下的传输时延概率密度函数，为预分配周期建立时延约束；最后采用设备缓冲状态报告(buffer status report, BSR)机制代替传统的授权调度，在低控制信道使用率下完成基于预分配的可变大小RB分配，以适应突发和非固定大小的数据包。仿真结果证实了该方案的有效性。
1 系统模型与约束1.1 半静态调度(SPS)机制动态调度(dynamic scheduling, DS)每次传输数据前需等待上行授权(UL grant)。受控制信道数限制动态调度的用户数有限，以VoIP(voice over IP)为例，由于语音业务数据量大，LTE带宽所能支持的用户数是其所能调度用户数的5倍左右[12]。为此LTE利用VoIP数据包大小固定、到达间隔恒为20 ms的特点提出SPS[13]，其资源分配如图 1所示。
Fig. 1
 | Download: JPG larger image |
| 图 1 SPS资源使用示意图 Fig. 1 SPS resource usage diagram 图 1 SPS资源使用示意图 Fig. 1 SPS resource usage diagram --> | |
eNB通过PDCCH给UE下达SPS指示后，UE周期性地每隔20 ms就在固定的指定时频资源位置上发送或接受VoIP数据包，有效节省了用于调度的PDCCH信令开销。不同填充的业务信道静态分配给不同用户，无填充块用于动态调度。语音用户获得更大系统容量同时也确保其QoS需求。如有必要，调度程序可重新指示时频资源位置以匹配信道条件。
1.2 动态预分配系统模型由于SPS仅适用于周期到达且数据包大小固定的业务流，本文针对M2M业务非连续到达与非固定大小数据包，提出RB动态预分配(DPA)模型如图 2。模型参数定义在表 1中。
Fig. 2
 | Download: JPG larger image |
| 图 2 动态预分配(DPA)模型 Fig. 2 Dynamic pre-allocation (DPA) model 图 2 动态预分配(DPA)模型 Fig. 2 Dynamic pre-allocation (DPA) model --> | |
Table 1
 表 1 DPA模型参数Table 1 DPA model parameters
| 表 1 DPA模型参数Table 1 DPA model parameters |
如图 2(c)，一旦设备连接(RRC_CONNECTED)并请求资源，eNB就通过初始授权周期性地为它们预分配静态资源，其大小为Θ，代表着可分配给该设备的最大RB数。稳定通信系统中设备缓冲区队列大小不会无限增长，这要求DPA周期内平均队列长度增加值ΔQ小于最大数量离开值Θ，Θ值可通过流量到达模式分析和MTCD测量获得，符合当前业务负载可能达到的最佳阈值。
与图 2(b)静态分配不同的是，在每个DPA周期中的特定时频位置，为设备分配可变大小的资源块r，而非预分配的固定大小Θ。设备和基站都使用最近队列大小数据Qp作为预先约定的自适应适配功能ξ(Qp, Θ)的输入，以计算下一个传输机会所需的上行链路资源的容量r，r小于等于初始授权时协商分配的最大值Θ。
| $\xi \left( {{Q^p},\Theta } \right) \in N.$ | (1) |
| $1 \le \xi \left( {{Q^p},\Theta } \right) \le \Theta .$ | (2) |
| $\left\{ {\begin{array}{*{20}{l}}{\xi \left( {{Q^p},\Theta } \right) \ge {Q^p},{Q^p} \le \Theta .}\\{\xi \left( {{Q^p},\Theta } \right) = \Theta ,{Q^p} > \Theta .}\end{array}} \right.$ | (3) |
1.3 模型可行性75%左右的M2M业务具备一定时延容忍性，此类业务通常有着较为固定的到达模式[15]，如周期或泊松到达。紧急型业务占比约为10%，往往由事件驱动，突发到达但发生频率低，模型牺牲数据时延性能换取低控制信道使用是合理的。基于大部分MTCD移动性较低甚至处于静态环境的事实如NB-IoT Rel-13标准中不支持连接状态的移动性管理[16]，调度期间MTCD不太可能与不同的eNB相关联，因此预分配方案可行。
1.4 DPA周期设计延迟容忍仅代表业务可接受一定程度时延而非无时延约束。本文假设MTCD业务是平均到达为λ的泊松过程，图 3为业务的到达与服务过程。
Fig. 3
 | Download: JPG larger image |
| 图 3 业务到达与发送过程 Fig. 3 Traffic arrival and delivery process 图 3 业务到达与发送过程 Fig. 3 Traffic arrival and delivery process --> | |
业务时延容忍时长(delay tolerance time, DTT)为σDTT，DPA周期Tdpa的设计受限于两个预定义服务要求:时延约束与空缓冲区概率。
1) 时延约束
如图 3(a)，T1至T2间新达到的分组被缓存并在T2时刻统一上报其大小，以此确定下一周期T3时刻的资源分配。由于预分配的周期性，新到达分组在设备缓冲区被缓存，因此距离BSR上报存在着一定延迟。这个延迟τd是随机变量，Tdpa越大τd就越大。通过以下3个参数表征DPA方案带来的BSR上报时延：最大时延τmax，平均时延τ以及概率时延τp。显然τmax=Tdpa，τp是指给定目标概率P，有prob{τd≤τp}=P。为得到τ和τp，需推导出随机变量τd的概率密度函数。
考虑在第(p-1)和p个DPA周期之间有M个分组到达的一般情况，则第m个分组到达时间sm为
| ${s_m} = \left( {p - 1} \right){T_{{\rm{dpa}}}} + \sum\limits_{i = 1}^m {{x_i}} .$ | (4) |
| ${d_m} = p{T_{{\rm{dpa}}}} - {s_m} = {T_{{\rm{dpa}}}} - \sum\limits_{i = 1}^m {{x_i}} .$ | (5) |
| ${s_m} = \sum\limits_{i = 1}^m {{x_i}} .$ | (6) |
| ${f_{{x_1}{s_2}}}\left( {{x_1},{s_2}} \right) = {f_{{X_1}}}\left( {{x_1}} \right){f_{{X_2}}}\left( {{s_2} - {x_1}} \right).$ | (7) |
| $\begin{array}{l}{f_{{s_2}\left( {{s_2}} \right)}} = \int_{{x_1}}^{{x_1} + {T_{{\rm{dpa}}}}} {P\left( {{S_2} = \left( {s + 1} \right){T_{{\rm{dpa}}}} - \Delta x|{X_1} = } \right.} \\\;\;\;\;\;\;\;\;\;\;\left. {{x_1} + \Delta x} \right) \times {f_{{X_1}}}\left( {{X_1} = {x_1} + \Delta x} \right){\rm{d}}x\\\;\;\;\;\;\;\;\;\;\; = \frac{1}{{{T_{{\rm{dpa}}}}}}\int_x^{{x_1} + {T_{{\rm{dpa}}}}} {P\left( {{S_2} = \left( {s + 1} \right){T_{{\rm{dpa}}}} - \Delta x|{X_1} = } \right.} \\\;\;\;\;\;\;\;\;\;\;\left. {{x_1} + \Delta x} \right){\rm{d}}x.\end{array}$ | (8) |
| $\begin{array}{*{20}{c}}{{f_{{X_1}{S_2}}}\left( {{x_1},{S_2}} \right) = {\lambda ^2}{{\rm{e}}^{ - \lambda {x_1}}}{{\rm{e}}^{ - \lambda \left( {{S_2} - {x_1}} \right)}} = {\lambda ^2}{{\rm{e}}^{ - \lambda {S_2}}},}\\{0 \le {x_1} \le {S_2}.}\end{array}$ | (9) |
| ${f_{{S_1}{S_{M + 1}}}}\left( {{S_1}, \cdots ,{S_M},{S_{M + 1}}} \right) = {\lambda ^2}{{\rm{e}}^{\left( { - \lambda {S_{M + 1}}} \right)}}.$ | (10) |
| $0 \le {s_1} \le \cdots \le {s_M} \le {s_{M + 1}}.$ | (11) |
| $\begin{array}{l}PDF\left( {{d_m}} \right) = 1/{T_{{\rm{dpa}}}},\\CDF\left( {{d_m}} \right) = {d_m}/{T_{{\rm{dpa}}}},0 \le {d_n} \le {T_{{\rm{dpa}}}}.\end{array}$ | (12) |
| $\bar \tau = {T_{{\rm{dpa}}}}/2,{\tau _p} = P{T_{{\rm{dpa}}}}.$ | (13) |
| ${T_{{\rm{dpa}}}} + \min \left\{ {{\tau _{{\rm{max}}}},2\bar \tau ,{\tau _p}/P} \right\} + {t_{{\rm{slot}}}} \le {\sigma _{{\rm{DTT}}}}.$ | (14) |
| ${T_{{\rm{dpa}}}} \le {\sigma _{{\rm{DTT}}}} - \min \left\{ {{\tau _{{\rm{max}}}},2\bar \tau ,{\tau _p}/P} \right\} - 1.$ | (15) |
需尽量避免一个DPA周期内无新分组到达造成BSR报告为0的情况，否则分配的无线资源可能因为缓冲区无数据而被浪费，尽管通过动态分配已将浪费减为最小。定义一个DPA周期内缓冲区为空的概率为Pempty，根据泊松过程分布得到
| ${P_{{\rm{empty}}}} = P\left( {\frac{1}{\lambda } \ge {T_{{\rm{dpa}}}}} \right).$ | (16) |
| ${T_{{\rm{dpa}}}} > 1/\lambda .$ | (17) |
| $\begin{array}{l}r = \xi \left( {Q,\Theta } \right) = \left\{ {\begin{array}{*{20}{l}}{\min \left( {{N_{{\rm{PB}}}},\Theta } \right),}&{{\rm{BSR}} > 0}\\{1,}&{其他情况}\end{array},} \right.\\{N_{{\rm{RB}}}} = \frac{{2L}}{{\left( {{N_{{\rm{SC}}}} \times l} \right) \times {\rm{CR}} \times {\rm{MS}}}}.\end{array}$ | (18) |
步骤1) ? ?识别请求调度的业务类型:若业务属于时延容忍类则符合预分配条件，并在约束(15)和(17)下最大化Tdpa值后依次执行步骤2~6；若业务属于紧急类型、HARQ重传或不符合约束(15)和(17)的时延容忍类，则采用动态调度并跳过步骤2)~5)；
步骤2)? ? eNB基于最新MTCD测量，确定预分配给设备的最大RB数Θ，静态帧偏移v，子帧号w，RB起始索引k和适配函数ξ(.)，通过初始授权通知设备预分配参数；
步骤3)? ?设备依据预分配参数和存储的最近队列大小Qp，利用自适应适配功能ξ(Qp, Θ)确定所使用的r个RB，r值由eNB和设备根独立计算得到；
步骤4)? ?剩余Θ-r个RB资源eNB用于动态调度紧急业务和HARQ重传；
步骤5)? ?设备完成当前DPA周期的数据传输同时上报当前缓冲区队列状态，以计算下周期资源分配；
步骤6)? ?若RRC重新建立连接或需更新预分配参数，则更新eNB预分配数据库，重新激活并通知设备以下预分配参数：DPA周期Tdpa，最大RB值Θ，帧偏移量v，子帧号w，RB起始索引k和适配函数ξ(.)。
3 仿真OPNET搭建系统级仿真环境，表 2为部分仿真参数设置。设备时延期限为101 ms，业务到达过程为平均时间间隔为20 ms的泊松过程，紧急设备占比10%。通过与完全动态调度(DS)算法以及LTE中已实现的半静态调度(SPS)算法进行对比来评估所提出动态预分配调度(DPAS)算法性能。
Table 2
表 2 仿真参数Table 2 Simulation parameters
| 表 2 仿真参数Table 2 Simulation parameters |
SPS算法为紧急业务动态分配资源，其他业务静态分配固定的2个RB，DS算法则对所有业务进行动态调度，所采用的DS算法为比例公平算法。图 4给出DS、SPS和DPAS这3种算法在不同MTCD数时的上行业务时延期限满足情况以及PDCCH和PUSCH负载情况。
Fig. 4
 | Download: JPG larger image |
| 图 4 不同MTCD数下3种算法的延迟满意度、PDCCH使用率和PUSCH使用率 Fig. 4 Delay satisfaction and utilization rates of PDCCH and PUSCH of the three algorithms at different MTCD numbers 图 4 不同MTCD数下3种算法的延迟满意度、PDCCH使用率和PUSCH使用率 Fig. 4 Delay satisfaction and utilization rates of PDCCH and PUSCH of the three algorithms at different MTCD numbers --> | |
从图 4(a)可看出随着MTCD数量的增加，DPAS算法在业务时延方面表现最佳，MTCD为3 000时满足时延要求的业务占比高达88%，而另外两种算法在MTCD大于1 500后时延满意度迅速下降。
图 4(b)给出相同信道条件下3种算法的PDCCH信道负载情况。DPAS算法控制信道使用率略高于SPS算法，因为可变大小的RB预分配使得系统剩余用于动态调度的RB多余SPS算法。DS算法PDCCH使用率最高，在MTCD为2 000时接近满负荷，这解释了为何DS算法时延满意度较差。
图 4(c)对比3种算法的业务信道PUSCH使用率，尽管SPS算法控制信道负载优于DPAS算法，但由4(c)可知同等情况下的SPS算法PUSCH使用率更高因此PUSCH更早趋于饱和。SPS静态调度部分的固定大小RB分配是造成SPS使用率偏高的主要原因，它不能适应流量变化导致大RB块可能用于传输小数据而被浪费。DPAS算法改善了SPS的非灵活分配，可以达到高业务信道使用率。DS算法则由于PDCCH限制而出现无法完全利用PUSCH的现象。
最后，为SPS算法分别分配固定的1、2、3个RB，在不同的业务到达间隔下与DPAS算法进行比较以评估RB浪费情况，图 5给出结果。公式(2)表明DPAS算法最小RB分配值为1个，随着业务达到间隔增大若缓冲区无数据则该RB被浪费。由于小RB分配造成了设备缓冲区的增长，因此图 5中每周期固定分配1个RB的SPS算法浪费最小。SPS算法RB浪费随着固定分配RB数的增加而增加，DPAS算法优于它们。
Fig. 5
 | Download: JPG larger image |
| 图 5 每帧平均浪费的RB数(SPS周期和DPAS周期均为50 ms) Fig. 5 The average number of the wasted RBs per frame (50 ms for both the SPS and DPAS periods) 图 5 每帧平均浪费的RB数(SPS周期和DPAS周期均为50 ms) Fig. 5 The average number of the wasted RBs per frame (50 ms for both the SPS and DPAS periods) --> | |
4 总结本文针对蜂窝物联网M2M业务特征提出一种RB预分配下的动态调度模型，引入BSR代替eNB指示的方案，推导方案需满足的约束条件并给出相应的算法流程，旨在降低调度过程中的PDCCH信令开销且适应可变大小的业务数据。仿真结果表明，本文算法时延性能和RB利用率优于动态调度算法和SPS算法，为控制信道有限下的物联网调度提供了一种解决思路。
参考文献
| [1] | CISCO. Cisco visual networking index: global mobile data traffic forecast update 2015-2020[R]. Cisco Public Information, 2016: 1-5. |
| [2] | 薛滔, 邱玲. 蜂窝网络中机器类设备突发上行随机接入的优化[J]. 中国科学院大学学报, 2016, 33(5): 669-673. |
| [3] | 夏学成. NB-IOT发展概述[J]. 广东通信技术, 2017(6): 6-9. |
| [4] | Lioumpas A S, Alexiou A. Uplink scheduling for machine-to-machine communications in LTE-based cellular systems[C]//IEEE GLOBECOM Workshops. IEEE, 2011: 353-357. |
| [5] | Mostafa A, Gadallah Y. A statistical priority-based scheduling metric for M2M communications in LTE networks[J]. IEEE Access, 2017, 5: 8106-8117. Doi:10.1109/ACCESS.2017.2700409 |
| [6] | Kay K S, Kwee W K, Yin O S. A study of Bayesian scheduling for M2M traffic in wireless LTE network[C]//International Conference on Robotics, Automation and Sciences. 2017: 1-4. |
| [7] | 王鑫, 邱玲. H2H与M2M共存场景的准入控制及资源分配[J]. 中国科学院大学学报, 2016, 33(3): 427-432. |
| [8] | Chen T H, Chang J W, Wei H Y. Dynamic inter-channel resource allocation for massive M2M control signaling storm mitigation[C]//Vehicular Technology Conference. IEEE, 2017: 1-5. |
| [9] | Ksentini A, Hadjadj-Aoul Y, Taleb T. Cellular-based machine-to-machine:overload control[J]. Network IEEE, 2013, 26(6): 54-60. |
| [10] | Lien S Y, Chen K C. Massive access management for QoS guarantees in 3GPP machine-to-machine communications[J]. IEEE Communications Letters, 2011, 15(3): 311-313. Doi:10.1109/LCOMM.2011.011811.101798 |
| [11] | You C, Zhang Y. A radio resource scheduling scheme for periodic M2M communications in cellular networks[C]//Sixth International Conference on Wireless Communications and Signal Processing. IEEE, 2014: 1-5. |
| [12] | 白炜. LTE系统的半静态调度传输解决方案[J]. 邮电设计技术, 2010(1): 45-48. Doi:10.3969/j.issn.1007-3043.2010.01.010 |
| [13] | Jiang D, Wang H, Malkamaki E, et al. Principle and performance of semi-persistent scheduling for VoIP in LTE system[C]//International Conference on Wireless Communications, NETWORKING and Mobile Computing. IEEE, 2007: 2861-2864. |
| [14] | 3 GPP. Evolved universal terrestrial radio access (E-UTRA); Medium Access Control (MAC) protocol specification. TS36.321 V10.8.0[S/OL].(2013-03-18)[2018-05-20].http://portal.3gpp.org/desktopmodules/Specifications/SpecificationDetails.aspx?specificationId=2437. |
| [15] | Chen B, Fan Z, Cao F, et al. Class based overall priority scheduling for M2M communications over LTE networks[C]//Vehicular Technology Conference. IEEE, 2015: 1-5. |
| [16] | 邹玉龙, 丁晓进, 王全全. NB-IoT关键技术及应用前景[J]. 中兴通讯技术, 2017, 23(1): 43-46. Doi:10.3969/j.issn.1009-6868.2017.01.010 |
| [17] | 王东升, 刘玉堂. 泊松过程在排队论中的应用[J]. 河南机电高等专科学校学报, 2007, 15(4): 121-122. Doi:10.3969/j.issn.1008-2093.2007.04.048 |
