分组调度算法（通用8篇）
分组调度算法 篇1
HSDPA系统通过采用自适应编码调制 (AMC) 、混合自动重传请求 (HARQ) 和快速分组调度等一系列技术手段, 使其理论峰值速率高达14.4 Mbps, 后续阶段甚至可达50 Mbp以上。在HSDPA的这些关键技术中, 分组调度的对象是小区内所有映射到HS-DSCH传输信道的用户, 主要解决系统资源与用户之间的平衡问题。可以说, 如果没有一种合理有效的调度算法, 速率再高的网络也难以获得理想的实用价值。衡量调度算法优劣的指标主要为:空口吞吐量、用户公平性、平均时延及实现的复杂度。本文主要针对适用于HSDPA系统的几种典型调度算法进行简要分析, 并对其性能作出客观评价。
一、轮询 (Round Robin) 算法
轮询算法的基本思想是让所有被服务用户按照某种确定的顺序, 循环均等地使用系统无线资源。轮询算法所遵循的规则如下:
(a) 每个用户对应一个缓存队列, 用以存放待传输的数据。
(b) 在进行调度时, 各非空队列以循环方式接受服务以传送数据。
(c) 一个接受过服务的队列, 只有其他非空队列都被服务过一遍后, 才能再次获得服务。
(d) 一个队列不能连续接受服务, 除非只有一个非空队列。
轮询算法能够保证各用户等时间占用系统无线资源, 在公平性方面表现相当出色, 其算法复杂度也很低, 易于实现, 在实际中应用范围较为广泛。
但是, 由于没有考虑到不同用户的信道特性及业务特性, 所以系统的吞吐量很低, 获得的用户感受也不理想。为了克服这些缺点, 近些年又出现了多种改进算法, 如加权公平队列、差额轮询、紧急轮询算法等。这些算法从不同角度对轮询算法进行改进, 并尽量保持其简单易实现的优点。
二、最大载干比 (Maximum C/I) 算法
最大载干比算法总是选择信道条件好的用户优先进行服务, 也即高C/I值的用户总比低C/I值的用户具有更高的优先级。用户优先级的选择可以用式 (1) 表示:
其中, ri (t) 为用户i在t时刻所支持的数据传输速率。
最大载干比算法选择的都是C/I值高的用户, 这样就可大幅提高编码效率, 调制时还可使用更高阶的调制, 从而可以最大化系统的吞吐量。最大载干比算法的复杂度也很低, 易于设计和实现。然而, 最大载干比算法又是一种极不公平的算法, 比如离基站近的用户通常具有好的信道条件, 而离基站远的用户的信道条件相对较差, 这样, 离基站近的用户就会持续得到服务, 而远端用户几乎得不到服务, 造成所谓的“饿死现象”。所以, 最大载干比算法的实际应用价值并不高。
三、正比公平 (Proportional Fair) 算法
正比公平算法既不像轮询算法那样, 对所有用户一视同仁, 只考虑用户的公平性, 也不像最大载干比算法那样, 只选择信道条件好的用户, 一味追求吞吐量的最大化, 而是综合考虑系统吞吐量和用户公平性, 对两者进行折中。其用户优先级计算公式如式 (2) 所示:
其中, Rk (t) 表示在t时刻第k个用户所请求的数据速率, Tk (t) 表示第k个用户在以t为结束时刻的时间窗口内的平均吞吐量。从式中可以看出, 信道条件好的用户在开始阶段数据速率Rk (t) 的值较大, 所以具有较高的优先级。但随着时间t的推移, 其分母Tk (t) 的值也会快速增大, 导致一段时间后该用户的优先级降到很低。当优先级很低时, 分母Tk (t) 又会快速减小, 其优先级Prik会逐渐增大。相应的, 信道条件差的用户优先级也会沿着相反的趋势动态变化。通过优先级的动态调整, 避免了某一用户持续占用系统资源的情况, 同时也兼顾了系统吞吐量。
四、自适应正比公平 (APF) 算法
正比公平算法在经历相似信道条件的用户之间, 能够表现出很好的公平性。而实际中各用户信道的衰落特性往往是不同的, 此时正比公平算法就难以合理地进行调度。只有及时捕捉到不同用户信道的快速变化, 并能以此为参考界定用户优先级, 才能实现真正公平合理的调度。自适应正比公平算法就是为解决这一问题而诞生的, 其用户优先级定义为:
其中, Ri (t) 为用户i在t时刻的瞬时速率, λi为该用户的平均数据速率, Ci是用户的控制参数, 用以跟踪其信道的快速变化。实践表明, 自适应正比公平算法在公平性方面比正比公平算法有所提高, 但这种公平性的提高是以牺牲吞吐量为代价的。而且, 由于在正比公平算法的基础上新增了用户监控模块, 使其算法复杂度也相应增加了。
总之本文对适用于HSDPA系统非实时业务的几种典型调度算法进行了简要分析, 通过分析可得出如下结论:轮询算法的公平性最好, 但系统吞吐量很低;最大载干比算法的吞吐量最高, 但公平性最差;正比公平算法综合了以上两种算法的优点, 在公平性和吞吐量之间进行了折中;自适应正比公平算法在公平性方面对正比公平算法进行了改进, 但公平性的提高须以牺牲一定的吞吐量为代价。
一种改进的无线分组快速调度算法 篇2
常用调度算法性能分析
吞吐量和公平性永远是在无线资源分组调度算法的研究中不可回避的两个重要因素。如何平衡这两个重要因素就是分组调度算法要解决的核心问题。当多个业务分组请求服务时, 必须综合考虑各种因素, 确定合理的优先级次序, 安排用户的服务顺序和服务时间, 以满足各种无线应用的优质性能。下面分析一下三种常用的分组调度算法:PF算法、APF算法和M-LWDF算法。
1 PF算法
PF算法就是正比公平算法, 该算法的基本思想是在长时间的通信过程中, 维护各用户之间吞吐量的基本公平, 同时又考虑到每个用户自身通信环境的变化情况, 以此来确定每个用户的优先级。
该算法的用户优先级定义如下:
式中 (C/I) i (t) 指用户i在t时刻的载干比, 而λi (t) 指该用户i的平均吞吐量。当用户i连续通信时, 其λi (t) 必然不断增大, 从而使该用户的优先级变小, 将信道让给其他用户。该算法是一种公平调度算法, 但其主要缺陷是对实时通信业务的适应能力较弱[3,4]。
2 APF算法
APF算法就是自适应比例公平算法, 该算法的基本思想是:为了弥补PF算法在用户信道快速变化时, 造成的公平性缺失, 在原有PF算法基础上, 增加了更新控制模块。该模块随时追踪用户信道变化情况, 不断更新相应控制参数。
该算法的用户优先级定义如下:
式中, Ri (t) 是用户i在t时刻的瞬时速率, 而λi (t) 是该用户的平均吞吐量, Ci是用户i的控制参数。该算法由于增加了一个控制模块, 虽然弥补了PF算法在公平性的上的不足, 但控制参数的更新需要较长的周期, 这就使得系统的整体吞吐量有所降低[4]。
3 M-LWDF算法:
与上述两种算法不同, M-LWDF算法是针对需要高速率支持的无线实时业务而提出的[3,4]。该该算法的基本思想是将分组数据包的时延和如何有效利用信道信息平衡考虑, 其用户优先级的计算不仅和用户当前的信道质量有关, 还和包的队列时延有关。
该算法的用户优先级定义公式如下:
式中δ是用户i的Qo S参数, Ri (n) 是用户i在第n个TTI内的最大数据速率, 而λi是该用户i的平均吞吐量, Di (n) 是用户i所在分组的队列延时, Ti是用户i能容忍的最大时延。该算法在用户吞吐量和用户等待时延之间做了有效的折衷, 即对信道条件好的用户尽可能的提高信道利用率, 又考虑到信道条件差的用户的等待时延, 随着等待时间的加长, 其调度优先级也随之增加。但是对于某些信道条件较差的用户, 其等待时延可能超过用户的最大容忍时间而被丢弃。
改进的调度算法
为了降低被抛弃的概率, 提高用户间公平性, 需要快速提高等待时间较长的数据分组的优先级, 使得信道条件较差的用户拥有被调度的机会。这时上面公式修正为:
式中, 我们将Tmin称之为快速调度时限, 将eMi称之为快速调度因子。快速调度因子的变化规律为, 随着等待时间Di (n) 的不断加长而先快后慢的变化。当用户i所在包的队列延时Di (n) ﹤Tmin时, 取对应的Mi=0, 则e Mi的值将等于1, 那么这时用户i的调度有限级将退化为, 在 (0, Tmin) 时间段内, 通信条件好的用户将得到更多的信道资源, 在一定程度上, 保证了系统原有的吞吐量。当用户i所在包的队列延时Di (n) ≧Tmin时, 则对应的, 当用户i所在包的队列延时Di (n逐渐接近用户i所能容忍的最大时延Ti时, 其对应的的值也就趋向于∞, 那么快速调度因子eMi的数值迅速增大, 使得用户i在第n个TTI的优先级也随之迅速增大, 从而迅速获得信道资源, 避免了信道条件较差的用户长期得不到调度的情况, 保证了系统中拥有良好的公平性。从长时间的通信来看, 信道质量好的用户占用信道的总时间会较长, 在很大程度上保证了整个系统的吞吐量, 信道质量差的用户占用信道的总时间会较短。由于该改进算法照顾到信道条件差的用户占用信道的机会, 必然会在一定程度上降低信道条件好的用户对信道资源的利用率。
4 结论
无线信道的时变特性是HSDPA系统的一个重要特性, 只有充分的考虑到系统的时变特性, 充分利用信道的时变信息, 在保证系统吞吐量的同时, 顾及到用户公平性, 才能获得了理想的整体性能。文中先对几种经典算法的性能进行了分析, 并结合HSDPA系统的特性, 对M-LWDF算法做了改进, 引入了快速调度因子, 在保证系统吞吐量的条件下, 迅速分配信道给信道条件差的用户, 防止这些用户在系统中被丢弃务, 从而提高了系统的公平性。
总之, 随着无线应用日益增多, 如何利用最有效的分组调度算法, 实现HDSPA的高性能, 仍有待于进一步研究。
参考文献
[1]孙华, 甄颖.一种增强WCDMA网络性能的技术:HSDPA[J].电信快报, 2004, 3.
[2]ANDREWS M, KUMARAN K.CDMA DATA QoS Scheduling on the Forward Link with Variable Channel Conditions[R].Bell Labs Tech-nical Memo No.10009626000404-05TM, 2000:1-45
[3]SHAKKOTTAI S, STOLYAR A L.Scheduling Algorithms for a Mixture of Real-time and Non-real-time Data in HDR[R].Proc.of17th International Teletraffic Confgress, (ITC-17) , 2001:173-804.
短作业优先调度算法 篇3
姓名：陈凯
学号：541413430202
地点：四教楼301
指导老师：张旭
专业班级：嵌入式软件14-02
实验名称：短作业优先调度算法
一、实验目的：
测试数据可以随即输入或从文件中读入。必须要考虑到作业的到达时间
最终能够计算每一个作业的周转时间。
二、实验内容：
模拟实现短作业调度算法，具体如下：
设置作业体：作业名，作业的到达时间，服务时间，作业间的链接指针 进程初始化：由用户输入作业名、作业的到达时间和服务时间进行初始化。显示函数：
1、显示当前调度的是哪个作业，后备队列中有哪些作业
2、最终显示每个作业的作业名、到达时间、服务时间、完成时间和周转时间
排序函数：对就已到达的作业按照服务时间进行排序。注意考虑到达时间 调度函数：每次从已到达的作业队列队首调度优一个作业执行。删除函数：作业结束后撤销。
三、实验代码
#include
char name[10];//进程名
floatarrivetime;//到达时间
floatservicetime;//服务时间
floatstarttime;
//开始时间
floatfinishtime;//完成时间 floatzztime;//周转时间 floatdqzztime;
//带权周转时间 };
sjf b[100];
//定义短作业优先算法进程的最大数量 voidSinput(sjf *p,int N)
//输入函数 { int i;
printf(“输入进程的名称、到达时间、服务时间:n”);for(i=0;i<=N-1;i++){
printf(“输入第%d进程的名称、到达时间、服务时间:”,i+1);scanf(“%s%f%f”,&p[i].name,&p[i].arrivetime,&p[i].servicetime);} }
//输出函数 voidSPrint(sjf *p,floatarrivetime,floatservicetime,floatstarttime,floatfinishtime,floatzztime,floatdqzztime,int N){ int k;
printf(“n执行顺序:n”);printf(“%s”,p[0].name);
for(k=1;k { printf(“-%s”,p[k].name);} printf(“n进程名tarrivetservicetstarttfinishtzztdqzzn”); for(k=0;k<=N-1;k++) { printf(“%st%-.2ft%-.2ft%-.2ft%-.2ft%-.2ft%-.2ftnn”,p[k].name,p[k].arrivetime,p[k].servicetime,p[k].starttime,p[k].finishtime,p[k].zztime,p[k].dqzztime); } } voidSsort(sjf *p,int N) //按短作业优先算法排序 { for(int i=1;i<=N-1;i++)for(int j=1;j<=i;j++) if(p[i].servicetime sjf temp;temp=p[i]; p[i]=p[j]; p[j]=temp;} } //运行结果 voidSdeal(sjf *p, float arrivetime,floatservicetime,floatstarttime,floatfinishtime,float&zztime,float&dqzztime,int N){ int k; for(k=0;k<=N-1;k++) { if(k==0){ p[k].starttime=p[k].arrivetime; p[k].finishtime=p[k].arrivetime+p[k].servicetime; } else { p[k].starttime=p[k-1].finishtime;//开始时间=前一个进程的完成时间 p[k].finishtime=p[k-1].finishtime+p[k].servicetime; //结束时间=前一个进程的完成时间+现在进程的服务时间 } } for(k=0;k<=N-1;k++){ p[k].zztime=p[k].finishtime-p[k].arrivetime; //周转时间=完成时间-到达时间 p[k].dqzztime=p[k].zztime/p[k].servicetime; //带权周转时间=周转时间/服务时间 } } void SJF(sjf *p,int N){ float arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0; Ssort(p,N); Sdeal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N); SPrint(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);} void main()//主函数 { int M;printf(“------------短作业优先调度算法-----------n”);printf(“输入作业数:”);scanf(“%d”,&M); Sinput(b,M);SJF(b,M);} 四、实验结果 五、实验总结 为适应移动通信技术的快速发展, 第三代合作伙伴计划 (3GPP) 启动了长期演进 (Long Term Evolution, LTE) 系统方案[1]。LTE系统采用正交频分多址 (Orthogonal Frequency Division Multiple Access, OFDMA) 技术[2]和多入多出 (Multiple Input Multiple Output, MIMO) 技术[3], 可以在时域、频域和码域上灵活地进行无线资源管理[4]。无线资源管理是LTE的关键技术之一, 它的主要功能是通过分组调度算法来确保用户的QoS和用户间的公平性并最大化系统的吞吐量。PF算法是最大载干比调度 (Max C/I) 和轮询调度 (RR) 的折中, 它兼顾了用户的公平性和系统的吞吐量, 但并没有考虑到QoS的速率需求[5]。文献[6]提出的USGF算法考虑了QoS的速率需求, 提高了整个系统的用户满意程度, 但当调度过程中所有用户都能满足QoS速率需求且有无线资源富余时, 并没有最大化系统的吞吐量。 为此, 这里结合PF算法和USGF算法, 引入用户满意度反馈提出一种判决因素可变的调度算法 (Factor Chang i ng Sc h ed u l i ng A lgo r i t h m, FCS) , 并在系统吞吐量、用户平均满意度和不同QoS速率需求业务之间的公平性等方面进行仿真和结果分析。 系统模型 考虑一个多小区的TDD LTE系统, 每个小区有三个扇区且小区半径相同, 基站位于小区的中心位置, 采用两发两收天线。每个扇区有N个用户和M个物理资源 (Physical Resource Block, PRB) , 用户k的QoS速率需求为Vk, 每个PRB占用B kHz的带宽和L个子载波。系统使用自适应调制编码 (Adaptive Modulation And Coding, AMC) 技术, 根据信道的瞬时状态采用QPSK、16QAM、64QAM三种不同的调制编码方案 (Modulation And Coding Scheme, MCS) [7]。采用动态系统仿真 (Dynamic System Simulation, DSS) , 为了考察用户间的公平性, 假定用户初始位置随机分配且有一部分用户长时间处于信道状况极度不好的状态。调度算法每个传输间隔 (Transmission Time Interval, TTI) 执行一次, 信道反馈延时d个I。 算法描述 定义矩阵单位阶跃函数ε (P) , P是一个一维矩阵, M 1为矩阵长度, 则有: PF算法 PF算法一方面充分利用用户信道的时变性, 另一方面较好地保证了系统多用户分集与公平性间的平衡。用户k在物理资源块m上的优先级为[8]: 式中rk, m (t) 为时间片t内用户k在物理资源块m上所支持的最大数据速率;Rk (t) 为用户k当前获得的平均速率, 每次调度后更新[9]。计算公式为: 式中tc为计算平均速率的时间片长度;rk', m (t) 为时间片t内用户k在物力资源块m上获得的速率, 当物理资源块m分配给用户k时, , 否则 USGF算法 USGF算法是一种保证用户满意度的公平算法, 用户k在物理资源块m上的优先级为: 式中R'k (t) 表示在时间片t内的调度过程中, 用户k获得的累计数据速率。 FCS算法 FCS算法是对USGF的一种改进, 引入用户满意度反馈ρk (t) 和Qos速率需求满足程度矩阵∆V, 在保证用户满意度和公平性的条件下提高系统的吞吐量。用户k在物理资源块m上的优先级为: 其中ρk (t) 表示用户k当前的满意度, 定义为: ρk (t) 的最小值定义为0.05以防止极小的满意度产生一个极大的优先级值, ∆V表示速率需求满足程度列矩阵, 定义为: 在时间片t开始调度过程中的t1时刻若ε (∆V) =0, 即此时PRB没有分配完毕, 但是所有用户都已经满足QoS速率需求, 同时还存在剩余的频率资源, 则式 (5) 化简为: 这时调度算法将不再考虑QoS速率需求, 而是将该资源块分配给在此资源块上数据速率最大的那个用户以获得最大的系统吞吐量。 调度结束后, 用户k所获得的吞吐量的计算公式为, 系统吞吐量计算公式为。 算法步骤: 1) 初始化用户集UE={U1, U 2...UN}, 物理资源块集PRB={RB1, RB2...RBM}和每个用户已获得的速率R'k (t) =0。 2) 取出用户集合UE和PRB中的一个物理资源块RBm。 3) 若α=0, 则用公式 (5) 计算优先级wk, m;若α=1, 则用公式 (9) 计算优先级wk, m。k∈[1, N], 选择最大的Wk, m并将RBm分配给Uk。 4) 将RBm从PRB中移除, 更新R'k (t) 和α后回到步骤2) , 直到所有RB分配完毕, 即PRB为空。 仿真与结果分析 仿真环境与参数设定 简单地, 假定系统中有如下两类业务类型。第一类业务 (class2) :目标速率Rk (t) =128kbps, 用户数为N/2;第二类业务 (class3) :目标速率Rk (t) =64kbps, 用户数为N/2;仿真参数如表1所示。 天线模型 每个基站均采用3扇区1 2 0度定向天线, 天线方向增益为:G (θ) =G-min[12 (θ/β) 2max, Gs] (dB) , 其中-π≤θ≤π, β=65π/180, Gs=20dB, Gmax=16dB。 宏观路损 使用3GPP TS25.814规范中定义的路损模型 (只和距离有关) 的路损公式来产生宏观路损图, 路损计算公式为L=128.1+37.6 log10 (R[km]) 。 阴影衰落 阴影衰落是由用户和基站间的传播路径中的障碍物引起的, 也可以看成是地形中的一些不规则的地理因素。它通常近似为一个均值为0dB、标准差为10dB的对数正态分布。 阴影会在一个较大的范围内产生影响, 为了捕捉对宏小区的动态影响, 这里采用了具有一定空间相关性的二维高斯过程。本模型中, 用一种低复杂度的方法将空间相关性引入到高斯过程中, 同时还保留它的统计属性和位置间的相关性。 仿真结果分析 (1) 图1给出了采用三种不同算法所获得的系统总吞吐量。可以看出PF算法所获得的总吞吐量远高于其它两种算法, 这是因为其它两种算法考虑了用户的速率需求, 部分速率需求高而信道状况差的用户造成了系统吞吐量的下降。通过计算, FCS算法比USGF算法系统吞吐量有所提高, 原因在于有些用户在某些时刻信道状况非常好, FCS算法能在满足用户速率需求的同时最大化系统的吞吐量。 (2) 图2给出了用户的平均满意度曲线。可以看出, FCS算法和USGF算法很接近, 而PF算法远低于这两种算法, 因为PF算法没有考虑用户的速率需求, 部分信道状况好而速率需求低的用户被分配了过多的资源造成了系统整体满意度的下降。 (3) 图3给出了三种算法下用户满意度的累积分布函数, 由用户的满意度累计分布函数曲线可以看出, 采用FCS算法和USGF算法时, 业务1和业务2的累计分布曲线较为接近, 而与PF算法则相差较大, 这说明FCS算法和USGF算法均能按照用户的速率需求分配资源, 相比PF算法更好地实现了不同用户不同速率需求业务之间的公平性。 结论 本文提出了一种保证QoS速率需求的分组调度算法并进行了仿真验证。通过对比, 得出该方法能够保证不同速率需求业务之间的公平性, 且在不降低用户满意度的条件下提高系统的总吞吐量。 参考文献 [1]沈嘉, 索士强, 全海洋, 等.3GPP长期演进 (LTE) 技术原理与系统设计[M].北京:人民邮电出版社, 2008 [2]ZHU H J, Hafez R H M.Scheduling Schemes for Multimedia Service in Wireless OFDM Systems[J].IEEE Wireless Communications, 2007, 14, (5) :99-105 [3]P.Xia, S.Zhou, G.B.Giannakis.Adaptive MIMO OFDM Based on Partial Channel State Information[J].IEEE Transactions on Signal Processing, 2004, 52, (2) :202-213 [4]3GPP TS36.331V8.5.0.E-UTRAN Radio Resource Control Protocols Specification[S].2009 [5]陆巍炜.LTE中QoS调度算法研究[D].西安:西安电子科技大学, 2009 [6]郑培超, 宋瀚涛, 贾韶军, 莫笑丽.LTE系统上行保证服务质量的分组调度算法[J].电子科技大学学报, 2009, 38, (2) :186-189 [7][Z/OL].http://www.nt.tuwien.ac.at [8]Hoon Kim, Keunyoung Kim, Youngnam Han, Sangboh Yun.A Proportional Fair Scheduling for Multicarrier Transmission System[J].IEEE Communications Letters, 2005, 9, (3) :210-212 [9]Pramod Viswanath, David N.C.Tse, Rajiv Laroia.Opportunistic Beamforming Using Dumb Antennas[J].IEEE Transactions on Information Theory, 2002, 48, (6) :1277–1294 [10]3GPP TS25.814.Physical Layer Aspects for E-UTRA[S].2006 [11]3GPP TS36.942V8.2.0.Radio Frequency System scenarios[S].2009 目前,全球移动数据业务的迅猛发展、对上行链路的数据速率和时延性能都有较高要求的业务应用的不断增加以及HSDPA技术的广泛应用都极大地推动了对HSUPA技术的需求,成为HSUPA技术商用的主要驱动力。虽然目前在TD-SCDMA网络中,需求较大的仍然是以下行为主的业务,HSUPA的具体引入时间点依赖于网络对以上行为主业务的需求,但随着未来网络业务媒体化、多样化的发展,以及对上行业务需求的日趋明显,HSUPA技术必将逐渐引入到网络中,研究TD-SCDMA系统中的HSUPA技术意义重大[1]。 在TD-HSUPA系统中,无线资源管理功能主要由分组调度算法来实现,分组调度算法将成为影响系统性能及保证用户服务质量的关键所在。研究先进的分组调度算法是提高数据业务吞吐量、保证用户间公平性、满足业务QoS的根本。合适的调度可让用户更公平地共享链路带宽,增强用户感知度,还可使网络承载更高的数据服务容量,增强网络建设的有效性。因此,在TD-HSUPA网络平台下,结合TD-HSUPA系统及所承载的多样化业务类型的特点,寻找一种合适的的调度算法很有必要。 2 TD-HSUPA系统的Node B快速调度 TD-HSUPA是TD-SCDMA系统R7版本中引入的增强技术,它可以为上行提供2.2 Mbit/s的峰值速率,这主要得益于TD-HSUPA系统在物理层引入了大量关键技术,如自适应编码调制(AMC)、混合自动重传请求(HARQ)及Node B快速调度等。本文重点介绍的就是Node B快速调度算法。 在TD-HSUPA系统中,基于Node B快速调度的方法是:由Node B代替RNC直接控制UE的传输速率和传输时间。在每个TTI中,UE通过上传调度信息向Node B汇报当前UE缓存中的待发数据量以及可用功率。这样,Node B和UE之间直接进行信令传输,且在TD-HSUPA中还支持5 ms的TTI,这样,这种基于Node B的快速调度大大缩短了调度控制信令和UE的响应时延,从而可以更加精确、快速地控制小区负载,从而获得更大的上行吞吐量,充分利用有限的带宽资源[2]。 UE请求下行调度资源时,Node B快速调度方法使用调度许可来指示UE被允许使用的最大资源。当确定调度许可时,Node B可以使用服务RNC提供的和UE发出的调度请求中的QoS相关信息。 在TD-HSUPA系统中,UE为了请求Node B上行调度资源,UE需要通过E-RUCCH信道传输上行资源请求,其中携带调度信息(SI),其中包括E-RNTI信息。如果UE被许可在E-DCH上发送数据,SI信息可以在MAC-e头中携带。UE为调度提供的内容包括Buffer信息和物理层信息[3]。 基于Node B的快速调度中,Node B在RNC设定E-TFC子集,通过发送L1信令,快速控制UE可选用的E-TFC集合大小,从而实现快速调整UE发送速率。图1给出了调度环境,该图显示分组调度与MAC-e相连。每个HSUPA UE在Node B中有自己的MAC-e实体。MAC-e最重要的功能是HARQ过程中的接收和确认部分。 3 无QoS保证调度算法 调度算法是在动态复杂的无线环境下使多用户更有效地使用无线资源,提高整个小区的吞吐率,与此同时,还要兼顾各个用户等级和公平性。下面介绍了TD-HSUPA中几种比较常用的无QoS保证的调度算法。 3.1 轮循(RR)调度算法 RR调度算法是一种最简单的调度算法,其特点是保证小区内的用户按照某种固定的轮询方式来循环占用有限的无线资源,从而实现数据传输。轮询的方式可分为基于时间的轮循方式和基于流量的轮循方式。基于时间的轮循中,每个用户被依次分配相同的时间,由于不同用户所处环境不同,得到的流量可能并不一致;基于流量的轮循中,每个用户被依次得到相同的流量服务,而不管用户实际信道条件的好坏。 RR算法较简单,并能绝对保证用户的公平性,但没有考虑用户实际无线信道间的差异,因此吞吐量很低。 3.2 最大载干比(Max C/I)调度算法 Max C/I调度算法的特点是追求最大的系统容量和最高的资源利用率,而不考虑用户间的公平性。它在任意时刻总是载干比最高的UE服务。 调度器在优先传输HARQ重传分组后,按照每个用户当前的C/I大小,选择最大C/I用户数据进行服务,用户载干比信息由用户设备测量后通过上行链路报告给Node B,或者Node B根据功率控制信息估计得到[4]。 当系统采用自适应调制编码技术时,采用最大载干比算法的无线系统可获得最大吞吐量,并且最大载干比算法实现简单,算法复杂度低。 但最大载干比算法完全没有考虑到不同用户的公平性要求,这种调度算法会使一些信道条件较差的用户长时间得不到服务。算法复杂度相比RR算法要高,因为需要对用户C/I值进行比较。通常认为最大载干比算法是最不公平的,并且把采用该算法得到的系统吞吐量看作系统吞吐量的上限。 在TD-HSUPA系统中,由于反馈的是0~30的离散整数信道质量指示(CQI)值,代表信道质量,因此调度算法中用CQI值代替载干比,称之为MAX CQI。调度优先级为 式中:i=1,2,…,N;CQIi(t)表示基站最近接收到用户i反馈的CQI值。 3.3 等比公平(PF)算法 PF算法中,每个用户根据信道状况、业务量大小以及服务状况等分配一个优先级,任意时刻小区中优先级最大的用户接受服务。优先级的计算为 式中:k=1,2,…,N;(C/I)k(t)为第k个用户在t时刻的载干比;Tk(t)为该用户在以t为结尾的时间窗口中的吞吐量。 在该调度算法中,每个TTI时间内,计算队列中的每个用户的相对瞬时信道质量,只有当用户具有最好的相对瞬时信道质量时才能得到服务。其中相对瞬时信道质量定义为瞬时信道质量与平均吞吐量的比值。这样,瞬时信道条件较好或者过去得到的吞吐量很低的用户的优先级将会提高。 综上所述,以上分析的3种算法都不具备时延约束条件,不能保证业务的传输时延要求,下面将分析具有时延约束的保证多业务QoS的调度算法。 4 保证多业务QoS的调度算法 4.1 M-LWDF调度算法 M-LWDF算法的优先级表示为 可以看出,该调度算法与前面所提到的3种无调度算法有明显的区别,那就是在优先级表达式中加入了时延相关的约束因子ai,通过ai来提高时延敏感业务的调度优先级;该表达式中的wi是队头时延;rij(n)表示用户在第j个信道上的传输速率,体现了用户的信道状况;Ri(n)表示用户i在第n个TTI内的平均吞吐量,在表达式中处于分母位置,这样可以提高公平性,照顾那些吞吐量低的用户,以防止出现“饿死现象”[5]。 该调度算法考虑了用户信道的状况和用户排队等待队列的时延情况,能够满足对时延要求高的用户需求。但是对于每一种业务种类,这种算法很难找到针对每种业务的理想解决方案,并且在系统负载较大时,这种算法的时延特性会有所下降。 4.2 EXP调度算法 EXP算法的优先级表达式为 式中:变量的定义均与M-LWDF算法中的相同,其中,是所有用户平均的加权包头延时,随着时间而变化,因而EXP调度对时延的敏感程度也是时变的,并且调度优先级与时延的关系呈指数关系。 该调度算法考虑了用户实际信道状况的好坏及不同实时业务的QoS要求,能够满足对时延敏感业务的需求。但该算法中指数运算的算法复杂度较高。 5 基于效用函数的调度算法 5.1 效用函数思想 在无线网络中,效用可以被解释为衡量用户对服务的满意程度。效用函数的基本思想是将系统资源和性能指标作为相应的效用函数的参数,不同的用户可以使用不同的效用函数,系统调度目的是在一定条件下取得最大的效用值[6]。效用函数的特点是,当系统提供的某一参数低于某一值时,效用值几乎为零;而当某一参数高于某一值时,则效用值为最大值1,此时再增加该参数,效用值也不会再增加。 5.2 基于效用函数的调度算法 不同的业务可以使用基于不同性能指标的效用函数,从而使效用函数具有不同的效用值曲线。非实时类业务效用函数的性能指标可以选取“吞吐量”,而时延敏感业务的效用函数可以选取“时延”作为性能指标。设计效用函数表达式的方法有两种:一种是对各种业务做全面的主观满意度调查,从而得出一个总体的效用函数表达式;另一种则是基于业务特性和公平性等因素设计出较合理的效用函数表达式。但是无论用哪种方法,都需要能够反映相应业务的Qo S要求[7]。 如图2所示,话音、数据和多媒体业务的效用函数的形式是不同的。对于话音业务,它必须达到一个固定的QoS指标,才能成功通信;而数据业务则将吞吐量作为性能指标,吞吐量越高用户的效用值也就越高,它的变化趋势可以用一个单调增的凸函数来表示;多媒体业务介于两者之间,可以采用S-型函数(如Sigmoid型函数)来表示。 在实际调度过程中,可根据不同的业务类型,来指定不同性能指标的效用函数,通过基于不同的主要性能指标进行资源分配。在基于效用函数的调度方法中,可分别用一条曲线来表示用户的效用值,该曲线可表示效用函数基于功率、速率、时延等性能指标的效用值[8]。 6 小结 文中讲述的几种无QoS保证的调度算法,算法结构简单,容易实现,但不能保证业务的实时性;保证多业务QoS的M-LWDF调度算法考虑了业务实际的信道状况好坏和排队时延情况,能够满足业务对时延的要求,但在系统负载较大时,这种算法的时延特性会有所下降;EXP调度算法同样考虑了信道状况的好坏及不同业务的QoS要求,能够满足时延敏感业务的需求,但该算法中指数算法的复杂度比较高。 因此,最后引入了基于效用函数的调度算法,将业务的时延、吞吐量等客观属性映射为代表用户满意度的效用值,结合相应业务的QoS要求,设计出合理的效用函数,并将其作为评估用户满意度的依据。这样得出的调度效果更加真实地反应了用户的满意情况,并可作为调度算法改进的依据。基于效用函数思想的调度算法将能大大提高TD-HSUPA系统的调度效果,从而使网络能够承载更高的数据服务容量,提高网络建设的有效性。 参考文献 [1]程军,李鸥,来卫国,等.无线网络信道队列状态感知资源调度算法[J].计算机科学,2009(4):47-49. [2]常永宇,杨大成.TD-HSPA移动通信技术[M].北京:人民邮电出版社,2008. [3]郑培超,贾韶军,宋瀚涛,等.LTE系统上行保证服务质量的分组调度算法[J].电子科技大学学报,2009(3):186-189. [4]范晨,张琳,廉文娟.一种在混合业务中保证流业务QoS的调度算法[J].北京邮电大学学报,2007(6):75-78. [5]翁英萍,季中恒,彭建华.基于时延的分级多业务调度算法研究[J].计算机工程与设计,2009(6):1311-1315. [6]牛志升,王兰,段翔.多媒体DS-CDMA系统中基于效用函数的无线资源优化策略[J].电子学报,2004(10):1594-1599. [7]GUO K,SUN L,JIA S,et al.Dynamic data scheduling and re-source management using max-utility estimation in next generation wireless networks[C]//Proc.First International Conference on Inno-vative Computing,Information and Control.Washington:IEEE Press,2006:433-436. 1 定长分组与变长分组交换的特点 虽然就交换结构本身而言, 基于信元的交换技术已发展的相当完善, 但从系统的角度看它仍存在一些问题。首先, 由于交换结构在入端口需要对变长分组切割、在出端口需要对信元重组, 从而引入了较大的交换时延;其次, 在分组切割为信元的过程中还存在n+1问题;此外, 多级交换网络中采用定长信元交换, 除了在单Crossbar中的缺点外, 还会引起信元的乱序。信元间乱序会使交换网络为了重排序而付出很大代价, 所以在多级网络中要尽量避免信元间的乱序。 开展对变长分组交换技术的研究是对现有交换技术的完善和补充, 变长交换技术实际上就是在交换结构中直接处理变长分组, 而不将分组切割为信元再来传输。在数据通道上, 当某个入端口开始交换一个分组到出端口时, 这条入端口一出端口的数据通道一直保持畅通, 直到整个变长分组被传送到出端口才释放该通道。为了提高变长交换的效率, 解决分组切割和重组带来的缺陷, 降低网络实现的成本和难度, 通常在变长分组到达入端口时, 并不采取真正的物理上的切割分组, 而是逻辑的切割分组为定长信元, 对定长信元背靠背传输, 因此在传输的过程中以及到达出端口处收到的分组仍然是完整的, 从而避免了重组分组的操作。将每一个分组从逻辑上分割为多个信息单元, 一个信息单元的长度是交换网络一个时隙转发信息的数量 (为了简单起见, 也将其称之为信元) 。分割后只在第一个信元加上分组标识, 在最后一个信元加分组结束标志, 其他的中间信元不需要加任何开销 (这种交换方式类似于直接连接网络中的Virtual Cut-Through交换方式) 。 2 基于变长分组交换的MSM型三级Clos结构 2.1 改进的MSM型三级Clos结构 为了更好地支持交换结构的可扩展性[5], 这里改进了MSM型的三级Clos结构, 在输入增加了队列管理器, 输出增加了令牌发生器和输出调度器, 如图1所示。 在这个三级结构中, 将这三级分为输入级模块 (ingress module, IM) 、中间级和输出级 (egress module) 。每一级都有多个模块 (Modules) , 每个模块又有多个入端 (inport, IP) 和出端 (outport, OP) 。这里只有中间级是纯粹的Crossbar交换结构, 没有缓存器件;而输入级和输出级模块中都含有缓存队列。输入级包 含VOQ以消除HOL阻塞, 输出级的输出队列用于当多个数据包竞争同一输出端口和信元重组的缓存。在输出级当中, 每个输出端口都拥有一个输出端口调度器 (output scheduler, OS) 。 另外, 实际交换机应该是N×N的对称结构, 所以规定三级结构中输入级和输出级模块的个数是相等的, 并且每个输入模块的输入端口数和每个输出模块的输出端口数也应该是相等的。而中间级crossbar模块个数和每个模块的端口数是可以调整的, 但应该是输入端和输出端相等的“方形”结构, 如图2所示。 输入级的作用:去往特定目的端口的数据包在输入端的VOQ中排队, 等待发送;VOQ 避免了队头阻塞;队列控制器将队列的状态通知相应输出端口的输出调度器 (当队列长度超过了一定的门限值时, 输入级向输出调度器发送队列状态信息) ;根据输出调度器返回的信息发送存储的数据包。 输出级的作用:解决数据包在输出级的冲突;用于对分段数据包的重组;根据调度算法和收到的队列状态信息发放令牌, 分配输出端口的带宽 (带宽的分配即可按队列长度划分可按队列的服务等级来划分) 。 中间级的作用:在MSM结构中, 中间级无缓存, 由Crossbar组成, 中间级与输入级、输出级采用了全互连的方式连接。中间级的主要作用是为从输入级转发出来的数据包提供多条路径。 队列管理器:在每一个输入级模块中, 都需要有一个队列管理器来管理VOQ的状态, 并根据当前状态及时向位于输出端口的输出调度器发出队列状态信息来请求输出带宽。每当队列状态发生变化时, 队列管理器就向输出调度器发送信息, 通知调度器及时更新队列数据库。为了减少控制信息的流量, 以避免控制信息过多地占用数据通道, 我们设定, 每当队列的长度超过一个事先设置好的门限时, 才进行发送队列信息的操作。 输出调度器:接收来自输入级队列管理器的队列状态信息, 并根据所维护的队列状态数据库中的队列属性, 按照一定的调度算法来进行调度, 并将自己从令牌发生器处获得的令牌分配给满足条件的队列。 令牌发生器:令牌是由专门的令牌发生器产生的, 每个输出级拥有一个令牌发生器, 它根据各个输出端口的带宽来产生令牌, 并把令牌分配到各输出端口供输出调度器调配。 优点:经过改进的三级结构可以构造出任意大小的交换机而没有性能的损失, 它只需要提供出足够的用于互连的交换单元即可, 系统还可以增加其他速率的端口或对己有端口的重用来增加初始时的系统速率。同时, 集中式调度算法的复杂度与端口数量有关, 增加端口数量将进一步加大调度器的实现难度, 而分布式的输出调度器放置, 增加了交换结构的可扩展性。总之, 改进的交换结构具有较强的可扩展性, 可以任意增加交换单元的数目和端口速率来扩展交换容量[6,7,8]。 2.2 ACBS算法调度过程 根据上述的多级Clos交换网络结构, 设计相应的ACBS (asynchronous credit-based scheduling) 算法, ACBS与传统用于多级结构的调度算法区别在于:调度器分布在各个输出端口, 是一种分布式的调度算法;各个输入级独立发送数据包, 支持第一级链路的负载均衡;摒弃了传统的“两次匹配”的调度过程, 采用一次调度;调度算法的成功实现要依赖于令牌的分配和发放。在该结构中, 一个输入队列象征着一个用户流, 同时对应着一个输入端口、输出端口和服务属性。一个输出调度器与一个目的端口相连, 调度器通过将输出端口带宽分配给所有竞争的队列来控制数据从输入队列中“拉”出。当队列某一状态发生变化时, 队列管理器立刻向调度器发出队列状态改变信息, 调度器将自己从令牌发生器获得的令牌分配出去, 令牌经过交换结构被送往输入级, 如图3所示。输入级积累一定的令牌, 用来发送数据包给交换结构。收到输出调度器返回的令牌之后, 队列管理器将数据包从队列中移出并向交换结构转发[9]。 2.2.1 ACBS输入级算法步骤 ACBS输入级算法步骤如下: 步骤1: 收到来的数据包, 读取其目的地址并将其分往相对应的VOQ (i, j, h) 中。由于在每个输入级当中, n个输入端口共用同一组VOQ, 因此, 当多个输入端口同时将数据送往同一个VOQ时, 采取随机选取方式解决冲突。当输入流具有不同的相对优先级时, 则根据优先级等级个数来增加VOQ的组数。 步骤2: 队列管理器负责监控队列状态, 当VOQ (i, j, h) 队列状态发生改变的时候, 立刻把队列状态消息status_msg (i, j, h) 送到输出调度器OS (j, h) 处。但是由于控制信息的发送仍然是占用数据通道, 因此, 为了减小控制信息的流量, 采取了每隔一定的时间发送队列状态信息的方法。该算法中, 将时间间隔定义为VOQ (i, j, h) 的队列长度Queue_L (i, j, h) 超过了门限值Threshold, 队列控制器才发送:status_msg (i, j, h) :Queue_L (I, j, h) ≥Threshold。 步骤3: 接收令牌Credit (i, j, h) 。为了方便地管理每个队列, 队列管理器为每个VOQ维持了一个令牌计数器CC (i, j, h) 。当令牌从输出调度器OS (j, h) 返回给输入级IM (i) 时, 队列控制器作出以下操作:CC′ (i, j, h) =CC (i, j, h) +1。 步骤4: 输入级IM (i) 将CC (i, j, h) 最大的VOQ中的数据包从队列中取出, 如果处理的对象为定长分组, 就直接将其分发到第一级的所有链路上;如果需要交换的是变长分组, 则先将其切分为相同长度的分组, 再逐一转发到第一级的所有链路上。同时, 将CC (i, j, h) 减去分组长度对应比例 (比例设为1个令牌可以发送长度为所有数据包平均长度Avrg_L的分组) 的令牌, 更新CC (i, j, h) 。当链路空闲后, 重复步骤4, 直到IM (i) 中所有CC (i, j, h) <0。 2.2.2 ACBS输出级算法步骤 ACBS输出级算法步骤如下: 步骤1: 输出调度器OS (j, h) 维持了输入级所有请求本端口带宽的VOQ的队列状态数据库。它实时接收来自输入级的队列状态信息status_msg (i, j, h) , 并同时更新队列状态数据库。 步骤2: 输出级EM (j) 的令牌发生器按照各输出端口带宽以一定速率产生令牌, 并将令牌定时分配给各输出端口。目前讨论的交换结构所有输出端口带宽相同, 因此, 所有输出端口获得相同的令牌。 步骤3: 输出调度器OS (j, h) 根据队列状态数据库对输入级的VOQ进行调度, 给有资格获得输出带宽的VOQ返回令牌。在本算法中, 为了简化调度过程, 定义队列长度最长的VOQ (i, j, h) 可以获得令牌。输出调度器OS (j, h) 根据其队列长度Queue_L (i, j, h) 的比例减去已发送的令牌值;若此时OS (j, h) 的令牌有剩余, 则重复步骤3将余下的令牌分发给其他VOQ。 步骤4: 接收从中间级到来的信元, 将信元放入输出队列中等待重组转发。 3 ACBS调度算法及性能分析 在仿真实验中首先检验了ACBS算法在变长分组交换体制下的性能, 图4给出了仿真性能, 在变长分组交换体制下, 当输入负载在0.5以下时, ACBS算法能获得良好的时延特性。 同时, 也将ACBS算法和CRRD-PM调度算法进行了比较, 由图5可以看出ACBS能有效地降低分组的端到端时延, 这是因为在ACBS中, 采用1次调度的方式进行输入/输出端的匹配;而且数据交互实时进行, 有效地降低了分组在VOQ中的配对时间。而CRRD采用轮询的方式进行二次调度, 当输入负载接近100%时, 会引起分组的积压, 增加了总的交换时延。 4 结 语 通过性能分析和比较, 对三级Clos网络中交换机制选择可以得出如下结论:采用变长分组交换不需要将分组分割的ISM模块和信元重组的ORM模块, 可以降低成本, 同时, 变长分组交换较定长信元交换节省开销, 可以充分利用交换网络资源;更为重要的是在多级网络中, 变成分组交换不会引起同一分组信元间的乱序, 不需要引入了输出重排序缓存或负载的防止信元乱序算法, 降低了交换网络调度算法的实现难度;但是变长分组交换对输入业务的适应性不如定长信元交换, 在变长分组交换中, 交换网络的性能和分组到达以及分组长度分布具有很大的关系;而在定长信元交换中, 对分组长度分布的依赖性不是很强;同时, 网络负载较大时, 变长分组交换方式性能不如定长信元交换[10];ACBS算法属于流调度算法, 采用分布式的调度方式, 通过输出调度器将数据包从输入端口“拉”向输出端口。在ACBS中, 输入/输出之间采用异步交互控制信息的方式进行分布式的一次调度算法。仿真表明, 它能考虑业务特性和输出带宽进行调度, 降低数据包的平均时延, 能方便地支持负载均衡。 参考文献 [1]FIROI U V, L E BOUDEC J Y, TOWSLEY D, et al.Theo-ries and models for internet quality of service[J].Proceed-ings of the IEEE, 2002, 90 (9) :1565-1591. [2]王重钢, 隆克平, 龚向阳, 等.分组交换网络中队列调度算法的研究及其展望[J].电子学报, 2001, 29 (4) :43-48. [3]JINOO Joung, JONGTAE Song, SOONSEOK Lee.Flow-based QoS management architectures for the next generationnetwork[J].ETRI Journal, 2008, 30 (2) :238-248. [4]WANG F, ZHU Wen-qi, HAMDI M.The central-stage-buffered Clos-network to emulate an OQswitch[C]//IEEEGlobecom Proceedings.California:[s.n.], 2006:4244-4257. [5]杨君刚, 刘增基, 顾华玺, 等.混合交换机制三级Clos网络分布式调度算法[J].西安电子科技大学学报, 2008, 35 (4) :581-585. [6]NICT.New generation network architecture[M/OL].[S.l.]:[s.n.], [2007-10-08].http://akari-project.nict.go.jp/eng/.October 2007. [7]GANJALI Y, KESHAVARZIAN A, SHAH D.Inputqueued switches:cell switching vs.packet switching[C]//IEEEINFOCOM’03.San Francisco:[s.n.], 2003:1651-1658. [8]ZHONG Hakhan, XU Du, ZHUZhen-yu.Aparallel packetswitch supporting variable-length packets[C]//InternationalConference on Communications, Circuits and Systems Pro-ceedings.Hong Kong:[s.n.], 2005:613-617. [9]GOUDREAU M W.Scheduling algorithms for input-queuedswitches:Randomized techniques and experi mental evalua-tion[C]//IEEE INFOCOM’00.Tel Aviv:[s.n.], 2000:1624-1643. 近年来移动视频业务迅速增长, 已经逐渐成为移动互联网的主导业务[1]。根据思科的市场研究报告, 2013年以来, 全球移动数据流量增长了81% , 这其中大约有53% 是移动视频业务的增长[2]。预计到2015年移动视频流量将占超过全球移动流量的一半。移动视频流量的快速增长给无线网络的高质量视频传输带来了挑战。 高质量的视频传输往往需要足够大的带宽。例如, 传输H.264/AVC编码的1080p分辨率的视频平均需要6Mbit/s -8Mbit/s。假如通过宽带有线网络来传输的话, 将很容易满足需求。然而, 利用单一的无线网络可能无法支持高质量视频的传输。尽管如此, 目前的主流技术仍然是利用单一的无线网络传输视频。由于单一无线网络 ( 例如UMTS和WLAN) 的容量受限以及信道的时变特性, 只利用单一的无线网络传输高质量视频的话, 移动终端用户可能遭受频繁的播放中断, 影响了用户的体验。 目前, IEEE802.11系列, IEEE802.16 WiMAX系列和蜂窝网络家族 ( GSM, UMTS, LTE) 等无线接入技术的发展, 促成了下一代无线网络的异构特性。与此同时, 智能手机也逐渐地在普及起来。据2014年1月27日的国际数据公司 ( IDC) 全球手机季报, 2013年的全球智能手机出货量首次超过十亿部。通常来说, 几乎所有的智能手机都配备多个网络接口。因此, 智能手机具有同时地能够连接到多个无线网络进行数据传输的能力。在这种情况下, 我们可以考虑同时利用多个无线接入网传输高质量的视频流。在本文中, 我们称之为多网并发传输高质量视频流。虽然多网并发传输视频在文献中得到了广泛的讨论, 却因为对网络设备存在额外的性能需求而无法广泛部署。另外一个关键点是需要在服务器端实现合适的分组调度算法。 在多网并发传输高质量视频中, 分组调度算法应当充分地考虑应用所要求的QoS和无线网络的特性。传统的分组调度算法按照轮询的方式将视频流分配到特定的接入网进行传输。这种传统的round -robin方法由于接入网络之间负载不均衡以及数据包乱序的到达可能会导致视频质量的下降和播放中断。针对这种情况, 基于对可用带宽进行测量的速率控制方法 ( rate -control) 实现了吞吐量和延迟之间的良好折衷。然而, 速率控制方法没有考虑视频数据包之间的相互依存性。在视频编码中, 每个图像组 ( GOP) 中不同的视频帧有不同程度的的重要性。例如, I帧根据原始帧独立压缩, 而P帧都依赖于前面的I/P帧, 而B帧则依靠前面和后面的帧。因此, 在多网并发的视频传输中, 应该充分考虑每个接入网的状态和视频帧之间的依赖关系来确定如何分配调度视频分组到各个无线网络当中。 另一方面, 可伸缩视频编码, 如H.264/SVC标准, 由于它在各个场景下均具有很好的适应性和向后兼容性, 已广泛地应用在视频流传输中。H.264/SVC标准定义了三种典型的可扩展纬度, 包括空间可扩展性, 时间可扩展性和质量可扩展性。在可伸缩视频编码中, 一个比特流被分层为基本层和增强层。基底层向后兼容非可伸缩视频编码并提供了基本的视频质量, 而增强层与基础层结合起来又提供了进一步改善的视频质量。本文利用图1帮助读者理解不同视频帧的分层结构。其中, 箭头表示视频帧之间的相互依赖关系。从图中可以看到, 基体层包含I帧和P帧, 而B帧则构成的增强层。视频帧之间的这种相互依赖关系促使在调度视频帧到接入网络时要充分考虑各种因素, 尤其是在多网并发传输视频流的情况下。关于H.264/SVC标准的详细信息, 请参阅[5]。 在异构无线接入网络的环境下, 为了提高多网并发传输视频流的性能, 本文提出了一种有效的分组调度算法, 基于每个接入网络的特性和视频帧特征, 来确定每个接入网络的传输速率与被包含在每个子流视频数据包。本算法的目标是最大限度地提高接收端的视频质量。典型地, 视频内容以H. 264/SVC进行编码, 基于它在多网并发传输视频流上的优越性。在仿真中使用了真实的视频trace文件去研究了该算法的性能, 并与传统的round -robin方法和码率控制rate -control方法进行比较。 文章的结构如下: 第二节, 本文将回顾多网并发传输视频流的相关工作. 然后, 我们在第三部分描述系统模型并对问题进行建模. 多网并发传输可伸缩编码视频流中质量驱动的分组调度算法将在第四部分进行描述. 然后我们对提出的算法仿真进行性能评估。最后, 我们给出本文的结论和未来开展的工作。 2 相关工作 我们将回顾多网并发传输视频流的一些相关工作。文献[6]提出了在WCDMA网络视频传输中的一种内容感知的优化方案, 该方案选择了最优的视频帧的集合来传输。然而, 作者主要关注了单一网络中的视频传输问题。Freris等考虑了异构接入网络中的多网并发传输可伸缩编码视频的问题, 为了最小化接收视频质量的失真, 提出了一种基于凸规划的随机分组调度算法。但是, 该算法只能应用在具有少数客户的服务器上, 否则, 会引起大量的开销。在文献[8]中, 作者考虑到了视频业务批量到达的性质, 并提出了对多网并发传输视频流下的概率分流方案的性能分析框架。文献[9]提出了一种能效和内容感知的多网并发传输视频流媒体框架, 但是该文献假设分组不会遭受丢包的影响, 这是不合理的. 文献[10]将多网并发传输点播视频流建模成马尔科夫决策问题, 并提出了有效的参数估计, 阈值调整和阈值补偿算法. 但是该文献中并没有考虑可伸缩编码视频流。 3 系统模型和问题建模 3. 1 网络模型 图2为异构多网并发传输可伸缩编码视频流的应用场景示意图, 从图中可以看出, 多模终端有多个可接入的网络:WiFi网络, 3G或4G的无线通信网等。多模移动终端采用哪个接入网络来传输视频流中的特定的数据包是本算法所要解决的问题。假设存在N个独立的接入网并分别定义为n = {1, 2, …, N} , N≥2 , 由于每个接入网络都是时变的, 需要定时检测它们的可用速率Cn、往返时延τn, 并根据下面的等式来估计每个接入网的丢包率pn: 其中, αn是系统参数, 可根据经验来设定。 3. 2 视频流模型 视频序列根据H.264/SVC标准被编码成具有固定帧率f的比特流。这个已编码的视频流S包括有多个网络提取层单元 ( Network Abstract Layer Unit, NALU) , 每个网络提取层单元Uk, l的大小由sk, l来表示, 这里的k和l分别表示帧号以及增强层数。由于不同的NALU有不同的大小, 而且它们的大小可能超过最大传输单元 ( MSS) , 因此这些NALU被封装成多个数据包进行传输。在本文中, 假设属于同一个NALU的数据包都采用同一个接入网进行传输, 因此, 本文提出的方法的粒度在NALU上。由于视频流采用图像组 ( GoP) 结构进行编码, 也就是说, 来自相同图像组的视频帧采用运动补偿的方式进行编码, 它们之间是相互依赖的;而来自不同图像组 ( GoP) 的视频帧是相互独立的, 正如图1所描述的那样。视频帧的这个特性导致了不同的NALU具有不同的重要性, 因此, 在对可伸缩编码的视频流进行分组调度时需要考虑每个NALU对接收端视频质量的贡献。定义NALU的重要程度为权重dk, 也就是说, 具有相同帧号k的NALU具有相同的重要性。 本文提出的算法应用于时隙定长的环境, 也就是说, 时间被分成多个固定时间长度为δ的时隙t = {1, 2, …, T} 。在每个时隙内, 发送端都有一段来自相同图像组 ( GoP) 的视频分组需要进行调度传输, 这些视频分组来自基础层和增强层。时隙的长度δ等于大小为n的图像组的播放时长, 可表述为δ = n/f。然后在每个时隙内, 发送端根据网络的状态和视频帧的特性对每个待发送的图像组 ( GoP) 里的NALU做出调度。本文定义每个时隙 ( 图像组) 内的最大帧数是KT, 即是0≤k≤KT; 最大增强层数为LT, 即是0≤l≤LT。 3. 3 问题建模 在本节中, 我们将讨论多网并发传输视频流的建模问题, 目标是最大化接收端的视频质量. 在调度分组时需要考虑视频分组的特征 ( 失真权重和播放期限) 以及接入网的特性 ( 可用带宽, 丢包率和时延特性) 。 定义xk, l, n为指示NALU通过哪个接入网传输的0 -1变量, 当xk, l, n= 1表明Uk, l接入网n来传输, 否则的话, xk, l, n= 0。每个分组最多只允许通过一个接入网来传输, 可以表示为等式 ( 2) 在考虑有丢包的情况下, 接收端视频质量可以量化为D , 表示为式 ( 3) 每个分组都存在一个播放期限, 相同视频帧的NALU具有相同的播放期限, 在期限之前这个分组必须在接收端被解码, 超过这个期限视频帧将会被丢弃。由于编码过程存在依赖性, 如果视频帧在发送时与播放时的顺序不同, 接收端必须重新组织视频帧以进行顺利播放, 这就导致不同的帧类型具有不同的播放期限限制。例如, B帧相比I帧和P帧具有更加严格的播放期限。因此本发明将属于B类型的NALU调度到具有较小时延的接入网进行传输。另外, 每个接入网在每个时隙中的传输的NALU的速率为rn, 满足等式 ( 4) 根据H.264/SVC标准, NALU之间存在解码的依赖关系, Uk, l的成功解码需要依赖于Uk, l' ( l' < l) , 本发明定义Pk帧k的父帧集, 即Uk, l解码需要依赖的视频帧的集合。根据解码的依赖关系, 如果Uk, l的父帧集里的NALU没有被调度的话, 它也不能被调度传输。这可以用等式 ( 5) 表示。 根据以上分析, 本发明将异构网络并发传输可伸缩视频流建模为类似于一个受限的多背包问题, 并表示为 其中, s. t. 代表subject to, 即限制条件, s. t. ( 2) — ( 5) 表示以公式 ( 2) —公式 ( 5) 作为限制条件。 4 优化算法 本节提出一种多网并发传输视频流的启发式分组调度算法。该算法在调度数据包到可用的接入网络时考虑了分组特性与网络条件。 正如算法1所示, 它的输入是丢包率pn, 网络可用速率cn, 网络往返时延τn, 输出变量是二进制变量xk, l, n, 这个输出变量指示每个NALU的选择哪个接入网络进行传输。首先, NALUs被分类成基础层和增强层[9]。然后这两类不同的NALUs分别地根据dk/sk, l的大小进行排序。属于基础层的已经排好序的NALUs再逐一分配到丢包率最小的接入网进行传输, 如果基础层的NALUs没有进行传输, 那么属于增强层依赖于基础层才能解码的NALUs是不能传输的。定义Rn为接入网n目前已经使用的带宽。据此, 要成功分配某个NALU到接入网络n进行传输的话, 必须满足r ( Uk, l) + Rn≤cn。 属于增强层的NALUs进行调度时, 首先根据τn的升序对接入网进行排序, 但是剔除不满足最大允许丢包率pmax条件的接入网。然后已经排序的NALUs分配到还要剩余容量的接入网去。该算法每隔一个时隙δ运行一次, 因此, 输入变量pn, cn, τn以及pmax需要在每个时隙都更新一次。该算法的伪代码如下所示。 算法1: 多网并发传输视频流的启发式算法 5 仿真结果 为了验证本文提出算法的性能, 在仿真中采用了NS -2仿真软件、JSVM工具和SVEF工具。首先采用JSVM工具对四个不同的视频序列 ( 分别是Foreman, Football, Crew和Harbor) 进行编码产生比特流。编码之后的比特流由基础层和两个增强层组成。然后这些比特流经过SVEF工具处理产生NS -2的trace文件。这些trace文件包含了视频帧的大小和帧号。时隙间隔大约为520ms。利用NS -2仿真软件搭建一个异构无线接入环境, 包括WLAN ( IEEE802.11n) 以及UMTS两个不同的接入网, 用来将视频trace传输到多模终端。视频分组按照本文提出的启发式算法以及两种参考算法 ( 分别是round -robin和速率控制方法) 调度到不同的接入网来传输。在多模终端侧, 两个接收trace文件将会产生并合并成一个新的trace文件。然后, 利用SVEF和JSVM将接收比特流解码产生接收视频。本文利用峰值信噪比来对比算法的性能。我们首先描写仿真搭建的过程, 其中包括视频序列的编码, trace文件的分流以及仿真的方法。我们考虑这样的一个场景: 远端服务器发送采用H。264/SVC可伸缩编码的视频到处于背景流量下的一个多接口终端。 5. 1 接收端视频的质量对比 图3为本发明方法与现有技术中的round -robin方法、速率控制方法的实验结果对照图, 从图3可以看出本发明提出的方法能够使得接收端获得更高的视频质量和用户体验。能够使得接收端播放的视频质量保持稳定, 而其他两种方法产生较大的视频播放质量波动。 5. 2 不同视频序列下的视频质量 我们提出的启发性算法与前面提到的两个参考算法进行比较。从图4可以看出, 提出的分组调度算法在峰值信噪比上优越于其他的两种算法。 5. 3 对抗丢包的能力 图5为本文提出算法与现有技术中的round -robin方法以及速率控制方法在不同丢包率下的性能比较图。从图5中可以看出, 在丢包率逐渐增加的过程中, 采用本发明方法所得到传输结果的视频质量比采用其他两种方法所得到的传输结果的视频质量下降的慢。因为本发明将具有较高权重的分组调度到较小丢包率的接入网进行传输, 因此本发明方法具有较高的对抗丢包的能力。 6 结束语 本文中, 提出了一种可内容感知可伸缩视频流媒体框架, 该框架通过同时地利用多个异构的无线接入网络从远程服务器传输视频到多宿主终端。我们提出了一种多接口传输可伸缩视频流的启发式算法, 并利用NS -2仿真软件以及真实的视频trace来验证算法的性能, 实验表明, 我们提出的算法相比传统的算法能够明显地提升接收端的视频质量。 参考文献 [1]Evensen K, Kaspar D, Griwodz C, et al.Improving the performance of quality-adaptive video streaming over multiple heterogeneous access networks[C]//Proceedings of the second annual ACM conference on Multimedia systems.ACM, 2011:57-68 [2]IDC.Worldwide Smartphone Shipments Top One Billion Units for the First Time, According to IDC.https://www.idc.com/getdoc.jsp?containerId=prUS24645514. [3]Ramaboli A L, Falowo O E, Chan A H.Improving H.264 Scalable Video Delivery for Multi-homed Terminals Using Multiple Links in Heterogeneous Wireless Networks[C]//Military Communications Conference, MILCOM 2013-2013 IEEE.IEEE, 2013:1063-1068 [4]Freris N M, Hsu C H, Singh J P, et al.Distortion-aware scalable video streaming to multinetwork clients[J].Networking, IEEE/ACM Transactions on, 2013, 21 (2) :469-481 [5]Schwarz H, Marpe D, Wiegand T.Overview of the scalable video coding extension of the H.264/AVC standard[J].Circuits and Systems for Video Technology, IEEE Transactions on, 2007, 17 (9) :1103-1120 [6]Pandit K, Ghosh A, Ghosal D, et al.Content aware optimization for video delivery over WCDMA[J].EURASIP Journal on Wireless Communications and Networking, 2012, 2012 (1) :1-14 [7]J.Nightingale, Q.Wang, and C.Grecos, “Performance evaluation of concurrent multipath video streaming in multihomed mobile networks, ”International Journal of Digital Multimedia Broadcasting, vol.2013. [8]Song W, Zhuang W.Performance analysis of probabilistic multipath transmission of video streaming traffic over multi-radio wireless devices[J].Wireless Communications, IEEE Transactions on, 2012, 11 (4) :1554-1564. [9]Ismail M, Zhuang W, Elhedhli S.Energy and Content Aware Multi-Homing Video Transmission in Heterogeneous Networks[J].Wireless Communications, IEEE Transactions on, 2013, 12 (7) :3600-3610. 关键词：HSDPA,实时调度算法,M-LWDF,中断率,吞吐量 0 引言 HSDPA是UMTS的最新演进。在HSDPA系统中,无线资源管理功能主要是由分组调度算法来实现的,研究先进的分组调度算法是提高数据业务吞吐量、保证用户间的公平性的、满足业务QoS的根本[1]。 针对非实时业务,高通公司提出的Proportional Fair(PF)算法具有很好的应用前景,但是该算法不支持实时业务。为了支持实时业务的要求,同时又考虑系统吞吐量的优化,朗讯贝尔实验室提出了M-LWDF(Modified Largest Wait Delay First)和 EXP-rule算法[2,3],并从理论上证明它们具有吞吐最优的性质。但是,M-LWDF算法在用户公平性方面不是特别理想。M-LWDF算法的吞吐量性能的提升是以用户公平性为代价的,信道状态较差的用户的分组会在基站队列中等待,而一旦超过时间限制,这些分组将会丢掉而不再被服务。为了降低被丢弃的概率,提高用户的公平性,本文对M-LWDF算法优先级公式进行了修改,对吞吐量较低的用户进行补偿。通过设置合理的参数对所修改的M-LWDF算法进行仿真分析,并从系统吞吐量、用户中断概率等方面与现有M-LWDF调度算法进行了比较。 1 M-LWDF算法分析改进 最小吞吐量保证是QoS要求的重要组成部分,如果每个用户都有最小吞吐量保证,那么所有满足此条件的用户将被服务;对不不满足此条件的用户,可以通过改变调度规则,使其调度优先级得到提高,以保证低吞吐量用户的公平性。调度规则选中的用户可以定义如下: 式中,pi为被服务用户的优先级;j为拥有最高优先级的用户。 M-LWDF算法是针对高速业务流提出的,其主要思想是将分组包的时延和如何有效利用信道信息平衡考虑,其用户优先级的计算不仅和用户当前的信道质量有关,还和包和队列时延有关[6]。 M-LWDF算法用户优先级定义为: 式中,δi为QoS参数,表示最大分组丢失概率,主要是对分组时延进行限制;Ri为在每个TTI内所支持的最大数据速率,它放映了信道的瞬时状况,信道条件越好,支持的最大传输速率就越高,那么用户的优先级就越高;λi为用户平均吞吐量的估计,考虑到用户的公平性,对信道条件好的用户限制其优先级,使得信道条件差的用户可以得到服务;Di为用户i的HOL分组延时,分组在队列中等待的时间越长,其优先级也就越高,这里也是考虑到了用户公平性;Ti为用户i在队列中等待的时延限制,当分组在队列中的等待时延超过此值时,分组就被丢掉,因此时延限制越大,分组包被丢弃的概率就越小。在每个TTI拥有最高pi的用户得到服务。 M-LWDF算法是一种非公平算法,对信道条件差的用户,该算法会造成这些用户的数据包在基站侧有较大的时延,当时延超过用户的最大容忍时间时就会被抛弃。 为了降低Node B侧数据流包被丢弃的概率,需要对信道条件差的用户进行补偿。改进算法的调度规则如下,基于用户公平性,在保证用户分组的最小吞吐量的条件下最大化实时业务的用户数。调度规则为: 式中,C为提前定义的最小吞吐量[4,5]; 算法不仅考虑到信道条件和用户时延的影响,还考虑到了用户最小吞吐量保证。对于平均吞吐量开始低于最小吞吐量的用户,通过乘上一个权值因子W来提高低吞吐量用户的优先级,增加了系统中用户之间的公平性。 2 改进算法的性能测试 视频流业务的稳态模型如图1所示。在这个模型中,一个会话时间被定义为整个仿真时间,即整个仿真时间处于同一个会话中;视频数据的每一帧以间隔T到达,T由帧速率决定;每一帧可以分解为确定数据量的片段,每个片段作为一个分组发送;编码延时指在视频编码器引入的时延,也就是一帧中分组间的间隔。 为了评估算法的容量性能,网络仿真必须能够满足那些提供不同负载和时延限制参数的小区。针对此,定义平均吞吐量,其表达式定义如下[6]: 式中,α[n]为在TTI[0,n]内HS-DSCH信道上成功传输的比特数。 中断率也是评价网络性能的重要方面,实时业务系统中断率定义如下: 式中,Num为对列时延超过最最大时延限制的用户数;Ntotal为被服务用户的总数;Di、Ti意义如前面所述。 3 仿真环境设置和结果 3.1 仿真环境设置 本文是用C++搭建HSDPA仿真平台,系统服务区包括19个小区,每个小区有3个扇区。文中采用128 kbps的固定比特速率视频流业务,CBR视频流编码。3GPP规定传输时延属性:传输时延以95%的概率小于门限值,即中断概率小于0.05。如果传输时延增加导致用户抗抖动缓冲器中没有分组,用户不可以再触发新的缓冲,这种情况也归为终端状态之内。路径损耗模型[5]为: L=128.1+37.6lgR。 (6) 式中,R为小区到移动台的距离。其他仿真参数设置如表1所示[6]。 3.2 仿真结果 在M-LWDF算法情况下,不同时延限制下,吞吐量和中断率的试验结果如图2所示。文献[6]只给出3条时延限制1 s、2 s和3 s试验曲线。 从图2可以看出,在保持中断率不变的情况下,增加时延可以增加小区吞吐量,随着时延的增加,小区可容纳的用户数增多了,相应小区的吞吐量就增大了。同时在相同的时延限制下,随着中断率的增加,小区吞吐量增加,此时,信道条件差的用户减少,基站将大部分资源分配给信道条件好的用户,小区吞吐量增大。当中断率为5%,时延限制为1 s时,HS-DSCH吞吐量约为1.4 Mbps,当时延限制为2 s时,吞吐量约为1.63 Mbps,当时延限制增加到3 s时,吞吐量增加到1.8 Mbps。 在改进的M-LWDF算法下的小区吞吐量和中断率的关系如图3所示。同图2一样,吞吐量的提升会引起中断率的增加。与图2相比,对于相同吞吐量改进后的算法中断率上升了,在相同时延限制下,M-LWDF算法HS-DSCH吞吐量明显比改进版本算法吞吐量大,因为算法的目的是增加用户之间的公平性,这样信道条件差的用户被调度的机会增多,把相同的资源分配信道条件差的用户,必然会导致小区吞吐量的下降。 4 结束语 文中对M-LWDF算法的改进,提高了信道条件差的用户的调度优先级,防止这些用户在系统中被丢弃,使这些用户得到服务。但是此算法降低了小区的吞吐量。综上所述,改进后的算法是以小区吞吐量为代价,提高用户的公平性。因此对于流业务用户来说,很难对信道条件差的用户分配更高的优先级,以免消耗大量的物理资源[6]。 参考文献 [1]彭木根,王文博.3G无线资源管理和网络规划优化[M].北京:人民邮电出版社,2006. [2]ANDREWS M,KUMARAN K.CDMA Data QoS Scheduling on the Forward Link with Variable Channel Conditions[R].Bell Labs Technical Memo No.10009626000404-05TM,2000:1-45. [3]SHAKKOTTAI S,STOLYAR AL.Scheduling Algorithms for a Mixture of Real-time and Non-real-time Data in HDR[R].Proc.of17th International Teletraffic Congress,(ITC-17),2001:793-804. [4]KIMD H,SU H,LEE D W.Packet Scheduling Algorithmfor NRTService in Wireless Systemsupporting Integrated Services of RT and NRT applications[C].Communications and Information Technologies,2007:500-504. [5]BADER A M,HASSANEIN H.Packet Scheduling in3.5G High-speed Downlink Packet Access Networks:Breadth and Depth[J].Network,IEEE,2007,21(1):41-46.分组调度算法 篇4
分组调度算法 篇5
分组调度算法 篇6
分组调度算法 篇7
分组调度算法 篇8