（计算机应用技术专业论文）基于ieee80216e的mac层qos保证机制研究与实现.pdf

哈尔滨t 稗大学硕十学何论文 摘要 i e e e8 0 2 1 6 e 是宽带无线接入协议，8 0 2 1 6 e 中的q o s 支持主要体现在 物理层、数据链路层；i e e e8 0 2 1 6 e 的m a c 层对q o s 服务流和参数配置了 完整的信令体系、基于q o s 的调度服务类别和相应的带宽请求分配运行等机 制进行了定义。但却没有制定必要的接纳控制、q o s 参数映射、拥塞控制、 分组调度算法等一系列重要的问题。因此，在现有协议的基础上提出和实现 完整的q o s 保证机制是业界研究的热点，是宽带无线接入网络大规模商用的 必要基础。 本文首先介绍了8 0 2 1 6 协议族的产生背景、发展历程和技术特点；总体 介绍一下8 0 2 1 6 e 的m a c 层协议，其中详细分析了8 0 2 1 6 e 协议规定的q o s 机制、所支持的服务类型和带宽分配机制；然后，在协议q o s 框架的基础之 上结合现有的研究成果，提出了一种新的完整的8 0 2 1 6 eq o s 架构和详细的 算法设计，包括接纳控制、拥塞控制和分组调度的设计方案及w i m a x 系统 的调度器的具体实现。最后，对实现的系统进行测试。 该调度器的实现是在z t ec b w a 系统上完成的，测试结果证明，本文的 实现算法是有一定优越性的，系统性能有了明显的提高。 关键词：q o s ；调度算法；带宽分配；接纳控制；拥塞控制 哈尔滨丁程大学硕十学俜论文 a b s t r a c t i e e e8 0 2 。16 ei sab r o a d b a n dw i r e l e s sa c c e s sp r o t o c 0 1 t h es u p p o r to fq o s o f8 0 2 16 ei sm a i n l yr e f l e c t e di nt h ep h y s i c a ll a y e ra n dd a t al i n kl a y e r t h em a c l a y e ro fi e e e8 0 2 16 ec o n f i g u r e sac o m p l e t es i g n a l i n gs y s t e ma n d f o rs e r v i c e f l o wa n dp a r a m e t e r s ；a l s o ，i td e f i n e st h e q o ss 西e 魏l i n gs e r v i c et y p e s ，t h e c o r r e s p o n d i n gb a n d w i d t hr e q u e s t d i s t r i b u t i o nm e c h a n i s m s b u tt h e r e i sn o d e f i n a t i o no fa d m i s s i o nc o n t r o l ，q o sp a r a m e t e r sm a p p i n g ，c o n g e s t i o nc o n t r o l ， p a c k e ts c h e d u l i n ga l g o r i t h m sa n das e r i e so fi m p o r t a n ti s s u e s a sar e s u l t ，t h e p r e s e n t i n go fac o m p l e t eq o sm e c h a n i s mb a s eo ne x i s t i n gp r o t o c o li sah o t s p o t a n di san e c e s s a r yb a s i sf o rl a r g e s c a l ec o m m e r c i a la p p l i c a t i o n t h i st h e s i sf i r s t l yi n t r o d u c e dt h e8 0 2 16p r o t o c o lf a m i l yb a c k g r o u n d ，t h e c o u r s eo fd e v e l o p m e n ta n dt e c h n i c a lc h a r a c t e r i s t i c s ；i n t r o d u c e st h eo v e r a l l 8 0 2 16 et h em a c l a y e rp r o t o c o lb r i e f l ya n dm a k e sad e t a i l e da n a l y s i so fq o s m e c h a n i s mo f8 0 2 16 e ，s u p p o r t e ds e r v i c e t y p e so f8 0 2 。16 ea n db a n d w i d t h a l l o c a t i o n t h e n ，b a s eo nt h ee x i s t i n gr e s e a r c hr e s u l t sa n dt h eq o sf r a m e w o r ko f 8 0 2 。16 e ，t h et h e s i s p r e s e n t san e wc o m p l e t e8 0 2 。16 eq o sf r a m e w o r kw h i c h i n c l u d e st h ea d m i s s i o nc o n t r o lm o d u l e ，c o n g e s t i o nc o n t r o lm o d u l ea n dp a c k e t s c h e d u l i n gm o d u l ea n dp r e s e n t sa ni m p l e m e n t a t i o no fw i m a xs c h e d u l e r f i n a l l y ， m a k et e s t so ni m p l e m e n t e ds y s t e m t h ei m p l e m e n t a t i o no fw i m a xs c h e d u l e ri sb a s e do nz t ec b w a s y s t e m t h er e s u l t so ft e s t sd e m o n s t r a t et h ev a l i d i t yo fa r i t h m e t i cf r o mt h i st h e s i s a n dt h ep e r f o r l t l a n c eo fs y s t e mi si m p r o v e d k e yw o r d s ：q o s ；s c h e d u l i n g ；b a n d w i d t ha l l o c a t i o n ；a d m i s s i o nc o n t r o l ； c o n g e s t i o nc o n t r o l 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中己注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：讯雷 日期： 矽口7 年砂月巧日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可口在授予学位1 2 个月后 口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：砑、爹 日期：z 9 口0 1 年2 月z ；日 导师c 签字，：莲妨 抄。7 年盯日 哈尔滨t 程大学硕十学伊论文 第1 章绪论 1 18 0 2 1 6 系列协议和w i m a x 随着通信技术快速发展和通信市场的不断扩张，未来用户的需求表现出 了一些新的特点：一方面，传统宽带固定接入用户已经不满足于仅仅在家庭 和办公室等固定环境内使用宽带服务，希望使用宽带接入移动服务；另一方 面，传统的移动用户也不满足于简单的语音、短信和低速数据服务，希望能 使用更高数据速率的服务。用户的新需求使固定宽带接入服务和移动服务在 技术和服务上呈现融合的趋势，宽带移动化和移动宽带化逐渐成为两个领域 技术发展的趋势，并互为补充、互相促进。其中i e e e8 0 2 1 6 是宽带移动化 的重要里程碑，促进了移动宽带的演进和发展。 i e e e8 0 2 委员会于1 9 9 9 年成立了8 0 2 1 6 工作组来专门开发宽带无线标 准。i e e e 8 0 2 1 6 标准，又称为i e e e 无线城域网空中接口标准，是工作于2 6 6 g h z 无线频带的空中接口规范。由于它所规定的无线系统覆盖范围可高达 5 0 千米，因此8 0 2 1 6 系统主要应用于城域网，符合该标准的无线接入系统被 视为可与d s l 竞争的最后一公里宽带接入解决方案。到目前为止，i e e 8 0 2 1 6 标准系列以及各标准所负责的领域如表1 1 所录t 】。 2 0 0 1 年，由全球一些主要的宽带无线接入设备厂商及芯片制造商共同成 立了一个非盈利工业贸易联盟组织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 e a c c e s s ，全球微波互操作性) 。目的是制定一套基于i e e e 8 0 2 1 6 标 准的测试规范和认证体系，对基于i e e e 8 0 2 1 6 标准和e t s ih i p e r m a n 标准 的宽带无线接入产品进行一致性和互操作性认证，使不同厂商的产品在经过 认证之后具有良好的互操作性，以促进宽带无线接入设备的兼容性和互操作 性，从而推动8 0 2 1 6 产品的应用。 随着8 0 2 1 6 e 技术和规范的进展，该组织的目标也逐步扩展，不仅要建 立一整套基于i e e e8 0 2 16 标准和e t s ih i p e r m a n 标准的认证体系，同时还 致力于可运营的宽带无线接入系统的研究、需求的分析、应用模式的探索、 市场的拓展等一系列大力促进宽带无线接入市场发展的工作。通常认为， 哈尔滨丁群大学硕十学伊论文 i e e e8 0 2 1 6 工作组是i e e e 8 0 2 1 6w i m a x 空中接l j 规范的制定者，而w i m a x 表1 1i e e e8 0 2 1 6 系列标准 范阑 标准编号技术领域发布酲期 1 0 6 6 g h z 固定宽带无线接入系统空 8 0 2 1 62 0 0 1 1 2 中接疆标准 将工作范围扩展到无许可频段2 l l ( 对 8 0 2 1 6 a2 0 0 3 1 8 0 2 1 6 的修正2 ) 8 0 2 1 6 c 增搬1 0 , - - 6 6 g h z 系统的详缀规范，支持 空中接口标准兼容性( 对8 0 2 1 6 的修正1 ) 2 0 0 2 1 2 支持多媒体服务帮多种物理层规范( 对 8 睨1 6 d2 4 1 0 8 0 2 1 6 和8 0 2 1 6 a c 的修改) 规定了工作在 = s f i 最小船s l o t s f 2 最小架i e s l o t 七七s 琴。最 小保证姐o t 斗薪s f 最小保证s l o t - - - s f l 接纳速率? f 1 1 七s f 2 接纳逮莉礁2 七七 s f 接纳速霸礓2 灏疆接纳速率氇x ， 接纳控制有几种不同的应用场景包括“初始接入时的d s a 接纳控制、 “基接入的用户申请变更服务流带宽时的d s c 接纳控制 和“用户终端发生 切换时的切换接纳控制”。 切换接纳判决不是考察单个服务流，而是考察当前m s 所有服务流的总 的q o s 要求。暂时定为当前m s 所有服务流的q o s 最小要求能得到满足，即 可接纳。南于大多数情况下是因为信号原因辱| 起的切换，是露l 性的，不切换 就会导致掉线。所以切换接纳门限还可以考虑适度放宽。切换完成时需要释 放原b s 接纳控制预罄的资源。 1 8 哈尔滨丁程人学硕+ 学侮论文 | 1 _ i 萱i i i 甬黼i 置i i i i i 麓篇i i i i i i 鼍麓置i i i 萱i 嗣麓i i i i i i i 黛薯i i i i i i 麓冀苗i i 表3 1 服务类型的“接纳速率 服务类型 接纳速率 u g sm a x i m u ms u s t a i n e dt r a 伍cr a t e e r t v rm a x i m u ms u s t a i n e dt r a 爆cr a t e r 册m i n i m u mr e s e r v e dt r a f f i cr a t e n r t v rm i n i m u mr e s e r v e dt r a f f i cr a t e b eo 3 。3 本章小结 本章给出了一种简单的用于w i m a x 系统的接纳控制方法，首先讨论了 w i m a x 空中接口的资源，并针对每稃服务类型的特点及和具体应焉场景描 述了接纳控制分别应该预留的带宽，然后给出了接纳控制的判决准则及其不 同情况下的实施。 1 9 哈尔滨丁程大学硕+ 学能论文 第4 章w i m a x 系统的m a c 层调度框架设计方案 协议中规定的五种数据转发服务类型的优先级依次为：u g s 、e r t v r 、 r t v r 、n r t v r 、b e 。采用绝对优先级调度的优点是可以对和有较强时延要 求的服务提供较好的时延保证。它的缺点是有可能导致其它服务的“饿死”。 为了克服这问题，首先，在准入控制中必须对高优先级的服务的总顸留速 率进行限制；其次，在连接存在的过程中，必须按事先商定的参数对服务流 的流量进行监管和调节最后，采用合适的调度算法来改善公平性。 目前，许多研究是通过采用逆差公平优先队列来改善公平性，但各个队 列的需求值设定多数的算法都是采用最大维持速率之和，这样虽然能够较好 的满足各实时服务的时延要求，但队列中的数据并不是所有时刻都要按最大 维持速率来发送才能满足时延要求的，某些时刻只要按照大于最小预留速率 并显小于最大维持速率发送即可满足时延要求。所以，考虑合理的分配带宽， 既能满足q o s 参数的约束，又能尽量多地给低优先级服务机会是本文改进的 嚣标。下面先从一般的d f p q 算法开始讨论 7 - 2 s 。 4 1 基站侧相同服务类型的调度算法设计 w i m a x 系统的q o s 调度包括基站和终端两方面的调度，基站侧的调度 包括上行带宽分配的调度和下行链路服务数据( 包括管理消息) 的调度，上 行带宽分配是基于连接进行带宽分配，但最后是按m s 授予带宽，郎m s 上 所有连接申请的带宽都加在一起分配给m s ，所以m s 在发送上行数据时也 要进行调度。本文只讨论基站侧的调度机制。 基站侧的调度分上行和下行，但调度的对象是不同的，上行是调度带宽 申请或主动授予带宽，看不到终端侧的实际数据；蔼下行则是把一些管理消 息和由服务器发过来的数据包通过空口发送给m s ，所以下行是数据驱动的。 就调度算法丽言，上下行可以采用相同的调度算法，两本章的描述以下行为 主，上行只简单描述其与下行的差异。首先介绍几个主要的调度算法，然后 再结合w i m a x 的调度机制设计各种服务的调度算法。 2 0 哈尔滨t 程大学硕十学位论文 4 1 1 主裴调度算法分析 调度要解决的主要阀题就是当现有的资源有多个用户来竞争时，以种 怎样的规则来安排合适的服务顺序。好的调度算法是优化系统漆源管理的关 键。 ( 1 ) 先来先服务队列调度算法 先来先服务( f i r s tc o m ef i r s ts e r v e f c f s ) 队列调度算法是指分组进 入队列的顺序与被传输的顺序相同。通过将分组放置到一个队列中，并按照 它们到达的先后顺序对它们进行服务。 它的特点是队罗l 管理篙单，调度实现方便；但不熊对具有不同服务等级 要求的服务流进行区别对待，即不能对不同流提供区分服务。即无法保证一 个对q o s 要求高的分组得到比一个对q o s 要求低、甚至没有q o s 要求的 分组获得更好的服务。 ( 2 ) 基于优先级的调度算法 常见的基于优先级的分组调度算法有基于优先级调度策略( p r i o r i t y q u e u e i n g ，p q ) 和q l t ( q u e u el e n g t ht h r e s h o l d ) 算法【2 9 】。 p q 算法通过对每个队列设置不同的优先级来对它们进行调度。具体的调 度规则就是按照优先级从高到低依次服务，只要更高优先级的队列非空，每 次调度时都会优先服务高优先级的欧列，一里最高优先级的队列为空，就在 剩余的队列中选择最高优先级的队列服务，这样依次类推。 p q 算法的优点在于简单，复杂性低且易实现，能够对高优先级的队列提 供充分的带宽，但是这种算法的公平性不好，一些低优先级的队列可能很长 一段时间都得不到服务，导致被“饿死 。 ( 3 ) 基于轮循昀调度算法 一般的轮询算法r r ( r o u n dr o b i n ) 先将分组分配到指定的队列，然后 对不同队列进行无区别的循环调度服务，跳过空队列。一次调度令分组， 然后下个队列。 w r r ( w e i g h t e dr o u n dr o b i n ) 算法 3 0 i 没有解决因分组长度不同两产生 的不公平性，它在r r 基础上为每个队列赋予了一个权值，同时为每个队列 维护一个记数器，初始值为权值。在每次轮循时，计数器允许非零的队列仅 2 1 哈尔滨t 程大学硕十学位论文 发送一个信元，并把计数器减l 。当所有的队列的计数器均为零时，重置为 权值。w r r 算法的例子如图4 1 所示。 2 二图弁 f 1 i t 21 2 1h 士f 3 匝翌圆廿 图4 1w r r 算法 d p - u r ( d e f i c i tr o u n dr o b i n ) 算法【3 l 】：是为了解决r r 和w r r 算法中由 于分组变长带来的不公平性，d r r 算法以字节为单位为每个队列分配一个带 宽配额，该配额的比例对应于队列服务速率的比例。同时，为每个队列维护 一个计数器，初始化为其带宽配额。每次轮循时，如果待发送分组长度小于 或等于计数器值，则允许发送，并把计数器减去此分组长度值；如果待发送 分组长度大于计数器值，则检查下一个队列，同时把该队列计数器值累加到 下一次循环。 ( 4 ) 基于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 ) 模型【3 2 】是一种理想 化的流体模型，它假设每个队列中的服务元可以无限小并且队列之间具有相 同的优先级，从而调度器可根据各队列的共享比例同时服务所有的队列，使 得各个服务流公平地共享服务器。可见，这种模型可以根据各个服务流不同 的服务参数要求比如带宽要求、时延要求等对它们提供服务。 这种模型是一种理想的模型，在实际网络中无法实现，因为队列中的服 务元不可能是无限小的，它的最小调度粒度是分组。为了将模型应用到实际 的网络中，继而出现了一类在分组环境中逼近g p s 的分组调度算法。常见的 基于g p s 模型的算法有加权公平排队w f q t 3 3 】( w e i g h t e df a i rq u e u i n g ) 、随机 公平排队s f q t 3 4 】( s t o c h a s t i cf a i rq u e u e i n g ) 、无线注水公平排队w f 2 q t 3 5 1 ( w o r s t c a s ef a i rw e i g h t e df a i rq u e u i n g ) 等。考虑到无线信道特征，人们还提 出了理想加权公平排队( i w f q ) 、独立于信道状态的公平排队( c i f q ) 、基 于服务器的公平算法( s b f a ) 和改进的基于信道状态的包调度( i c s d p s ) 哈尔滨t 程大学硕十学佗论文 算法【3 6 】【3 7 】【3 s 1 。其中w f q 算法应用较。泛。 ( 5 ) 基于时延的调度算法 基于时延的算法首要的目的就是为服务流提供时延保障，很适合对实时 性要求高的服务。e d f ( e a r l i e s td e a d l i n ef i r s t ) 算法 3 9 1 是一种常用的基于时 延的算法。 基于时延的算法的基本思想是：每个队列被分配一个时延参数作为时延 上界，对应到达该队列的每一个分组可以通过计算得到一个时间标签作为服 务的截止期限( d e a d l i n e ) ，e d f 算法每次选择有最小d e a d l i n e 的分组进行调 度，也就是优先调度最早达到截止期限的分组。可见该算法主要是为服务流 提供时延保障，适合有实时性要求的服务。 ( 6 ) 基于衰落信道的调度算法 基于衰落信道的调度算法主要包括最大c i ( m a xc i ) 算、法【o 】、比例公 平( p f s ) 算法【4 l 】、l w d f m - l w d f ( m o d i f i e dl a r g e s tw e i g h t e dd e l a yf i r s t ， 改进的最大加权时延优先) 算法和e x p ( e x p o n e n t i a lr u l e ，指数规则) 算法 4 2 4 3 1 1 4 4 。一开始这些算法都是为了解决h d r c d m a 系统中下行共享数据服务 信道上的无线调度问题而提出的。例如，比例公平调度算法就广泛应用于 c d m a 2 0 0 0l x e v d o 和h s d p a 系统中。这些算法都是以时隙为单位进行调 度，每个时隙开始时，调度器选择优先级最高的服务流提供服务。服务流的 优先级是依据调度算法的计算公式得出的，每时隙更新一次，不同的调度算 法下系统吞吐量和q o s 保证程度也不同1 4 5 1 。 最大c i 算法 与有些文献中的最大速率优先调度算法策略相同，能最大限度提高系统 吞吐量，但服务流间无任何公平性。服务流相关的优先级参数是载干比，设 c i r f 俐为用户的载干比，则它的调度准则为：j = a r g m a xc i r ，( t ) 。 比例公平算法 比例公平调度( p r o p o r t i o n a lf a i rs c h e d u l i n g ，p f s ) 将当前信道质量和以 往系统提供给服务流的平均吞吐量的比值作为优先级参数，它权衡了各服务 流吞吐量和系统吞吐量的关系，对服务流之间的公平性提供了一些保证。在 瞬间向具有最好信道条件的用户发送数据，这样在每个瞬间都可以达到最高 的用户数据速率和最大的数据吞吐量，同时也考虑了对每个用户的公平性， 哈尔滨丁程大学硕十学位论文 在短期内以信道条件为主，长期则兼顾到对所有用户的吞吐量，是系统获取 最大吞吐量和公平性的一种折衷算法。但是对具体的q o s 指标没有保证，而 且只适用于单服务。 目前已经出现了一些改进的比例公平调度算法，可以满足服务流的q o s 要求( 如最小预留速率) ，但仍没有一种比例公平算法能够提供实时服务的 最大时延保证。比例公平算法没有把服务流的时延特性考虑进去；l w d f 算 法考虑了时延特性；m l w d f 算法不仅考虑了时延特性同时具有比例公平特 性。 l w d f m l w d f 算法 l w d f m l w d f 算法是参数化的f i f o 调度算法，其中m l w d f 算法 考虑了无线信道的时变特性。l w d f 算法考虑了每个服务流的时延方面的公 平性，但没有考虑无线衰落特性。改进后的l w d f 算法，即m l w d f 算法 跟l w d f 相比提高了信道利用率( 系统吞吐量) ，补偿了滞后流。 z x e 算法 e x p 算法在m l w d f 算法的基础上又进行了改进，e x p 算法是比例公 平机制与时延平衡机制的结合。可以证明e x p 算法下系统吞吐量比m l w d f 算法下的稍差，但每个服务流上时延特性更好。 4 1 2 一种可用于余留调度时期的综合调度算法 所谓“余量调度”是指在满足预留速率和时延等q o s 要求以后的调度阶 段。综合调度算法的公式为： p r i 。r i t y 。( f ) = 旯瓦o ) + 三 三筹( 4 1 ) 夺 c h c o n & ( f ) 一在t 时刻用户k 的信道状况；在w i m a x 系统下可以取为 当前可提供给用户k 的最大传输速率，与载干比( “力相对应，反应目 前的信道状态，系统中对应物理层的最大传输能力，根据调制编码方式 和重复次数换算出； 砀“力在f 时刻用户k 的历史流量； 聪矿一在t 时刻用户k 从上次调度以来等待的时间； p r i o i r t y k ( f 卜在t 时刻用户k 的综合优先级； 哈尔溟t 程大学硕十学位论文 p f s 的实现 设一个系统中有个用户，p f s 算法给小区内每个用户k 分配一个相应 的优先级p p f & ( t ) ，在第t 时刻时，调度器选择小区所有用户中优先级p p f s k ( t ) 最大的用户接受服务。令式( 4 1 ) 中2 = 0 ，= 1 ，v = l ，p f s 算法的优先级定 姚 州垆等 ， c h c o 删为当前可提供给用户i 的最大 传输速率，与载干比( c o k ( t ) 相对应。反应目前的信道状态，系统中对应物理 层的最大传输能力，具体实现时用该用户k 当前支持的调制编码方式和重复 次数换算出一个值代替：c h c o n d k ( t ) = 触堀制方苟- f - s l o t 可露裁崩嬲 重复次数其中r h k ( t ) 为用户k 在t 时刻的加权平均传输速率，计算公式为： 11 t h k ( t ) = ro ) = ( 1 一) r to 一1 ) + ( ) t r a n s r a t e k ( f 一1 ) ， l c l c 具体实现时t r a n s用本帧给用户的所有类型连接实际分配的r a t e k ( t - 1 ) kb e 带宽资源的总和代替。 m a xc i 的实现 设一个系统中有个用户，m a xc i 算法给小区内每个用户k 分配一个 相应的优先级己。m ( f ) ，在第f 时刻时，调度器选择小区所有用户中优先级 尸懈吮( t ) 最大的用户接受服务。令式( 4 - 1 ) 中2 = 0 ，= j ，v = o ，则m a xc i 算法的优先级定义为：己。i ( f ) = 1 + c h c o n d k ( t ) ，其他参数计算与p f s 相同。 公平流量的实现 设一个系统中有个用户，公平流量算法给小区内每个用户k 分配一个 相应的优先级吃的咖。( f ) ，在第t 时刻时，调度器选择小区所有用户中优先级 匕，撇。( f ) 最大的用户接受服务。令式( 4 一1 ) 中2 = 0 ，= d ，v = l ，公平流量 算法的优先级定义为：名蝴t ( f ) = r 丽1 ，其他参数计算与p f s 相同。 公平时间的实现 设一个系统中有n 个用户，公平时间算法给小区内每个用户七分配一个 相应的优先级匕们拥。( t ) ，在第t 时刻时，调度器选择小区所有用户中优先级 巴蜘。( f ) 最大的用户接受服务。令式( 4 - 1 ) 中2 = 1 ，0 ，1 ，= 0 ，公平时间算 哈尔滨t 稃大学硕十学付论文 法的优先级定义为：巳以砌已。( t ) = 瓦( f ) ，默力是在t 时刻用户k 从上一次 调度以来等待的时间，可以用帧号的间隔来代替。 o f i f o 的实现 令式( 4 1 ) 中五_ o ，g = 0 ，v = 0 即得到f i f o 算法，即先进入网络的连接， 其优先级越高，所以会先得到调度。 4 1 3 一种以速率加权的轮循调度算法 本节以b e 连接的调度为例说明以速率加权的轮循调度算法r w r r ( r a t e w e i g h t e dr o u n dr o b i n ) 是如何实现的。 普通的r r 算法是循环调度每个分组队列，一个队列每次发送一个分组， 由于分组的大小不同导致不公平；而w i 氓算法通过给定每个队列不同的权 值达到公平的目的，即分组小的队列权值高，会发送较多的分组，从而弥补 分组小带来的不公平。 b e 服务有最大维持速率这个q o s 参数，在调度时如何分配分配带宽才 算公平? 举例进行说明： 夺三个有相同最大维持速率参数的b e 连接，b e 连接的可用带宽不能 满足三个b e 用户：自然是三个用户平分带宽最公平； 令两个有b e 连接，最大维持速率参数分别为4 m 和1 m ，现在空口可 用带宽为2 m ：第一种分配方式是每个用户分配1 m ，第一种分配方 式是按1 6 m 和0 4 m 分配，哪一种公平? 速率参数配置大的连接理应获得较大带宽分配，而且根据速率大小成比 例，即上述例子中的第二种分配方式是公平的。这是本节的r w r r 算法衡量 “公平性 的准则。 由于进入w i m a x 系统m a c 层的s d u 大小不同，不能以s d u 的个数 作为权值。 w i m a x 系统是按帧调度的，即每个时间间隔发送一定量的数据。以b e 服务为例，可以用b e 服务的最大维持速率折合到每帧的b y t e s 数作为权值， 然后在每次轮循时，允许发送权值规定大小的数据( s d u 可以分片) 。 r w r r 算法的要点如下： 2 6 哈尔滨j 。挂大学硕 学位论文 夺以r r 的力式循环蛹度每个连接，每次调度其权值大小的额度： 夺当前帧没有轮循一遍，卜一帧端续本次循环； 夺每帧最后调度的连接如果没发送到其最大速率对应的b y t e s ( 驯w ) ， 则下帧继续填度孩连接： 夺考虑数据的突发性，设置个补偿值，即实现w 的，u 变。 以相同t r a f f i c p r i o r i t y 的b e 连接为例，在理想状态下( 即母次都可阻删 够权值大小的数据) 的r w r r 算法示意图如图4 2 。 + 时 ；f ：_ _ _ - _ - 曲_ - _ t 一 目42 理想状态fr w r r 算法 42 带令牌桶的d f p q ( 亏损公平优先队列) 调度架构 4 21d f p q ( d e f i c i tf a i rp r i o r i t yq u e u e ) 算法 文献f 2 5 提出的d f p q 算法是采用t h em i n i m u mr e s e r v e dt r a f f i cr a t e 用束 作接纳控制，t h e m a x i m u ms u s t a i n e d t r a f f i cr a t e 用来作谰度。) 哿调度分成两个 层次。 第层调度：按服务类型调度，r t p s 优先级i 为1 ，n r t p s 为2 ，b e 为3 ( u g s 因为是每帧调度i 习定值，敝小用考虑它怎么调) ，按此优先级川贞序峒 度， 世种业务类型的带宽t 用大小小超过一定值，所以，这里就是考虑公平 性，不管此时高优先级连接是雨有需求，转到低优先级连接的调度，使优先 级低的用户不致饿死，去除r 绝对优先级队列的缺点；第一层调度：同一优 先级队列调度时采用不同策略，n p s e d f ，n n p s w f 0 ，b e r r 。 之后，要清除超过晟大时延的数据包( 对于上 ，足m s 侧，对于f 行是基站 侧) 。 核心在于第层调度算法，具体如下：按小同用户类型，殴置不同的对 列，队列中7 i 素是每个连接的带宽申请值：按r t p s ，n r t p s ，b e 顺序调度( u g s 哈尔滨下稃大学硕十学伊论文 不用考虑) ，各队列将要被调度的数据量按各队列内所有连接的，m a x 的总和 为标准；即，设置变量d e f i c i t c o u n t e r ，第一轮：d e f i c i t c o u n t e r i 初始值为 ， q u a n t u m i ，q u a n t u m i = r 一( f ，) ，每调度一个连接，d e f i c i t c o u n t e r i j = o 减去该连接的带宽申请值。直到d e f i c i t c o u n t e r i d 、于等于零，再调下一个队 列；后续各轮：d e f i c i t c o u n t e r i 初始值为此时的q u a n t u m i + 上_ 轮乒最终 的d e f i c i t c o u n t e r i ；调度方法如上一轮。每轮调度结束的条件有四个： 令d e f i c i t c o u n t e r ( i 】曼o ； 令带宽请求队列为空； 令 空口带宽已经全部分配结束； 到了发送调度结果的时间。 文献 2 5 1 中的例子如图4 - 3 所示。 等待队列 可用带宽三删= 2 5 0 0 r 互二匝丁堑口匝工 l 矗 b e 队列( q u n t mcc b z ：5 0 0 ) l = 二匪叵 丁亘丑 臣正 d e e ic it c o t m t e r r t p s = q u m t t m r t p s 一6 0 0 3 0 0 4 0 0 ) 匝匝卫互皿皿一s e t v i c ef 1 。w d e f ic it c 。u n t e r b z ：0 1 3 0 0 二二互二二z 。= 1 2 0 0 r t p s 队列( q u n t m r t f s = 1 0 0 0 ) ，。f 二= = 二二i 2 0 0 1 嘧 1 b e 队列( o u m t u m b e = 5 0 0 ) l 二= 二j 匝正 臣口口五 d e f ic it c o a m t e r r t p s = 3 0 0 = = 互二 d e f ic it c o u n t e r b e 】= q u a i n t l l m b e 一3 0 0 4 0 0 口二口一s e r v i c f 1 。 z 廿- 5 0 0 r t p s 队列( q u a t u m r t p s = 1 0 0 0 ) d f ic it c o t t a t l r r t p s = 一3 0 0 + q u 札t u m r t f s 一2 0 0 = 5 0 0 r = = 二= 二二二 2 0 丑0i 二二回+ 一s e t v i c ef 1 0 w 知l b e 队列( 。u n t m b e ：5 0 0 ) d e f ic it c 。u t e r b e 】：一2 0 0 l 工贰一 1 广 z = 3 0 0 b e 队列( q n n t m b e = 5 0 0 ) d e f ic it c o t m t e r r t p s 】= 0 = = 互二二 d e f ic it c 0 1 】m t e r b e 】= 2 0 0 + 日u 毫n t 锄【b e 】一3 0 0 = 0 回+ 一s e r v i c e f 1 0 * | 图4 3d f p q 算法示例 哈尔滨i ：稷入学硕十学傅论文 4 2 2 带双令牌桶的d f p q 调度算法 除了b e 服务，其它服务的q o s 参数中都有最小预留速率翻最大维持速 率，最小预留速率是必须要满足的；同时，要考虑实时服务的时延参数。假 定最大维持速率能够满足所有状况下的时延，所以瞬时的速率要在最大和最 小之间根据s d u 队列和每个s d u 的到达时间灵活控制。 同时，在具体实现中，数据是按帧来调度的；每个帧的间隔也是根据系 统设定的，我们采用5 m s 帧。如果是按帧调度，就要考虑带宽补偿问题；由 于数据分组到达s d u 队列的瞬时速率存在不均匀性，即某些帧较少，某些帧 较多，这样按照d f p q 算法，就算按照最大维持速率计算，也不一定能满足 s d u 的时延和速率要求。造成上述情况的原因是：例如在第n 帧，某一服务 类型连接的速率之和为毖僵s d u 队列中只有m 4 的数据，则只发送了m 4 的数据，而下一帧来了j 乃懈的数据，则按照这时的d f p q 算法，只能发 送m 大小的数据，则这两帧少发送了2 * m - 1 。2 5 m = a 7 5 m 的数据，就是说 第帧浪费了疆7 5 m 发送数据的机会。所以，在具体实现时要考虑按帧调 度的带宽补偿问题，即在第n + i 帧要补上第帧的0 7 5 m 数据发送机会。 我们的带宽补偿采用令牌桶枫制来完成。但考虑到最小预留速率和时延两个 参数的保证，所以只用一个令牌桶是不够的。本文的算法采用两个令牌桶来 保证两个q o s 参数。第一个令牌捅保证最小颈留速率，第二个令牌桶保证 s d u 的时延。第一个令牌桶按最小预留速率积累令牌，第二个令牌桶按最大 维持速率和最小预留速率之差积累令牌。具体算法描述如下。 有带宽补偿d f p q 算法也是将调度分成两个层次( 以下行为僦) ，其结构 如图4 4 所示： 第一层调度：按服务类型调度，r t v r 优先级为3 ，n r t v r 为4 ，b e 为5 ( u g s 和e r t v r 因为是固定和段时间固定比特率服务，故在d f p q 第一层调度中不讨论这两种类型服务，实际是存在的) ，按此优先级顺序调度； 第二层调度：不同服务类型连接采用不同的调度策略，此层次的调度算 法在4 。2 3 节中详细讨论。 第一层调度即寅现有带宽补偿的d f p q 算法，具体为：按不同用户类型， 设置不同的对列，队列中元素是每个连接的s d u ；按r t v r ，n r t v r ，b e 哈尔滨t 程大学硕十学何论文 稀氯孙 ( 脯三) 兰d ( p f 季) 牡自由审白白 p r i o r i t y p r i o r i t yp r i o r i t yp r i o r i t y p r i o r i t y q u e u e q u e u eq u e u eq u e u eq u e u e 图4 4 带双令牌桶的d f p q 调度架构 顺序调度，各队列将要被调度的数据量按各队列内所有连接的两个令牌桶的 令牌数为依据设置变量d e f i c i t c o u n t e r i 、q u a n t u m i 、 d e f i c i t c o u n t e ，如r l a t e n c y i 】和q u a n t u m f o r l a t e n c y i ，后两个变量是为时延参 数设置的。 第一轮调度： ， d 驴础“刀御 司初始值为q u a n t u m i ，q u a n t u m i = 尽啦砌l ( f ，) ， j = o d e f i c i t c o u n t e r f o r l a t e n c y i 初始值为q u a n t u m f o r l a t e n c y i ， ， q u a n t u m f o r l a t e n c y i = ，如砌n 2 ( i ，) 。其中，m 是第一个令牌桶的令牌 ，= o 数，2 是第二个令牌桶的令牌数，砌是每个令牌所代表的速率。为满足 最小预留速率，按q u a n t u m i 】进行调度，即使满足每个连接能够发送其最小 3 0 哈尔滨t 程大学硕十学伊论文 预留速率对应的数掂量。如果按q u a n t u m i 调度后彳i 能把所有当日订服务类型 连接中处于“时间窗口”中的s d u 全部调度完，则继续按照 q u a n t u m f o r l a t e n c y i 进行调度。 后续各轮调度： d e f i c i t c o u n t e r i 和d e f i c i t c o u n t e r f o r l a t e n c y i 的初始值分