《分组数据业务调度算法教学文案》由会员分享，可在线阅读，更多相关《分组数据业务调度算法教学文案（51页珍藏版）》请在金锄头文库上搜索。
1、2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,1,分组数据业务调度算法,王亚峰,2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,2,前向链路,2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,3,提纲,调度算法的研究背景调度算法原理最大C/I算循算法正比公平算法公平性与累积分布函数曲线参考文献,2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,4,调度算法的研究背景（一）,数据业务和话音业务的特点传输速率时延特性传输的正确性,2020/7/4,BUPT-QUALCOMMRESEARCHCENT
2、ER,6,调度算法的研究背景（三）,快速小区交换技术类似于硬切换技术，在每一时刻移动台只同信号最好的基站通信最佳扇区的指示由R-CQICH信道反馈由于没有软切换的宏分集增益，处于小区边缘的用户C/I很低,2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,7,调度算法的研究背景（四）,速率控制的基本思想每个时隙移动台测量其C/I，经量化后通过R-CQICH信道反馈至基站基站根据反馈的C/I、可供分配的Walsh码、待传输数据队列的长度确定最大可支持的数据速率然后从所有请求传输的用户中，按照一定的调度算法选出其中的一个用户，给予传输机会,2020/7/4,BUPT-QUAL
3、COMMRESEARCHCENTER,8,调度算法的研究背景（五）,调度算法的意义调度算法是分组数据业务系统的一个特色，目的是充分利用信道的时变特性，得到多用户分集增益在调度算法的研究中，需要考虑系统吞吐量和单用户公平性的折中问题选取不同的调度算法，对系统性能影响很大,2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,9,调度算法原理（一）,最大C/I算法基站总是选择信道条件最好的用户，给予传输机会如果只在信道条件好的时候传输，可以提高传输速率、降低编码的冗余通过实时的改变传输方案来适应时变的信道环境，可以提高吞吐量,2020/7/4,BUPT-QUALCOMMRESE
4、ARCHCENTER,10,调度算法原理（二）,最大C/I算法由于具有多用户分集增益，这种调度算法是所有可能的算法中系统吞吐量最大的但这种算法存在的最大问题是公平性差，接近基站的移动台吞吐量很大，而小区边缘的用户得不到服务机会，存在“饿死”现象。因此，这种算法被认为是最不公平的,2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,11,调度算法原理（三）,轮询算法基站不考虑用户的信道状况，随机选取用户传输由于没有多用户分集增益，系统吞吐量低每个用户享有系统资源的机会相同，因此在一定意义上它被认为是最公平的,2020/7/4,BUPT-QUALCOMMRESEARCHCEN
5、TER,12,调度算法原理（四）,轮询算法但在固定网方面的研究中提出，在讨论公平性问题时，不能只考虑分配资源的方式，还要考虑利用资源的效用，同样的资源给不同的用户获得的效用是不一样的选择不同的用户，由于请求的传输速率不同，因此传输分组占有的时隙数是不同的，即传输速率不同正是由于对资源利用的效用不同，轮询算法也不是绝对公平的,2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,13,调度算法原理（五）,正比公平算法为了做好吞吐量和公平性的折中，Qualcomm在HDR（HighDataRate,即1xEVDO)中提出了一种称为正比公平的调度算法在每个时刻t，每个用户k计算一
6、个优先权函数一个扇区的所有用户中，优先权最大的将获得传输机会,2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,14,调度算法原理（六）,正比公平算法在时刻t，用户k的优先权函数计算如下式中DRC(t)是可以支持的最大传输速率，由R-CQICH反馈的C/I计算得到是正比公平吞吐量,2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,15,调度算法原理（七）,正比公平算法是公平指数是自举因子根据和的取值不同，这种调度算法又可分为两种算法1（针对提供实时视频业务的系统）1,2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,16,
7、调度算法原理（八）,正比公平算法算法2（针对不提供实时视频业务的系统）5算法1和算法2的区别算法2提高了公平性算法1保证了实时视频业务的时延要求,2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,17,调度算法原理（九）,正比公平算法在计算时，是以时隙为单位的，如下式如果在上一时隙用户k没有被调度上如果在上一时隙用户k被调度上的值为如果用户队列满时的分组大小,2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,18,调度算法原理（十）,正比公平算法为时间常数，表示滑动时间窗口的长度，实际上反映了一个用户对接收不到数据传输的忍受能力较长的时间常数将允
8、许等待较长的时间直到该用户的信道质量变好，这有利于系统吞吐量的提高，但可能带来附加的延迟在HDR中取值为，相当于时间常数为1.5s,2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,19,调度算法原理（十一）,正比公平算法对调度算法进行简化，可以得到下式由此可以看出，正比公平算法的实质是两个因素共同起作用，相互制约以达到吞吐量和公平性的折中,2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,20,调度算法原理（十二）,用户吞吐量和距离的散点图由于最大C/I算法总是选择信道最好的用户，所以离基站近的用户吞吐量很高处于小区半径中间的用户，由于快衰和慢
9、衰的影响，在一些时候C/I可以最高，因此也能被调度上，但下降趋势很快离基站远的用户，由于C/I为最大的概率很小，因此吞吐量接近于0,2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,21,调度算法原理（十三）,图1用户数据吞吐量和其到最佳服务扇区距离的散点图(最大C/I调度算法）,2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,22,调度算法原理（十四）,用户吞吐量和距离的散点图由于轮询算法不考虑用户的信道状况，所以离基站近的用户其吞吐量也不是很高随着距离增加，单用户的吞吐量缓慢下降但相对而言，边缘用户的吞吐量还是比较低，这不是因为公平问题，而
10、是前面提到的效用问题，离基站远的用户，他请求传输的速率本身就不高,2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,23,调度算法原理（十五）,图2用户数据吞吐量和其到最佳服务扇区距离的散点图(轮询调度算法）,2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,24,调度算法原理（十六）,用户吞吐量和距离的散点图正比公平算法介于前二者之间，最高吞吐量虽远低于最大C/I算法，但高于轮询算法随着距离增加，单用户的吞吐量下降速度快于轮询算法前者说明其吞吐量高，后者保证了它的公平性,2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,
11、25,调度算法原理（十七）,图3用户数据吞吐量和其到最佳服务扇区距离的散点图(正比公平调度算法）,2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,26,公平性准则和累积分布函数(一),公平性准则3GPP2为了衡量各算法的公平性，在鼓励提出新调度算法的同时，确定了一个公平性准则该准则是用相对于所有用户平均吞吐量归一化的用户吞吐量的累积分布函数表示式中的是指用户k的实际吞吐量,2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,27,公平性准则和累积分布函数(二),公平性准则该准则由下表的3个点表示,2020/7/4,BUPT-QUALCOMMRES
12、EARCHCENTER,28,公平性准则和累积分布函数(三),公平性准则上表实质上是限制了低吞吐量用户占总用户数的比例，比如低于0.1倍平均吞吐量的用户数不能超过总用户数的10%按照该准则，所有满足公平性要求的调度算法，其CDF曲线一定在这三点连成的直线的右侧，否则就是违反了公平性准则,2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,29,公平性准则和累积分布函数(四),图4各种调度算法的累积分布函数曲线,2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,30,公平性准则和累积分布函数(五),公平性准则和累积分布函数的关系上页的累积分布函数曲线
13、表明，轮询算法和正比公平算法都满足公平性要求，而最大C/I算法不满足从系统吞吐量角度来看，正比公平算法大于轮询算法，而最大C/I算法是各种算法中最大的随着累积分布函数曲线的底端向左，系统吞吐量越大，这是由于越往左，表示低吞吐量用户占的比例越大，也就是调度算法给信道条件差的用户给的传输机会越少,2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,31,公平性准则和累积分布函数(六),公平性准则和累积分布函数的关系这也启发我们，在满足公平准则的前提下，累积分布函数曲线尽量向左靠近公平准则，这样的调度算法将是吞吐量和公平性折中最好的从前面的图4可以看出，正比公平算法是做好吞吐量
14、和公平性折中的一种尝试，但不是最优的尽管最优解得到很困难，但近似最优解是可以达到的,2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,32,仿真环境和数值结果（一）,仿真环境每扇区20个FTP用户，业务模型为数据队列全满基站功率有20的开销信道模型是单径Rayleigh，120kmph其它参数见参考文献3,2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,33,仿真环境和数值结果（二）,图5各种调度算法的吞吐量,2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,34,参考文献,1P.Benderetal.,“CDMA/HD
15、R:ABandwidth-EfficientHigh-SpeedWirelessDataServiceforNomadicUsers”,IEEECommunicationsMagazine387Jul2000,pp.70-77.2A.Jalali,R.Padovani,R.Pankaj,“DataThroughputofCDMA-HDR,aHighEfficiencyDataRatePersonalCommunicationWirelessSystem”,VTC2000,pp.1854-1858.3FrankZhou,1xEV-DVEvaluationMethodology(Rev.26),W
16、G5EvaluationAHG,May9,2001,2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,35,反向链路,2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,36,提纲,调度算法的研究背景调度算法原理参考文献,2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,37,调度算法的研究背景（一）,前向和反向数据业务的特点前向和反向数据速率不对称，一般前向高于反向前向数据业务在分组数据业务信道（PDCH）传输，而反向则在SCH信道上传输SCH信道上的数据传输有两种，一是自发传送，针对低时延要求的低速数据业务，二是调度传送，针对时延要求不高的业务1,2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,38,调度算法的研究背景（二）,前向和反向数据业务的特点不同于前向数据业务的速率控制，反向采用功率控制反向在速率申请时，和前向也有所不同不同于前向数据业务的快速小区交换，反向仍采用软切换,2020/7/4,BUPT-QUALCOMMRESEARCHCENTER,39,调度算法的研究背景（三
