分组数据业务调度算法课件

1、分组数据业务调度算法王亚峰 wangyf9/22/20221BUPT-QUALCOMM RESEARCH CENTER 前向链路9/22/20222BUPT-QUALCOMM RESEARCH CENTER 提纲调度算法的研究背景调度算法原理 最大C/I算法轮循算法正比公平算法公平性与累积分布函数曲线参考文献9/22/20223BUPT-QUALCOMM RESEARCH CENTER 调度算法的研究背景（一）数据业务和话音业务的特点传输速率时延特性传输的正确性9/22/20224BUPT-QUALCOMM RESEARCH CENTER 调度算法的研究背景（三）快速小区交换技术类似于硬切换技

2、术，在每一时刻移动台只同信号最好的基站通信最佳扇区的指示由R-CQICH信道反馈由于没有软切换的宏分集增益，处于小区边缘的用户C/I很低9/22/20226BUPT-QUALCOMM RESEARCH CENTER 调度算法的研究背景（四）速率控制的基本思想每个时隙移动台测量其C/I，经量化后通过R-CQICH信道反馈至基站基站根据反馈的C/I、可供分配的Walsh码、待传输数据队列的长度确定最大可支持的数据速率然后从所有请求传输的用户中，按照一定的调度算法选出其中的一个用户，给予传输机会9/22/20227BUPT-QUALCOMM RESEARCH CENTER 调度算法原理（一）最大C/

3、I算法基站总是选择信道条件最好的用户，给予传输机会如果只在信道条件好的时候传输，可以提高传输速率、降低编码的冗余通过实时的改变传输方案来适应时变的信道环境，可以提高吞吐量9/22/20229BUPT-QUALCOMM RESEARCH CENTER 调度算法原理（二）最大C/I算法由于具有多用户分集增益，这种调度算法是所有可能的算法中系统吞吐量最大的但这种算法存在的最大问题是公平性差，接近基站的移动台吞吐量很大，而小区边缘的用户得不到服务机会，存在“饿死”现象。因此，这种算法被认为是最不公平的9/22/202210BUPT-QUALCOMM RESEARCH CENTER 调度算法原理（三）轮

4、询算法基站不考虑用户的信道状况，随机选取用户传输由于没有多用户分集增益，系统吞吐量低每个用户享有系统资源的机会相同，因此在一定意义上它被认为是最公平的 9/22/202211BUPT-QUALCOMM RESEARCH CENTER 调度算法原理（四）轮询算法但在固定网方面的研究中提出，在讨论公平性问题时，不能只考虑分配资源的方式，还要考虑利用资源的效用，同样的资源给不同的用户获得的效用是不一样的选择不同的用户，由于请求的传输速率不同，因此传输分组占有的时隙数是不同的，即传输速率不同正是由于对资源利用的效用不同，轮询算法也不是绝对公平的9/22/202212BUPT-QUALCOMM RESE

5、ARCH CENTER 调度算法原理（五）正比公平算法为了做好吞吐量和公平性的折中，Qualcomm在HDR（High Data Rate,即1x EV DO)中提出了一种称为正比公平的调度算法 在每个时刻t，每个用户k计算一个优先权函数一个扇区的所有用户中，优先权最大的将获得传输机会9/22/202213BUPT-QUALCOMM RESEARCH CENTER 调度算法原理（六）正比公平算法在时刻t，用户k的优先权函数计算如下式中DRC(t) 是可以支持的最大传输速率，由R-CQICH反馈的 C/I计算得到 是正比公平吞吐量9/22/202214BUPT-QUALCOMM RESEARCH

6、 CENTER 调度算法原理（八）正比公平算法算法2（针对不提供实时视频业务的系统）5 算法1和算法2的区别算法2提高了公平性算法1保证了实时视频业务的时延要求9/22/202216BUPT-QUALCOMM RESEARCH CENTER 调度算法原理（九）正比公平算法在计算 时，是以时隙为单位的，如下式如果在上一时隙用户k 没有被调度上如果在上一时隙用户k被调度上 的值为如果用户队列满时的分组大小9/22/202217BUPT-QUALCOMM RESEARCH CENTER 调度算法原理（十一）正比公平算法对调度算法进行简化，可以得到下式由此可以看出，正比公平算法的实质是两个因素共同起作

