2016, Vol. 48
2. 哈尔滨工业大学 电子与信息工程学院，哈尔滨 150001
2. School of Electronics and Information Engineering, Harbin Institute of Technology, Harbin 150001, China
随着通信技术的快速发展，人们对高数据速率、高服务质量的移动通信业务的需求日益增长.为了应对这个趋势，第三代合作伙伴计划3GPP(3rd generation partnership project)组织启动了长期演进LTE(long term evolution)项目[1].其目标就是利用有限的无线资源来实现高速的全分组数据传输，在满足业务需求的同时，最大化系统吞吐量并保障用户间的公平性.而实现这一目标的关键就是无线资源的合理调度, 因此作为LTE核心技术之一的分组调度受到了广泛关注.
非实时业务如FTP、WWW等是LTE系统中重要的业务应用类型.非实时业务调度的主要目标是在保证用户间公平性的前提下，最大化系统吞吐量.早期的资源算法如轮询RR(round robin)算法在所有用户间轮流进行资源分配，保证每个用户都可以获得相同的无线调度机会；吞吐量公平BET(blind equal throughput)算法[2]则是为所有的用户分配等量的无线资源，尽力保证所有的用户获得相等的吞吐量.这些算法的目标都是为了获得较好的公平性，而忽略了用户的信道条件，因此算法的系统吞吐量很低.而最大吞吐量MT(maximum throughput)算法旨在最大化系统吞吐量，把所有的资源都分配给信道条件最好的用户，而信道条件差的用户难以得到系统资源，因此用户间公平性极差.为了解决这些问题，研究人员提出了比例公平PF(proportional fair)算法[3-4]. PF算法综合考虑了用户的信道条件和平均吞吐量，因此在系统吞吐量和用户公平性上都可以获得良好的性能. PF算法因能在系统吞吐量和用户公平性之间取得良好的平衡而备受关注，因此后期提出的广义比例公平GPF(generalized proportional fair)算法以及平均吞吐量TTA(throughput to average)算法等都是在其基础上得到[5].但是在讨论上述算法性能的文献中，其仿真采用的业务模型均为full buffer业务，这与实际数据分组业务的模型差别极大[6]，因此当上述算法运用到实际的系统中时，其性能会有较大下降.
为了解决此问题，本文在有限缓存(finite-buffer)队列模型下，综合考虑了用户的信道状态和用户缓冲区中待传送的数据包信息，提出一种兼顾用户吞吐量和用户公平性的算法—基于缓存信息的调度BIBS(buffer information based scheduling)算法.与PF算法相比，BIBS算法可以有效提升系统吞吐量，同时用户间公平性和通信中断性能也得到了极大的改善.
1 系统模型考虑一个多小区的LTE系统，本文中参与调度的用户只随机分布在中心小区中.中心小区包含25个物理资源块PRB(physical resource block)，占据5MHz带宽.基站位于小区的中心位置，不考虑用于信令传输的资源，即所有的资源块都参与中心小区内的用户调度.
用户的瞬时下行信道信干噪比SINR(signal to interference plus noise ratio，)随物理资源块和TTI的不同而不同.根据用户收到的瞬时下行SINR值，用户在每个TTI都将相应的CQI(channel quality indicator，信道质量指示)报告给基站，基站可以根据上报的CQI信息及时调整和更新用户的信道状态信息，基站可以根据上报的CQI信息及时调整和更新用户的信道状态信息.这样基站就可以动态、及时获取和更新用户的信道状态信息.而当系统检测到用户信道处于慢变状态时，可以调整CQI上报的周期，从而在节省信令开销和提高通信质量之间实现良好的折衷.根据CQI信息，系统采用自适应调制编码AMC(adaptive modulation and coding)技术，在共享信道上应用不同的调制编码方案MCS(modulation and coding scheme)来匹配信道，即在信道信噪比低时，采用较低调制阶数的调制方式和较低码率的信道编码方案；当信道质量较好时，可以增加调制阶数，同时提高信道编码的码率，从而实现在多用户情况下进行系统资源的最优分配.
3GPP给出了RSIN与CQI的对应关系以及CQI与MCS的对应关系，如表 1所示.本文利用下式来确定用户k在第i个PRB上可以获得的理论数据速率：
| $ r_k^i\left( t \right) = \left( {N - 3} \right) \times M \times {Q_k} \times n{\rm{bits}}_k^i\left( t \right)/1\;024 $ | (1) |
|
表 1 MCS与RSIN映射表 Table 1 Mapping of downlink RSIN to MCS |
式中：N为一个子帧上的OFDM符号数；M为一个资源块上的子载波数；Qk是用户k一个符号所能携带的比特数，由调制方式所决定；nbitski为根据用户的RSIN值由表 1映射得到的用户k在第i个PRB上的编码速率[7].
在实际的蜂窝移动通信系统中，基站为每位用户分配了一个缓存区.缓存区中每个业务流缓存队列数据包采取先进先出策略.位于基站侧的调度器根据采用的调度算法来决定用户的优先级，然后在每个TTI选择调度哪个用户.如果选定某个用户开始传输，调度器将为此用户分配一个或多个PRB，当前用户传输的数据速率将依据用户上报的CQI值和用户缓冲区内待传送的比特数来共同确定.
2 算法分析 2.1 传统比例公平算法传统比例公平算法提出的基本思想是兼顾系统吞吐量和用户间公平性的准则下，计算小区内的每个待调度用户在每个资源块上的优先级.对于第i个物理资源块，调度时选取当前资源块上具有最大优先级的用户k，其优先级计算公式为
| $ K = {\rm{argmax}}\left( {\frac{{r_k^i\left( t \right)}}{{{{\bar R}_k}\left( t \right)}}} \right), $ |
式中：rki(t)为用户k在第i个PRB上获得的理论数据传输速率；Rk(t)为用户k在时间窗内的平均吞吐量，其定义为
| $ {{\bar R}_k}\left( t \right) = \left( {1 - \frac{1}{{{t_c}}}} \right) \times {{\bar R}_k}\left( {t - 1} \right) + \left( {\frac{1}{{{t_c}}}} \right) \times {r_k}\left( {t - 1} \right). $ |
式中：tc为更新时间窗，其长度一般会足以覆盖快衰落的变化；rk(t)是用户k在时隙t时获得的数据速率.
由PF算法的定义可知，该调度算法主要选择无线信道条件好的用户来提供调度机会，但当某个用户连续通信时，由于该用户时间窗内的平均吞吐量不断增大，因而导致该用户优先级降低.这种分组调度机制使得小区内的用户不会由于信道条件好而长时间占据无线信道资源，因此保证了小区内用户间的公平性[8].
2.2 基于缓存信息的调度算法在讨论非实时业务调度算法的相关文献中，其仿真采用的业务均为full buffer业务，缓冲区一般采用的都是无限缓存(Infinite-Buffer)队列模型.无限缓冲队列模型是非实时业务数学模型，模型中假设业务都拥有无限长的数据缓存队列，也即业务随时都有无穷多的数据在等待着传输.但是在实际的蜂窝移动通信系统中，每个用户的业务量不可能是无穷的，而是随着业务的类型以及用户的需求时变的，如果采用无限缓存队列模型，难以体现出调度算法在实际通信系统中的性能.因此，结合实际无线分组数据业务的特点，本文采用更为实际的有限缓存队列模型，如图 1所示.缓冲区数据包的数量是根据基站来的数据包以及用户已传送的数据包共同确定，影响其数量的因素主要有数据包相继到达的间隔时间分布或到达的统计特性等[9].
|
图 1 分组数据业务模型 Figure 1 Wireless packet service model |
通过对PF算法的分析可知，PF算法综合考虑了用户的信道状态和用户的窗吞吐量，可以在系统吞吐量和公平性之间取得良好的折中，但在有限缓存队列模型下，由于PF算法并没有考虑用户缓冲区的数据信息，因此有可能待传输信息量很小而信道条件好的用户会被选中服务，从而导致信道的传输数据量较小，与此同时，其他用户却难以得到资源，从而导致资源不能被有效利用.因此本文提出一种新的处理非实时业务的分组资源调度算法—BIBS算法. BIBS算法同时考虑了用户的信道状态和用户缓冲区的队列信息，这样BIBS算法可挑选出既有大量数据等待传送，同时信道条件较好的用户接受调度，能够充分利用系统资源的同时，尽量保证所有的用户都能够获得资源.与PF算法相比，BIBS算法在系统吞吐量，用户间的公平性以及通信中断性能上都能得到有效的提升.
BIBS算法是在有限缓存队列模型下，兼顾系统吞吐量和用户间的公平性而提出的，调度示意图如图 2所示.
|
图 2 BIBS算法调度示意图 Figure 2 Flowchart of BIBS algorithm |
对于第i个物理资源块，用户k的优先级计算公式为
| $ M_k^i = r_k^i\left( t \right) \times {w_k}\left( t \right), $ | (2) |
式中，rki(t)为用户k在第i个PRB上获得的理论数据传输速率.根据表 1和式(1)可知，rki(t)由用户上报的CQI值所决定，因此rki(t)可表征用户的信道状态；wk(t)是用户k在缓冲区中待传送的数据包的数目.对于第i个物理资源块，根据下式对用户的优先级数值进行升序排列，然后选取优先级最大的用户K接受调度：
| $ K = {\rm{arg}}\;{\rm{max}}\;M_k^i. $ | (3) |
结合式(2)和式(3)可知，信道条件越好的用户优先级越高，可以获得更多的调度机会，可有效提升系统吞吐量.但当某个用户连续通信时，由于该用户缓存区队列中待传送数据包的数据wk(t)不断减少，甚至为零，因而导致该用户优先级降低.对于信道条件较差的用户，即使刚开始难以得到调度机会，但是随着用户wk(t)的增多，其优先级也会随之提升.因此即使是信道条件差的用户也可以获得一定的服务机会. BIBS算法综合考虑了用户信道状态和用户缓冲区的队列信息，这样就有效保证了系统吞吐量和用户间公平性.
算法 基于缓存信息的调度(BIBS)算法
输入：
系统调度时隙数目NTTI;
系统资源块数目NPRB;
接入系统用户数目NUE;
每个用户在每个PRB上的数据速率r11, r12…rki.
输出：
资源块分配矩阵allocation_RB.
1) 赋值i_TTI=1；
2) 查看每个用户在当前时隙在缓冲区中待传送的数据包的数目w1(i_TTI)，w2(i_TTI), …, wk(i_TTI)；
3) 根据式(2)计算每个用户在, 每个物理资源块上的优先级数值；
4) 赋值i_PRB=1；
5) 根据式(3)挑选出第i_PRB个物理资源块上优先级最高的用户K；
6) 在第i_PRB个物理资源块上传输用户K的数据，并更新资源块分配矩阵allocation_RB；
7) i_PRB=i_PRB+1；
8) 判断i_PRB是否等于NPRB，若不相等，则重复步骤5)-8)，直至i_PRB等于NPRB；
9) i_TTI=i_TTI+1；
10) 判断i_TTI是否等于NTTI，若不相等，则重复步骤2)-10)，直至i_TTI等于NTTI；
11) 返回资源块分配矩阵allocation_RB.
3 仿真分析 3.1 仿真场景的设置本文主要对PF和BIBS算法从系统吞吐量、公平性和系统中断性能等三个方面进行性能仿真.系统分别采用平均速率Ravg为128 kbps、最低速率门限rth为50 kbps和平均速率Ravg为256 kbps、最低速率门限rth为100 kbps的分组数据业务来验证BIBS算法的性能，主要的系统仿真参数设置如表 2所示，采用的无线分组业务模型如表 3所示.
|
|
表 2 LTE下行系统参数设置 Table 2 Downlink LTE system parameters |
|
|
表 3 无线分组业务模型[10] Table 3 Wireless packet service model |
为描述算法的性能，这里定义系统的吞吐量为
| $ {\rm{T}}{{\rm{h}}_{{\rm{sys}}}} = \sum\limits_t^{{N_{{\rm{TTI}}}}} {\sum\limits_k^{{N_{{\rm{UE}}}}} {{v_{k,t}}} } /{N_{{\rm{TTI}}}}. $ |
式中：Thsys是系统吞吐量，NTTI仿真时间，NUE是仿真用户总数目，vk, t是用户k在第t个调度周期获得的传输速率.
用户间的公平性指数Jain’s指数表示为
| $ F = \frac{{{{\left( {\sum\limits_k^{{N_{{\rm{UE}}}}} {{\rm{T}}{{\rm{h}}_{{\rm{ue}}}}\left( k \right)} } \right)}^2}}}{{{N_{{\rm{UE}}}} \times {{\sum\limits_k^{{N_{{\rm{UE}}}}} {{\rm{T}}{{\rm{h}}_{{\rm{ue}}}}\left( k \right)} }^2}}}. $ |
式中: Thue(k)是用户k在仿真时间内获得的吞吐量，可表示为
同时，定义系统的中断率为
| $ {P_{{\rm{outage}}}} = P\left\{ {\overline {{T_k}} \left( t \right) < {r_{th}}} \right\}, $ |
式中
图 3是PF算法和BIBS算法系统吞吐量对比图.从图 3中可以看出，随着用户数目的增多，系统吞吐量随之提升，而且BIBS算法的系统吞吐量相比PF算法有明显提升.这是由于PF算法并未考虑缓存队列信息，因此被挑选中的用户虽然优先级较高，但是该用户缓存队列中待传送的数据包可能很少，甚至没有，这样可能会导致资源的浪费.而BIBS算法在考虑用户信道条件的同时，也考虑到了缓存队列中数据包的数目，因此待传输数据量较少的用户，优先级也会降低，从而避免了资源浪费的现象；而且对于用户具有同样缓存信息的条件下，BIBS算法优先挑选信道条件好的用户接受调度，因此BIBS算法的系统吞吐量得到了有效提升.此外，由图 3也可以发现，随着用户平均速率的增加，系统的吞吐量也随之增大.
|
图 3 两种算法的系统吞吐量对比 Figure 3 Comparison about system throughput |
图 4是PF算法和BIBS算法系统公平性对比图.从图 4中可以看出，随着用户数目的增多，用户间的公平性随之降低，而且BIBS算法比PF算法的公平性有较大提升.这是由于PF算法虽然也引入参数“用户的窗吞吐量”来保证用户间的公平性，但是此参数与时间窗相关，即在时间窗tc这一段时间内，信道条件差的用户至少可以得到一次服务机会，但是由于用户信道条件很差，即使得到一次服务机会，其获得的数据速率仍然很低，因此用户间的公平性并不是很好.而BIBS算法则是通过缓冲区用户待传送的数据包个数这一参数来保证用户间的公平性.由于所有用户都设置为相同的业务，所以其传送的数据量大致相同，对于信道条件差的用户，如果服务次数少，则发出的数据包个数必然较少，会导致缓冲区待传送数据包个数的增多，因此用户优先级也会随之提升，就能发出更多的数据包.所以相比于PF算法，BIBS算法可以更加有效地保证用户间吞吐量的公平性，而不是用户间调度机会的公平性.
|
图 4 两种算法的用户公平性对比 Figure 4 Comparison about fairness |
图 5是PF算法和BIBS算法系统通信中断性能对比图.从图 5中可以看出，随着用户数目的增多，系统的通信中断概率随之提升.当系统轻载时，两种算法中断性能相差不大.但随着系统中接入用户数目的增加，BIBS算法的中断性能相比于PF算法有明显提升.这是由于在系统处于重载时，系统中必然有较多信道条件较差的用户，在这种情况下，系统中有大量的用户有相同的信道条件或是缓存区内等待传输的数据包状态，BIBS算法是同时考虑用户缓存区内待传输的数据包的信息和用户的信道信息，因此在用户具有同样的缓存信息条件下，BIBS算法优先挑选信道条件好的用户接受调度，反之，对于相同信道条件下的用户，BIBS算法也会优先挑选缓存区内等待传输数据量较大的用户接受调度.由于系统资源是有限的，必定有一定用户的调度请求得不到满足. BIBS算法尽量利用有限的资源传输更多的数据，因此相比于PF算法，BIBS算法的中断性能大大提升.
|
图 5 两种算法的中断性能对比 Figure 5 Comparison about outage probability |
结合无线分组数据业务的特点，在有限缓冲队列模型下，提出了综合考虑了用户信道条件和缓存区内待传送的数据包信息的BIBS算法，同时把PF算法作为对比算法，分别采用平均速率Ravg为128 kbps和256 kbps的分组数据业务，对上述两种算法进行了仿真分析.根据仿真结果可知，当系统负载较轻，即用户数低于40时，两种算法性能相差不大.但是随着用户数目的增加，BIBS算法的系统吞吐量比PF算法提升了10%~20%，而且BIBS算法比PF算法的用户公平性也有了较大提升.此外，与PF算法相比，BIBS算法的通信中断性能也得到了极大的改善.
| [1] | SESIA S, TOUFIK I, BAKER M, et al. LTE-The UMTS Long Term evolution: from theory to practice[M]. New York: John Wiley & Sons, 2009 : 1 -5. |
| [2] | ASTELY D, DAHLMAN E, FURUSKAR A, et al. LTE: the evolution of mobile broadband[J]. IEEE Communications Magazine,2009, 47 (4) : 44-51. DOI: 10.1109/MCOM.2009.4907406 |
| [3] | KELA P, PUTTONEN J, KOLEHMAINEN N, et al. Dynamic packet scheduling performance in UTRA long term evolution downlink[C]// 3rd International Symposium on Wireless Pervasive Computing (ISWPC). Santorini: IEEE, 2008: 308-313. |
| [4] | KWAN R, LEUNG C, ZHANG J. Proportional fair multiuser scheduling in LTE[J]. Signal Processing Letters, IEEE,2009, 16 (6) : 461-464. DOI: 10.1109/LSP.2009.2016449 |
| [5] | PROEBSTER M, MUELLER C M, BAKKER H. Adaptive fairness control for a proportional fair LTE scheduler[C]// IEEE 21st International Symposium on Personal Indoor and Mobile Radio Communications (PIMRC). Instanbul: IEEE, 2010: 1504-1509. |
| [6] | CAPOZZI F, PIRO G, GRIECO L, et al. Downlink packet scheduling in lte cellular networks: Key design issues and a survey[J]. IEEE Communications Surveys & Tutorials,2012, 15 (2) : 678-700. DOI: 10.1109/SURV.2012.060912.00100 |
| [7] |
朱春梅, 徐菲, 王瑜, 等. 第三代移动通信系统中分组数据业务模型的研究[J].
重庆邮电大学学报,2002, 14 (3) : 1-6.
ZHU Chunmei, XU Fei, WANG Yu, et al. Research on Wireless Packet Service Model in 3G Mobile Communication System[J]. Journal of Chongqing University of Posts and Telecommunications,2002, 14 (3) : 1-6. DOI: 10.3979/j.issn.1673-825X.2002.03.001 |
| [8] |
吴宣利, 韩杏玲, 赵婉君. LTE系统中一种低丢包率的实时业务调度算法[J].
哈尔滨工业大学学报,2015, 47 (3) : 24-28.
WU Xuanli, HAN Xingling, ZHAO Wanjun. A low packet loss rate scheduling algorithm for real-time traffics in LTE system[J]. Journal of Harbin Institute of Technology,2015, 47 (3) : 24-28. DOI: 10.11918/j.issn.0367-6234.2015.03.004 |
| [9] | REBEKKA B, MALARKODI B. Performance evaluation of resource allocation schemes in LTE downlink[C]//2014 International Conference on Electronics and Communication Systems (ICECS). Coimbatore: IEEE, 2014:1-4. |
| [10] |
刘壮. LTE系统中下行链路的分组调度算法研究[D].北京:北京邮电大学, 2014.
LIU Zhuang. Research on packet scheduling algorithm in LTE downlink system[D]. Beijing: Beijing University of Posts and Telecommunication, 2014. http://cdmd.cnki.com.cn/article/cdmd-10013-1015526374.htm |
| [11] | BASUKALA R, MOHD RAMLI H A, SANDRASEGARAN K. Performance analysis of EXP/PF and M-LWDF in downlink 3GPP LTE system[C]//First Asian Himalayas International Conference on AH-ICI 2009. Kathmandu: IEEE, 2009: 1-5. |