分组数据业务调度算法.ppt
《分组数据业务调度算法.ppt》由会员分享,可在线阅读,更多相关《分组数据业务调度算法.ppt(51页珍藏版)》请在三一文库上搜索。
1、,分组数据业务调度算法,王亚峰 ,前向链路,2019/4/10,BUPT-QUALCOMM RESEARCH CENTER,3,提纲,调度算法的研究背景 调度算法原理 最大C/I算法 轮循算法 正比公平算法 公平性与累积分布函数曲线 参考文献,2019/4/10,BUPT-QUALCOMM RESEARCH CENTER,4,调度算法的研究背景(一),数据业务和话音业务的特点 传输速率 时延特性 传输的正确性,2019/4/10,BUPT-QUALCOMM RESEARCH CENTER,5,调度算法的研究背景(二),数据业务系统的特点 由于数据业务消耗的资源较大,不适合采用软切换,采用了快速
2、小区交换技术 为了保证传输的正确性,要采用差错控制重传机制 取代了功率控制技术,这里采用速率控制,2019/4/10,BUPT-QUALCOMM RESEARCH CENTER,6,调度算法的研究背景(三),快速小区交换技术 类似于硬切换技术,在每一时刻移动台只同信号最好的基站通信 最佳扇区的指示由R-CQICH信道反馈 由于没有软切换的宏分集增益,处于小区边缘的用户C/I很低,2019/4/10,BUPT-QUALCOMM RESEARCH CENTER,7,调度算法的研究背景(四),速率控制的基本思想 每个时隙移动台测量其C/I,经量化后通过R-CQICH信道反馈至基站 基站根据反馈的C/
3、I、可供分配的Walsh码、待传输数据队列的长度确定最大可支持的数据速率 然后从所有请求传输的用户中,按照一定的调度算法选出其中的一个用户,给予传输机会,2019/4/10,BUPT-QUALCOMM RESEARCH CENTER,8,调度算法的研究背景(五),调度算法的意义 调度算法是分组数据业务系统的一个特色,目的是充分利用信道的时变特性,得到多用户分集增益 在调度算法的研究中,需要考虑系统吞吐量和单用户公平性的折中问题 选取不同的调度算法,对系统性能影响很大,2019/4/10,BUPT-QUALCOMM RESEARCH CENTER,9,调度算法原理(一),最大C/I算法 基站总是
4、选择信道条件最好的用户,给予传输机会 如果只在信道条件好的时候传输,可以提高传输速率、降低编码的冗余 通过实时的改变传输方案来适应时变的信道环境,可以提高吞吐量,2019/4/10,BUPT-QUALCOMM RESEARCH CENTER,10,调度算法原理(二),最大C/I算法 由于具有多用户分集增益,这种调度算法是所有可能的算法中系统吞吐量最大的 但这种算法存在的最大问题是公平性差,接近基站的移动台吞吐量很大,而小区边缘的用户得不到服务机会,存在“饿死”现象。因此,这种算法被认为是最不公平的,2019/4/10,BUPT-QUALCOMM RESEARCH CENTER,11,调度算法原
5、理(三),轮询算法 基站不考虑用户的信道状况,随机选取用户传输 由于没有多用户分集增益,系统吞吐量低 每个用户享有系统资源的机会相同,因此在一定意义上它被认为是最公平的,2019/4/10,BUPT-QUALCOMM RESEARCH CENTER,12,调度算法原理(四),轮询算法 但在固定网方面的研究中提出,在讨论公平性问题时,不能只考虑分配资源的方式,还要考虑利用资源的效用,同样的资源给不同的用户获得的效用是不一样的 选择不同的用户,由于请求的传输速率不同,因此传输分组占有的时隙数是不同的,即传输速率不同 正是由于对资源利用的效用不同,轮询算法也不是绝对公平的,2019/4/10,BUP
6、T-QUALCOMM RESEARCH CENTER,13,调度算法原理(五),正比公平算法 为了做好吞吐量和公平性的折中,Qualcomm在HDR(High Data Rate,即1x EV DO)中提出了一种称为正比公平的调度算法 在每个时刻t,每个用户k计算一个优先权函数 一个扇区的所有用户中,优先权最大的将获得传输机会,2019/4/10,BUPT-QUALCOMM RESEARCH CENTER,14,调度算法原理(六),正比公平算法 在时刻t,用户k的优先权函数计算如下 式中 DRC(t) 是可以支持的最大传输速率,由R-CQICH反馈的 C/I计算得到 是正比公平吞吐量,2019
7、/4/10,BUPT-QUALCOMM RESEARCH CENTER,15,调度算法原理(七),正比公平算法 是公平指数 是自举因子 根据和 的取值不同,这种调度算法又可分为两种 算法1(针对提供实时视频业务的系统) 1,2019/4/10,BUPT-QUALCOMM RESEARCH CENTER,16,调度算法原理(八),正比公平算法 算法2(针对不提供实时视频业务的系统) 5 算法1和算法2的区别 算法2提高了公平性 算法1保证了实时视频业务的时延要求,2019/4/10,BUPT-QUALCOMM RESEARCH CENTER,17,调度算法原理(九),正比公平算法 在计算 时,是
8、以时隙为单位的,如下式 如果在上一时隙用户k 没有被调度上 如果在上一时隙用户k被调度上 的值为如果用户队列满时的分组大小,2019/4/10,BUPT-QUALCOMM RESEARCH CENTER,18,调度算法原理(十),正比公平算法 为时间常数,表示滑动时间窗口的长度,实际上反映了一个用户对接收不到数据传输的忍受能力 较长的时间常数将允许等待较长的时间直到该用户的信道质量变好,这有利于系统吞吐量的提高,但可能带来附加的延迟 在HDR中取值为 ,相当于时间常数为1.5s,2019/4/10,BUPT-QUALCOMM RESEARCH CENTER,19,调度算法原理(十一),正比公平
9、算法 对调度算法进行简化,可以得到下式 由此可以看出,正比公平算法的实质是两个因素共同起作用,相互制约以达到吞吐量和公平性的折中,2019/4/10,BUPT-QUALCOMM RESEARCH CENTER,20,调度算法原理(十二),用户吞吐量和距离的散点图 由于最大C/I算法总是选择信道最好的用户,所以离基站近的用户吞吐量很高 处于小区半径中间的用户,由于快衰和慢衰的影响,在一些时候C/I可以最高,因此也能被调度上,但下降趋势很快 离基站远的用户,由于C/I为最大的概率很小,因此吞吐量接近于0,2019/4/10,BUPT-QUALCOMM RESEARCH CENTER,21,调度算法
10、原理(十三),图1 用户数据吞吐量和其到最佳服务扇区距离的散点图(最大C/I调度算法),2019/4/10,BUPT-QUALCOMM RESEARCH CENTER,22,调度算法原理(十四),用户吞吐量和距离的散点图 由于轮询算法不考虑用户的信道状况,所以离基站近的用户其吞吐量也不是很高 随着距离增加,单用户的吞吐量缓慢下降 但相对而言,边缘用户的吞吐量还是比较低,这不是因为公平问题,而是前面提到的效用问题,离基站远的用户,他请求传输的速率本身就不高,2019/4/10,BUPT-QUALCOMM RESEARCH CENTER,23,调度算法原理(十五),图 2 用户数据吞吐量和其到最佳
11、服务扇区距离的散点图(轮询调度算法),2019/4/10,BUPT-QUALCOMM RESEARCH CENTER,24,调度算法原理(十六),用户吞吐量和距离的散点图 正比公平算法介于前二者之间,最高吞吐量虽远低于最大C/I算法,但高于轮询算法 随着距离增加,单用户的吞吐量下降速度快于轮询算法 前者说明其吞吐量高,后者保证了它的公平性,2019/4/10,BUPT-QUALCOMM RESEARCH CENTER,25,调度算法原理(十七),图3 用户数据吞吐量和其到最佳服务扇区距离的散点图(正比公平调度算法),2019/4/10,BUPT-QUALCOMM RESEARCH CENTER
12、,26,公平性准则和累积分布函数 (一),公平性准则 3GPP2为了衡量各算法的公平性,在鼓励提出新调度算法的同时,确定了一个公平性准则 该准则是用相对于所有用户平均吞吐量归一化的用户吞吐量的累积分布函数表示 式中的 是指用户k的实际吞吐量,2019/4/10,BUPT-QUALCOMM RESEARCH CENTER,27,公平性准则和累积分布函数 (二),公平性准则 该准则由下表的3个点表示,2019/4/10,BUPT-QUALCOMM RESEARCH CENTER,28,公平性准则和累积分布函数 (三),公平性准则 上表实质上是限制了低吞吐量用户占总用户数的比例,比如低于0.1倍平均
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 分组 数据业务 调度 算法
链接地址:https://www.31doc.com/p-2572421.html