（通信与信息系统专业论文）wimax调度算法研究.pdf

摘要 摘要 w i m a x 作为一项新兴技术已经在全球很多地方开始了布网建设，而调度技术 则关系到整个网络性能的好坏。i e e e8 0 2 1 6 e 标准定义了w i m a x 网络支持的五种 业务，给出了基站和终端之间调度所采取的信令交互的方式。但是在这样一个调 度环境下，标准没有具体给出基站的调度算法，而不同场合需要的调度算法也不 尽相同，所以针对不同的应用场景给出相应的解决方案是很有必要的。 本文首先介绍了w i m a x 调度技术的研究背景，给出了调度算法的研究现状。 然后描述了w i m a x 网络调度算法实现的机制。w i m a x 调度模块主要在m a c 层 实现。本文给出了m a c 层的分层模型，重点介绍了汇聚子层下五种业务流的特点， 列举了几种业务的q o s 参数集。接着文中结合q o s 参数的特点详细描述了分组调 度的几种算法，对它们进行了理论分析，并结合仿真结论进行对比，验证了算法 的性能，给出了各种算法的优缺点。最后在这些结论的基础上结合w i m a x 网络 自身特点，给出了一个分级调度补偿算法，并搭建了o p n e t 仿真平台进行了分析。 关键词：w i m a x 调度m a c 层q o so p n e t a b s t r a c t a sa ne m e r g i n gt e c h n o l o g y , w i m a xh a sb e e na p p l i e di nm a n yp a r t so ft h ew o r l d f o rt h en e t w o r kc o n s t r u c t i o n t h es c h e d u l i n gt e c h n o l o g yi st h ek e yo ft h ep e r f o r m a n c e o ft h ew h o l en e t w o r k i e e e8 0 2 16 es t a n d a r dd e f i n e sf i v es e r v i c e s ，w h i c hs u p p o r t e db y w i m a xn e t w o r k a n dt h es c h e d u l i n gi n t e r a c t i o na p p r o a c h e so fs i g n a l i n gb e t w e e n t e r m i n a la n db a s es t a t i o na 陀g i v e nb yi e e e8 0 2 16 e h o w e v e r , i ns u c has c h e d u l i n g e n v i r o n m e n t , t h es c h e d u l i n ga l g o r i t h m so ft h eb a s es t a t i o na r en o ts p e c i f i c a l l yg i v e nb y t h es t a n d a r d b u td i f f e r e n tc i r c u m s t a n c e sn e e dd i v e r s es c h e d u l i n ga l g o r i t h m t h e r e f o r e ， i ti sn e c e s s a r yt h a tt h ec o r r e s p o n d i n gs o l u t i o n sf i l eg i v e nf o rt h ed i f f e r e n ts c e n a r i o s t h eb a c k g r o u n do ft h ew i m a xs c h e d u l i n gt e c h n i q u e sa n dt h er e s e a r c hs t a t u so f s c h e d u l i n g a l g o r i t h m si s i n t r o d u c e db yt h i sp a p e r a n dt h e nt h ei m p l e m e n t a t i o n m e c h a n i s mo ft h ew i m a xn e t w o r ks c h e d u l i n ga l g o r i t h mi sd e s c r i b e d w i m a x s c h e d u l i n gm o d u l ei sm a i n l ya c h i e v e di nt h em a cl a y e r t h eh i e r a r c h i c a lm o d e lo ft h e m a cl a y e ra n dh i g h l i g h t st h ec h a r a c t e r i s t i c so ff i v ek i n d so ft r a f f i cf l o w su n d e rt h e c o n v e r g e n c es u b - l a y e ra r ep r e s e n t e db yt h ep a p e r a n ds e v e r a lb u s i n e s s e ss e to fq o s p a r a m e t e r sa r eg i v e n t h e ns e v e r a ls c h e d u l i n ga l g o r i t h m si nc o m b i n a t i o nw i t ht h e c h a r a c t e r i s t i c so fq o sp a r a m e t e r sa r ed e s c r i b e db yt h et e x t , w h i c hh a v eb e e na n a l y z e d a n dc o m p a r e d 晰t l ls i m u l a t i o nr e s u l t s ，t ov e r i f yt h ep e r f o r m a n c eo ft h ea l g o r i t h m s a n d t h e nt h em e r i t sa n dd i s a d v a n t a g e so fv a r i o u sa l g o r i t h m sh a v eb e e ng i v e n f i n a l l y , o nt h e b a s i so ft h e s ec o n c l u s i o n sa n di nt h ec o m b i n a t i o nw i t ht h ec h a r a c t e r i s t i c so ft h e w i m a xn e t w o r k , ah i e r a r c h i c a ls c h e d u l i n gc o m p e n s a t i o na l g o r i t h m si sp r o v i d e db y t h i sp a p e ra n das i m u l a t i o np l a t f o r mo fo p n e ti sb u i l ta n da n a l y z e d k e y w o r d s ：w i m a xs c h e d u l i n g m a c l a y e rq o s o p n e t 摘要 独创性( 或创新性) 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：习这坦 日期：垫里：呈： 垒 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文：学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名： 三l 匝丛 日期：冱z 竺：呈：! 笪 导师签名： 第一章绪论 第一章绪论 当人们正在为3 g 网络带来的便利而欢呼的时候，w i m a x 已经成为了4 g 技 术的生力军。作为一项新兴技术，w i m a x 能够在比晰f i 更广阔的地域范围内提 供“最后一公里 宽带连接性。凭借其在任意地点的l 6 英里覆盖范围，w i m a x 将可以为高速数据应用提供更出色的移动性。此外，凭借这种广泛的覆盖范围和 高速的数据速率，w i m a x 还能够为电信基础设施、企业园区和w i f i 热点提供回 程。虽然l t e 的出现势必会给w i m a x 的技术应用带来竞争，但是当前w i m a x 技术已经较为成熟且已走向商用。市场早期的领先抢占，给即将到来的4 g 通信时 代开创了宽带移动性的先河。 1 1w i m a x 技术概述 2 0 世纪9 0 年代宽带无线接入技术发展迅速，以本地多点分配系统( l m d s ) 和 多信道多点分配为代表的无线技术的市场定位为小型办公室( s o h o ) 、中小企业、 城市商业中心等用户。但是这一产业并没有像人们预期的那样进一步繁荣壮大， 个重要的原因就是没有统一的全球性宽带无线接入标准。 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 rm i c r o w a v ea c c e s s ) 全称为全球微波接入互操 作性，是基于i e e e 8 0 2 16 tl 】【2 1 标准的无线城域网技术。w i m a x 组织从2 0 0 1 年开 始制定标准，并对芯片、设备进行认证，使成本下降成为可能，w i m a x 的应用领 域也随之扩大。据统计，截止到2 0 0 2 年美国有2 4 0 0 个i s p ( 互联网接入服务提供 商) 为超过6 0 0 0 个无线接入市场服务，但是由于标准不统一，各个供应商设备昂贵， 不能互联，给用户带来了很大的负担。w i m a x 的出现正好能够解决这个问题。 2 0 0 9 年至2 0 1 3 年，移动w i m a x 用户预期将会出现高速增长。全世界，包括 移动运营商、地区通信提供商和多业务运营商在内的很多服务提供商的移动 w i m a x 已经初见成功，他们都希望在无需长时间等待l t e 的情况下，通过w i m a x 提供移动宽带业务。 w i m a x 之所以能成为新一代的无线接入技术，因为在物理层中主要采用三项 核心技术：o f d m 、时编码和链路自适应技术。 o f d m t 3 】- 【5 】技术的主要思想是在频域内将给定信道分成多个正交的子载波信 道，然后将高速数据信号转换成多个并行的低速子数据流，调制到每个子载波信 道上进行窄带传输。每个子载波信道上的信号带宽小于信道的相干带宽，因此每 个子载波信道都可以看成平坦衰落信道。由于o f d m 是一种多载波调制技术， 2 w i m a x 调度算法研究 o f d m 系统采用正交方法来区分不同子载波，子载波间的频谱可以相互重叠，这 样不但减小了子载波间的相互干扰，同时又极大地提高了频谱利用率。 空时编码技术【6 】【8 】其中核心的应用就是与多天线技术的结合。多天线技术是指 在发射端和接收端分别使用多个发射天线和接收天线，其出发点是利用多输入多 输出改善无线通信系统传输质量或提高无线通信系统传输速率。8 0 2 1 6 e 协议中支 持的m i m o ( 多输入多输出) 和a a s ( 自适应天线阵列) 两种不同的多天线实现 方式。所支持的m i m o 模式包括3 中：空时发射分集s t t d 模式、复用( s m ) 模式 和分集与复用相结合的混合( s t t d & s m ) 模式。a a s 在协议中规定的是一种可选的 技术，在上下行链路中都可以选择支持该技术。采用a a s 技术可以提高系统容量、 扩大覆盖范围、提高通信的可靠性和降低运营成本等。 链路自适应技术i9 】【1 0 j 包括：自适应调制编码( a m c ) ，混合自动重传( h a r q ) 等。 a m c 就是收发端可以根据信道的质量信息，随时改变信号调制的编码方式，以适 应不同的无线通信环境的一项技术。收发端可以根据接收或者发射的信号，或者 通过信令上报的值( 反映信道质量) 来选择一个合适的编码方式，这样能够提高 通信的质量。信道质量的反馈方式在8 0 2 1 6 e 协议中是有很多种的，例如m a c 头 的反馈，c q i c h 等。h a r q 技术充分利用前向纠错和自动重传请求的优点，提高 数据传输的可靠性和系统吞吐量。h a r q 基于信道条件提供精确的编码速率调节、 自动适应瞬时信道变化、且对时延和误差不敏感。 w i m a x 不仅技术先进，而且应用广泛。w i m a x 论坛给出了它的5 种应用场 景的定义：固定、游牧、便携、简单移动和全移动。 1 ) 固定应用场景：固定接入业务是8 0 2 1 6 运营网络中最基本的业务模型，包 括用户因特网接入，传输承载业务以及w i f i 热点回程等。 2 ) 游牧应用场景：游牧式业务是固定接入方式发展的下一个阶段。终端可以 从不同的接入点接入到一个运营商的网络中；在每次会话连接中，用户终端只能 进行站点式的接入；在两次不同网络的接入中，传输的数据将不被保留。在游牧 式及其以后的应用场景中均支持漫游，并应具备终端电源管理功能。 3 ) 便携应用场景：在这一场景下，用户可以步行连接到网络，除了进行小区 切换外，连接不会发生中断。便携式业务在游牧式业务的基础上进行了发展，从 这个阶段开始，终端可以在不同的基站之间进行切换。当终端静止不动时，便携式 业务的应用模型与固定式业务和游牧式业务相同。当终端进行切换时，用户将经 历短时间( 最长为2 s ) 的业务中断或者感到一些延迟。切换过程结束后，t c p i p 应对当前p 地址进行刷新，或者重建i p 地址。 4 ) 简单移动应用场景：在这一场景下，用户在使用宽带无线接入业务中能够 步行，驾驶或者乘坐公共汽车等，但当终端移动速度达到6 0 1 2 0 k m h 时，数据 传输速度将有所下降。这是能够在相邻基站之间切换的第一个场景。在切换过程 第一章绪论 3 中，数据包的丢失将控制在一定范围内，最差的情况下，t c p i p 会话不中断，但 应用层业务可能有一定的中断。切换完成后，q o s 将重建到初始级别。简单移动 和全移动网络需要支持休眠模式，空闲模式和寻呼模式。移动数据业务是移动场 景( 包括简单移动和全移动) 的主要应用，包括目前被业界广泛看好的移动电子 邮件、流媒体、可视电话、移动游戏、移动v o i p ( m v o i p ) 等业务，同时它们也是 占用无线资源较多的业务。 5 ) 全移动应用场景：在这一场景下，用户可以在移动速度为1 2 0 k m h 甚至 更高的情况下无中断地使用宽带无线接入业务，当没有网络连接时，用户终端模 块将处于低功耗模式。 在上述的几种应用中，w i m a x 都支持数据、语音和视频。w i m a x 独有的服 务质量保i t 正( q o s ) 、按需提供的带宽分配、自适应参数调整等特点，给组网带来更 大的灵活性。例如在语音和视频服务中，对时延非常敏感，但是对差错就不那么 敏感，而数据服务则正好相反，对时延不敏感，对差错非常敏感，w i m a x 可以根 据不同的上层应用提供相应等级的服务质量保障，提高网络吞吐容量。 1 2w i m a x 调度技术研究背景 鉴于w i m a x 技术采用o f d m a 、m i m o 等先进的4 g 技术思想，加之商用场 景的广泛应用，研究w i m a x 技术对未来无线宽带事业具有重要的意义。目前 8 0 2 1 6 e 标准对w i m a x 无线网络的p h y 层和m a c 层进行了规定，标准详细的表 述了各个子层的具体实现。其中定义了调度需要针对的五种类型的业务流：u g s 、 r t p s 、n r t p s 、e r t p s 、b e 。这几种业务流有其基本的q o s 参数要求，有的对时延要 求高，有的对吞吐量要求高，有的要求其公平性，那么这就需要对不同的业务流 采用合适的调度算法。而一些场合可能存在多种业务流并存的情况，这样就要求 基站调度的时候充分考虑基站入网范围内的所有终端，这时候要把一些调度算法 结合起来考虑实现整个网络的性能优化。但是对于调度模块，标准却没有给出具 体的实现，而针对不同的业务类型调度算法也不尽相同，所以它一直是研究的热 点。 通信系统的分组调度算法在有线网络下已经比较成熟，但是由于无线信道的 状态变化，导致系统对于吞吐量、时延、抖动等指标有一定的要求，所以无线调 度算法要比有线调度算法复杂。一个好的无线调度算法对这些指标应该都尽量满 足，才能适应无线信道的变化特点。然而w i m a x 系统有不同的业务需求，有q o s 参数的保证，所以不同的w i m a x 系统需要不同性能指标的无线调度算法。 基于上述原因，目前无线分组调度算法在国内外都是研究的热点，一个好的 调度算法能够在保证基本业务质量的前提下节省带宽资源，提高系统资源利用率 4 w i m a x 调度算法研究 等。本文研究的目的也在于充分研究各种调度算法，吸取算法的优点，结合实际 建立起一个适合w i m a x 系统的无线调度算法，以适合现在的商用w i m a x 网络。 1 3 调度算法研究现状 调度算法的作用就是在若干等待调度状态的分组或是信元中选择下一个服务 的对象，各种不同的选择方法就构成了不同的调度算法。最简单的调度算法是 r o u n d r o b i n ( r r ) 算法，无优先级别，单纯的以轮询来保障对用户调度的公平性。 后来涌现了好多r r 的改进算法。著名的有s h i m o n i s h i 等人提出的w r r 算法，但 是这种算法没有考虑时延问题。s t r a u b 等人提出的e d f 1 l 】【1 3 】算法考虑了时延的因 素，它是一种动态优先级别的算法。这些早期的算法主要是用于a t m 网络。 现在的一些无线的经典分组调度算法考虑了网络的时延，抖动等多种复杂因 素，它们更适用于无线网络。a d e m e r s 等首次提出了一种适用于i n t e m e t 网关的 i p 分组公平排队算法( f q ，f a i rq u e u i n g ) t 1 4 】【1 5 】，此算法可以使各个连接在时延、吞 吐量方面较为一致，可以防止恶意用户滥用带宽资源，具有公平性。著名的w f q 6 j 算法就是由f q 算法进行加权处理改进而来。a k p a r a k h 研究了w f q 的流体模型 g p s l l 7 l ( 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 ) ，指出w f q 算法是对g p s 算法在分组情况 上的近似。后来j c r b e m e t t 等提出了比w f q 更接近于g p s 、公平性更好的 w f 2 q 8 】算法，并提出了另外一种度量公平性的指标w f i 。 c s d p s 算法是一种基于信道状态的调度算法，常常结合r r 、e t f 、l q f 等调 度算法。后来又有i - c s d p s 以及c s d p s + c b q 等改进算法，这些都是根据无线信 道提出的实时调度算法，能满足实时业务的要求。 至今国内外对调度算法的研究有很多，各种算法的性能针对时延、吞吐量、 公平性也都不尽相同，但是对于w i m a x 网络适用的算法要根据条件来选择一些 算法进行融合，以满足业务多样化的要求，这也是本文研究的目的。 1 4 本论文的工作和章节安排 本文首先针对协议规定的m a c 层的w i m a x 调度机制进行介绍，之后主要对 无线的调度算法进行比较和研究。分析了几种经典的分组调度算法，并在仿真平 台上进行了性能验证。得出了算法在各方面的性能特点，给出了这些算法使用的 环境。最后在一个搭建的w i m a x 平台上提出了一个分层的分组调度算法，并对 w i m a x 系统调度算法进行了仿真，与p f 算法性能进行比较，从结果可以看出算 法在吞吐量、负载和时延等方面的优势。 本文下面章节主要按上面所述内容展开，在第二章中针对w i m a x 系统的调 第一章绪论 5 度机制进行描述，阐述了q o s 保证体系，根据不同业务流的特点给出了相应的q o s 参数，最后指出分组算法的制定应该满足不同的q o s 参数集的需求；第三章描述 了几种经典的分组调度算法，并对算法进行了仿真分析，给出了各种算法的优缺 点；第四章在o p n e t t l 9 】【2 0 1 平台下，针对提出的算法进行了仿真分析，给出了算法 的优缺点：最后在第五章对所做工作进行总结，并对未来的工作进行展望。 第二章w i m a x 调度机制 7 第二章w i m a x 调度机制 i e e e 8 0 2 1 6 e 协议是在8 0 2 1 6 d 协议基础上，在无线宽带接入的前提下引入了 移动性。i e e e 8 0 2 1 6 e 协议主要定义了接入网的物理层和数据链路层的标准和接 口。2 1 节中介绍了m a c 层的分层模型；2 2 给出了调度中使用的分类器规则，因 为分类器是针对相应的业务对数据包进行分类的，所以业务类型不同调度算法也 不尽相同；2 3 节中给出的带宽资源是调度中直接进行操作的对象，很多算法是要 根据带宽请求的情况采取相应的分配带宽的策略；q o s 保证体系是调度算法评价 的标准，每一种调度算法针对不同的业务必须满足特定要求，这在2 4 节给出了描 述。 2 1 协议分层模型 m a c 层包括三个子层，如图2 1 所示。 图2 18 0 2 1 6 e 的协议栈和接入服务提供点( s a p ) ( 1 ) 特定服务汇聚子层( c s ) ，提供内部数据的传输或者映射，这些数据通过 c s 业务接入服务提供点( s a p ) ，完成到m a c 业务数据单元( s d u ) 的映射，而s d u 是通过m a c 公共子层( c p s ) 的m a c 接入服务提供点( s a p ) 得到的。这个过程包括 8 w i m a x 调度算法研究 对内部网络s d u 的分类和将它们与合适的m a c 层业务流标示( s f i d ) 和连接标示 ( c i d ) 进行联合，它也包括载荷压缩字头( p h s ) 的功能。c s 载荷的内部格式对c s 层来说是唯一的，并且m a c 的c p s 层没有要求可以识别这种格式，或者说从c s 载荷中解析任何的信息。 ( 2 ) m a cc p s 提供了核心的m a c 层系统接入功能，如：带宽分配、连接确 定以及连接维护。它从c s 层接收数据，通过m a c 层的s a p ，将其归类到各种特 殊的m a c 层连接。 ( 3 ) m a c 也包含了一个独立的安全子层以提供认证服务，如：安全密钥的 交换，加密数据以及物理层控制，并统计在m a cc p s 和物理层之间传输的数据。 2 2 汇聚子层中的业务分类 w i m a x 网络是面向连接的网络，它是由各种分类器规则映射到各个c i d 的。 而分类器的实现主要就是在汇聚子层中实现的。下面介绍c s 层的主要功能有： 1 接收高层协议数据单元( p d u ) 。 2 实行对p d u 的归类。 3 对基于分类的p d u 进行处理。 4 将c sp d u 投递到合适的m a cs a p 中。 5 接收来自于相同实体的c sp d u 。 发送端的c s 层是负责投递m a c 服务数据单元( m s d u ) 到m a cs a p 。m a c 层负责将m s d u 发送到同等的m a cs a p 实体中去，而这个实体是与很多功能相 对应的，如：q o s 、分片、链接以及其他与一定连接业务流特性相关联的功能。接 收端的c s 层是负责从同等m a cs a p 实体接收m s d u 并投递到一个较高层的实 体中去。 2 2 1m s d u 的格式 较高层的p d u 将会被分类，并根据分类原则以m s d u 的格式被封装。格式 如图2 2 所示。 图2 2 m s d u 的构成图 第二章w i m a x 调度机制 9 2 2 2 分类器 图2 3 分类器和c i d 映射( a s 到s s ) 图2 4 分类器和c i d 映射( s s 到a s ) 分类器实现的是这样一个过程，上层实体的m s d u 通过m a cs a p 传输到汇 聚子层。一个m s d u 被映射到一个传输连接上，在m a c 层间的实体进行传输。 映射过程是将一个m s d u 和一个传输连接进行绑定，并与相应的业务流的特性进 行关联。这个过程使得m s d u 的传输与合适的q o s 参数相匹配。如图2 - 3 和2 4 所示的，上下行的分类器通过分类器的规则把各个s d u 分配到不同c i d 的连接上。 一种分类器就是一系列适用于进入i e e e 8 0 2 1 6 标准定义的网络包的规则，它 包含一些特定协议包匹配规则( 例如：基于目的i p 地址) 。一个分类器的优先级， l o w i m a x 调度算法研究 与一个c i d 是关联的。如果是一个匹配特殊包映射规则的包，它将被传递到s a p ， 并用于在由c i d 定义的连接上进行传输。连接的业务流特性则是为包提供了q o s 参数保证。 几个分类器可用于同一个业务流，而分类器的优先级则被用于给包进行排序。 明确的排序是非常有必要的，因为分类器进行分类后的业务类型是会重复的，即 同种的业务流类型可以分别来自不同的终端。优先级不需要唯一，但是注意到同 等优先级别下，分类器下要防止分类规则的模糊。 2 3 调度和带宽分配机制 调度的过程就是要根据网络的带宽需求情况和剩余带宽的状况来决定分配带 宽的策略。w i m a x 规定了标准的业务类型，还有带宽请求和分配的方式。当带宽 请求和分配完成后，就以m a cp d u 的格式封装在物理帧之中并发送出去。 2 - 3 1m a cp d u 的格式 每一个p d u 都有一个m a c 头。头后面将会跟一个载荷m p d u 。载荷信息会 随信息量的多少而变化，所以一个m p d u 的长度是不同的。m a cp d u 的格式如 图2 5 所示，其中所跟c r c 校验是可选的。从上节中知道 m a c 头载荷c r c 校验 2 3 2 业务的调度类型 图2 5m a cp d u 结构图 调度服务就是由m a c 层调度器支持的用于在一个链接上进行数据传输的数 据处理机制。每一个链接与一个调度服务关联。调度服务由一系列q o s 参数确定， 这些参数由d s a 和d s c 消息来进行管理。 ( 1 ) 主动授权业务( u c s ) u g s 是以周期的形式传输固定的数据包的调度类型，它主要用于支持实时上 行业务流，例如t 1 e 1 以及没有静默压缩的v o i p 业务。这种业务提供固定宽度的 数据业务，并以周期的形式授予带宽，它省略了s s 进行带宽请求的开销，保证了 业务较小的延迟，这对于满足业务实时性的需求是非常有用的。b s 将在周期间隔 内分配带宽给s s 以满足最大的业务流维持速率。这种类型所必需的q o s 参数有： 最大传输速率、最大时延、可容忍的抖动、上行带宽分配类型和请求传输策略。 最小保证速率应该与最大速率相同。 第二章w i m a x 调度机制 ( 2 ) 实时轮询业务( r t p s ) 用于支持可变速率实时业务，是为满足动态的业务需求而设计的，基站为用 户提供周期性的单播轮询请求机会，用户根据自己当前发送缓冲区中数据多少， 使用该带宽请求机会发送带宽请求，基站收到用户的带宽请求后，综合考虑小区 内所有用户的请求，为用户分配上行数据带宽。此种上行调度机制禁止使用其他 竞争请求机会和捎带请求。这种业务类型所必需的q o s 参数有最小保证速率、最 大传输速率、最大时延、上行分配带宽调度类型和请求传输策略。 ( 3 ) 拓展实时轮询业务( e r t p s ) 基于u g s 和r t p s 的效率，为节省带宽请求时延，基站主动提供单播带宽分配， 与u g s 固定带宽分配不同，e r t p s 的带宽分配大小是动态的。基站周期性提供上行 带宽分配，用户可以使用该带宽进行数据传输或发送带宽请求。在缺省情况下， 基站根据该链接的最大保持业务速率分配上行带宽，用户可以使用捎带请求或在 信道质量报告( c q i c h ) 上发送码字，通知基站改变上行带宽分配的大小。u g s 和 n p s 的q o s 参数对于e r t p s 都有。 ( 4 ) 非实时轮询业务( n r t p s ) 这种业务类型支持非周期性的、变长数据报文的非实时数据业务。b s 将有规 律的为这种业务连接提供单播轮询机会，甚至在网络拥塞的时候保证上行连接可 以接受到带宽请求机会。这种业务类型所必须的q o s 参数有：最小保证传输速率、 最大传输速率、业务优先级、上行带宽分配调度类型和请求传输策略。 ( 5 ) 尽力而为的业务( b e ) b e 这种连接可以使用单播轮询所提供的发送机会，而且可以使用竞争模式来 发送带宽请求。但是单播轮询发送机会的出现取决于网络的负载情况，因此发送 该业务的s s 不能依赖于单播轮询发送机会。这种类型不需要q o s 参数的保证。 2 3 3 带宽分配和请求机制 每一个s s 在入网的时候需要建立三对业务流，分别对应三种类型的c i d ，用 于管理信息，数据业务等的传输。增加或者减少带宽请求的过程对于所有的业务 都是有必要的，除了不能压缩的固定速率的u g s 链接，因为u g s 在链接开始和 终结期间都不会改变带宽的需求。但是其他业务可以通过多种方法通过s s 得到 b r 信息给b s ，以用于增加或减少带宽请求。方法主要如下： ( 1 ) 请求( r e q u e s t s ) 请求是指一种机制，s s 可以用来通知b s 需要u l 带宽的分配。一个请求可以 来自一个带宽请求( b r ) 头或者来自捎带请求( p i g g y b a c k ) ，而后者是可选的。 因为u l b u r s t 的内容可以改变，所有的带宽请求需要根据携带的m a c 头和载 1 2 w j m a x 调度算法研究 荷的字节数目来确定。带宽请求信息可以在u l 分配期间进行传输，而不会发生在 初始化测距间隔。 b r 请求可以是新增加了多少带宽，也可以是总共需要的带宽。当b s 接收到 一个新增的b r ，它将会在当前需求的链接带宽中增加带宽请求的数量。当它接收 到的是一个总共需要的带宽的时候，它就会代替当前需求的链接带宽。带宽请求 的种类是增加的还是总共需要的，是由b r 头中的种类( t y p e ) 字段决定。因为 p i g g y b a c k e d 类型的b r 并没有类型字段，所以p i g g y b a c k e db r 的带宽请求类型总 是增加的( i n c r e m e n t a l ) 。由于请求授予的特性，协议要求s s 可以周期性的使用总 计类型b r 请求作为保证业务q o s 的一个功能。而由于碰撞的原因，带宽请求就 是要增加类型的请求。其他类型的带宽请求在这里不做过多的阐述。 ( 2 ) 授权( g r a n t s ) 对于s s ，b r s 是针对每个单独的链接的，但是每一个带宽授权是通过b a s i c c i d 发送的，而不是单播的c i d 。授权如果在单播中发送，会因为不确定性的因素导 致s s 无法执行这个授权。在所有可能的情况下，来自于b s 的信息和请求的状态， s s 可以决定实施回退或者是再次请求，或者干脆丢弃s d u 。 授权的形式可以使用广播的请求i e ，或者直接通过多播的轮询组，在者是由b a s i c c i d 。在所有情况下，可以使用请求i eb u r s t 的内容，即使一个b s 有能力再多接 收s s 的一个有效的b u r s tp r o f i l e 。而为了充分接收b u r s tp r o f i l e ，s s 应该通过有一 个d a t ag r a n ti e 在b a s i cc i d 上定义的一个间隔来传输。因此，一个s s 单播的轮 询将会通过在它的b a s i cc i d 上分配一个d a t ag r a n ti e 来实现。同时注意到在b a s i c c i d 上传输的d a t ag r a n t1 e 可以使得s s 的b r 用于它的所有连接。请求和授权的 过程如图2 6 所示。 ( 3 ) 轮询( p o l l i n g ) 轮询是这样一个过程，b s 以带宽请求为目的，向多个s s 分配带宽。这些是 针对单独s s 或者s s 组的。这种分配不是以一种明确的消息，而是包含在u l m a p 所包含的一些正中。注意到轮询是针对s s 的，但是带宽总是在b a s i cc i d 上分配。 ( 4 ) 单播( u n i c a s t ) 当一个s s 被进行单播轮询，并没有明确的消息传输到s s 。而这个s s 是通过 在一个u l m a p 消息中被分配了充足的带宽去响应一个b r 。如果s s 不需要带宽， 那么就会把分配的带宽进行补充( p a d d i n g ) 处理。s s 动态建立的u g s 业务流将不会 做单播的轮询处理，除非在一个报头中设置了p m 的b i t 位。这样将节省轮询所有 s s 的带宽。注意到单播的轮询会在每一个s s 上进行，通过直接在它的b a s i cc i d 上分配一个d a t ag r a n ti e 。单播的流程如图2 7 所示。 第二章w i m a x 调度机制 1 3 图2 6s s 请求，授权业务流框图 1 4 w i m a x 调度算法研究 图2 7 单播轮询流程 第二章w i m a x 调度机制 1 5 2 4 1q o s 简介 2 4q o s ( 服务的质量) 参数和调度类型 在现代高速宽带通信网领域，网络中承载的是复杂的混合的业务，诸如音频、 视频、数据等等，它们都在相同的介质上传输，不同的业务所需要的服务质量是 千差万别的，为不同业务提供满意的服务质量就成为网络技术中的一个至关重要 的问题。 q o s 业务是网络不容易理解的参数，必须经过q o s 映射将业务q o s 参数转换 成网络承载的q o s 业务参数。这个过程是由终端或接入设备完成的。例如，对于 交互式视频业务，终端要根据所需的图像分辨率、压缩编码算法及压缩效率，计 算出所需的峰值带宽、平均带宽等参数；交互式业务还需要有一定的反应速度， 根据这些来提出对网络总延时的要求；根据本端接收缓冲区的大小和传输速率计 算出对时延抖动的要求；另外还有根据终端和信道编码的检错、纠错能力，以及 误码对压缩图象质量和同步的影响程度，提出信元丢失率指标。 q o s 主要是为用户提供端到端的服务质量保证。在通信网络中，当分组数据通 过一个或是多个网络时所表现出来的性能属性，可以通过业务有效性、时延、抖 动、丢包率、吞吐量等参数进行描述。q o s 定义的主要参数： ( 1 ) 业务有效性，是指用户获取业务连接的可靠性。 ( 2 ) 时延，是指在两个参照点之间发送和接收数据包的时间间隔。 ( 3 ) 抖动，是指在一个节点上，发送同一组数据流中的数据包之间的时间差。 ( 4 ) 吞吐量，是指发送数据包的速率，可用平均速率或是峰值速率表示。 ( 5 ) 丢包率，是指在网络中传输数据包时所允许的丢弃数据包的最高比率。数据 包的丢弃一般是由于网络拥塞所造成的。 2 4 2 业务流 一个业务流就是一个m a c 层传输业务，它将提供单项的包的传输，要么是通 过s s 进行的上行传输，要么是通过b s 的下行的传输。一个业务流通过q o s 参数 的设置被特性化，例如延迟、抖动、以及吞吐量保证。为了在s s 和b s 之间进行 标准化操作，这些属性包括s s 要求上行带宽分配和b s 上行调度的预期行为。 业务流的一些特性化属性如下： ( 1 ) 业务流i d ( s f i d ) ：一个s f i d 被分配到每一个存在的业务流。s f i d 服务 作为一个b s 和一个s s 之间的原则性标示。一个业务流至少有一个s f i d 和一个 相关联的方向。 1 6 w i m a x 调度算法研究 ( 2 ) c i d ：传输连接的标示，只有当业务流出于a d d m i t t e d 或者a c t i v e 状态的 时候才存在。s f i d 和c i d 的关系是唯一的。一个s f i d 绝不会和多于一个传输c i d 相关联，而一个传输c i d 也不会和多于一个s f i d 相关联。 ( 3 ) p r o v i s i o n e d q o s p a r a m s e t ：一个预分配q o s 参数，它的设置意味着超出了 标准的范围。 ( 4 ) a d m i t t e d q o s p a r a m s e t ：定义了b s 的一系列q o s 参数，这些都是给b s 的预留资源。最重要的预留资源就是带宽，但是这也包括了其他的记忆单元或者 基于时间的随后需要激活的资源。 ( 5 ) 授权模块：它其实就像一个“包装 限制了a d m i t t e d q o s p a r a m s e t 和 a c t i v e q o s p a r a m s e t 的可能的值。 q o s 参数设置如图2 8 和2 9 所示。a c t i v e q o s p a r a m s e t 是a d m i t t e d q o s p a r a m s e t 的一个分支，而它是授权“包装 的一个分支。在多样的授权模型中，这个包装 是由授权模块决定的。在这个预留授权模块中，这个包装由 p r o v i s i o n e d q o s p a r a r n s e t 所决定。 一条业务流由三个参数集组成：指定q o s 参数集、已接纳q o s 参数集和激活 q o s 参数集。指定q o s 参数集指对业务流进行静态或者动态配置时指定的q o s 参 数集。系统可以在配置业务流期间或者在创建业务流的过程中对其资源要求能否 被满足进行审查。已接纳q o s 参数集是b s 认为能够满足其资源要求的q o s 参数 集。b s 必须为接纳了的业务流按其已接纳q o s 参数集要求保留预留资源。对于已 激活的q o s 参数集来说，b s 为处于激活状态的业务流提供其实际需要同时又不大 于接纳q o s 参数集的资源要求。同一条业务流的三个q o s 参数集满足如下关系： 激活q o s 参数集为已接纳参数集子集，已接纳q o s 参数集为指定参数集的子集。 图2 8 预留的业务流封装模型 第二章w i m a x 调度机制 1 7 2 4 3 对象模型 图2 9 动态的认证封装模型 对象模型如图2 1 0 所示，阐述了业务流，连接，分类器等对象之间的关系。 每一个对象有很多属性；这些属性由其名字被唯一标示。可选的属性用中括号进 行了标示。这些对象间的关系用线进行了关联。例如，一个业务流可以来自0 到n 个p d u s ，但是一个p d u 只能和一个业务流相对应。业务流是m a c 协议的核心， 它唯一的由一个3 2 比特( s f i d ) 来标示。这个被标示的业务流可以是上行，也可以 是下行。在a d m i t t e d 和a c t i v e 业务流之间是一对一的映射关系。 c i d 用于标示网络中已经被接纳的业务流。在注册和动态业务增加过程中， b s 为被接纳的业务流分配c i d 。再将已接纳q o s 参数集由空连接业务流成功改变 为非空动态业务流过程中，b s 也要为相应的业务流分配c i d 。c i d 主要用于 u l m a p 的分配。如果执行d s c 过程后，某业务流已接纳q o s 参数集为非空，则 它的c i d 将被释放，但s f i d 仍保留。 一个分类器规则对数据包到它的传输连接中进行了唯一的映射。这个分类器 规则和o 或者1 个p h s 规则相关联。当产生一个和p h s 规则关联的分类器规则序 号的时候，它就被用作是一个参考。一个p h s 规则是与一个单一的业务流相关联。 分类器规则将其数据包唯一的映射到与它关联的p h s 规则。 业务流等级是一个可选的对象，可以在b s 端进行实行。它用一个a s c l l 名字 做参考。其中它是用作预留的目的。一个业务等级在b s 端定义，以拥有一个特殊 的q o s 参数设置。q o s 参数设置也会包含一个与业务流等级名字作为宏的参考。 1 8 w i m a x 调度算法研究 图2 1 0 操作对象理论模型 2 5 本章小结 本章主要讲述了基于业务流的w i m a x 调度机制，表2 1 给