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

调度算法原理（五） 正比公平算法 为了做好吞吐量和公平性的折中，Qualcomm在HDR（High Data Rate,即1x EV DO)中提出了一种称为正比公平的调度算法 在每个时刻t，每个用户k计算一个优先权函数 一个扇区的所有用户中，优先权最大的将获得传输机会 调度算法原理（六） 正比公平算法 在时刻t，用户k的优先权函数计算如下 式中 DRC(t) 是可以支持的最大传输速率，由R-CQICH反馈的 C/I计算得到 是正比公平吞吐量 调度算法原理（七） 正比公平算法 ?是公平指数 是自举因子 根据?和 的取值不同，这种调度算法又可分为两种 算法1（针对提供实时视频业务的系统） ?＝1 调度算法原理（八） 正比公平算法 算法2（针对不提供实时视频业务的系统） ?＝5 算法1和算法2的区别 算法2提高了公平性 算法1保证了实时视频业务的时延要求 调度算法原理（九） 正比公平算法 在计算 时，是以时隙为单位的，如下式 如果在上一时隙用户k 没有被调度上 如果在上一时隙用户k被调度上 的值为如果用户队列满时的分组大小 调度算法原理（十） 正比公平算法 为时间常数，表示滑动时间窗口的长度，实际上反映了一个用户对接收不到数据传输的忍受能力 较长的时间常数将允许等待较长的时间直到该用户的信道质量变好，这有利于系统吞吐量的提高，但可能带来附加的延迟 在HDR中取值为 ，相当于时间常数为1.5s 调度算法原理（十一） 正比公平算法 对调度算法进行简化，可以得到下式 由此可以看出，正比公平算法的实质是两个因素共同起作用，相互制约以达到吞吐量和公平性的折中 调度算法原理（十二） 用户吞吐量和距离的散点图 由于最大C/I算法总是选择信道最好的用户，所以离基站近的用户吞吐量很高 处于小区半径中间的用户，由于快衰和慢衰的影响，在一些时候C/I可以最高，因此也能被调度上，但下降趋势很快 离基站远的用户，由于C/I为最大的概率很小，因此吞吐量接近于0 调度算法原理（十三） 图1 用户数据吞吐量和其到最佳服务扇区距离的散点图(最大C/I调度算法） 调度算法原理（十四） 用户吞吐量和距离的散点图 由于轮询算法不考虑用户的信道状况，所以离基站近的用户其吞吐量也不是很高 随着距离增加，单用户的吞吐量缓慢下降 但相对而言，边缘用户的吞吐量还是比较低，这不是因为公平问题，而是前面提到的效用问题，离基站远的用户，他请求传输的速率本身就不高 调度算法原理（十五） 图 2 用户数据吞吐量和其到最佳服务扇区距离的散点图(轮询调度算法） 调度算法原理（十六） 用户吞吐量和距离的散点图 正比公平算法介于前二者之间，最高吞吐量虽远低于最大C/I算法，但高于轮询算法 随着距离增加，单用户的吞吐量下降速度快于轮询算法 前者说明其吞吐量高，后者保证了它的公平性 调度算法原理（十七） 图3 用户数据吞吐量和其到最佳服务扇区距离的散点图(正比公平调度算法） 公平性准则和累积分布函数 (一) 公平性准则 3GPP2为了衡量各算法的公平性，在鼓励提出新调度算法的同时，确定了一个公平性准则 该准则是用相对于所有用户平均吞吐量归一化的用户吞吐量的累积分布函数表示 式中的 是指用户k的实际吞吐量 公平性准则和累积分布函数 (二) 公平性准则 该准则由下表的3个点表示 归一化吞吐量 0.1 0.2 0.5 累积分布函数 0.1 0.2 0.5 公平性准则和累积分布函数 (三) 公平性准则 上表实质上是限制了低吞吐量用户占总用户数的比例，比如低于0.1倍平均吞吐量的用户数不能超过总用户数的10% 按照该准则，所有满足公平性要求的调度算法，其CDF曲线一定在这三点连成的直线的右侧，否则就是违反了公平性准则 公平性准则和累积分布函数 (四) 图 4 各种调度算法的累积分布函数曲线 公平性准则和累积分布函数 (五) 公平性准则和累积分布函数的关系 上页的累积分布函数曲线表明，轮询算法和正比公平算法都满足公平性要求，而最大C/I算法不满足 从系统吞吐量角度来看，正比公平算法大于轮询算法，而最大C/I算法是各种算法中最大的 随着累积分布函数曲线的底端向左，系统吞吐量越大，这是由于越往左，表示低吞吐量用户占的比例越大，也就是调度算法给信道条件差的用户给的传输机会越少 公平性准则和累积分布函数 (六) 公平性准则和累积分布函数的关系 这也启发我们，在满足公平准则的前提下，累积分布函数曲线尽量向左靠近公