（通信与信息系统专业论文）基于广义共享机制gps下的分组调度算法研究与分析.pdf

南京邮电大学硕十研究生学位论文 摘要 摘要 随着无线网络的发展，移动通信用户数和i n t e m e t 用户数急剧增加，人们期望新一代移 动通信系统不仅具有更大的容量，还要支持移动多媒体业务，除了提供话音业务外，还支 持低高速数据、图像等非话音业务的传输。不同业务有不同的服务质量( q o s ) 要求，如对 时延、分组丢失率、数据速率的要求不同。正交频分复用( o f d m ) 技术作为一种无线环境 下的高速传输技术，具有良好的抗多径信道干扰能力，因此本文主要研究基于o f d m 技术 的固定宽带无线接入系统中的多业务分组调度算法。 论文首先概述了有线和无线网络下的分组调度算法，以及各自的优缺点，并在接下来 分析了加权r o u n d - r o b i n ( w r r ) ，最大载干比( m a xc r ) 以及基于g p s 机制下的比例公平调度 ( q p f ) 三种经典的分组调度算法在仿真系统中的实现流程，重点分析了q p f 算法的性能 及存在的问题。接着利用o p n e t 软件对这三种算法分别应用到根据q o s 划分的四类业务性 能进行了仿真比较，并得出基于g p s 机制下的比例公平算法具有很大优势的结论。在此基 础上，一方面对有线网络比例公平算法中的算法的改进，并在理论上证明了改进过的算法 可以应用到无线动态服务链路，同时也具有w f 2 q h 优秀的性能；另一方面，根据跨层体系 的思想，引入物理层的链路状态，将缓存管理算法从g p s 模型中的进缓存队列管理策略中 剥离出来，并与分组调度算法结合起来。在g p s 的整体模型下通过选取简单常用的尾丢弃 算法与分组调度算法进行联合仿真，从结果可以看到该方案可以有效避免或减缓网络拥塞 现象。 南京邮电大学硕士研究生学位论文 a b s t r a c t a b s t r a c t w i t ht h ed e v e l o p m e n to fm o b i l ec o m m u n i c a t i o n s ，m o b i l eu s e r sa n di n t e m e tu s e r sa r e i n c r e a s i n gd r a m a t i c a l l y p e o p l ee x p e c tt h a tn e x tg e n e r a t i o nm o b i l ec o m m u n i c a t i o ns y s t e m sc a l l p r o v i d el a r g e rc a p a c i t ya n ds u p p o r tm o b i l em u l t i m e d i as e r v i c e s b e s i d e sp r o v i d i n gr e a l - t i m e s p e e c hs e r v i c e ，n e x tg e n e r a t i o nm o b i l ec o m m u n i c a t i o ns y s t e m sa r er e q u i r e dt os u p p o r to t h e r s e r v i c e ss u c ha sl o w h i g hr a t ed a t a , p i c t u r e se t c h e t e r o g e n e o u ss e i 、，i c e sh a v ed i f f e r e n tq u a l i t yo f s e r v i c e ( q o s ) r e q u i r e m e n t s ，f o re x a m p l e ，t h er e q u i r e m e n t so ft i m ed e l a y ，p a c k e tl o s sr a t e ，a n d t r a n s m i t t i n gr a t ef o rh e t e r o g e n e o u ss e r v i c e sa l ed i f f e r e n t o f d mt e c h n o l o g y ，a sah i g h - s p e e d t r a n s m i s s i o nt e c h n o l o g yf o rw i r e l e s se n v i r o n m e n t ，i sg o o da ta n t i - m u l t ip a t hf a d i n g s ot h et h e s i s m a i n l yp r o v i d e st h er e s u l t sf o rd i f f e r e n tp a c k e ts c h e d u l i n ga l g o r i t h m si nf i x e db r o a d b a n d w i r e l e s sa c c e s ss y s t e m s f i r s tc h a p t e ri n t r o d u c e st h es c h e d u l i n ga l g o r i t h m si nw i r e da n dw i r e l e s sn e t w o r k s ，i n c l u d i n gt h e i r h i s t o r i e s ，a d v a n t a g e sa n dd i s a d v a n t a g e s t h e nt h es e c o n dc h a p t e rp r o v i d e s3c l a s s i c a la l g o r i t h m s ，w e i g h t e d r o u n d - r o b i n ( w r r ) ，m a xc i ，a n dq p ff r o mq u a l c o m m t h ef o r m e rt w oa l g o r i t h m s 批s i m p l ya n a l y z e d a n dt h eq p fa l g o r i t h mi sd e t a i l e da n a l y z e d , s u c ha sp e r f o r m a n c e ，p r o b l e m sa n ds oo n t h e ni nt h et h i r d c h a p t e rs h o w st h es i m u l a t i o n so ft h ef o r m e rt h r e ea l g o r i t h m so no p n e t , a n ds h o w st h el a s ta l g o r i t h m p e r f o r m a n c eo f d e l a ya n dt h r o u g h p u ti sq u i t eg o o d ，a n di ti se a s yf o rc o n t r 0 1 i nt h ef o r t hc h a p t e r , w ep r e s e n ta s i m p l ea n de f f i c i e n ta l g o r i t h mf o re n a b l i n gw f 2 q + t os u p p o r tad y n a m i ct r a 伍cm i xt h r o u g hu s i n ga d y n a m i cf u n c t i o nr e f ( t ) a tl a s t , af a i rp a c k e td r o p p i n ga l g o r i t h mi sp r o p o s e di nt h ef i f t hc h a p t e rt od e c i d e d r o p p i n gp o l i c yi nw i r e l e s sn e t w o r k sw h e nc o n g e s t i o no c c i , i r s t h ea l g o r i t h mc o n s i d e r sb o t hc h a n n e lc o n d i t i o n a n df a i r n e s ss oa st oa c h i e v et r a d e o f fb e t w e e n t h r o u g h p u ta n df a i rs e r v i c e s n 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研 究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得南京邮电大学或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示了谢意。 研究生签名：叠】重复日期：型孽：垒：壹 f 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保 留本人所送交学位论文的复印件和电子文档，可以采用影印、缩印 或其它复制手段保存论文。本人电子文档的内容和纸质论文的内容 相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权南京邮电大学研究生部办理。 研究生签名：叠3 媛导师签名： 研究生签名：缝l ! 爱姿导师签名： 日期：学 车j 泉邮i 也人学硕f 研究生学位论文 第一幸绪论 1 1 本文研究的背景 第一章绪论 移动通信系统的目标是提高系统容量，同时保证高质量的通信，要实现这一目标，可 以通过选用高效的调制解调方式、编码方式( 包括信源和信道编码) 、多址方式、小区复用 方式等来实现。这些措施确定了系统中可供使用的物理信道和网络结构。所要管理的无线 资源包括频率资源，码资源，时隙资源。无线资源管理就是通过合理地动态分配这些无线 资源，有效地降低系统的干扰，提高系统的容量，保证通信链路的质量。近年来，无线移 动通信发展迅猛，无线移动用户数目急剧增长，在当前乃至将来的无线移动通信系统中须 为用户提供更多的数据、图像和视频等多媒体业务信息，这些均导致更多的无线资源将被 占用。但这一需求同无线资源的稀缺性构成矛盾，使得应该以怎样的方式来更加合理有效 地分配和利用有限的无线资源、支持尽量多的用户而又保证多种业务运用的服务质量等问 题成为一个重要的研究课题。这就是无线资源管理要解决的问题。无线资源管理( r m m ， r a d i or e s o u r c em a n a g e m e n t ) 负责空中接口资源的利用，保证移动用户的q o s 要求，维持 系统预规划的覆盖区。图1 1 给出了位于基站中的无线资源管理算法的基本模型，资源估 计器( r e s o u r c ee s t i m a t o r ) 控制着整个无线资源管理算法的实现。接纳控锖t ( a d m i s s i o nc o n t r 0 1 ) 裁决用户连接请求是否能被接纳。对于电路交换类型业务，若被接纳则经功率控制后就可 以直接发送出去。对于分组交换类型业务，若被接纳则根据其业务类型送到相应的队列中； 而后，队列调度器进行发送调度。若采用的是时间调度器( t i m es c h e d u l e r ) ，则是进行时隙 的分配。功率及速率调度器( p o w e ra n dr a t es c h e d u l e r ) 完成对发射功率分配及发送速率的指 定。无线资源管理主要包含有功率控制、接纳控制、越区切换考虑及分组调度等方面。切 换控制负责处理用户的移动性。当移动用户从一个小区进入另一个小区时，必然发生切换。 切换控制就是运用一定的策略，保证用户越区切换或系统间切换时通话的连续性，并且使 通信质量达到预定的q o s 要求。功率控制使空中接口的干扰电平维持最小，保证移动用 户的q o s 要求。负荷控制的目的是，以目标方式在给定的限制条件范围内维持网络无线 资源的使用。分组调度是使各分组用户合理地使用系统的可用资源，为各个用户分配数据 速率。接纳控制是在有限系统容量的基础上，以不牺牲已有连接的服务质量为代价，尽可 南京【| j 【；l 也人学硕if j f 究生学位论文第一争绪论 能多地对新到达的( 新发起的或以切换方式到达的) 连接请求予以接纳的决策问题。 搽祥 状态 资源估计器 i ； j 业分矢型f浩出m莯藔 ；粤些篓，l 类型 - 务类型n 请求 业型n 请求i - 业务 ； 非实时业务 ； 型n + l 请求 厶 + i 请求i 一 曩 i 、 ：类型n + m 请求l + m 请求i 度器 一一：m + m m , j 一一一- - ： i 无线资源管理系统框图 1 1 有线网络中的调度算法 实际路由器中获得应用的调度算法是先进先, m , ( f i r s ti nf i s to u ，f i f o ) 算法。 这度方法完全依据分组的到达次序进行输出。如果某个流在一段时间内发生业务突 发达的分组数目较多，那么其他的流就无法得到正常的服务，因此，fifo无法保证 各之间的公平性，各个流之间的独立性也不好。 5 年左右，h a h n e 提出了加权r n o u dr o i n ( w e i g h t e dr n u dr o i n ，w r r ) 算法【l 】， 这法摒弃了这种依靠分组到达次序的排队方法，通过为各个业务流合理地分配权值来 控们获得发送的机会，公平性有所增强，但是，在处理变长分组的时候，效果仍然不理 代，基于分组传输综合业务的实际需求带动了对于调度算法的研究。d e m e r s 2 1 ， pekh和galager3】【41等人先后研究了基于流体流的并行服务模型，即通用处理器共享 (neralized p r c e s s o rs h r i n g ，g p s ) ，在这种模型中，业务流被看成是可以无限分割的流 体服务器可以同时为多个业务流同时服务，服务的尺度也可以无限小。因此，gps 模以满足流之间的独立性，并可以实现对不同时延带宽要求的业务流的区分服务，为2 p 南京邮e 也人学坝j 研究生化论文第。荦绪论 调度算法的后期研究提供了理论参考。 g p s 模型是一个理想化的公平模型，在实际系统中不可能实现。这是因为实际系统 中，输出链路在同一时刻只能服务一个分组，而且只有当传送完一个分组之后才能够服务 其他的分组。也就是说，实际系统中，调度的“粒度”要比g p s 模型粗得多。根据g p s 模型，p a r e k b 和g a l a g e r 提出了基于g p s 分组化近似的加权公平排队( w e i g h t e df a i r q u e u e i n g ，w f q ) 调度算法f 3 】【4 1 。这是第一个真下意义上的公平调度算法，可以提供有界的 时延保证。w f q 在路由器的设计中获得了实际应用。但是在处理高速分组调度时，w f q 显得复杂度相对较高。 g p s 模型虽然简单，但也有一定的局限性。在g p s 模型和其近似化算法中，对业务 的需求只使用速率一个参数来进行描述，这就使得时延与带宽的分配互相耦合在一起。也 就是说，如果需要低时延，那就必需高带宽。因此这对于低时延、低带宽的业务无法获得 高的资源利用率。因此，对于时延敏感性业务，需要有其他的算法进行q o s 的保证。 1 1 2 无线网络中的调度算法 无线调度算法的研究要稍微晚一些。1 9 8 9 年，a d e m e r s 等人最早将无线网络中区域 性和突发错误无线调度算法的研究要稍微晚一些。1 9 8 9 年，a d e m e r s 等人最早将无线网 络中区域性和突发错误特性考虑进调度算法，提出了依靠链路状态的分组调度算法 ( c h a n n e ls t a t ed e p e n d e n t p a c k e ts c h e d u l i n g ，c s d p s ) 【2 】o1 9 9 7 年，l u 和b h a r g h a v a 等人以 w f q 为参照，提出了蜂窝结构无线网络中的理想公平调度算法( i d e a l i z e dw i r e l e s sf a i r q u e u e i n g ，i w f q 【5 1 。在其论文中，作者指出无线链路突发错误会导致有线网络发展起来 ， 的调度算法在无线环境中应用时的失效。因为有些处于积压状态的业务流( 设为- ) 即使根 据w f q 等算法的调度结果获得了发送机会也会出于链路失效而将发送机会转让给其他的 业务流( 设为，z ) ，从而导致公平性无法保证。为了保证公平性，就需要对发生链路突发错 误的业务流在其恢复正常传输时对之进行补偿。i w f q 中的补偿模型是隐含的，算法保持 了服务的顺序标记，可以记录滞后流滞后的服务量。这样，滞后流一旦检测到链路恢复正 常，就会马上启动发送过程，并将滞后的业务量弥补过来。 针对i w f q 的缺点和在无线网络上传输时延敏感型业务的需求，l u 和b h a r g h a v a 等 人又提出一种新的算法无线公平服务( w i r e l e s sf a i rs e r v i c e ，w f s ) 算法【s 1 。w f s 将理想公 平、信道状态及补偿与惩罚相结合，实现了时延和带宽的解耦，同时实现了长时公平性和 短时公平性的保证，此外，w f s 算法具有较好的隔离性，实现了超前服务量的良好降级 3 i ；柯京邮! n 人学形! t 彬f 究生学位论义 第一章绪论 性能。 1 1 3 无线网络的特点对调度机制的影响 未来的无线网络必须能够提供高速数据通信的能力，这样才可以用于多媒体业务。但 由于无线网提供给用户的带宽受到射频带宽资源的限制，只有通过更加有效的方法进行频 率利用，才能实现上述目标。在提供给用户更多服务内容的同时，还必须保证用户的服务 质量。在有线网络中，资源分配方法和分组调度算法对提供服务质量起到了重要的保障。 调度算法包括加权轮循( w e i g h t e dr o u n dr o b i n ，w r r ) 等基于帧结构的算法，基于最大载 干比的m a xc i 算法以及与广义处理器共享( g e n e r a l i z e dp r o c e s s o rs h a r i n g ，g p s ) 相关的公 平排队算法。公平排队算法可以保证各个连接的基本带宽以及对时延的要求。目前调度算 法的研究主要集中在公平排队算法上。需要提出注意的是，无线网络同有线网络相比具有 很大的特殊性，所以要将有线网络中的分组调度算法有效地引入无线网络，就必需充分的 考虑无线网络的特殊性。这些特殊性主要有下面列举的这些： 高的误码率和突发错误。 无线链路容量与位置相关，与时间相关。 有限的带宽。 用户的移动性。 功率受限。 基于无线网络以上的一些特殊性及分组调度本身的目标，我们在设无线网络中分组调 度算法的时候必需考虑上述特殊性，下面将对一些主要的问题进行阐述。 1 ) 无线链路的可变性 无线网络和有线网络最大的不同就是传输链路的可变性。依靠高质量的传输媒质，有 线网络中的数据包有非常低的误码率。然而由于干扰、衰减等因素，无线信道的质量有很 高的可变性。在某些高突发错误的状态下，一个无线链路有可能恶化到一个数据包都不能 成功的传送。除了时间相关的问题，无线链路的质量还是位置相关的。在同一时间，基站 可和几个不同的移动台进行通信。由于不同的位置，一些移动台可以和基站进行无错的通 信，然而其它有一些可能根本不能进行通信。此外，移动台的移动性增加了链路的可变性。 这样的链路可变性要求设计的调度算法必需有动态的机制来处理这些与时间和位置有关 的信道质量变化。 2 ) 公平性 在有线网络中，调度的公平性通常是由分配一个确定的服务速率给一个具体的流加以 4 南泉邮 u 人字坝i 挪f 宅掌位论义笫一审结论 保证的，而且调度算法阻止不同的流互相干扰。因为有线媒质可以考虑是无错的，所以对 于一个流来说。分配的服务速率就是实际的接受速率。然而公平性问题在无线网络调度中 更加复杂一些。有可能按照一定的没有考虑链路状态的服务策略，对某个数据包加以调度， 在一定的无线链路上加以发送，然而这个无线链路实际上处于错误状态，如果这个数据包 发送了，接收方不能接收，而且浪费了传输资源。考虑到这样的问题，推迟这个数据包的 发送到该链路从错误状态中恢复过来为止是一个合理的选择。因此这个受影响的流暂时损 失了分配给它的带宽。为了确保公平性，当链路状态恢复过来后，需要补偿这个受影响的 流的损失。但是如何补偿这个损失不是一个容易的问题。此外，公平性的粒度例如短期公 平性和长期公平性是影响调度策略的另一个因素。 3 ) 服务质量 宽带无线网将为不同类型的业务提供服务，对这些不同类型的业务需要提供不同的 q o s ( q u a l i t yo f s e r v i c e ，服务质量) 。因此，在系统中必需保证不同业务获取了不同的q o s 支持。为了达到这个目标，相应的机制必需集成到调度算法里面。在不同的调度模型中， 保证q o s 的机制也是不一样的。当然，保证一个信道质量经常存在问题的链路上的业务 的q o s 是有一定难度的。然而只要物理信道质量恶化不超出一定的门限，对于在其上的 业务的q o s 是应该加以保证的。 4 ) 数据吞吐量和信道利用率 对于无线网络来说最重要的资源就是带宽。一个有效的无线分组调度算法必需尽量的 减少在处于错误状态的链路上进行的无效传输，同时必需尽量增加有效的服务分配和无线 信道的带宽利用率。 5 ) 功率限制和简单性 在蜂窝无线网中，分组调度算法主要是运行在基站上。基站用于计算的功率是不用加 以考虑的。然而对于移动台来说功率是受限的，所以一个好的分组调度算法应该使用最少 数量的控制信息，以减少移动台发送这些信息的功率开销。 除此之外，分组调度算法还必需满足简单的原则，不能过于复杂，这样才能高速的调 度实时的媒体业务，满足其严格的时延要求。 1 2 本文的主要工作和结构安排 在参阅了大量中英文文献的基础上，本文对无线资源管理中的分组调度进行了研究分 析，采用o p n e t 仿真软件构建模型基于应用层所规定的四类业务对三类分组调度方案进行 苗j j j 眦电人学坝1 自j i 5 r 2 生学位论文第一节绪论 了仿真比较。之后对从有线环境中基于g p s 机制下的w f 2 q + 算法进行改进，并证明引入 了动态函数r e f ( t ) 的w f 2 q + 改进算法可以成功应用于动态的服务流传输链路。但是实际 中，无线链路不仅要考虑到随时间和终端位置变化的容量，还需考虑用户移动性带来的传 输链路的易变性，这就意味着需要采用跨层体系架构思想。最后根据这一思想将分组调度 算法与缓存管理中的分组丢弃算法相结合，有效的避免和缓解了队列数据包的大量堆积而 造成的网络拥塞现象。 本文的章节安排如下： 第一章绪论简单介绍无线资源管理的背景环境，针对其中的分组调度策略进行阐 述，并强调了其在实际应用过程需要注意的问题。 第二章介绍了三类分组调度算法的基本原理以及发展进程。 第三章基于上层协议所划分的四种不同业务类型，使用o p n e t 软件分别对三类分组 调度算法进行了仿真，从几个指标上比较出各类业务较为合适的分组调度算法。 第四章重点研究了g p s 机制模型下的分组调度算法，通过对w f 2 q + 算法的改进， 提出引入动态函数i 冱f ( t ) 改进算法w f 2 q + 使得可以应用于动态的服务流传输链路。在保 证其原有特性的基础上，使其可以应用于动态的服务流传输链路上。 第五章从跨层体系来构架模型研究分组调度算法，并结合进入队列之前的分组丢弃 算法，可以从仿真出看出跨层思想的优越性能。 第六章对全文工作的总结和展望。 6 第一事绛典的j ，组驯腹算法确介 第二章经典的分组调度算法简介 2 1 加权r o u n d r o b i n 算法 2 1 1w r r 算法描述与规则 r o u n d r o b i n 算法是一种最简单、最公平的调度算法。加权r o u n dr o b i n 算法( w r r ) t 1 】 在r r 算法的基础上作了改进，按照权重公平的分配整个资源。在我们的仿真中，w r r 就是给每个不同的连接以权重，从而按照权重大小分配带宽。比如有两个连接a 和b ， w e i g h g 和w e i g h t 8 的权重分别是0 6 和0 4 。时隙的总数为1 0 ，那么连接a 和连接b 的时 隙分别为6 和4 。所以w r r 这个算法的核心问题就是权重的选取。在本算法中，我们选 取了某个连接的最小预留业务带宽占所有连接的最小预留业务带宽比重作为权重。 在本算法中，我们选择业务的最小预留数据速率作为权值计算的参考，根据这个参数 以及该业务采用的调制编码方式，计算出该链接本帧需要的总调制符号数，再用调制符号 数占所有连接需要的总的调制符号数的比重作为权值。这种情况下，不论信道好坏，也无 论采用什么调制编码方式，只要它们的最小预留数据速率相同，每个连接能传的净比特数 就相等。假设宽带无线接入( b r o a d b a n dw i r e l e s sa c c e s s ，b w a ) 系统中现有n 个连接，连 接i 上的最小预留数据速率为r ，i = l ，n ，帧长为t ，一帧内所有用来分配的总调制符号 数为尽删，则w r r 算法调度规则描述如下： 根据连接i 所在s s 的第t 个时隙的信道情况，计算出连接i 上的最小预留业务带宽 茸( ，) 。假设连接i 采用的调制编码方式为6 4 q a m ，编码速率为3 4 ，则 耳( ，) = r 奎t + 6 毒3 4 ( 2 1 ) 计算连接i 上的权重只( ，) ： 讹) ：乒盟 耳( f ) h i ( 2 2 ) 根据连接i 上的权重p ( f ) ，按照式( 2 - 3 ) 计算该连接i 上应分配的调制符号带宽e ( r ) ， 7 萄京i | l i ：l 【1 人学坝i 埘7 生学位沦支第：带绛典的分组洲度箅法简，r 给每个连接分配带宽： e ( ，) = p ( f ) 幸既旧， ( 2 3 ) 2 1 2 w r r 算法实现与简单分析 由于在仿真系统中，涉及的因素较多，算法实现较为复杂，限于篇幅，本文仅以联合 加权调度算法为例，详细描述算法的实现流程。上行w r r 调度算法的简单流程图，如图 2 1 。 初始化帧资源 上 分配一定的带宽给周期测距信令 土 根据最小的预留数据速率计算各连接上的权重 上 根据权重计算每条连接上分配到的o f d m 符号数 1 l 按照各自分得的带宽取相应比特来建立m a c p d u 上 调度结束 图2 1w r r 算法流程图 需要说明的是，实际实现的o f d m 上行调度算法分配带宽的颗粒为调制符号，分配结 果的最小单位为o f d m 符号，也就是说，尽管w r r 算法按权值平均的是比特数，但是实际 分配的是调制符号数，而写进u l m a p 的分配结果是占用多少个o f d m 符号。由于不考虑子 载波分配，上行帧中一个o f d m 符号只能分配给一个s s ，因此即便该s s 只占用几个比特的 带宽，也必须分配一个o f d m 符号。所以在调度过程中，一方面要考虑一个整o f d m 符号， 另一方面分配每个连接时分配的是净比特带宽，因此我们折衷选择了调制符号作为带宽分 配单位。因为是基于s s 的带宽分配( g r a n tp e rs ，g p s s ) 系统，只要将分配给某个5 所有连 接上的调制符号数求和后折算得到的上取整o f d m 符号数，就是该s s 获得的带宽。选择调 制符号作为分配带宽最小颗粒的另一个原因是为了在实现汇聚的情况下准确计算每个连 接的突发起始时间。 8 南京i 也人? 坝f j 研究生学位论文 第一二节绐典的分组涮度箅法简介 w r r 算法在系统承载量很轻时，服务流每次能获得大于自身的平均需求的带宽，因此 所有服务流都能获得很好的性能。但是当系统承载量越来越重，带宽不再足够，所有用户 的性能都会急剧下降，并且系统会较早地呈现饱和状态。 2 2 最大载干比m a xc i 算法 2 2 1m a xc i 算法描述及规则 最大载干比算法( m a xc i ) 7 1 就是根据最大载干比来寻求服务对象。采用的带宽数量分 配方式是最大努力式的，就是说用户请求多少就给予服务多少，如果剩余带宽不够，则把 剩余带宽都给该用户。 假设系统中现有n 个连接，连接i 上第t 帧的载干比为c i r ，( t ) ，i = l ，n ，贝, l j m a xc i 以 算法调度规则描述如下： 选择所有连接中载干比c i r ，( t ) 最大的用户进行服务，并满足该连接的请求带宽。如果 请求带宽为零，则选择最大载干比连接进行服务。如果该连接的请求带宽大于本帧剩余 带宽，则将剩余带宽都给该连接，否则选择此最大载干比用户继续服务，直到带宽分配完 或者所有用户己经全部得到满足。 2 2 2m a xc i 算法实现与分析 如上所述，这里也只给出了上行m a xc i 调度算法的简单流程图，如下图所示。当调度 开始时，首先满足周期测距信令的带宽要求，然后寻找获得最大信噪比的s s 站，如果没有 连接有业务要传i 则跳过，若有则尽最大努力来满足其s s 站上所有连接的需求。如果此时 带宽还有剩余，则寻找第二大载干比的s s 站，若有业务则尽最大努力服务该用户站上所有 连接，依次下去，直到一帧资源分配完毕。b s 将每个s s 的上行信道信噪比记录下来，定时 通过测距信令来更新，每0 3 s 更新一次。 9 南糸i | | ； 乜人。硕 究生学位论文第二擎绎典的分组洲度算法确介 初始化帧资源 上 分配一定的带宽给周期测距信令 寻找拥有最大信噪比的用户站 上 找出该用户站上所有待传数据的连接，按照业务优先级及q o s 要 求依次进行最大努力的服务 土 如有资源剩余，寻找下一个次最大信噪比的用户站 上 i 找出该用户站上所有待传数据的连接，按照业务优先级及q 。s 要 求依次进行最大努力的服务 上 依次下去，直至资源耗尽或者所有连接服务完 图2 2m a xc i 算法流程图 理论上m a xc i i l 达到最大带宽利用率，获得最高的系统吞吐量。这里的最大努力是指： 如果是u g s 业务，则定期分配固定带宽；如果是r t p s 、n r t p s 或者b e 业务则根据请求的多少 最大程度的予以满足，如果本帧资源不够就将所有资源都给它，如果本帧资源足够，则按 照请求的多少来给予。另外，本次仿真采用信噪比来代替载干比，相当于考虑了载波功率、 干扰功率以外影响信道情况的其他因素。 b w a 系统下的m a xc i 算法并不能获得最大的系统吞吐量。m a xc i 的最大吞吐量性能 建立在“f u l lb u f f e r 业务的基础上。而在b w a 系统中，如果采用实时轮询或非实时轮询的 服务方式，b s 每隔一段时间给s s 一次带宽请求的机会，而在请求间隔内根据各调度算法的 规则，选择其间某几帧中的带宽来满足其请求的服务。这样使得业务不再是流畅的，就算 是“f u l lb u f f e r 型的业务，b s 也只能每隔一个时段获悉s s 上总的请求带宽。由于算法每找 到一个最大信噪比的需要被服务的用户，就最大努力地予以满足，因此一般一帧仅服务一 到两个连接，但是几帧就能把轮询期间积存的业务传送完。正因为如此，算法在服务用户 时，可选择服务的用户范围也会随着下一次轮询的临近越来越小。最后，可能不得不用最 棒的调制方式来服务剩余有需求的用户，而这个用户可能在这次轮询间隔内曾经有段时间 1 0 堕墨! ! ! 坠叁兰丝! 型! ! ! 竺兰丝堕苎笙= 主丝壅堕坌丝塑壁望姿堕坌 信道较好，但是却不是信噪比最大的用户。也就是说m a xc i 在这段时间内的服务顺序并不 是最优的，需要的排序方式来获得更大的吞吐量性能。这样的业务模型和带宽请求授予机 制导致- m a xc i 算法并不能获得最大的系统吞吐量，这点在后文的仿真结果中体现出来。 2 3 基于g p s 机制模型下的公平队列算法 2 3 1g p s 与比例公平的定义 公平队列算法是一类基于派生于有线环境下的广义处理器共享( g e n e r a l i z e d p r o c e s s o r s h a r i n g ，g p s ) 的算法。在这种模型中，业务流可以看成是无限分割的流体，而服务器可以 同时为多个业务流同时服务，服务的尺度也可以无限小。因此，g p s 模型可以满足流之间 的独立性，并可以实现对不同时延带宽要求的业务流的区分服务，为调度算法的后期研究 提供了理论参考。 g p s 模型是一个理想化的公平模型，在实际系统中不可能实现。这是因为实际系统中， 输出链路在同一时刻只能服务一个分组，而且只有当传送完一个分组之后才能够服务其他 的分组。也就是说，实际系统中，调度的“粒度 要比g p s 模型粗得多。根据g p s 模型， p a r e k b 和g a l a g e r 提出了基于g p s 分组化近似的加权公平排队( w e i g h t e df a i rq u e u e i n g ，w f q ) 调度算法【3 】【4 】。这是第一个真正意义上的公平调度算法，可以提供有界的时延保证 k e l l y 在文献【1 5 】中首次给出了比例公平的定义：称在一定的容量限制范围内对流i 的速 率分配u ，i = l ，m ，是比例会平的，如果这种分配方式能够满足：对于任意其他的分配 肘rrrr 方式矿，所有流的比例变更之和有竺三生o 成立。k e l l y 发现，比例公平的概念和对 i = 1 u f 数形式的效用函数有着密切的关系。之后在m a s s o u l i e 等人的论文，则直接使用对数形式的 效用函数定义了比例公平l z j ： m 如果对流i 的速率分配u ，i = 1 ，m ，能够使得总的效用函数l o g u ，最大，那么就称 这种速率分配是比例公平的。 ， 比例公平的定义事实上反映的是长期的绝对公平，当所有流独立同分布，相等时使 得效用函数最大。， 南京批f u 人学坝 j 研究生掌位论义 第一辛绎典的分纠l 测度算法简介 2 3 2q p f 比例公平算法规则 q u a l c o m m 公司的j a l a l i 等人在研究h d r 系统时，将比例公平调度思想引入到无线环境 中，提出了比例公平算法，将的物理意义从费率转化为每个用户在链路自适应技术下获 得的实际链路容量l b 】，下文称为q p f 算法。 在时隙化的h d r 系统中，时隙是分配给用户进行数据传输的最小单位。信道是一个时 变信道，位置移动、多径衰落以及阴影效应都有可能是造成这种时变特性的因素。假i 发h d r 系统中现有n 个用户，用户i 在第t 个时隙估计出的平均速率为足( f ) ，而在第t 个时隙根据信 道情况能获得的瞬时速率为d r c , ( t ) ，i - - 1 ，n 。贝, i j q p f 调度算法规则描述如下： 1 ) 计算在第价时隙半比值，月艮务该比值最大的用户。如果两个用户的半 一样大，则随机选择一个进行服务；如果里值最大的用户没有业务需要传送，则服务 次最大值用户。 2 ) 用户i 在t + l 时刻的平均速率用式( 2 _ 4 ) 进行更新： r ) _ ( 1 一 w f ) + 丢宰d r c , ( r ) ( 2 4 ) 其中，i 代表用于统计平均速率的时间窗，丢也称为遗忘因子，是q - p f 算法中的一个 很重要的参量。如果一个用户没有在本时隙得到服务，则令用来更新r p + 1 ) 的d r c , ( t ) 为 0 。无论用户是否有数据发送，足( f ) 都应该逐时隙更新。 j a l a l i 指出如果其他的算法能够使某个特定用户的容量提高x ，那么，在该算法下，所 有其他用户所下降的容量之和的比例将超过x ，即，从比例公平的意义上说，q p f 算法 是最优的。文献【1 6 】指出如果所有用户的快衰落特性独立同分布，则q p f 算法调度的最终结 果是使所有用户分配到的功率和时隙资源相同，并且足( f ) 与瞬时的e s n o 成正比。 文献【6 】中给出 q u a l c o m m 公司的q f p i 肩 度算法规则与比例公平定义之间的等价关系， m 即能够证明这种调度规则能够满足各个流长时平均速率的效用函数之和l o g u ，最大。证 石i 明的关键假设有两点：一是逐时隙分配带宽，每个时隙仅分给某一个用户；二是平均速率的 1 2 南京l 懈电入学彤! 扩究生学位论义第一一辛绛典的分组渊度算法简介 计算，平均速率应为历史上总的平均吞吐量 2 3 3q p f 算法的相关讨论 文献【8 1 从以下几方面对q f p 算法做了进步讨论： 1 ) 平均速率更新机制对于比例公平性的影响 q p f 算法在对平均速率逐时隙更新时，没有采用从起始时间算起逐时隙更新的平均速 率，而是采用式( 3 4 ) 中基于时间窗i 的方法来更新，这必然与理论值存在一定的误差，而 且t 越小，误差越大。这对q p f 算法的比例公平性将产生不利影响。 2 ) 饥饿避免机制 如果一个业务流在调度算法的控制下，长期得不到正常的服务，称此业务流处于饥饿 状态。例如m a xc i 算法中，某些信道条件不太好的业务流会长期处于饥饿状态。显然，饥 饿状态的出现对于保证业务的q o s 是不利的。根据式( 2 4 ) 进行调度有可能出现一些流的饥 饿现象，由于算法总是试图在用户信道条件达到最好的时候对它进行服务，因此，当一个 业务流的质量突然变化，或者用户沿着背离基站的方向运动时，将有可能在较长时间内无 法得到服务。 q p f 算法试图通过引入基于f c 的平均速率更新来实现饥饿避免。文献【6 1 提出，如果信 道变差的时间超过f c ，算法能够保证用户会得到服务。较大的乞能够使算法对于用户信道 条件的选择有更多的自由度，有利于提高系统的容量，但是它同时意味着用户数据包可能 由于“饥饿”，而被延迟更长的时间。所以实际应用中要对这两个方面折衷考虑。 文献【明分析了这种饥饿避免机制的不足之处：( 1 ) 利用式( 2 4 ) 计算平均速率可能引入新一类 的“饥饿”现象，即当新用户加入系统，依据所得到的平均速率较高远小于其他用户的平 均速率，从而使q p f 更倾向于对新用户的服务，造成其他用户的“饥饿”；( 2 ) 如果某个用户i 在时刻t 信道条件变差，那么它何时再度接受到服务，不仅与t 有关，而且与所有用户在t 时刻的速率均值的分布和这些用户的信道状态分布都有关系，也就是说，随着参数分布的 不同，用户有可能不需要经历心那么长时间就可以得到服务，也有可能既是饥饿时间超过 了t ，也仍然得不到服务；( 3 ) 即使q p f 算法能够保证用户的“饥饿”时间不超过，c ，通过基于 的平均速率更新算法来实现“饥饿”避免也不是最佳的，因为不同用户的不同业务对于“饥 饿”的容忍能力不同，为照顾容忍能力差的用户而取最小的f c 值，代价是总的系统容量的下 1 3 南京 | | j u 人学坝l j 埘了生。学位论正第二节经典的分组渊度算法简介 降。 3 ) 非时延保证胜调度算法 对于实时业务，j z l ：i v o l p 业务，需要引进其他的机制才能够很好地支持。 2 4 本章小结 公平队列算法是一类基于派生于有线环境下的广义处理器共享( g e n e r a l i z e dp r o c e s s o r s h a r i n g ，g p s ) 的算法。在第三章的仿真中可以看出，该类算法相比于w r r 算法和m a xc i 算法可以较好的保证各个链接的基本带宽以及对时延的要求。目前调度算法的研究主要集 中在公平排队算法上，而w f 2 9 + 是这类有线环境下算法中的佼佼者，在所有的可以提供 q o s 保证的p f q 调度算法具有最小的时延限制，最小的最坏公平指数，以及最佳的算法复 杂度。在第四章将通过引入动态函数r e f ( o 改进算法f c f 2 9 + 使得可以应用于动态的服务流 传输链路。 1 4 南京邮i 也人学坝i 研究牛学化论文第t 节j t 用十多种业务下的分鲺l 调度箅；上 第三章应用于多种业务下的分组调度算法 随着无线物理层技术的演进，按照q o s 需求不同规定了不同的优先级业务，在i e e e 8 0 2 1 6 e 系统中，就规定了u g s 、r t p s 、n r t p s 和b e 的四种调度业务。 其中增加的e r t p s 调度业务，这是一种综合u g s 和r t p s 效率的调度机制。对于 e r t p s ，基站将像在u g s 中一样以主动方式提供单播授权，从而节省了带宽请求的反应 时间，但不同于u g s 以固定大小分配的方式e r t p s 的资源分配是动态的，与r t p s 业务 模式类似。考虑到2 种调度业务调度算法的核心没有本质区别，所以不需要区别对待。 瞬时载干比( c i r ) 的值不易确定，与m s s 的发射功率、其他基站的总发射功率、路 径损耗等密切相关。如果采用基于传统理论的调度算法，具有更高c i r 和更大传输速率 的m