7、用，相互制约以达到吞吐量和公平性的折中9/22/202219BUPT-QUALCOMM RESEARCH CENTER 调度算法原理（十二）用户吞吐量和距离的散点图由于最大C/I算法总是选择信道最好的用户，所以离基站近的用户吞吐量很高处于小区半径中间的用户，由于快衰和慢衰的影响，在一些时候C/I可以最高，因此也能被调度上，但下降趋势很快离基站远的用户，由于C/I为最大的概率很小，因此吞吐量接近于09/22/202220BUPT-QUALCOMM RESEARCH CENTER 调度算法原理（十三）图1 用户数据吞吐量和其到最佳服务扇区距离的散点图(最大C/I调度算法）9/22/202221BU

8、PT-QUALCOMM RESEARCH CENTER 调度算法原理（十四）用户吞吐量和距离的散点图由于轮询算法不考虑用户的信道状况，所以离基站近的用户其吞吐量也不是很高随着距离增加，单用户的吞吐量缓慢下降但相对而言，边缘用户的吞吐量还是比较低，这不是因为公平问题，而是前面提到的效用问题，离基站远的用户，他请求传输的速率本身就不高9/22/202222BUPT-QUALCOMM RESEARCH CENTER 调度算法原理（十五）图 2 用户数据吞吐量和其到最佳服务扇区距离的散点图(轮询调度算法）9/22/202223BUPT-QUALCOMM RESEARCH CENTER 调度算法原理（十

9、六）用户吞吐量和距离的散点图正比公平算法介于前二者之间，最高吞吐量虽远低于最大C/I算法，但高于轮询算法随着距离增加，单用户的吞吐量下降速度快于轮询算法前者说明其吞吐量高，后者保证了它的公平性9/22/202224BUPT-QUALCOMM RESEARCH CENTER 公平性准则和累积分布函数 (一)公平性准则3GPP2为了衡量各算法的公平性，在鼓励提出新调度算法的同时，确定了一个公平性准则该准则是用相对于所有用户平均吞吐量归一化的用户吞吐量的累积分布函数表示式中的 是指用户k的实际吞吐量9/22/202226BUPT-QUALCOMM RESEARCH CENTER 公平性准则和累积分布

10、函数 (二)公平性准则该准则由下表的3个点表示归一化吞吐量累积分布函数9/22/202227BUPT-QUALCOMM RESEARCH CENTER 公平性准则和累积分布函数 (四)图 4 各种调度算法的累积分布函数曲线9/22/202229BUPT-QUALCOMM RESEARCH CENTER 公平性准则和累积分布函数 (五)公平性准则和累积分布函数的关系上页的累积分布函数曲线表明，轮询算法和正比公平算法都满足公平性要求，而最大C/I算法不满足从系统吞吐量角度来看，正比公平算法大于轮询算法，而最大C/I算法是各种算法中最大的 随着累积分布函数曲线的底

11、端向左，系统吞吐量越大，这是由于越往左，表示低吞吐量用户占的比例越大，也就是调度算法给信道条件差的用户给的传输机会越少 9/22/202230BUPT-QUALCOMM RESEARCH CENTER 公平性准则和累积分布函数 (六)公平性准则和累积分布函数的关系这也启发我们，在满足公平准则的前提下，累积分布函数曲线尽量向左靠近公平准则，这样的调度算法将是吞吐量和公平性折中最好的 从前面的图4可以看出，正比公平算法是做好吞吐量和公平性折中的一种尝试，但不是最优的尽管最优解得到很困难，但近似最优解是可以达到的9/22/202231BUPT-QUALCOMM RESEARCH CENTER 仿真环

12、境和数值结果（一）仿真环境每扇区20个FTP用户，业务模型为数据队列全满基站功率有20的开销信道模型是单径Rayleigh，120kmph其它参数见参考文献39/22/202232BUPT-QUALCOMM RESEARCH CENTER 仿真环境和数值结果（二）图5 各种调度算法的吞吐量9/22/202233BUPT-QUALCOMM RESEARCH CENTER 参考文献1 P. Bender et al., “CDMA/HDR: A Bandwidth-Efficient High-Speed Wireless Data Service for Nomadic Users”, IEEE

13、 Communications Magazine 38 7 Jul 2000, pp. 70-77.2 A.Jalali, R. Padovani, R. Pankaj, “Data Throughput of CDMA-HDR, a High Efficiency Data Rate Personal Communication Wireless System”, VTC2000, pp.1854-1858.3 Frank Zhou, 1xEV-DV Evaluation Methodology (Rev.26), WG5 Evaluation AHG, May 9, 20019/22/20

14、2234BUPT-QUALCOMM RESEARCH CENTER 反向链路9/22/202235BUPT-QUALCOMM RESEARCH CENTER 提纲调度算法的研究背景调度算法原理参考文献9/22/202236BUPT-QUALCOMM RESEARCH CENTER 调度算法的研究背景（一）前向和反向数据业务的特点前向和反向数据速率不对称，一般前向高于反向前向数据业务在分组数据业务信道（PDCH）传输，而反向则在SCH信道上传输SCH信道上的数据传输有两种，一是自发传送，针对低时延要求的低速数据业务，二是调度传送，针对时延要求不高的业务19/22/202237BUPT-QUALC

15、OMM RESEARCH CENTER 调度算法的研究背景（二）前向和反向数据业务的特点不同于前向数据业务的速率控制，反向采用功率控制反向在速率申请时，和前向也有所不同不同于前向数据业务的快速小区交换，反向仍采用软切换9/22/202238BUPT-QUALCOMM RESEARCH CENTER 调度算法的研究背景（三）反向调度算法的特点反向由于单用户申请的速率不高，所以可以同时选多个用户选择多少用户同时传输，依赖于基站端的ROT值9/22/202239BUPT-QUALCOMM RESEARCH CENTER 调度算法的研究背景（四）反向调度算法的意义使可达到的时分调度增益最大，同时最充分

16、地利用BS的noise-rise资源 限制同时传输的数据用户数，以降低移动台之间的干扰降低位于小区边缘用户的传输速率，以降低对邻小区的干扰9/22/202240BUPT-QUALCOMM RESEARCH CENTER 调度算法简介（一）调度算法的流程反向功率控制反向pilot由内环功控在一个所希望的门限上为使突发工作的R-SCH获得所需QoS（设置为5% FER)，各MS还应支持额外的1500bps的R-FCH，功率控制使该R-FCH的FER在1%，这是针对激活集中各BS而言的 为消除在某些信道模型下的高FER，将针对各种turbo码 速率的IS-2000.2-A规定的pilot参考电平提高

17、了0.25dB29/22/202241BUPT-QUALCOMM RESEARCH CENTER 调度算法简介（二）调度算法的流程速率申请各MS使用其R-FCH或R-DCCH提供队列大小信息以申请R-SCH上的数据速率 所申请的速率是基于数据队列长度及MS可用发射功率确定的，MS可用的发射功率的计算应考虑：最大可用发射功率、当前pilot发射功率、以及为功率控制偏差所留的余量（margin）9/22/202242BUPT-QUALCOMM RESEARCH CENTER 调度算法简介（三）调度算法的流程速率申请的计算设BS处接收到的RL导频C/I（即Ec/Io）的目标值为 ，则功率控制的目标是

18、令下式满足：其中， 表示当前RL导频信道发射功率，L为损耗，I为干扰功率9/22/202243BUPT-QUALCOMM RESEARCH CENTER 调度算法简介（四）调度算法的流程速率申请的计算然后，MS用下面的方法来确定要申请的R-SCH速率（对于高速传输）求出所能达到的最大R-SCH和导频功率之比根据这个T/P功率比，查它所能满足的数据速率，向BS申请39/22/202244BUPT-QUALCOMM RESEARCH CENTER 调度算法简介（五）调度算法的流程调度和速率分配 每个调度周期的开始，MS被分配一个基于其申请速率和队列信息的速率调度周期为一帧（20ms），MS在每一帧

19、都可调度为不同速率。这是对于20ms帧结构来说最快的调度周期9/22/202245BUPT-QUALCOMM RESEARCH CENTER 调度算法简介（六）调度算法的流程调度算法对MS所申请的速率进行优先级排队，然后使用greedy filling策略调度，在RL上传送数据的权利先给优先级最高的MS及其后面跟着的优先级略低的MS 只要ROT没有超过要求的门限，在优先级队列中排在靠前位置的所有MS将都被赋予传输其申请的速率的权利9/22/202246BUPT-QUALCOMM RESEARCH CENTER 调度算法简介（七）调度算法的流程调度算法这种集中式的调度考虑了MS对其激活集中各扇区的noise-rise的贡献 优先级函数则在充分保证链路质量和公平度之间做出了折中下页的优先权计算方法是正比公平策略的一种实现方式，而实际的系统中不同的厂商可能会用不同的实现方法9/22/202247BUPT-QUALCOMM RESEARCH CENTER 调度算法简介（八）优先权函数的计算其中，Rreq为MS所申请的速率Ralloc为过滤（平均）后的所分配给MS的速率 9/22/202248BUPT-QUALCOMM RESEARCH CENTER 调度算法简介（九）优先权函数的计算续上页SetPt表示归一化的功率控制设置点Prx(1)表示激活