（通信与信息系统专业论文）hsdpa系统分组调度算法研究(1).pdf

h s d p a 系统分组调度算法研究 a b s t r a c t h s d p a ，t h en e wf e t u r ci n3 g p pr e l e a s e5 ，p l a y sak e ym l ei nt h ee v 0 1 u t i o n t o w a r db 3 g w c d m aa r c h i t e c t l l r ei sr e t a i n e di nh s d p a ，w h i l es o m ec h a n g e sa r e m a d es u c h 船s h a r e dp h ”i c a lc h a n n e l s ，n e wl a y e rm a c h so nn o d e b ，c t c a m c ，h a r qa i l df a s tp a c k e ts c h e d u l i n g ( p s ) a l g o 删h s ，t 1 1 ei 衄o v a l i v et e c h n 0 1 0 9 y a i m i n ga th i g h e rt r a n s p o r t a t i o nr a t ea n ds y s t e mc a p a c i t y ，a r e 印p l i e dt oh s d p a s ”t e m h o w e v e r3 g p pd i dn o tm a k e o u ta i l yp ss p e c m c a t i o n sf o rh s d p a ，p s sa r c v 撕e db e _ c 、e e nm a n u f a c t i l r e r sw i 血o u ts t a n d a r d i z e dm o d e t h em o s tp o p u l e rp s r r ，p fa i l d m a ) 【c ia n d m e n e wa l g o r i t h m m - 啪fh a db e e np r o v e d t ob es h o r t o f s u p p o r t o ns 打e a m i n gm u l t i m e d i as e i c e s t h ea u 廿1 0 rc o n d u c t sf i l m l e rr e s e a r c ho nh s d p ap sd e s i g nm e l o d si n 廿1 i sp a p e l t h em a i ni d e a 扭p sm u s tu t i l i z et l l ea d v a l l t a g eo fh s d p ：at e c l l l l o l o g yt oa c h i e v e c o m p r e h e n s i v eb u tn o tp a r t i a lo fq o sg u a r a n t e e n l i sp a p e rs e tu p 1 em a m e m a t i c a l m o d e lf i o re a c hf 她t o rt h a tp o s s i b l yi m p a c to nq o sp e r f o n n a i l c ei nh s d p a o n e c o l b i n e dp sa l g o r i 她i sp r o p o s e d ，s h o w i n gag r c a tp e r f b 肌a i l c eo ne i t h e r m m u g h p u ta 1 1 dq o sm r o u g hs i m u l a t i o nr e s u l t s t h ea u 也o ra l s od o e st r e n d 锄l y s i sf o rp se v o l u t i o n ，s e l f _ a d 印t a t i o ns c h 锄ei s p m p o s e dt 0i m p m v et h em n c t i o na g m t y a c c u r a c ya 1 1 de n l a r g em es c o p eo ft 1 1 e a l g o r i t h ma p p l i c a t i o n t h i sp 印e r 柚a l y s e sh o wt oi n t m d u c es e l f _ a d a p t a t i o ns c h e m e s f o rt h m u 曲p u t ，r a t eg u a r a n t e ea 1 1 dm c sr c s o u r c ea 1 1 0 c a t i o ni nh s d p a s y s t e m a tm ee n do fm ep a p e r ，o n cc o m p o s i t i v er e s o u r c ec o n t r o lm o d e lf o rh s p d aw a s p r o p o s e da st h eg u i d a n c eo f h s d p a p sd e s i g n k e yw o r d s ：p a c k e ts c h e d u l i n g ( p s ) ，h s d p a ，q o s ，t h r o u g h p u t ，d e l a y ，r c s o u r c e a 】o c a t i o n 北京交通大学电子信息工程学院硕士论文 3 h s d p a 系统分组调度算法研究 摘要 h s d p a 是w c d m a 系统向b 3 g 演进的增强型技术，出现于3 g p p 的r 5 版 本，它在不改变原有w c d m a 网络结构的基础上新增了h s d s c h 共享物理信 道以及n o d e b 上的m a c l l s 子层，并采用了a m c ，h a r q 等新技术大大提高了 w c d m a 系统下行链路的传输速率和容量。m a c - h s 层上的快速调度算法作为 h s d p a 的一项关键技术，决定了系统分组数据传输的性能而且影响着整个系统 的容量和效率。由于3 g p p 并没有对h s d p a 调度算法作出具体的规定，各个 设备厂商选择的调度算法均不一致，原有的常用调度算法应用在h s d p a 上没能 显示h s d p a 系统的技术优势，少数新提出的算法对q o s 的改进也不够全面。 针对当前h s d p a 调度算法应用的现状，笔者认为只有充分结合h s d p a 技 术优势的调度算法才能在h s d p a 系统上体现优秀的性能。根据这个思路，笔者 首先提出了h s d p a 系统上各种调度因素的数学模型，全面而准确的衡量了吞吐 量、q o s 保证，尤其是h s d p a 特有的m c s 资源分配因素对调度优先级的影响： 进而利用这些数学模型设计了适用于h s d p a 系统的新算法一组合型调度算 法。仿真结果显示了此算法在吞吐量、用户q o s 保证方面优于其它常用算法， 确实发挥出h s d p a 技术的卓越性能。 结合无线调度算法的发展趋势，本文还提出了为h s d p a 算法增加自适应控 制机制的设想，并给出了h s d p a 系统上吞吐量、q o s 以及m c s 资源分配的自 适应控制机制的设计方案。 文章最后提出了h s d p a 调度系统综合模型，融合了组合型调度算法和自适 应控制机制的思想，这个模型可以成为h s d p a 系统调度算法设计的依据。 关键词：调度算法，h s d p a ，q o s ，吞吐量，时延，资源分配 一一一北京交通大学电子信息工程学院硕士论文 一一一一一一一一h s d p a 系统分组调度算法研究 第一章h s d p a 关键技术 快速无线分组调度算法是h s d p a 关键技术之一，它的设计不是孤立的而 是与h s d p a 系统整体紧密相关的，本文- 丌篇首先对h s d p a 关键技术进行归纳， 有助于对h s d p a 系统全面深入的认识。 支持高速移动分组数据业务传输是3 g 系统重要的特征之一。目前w c d m a r 9 9 版本只能提供3 8 4 k b i t s 的数据速率，无法满足视频，流媒体和下载等宽带 数据业务的需求，h s d p ：a ( h i 曲s p e e d d o w n l i n kp a c k a g ea c c e s s ，高速下行分组 接入) 技术的引入，不仅可以支持高速下行数据服务，而且可以满足上述业务对 带宽和系统时延的要求，为w c d m a 实现更高传输速率和更大吞吐量提供了一 条平滑演进途径。h s d p a 技术是对w c d m a 无线接入部分的增强与演进，系统 结构与r 9 9 保持不变，仅仅在d eb 增加了一个新的m a c i l s 子层和专门的 物理信道，并且可以采用h s d p a 和r 9 9 共享载波的组网方式，有利于系统的灵 活部署，使移动用户可以享受1 4 4 m b i 讹的峰值下行传输速率，同时保证系统的 前向兼容，提升了高速流媒体业务承载能力，为w c d m a 的发展提供了强大的 支撑。 h s d p a 系统的设计放弃了w c d m a 采用的软切换、可变扩频因子技术， 定义非常小的数据传输时隙2 m s ，采用快速链路自适应技术( 自适应调制编码 舢订c 多码传输) 、快速混合重传技术( h a r q ) 、快速集中调度技术( f p s ) 等， 这些关键技术，3 g p pw c d m ar 5 规范中都作了详细的规定。新技术的应用可 以充分满足数据业务一定的时延容忍限度和对误码率的高要求，非常适合数据业 务的传输。 一北京交通大学电子信息工程学院硕士论文 h s d p a 系统分组调度算法研究 i i s i ) p h s df n 浈l ! ，型女术j i s n p 小1 t f 。坩吣一k 一、 的撞e 、 多码传输、 a m c l 、 h a r q f 软切换 乏、 、 。( w c d m a 技术 j 1 1 t l 一2 m s ： ，_ 、 、 、 ， 可变 、 ，高级 、 扩频幽子 心膊夕 、 图1 1h s d p a 关键技术 快速链路自适应技术 h s d p a 使用链路自适应技术来代替功率控制技术和时变的扩频参数，主要 通过自适应调制编码舢订c 和多码传输实现。为了应付u e 端动态变化的e s n o 。 h s d p a 会根据瞬时的无线链路条件对调制方法、编码率和信道化码的数目的进 行调整。前两项的组合被称为a m c ( a d a p t i v em o d u l a t i o na n dc o d i n g 白适应调制 编码) 。h s d p a 使用q p s k 和1 6 q a m 来增加处于良好链路条件下用户的峰值 速率，相比q p s k ，高阶调制1 6 q a m 高阶调制是给接收终端是引入了一些复杂 性的。h s d p a 采用一种基于r 9 9 规范的t u r b o 编码器，编码效率是l 3 ，可以通 过速率匹配达到从1 6 到1 1 的不同编码效率。通过编码效率和调制方式的组合 可以达到不同的码速率，两者的组合称为m c s ( m o d u l a t i o na n dc o d i n gs c h e m e 调制编码机制) 。表1 1 给出了m c s 集的例子，可以看到调制编码方式和相应码 速率的关系。 h s d p a 系统分组调度算法研究 m c s调制方式 有效每个t t i一个码的 编码效率比特数峰值速率 1 l 42 4 0 1 2 0 k b p s 2 q p s k l 24 8 0 2 4 0 k b p s 33 ，47 2 0 3 6 0 k b p s 4 l 29 6 04 8 0 k b d s 5 1 6 q a m 3 41 4 4 07 2 0 k b d s 表1 1 除了a m c ，多码传输也是实现链路自适应的方式。如果用户具有较好的 信道条件，n o d eb 可以利用它并行传输多码，以达到大的峰值速率。例如，利 用m c s5 和1 5 个多码，最大峰值速率可以达到1 0 8 k b p s 。在瞬时信号质量条件 很好时使用高峰值速率有利于增加用户和系统的吞吐量性能。 链路自适应功能必须选择m c s 和多码数来适应瞬时e j n o ，由于m c s 阶 数与每数据比特消耗能量成正比，低阶m c s 适合于能量受限的信道条件差的用 户，高阶m c s 适合信道条件较好或多码资源短缺的情况。 链路自适应技术是根据道反馈信息来做出调整的决定的，常用的指示信息 包括信道质量指示参数( c q i ) 、相关d p c h 的功率测量、混合a r q ( h a r q ) 确认、缓存器大小等。其中c q i 报告看起来是最具吸引力的方案，终端u e 在上 行信道发送c q i 报告，指明用户接收到的瞬时信号质量。c q i 指明u e 可支持的 备选集中的传输块长度，码数和调制方式。它对于网络来说很简单，准确而频率 较高。 h a r q 技术 混合自动重复请求( h a r q ) 技术把前馈纠错( f e c ) 和a r q 方法结合在一起，保 存以前尝试失败中的信息，用于未来解码中。h a r q 是一种暗示链路适配技术， 相比a m c 采用明示的c i 或类似措施设置调制和编码格式，h a r q 则采用链路层 一北京交通大学电子信息工程学院硕士论文 h s d p a 系统分组调度算法研究 确认( a c k n a c k ) 制订重传决策。如果说a m c 提供了粗数据速率选择，h a r q 则根据信道条件提供数据速率微调功能。 终端通过 a r q 机制快速请求基站重传错误的数据块，减轻链路层快速调整 导致的数据出错的影响。终端在收到数据块后5 m s 内向基站报告数据解码成果或 出现错误。终端在收到基站重传数据后，在进行解码时，结合前次传输的数据块 以及重传的数据块，充分利用它们携带的相关信息，以提高译码概率。基站在收 到终端的重传请求时，根据错误情况以及终端的存储空间，决定使用的“软合并” 方案控制重传相同的编码数据( 追赶合并法( c h a s ec o m b i n i n g ，c c ) ) 或不同的 编码数据( 增量冗余法( i r ) ，以帮助终端提高纠错能力。 混合自动重复请求( h a r q ) 功能位于m a c - h s 层，传输块的重传过程比r l c 层重 传要快，由于不涉及r n c 和i u b ，h a r q 明显减少了系统传输时延。 快速分组调度技术 快速分组调度算法是本文研究的核心领域。快速分组调度技术是决定h s d p a 性能的关键因素。h s d p a 把分组调度功能从网络控制器移到了n o d eb ( b t s ) 中 的m a c 层。3 g p p 并没有明确规定h s p d a 所使用的调度算法，但是有一点是很 明确的_ h s d p a 追求的是系统级的最优，新的快速调度机制必须可以根据无线 信道条件和传输到不同用户的数据流量情况决定哪个用户可以使用信道，以何神 速率使用信道。可以说它既要使得最能充分利用信道的用户使用信道以提高系统 吞吐率，也要使得信道条件相对不好的用户在一定时间内能够使用信道，也保证 服务公平性和业务连续性。集中调度技术使得信道总是为与信道状况相匹配的用 户所使用，从而最大限度地提高信道利用率。同时，h s d p a 系统对高速多媒体数 据的支持也对快速分组调度技术提出了更高的要求如何保证业务的q o s 性 能，这也是本文研究的核心之一。 北京交通大学电子信息工程学院硕士论文 h s d p a 系统分组调厦算法研究 f c s 快速小区选择技术( f c s ) 使得移动台不需要同时从多个小区内选择数据，只需 要在每镇选择最好的小区来传输数据。上行d p c h 用来指示需要的小区，网络利 用这个蜂窝把数据一镇一镇的传给移动台。对于上行信道，每个小区被分配一个 临时i d ，移动台周期性的把主要小区的i d 通知给邻近的小区。那些没有移动台 选择的非主要小区就关闭他们的发射机。然而对于快速小区选择，移动台在每镇 选择最佳的小区，用最佳小区在h s d s c h 上接收数据。h s d s c h 只在这个小区中 传送。 短t t i 更短的t t i 使数据包传送的速度更快，使h a r q 的时延变得更小，使a m c 的信道 适应更加及时，h s d p a 中一般t t i = 2 m s 。 m i m o 技术 m i m 0 可以成倍的提高衰落信道的信道容量。m i m i o 天线阵列是一种开环的 m i m 0 技术，m 个发送天线，使用变码重用技术将同样的码集的每个码重复使用m 次，每个码用来调制不同的数据子流，这样，在不增加码资源的基础上提高了原 始数据的传输速率。为了分辨m 个数据子流，在接收端也要使用多天线和空间信 号处理。m i m 0 是一种能使h s d p a 增加容量和提高峰值速率的技术，但受限于物 理信道模型，会增加射频的复杂性，使h s d p a 进一步发展的技术。 h s d p a 信道结构 h s d p a 增加了一个新的传输信道，称为h s d s c h ，该信道主要用于进行“尽力 而为”方式的分组业务传输，同时辅助h a r q 、a m c 等h s d p a 关键技术的实现。 h s d s c h 信道和d s c h 信道一样也是一种公共信道，主要是在时域内采用信道码 ( 多码) 机制并同时被多用户使用。在h s d s c h 中采用固定的扩频因子1 6 ，这 样可用的码最多不会超过1 6 个，一般取最大码数为1 4 个。采用固定扩频饮子可 以减低移动台的复杂性同时减少下行的信令。 一一北京交通大学电子信息工程学院硕士论文 h s d p a 系统分组调度算法研究 h s d p a 功能模块 h s d a p 中，分组调度算法、h a r q 、州c 等关键技术的实现关系如下图所示 图王_ 2 从上述总结可知h s d p a 系统采用了很多的新技术，其中快速分组调度算法的 设计将是本文研究重点。在后面的研究中会得知，快速分组调度算法的设计应该 与h s d p a 其他技术紧密结合。 北京交通大学电子信息工程学院硕士论文 1 0 一一一一h s d p a 系统分组调度算法研究一一一一 第二章无线分组调度策略 h s d p a 系统作为一种典型的无线系统，其上的调度算法具有普通无线调度算 法的的一切基本性能。本章主要从无线系统的角度提出分组调度策略的设计规 律，这是h s d p a 系统分组调度算法设计的基本要求。传统的有线网络调度算法对 于各个连接的服务质量保障是独立的，即各个数据流之间无相互影响，调度算法 多采用公平的排队算法。对于无线信道而言，其调度算法的复杂度比较高。多变 的信道条件数据分组难以正确有效的传输，所以调度器要选择在尽蜘能好的条件 下佶输数据；时间、信道化码、带宽等无线资源是受限的，共享信道的存在导致 了多用户对信道的竞争，而移动用户并不知道竞争状态，如果将某一信道临时分 配给其它连接，必然造成流之间的相互影响，如果资源分配给了条件较差的用户， 也必然会消耗大量资源，影响其余用户数据的传输效率。在较恶劣的无线环境中， 充分利用有限的资源和信道的时变特性，是无线系统分组调度算法的最基本要 求。存无线通信系统中，好的调度算法一方面要对信道特征关注，同时还应该考 虑所服务的数据包的服务模型，业务类型等因素以保证q o s 。无线通信系统e 业务的发展迅速，以3 g 系统为例，它能提供如视频会议，实时过程控制与遥测， 音频视频流和高速数据传输等不同业务，每种应用会向网络请求所需的q o s ，因 此无线系统的调度算法必须提取各种业务的特征和服务模型，公平的分配资源设 置合理的优先级，保证业务的正常进行。 本章从无线分组调度策略的原理，q o s 保证，优先级和公平性策略八手，明 确了无线系统分组调度策略应该具备的基本性能。 2 1 无线q o s 特点 服务质量q o s 是指用户要求网络系统所必须保证的关于信息传输的质和量的 服务质量q o s 是指用户要求网络系统所必须保证的关于信息传输的质和量的 北京交通大学电子信息工程学院硕士论文 h s d p a 系统分组调度算法研究 特征集，它反映服务提供者( 网络系统) 和服务使用者( 用户) 之间的能力和需求关 系，用来描述网络的性能。能否为用户提供满意的服务，是一个网络技术能否生 存和发展的前提。q o s 无论对于网络具有非常重要的意义。无线分组交换网的 0 0 s 体系结构包含流描述、服务类别、接入控制、公平调度技术等。 无线分组交换网络中，每个业务呼叫有其特定的q o s 需求，如分组时延 ( d e l a y ) 、时延抖动( d e l a yj i t e r ) 、丢失率( 1 0 s sr a t e ) 等。从服务提供的观点 来看，一个业务流可以通过流特征来说明，流特征为在服务初始期间向网络服务 提供者所提供的一系列参数。h s d p a 系统做为3 g 的增强型演进系统，系统种常 用的流特征参数是一致的，包括保证的比特率( g b r ) 、突发长度、最大比特率、 延迟和延迟变化、s d u 错误率、剩余误比特率、错误s d u 传输。参数的具体含 义如表2 ，l 。 参数含义 保证的比特率在通话过程中。u 灯s 系统承载必须保证的用户或应用的比特率，它至 ( g b r ) 少要等于可持续比特率，后者等于通话或整个时间内平均的比特速率 突发长度前后快速到达的数据包之间的时间间隔比通话过程中包的平均到达时 间要短时，称该突发的比特数为突发氏度，对于音频流总体上来说是 非突发性的，相比而言流式视频业务更具突发性 最大比特率一个突发对持续时间进行平均的比特数，是一个用户或应用可以提供 或接收的比特率的上限，网络用此参数来选择无线接口的下行信道上 的编码类型和编码速率，这个为了应用定义的参数可以应用与不同比 特率。例如带有实时编码的视频应用 延迟和延迟变化在从业务源到目的地的传输过程中，包在很多地方会遭遇时延( 包括 一北京交通大学电子信息工程学院硕士论文 h s d p a 系统分组调度算法研究 传播时延、输入或输出端的缓冲时延、排序时延、交换时延) 时延变 化的限制有利于配合保证比特率的实现 s d u 错误率被丢失的或错误接受的s d u 相对于全部s d u 数目的比值，s d u 错误率 要求暗示着r i 层的运行模式，如果物理层可以提供足够的可靠的连 接来满足s d u 错误率需求，r l c 层将运行在确认模式来满足这个承载 特性 剩余误比特率所发送的s 叫中未检查到的误比特率，可以用于选择协议和检错码 错误s d u 传输决定是否必须传输带有检测错误的s d u ，通过使用s d u 错误率，剩余 比特错误率咀及错误s d u 传输特性，就可以满足应用的错误率需求 表2 1 无线业务分类有多种方式，根据传输需求分类，可以分为实时业务( r t ) 和非 实时业务( n r t ) ，其含义见表2 2 。 业务类型含义 实时业务( r t )在端到端通信中有严格的时延需求，所以与实时业务传输相管的任 何网络节点都必须在一个最大容许时延的范围之内传输r t 分组。 不能实现链路级重传，纠错性非常有限。 非实时业务( n r t )被普遍认为对错误敏感的，相比实时业务没有那么高的时延要求。 利用重传机制可以实现无错传输。 表2 2 按照网络如何分配资源( 带宽) 可以将业务分为：恒定比特率业务( c b r ) 、 实时可变比特率业务( v b r ) 、非实时可变比特率业务。如话音，高质量音频，视 频电话和动态视频等属于恒定比特率业务，实时可变比特率业务则包括例子包 一一北京交通大学电子信息工程学院硕士论文 一一一一一一h s d p a 系统分组调度算法研究 括可变比特率编码的音频，按某种m p e g 标准编码的交互式视频等，而交互式大 文件传输业务属于非实时可变比特率业务。 业务类型含义 恒定比特率业务 恒定比特率业务对时延敏感，周期性地产生固定跃度地包，维持数据包 ( c b r ) 之间的时间相对关系。每种应用自身知道其通话过程中所需要的带宽， 并据此来发出q o s 请求 实时可变比特率业实时可变比特率业务( v b r ) 周期性产生可变长度的包，数据包之间的 务( v b r ) 时间关系不固定。廊用不知道它所需要的确切带宽，但可以知道可持 续业务速率，最大业务速率和最大业务突发。 非实时可变比特率非实时可变比特率业务这种类型的业务可以容忍时延或时延变化。业 业务 务源可以向网络指明它的最小可持续业务速率和连续传输之间最大可 容忍的时延。 表2 3 按能容忍的端到端时延敏感程度，业务可以分为：实时会话业务、交互式业 务、流业务、背景业务，具体特点如表2 4 ： 业务类型基本特点 应用举例 会话类型话音，可视电话， 须保持流中信息实体间的时间关系( 变化) 视频游戏 数据流类型会话模式( 苛刻的，高的时延要求) 流式多媒体 互动类型须保持流中信息实体间的时间关系( 变化)网页浏览，网络游戏 请求一响应模式，须保持数据的完整性 后台类型 信息接收目的端并不在某一时间内期待数据e m a i l 的后台下载 的到达，保持数据的完整性 一一北京交通大学电子信息工程学院硕士论文 1 4 h s d p a 系统分组调度算法研究 表2 4 分组调度算法及其接纳控制算法都在确保q o s 方面起着至关重要的作用。调 度算法可以看作是对系统资源的一种使用方式，为了确保连接的q o s ，必须为业务 流分配一定的资源，这是保证q o s 的必要条件。为此系统中接纳的业务总量不能 超过系统的服务能力。接纳控制算法的作用就是分配与安排系统资源，使系统不 超出的服务能力，保证每一类业务的q o s 。具有不同q o s 需求的用户的接纳控制 策略是研究的无线资源管理的重点，它将通过探测网络是否有足够的资源来确保 接入用户的q o s ，并且考虑目前己存在的用户的q o s 不会被破坏。 2 2 无线分组调度算法 2 2 1 无线分组调度算法原理 下图给出了一个分组调度的模型描述调度过程。输入端存在时变信道的用户 集 f ，它的瞬时性能符合如下统计过程： 吩( 一) ，f = 1 ， 其中 r ( ”) 是每个t t i 内对于某特定b l e r 的最大的可支持数据速率，分组调 度算法于第n 个t t i 时隙间隔选择属于用户集f f l 的用户队列的头部分组( h o l ， h e a do fl i n e ) ，把功率和资源分配给此用户，输出到输出链路上。注意由于 基站( 调度器) 处理的是分配时隙的任务，只是将时隙分配给某一个排队队列的第 一个分组数据包( h e a do f l i n e ) ，而不去考虑这一队列中分组的顺序。比如在某 个队列中，由于误码或别的原因重发的包在队列中的位置靠后，如果按照有线网 络中的公平排队算法，它在这一队列中将最晚得到服务，对于时延敏感的业务来 说，会出现大量丢弃分组的状况。因此，在无线分组调度算法中应该建立将分组 一一一一北京交通大学电子信息工程学院硕士论文 h s d p a 系统分组调度算法研究 顺序映射到排队顺序上的模块，当分组到达后，根据其分组的顺序重新调整排队。 定义调度器的运行任务是根据一定的规则在每个t t i 间隔内选择用户队列 头部分组数据，分配小区资源，并将其按一定的优先级次序进行队列映射重组， 送入发送队列进行服务。 + t t i 图2 1 从业务角度看，图2 2 给出了无线调度算法应用的业务范畴部分实时业务 和大量非实时业务，相应的也就是流媒体业务，交互业务和后台业务。 0 n s 级 调地 f j 。，通 二j 互 二匦互二 冈叵图匹 互亟巫互 二互巫互 厂玉互 二二亚画f 二 二正 互亟互亟互司 一一北京交通大学电子信息工程学院硕士论文 h s d p 系统分组调度算法研究 圈2 2 分组调度算法决定着分组的输出次序，因此它决定着分组的时延、时延抖动， 如果一个连接中的分组在较长时间内得不到服务，该连接的队列就有可能溢出， 分组丢失率受其影响，业务受阻，所以分组调度算法与q o s 关系十分密切。实时 业务与非实时业务有不同的时延需求：交互业务，流式业务和后台业务有不同的 保证比特速率需求和时延需求，在综合业务的环境下，一个好的调度算法应该能 够满足各种业务对于q o s 的需求，不同业务类型有不应该同的调度方式。 从信道和资源角度看，一种高效的无线调度算法应能保证错误链路上的无效 传输最小化，同时使有效的吞吐量输出和无线信道利用率最大化。移动终端是功 率受限的，好的调度算法应该使移动台需要的与调度相关的控制信息数目最小， 这些信息可能包含移动终端的排队状态，包到达时间和信道状态。调度算法不应 该太复杂，以便高速执行。 总体上说，对于给定用户集似，f = 1 ，调度器的运行目标是使小区的 吞吐量输出达到最大化同时满足小区承载的q o s 需求。 2 2 2 无线分组调度算法的优先级 当每个数据包到达发送端时，调度算法会根据特定的规则为其设置服务优先 级参数，调度算法根据服务优先级进行比特速率的选择和控制比特速率的升降， 并对不同用户的分组数据进行排序，发送到共享信道上。较高优先权的分组数据 会首先处理，这样就可以通过类似q o s 分集的方法为不同用户群提供不同的q o s 的服务。 用户的优先级可以用只( f ) f = 1 ，2 ，来表示，指的是用户i 在t 时刻被分 配的优先级。 一一北京交通大学电子信息工程学院硕士论文 h s d p a 系统分组调度算法研究一一一 2 2 3 无线资源配置的公平性 由于分组调度算法控制着小区资源的分配，如果它一味强调增加小区的吞吐 量，则必然会影响用户之间无线资源分配的公平性。当选择为小区中哪个用户提 供服务时，分组调度决定如何为所有的用户分配小区资源。资源分配的公平程度 与不计用户信道条件的无偏向程度密切相关。一般的调度算法都基于以下三种基 本的公平级别： 基于c i ( b a s e do n c ，i ) c i 标志着信道质量的优劣程度。具有最好的信道质量的用户将会被考虑优 先分配资源。也就是较高c i 值的用户比较低c 竹值的用户具有更高的分组传输 优先权。这种类型的调度算法中，c i 调度器以牺牲用户之间占用资源的公平性 为代价达到更大的系统容量。如图2 - 3 ，如果u e l 具有最高的c i ，它将在整个 时间内占用信道资源，这使u e 2 得不到服务，直到前者的缓冲器清空，u e 2 才 开始得到服务。因此信道条件差的用户遭遇很差的q o s ，在小区负载很重的情况 下可能产生这些用户的可用资源匮乏 u e l ；u 融；u e 2 得到服务的u e 图2 3 一一北京交通大学电子信息工程学院硕士论文 h s d p a 系统分组调度算法研究 基于资源的公平( f a i rr e s o u r c e ) 也称为链路匹配。这种调度算法将小区资源( 编码、功率和时间) 等量的分 配给用小区户集，f _ 1 ，这时小区边界的用户比靠近基站的用户得到更低 的吞吐量，因此用户的q o s 并不是完全公平分布的。与使用基于c i 的调度算 法和使用后面所述的基于公平吞吐量的调度算法相比，这种算法的总体小区容量 较低，因为低c i 的用户与高c i 的用户消耗同样多的小区资源。这是因为无论 用户c i 。 基于吞吐量的公平( f a i rt h r o u g h p u t ) 也成为“最大一最小公平算法”( m a x m i nf a i m e s s ) 。这种标准不考虑用户 的信道质量和位置如何，必须对所有的用户提供相同的吞吐量，即小区边界的用 户和n o d eb 附近的用户会具有相同的吞吐量。一些报告给出了相关的定义：“当 一个用户吞吐量集 ) ，i = 1 ，的每个元素都可达且每一个用户的吞吐量 在，除非它保持可达性”这种调度为了让所有用户具有相同的吞吐量，低c i 的 用户比高c i 的用户应该分配更多的资源，这于基于c i 的算法恰恰相反，因此 这种调度算法可以视为一种逆c i 调度算法。由于资源分配的不公平性，这种算 法达到了吞吐量的公平性但是降低了小区整体的吞吐量大小。 为了增加终端用户的q o s 的公平性，必须为具有较差信道质量的用户分配 更多的信道资源去平衡其吞吐量。因此，如若想增加小区吞吐量的公平性，一定 等于降低总体的频谱效率。有一点应该注意的是提到资源分配的公平性并不意味 着每个用户获得绝对数量意义上相同的资源，而是说用户得到相同的资源分布。 也就是说，即使两个用户获得资源的公平程度是一样的，他们获得的绝对资源数 量也肯定是不同的。因为用户的平均负载不相同，瞬时负载更是时刻变化着的。 北京交通大学电子信息工程学院硕士论文 1 9 h s d p a 系统分组调度算法研究 第三章常用调度算法在h s d p a 系统上的应用 3 g p p 标准中没有规定调度算法，各个厂商的调度策略可以是不同的，提 供设备的性能差别也会很大，这是比较不同设备供应商的设计能力和设备技术性 能的关键参考点之一。当前已经有一些对于常用调度算法在h s d p a 系统上应用 的研究，但是仅仅给出了性能结果，并没有进行深入的规律性的分析。在本章， 笔者重新解读了文献 1 】、 2 和 3 的部分研究成果，从新的角度更加全面和深入 研究各种常用算法的性能表现，从性能差异中分析算法的设计规律，得出相关结 论，为设计优秀的调度算法作准备。 3 1 主要调度算法 轮询调度r o u n dr o b i n ：r o u dr o b i ， 算法在基站端执行，作用于小区内部，保证该小区内的所有用户按照某种确 定的顺序循环占用等时间的无线资源来进行通信。每个用户对应一个队列，用以 存放待传数据，载一个队列再次接收服务之前，其他所有的非空队列必须都被服 务过一遍，除非只有一个非空队列，否则一个队列不可能连续接收服务，调度算 法可一次传送多个数据包。轮询调度的优点是不仅可以保证用户间的长时公平 性，也保证了短时公平性，算法实现非常简单。但是轮询算法的最大缺点是，由 于没有考虑不同用户的无线信道的具体情况，应此系统吞吐量是很低的。通常， 人们认为轮询算法是最公平的，它保证所有用户占用等量的时间进行通信，同时 人们认为该算法的性能是最低的，它是公平性的上界和吞吐量的下界。 最大c ，i ( m a x c ，i ) 在每一个t t i 内调度具有最高瞬时支持数据速率的用户。用公式表示为： 只( f ) = 口 ( c ，) j ( f ) ( 3 1 ) 一一一北京交通大学电子信息工程学院硕士论文 h s d p a 系统分组调度算法研究 公式表示时刻t 时用户i 获得调度的概率与载干比成正比。这种方法获得最大的 系统吞吐量，实现简单，但是由于具有较差信道条件的用户被调度的可能性大大 降低，各个用户之间的吞吐量很公平性较差。但是由于相比平均链路传播条件快 衰落具有更大的变换范围，无线链路质量较差的用户仍然可以接入信道。此算法 在基站执行，作用于小区内部，保证在任意时刻总是载干比最好的用户接收服务。 通常认为最大载干比算法是最不公平的，并且把采用该算法得到的系统吞吐量看 作系统吞吐量的上届。 正比公平调度p r o p o r t i o a l f a i r 正比公平调度在基站执行，每个用户被分配如下优先级 只：掣或暑：掣i ：l ，n ( 3 2 )。 ( f ) 丑o ) p i ( t ) 是指用户优先级，砌( t ) 指被调度的用户i 在时刻t 的瞬时支持数据速率， 或者用户i 在时刻t 的载干比，其值较高也就意味着信道条件好。元是用户的吞 吐量。这个算法旨在调度那些与平均水平相比具有较好的瞬时无线链路质量的用 户。在快衰落条件是i i d ( 独立同分布) 并且速率r i ( t ) 与瞬时e s n o 成线性关系 时，p f 算法为所有的用户提供相同的功率和时间资源，且速率足o ) 与瞬时c i 成 正比。但是在实际的h s d p a 环境中，线性关系的假设是不会满足的，因为a m c 功能的局限性所致。所以p f 算法职能做到吞吐量和资源分配的有条件的公平。 快速公平吞吐量调度伊a s tf a i rt h r o u g h p u t ) 这种算法利用短期无线链路衰落的变化为小区所有的用户提供公平的吞吐 量( m a ) 【一m i n 机制) 。在 1 2 中，作者提供了如下的改进型p f 公式： 北京交通大学电子信息工程学院硕士论文 h s d p a 系统分组调度算法研究 皇：刹磬 ( 5 0 4 ，b ， 丑( f ) l 足( f ) i m a x 虿 指所有用户的最大平均支持速率，是常量。注意鬲的作用是在快 衰落是独立同分布情况且r ( f ) 与e s n o 成线性关系时，补偿信道条件较差的用户 的优先级。 平均c i ：这种算法在每一个t t i 时间间隔调度具有最大平均c i 待传数据 的用户。缺省的平均时间窗口长度是1 0 0 m s 曰( f ) = a - 爿v g ( c ，) ；o ) ( 3 4 ) 公式表示， 时刻t 时用户i 获得调度的概率与其平均载干比成正比。 - 1 h ( f a i rt h r o u g h p u t ) 在每个t t i 间隔调度具有最低吞吐量的用户。不需要知道瞬时的信道质量信息， 属于慢调度。 即) 2 焘 ( 3 s ， 公式表明，时刻t 时用户i 获得调度的概率与平均获得的吞吐量成反比。 3 2 调度算法的分类 总结起来调度算法通常分为两大类： 快调度调度的决策基于当前的终端信道质量度量结果，必须追踪用户支 持数据速率的瞬时值。这个调度算法必须在n o d eb 执行，以获得目前的信道质 量信息。 慢调度调度的决策基于获得的用户信道质量长期平均值，或根本不用任 何用户性能数据。 北京交通大学电子信息工程学院硕士论文 h s d p a 系统分组调度算法研究一一一 洲皂玎浊 调度速率服务f无线资泓! 公、l 。什 l 轮咖叫j 女( r r ) 陧调腰( j 土j 期p p 洲度均衡的备吐讨公平陀村 问 l o o m s ) 的平均无线资源分配 f a l rt h r o l l 曲p i l l ( f r h ) 慢调度( 首先渊度平均吞：l l许 碱公半 1 0 0 m s )量最低州户 1 7 均c ( 1 p i )陧调度( 首先调度k | j j 甲均 偏向i 置信道质甘川厂1 的0 i 公 1 0 0 m s ) 化道质谴最女，的川平的无线资源分机 p r o p o r t i o n a lf a h p f ) 快调度( 每 首先调度瞬时相关在特定条件下的均衡的吞吐 t t i ) 信道质量最高的用量公平性等量的无线资源 分配 快速公平吞吐量快调度( 每首先调度瞬时相关特定条件下的吞吐量公平性 ( f f t h )t t i ) 信道质量最高的用 户 ” 最大c ，i ( m a x c i ) 快调度( 每首先调度瞬时相关偏向于高倍道质越用户的不 t t i ) 信道质薰最高的用公平的无线资源分布 户 表3 1 常用调度算法分类 下面就来深入分析各种算法在h s d p a 系统上的性能。 3 3 无q o s 约束时常用调度算法吞吐量性能 吞吐量性能时衡量调度算法优越性的重要指标，当前仿真主要集中于研究不 同输入负载及用户环境条件下吞吐量的性能情况。典型的仿真设置见参考文献 【1 ，一般是对于步行( p e d e s 伍a na ) 和车载( v e h i c u l a r a ) 条件下以特定速度 运动的小区用户进行调度，选用相对较高的2 3 m b p s 负载输入。下面深入研究6 种常用的调度算法的吞吐量性能和各种因素之间的关系。 吞吐量性能和公平度关系 图3 i 显示了在3 h n m 步行的移动环境不6 种常用调度算法的用户吞吐量 概率分布图。 北京交通大学电子信息工程学院硕士论文 h s d p a 系统分组调度算法研究 1 o 9 08 n 7 o6 口05 u 4 03 0 2 0 1 u s e rt h r o u g h p u tf p s ) 图3 1 六种典型调度算法的吞吐量性能【1 】 数据分析： 1 1 从吞吐量公平性方面考察，符合公平吞吐量策略的吞吐量分布曲线斜率较大 ( f t h ，f f t h ) ，可达的吞吐量范围彼此相似，也就是达到了吞吐量彼此公平的 目的；符合公平资源策略的吞吐量分布曲线相对前者就平缓得多( p f r r ) ，可达 的吞吐量范围较大，也就是吞吐量很不公平。 结论：算法的公平性( 吞吐量公平，资源公平) 决定了用户吞吐量分布概率曲线