（通信与信息系统专业论文）hsupa系统分组调度算法研究与仿真.pdf

摘要 摘要 无线网络中的上行分组调度器在用户请求到达调度节点时，确定各用户的调度优先 级，然后分配无线资源，如下行码、速率和功率等，以满足系统的各种性能要求。本文 以h s u p a 系统为背景，对无线网络中的上行快速分组调度算法进行了研究和仿真，主 要工作如下： 第一章简要介绍了移动通信系统无线资源管理的关键技术和无线系统中的分组调 度算法，并概括了全文的主要研究工作。 第二章在介绍无线分组调度算法发展过程的基础上，结合调度算法的数学模型，对 轮询调度算法、m a xc i 调度算法和比例公平调度算法的基本原理作了阐述。 第三章对h s u p a 系统中的快速重传和快速分组调度等关键技术进行了介绍，并对 h s u p a 系统仿真平台作了比较详细的描述。 第四章以公平机会调度算法和m a xp o 调度算法为参考，提出了一种时间速率混合 调度算法，该算法根据用户的缓存区内的状况将用户进行分组，然后根据用户的请求速 率进行资源分配，并基于比例公平性原则对用户进行资源补偿。此外，还通过系统仿真， 分析和比较了三种算法的性能。 最后对全文进行了总结。 关键词：h s u p a ，分组调度，轮循调度，最大载干比调度，正比公平性调度，系统 平均吞吐量，长期公平性，短期公平性，公平机会调度。 a b s t r a c t a b s t r a c t p a c k e ts c h e d u l e ri nw i r e l e s sn e t w o r ki su s e dt oa s s i g ns c h e d u l i n gp f i o d t yf o ra l lu s e r s ， a l l o c a t ew i r e l e s sr e s o u r c e ，e g c o d e s ，v e l o c i t ya n dp o w e r , s oa st os a t i s f yk i n d so fs y s t e m s p e r f o r m a n c ed e m a n d t h i st h e s i sf o c u s e so nt h er e s e a r c h i n go fp a c k e ts c h e d u l i n ga l g o r i t h m s i nh s u p a s y s t e m t h em a i nc o n t e n t sa l ea sf o l l o w s ： i nc h a p t e r1 ，w eb r i e f l yi n t r o d u c et h ek e yw i r e l e s sr e s o u r c em a n a g e m e n tt e c h n i q u e so f t h em o b i l ec o m m u n i c a t i o n ss y s t e ma n dt h ep a c k e ts c h e d u l i n ga l g o r i t h mo ft h ew i r e l e s s s y s t e m i n c h a p t e r2 ，f i r s t l yi n t r o d u c et h ed e v e l o p m e n to ft h ew i r e l e s sp a c k e ts c h e d u l i n g a l g o r i t h m s ，a n dt h e ne x p a t i a t eo nf u n d a m e n t a lo fp a c k e ts c h e d u l i n ga l g o r i t h m se t cr o u n d r o b i ns c h e d u l i n ga l g o r i t h m ，m a xc ia n dp r o p o r t i o n a lf a i r n e s s s c h e d u l i n ga l g o r i t h m c o m b i n i n gw i t l lt h em a t h e m a t i cm o d e lo fs c h e d u l i n ga l g o r i t h m i nc h a p t e r3 ，w eb r i e f l yi n t r o d u c et h ek e yt e c h n i q u e so fh s u p as y s t e me t cf a s t r e t r a n s m i ta n df a s tp a c k e ts c h e d u l i n ga l g o r i t h m a n dt h e nd e s c r i b es y s t e ms i m u l a t i o nt a b l e i nc h a p t e r4 ，w eg i v eac o m b i n e dt i m ea n dv e l o c i t ys c h e d u l i n ga l g o r i t h m t h i sa l g o r i t h m c l a s s i f yu s e r sb a s e do nt h eb u f f e rs t a t u s ，a n dt h e na l l o c a t et h er e s o u r c eb a s e do nv e l o e i t y r e q u i r e m e n ta n dc o m p e n s a t eu s e rr e f e r e n c et of a i ro p p o r t u n i t yp r i n c i p l e t h r o u g hs i m u l a t i o n s ， w ea n a l y z ea n dc o m p a r et h e p e r f o r m a n c eo f t h r e es c h e d u l i n ga l g o r i t h m s i nc h a p t e r5 ，w es u m m a r i z et h ew h o mt h e s i sa n d p o i n tt h ei s s u e st ob ef u r t h e rs t u d i e d k e y w o r d s ：h s u p a ，p a c k e ts c h e d u l i n g ，r o u n dr o b i ns c h e d u l i n g ，m a xc i s c h e d u l i n g ，p r o p o r t i o n a lf a i r n e s ss c h e d u l i n g ，s y s t e ma v e r a g et h r o u g h p u t ，l o n gt e r mf a i m e s s ， s h o r tt e r nf a i m e s s ，f a i ro p p o r t u n i t ys c h e d u l i n g i i i 插图目录 插图目录 图1 1 ：无线资源功率算法在h s u p a 系统中的典型位置2 图1 2 ：分组调度器输入信息及其计算原理5 图2 1 ：调度器模型7 图3 1 ：h s u p a 中e d c h 协议模型2 2 图3 2 ：h s u p ：a m a c e 协议结构图2 2 图3 3 ：h s u p a 系统工作流程2 3 图3 4 ：h s u p a 系统仿真网络模型2 8 图3 5 ：u e 节点的协议结构。3 0 图3 - 6 ：l i e 的节点模型3 1 图3 7 ：n o d e b 的节点模型3 2 图3 8 ：管道流程3 3 图3 - 9 ：r n c 节点模型。3 4 图4 1 ：资源分配流程4 2 图4 2 ：资源补偿流程4 4 图4 3 ：公平机会调度算法的用户调度优先级分布4 7 图4 4 ：m a xp o 调度算法的用户调度优先级分布1 。4 8 图4 5 ：m a xp o 调度算法的用户调度优先级分布2 4 8 图4 - 6 ：m a xp o 算法下1 1 个用户调度优先级分布4 9 图4 7 ：时间速率调度算法的用户调度优先级分布l 5 0 图4 8 ：时间速率混合调度算法的用户调度优先级分布2 5 0 图4 - 9 ：三种算法的系统r o t 累积概率分布1 5 2 图4 1 0 ：三种算法的系统r o t 累积概率分布2 5 2 图4 1 l ：三种算法的系统平均吞吐量曲线1 。5 5 图4 1 2 ：三种算法的系统平均吞吐量曲线2 5 6 图4 - 1 3 ：三种算法的长期公平性曲线1 。5 7 图4 1 4 ：三种算法的长期公平性曲线2 。5 8 图4 1 5 ：三种算法的短期公平性曲线1 5 9 i 东南大学硕士学位论文 图4 1 6 ：三种算法的短期公平性曲线2 。5 9 图4 1 7 ：三种算法的r l c 层端到端延时曲线1 6 0 图4 1 8 ：三种算法的r l c 层端到端延时曲线2 6 l i i 表格目录 表格目录 表2 1 ：一些无线分组调度算法的比较1 2 表3 1 ：网络模型主要参数假设2 8 表4 1 ：移动台的参数配置4 5 表4 2 ：小区的参数配置4 5 表4 3 ：移动台的位置与速率配置4 5 表4 4 ：时间参数配置4 6 表4 5 ：三种算法的分组丢失率5 3 表4 6 ：三种算法的系统平均吞吐量5 3 i x 缩略语 3 g a c k c a c c d f c d 【a m h a r q h c h s d p a h s u p a l c m a c n a c k p c q o s r n r n c r r m r t w p s f i t d m u e u f w c d m a w f i 缩略语 3 t hg e n e r a t i o n a c k n o w l e d g e m e n t c a l la c c e s sc o n t r o l c u m u l a t i v ed i s t r i b u t i o nf u n c t i o n c o d ed i v i s i o nm u l t i p l ea c c e s s f i l et r a n s f e rp r o t o c o i h y b r i da u t o m a t i cr e p e a tr e q u e s t h a n d o f fc o n t r o l h i 曲s p e e dd o w n l i n kp a c k e ta c c e s s h i 曲s p e e du p l i n kp a c k e ta c c e s s l o a dc o n t r o l m e d i u ma c c e s sc o n t r o l u n a c k n o w l e d g e d p o w e rc o n t r o l q u a l i t yo fs e r v i c e r a d i on e t w o r k r a d i on e tc o n t r o l r a d i or e s o u r c em a n a g e m e n t r e c e i v e dt o t a lw i d eb a n dp o w e r s e r v i c ef a i m e s si n d e x t i m ed i v i s i o nm u l t i p l e x u s e re q u i p m e n t u t i l i t yf u n c t i o n w i d e b a n dc o d ed i v i s i o nm u l t i p l ea c c e s s w o r s t c a s ef a i m e s si n d e x x i 第三代移动通信 接收成功确认 呼叫接入控制 累积分布函数 码分多址接入 文件传输协议 混合自动重传请求 切换控制 高速下行分组接入 高速上行分组接入 负载控制 媒体接入控制 接收错误确认 功率控制 服务质量 无线网络 无线网络控制器 无线资源管理 总宽带接收功率 服务公平指数 时分复用 基站收发信系统 效用函数 宽带码分多址接入 最坏公平指数 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了谢意。 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文 的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档 的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借 阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东 南大学研究生院办理。 期：纩多了 第1 章绪论 第1 章绪论 3 g 技术的成熟和完善为其大规模商用打下了坚实的基础。3 g 不仅是对2 g 发展的延 续，更是整个移动通信产业再次实现跨越式发展的新契机。 本章首先简要介绍了无线资源管理和无线分组调度，然后介绍了论文的主要研究工 作。 1 1 研究背景 随着信息技术的不断发展，移动通信技术和i n t e m e t 技术逐渐呈现日益融合的趋势。 同时，用户的多业务服务需求也在迅猛增长，因此支持多媒体通信的3 g 技术应运而生。 为了满足用户对上行传输的性能需求，3 g p p 在h s d p a ( h i g hs p e e dd o w n l i n kp a c k e t a c c e s s ) 规范发布之后，又启动了h s u p a ( h i g hs p e e d u p l i n k p a c k e t a c c e s s ) 研究项目。 h s u p a 作为w c d m a 上行链路的演进标准，是一种理论上峰值数据速率可以达到 5 7 6m b s 的高速上行数据传输技术，其目标是通过提高小区的吞吐量和高数据速率的覆 盖来提高上行链路容量。为支持这种高速数据传输，h s u p a 引进一种新的传输信道 e d c h ( 增强型专用传输信道) 来传输数据。e d c h 可以用来传输分组业务数据，它支 持变速率传输，快速重传和快速分组调度等。 如何有效地利用有限的上行无线资源实现系统性能的最大化是h s u p a 系统中所要 解决的核心问题。 1 1 1 无线资源管理( r i ) 无线通信系统的无线资源是很广泛的，可以是频率、时间，也可以是码字、功率等。 不论从哪个角度来看，以移动通信为代表的无线通信系统都是资源受限的系统。所谓的 无线资源管理就是对系统的空中接口资源进行规划和调度，其目的就是基于有限的无线 资源，在保证一定的规划覆盖以及服务质量( q o s ) 要求的情况下，接入尽可能多的用 户。无线资源管理包括呼叫接入控制( c a c ) 、功率控制( p c ) 、切换控制( h c ) 、负载 控制( l c ) 以及分组调度( p s ) 等。这些无线资源管理都是基于干扰的无线资源管理。 图1 1 给出了无线资源管理算法在h s u p a 系统中的典型位置。 东南大学硕士学位论文 功率控制快速功率控制 快速负载控制 快速分组调度 外环功率控制 切换控制 接入控制 负载控制 图l - 1 ：无线资源功率算法在h s u p a 系统中的典型位置 无线资源管理的具体算法与网络结构、多址接入方式( w c d m a 、c d m a 2 0 0 0 、 t d s c d m a ) 、业务种类、切换方式以及上行或下行场合等因素有关。下面对无线资源 管理的主要算法做一个概述。 ( 1 ) 呼叫接 控制 若过度增加空中接口负荷，小区的覆盖区域会低于规划值，而且不能保证已有连接 的业务质量。在接纳一个新的u e 前，必须确认本次接入不会破坏规划好的覆盖区域或 已有连接的质量。接入控制的责任就是接受或拒绝建立无线接入承载。在建立或改变承 载时，都要执行接入控制算法。接入控制功能位于r n c 中，接入控制算法将评估建立这 些承载所导致的无线网络中负载的增加。上下行链路的评估必须分别进行，只有当上行 链路和下行链路的接入控制均可以接纳，建立无线承载的请求才能得到认可，否则给予 拒绝，以避免网络中产生干扰过量。接入控制的限制条件要通过无线网络规划来设置。 ( 2 ) 功率控制 功率控制的目标是在为每个用户提供可以接受的服务质量的同时尽可能地减少对 其他用户的干扰。常见的c d m a 功率控制技术可有开环功率控制、闭环功率控制和外环 功率控制三种类型。在h s u p a 中采用的功率控制方案是快速闭环功率控制和外环功率控 制。在上行链路的功率控制中，基站要频繁地估计接收到的信干比( s i r ) ，并把它同目 标s i r l t 较，产生适当的功率控制命令；移动台接收到功率控制命令后调整其发射功率。 这个“测量一指示一反应”循环的周期为1 5 0 0 7 欠, s ( 1 5 k i - i z ) ，比任何较明显的路径损耗 2 圜 第1 章绪论 的改变都要快。这样闭环功率控制就能够有效防止在基站接收的所有上行链路信号中出 现功率不平衡的现象。外环功率控制根据各个单独的无线链路的需要来调整闭环功率控 制的s m 目标值。其目的是取得恒定的链路质量，通常定义为某个误码率( b e r ) 或误 块率( b l e r ) 。 ( 3 ) 切换控期 当一个移动台从一个基站的覆盖范围移动到另外一个基站的覆盖范围时，通过切换 来保持移动台与基站的通信。切换分为软切换、更软切换和硬切换三种方式。 软切换是当移动台从一个蜂窝移动到另一个蜂窝时不中断呼叫，移动台可以同时与 多个基站连接。更软切换则是一种蜂窝内的切换，发生在两个扇区或三个扇区之间。这 种类型的切换不涉及无线网络控制器( r n c ) 。硬切换是指在与新基站建立连接前中断 与原基站的连接的切换方式。 未来的通信系统所能服务的业务种类越来越多，不同的业务对通信质量的要求不 同，在触发切换请求时，针对不同业务的特性应做不同的处理。如何实现各种业务的无 损切换将成为未来移动通信系统能否成功提供多媒体业务的重要问题。 ( 4 ) 负栽控制 无线资源管理功能的一个重要任务是确保系统不要过载，保持系统运行的稳定。如 果系统规划适当，接入控制和分组调度就能工作得很好，过载的情况就能避免。但是如 果遇到了过载的情况，负载控制功能将系统迅速返回到无线网络规划定义的目标负荷 值。下面是为了减少负荷而采取的必要的负荷控制措施： 下行快速负载控制：拒绝执行来自u e 的下行功率增加命令； 上行快速负载控制：降低由上行快速功率控制使用的目标e c h o ； 降低分组数据业务的吞吐量： 切换到其他w c d m a 载波； 切换到g s m 系统； 减少实时业务的比特速率； 以受控方式阻止低优先级的呼叫。 3 东南大学硕士学位论文 ( 5 ) 分组调度 目前，基于分组的多媒体业务正蓬勃发展，为了适应这种应用需求，保证实时的、 非实时的、高速的、低速的不同业务f 勺q o s ，并同时对无线资源加以优化使用，需要采 用流量控制技术，结合无线链路特性，对分组进行调度。分组调度的功能包括【1 】： 在分组用户之间共享可用的空中接口资源； 确定用于每个用户的分组数据传输的传输信道； 监视分组分配和系统负载。 一般分组调度有两种方式：码分或时分。在码分方式下，大量的用户可同时使用一 个低速率信道。当用户容量需要增加时，码速率就要降低。在时分方式下，在某一时刻 所有资源可被分配给一个或少数的几个用户，这样某些用户可用一个非常高的速率传 输。当在时分方式下用户数增加时，每个用户都要等待较长的时间来传输。在h s u p a 系统中，对系统资源即总传输功率资源的处理与h s d p a q 6 处理完全不同，在下行链路中， 功率资源是集中的，而在上行链路，每个用户都有自己的功率资源；因此纯时分的调度 方式在h s u p a 中意义不大。更多的研究倾向于码分的调度方式。 1 1 2 无线分组调度 传统的无线分组调度放在r n c 中进行 时，不能快速地反映当前时变信道的状况， 但是在r n c 控制分组调度会引入一定的延 因此难于进行快速的链路自适应和快速分组 调度。在h s u p a 系统中，快速分组调度功能不再由r n c 控制，而是被转移到n o d e b 中进 行。将分组调度功能实体放在n o d e b q b ，可以直接使用物理层实时测量的信息和内部统 计信息，这样就可以及时利用不同用户的信道状况和衰落特性等信息，对系统资源进行 合理的分配，减少系统的传输延时。这种改进使网络可以更快地对负载的变化做出反应， 为各种应用分配更合适的速率，有效地控制上行链路噪声的变化率，并有可能减少上行 链路为防止过载而预留的系统资源。 分组调度器是周期性运行的，它的周期是一个可配置的参数，一般为几十毫秒到1 秒。如果负荷超出目标值，分组调度器可以通过减少分组包的比特速率来降低负荷；如 果负荷低于目标值，可以通过分配更高的比特速率来增加负荷。调度的目标是既要有效 地将小区的剩余资源用于非实时连接，又要保证干扰强度在规划范围之内，从而保证实 时连接不受影响。 4 第1 章绪论 调度器利用下列信息作为输入【2 】： n o d e b 的总功率 非实时承载利用的容量。 网络规划参数设定的目标负荷值。这个参数定义了在不影响实时连接前提下小 区能容忍的最大干扰程度。 来自用户的比特速率提升要求。 输入信息和计算原理如图1 2 所示。 调度周期 报告周期 图1 2 ：分组调度器输入信息及其计算原理 无线分组调度算法的研究比有线领域调度算法的研究稍晚一些；且与有线调度算法 有着密切的联系，不少无线分组调度算法的研究，都是基于已有的有线调度算法而展开， 并借鉴了很多有线网络环境下的研究成果；但随着研究的深入，无线环境的复杂特性使 得无线分组调度算法显示出越来越多的特色。影响无线系统的分组调度算法，使之与有 线系统的分组调度算法呈现较大差异的因素主要有： 无线链路中的突发误码； 对分组的调度区分上下行； 无线系统中的并行服务行为。 5 东南大学硕士学位论文 在无线通信中，现有技术对误码率的保证一般在1 0 - 6 1 0 。3 的水平，这种高的误码 率对差错敏感性的数据业务影响很大；而且，无线环境中，链路质量是与移动台的位置 相关的，不同移动台感受到的链路质量不一样。这对于调度算法的公平性保证有很大的 影响，往往使得保证公平的“努力”得不到相应公平的“结果”。为了实现公平性，在 链路质量差的连接恢复正常以后，应该对其进行适当地补偿。 无线分组调度是区分上下行的。对于下行方向，n o d e b 容易了解到各个业务流占用 缓存的情况，并且系统资源( 即下行总传输功率) 是集中的，n o d e b 可以精确地分配和 回收功率资源，因此容易控制系统负荷和保证各种业务的q o s 。但上行与下行链路数据 传输有着根本差别：在上行方向，每个用户都有自己的功率资源，上行业务流的信息需 要通过无线信道报告给n o d eb ，这样就引入了延时和不确定性。由于无线信道的时变特 性以及下行码资源的限制等因素，上行分组调度要相对复杂一些。 另外，在有线网络中，链路基本工作于t d m ( 时分复用) 模式，分组调度器所分配 的资源通常是时隙，一个时隙内只能允许一个用户传输数据。而在c d m a 系统中，同一 时刻允许多个用户使用不同的码道同时发送数据。在排队论中，多个服务者的情况是比 较复杂的，再考虑c d m a 系统的白干扰特性，问题将变得更加复杂。 综上所述，基于有线网络的分组调度算法不能直接应用于无线网络。有些问题可以 从现有的有线调度算法的成果中加以推广从而获得解决，而很多问题动摇了一些有线调 度问题中的基本假设。本论文在遵循分组调度基本原则的基础之上，结合h s u p a 系统， 具体问题具体分析，从多个角度进行研究并提供有效的折衷和改进的办法。 1 2 论文的研究工作 本文基于h s u p a 系统，研究了增强型专用信道( e d c h ) 的分组调度算法，论文主 要内容安排如下： 第二章叙述了无线通信系统中典型调度算法和前人的研究成果的特点与不足。第三 章描述了h s u p a 系统的基本结构、关键技术及其系统仿真平台。 第四章以公平机会调度算法和m a xp o 调度算法为参考，提出了一种时间速率混合 调度算法，该算法基于用户缓存状况将用户分组，然后基于用户请求的速率分配资源并 基于比例公平性原则进行资源补偿。最后，通过仿真，分析和比较了三种算法的性能。 第五章，对全文进行了总结。 6 第2 章无线通信系统分组调度算法概论 第2 章无线通信系统分组调度算法概论 本章首先介绍调度的基本概念，明确调度问题的根源在于对资源的竞争和分配。然 后，介绍了无线网络发展过程中出现的一些有代表性的调度算法。最后从理论上对调度 模型进行了分析。 2 1 调度概述 调度表达的是一个与时间次序有关的概念。调度算法希望解决的是在多个用户争用 有限资源时，如何确定一种服务次序。广义的调度可以跨越时间的概念而泛指对任务、 工作、资源等进行适当分配和规划来满足预定的目标，如车辆调度，操作系统中对进程 和内存的调度等。调度的要素总结起来有7 个：被调度对象、调度者、调度资源、调度 目标、调度规划、调度代价和调度结果。在无线通信系统的调度中( 上行) ，被调度对 象一般是移动台，调度者是基站，调度资源有多种如频率、时隙、码字或功率等，调度 目标可能有多个如系统容量最大化，服务质量满意度或公平性最好等，不同的调度目标 对应不同的调度规划，调度规划就是调度算法，调度代价一般是指为了获得预定的调度 目的，牺牲了某个性能指标或者增加了算法的复杂度，调度结果就是指每个被调度对象 获得的调度资源。通常，为了达到预定的调度目标，往往需要在调度代价和调度目标之 间做出一定的折中，因此调度也往往转化为优化问题【”。在h s u p a 系统中，调度器位 于n o d e b 。其调度器模型如图2 1 所示： 用户 图2 - 1 ：调度器模型 2 1 1 分组调度算法的基本概念 调度嚣 输出 分组调度算法也称队列调度算法，按照一定的服务规则对不同输入业务流分别进行 7 一，黔一 ，ji 门榭i 翌磊詈竺i 一嚣黧 东南大学硕士学位论文 调度和服务，使所有的输入业务流能按预定的方式共享交换节点的有限资源。下面对分 组调度算法所涉及的一些基本概念进行介绍f l 】。 1 连接，用户，u e 连接、用户以及l i e 等概念在仿真平台和调度算法中，通常表示的是一个意思。 在实际系统中，连接一般表示用户与网络之间的协议连接；在仿真中，连接、用户和 u e 都是被服务者的概念。 2 队列状态 分组进入系统之后，不一定能立刻发送出去，有可能会在队列中进行缓存，等待发 送。因此可以根据队列中是否有等待的分组，将队列状态分为两种：积压状态和无积压 状态。通常调度算法只对处于积压状态的队列进行调度。 3 公平性标准 调度实质是分配问题，因此必须考虑公平性。公平性的量化方法有很多，被广泛认 可的公平性判据有服务公平指数s f i ( s e r v i c ef a i r n e s si n d e x ) 和最坏情况公平指数w f i ( w o r s t e a s ef a i r n e s si n d e x ) 。本文中采用h s u p a 协议中介绍的公平性判据：归一化吞 吐量。将各个用户的吞吐量与系统平均吞吐量之比( 归一化吞吐量) 统计起来，最后考 察这些统计值的累积概率分布来判定公平性。若某一个调度算法的归一化吞吐量的累积 概率分布曲线在1 附近的阶跃幅度比其他的算法大，则表示该调度算法中多数用户的吞 吐量与系统平均吞吐量相当，因此其公平性较好。 4 工作保持型和非工作保持型 只要队列处于积压状态，就对该队列进行调度，则调度算法就是工作保持型算法； 相反，系统中有处于积压状态的队列，而调度算法并不立即响应，则这种算法就是非工 作保持型算法，周期性调度算法属于非工作保持型算法。 2 1 2 无线分组调度算法的主要特点 无线分组调度算法借鉴了很多有线网络环境下的研究成果，但毕竟无线网络与有线 网络的有着根本的差异，因此有必要从多个方面将这些不同点加以比较。 从排队论的角度来看，无线系统与有线系统的主要区别在于服务者行为方面的差 别。一条有线链路通常可以用一个以恒定比特速率进行服务的单服务者模型表示。而 8 第2 章无线通信系统分组调度算法概论 同一时刻，只能有一个业务流占用实际带宽；而在无线通信系统中，对于不同的接入方 式，用户接受服务的方式有时分、频分和码分等多种方式。从链路的角度来看，无线链 路比有线链路复杂得多，一条有线链路通常可以看作是静态的，其传送特性一般可视为 常量；而无线链路则呈现出随机时变特性。要将有线网络中的分组调度算法有效地引入 无线网络，就必须充分考虑无线网络的特殊性。下面对无线系统中一些主要的问题进行 阐述。 1 无线链路的可变性 无线网络和有线网络最大的不同就是传输链路的可变性。在有线网络中，高质量的 通信链路如光纤可以保证极低的误码率。而在无线网络中，链路质量通常与移动台的位 置和速度有相关性，再加上噪声、干扰、衰减等因素，无线信道的质量呈现出复杂的随 机时变特性。在高突发错误的情况下，一个无线链路有可能恶化到根本不能进行通信的 程度。这对于调度算法的公平性保证有很大的影响。假如每个用户占用资源的时间在概 率意义上趋于相等，但有的用户由于链路质量差，在它占用资源的时间段内得不到相应 的吞吐量，这样就出现了保证公平的努力得不到公平的结果的现象。许多学者对突发误 码影响下的公平调度算法作了比较深入的研究，公平性调度算法有公平时间调度、公平 吞吐量调度以及公平速率调度等。 2 信道模型 信道是通信系统中的重要组成部分，它通过传输媒介为信号传递提供通路。在大多 数有线信道，特别是高质量的光纤信道中，误码率很小，可以忽略，所以在有线调度算 法研究中，一般假设链路速率固定为常数。无线信道的传输特性取决于无线电波环境， 而在移动通信环境中，受多径衰落、多普勒频移等因素的影响，接收信号的包络多数情 况下呈瑞利分布，相位则呈现均匀分布。多数上层的研究，都倾向于使用简化的信道模 型如g e 模型( 即两状态的m a r k o v 信道模型) 和多状态m a r k o v 信道模型。 3 公平性保证 正如上面所述，链路质量的差别会丧失公平性并浪费系统资源，因此一个有效的无 线分组调度算法应该对出现这种情况的连接在链路质量恢复以后给予补偿。至于如何补 偿，也是一个值得深入研究的课题，一般在保证公平性的调度算法中，短期公平性和长 期公平性是主要考虑的因素。 9 东南大学硕士学位论文 4 服务质量 q o s 体现了用户对服务的满意程度。q o s 的关键指标主要包括：吞吐量、时延和分 组丢失率。3 g 系统的目标是支持多种业务，不同类型的业务有不同的时延要求。需要 提供不同的q o s 保证。当系统同时承载多种q o s 要求的业务时，网络性能优化变得比 较困难，尤其是在h s u p a 中，不同q o s 要求的业务复用在一条或多条物理信道上，这 样就削弱了业务的q o s 与物理层的无线资源控制间的关系，增加了调度的难度。 5 吞吐量和资源利用率 对于无线网络来说，最重要的资源就是带宽。一个有效的无线分组调度算法必须尽 量减少在处于错误状态的链路上进行的无效传输，同时尽量增加有效的服务分配，一旦 某个连接有空闲的容量，就应该将空闲的容量迅速分配给其他连接。这样就能使系统负 荷的目标工作点尽可能地接近最大的负荷水平，而不会增加超过负荷的概率，从而提高 系统资源的利用率。 6 复杂度 在无线网络中，调度器一般位于基站，调度方式是集中式调度。一种有效的调度算 法应力求在至少以下三个原则中取得平衡：( 1 ) 需要的控制信息尽量少( 这些信息可能包括移 动台的业务类型，信道状态等) ；( 2 ) 对资源的利用率尽可能高；( 3 ) 算法不应该过于复杂，以 便它能够高速执行。在遵循这些原则的前提下，再谋求对某些性能指标的优化。 2 2 无线领域的调度算法 2 2 1 无线分组调度算法的发展 1 9 9 7 年，l u 和b h a r g h a v a 等人以w f q ( w e i g h t e d f a i r q u e u e i n g ) 为参照，提出了 无线环境下的理想公平调度算法，s t i o i c a 和z h a n g 等人对补偿模型进行了研究，形成了 一个无线网络的分组调度算法模型，基本可分为以下五个部分： 1 无错服务模型( e r r o r - f x e es e r v i c em o d e l ) 即理想状态下的分组调度模型，在无线分组调度算法研究中作为参考。这种模型与 有线网络中基本一致，因此现有的无线公平排队算法多数采用有线网络中的分组调度算 法，如w f q ( w e i g h t e df a i rq u e u e i n g ) 和s t f q ( s t a r t t i m ef a i rq u e u e i n g ) 等算法。 1 0 第2 章无线通信系统分组调度算法概论 2 超前和滞后模型( l e a da n dl a gm o d e l ) 首先定义超前( 1 e a d i n g ) 流和滞后( 1 a g g i n g ) 流的概念。实际接受无差错服务超过 预定的无差错服务的流为超前流，而实际接受无差错服务少于预定的无差错服务的流为 滞后流。既不超前也不滞后的流，作为参考称之为正常流。算法中规定只能在超前流和 滞后流之间进行补偿，不能影响正常流所能得到的服务；而且只有当超前流主动“交出 超前份额”的时候，滞后流才能得到补偿。 3 补偿模型( c o m p e n s a t i o nm o d e l ) 补偿模型是对滞后流在其信道变为无差错( e r r o r - f r e e ) 状态后进行补偿的策略。这是 无线公平调度算法的关键部分。补偿的策略一般是采用超前流补偿滞后流的方式。当然 还有其他的补偿策略，如系统预留带宽补偿方式等。 4 时隙和分组队列( s l o tq u e u e sa n dp a c k e tq u e u e s ) 分组可能会因为错误需要重传。如果需要重传的分组排在队列中靠后的位置，那么 根据有线网络中的公平队列算法，该分组在队列中将较晚得到服务，对于时延敏感的业 务，该分组可能会超时变成无用分组而被丢弃。在无线网络中，这种情况更容易发生。 因此，在调度算法中应该保持分组顺序和排队顺序的对应关系，当分组到达后，根据分 组的顺序重新调整排队顺序。 5 信道监测和预测( c h a n n e lm o n i t o r i n ga n dp r e d i c t i o n ) 由于调度器位于基站，调度需要考虑链路速率、链路质量以及上下行的要求，因此 需要对链路质量进行测量和反馈。基站难于预测用户到基站的上行流的状态( 如何时到 达，何时传送完毕等) ，所以有必要由用户监测信道状态，预测未来信道状态，并将此 信息反馈给调度器。在此过程中需要建立适当的信道模型，研究中多数采用二阶m a r k o v 模型来描述无线信道错误。 我们可以借助这个模型对一些无线分组调度算法进行简单的分析，如i w f q ( i d e a l i z e dw t r e l e s sf a i rq u e u e i n g ) 、c i f - q ( c h a r m e l c o n d i t i ni n d e p e n d e n tp a c k e tf a i r q u e u e i n g ) 、s b f a ( s e r v e rb a s e df a i r n e s sa p p r o a c h ) 等，表2 - 1 简单比较了其中几种算 法。 东南大学硕士学位论文 表2 - 1 ：一些无线分组调度算法的比较 i w f qc i f - q s b f a 无错服务模型采用w f qs t f q 不定 无超前流的概念，只 超前滞后模型实际的服务量与理论值比较同i w f q 有滞后流 隐含的补偿，保持服务顺序，记 由超前流补由系统预留带宽，对 补偿模型录滞后流量，在链路恢复后立刻 偿滞后流滞后流进行补偿 启动发送过程 这些调度算法考虑的无线环境局限于突发链路错误的影响，链路模型多采用两态的 m a r k o v 链的信道模型，信道分为两个状态：好和坏。这个模型对实际系统是来说简单 了一些。在3 g 系统中，采用了自适应编码调制，传输格式选择等技术，使得用户的比 特速率可以动态地改变，信道的s i n r ( s i g n a l t o i n t e r f e r e n c e p l u s n o i c e r a t i o ) 值已经被 量化，再用两态的m a r k o v 链的信道模型，就不能反应s i n r 的实际变化情况，因此多 状态的m a r k o v 链也常常被用来模拟信道状态。 这个模型中没有考虑业务的优先级，在3 g 系统中，对不同业务的要求设置不同的 优先级是非常重要的。已经存在一些针对多业务分类的无线分组优先级调度算法，如 d r s ( d y n a m i cr e s o u r c es c h e d u l i n g ) 、m p f q ( m u l t i c l a s sp r i o r i t yf a i rq u e u e i n g ) 、w c f q ) ( w i r e l e s scl a s s b a s e df l e x i b l e f a i rq u e u e i n g ) 、w a f ( w i r e l e s s a d a p t i v ef a i rs c h e d u l i n g ) 等。但是上述算法重在引入优先级区分，对补偿方式未做进一步探讨。 1 9 9 9 年，c a s i m i r o 等人研究了自适应调制系统的分组调度问题，考察了轮询( r o u n d r o b i n ) 算法和最大载干比( m a xc i ) 算法下系统吞吐量的变化，并用仿真的方法研究 了m a xc i 调度算法的性能；为了提高公平性，e r i c s s o n 对r o u n dr o b i n 算法也进行了 仿真研究。可以从理论上推导出这两种基本算法的性能界限。m a xc i 调度算法基本上 给出了链路自适应系统中调度算法在容量方面的性能上界，而r o u n d r o b i n 算法则体现 了概率意义上的最好公平性。 2 0 0 0 年，j a l a l i 等人对q u a l c o m m 公司的c d m a h d r 系统提出了他们针对h d r 系 统所设计的比例公平调度算法q p f s ( q u a l c o m mp r o p o r t i o n a lf a i r n e s ss c h e d u l i n g ) ，该 算法基于s i n r 和吞吐量的测量，在调度时刻，选择一个当前s i n r 与吞吐量比值最大 的用户进行服务，该算法一定程度上改善了服务的公平性，并考虑到了“多用户分集” 1 2 第2 章无线通信系统分组调度算法概论 增益的可能性，但比例公平调度算法不是一种时延保证型的算法，对实时业务的支持能 力较差。