（信号与信息处理专业论文）移动宽带无线接入系统中mac层调度算法研究.pdf

摘要 摘要 近年来，随着i n t e m e t 和多媒体技术的飞速发展，用户对带宽的要求越来越 高，无线宽带接入技术已经日益成为人们关注的热点问题。i e e e8 0 2 委员会于 1 9 9 9 冬成立了8 0 2 。1 6 工作组来专f - i n 定无线宽带接入标准，以解决最后一公里 的无线宽带接入。2 0 0 5 年1 2 胄，i e e e8 0 2 工作组在i e e e8 0 2 1 6 d 协议的基础 上提出了i e e e8 0 2 1 6e 标准，定义了一种既能提供高速数据业务又使用户具有 移动性的宽带无线接入解决方案。 由于i e e e8 0 2 1 6e 标准支持多种类型的多媒体业务，并在媒质接入层 ( m a c 层) 部分提出了要对各种不同的服务应用提供服务质量( q o s ) 保证， 因此，如何最大限度地满足各类业务的q o s 就显得尤为重要。尽管i e e e8 0 2 。1 6 e 标准中定义了服务流机制以及各类业务的关键q o s 参数，健没有定义如何调 度来达到所要求的q o s ，并把m a c 层分组调度算法设计这一重要问题留待开 发者来解决。 本文在分析i e e e8 0 2 1 6e 标准中的m a c 层q o s 保障机制和服务类型定 义的基綦窭主，对i e e e8 0 2 。1 6e 系统中的m a c 层分组调度算法进行了研究。 首先，本文提出了将指数算法( e x p ) 应用到8 0 2 1 6e 系统实时类业务调 度中的m a c 层下行调度方案，并在e x p 算法的基础上进行了改进，提出了自 适应的指数算法( a 嚣x p ) ，以增强系统公平性和降低分组等待时延。通过实时 场景仿真实验将a e x p 算法和e x p 算法、自适应比例公平算法( a p f ) 进行比 较，验证了a e x p 算法能以牺牲小部分吞吐量的代价换取用户公平性和平均分 组时延方面的性能提升。 然焉，透过借鉴混合调度的思想，本文提出了针对非实时类业务的混合自 适应比例公平调度算法( h a p f ) ，并通过在非实时类业务的场景下进行的仿真 实验对比了h a p f 算法与比例公平算法( p f ) 、a p f 算法的性能，验证了h a p f 算法在僳证非实时类业务的最小预定传输速率方面的优越性。 关键词：分组调度，服务质量，m a c 层，i e e e8 0 2 1 6e a b s t r a c t a b s t r a c t w i r e l e s sb r o a d b a n da c c e s st e c h n o l o g i e sh a v eb e c o m et h ef o c u sp r o b l e ma l o n g w i | ht h ei n c r e a s i n gd e m a n df o rb a n d w i d t h i e e e8 0 2c o m m i t t e ec o n s t i t u t e d8 0 2 。16 w o r k g r o u pt oi n s t i t u t eb r o a d b a n dw i r e l e s sa c c e s ss t a n d a r d ，p r o v i d i n gt h el a s t m i l e c o n n e c t i o nt oi n t e m e ts e r v i c e i nd e c e m b e r2 0 0 5 ，8 0 2w o r k g r o u pp u b l i s h e dt h e i e e e8 0 2 16es t a n d a r d ，w h i c hd e f i n e sa na i ri n t e r f a c ef o rm o b i l eb r o a d b a n d w i r e l e s sa c c e s sn e t w o r k s b e c a u s et h ei e e e8 0 2 + 16es t a n d a r dd e f i n e s q u a l i t yo fs e r v i c e ( q o s ) r e q u i r e m e n t sf o rd i f f e r e n tc l a s so fm u l t i m e d i as e r v i c e si nm e d i aa c c e s sc o n t r o l ( m a c ) l a y e r , i ti sv i t a lt os a t i s f yt h er e q u i r e dq o s a l t h o u g ht h es t a n d a r dd e f i n e st h e s e r v i c ef l o wm e c h a n i s ma n dt h ek e yq o sp a r a m e t e r sf o re a c hs e r v i c et y p e ，t h e p a c k e ts c h e d u l i n ga l g o r i t h mi nm a cl a y e r i sl e f tt or e s e a r c h e r sa sa l lo p e ni s s u e 。 b a s e do nt h ei e e e8 0 2 16es t a n d a r da n dt h er e l a t e dq o sm e c h a n i s m ，t h i s p a p e rf o c u s e so np a c k e ts c h e d u l i n ga l g o r i t h m si nm a cl a y e ro fi e e e8 0 2 16e s y s t e m f i r s t l y , t h et h e s i sp r o p o s e dt h ea p p l i c a t i o no fa d a p t i v ee x p o n e n t i a l ( a e x p ) a l g o r i t h m t h ea e x pa l g o r i t h mi sd e s i g n e df o r t h ed o w n l i n kp a c k e ts c h e d u l i n gi n m a c l a y e rf o rr e a l t i m es e r v i c e s t h r o u g ht h er e a l - t i m es c e n a r i o ss i m u l a t i o n ，t h i s t h e s i sc o m p a r e da e x pa l g o r i t h mw i 攮a d a p t i v ep r o p o r t i o n a lf a i r n e s s ( a p f ) a n d e x p o n e n t i a l ( e x p ) a l g o r i t h m s n es i m u l a t i o nr e s u l t sp r o v e dt h a tt h ep e r f o r m a n c ei s i m p r o v e da sf a ra su s e rf a i r n e s sa n da v e r a g ep a c k e td e l a ya r ec o n c e r n e d t h e nb yc o m b i n gp r o p o r t i o n a lf a i m e s s ( p f ) w i t ha p fa l g o r i t h m s ，ah y b r i d a d a p t i v ep r o p o r t i o n a lf a i r n e s s ( h a p f ) a l g o r i t h mi sp r o p o s e df o rt h es c h e d u l i n go f n o n - r e a l - t i m es e r v i c e s t h en o n - r e a l t i m es c e n a r i o ss i m u l a t i o ni sd e s i g n e d ，a n dt h e s i m u l a t i o nr e s u l t sd e m o n s t r a t e dt h ep r o p o s e da l g o r i t h mh a sa d v a n t a g e si nt e r m so f s a t i s f y i n gt h em i n i m u mr e s e r v e dt r a f f i cr a t ef o rn o n r e a l t i m es e r v i c e s 。 k e yw o r d s ：p a c k e ts c h e d u l i n g , q o s ，m a cl a y e r , i e e e8 0 2 。16e i l 学位论文版权使用授权书 本入完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供冒录检索以及提 供本学位论文全文或者部分的阅览服务；学校有权按有关规定向国 家有关部门或者机构送交论文的复印件和电子版；在不以赢利为目 的的前提下，学校可以适当复制论文的部分或全部内容用于学术活 动。 姗繇崔窘吩 曙年；月c 户日 同济大学学位论文原创性声明 本人郑重声明：所里交的学位论文，是本人在导师指导下，进 行研究工作所取得的成果。除文中已经注明引用的内容外，本学位 论文的研究成果不包含任何他人创作的、已公开发表或者没有公开 发表的作品的内容。对本论文所涉及的研究工作做出贡献的其他个 人和集体，均已在文中以明确方式标明。本学位论文原创性声明的 法律责任由本人承担。 学位敝作者答名：孚穿吁 参扩年多月，笋日 第1 章绪论 1 1 研究背景和选题依据 第1 章绪论 随着i n t e m e t 和多媒体技术的飞速发展，用户的数据业务量迅猛增加，用户 对带宽的要求越来越高。目前各国的核心网络建设均已初具规模，宽带有线骨 干网络技术逐渐成熟，以光缆为主体的骨干网基本可以满足当前通信的需求。 但是在接入网方面，宽带接入的“最后一英里”成为了网络传输性能和多业务 集成的主要瓶颈。 在上世纪9 0 年代末和本世纪初，无线局域网( w u 州) 横空出世，它具有 网络铺设简单，并能提供高速无线接入等特点，从而使人们感受到了宽带无线 接入技术蕴涵的巨大潜力。w l a n 的缺陷主要在于覆盖范围较小，主要适合于 热点地区的覆盖。为了能够提供一种大范围( 几公罩到几十公里) 的覆盖，i e e e 8 0 2 局域网城域网标准委员会于1 9 9 9 年建立了8 0 2 1 6 工作组，专门负责为 1 0 6 6 g h z 频段的宽带无线接入的无线接口及其相关功z 日匕l - , 制定标准。基于i e e e 8 0 2 1 6 标准【卜2 】的宽带无线接入城域网( b r o a d b a n dw i r e l e s sa c c e s sm e t r o p o l i t a n a r e an e t w o r k ，b w a m a n ) 技术提出的w i m a x ( w o r l di n t e r o p e r a b i l i t yf o r m i c r o w a v ea c c e s s ，全球微波接入互操作性) 技术，是一种针对微波和毫米波频 段而提出的新的空中接口标准。它实现了2 一l l g h z t l e 视距( n l o s ) 传输和1 0 - - 6 6 g h z 的视距( l o s ) 传输，峰值带宽可达7 5 m b p s 。由于这种技术有覆盖面 广、带宽高、部署有效和维护成本低等优点，已经成为目前已成为解决接入“最 后一公里”问题的重要手段p j 。 从2 0 0 1 年1 2 月最早发布的i e e e8 0 2 1 6 标准开始，连续有多个修订版和新 版本被推出。最近的两个重要版本是：2 0 0 4 年l o 月j 下式推出的i e e e8 0 2 1 6 2 0 0 4 标准【l 】( 又称8 0 2 1 6 d 标准) 和2 0 0 5 年1 2 月7 日发布的i e e e8 0 2 1 6e 2 0 0 5 标 准【2 】( 又称8 0 2 1 6e 标准) 。 i e e e8 0 2 1 6 2 0 0 4 标准对2 - 6 6 g h z 频段的空中接口物理层和媒质接入层 ( m a c 层) 做了详细规定，定义了支持多种业务类型的固定宽带无线接入系统 的m a c 层和相对应的多个物理层，属于固定宽带无线接入规范，是相对比较成 第1 章绪论 熟并且最具实用性的一个标准版本。在移动性方面，该标准仅支持游牧和简单 移动模式。 i e e e8 0 2 1 6e 2 0 0 5 标准是作为i e e e8 0 2 1 6 2 0 0 4 的增补方案，它在2 6 g h z 的特许频段内支持移动终端，提供了一种既能提供高速数据业务又使用户 具有移动性的宽带无线接入解决方案。 由于i e e e8 0 2 1 6e 标准支持多种类型的多媒体业务，并在m a c 层部分提 出了要对各种不同的服务应用提供服务质量( q o s ) 保证，因此，如何最大限度 地满足各类业务的q o s 就显得尤为重要。虽然i e e e8 0 2 1 6e 协议中对动态业务 流机制和各类业务的关键q o s 参数进行了定义，但仅仅是提出了一个设备提供 商需要达到的标准，并没有定义完整的q o s 实现方案，而是把分组调度算法这 一重要问题留待开发者来解决。 同时，虽然有线网络领域的分组调度算法研究已经较为成熟，但无线网络 中的分组调度算法仍然当前的研究热点之一【4 】。这是因为，在无线网络中实现 q o s ，除了像在有线网络中那样考虑带宽、延迟、延迟抖动等，还必须要考虑到 无线链路的低可靠性、功率和缓存的制约、移动终端设备的移动性等问题，以 求在实现用户q o s 要求的同时，公平、有效地使用宝贵的无限资源，因而具有 更大的挑战性。 不仅如此，无线系统的分组调度技术是影响系统性能的关键部分，在很大 程度上决定系统的效率和资源利用率【4 5 1 。i e e e8 0 2 1 6e 标准所定义的移动宽带 无线接入系统中为各类业务所定义的q o s 需求包括不同用户的可变速率、不同 时延要求等方面，因而也就对能够保证业务q o s 的无线分组调度设计提出了新 的要求。虽然目前无线网络领域有很多不同的调度算法，但绝大部分不是针对 i e e e8 0 2 1 6e 系统所设计，也就没有顾及协议为各类业务应用所定义的关键q o s 参数，所以，现有的无线网络调度算法并不能直接应用到i e e e8 0 2 1 6e 所定义 的移动宽带接入系统中。 因此，有必要根据i e e e8 0 2 1 6e 所定义的移动宽带接入系统的特点来设计 合理有效的m a c 层分组调度算法和调度方案。基于这一点，本文在分析i e e e 8 0 2 1 6e 标准中的m a c 层q o s 保障机制和服务类型定义的基础上，对m a c 层 的分组调度算法及调度方案展开研究。 2 第1 章绪论 1 2 国内外研究发展状况 根据分组调度算法的应用领域，可以分为针对有线网络的分组调度算法和 针对无线网络的分组调度算法。从分组调度的研究发展状况来看，它在有线网 络中的发展已经比较成熟。有线网络中的分组调度作用更大程度上是避免拥塞， 为到达交换节点的各个连接选择下一次转发的路由和服务顺序。而在多级业务 的无线移动网中，算法复杂度体现在调度策略和服务机制上，同时，由于在无 线网络中信道的参数具有时变特性，设计优良的调度算法将遇到更大的挑战性。 在有线网络中已提出了大量的调度算法，根据调度算法的服务规则、调度 目标，可以大致分为四类【4 】。 第一类是基于轮循( r r ：r o u n dr o b i n ) 的调度算法。传统的轮循算法对不 同队列进行无区别的循环调度服务，在队列中如果不同的队列具有不同的分组 长度，则分组长度大的队列可能会比分组长度小的队列接受更多的服务，使队 列之间产生不公平的现象；而且这种算法不能对业务提供延时保证。为了改进 r r 算法的延时特性和其在变长分组环境下的不公平性，出现了一些改进型的算 法，如加权轮循算法【5 】、差额轮循算法( d r r ：d e f i c i tr o u n dr o b i n ) 【6 1 、紧急 轮循算法( u r r ：u r g e n c yb a s e dr o u n dr o b i n ) 【7 】。这些算法力图在尽量保持r r 算法实现简单性的同时，从不同的方面改善r r 算法的延时特性和其在可变长分 组环境下的不公平性。 第二类是基于广义处理器共享( g p s 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 ) 模型 的分组公平排队( p f q ：p a c k e tf a i rq u e u i n g ) 调度算法。g p s 是一个理想化的 流模型8 1 ，它根据各队列的共享比例对所有的活动队列同时服务，能使各业务流 真正公平地共享链路带宽，且它对每个队列的业务流都保证明确的端到端的延 时上限。g p s 模型是流系统，但是实际的系统都是分组系统，即在任何给定的 时刻只能有一个分组可以得到服务，分组的传输不能被抢占。基于该流模型， 出现了一类用来逼近g p s 模型的分组调度算法：p f q 算法【9 。17 1 。但这类算法通 常计算复杂度较高，系统开销较大，给硬件实现带来了较大的不便。 第三类是基于延时的调度算法。基于轮循和g p s 模型的调度算法可以看成 是基于速率的调度算法，它们通常通过为每个队列提供一定的速率保证来达到 提供延时保证的目的。而基于延时的调度算法则是以为各队列直接提供延时保 证为目的，这类算法的代表是最早期限优先( e d f ：e a r l i e s td e a d l i n ef i r s t ) 调度 第1 章绪论 算、法【1 8 1 以及h z h a n g 等人提出的r c s ( r a t e c o n t r o l l e ds e r v i c e ) 调度算、法【1 9 l 。 第四类是基于服务曲线的调度算法【2 0 。2 2 1 。g p s 模型的局限性在于业务只用 了一个参数( 速率) 来指定，使得延时与带宽的分配互相藕合在一起，也就是 说低延时就需要高带宽。这对于低延时、低带宽的业务来说就不能有很高的资 源利用率。为了解决这个问题，c r u z 首先提出了服务曲线的q o s 模型【2 3 1 。 以上这些算法虽然不修改或者稍微修改就可以适用于网络容量随时间变化 的状况，但是它们不能处理与位置相关的容量变化以及突发信道错误，而无线 信道的容量不仅随时间变化，而且信道错误是与位置相关的，并且是突发的， 因此这些算法不能直接适用于无线网络坏境。 现有的无线网络调度算法大部分是从上述有线网络的公平调度算法演化而 来，但是无线网络中的分组业务调度更侧重于对系统整体性能和业务服务质量 的保证，为业务在空中接口传输时选择合理的无线参数配置，算法的复杂度体 现在调度策略和服务机制上。由于无线网络信道的参数的时变性特性，对调度 算法的设计要求就更高。 根据无线网络调度算法所研究的对象是否仅限于m a c 层，可以将调度算法 分为集中在m a c 层的调度算法和结合跨层优化而设计的调度算法两类。 在最近的研究中所提出的几种集中在m a c 层的调度算法 2 4 - 2 9 】，一般都是 从q o s 的要求出发，提出一种调度体系结构和几种针对不同业务类的调度策略。 在调度架构中，加入了流量调节模块、缓存管理模块、接入控制模块和链路状 态监测模块等，以协助调度器更有效地运作【2 5 1 。在调度策略方面，考虑到无线 链路的特殊性，在各种业务内部并且分别采用现有的一些不同的调度方法和补 偿策略，以便在满足q o s 要求的同时，能够提高系统吞吐量，保障公平性【z 6 | 。 结合跨层优化而设计的调度算法通常认为有效的层问结合技术将实现各层 的q o s 无缝融合，因此，跨层优化、层间结合可以保障不同层面的q o s 需求， 结合跨层优化技术的调度算法由此也成为研究热点之一【3 0 。3 4 j 。这类调度算法可 以分为三类：结合物理层技术而设计的优化调度算法、结合网络层技术而设计 的优化调度算法和同时结合物理层网络层而设计的优化调度算法。其中，结合 物理层技术的跨层优化调度算法【3 0 3 2 】通常将物理层与m a c 层的资源分配结合 起来考虑，根据用户实时信道状态信息，动态地分配子载波、比特和功率，可 以提高系统的频谱效率，并在最大化系统的功率效率、保证q o s 和维持公平性 方面有较好的折衷。结合网络层技术的跨层优化调度算法【33 j 的主要思想是在考 4 第1 章绪论 虑了网络层采用的拥塞控制机制后，认为有时延要求的业务和尽力而为类业务 应该分开调度，并提出应对实时性业务采用基于时延的调度算法，以避免网络 层出现拥塞，并据此提出了一种为不同业务类分配不同的权重系数的调度算法， 以同时在吞吐量和公平性方面获得令人满意的表现。而同时结合物理层网络层 而设计的优化调度算法【3 4 】贝0 在跨层优化方面有更大突破，其主要思想是通过同 时考虑物理层的信道特性、m a c 层的调度策略以及网络层的各类业务特性来探 讨系统性能，对物理层的信道进行了建模，并采用马尔可夫过程来对无线数据 网络种的业务行为进行建模，并在此基础上，选取了几种较为经典的调度算法 作为m a c 层的调度策略，以借此分析物理层和网络层可能对调度结果带来的影 响，从而得到调度算法的优化方向。 无线网络的体系结构也会对调度规则的设计产生影响，从这个角度出发， 无线网络的分组调度算法可以可分为集中式调度算法和分布式的调度算法两 类。 集中式调度算法是针对集中式无线网络而设计的。集中式无线网络一般由 若干小区组成，每个小区由一个基站负责调度上行和下行链路传输，邻居小区 在不同的逻辑信道上传输，小区内的移动终端只能和基站进行通信。在以往的 研究中已经提出了多种无线公平调度算法【3 5 枷】，它们的主要思想都是在有线公 平调度的基础上，针对无线信道的错误与用户的位置相关，优先发送信道无错 的流，推迟发送信道错误的流，然后在以后的时间对推迟发送的流做出补偿， 以提高系统的吞吐量，提供长期和短期公平。目前常用的公平调度算法可以从 三个方面来分析：无错服务方耐3 5 钾】、领先和落后方式方面和补偿方式等方 面【3 9 舶】。 分布式的调度算法应用于分布式无线网络中【4 卜4 2 1 。由于分布式无线网络的 主要特点是没有预先存在的控制中心，无线终端以分布的方式交换信息，网络 拓扑结构随无线终端的运动而不断变化，而因为无线信号的传输的局部广播特 性，位置相邻的终端的数据包的传输存在着竞争。因此，在分布式无线网路中， 需要为空间竞争的流提供公平的信道分配。现在已有的一些分布式无线公平调 度算法可以分为两种，即：支持共享信道的包调度【4 i 】和多信道的包调度【4 2 1 。 上面提及的集中式以及分布式的无线网络调度算法都是以有线网络的公平 调度算法为基础，针对它们所面临的主要问题修改而成，其中，集中式无线网 络调度算法主要考虑了无线信道的错误特点，分布式无线网络的调度算法则考 第1 章绪论 虑了位置相邻的流的竞争关系。但是，它们都没有解决在无线移动环境下如何 定义公平和q o s ，调度算法的性能与业务q o s 特性之间的关系等问题。 i e e e8 0 2 1 6e 所定义的移动宽带无线接入网络也支持集中式和分布式的组 网模式，即点到多点( p m p ) 模式和网状霹络( m e s h ) 模式。 在p m p 模式下，i e e e8 0 2 1 6e 标准并未定义上、下行带宽分配的包调度算 法。近年来，y a x i nc a o 曾提出几种宽带无线网络分组调度算法【4 3 1 ，k i t t i w o n g t h a v a r a w a t 和a u r ag a n z 曾提出了一套专门针对i e e e8 0 2 。1 6 酶调度解决方 案【蚓，为i e e e8 0 2 1 6 定义的所有实时应用提供服务质量保证。该方案在上行链 路包调度( u p s ) 机制使用了e d f ( e a r l i e s td e a d l i n ef i r s t ) 算法【l 州和w f q ( w e i g h t f a i rq u e u e ) 算法f 9 】。但是，e d f 算法没有考虑到焉户的优先级需求，丽w f q 算 法复杂度太高，不利于硬件实现。 在m e s h 模式下，对于调度机制的信道资源调度算法研究的相对较少，其中 有文献提出考虑路幽和调度的结合的算法【4 5 1 ，也有文献引入频谱重用的算法 4 6 1 。 在本文中主要研究购是p m p 模式下的调度算法，对于m e s h 模式后面将不做具 体讨论。 。3 论文主要内容 本文针对i e e e8 0 2 1 6e 标准m a c 层协议所支持的实时类业务和非实时类 业务的分组调度算法进行重点研究。主要内容如下： 通过分析i e e e8 0 2 。1 6e - 2 0 0 5 标准疆】中提出的实时类监务r t p s 的特点，将 e x p 算法与协议所定义的实时类业务的关键q o s 参数结合起来，并进行改进， 提出了基于用户最大等待时延的a e x p 调度算法以及针对实时类业务的m a c 层 下行分组调度方案。选择t d d o f d m a 蜂窝网络，在实时类业务仿真场景下进 行仿真，分析e x p 、a p f 和a e x p 三种调度算法的系统吞吐量、公平性指数、 丢包率和平均分组延时。得到的仿真结果证明，虽然a e x p 算法虽然牺牲了一 部分吞吐量，但在丢包率方面与e x p 算法性能接近，同时在平均分组时延和公 平性方面都明显优予e x p 算法，能很好的满足实时类业务的q o s 要求。 同时，在对i e e e8 0 2 1 6e 标准中提出的非实时类业务n r t p s 的q o s 需求特 性进行分析的基础上，采用混合调度的思想，提出了融合p f 算法与a p f 算法特 性的h a p f 算法，并由此设计了针对n r t p s 监务的m a c 层下行分组调度方案。 6 第1 章绪论 利用网络仿真软件，在非实时类业务场景下进行仿真，分析比较a p f 、p f 和h a p f 三种调度算法的系统吞吐量、公平性指数以及能够达到q o s 参数中要求的最小 预留速率的用户个数。得出的仿真结果表明，在吞吐量和公平性方面，h a p f 算 法是p f 算法和a p f 算法的折衷，但是就保证用户的最小预留数据速率而言， h a p f 算法表现出了明显的优越性，为非实时类的业务提供了更好的q o s 支持。 1 4 论文的结构安排 本文的结构安排如下： 第1 章介绍i e e e8 0 2 1 6e 标准的应用背景和发展状况以及研究这一标准中 m a c 层的分组调度算法的意义，并概述了目前国内外分组调度算法的研究现状， 最后综述了论文的主要内容和创新。 第2 章介绍i e e e8 0 2 1 6e 系统中的m a c 层调度方案，对分组调度技术进 行了概述，阐述了p m p 模式下的m a c 层调度机制和常用的调度策略，并详细 分析说明了几种典型的无线分组调度算法。 第3 章提出针对实时业务的改进调度算法a e x p 算法，同时提出了适用于 实时类业务的m a c 层下行分组调度方案，然后进行了针对实时业务场景的仿 真，比较了a e x p 算法和其它两种算法：a p f 算法和e x p 算法，得出仿真结果 并进行了分析。 第4 章提出了基于混合调度思想的非实时类业务调度算法h a p f 算法，并 设计了针对非实时类业务的m a c 层下行分组调度方案，然后进行了仿真实验， 验证了h a p f 算法在为非实时业务提供q o s 支持方面的优越性。 第5 章对全文进行了总结和展望，提出了进一步研究的方向。 ， 第2 章i e e e8 0 2 1 6e 系统中的m a c 层调度方案 第2 章 ie e e8 0 2 16e 系统中的m a c 层调度方案 i e e e8 0 2 1 6e 标准在m a c 层定义了面向连接的服务流机制，为各种业务提 供q o s 的保证，同时定义了各种业务的关键q o s 参数，但是标准并没有给出实 现q o s 的m a c 层调度算法和调度方案，而是把这一重要问题留待开发人员研 究。 本章将首先介绍分组调度技术的基本概念，然后对i e e e8 0 2 1 6 标准 j - 2 1 所 定义的p m p 模式下的调度机制和常用的调度策略进行研究，并对典型的无线分 组调度算法进行分析。 2 1 分组调度技术概述 调度的英文单词s c h e d u l i n g 表示的是一个与时间次序相关的概念。分组调 度要解决的基本问题就是是当多个分组业务流等待接受服务时，必须确定合理 的服务规则，安排流的服务顺序和服务时间，以满足各个业务流的q o s 要求。 广义的调度可以跨越时间的概念而泛指对任务、工作、资源等进行适当分 配和规划来满足预定的目标。调度的要素有六个：被调度对象、调度者、调度 目标、调度规则、调度代价和调度结果。调度规则，也就是调度算法，是连接 其余五个要素的纽带。调度者通过一定的调度算法对被调度对象进行控制，力 求满足特定的调度目标。作为一种控制行为，在实际系统中，调度过程总需要 付出一定的代价( 例如计算复杂度、资源等等) ，即调度代价，而最终的调度结 果也往往和调度目标有一定的差异。 之所以出现调度问题，根源在于对资源的争用。分组通信中，为了获得统 计复用增益，需要多个业务流共享带宽，所以会出现业务流的分组调度问题。 物理上，i e e e8 0 2 1 6e 系统中的分组调度主要发生在基站或移动台节点，调度 者可以看作是这些节点本身，或是驻留在其中的一段程序；被调度对象为存放 在队列中的属于不同业务流的分组，这些业务流有着不同的业务特性和对q o s 的要求；调度目标通常就是保证这些业务的q o s 和各业务流之间享受服务的公 平性；调度代价是计算复杂度和缓存区的资源占用情况。而调度结果就是经过 第2 章i e e e8 0 2 1 6e 系统中的m a c 层调度方案 调度算法控制之后，各个业务流实际获得的服务质量。 分组调度是无线网络资源管理的重要组成部分之一。有线网络中的调度算 法较为成熟，但是由于无线网络自身的特点，不能直接应用有线网络的调度算 法。由于无线信道是易发生错误的信道，干扰、阴影、衰落以及移动台的移动， 都增加了传输链路的可变性，同时，无线网络中的公平性问题也较为复杂，这 些都给无线网络中的调度算法设计带来了挑战。 一种调度算法设计之前，应该有一个优化目标，设计好之后，应该有一个 评价其优劣的标准，这就是调度算法的性能指标。衡量无线分组调度算法的性 能指标包括分组时延( p a c k e td e l a y ) 、延时抖动( d e l a yj i t t e r ) 、吞吐量 ( t h r o u g h p u t ) 和分组丢失率( p a c k e tl o s sr a t e ) 等参数。 在无线资源管理的 调度算法的研究中，需要考虑的三个重要因素是：吞吐量、公平性以及各类业 务的q o s 。吞吐量包括小区吞吐量和用户吞吐量，公平性一般认为是各用户或 不同分组业务占用信道资源的统计结果。对于公平性的衡量，根据文献【4 7 】，一 般有以下几种方式： ( 1 ) 方差指数： f = 击静刊2 = 去参 ， ( 2 ) 协方差指数： ，：苹2 胪辛 2 ， ( 3 ) m i n m a x 指数： f ：m i n s , ( 2 3 ) m a x s i ) ( 4 ) j a i n 指数： f ：睦丛旺4 ， 刀y ”s ；2 式中，f 为公平性指数，s i 为第i 个用户获得的吞吐量，n 为用户个数。 一个好的调度算法的目标是：对无错流或偶发错误流提供长期公平性和吞 9 第2 章i e e e8 0 2 1 6e 系统中的m a c 层调度方案 吐量保证；获得高效的无线信道利用率；最小化丢包率；对无错流或偶发错误 流提供延时( 抖动) 界；支持不同q o s 的多种业务类型；在移动客户端的功率 消耗尽量小；算法复杂度适中。通常一个好的调度算法并不能在上述所有的性 能指标上都取得最优的表现，而只能根据实际系统的具体要求和业务的q o s 特 性，综合权衡各个性能参数并在数者之间取折衷。 2 2p m p 模式下的m a c 层调度机制 无线网络依赖于组网结构可粗略地分为两种。一种是小区蜂窝架构，也可 称为点对多点结构( p o i n tt om u l t i p o i n t ，p m p ) ，网络中所有的节点都直接与基站 通信，由基站来控制所有的传输和资源的分配。另一种是自组网状网结构，也 可称为m e s h 结构，所有节点间通过一跳或多跳链路可相互通信。2 0 0 5 年颁布的 i e e e8 0 2 1 6e 标准的m a c 层支持p m p 和m e s h 两种模式，其中p m p 是m a c 层协议中定义的主要网络拓扑结构，即是基站一用户站结构，如图2 1 。 在p m p 结构的网络中，连接建立在基站( b s ) 和用户站( s s ) 之问，s s 问的数据传输需要经过b s 中转。由于p m p 模式能够提供较高的传输速率，多 个用户可共享网络资源，所以过去的几年罩，宽带无线接入系统大多采用p m p 模式的网络结构。 图2 1i e e e8 0 2 1 6e 协议中p m p 网络的拓扑结构 在p m p 模式卜的调度t j j l - $ 0 中，带宽请求分为两种： r e q u e s t ( 单独请求) 和p i g g y b a c kr e q u e s t ( 捎带请求) 。 、 p 、j 7 、舯冷 器、 n 队吣7 、一 第2 章i e e e8 0 2 1 6e 系统中的m a c 层调度方案 单独请求有两种头：b ri n c r e m e n t a lh e a d e r 和b ra g g r e g a t eh e a d e r 。捎带请求 在g r a n tm a n a g e m e n ts u b h e a d e r 里指出。带宽请求可以是增加的带宽请求，或总 带宽请求。捎带带宽请求总是增加的带宽请求。 基于竞争的带宽请求是总带宽请求。每个带宽授权不是发送到单独的c i d ( 连接标识符) ，而是s s 的b a s i cc i d 。s s 对所获得的带宽在多个连接中进行调 度。如果没有授权，就退避后再请求，或丢弃s d u ( 用户数据报单元) 。 轮询是指b s 给s s 分配特定的带宽专门供s s 向b s 发送带宽请求信息的过 程。这些带宽可能分配给单独的s s 或者一组s s 。与带宽授权一样，轮询也是基 于s s 的，而非基于连接。 按照轮询对象的不同，轮询可以分为：单播轮询，组播轮询，广播轮询。 单播轮询是指b s 为一个s s 单独提供发送带宽请求信息的机会。当s s 被单 播轮询时，并非有明确的消息传达这一信息，而是在u l m a p 中被分配足够用 于带宽请求的带宽。如果一个s s 拥有一个活动的u g s 连接，则不会被单播轮 询，除非它将该u g s 连接上数据包的g r a n tm a n a g e m e n ts u b h e a d e r 里的p o l lm e ( p m ) 比特置为1 。 不能获得足够的带宽对许多不活动s s 单独轮询时，有些s s 将被归到组播 中轮询，或者直接使用广播轮询。协议预留了某些c i d 专门用于组播和广播轮 询。与单播轮询一样，并非有明确的消息传达这一信息，而是在u l - m a p ( 上 行链路映射) 中分配相应带宽。区别在于，分配的带宽不是给某个s s 的b a s i c c i d ，而是分配给某个组播c i d ( 0 x f f o o 一0 x f f f d ) 或广播c i d ( 0 x f f f f ) 。 组播轮询和广播轮询都是基于竞争的。当s s 等待了一定时间后仍然没有得 到b s 的授权信息时，s s 则认为传输带宽请求信息发生了冲突。为了避免再次 冲突，发生冲突的s s 分别采用二进制指数退避算法，来选择下一个传输机会发 送带宽请求信息。 如果一个s s 当前具有活动的u g s 连接，那么它可以在u g s 连接上数据包 的m a cp d u 的g r a n tm a n a g e m e n ts u b h e a d e r 中设置p m 位，来告诉b s 它需要 被轮询以请求发送非u g s 连接的带宽请求的机会。为了减少单独轮询的带宽需 求，具有活动u g s 连接的s s 当且仅当p m 位设置为l 、或者u g s 的发送间隔 太长，不能满足s s 其它连接的q o s 时，才能被单独轮询。一旦b s 检测到这种 轮询请求，就使用单独轮询来满足请求。 b s 通过u l - m a p 信令控制上行链路信道的分配和竞争时隙的长度与位置。 第2 章i e e e8 0 2 1 6e 系统中的m a c 层调度方案 根据相应i e 的定义，竞争可能发生在初始测距和带宽请求时段。带宽请求时段 可能发生冲突的工作站主要由i e 里指定的c i d 决定。 为了减少因竞争而发生碰撞的概率，i e e e8 0 2 1 6 冲突解决的主要方法是使 用截短的二进制指数退避算法，其初始退避窗口和最大退避窗口由b s 指定。具 体值在u c d ( 上行信道描述符) 信令中指定，表现为2 的指数。例如，4 表示 窗口是0 1 5 ，1 0 表示窗口数是0 1 0 2 3 。 当要传送信息预备并进入冲突解决过程时，首先确认初始和最大退避窗口的 数值，s s 将它当前的内部退避窗口设置成u c d 定义的“请求退避丌始”值，退 避窗1 ：3 的范围是 o ，2 n - 1 。s s 随机选择退避窗口内的一个数字，这个随机数就 是下次传送信息前需要延迟的竞争传输机会数量。 例如，一个s s 初始退避窗口是0 1 5 ，假设它随机选取了数字1 l 。则s s 必 须延迟共1 1 个竞争传输机会。如果第一个可用的请求i e 可以传输6 个请求，也 即有六次发送机会，该s s 不能发送信息此时还要延迟5 个机会。如果下一个请 求i e 可以传输2 个请求，该s s 还要等3 个机会。如果第三个请求i e 可以传输 8 个请求，则该s s 在等待3 个机会后可以在第4 个机会里传送信息。 发送的同时启动重传计数器，设定为最大重传值。传输后，一旦收到数据授 权i e ，即表示冲突解决，此次带宽请求成功。如果在接收c o n t e n t i o nb a s e d r e s e r v a t i o nt i m e o u t ( 在u c dc o m m o nc h a n n e le n c o d i n g s 中) 中指定个数u l m a p 消息后仍没有收到数据授权，s s 应该认为传送数据丢失或发生了碰撞，启 动重传机制。 重传机制为，s s 将退避窗口加倍，但不得大于最大退避窗口值。s s 在新退 避窗口中随机选取一个值，重复上文的延迟传输过程。同时重传计数器减1 。 若一直发生碰撞，当退避窗口等于最大退避窗口大小时，不再增大退避窗口， 但重传仍然进行，直到重传计数器中的数值减到o 。当达到最大重传次数时，重 传过程结束。此时，丢弃带宽请求p d u ，通知上层。 如果s s 在退避过程中收到单播轮询i e 或数据授权i e ，则立即停止冲突解 决过程，使用指定的传输机会。 2 3ie e e8 0 2 16e 系统中的m a c 层调度策略 i e e e8 0 2 1 6e 标准支持5 种调度业务：主动授权业务( u g s ) ，实时轮询 第2 章i e e e8 0 2 1 6e 系统中的m a c 层调度方案 业务( r t p s ) ，扩展的实时轮询业务( e x t e n d e dr t p s ) ，非实时轮询业务( n r t p s ) ， 和尽力而为业务( b e ) 【2 】。具体业务分类如下： ( 1 ) 主动授权业务( u g s ) ：支持实时固定比特率数据流，譬如t 1 e 1 和没 有静默压缩的v o l p 等。b s 周期性地提供d a t ag r a n tb u r s ti e s 给s s ，s s 不允许 使用任何竞争请求机会。 ( 2 ) 实时轮询业务( r t p s ) ：支持实时可变速率数据流，譬如m p e g 视频流。 b s 提供周期性的单播请求机会，s s 不允许使用任何竞争请求机会。 ( 3 ) 扩展的实时轮询业务( e x t e n d e dr t p s ) ：e x t e n d e dr t p s 是一