（信号与信息处理专业论文）宽带无线接入网络wimax技术下分组调度的研究.pdf

摘要 摘要 近年来，随着人们对于宽带业务需求的增加，无线宽带接入技术已经成为 人们关注的热点问题。i e e e8 0 2 委员会于1 9 9 9 年成立了8 0 2 1 6 工作组来专门制 定无线宽带接入标准，以解决最后一公里的无线宽带接入。e e e8 0 2 1 6 标准， 又称为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 e a c c e s s ，全球微波接入互操 作性) 。它是一项无线城域网( w m n ) 技术，是一种新的空中接口标准。 本文重点研究了w i m a x 中媒质接入层( m a c 层) 分组调度部分的内容。 由于其m a c 层支持p m p 和m e s h 两种模式，故本文主要针对这两种模式下的 分组调度进行研究。 在p m p 模式下，本文提出了一种基于q o s 的下行分组调度算法一d p f 算法。 该算法提供了最佳的用户公平性，较高的系统吞吐量和最低的丢包率。本文选 择t d d o f d m a 蜂窝网络，在三扇区单频小区和三扇区多频小区两种模式下， 运用网络仿真软件，编写基于协议定义参数的w i m a x 仿真平台。通过网络仿 真，分析了r r m a xc i , p f 和d p f 四种调度算法的系统吞吐量，用户公平性 和丢包率。仿真实验结果表明：调度算法和频率复用方案的选择需要根据系统 吞吐量，用户公平性和丢包率等因素来综合权衡。 在m e s h 协同分布式调度机制下，本文提出了基于优先级的时隙调度算法， 实现了高优先级业务流的低延迟，低丢包率和低请求失败率的o o s 保证。本文 首先详细讨论了i e e e8 0 2 1 6 - 2 0 0 4 标准的m a c 层调度机制，然后运用网络仿 真软件，编写了基于协议定义参数的m a c 层模块。网络仿真结果表明，在合理 的参数配置下，实时c b r 流和v b r 流的q o s 得到了良好的保障。最后得出结 论：基于不同的数据流合理分配资源，并实现各种数据流的o o s 保障，是提高 m e s h 网络性能的重要手段之一。 最后对全文进行了总结，对p m p 和m e s h 两种模式下的调度算法的进一步 研究进行了展望。 关键词：分组调度，公平性，吞吐量，丢包率，延迟 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 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 t 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 1 6 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 o e s ss t a n d a r d , p r o v i d i n gt h e l a s t - m i l e c o n n e c t i o nt oi n t e m e ts c r c i c e w i m a x ( w o r l d i n t e r o p e r a b i f i t yf o rm i c r o w a v e a c c e s s ) i so n e k i n do f w i r e l e s sb r o a d b a n da c c e s st e c b u o l o g i e s ，b a s e do ni e e e8 0 2 1 6 s t a n d a r d , a l s on a m e da f t e rw m a n ( w i r e l e s sm e t r o p o l i t a na r e an e t w o r k s ) ，w h i c hi s an e wa i ri n t e r f a c es t a n d a r d t h i sp a p e rf o c u s e so i lp a c k e ts c h e d u l i n ga l g o r i t h m so nm a c ( m e d i aa c c e s s c o n 仃0 0l a y e ro fw i m a x i nw h i c ht h e r ea l et w om o d e s ：p m pm o d ea n dm e s hm o d e t h e r e f o r e ，p a c k e ts c h e d u l i n ga l g o r i t h m sa l es t u d i e di nt h e s et w om o d e s f i r s t l y , i np m pm o d e ，t h r o u g h p u t , f a i r n e s sa n dd r o pr a t ep e r f o r m a n c e si n d o w n l i n ks c h e d u l i n go fi e e e8 0 2 1 6 eb a s e dt d d o f d m as e c t o r e dc c l l u l 盯 n e t w o r k sa l ee v a l u a t e d t h ep e r f o r m a n c e sm e n t i o n e da b o v ea l ea n a l y z e dw i t h d i f f e r e n ts c h e d u l i n ga l g o r i t h m sa n df r e q u e n c yr e u s es c h e m e s c o n s i d e r e ds c h e d u l i n g a l g o r i t h m sa r er r ，m a xc a ，p fa n dd p fw h i c hi sp r o p o s e di nt h i sp a p e r t h e 3 - s e c t o r e dw i t ht h es a m e 仃e q u e n c ya n d3 - s e c t o r e dw i t hd i f f e r e n tf r e q u e n c i e sp l a n s a r ec o m p a r e di nt e r m so ft h r o u g h p u tf a i r n e s sa n dd r o pr a t e ，w h i c ha s s i s ti n d e t e r m i n i n gt h ec h o i c eo f as c h e d u l i n ga n df r e q u e n c yr e u s ep l a n i n a d d i t i o n , t h em a cp r o t o c o lo fi e e e8 0 2 1 6 - 2 0 0 4s t a n d a r ds p e c i f i e s s c h e d u l i n gm e c h a n i s m sa b o u tm e s h , m o d ei nd e t a i l ，w h i l ei t sc h a n n e lr e s o u r c e s c h e d u l i n ga l g o r i t h m sa l en o ts p e c i f i e dd e t a i l e d l y t h i sp a p e rp r o p o s e st w os l o t s c h e d u l i n ga l g o r i t h m sb a s e d 衄p r i o r i t yt oa c h i e v eq 0 so nm a cl a y e r s i m u l a t i o n s a l ec o n d u c t e dt os t u d ya v e r a g ed e l a y , r e q u e s ti 嘲e c tr a t e ，m i n i s l o tu t i l i z a t i o na n dd r o p r a t eb a s e do np r o p o s e da l g o r i t h m n es i m u l a t i o nr e s u l t ss h o wt h a tp r o p o s e d a l g o r i t h m sa c h i e v eq o so fd i f f e r e n ts e r v i c e s l a s tb u tn o tl e a s t , ac o n c l u s i o no ft h i sp a p e ri sg i v e na n ds e v e r a la s p e c t so f f u r t h e rr e s e a r c ha r ep r e s e n t e dr e s p e c t i v e l yb a s e do np m pm o d ea n dm e s hm o d e k e yw o r d s ：p a c k e ts c h e d u l i n g , f a i r n e s s , t h r o u i g h p u t ，d r o pr a t e ，d e l a y 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：是元弓 ) o - 7 年3 月日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 年月日年月日 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均己在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 签名：堤元茜 一z 。7 年；月，5 日 第1 章绪论 第1 章绪论 1 1 研究背景与选题依据 随着随着互联网的发展，人们对i n t e r a c t 的信息传递、商务和娱乐等功能的 要求越来越高，因此用户对带宽的需求也不断增加。目前各国对以光缆为主体 的核心网络的建设已经初具规模，光缆的传输速率和容量可以满足要求。但是 在接入网方面，宽带接入已经成为制约高速上网和其他业务的瓶颈。 目前比较有竞争力的宽带接入技术有三种：w i f i ，w i m a x ，3 g 。其中 w i m a x ( w o r l d i n t e r o p e r a b i f i t yf o rm i c r o w a v ea c c e s s ，全球微波接入互操作性) 是基于i e e e8 0 2 1 6 标准的，它实现了2 - - 1 1 g i - i z 非视距( n l o s ) 传输和1 0 6 6 g h z 的视距( l o s ) 传输，峰值带宽可达7 5 m b p s 。由于其快速、低成本搭建、 易扩展等优点f 1 1 ，w i m a x 被普遍认为是未来的最有前途的宽带无线技术之一。 w i m a x 论坛是一个由业界领先的运营商、通信部件和设备公司共同成立的 组纠“。w i m a x 与i e e e8 0 2 1 6 工作组之间有着非常紧密的联系与合作，同时 又有着分工的不同。i e e e8 0 2 1 6 工作组是标准的制定者；w i m a x 论坛是i e e e 8 0 2 1 6 技术的推广者。根据服务供应商和厂商的设备计划，w i m a x 论坛决定首 先重点关注i e e e8 0 2 1 6 2 0 0 4 标准( 2 0 0 4 年6 月获得i e e e 批准，也称为i e e e 8 0 2 1 6 d 标准) 的2 5 6o f d mp h y 模式。这一物理层( p h y ) 与媒质访问控制层 ( m a c ) 结合在一起，确保为所有的w i m a x 实现提供一个统一的基础。基于慢 速移动的i e e e 8 0 2 1 6 e 标准已于2 0 0 5 年1 2 月获得了i e e e 批准。 在无线通信系统中，无线资源永远是有限的，因此，研究对于有限频谱资 源的最大化且合理利用总是有着积极而又重要的意义，而无线资源管理承担的 就是这样的作用，它包括了：分组调度、功率控制、移动性管理、接纳控制、 负载控制等等。它们每个部分都对无线系统的良好运作起着举足轻重的作用。 其中，分组调度更是影响系统性能的最关键一环，可以在很大程度上决定系统 的效率。 目前，针对不同无线系统的调度算法的研究已经越来越受人们重视，但其 成熟程度因系统的复杂程度不一也显得有些参差不齐。对于复杂链路环境，尤 其是多径丰富的无线链路环境下分组调度的研究才刚刚开始，如何在m a c 层的 方案、算法设计中考虑物理层信道变化对其的影响，实施跨越层次的算法设计 第1 章绪论 对于实际系统的演进有着重要的指导意义。同时，在w i m a x 系统中，无线链 路q u s 需求的加入，带来了不同用户的可变速率、不同时延要求的新特性，这 对于无线分组调度设计提出了新的，更高层次的要求。以上种种，正是本文展 开研究w i m a x 网络下分组调度的意义所在。 1 2 国内外研究现状 分组调度的概念在固定有线网中由来己久。在无线移动网络中，分组调度 同样有着重要作用，但由于两种网络在传输介质和网络结构上都有很大差异， 因此在两种网络中，算法的设计思想和侧重点都有所不同。固定有线网中的分 组调度作用更大程度上是避免拥塞，为到达交换节点的各个连接选择下一次转 发的路由和服务顺序；而在多级业务的无线移动网中，分组业务调度作为无线 资源管理的一个重要组成部分，更侧重于对系统整体性能和业务服务质量的保 证，为业务在空中接口传输时选择合理的无线参数配置，且往往是在某些资源 受限的系统中，算法复杂度体现在调度策略和服务机制上。而在无线网络中， 信道的参数具有时变特性，设计优良的调度算法将遇到更大的挑战性。 在有线网络中己提出了大量的调度算法，根据调度算法的服务规则、调度 目标，可以大致分为四类1 3 j 。 第一类是基于轮循的调度算法。传统的轮循( r r ：r o u n dr o b i n ) 算法对不 同队列( 业务流) 进行无区别的循环调度服务。这样，如果不同的队列具有不 同的分组长度，则分组长度大的队列可能会比分组长度小的队列接受更多的服 务，使队列之间产生不公平的现象；而且，这种算法不能对业务提供时延保证。 为了改进r r 算法的时延特性和其在变长分组环境下的不公平性，出现了一些改 进型的算法，如加权轮循【4 l 、差额轮循1 5 l ( d r r ：d e f i c i tr o u n dr o b i n ) 、紧急轮 循1 6 1 ( u r r ：u r g e n c y b a s e d r o u n d r o b i n ) 。这些算法力图在尽量保持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 是一个理想化的 流模型n 它根据各队列的共享比例对所有的活动队列同时服务，所以能使各业 务流真正公平地共享链路带宽。g p s 对每个队列业务流保证有明确的端到端的 2 第1 章绪论 时延上限，而且与其他队列业务流无关。g p s 模型是流系统，但是实际的系统 都是分组系统：在任何给定的时刻只能有一个分组可以得到服务，分组的传输 是不能被抢占的。因此出现了一类用来逼近基于流的g p s 模型的分组算法：p f q 算法【蹦6 1 。 第三类是基于时延的调度算法。基于轮循和g p s 模型的调度算法可以看成 是基于速率的调度算法，这种算法通常为每个队列提供一定的速率保证来达到 提供时延保证的目的。而基于时延的调度算法则是以( 为各队列) 直接提供时延保 证为目的，这类算法的代表是最早期限优先1 1 7 1 ( e d f ：e a r l i e s td e a d l i n ef i r s t ) 以及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 ) 调度算法i “。 第四类是基于服务曲线的算法 2 0 - m l 。g p s 模型的局限性在于业务只用了一 个参数( 速率) 来指定，使得时延与带宽的分配互相藕合在一起，也就是说低 时延就需要高带宽。这对于低时延、低带宽的业务就不能有一个很高的资源利 用率。为了解决这个问题，c r u z 首先提出了服务曲线的0 0 s 模型1 1 9 1 。 虽然上面提及的一些算法不修改或稍微修改一下，就可以适用于网络容量 随时问变化的状况，但是，它们不能处理与位置相关的容量变化。而无线信道 的容量不仅随时间变化，而且信道错误是与位鹭相关的，并且是突发的，这些 算法不能适应无线网络环境。除了无线信道所固有的特点，无线网络的体系结 构也会对调度规则的设计产生影响。无线网络在逻辑上可分为集中式和分布式 两类。集中式无线网络，也称为最后一跳网络，是有线网络的无线扩展，无线 终端与外界的通信都要通过基站。分布式无线网络，也称为a d - h o c 网络，无线 终端地位对等，不存在接入控制中心。 集中式无线网络_ 般由若干小区组成，每个小区由一个基站负责调度上行 和下行链路传输，邻居小区在不同的逻辑信道上传输，小区内的移动终端只能 和基站进行通信。在过去的几年里，已经提出了多种无线公平调度算法1 2 3 - 驾1 ， 为集中式无线网络中的业务流提供不同程度的长短期公平、长短期吞吐量边界、 平均和最差延迟边界以及出现信道错误时流的优美降级。它们的主要思想都是 在有线公平调度的基础上，针对无线信道的错误与用户的位置相关，推迟发送 信道错误的流，优先发送信道无错的流，然后在以后的时间对推迟发送的流做 出补偿，以期提高系统的吞吐量，提供长期和短期公平。目前常用的公平调度 算法可以从三个方面来分析：无错服务方面【扭2 5 j ；领先和落后方式方面【矧；补 偿方式方面【z o 硼。 3 第1 章绪论 分布式无线网络的主要特点是没有预先存在的控制中心，无线终端以分布 的方式交换信息，网络拓扑结构随无线终端的运动而不断变化。由于无线信号 的传输的局部广播特性，位置相邻的终端的数据包的传输存在竞争。因此，此 种类型网络的调度与有线网络和集中式无线网络不同。在有线网络和集中式无 线网络中，一个链路的调度器只需要考虑竞争那条链路的流，调度算法只需要 公平对待共享那条链路的所有流。在分布式无线网路中，需要为空间竞争的流 提供公平的信道分配。链路层的流是指一系列从源到目的地的数据包，源和目 的地是邻居。现有的m a c 协议，如i e e e8 0 2 1 1 ，e e 8 0 2 1 6 等没有提供公平 的概念。 现在已有一些分布式无线公平调度算法，它们可分为两种，分别支持共享 信道的包调度【2 9 l 和多信道的包调度1 3 0 j 。在共享信道的环境内，如果一个流的发 送者或接收者在另外一个流的接受者或发送者传输范围内。则称它们是竞争的。 具有竞争关系的流不能同时传输，但是互不干扰的流可同时传输。因而，共享 信道的包公平调度面临的主要问题是如何同时在空间域和时间域定义公平，保 证高的信道利用率。在共享信道的无线网络中，相邻的所有终端都参与竞争。 如果相邻终端使用不同的频率( f i ) m a ) 或码字( c d m a ) ，则可以减轻竞争。 但是，终端不能同时在两个以上的信道上接收或传输，因而共享一个终端的流 存在竞争。不同信道的调度是相互依赖的，一个信道上的流的带宽需求影响其 它信道的调度。 在w i m a x 网络p m p 模式下，i e e e8 0 2 1 6 标准并未定义上、下行带宽分配 的包调度算法。近年来，f 3 1 分别提出了几种宽带无线网络包调度算法。在此基 础上，【3 2 1 提出_ 套专门针对i e e e8 0 2 1 6 的调度解决方案，为i e e e 8 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 l ； l 算法和w f q ( w e i g h tf a i rq u e u e ) 1 8 】算法。但是， e d f 算法没有考虑到用户的优先级需求，而w f q 算法复杂度太高，不利于硬件 实现。 在w i m a x 网络m e s h 模式下，文献 3 3 1 考虑了路由和调度的结合，而 3 3 1 和 3 4 1 都引入了频谱的重用。对于协议中没有规定的基于m e s h 模式下调度机制 的信道资源调度算法研究的很少。z h i h u iz e n g l 3 5 l 提出了一种可以实现m a c 层 o o s 的基于优先级的分组调度算法。但是高优先级业务流和低优先级业务流的 区分服务不太明显，值得改进。 4 第1 章绪论 由此可见，不管是在p m p 模式下还是在m e s h 模式下，如何选取合适的分 组调度算法是一个研究重点。 1 3 主要研究内容 本文主要针对i e e e8 0 2 1 6 标准的m a c 层协议支持的p m p 模式和m e s h 模式下的分组调度进行重点研究。m a c 层的主要功能是调度传输上层来的数据 分组，将其正确无误地发送出去。 基于p m p 模式下，本文选择t d d o f d m a 蜂窝网络，在三扇区单频小区 和三扇区多频小区两种模式下，运用网络仿真软件o p n e t 和m a t l a b ，编写 基于协议定义参数的w i m a x 仿真平台，通过网络仿真，分析了r r , m a xc a , p f 和d p f 四种调度算法的系统吞吐量，用户公平性和丢包率，其中d p f 算法是一 种基于o o s 的下行分组调度算法。所以调度算法和频率复用方案的选择需要根 据系统吞吐量，用户公平性和丢包率等因素来综合权衡。 基于m e s h 协同分布式调度机制，本文首先详细讨论了i e e e8 0 2 1 6 - 2 0 0 4 标 准的m a c 层调度机制，然后运用网络仿真软件n s 2 ，编写了基于协议定义参 数的m a c 层模块。数据信道的资源调度一直是无线网络研究的热点。基于不同 的数据流合理分配资源，并实现各种数据流的o o s 保障，是提高m e s h 网络性 能的重要手段之一。在m e s h 协同分布式调度机制下，本文提出了基于优先级的 时隙调度算法，实现了高优先级应用的低延迟，低丢包率和低请求失败率的o o s 保证。网络仿真结果表明，在合理的参数配置下，实时c b r 流和v b r 流的o o s 得到了良好的保障。 1 4 论文的组织结构 本文的结构组织如下： 第1 章概述了论文研究背景与选题依据；介绍了目前国内外分组调度算法 的研究现状；最后综述了论文的主要研究内容和组织结构。 第2 章阐述了w i m a x 网络中两种模式下的调度机制，讨论了典型的分组 调度算法。 第3 章基于p m p 模式下，选择t d d o f d m a 蜂窝网络，在三扇区单频小 区和三扇区多频小区两种模式下，分析了r r ，m a xc i , p f 和d p f 四种调度算 5 第1 章绪论 法的系统吞吐量，用户公平性和丢包率。所以调度算法和频率复用方案的选择 需要根据系统吞吐量，用户公平性和丢包率等因素来综合权衡。 第4 章基于m e s h 分布式调度机制，对数据信道的时隙调度算法进行了研究。 在协同分布式调度机制下，提出基于优先级的时隙调度算法，实现分布式调度 下的q o s 保障。最后，将提出的算法嵌入到仿真平台中，验证算法的可行性， 并通过比较证明了算法的高效性。 第5 章对全文进行了总结和展望，提出了进一步研究的方向。 6 第2 章w i m a x 网络下的调度机制 第2 章w i m a x 网络下的调度机制 m a c 层的主要功能之一就是通过调度来解决相互竞争的多个用户共享无线 信道资源的问题，从而满足不同业务流的q o s 要求。由于每个用户所需的带宽 和延迟不同，所以m a c 协议必须灵活，要能够有效地支持不同数据流量模型。 i e e e8 0 2 1 6 - 2 0 0 4 标准的m a c 层设计了带宽请求和授权机制。为了提高系 统的灵活性，协议标准只定义了带宽分配和q o s 机制，将调度算法和预留资源 管理的细节留给设备供应商自己去开发。 2 1w i m a x 网络支持的两种模式 无线网络依赖于组网结构可粗略地分为两种：一种是小区蜂窝架构，也可 称为点对多点结构( 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 4 年颁布的 i e e e8 0 2 1 6 2 0 0 4 标准的m a c 层支持p m p 和m e s h 两种模式。 在过去的几年里，宽带无线接入系统大多采用p m p 结构，连接建立在基站 b s 和用户站s s 之问，s s 阃的数据传输需要经过b s 中转。p m p 能够提供较高 的传输速率，多个用户可共享网络资源。i e e e8 0 2 1 6 的体系结构定义了p m p 和m e s h 两种模式。其中p m p 是m a c 协议中定义的主要网络拓扑结构，即是 基站一用户站结构，如图2 1 。 图2 1w 洲a xp m p 网络的拓扑结构 7 第2 章w i m a x 网络下的调度机制 i e e e8 0 2 1 6 协议标准中，m e s h 模式是一种可选的模式。w m n 是一种动态 自组织自配置的网络，网络中的节点自动建立和维护他们之间的连接。因此， 这种特征使得w m n 具有低前期投资、快速搭建、简易的网络维护、鲁捧性和 可靠的服务覆盖等优点删。 如图2 2 是一个典型的i e e e8 0 2 1 6m e s h 网络的拓扑结构。每个节点都与周 围邻居节点形成多条链路，并且可以选择其中的一条链路，用来传输来自本节 点或其它节点的信息。这样，连接断开的可能性要远低于p m p 模式。同时，随 着节点数的增加，i e e e8 0 2 1 6m e s h 网络的健壮性加强，覆盖范围扩大。 图2 2w i m a xm e s h 网络的拓扑结构 对基于无线m e s h 结构的宽带无线接入网络来说，s s 问可直接或间接通信， 不必通过b s 中转。由于每个用户站可以作为一个中转站，信号是以逐跳方式传 输的，潜在地增加了网络的覆盖范围，当增加用户时不必再增加基站，其拓扑 结构可以动态改变。另外，m e s h 系统可以利用地形和建筑物，使用低传输功率 和相对短的链路来减少干扰。另外还可使用方向性天线来大大地减少干扰和传 输功率。减少内部干扰可以增加频率的再使用，提供频谱利用率；减少外部干 扰，可以减少保护频带。同时，s s 之问距离的缩短减小了室外天线功率和体积， 降低了s s 通信设备的成本。m e s h 拓扑结构在可靠性、覆盖面积、规划用户和 前期的低投入方面都有很好的表现1 3 7 3 8 j 。 第2 章w i m a x 网络下的调度机制 2 2p m p 模式下的调度机制 i e e e8 0 2 1 6 的体系结构中p m p 是m a c 协议中定义的主要网络拓扑结构， 即是基站一用户站结构。在该模式下的调度机制中，带宽请求分为两种： s t a n d - a l o n eb a n d w i d t hr e q u e s t ( 单独请求) 和p i g g y b a c kr e q u e s t ( 捎带请求) 。 单独请求有两种头：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 里指出。带宽请求可以是增加的带宽请求，或总 带宽请求。捎带带宽请求总是增加的带宽请求。 基于竞争的带宽请求是总带宽请求。每个带宽授权发送到s s 的b a s i cc i d ， 而不是单独的c 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 cc i d ，而是分配给 某个组播c d ( 弧f f d o o x f 肿) 或广播c 1 d ( o 】【f 凡下) 。 组播轮询和广播轮询都是基于竞争的。当s s 等待了一定时间后仍然没有得 到b s 的授权信息时，s s 则认为传输带宽请求信息发生了冲突。为了避免再次 冲突，发生冲突的s s 分别采用二进制指数退避算法，来选择下一个传输机会发 送带宽请求信息。 9 第2 章w i m a x 网络下的调度机制 如果一个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 位设置为1 、或者u g s 的发送间隔 太长，不能满足s s 其它连接的q o s 时，才能被单独轮询。一旦b s 检测到这种 轮询请求，就使用单独轮询来满足请求。 b s 通过u l - m a p 信令控制上行链路信道的分配和竞争时隙的长度与位置。 根据相应m 的定义，竞争可能发生在初始测距和带宽请求时段。带宽请求时段 可能发生冲突的工作站主要由m 里指定的c i d 决定。 为了减少因竞争而发生碰撞的概率，i e e e8 0 2 1 6 冲突解决的主要方法是使 用截短的二进制指数退避算法，其初始退避窗口和最大退避窗口由b s 指定。具 体值在u c d 信令中指定，表现为2 的指数。例如，4 表示窗口是m 1 5 ，1 0 表示 窗口数是0 1 0 2 3 。 当要传送信息预备并进入冲突解决过程时，首先确认初始和最大退避窗口的 数值，s s 将它当前的内部退避窗口设置成u c d 定义的“请求退避开始”值，退 避窗口的范围是【0 ，2 n 1 】。s s 随机选择退避窗口内的一个数字，这个随机数就 是下次传送信息前需要延迟的竞争传输机会数量。 例如，一个s s 初始退避窗口是0 - 1 5 ，假设它随机选取了数字1 1 。则s s 必 须延迟共1 1 个竞争传输机会。如果第一个可用的请求m 可以传输6 个请求，也 即有六次发送机会，该s s 不能发送信息此时还要延迟5 个机会。如果下一个请 求可以传输2 个请求，该s s 还要等3 个机会。如果第三个请求m 可以传输 8 个请求，则该s s 在等待3 个机会后可以在第4 个机会里传送信息。 发送的同时启动重传计数器，设定为最大重传值。传输后，一旦收到数据授 权m ，即表示冲突解决，此次带宽请求成功。如果在接收c o n t e n t i o n _ b a s e d r e s e r v a t i o nt i m c o u t ( 在u c dc o m m o nc h a n n e lc n c o d i n g s 中) 中指定个数u l m a p 消息后仍没有收到数据授权，s s 应该认为传送数据丢失或发生了碰撞，启动重 传机制。 重传机制为，s s 将退避窗口加倍，但不得大于最大退避窗口值。s s 在新退 避窗口中随机选取一个值，重复上文的延迟传输过程。同时重传计数器减1 。 若一直发生碰撞，当退避窗口等于最大退避窗口大小时，不再增大退避窗口， 但重传仍然进行，直到重传计数器中的数值减到0 。当达到最大重传次数时，重 1 0 第2 章w i m a x 网络下的调度机制 传过程结束。此时，丢弃带宽请求p d u ，通知上层。 如果s s 在退避过程中收到单播轮询m 或数据授权，则立即停止冲突解 决过程，使用指定的传输机会。 2 3m e s h 模式下的调度机制 i e e e8 0 2 1 6 协议标准中，m e s h 模式是一种可选的模式，它是将以前在军事 中广泛研究的a dh o e 网络的思想运用在民用中，具体的说来就是运用在无线城 域网中。 与p m p 模式相比较，其主要区别在于：p m p 模式中流量只是在b s 和s s 之间发生，任何节点如果需要通信都必须通过b s 来传输，传输过程中几乎所有 的控制过程都由b s 来执行。而在m e s h 模式中可以不通过b s ，而直接通过其他 的s s 来进行业务传输，进一步的，在s s 之间甚至可以直接进行业务。 。 8 0 2 1 6m e s h 模式的调度方式，可以分为集中式调度与分布式调度。其中集 中式调度的模式，类似于p m p ，该模式中有一个类似于b s 的m e s hb s 系统， 该系统是m e s h 网络内与网络外面的回程服务有着直接连接的系统。其它的节点 则为m e s hs s 。因此m e s h 的集中式调度中是通过m e s hb s 来协调各m e s hs s 的 传输，m e s hs s 想要发送数据必须等待m e s hb s 的许可。这种模式中，上行链 路和下行链路分别定义为朝着m e s hb s 的方向的链路和远离m e s hb s 的方向的 链路。 而m e s h 模式的分布式调度中，没有充当b s 的节点，各个节点是对等的。 s s 间可直接基于分布式调度算法进行通信，而不需b s 的许可。在m e s h 的分布 式调度中，用户站( s s ) 之间可构成小规模的l 一2 跳的多点到多点的无线连接， 没有明确的独立的上下行链路子帧，每个站能够与网络中的其它站建立直接的 通信链路。 m e s h 模式下的分布式调度具有如下特征： 、 无明确的协商：在多跳连接中，网状网络无明确调度协商的情况下支持 常规广播传输的调度，对于网络配置消息是有用的； 冲突避免：每个节点的扩展邻域内的调度是无碰撞的； 分布式：算法是完全无需中心控制的分布式的； 公平性：调度分配平等对待所有节点。 1 1 第2 章w i m a x 网络下的调度机制 i e e e8 0 2 1 6m a cc p s 子层控制多用户共享的空中资源，其m e s h 模式只 支持时分双工( t d d ) 方式。其m a cc p s 帧结构如图2 3 ，包括控制子帧和数据 子帧。 t u n e 曼三荨三一i 蚕 z z zz 鲁量县容 | 垂 田 兽 田 兽c 骂 膏 匕 一乌 硝 一 卜s c h e d u l ec o n t r o ls i i b f i a m c + p 一d a t as e l , f r a m e 斗 旧 口盆易舄 坌金坌坌 | 垂 田田口 重l 芒匕芒 习蜀舞 昌 一一 图2 3 m e s h 模式下的m a c 帧结构 控制予帧的长度由o f d ms y m b o l 来表示，等于7 m s hc t r l _ l e n ，其 中m s h 参数取值范围为o 1 5 。_ c t r l l e n 控制子帧有两种基本功能：网络控制和调度控制功能。因此控制子帧又可 分为网络控制子帧和调度控制子帧。两种控制子帧不能同时传输。 网络控制子帧用来创建和维持不同系统间的协调工作，广播网络信息给所 有的s s ，提供新节点接入网络时需获取同步和初始化的方式。带有网络控制子 帧的m a c 帧周期性地发送，周期为s c h e d u l i n g f r a m e * 4 + l 。其中，s c h e d u l i n g f r a m e 参数由m s h n c f g ( m e s hn e t w o r kc o n f i g r a t i o n ) 消息中的n e t w o r kd e s c r i p t i o n m ( 网络描述符信元) 给出。 调度控制子帧用来协调不同系统间的数据传输调度，发送m s h c s c h ( m e s h c e n t r a l i z e ds c h e d u l i n g ) 消息和m s h d s c h ( m e s hd i s t r i b u t e ds c h e d u l i n g ) 消息。 第2 章w i m a x 网络下的调度机制 m s h c s c h 消息用于集中式调度中b s 广播调度信息。m s h - d s c h 消息用于分 布式调度中发送数据前链路连接的建立，同时节点利用m s h d s c h 消息向邻居 广播调度表。控制子帧中各类消息的结构如图2 4 所示。 图2 4 控制子帧中各类消息的结构 控制子帧分为许多s l o t 单元，s l o t 的大小与对应的物理层调制编码方式有关， 等于7 个物理s y m b o l 大小。s l o t 的个数由m s h n c f g 消息中的n e t w o r k d e s c r i p t i o ni e 中的m s h c t r l - l e n 参数决定。在网络控制子帧中，第一个s l o t 必须用来发送m s h e n t r y ( m e s hn e t w o r ke n t r y ) 消息，剩余的m s h c t r l - l e n 一1 个s l o t 用来发送m s h - n c f g 消息。在调度控制子帧中，由n e t w o r k d e s c r i p t i o n m 中的m s h d s c h - n u m 参数说明有多少个s l o t 分配给m s h d s c h 消息。控 制子帧中前面m s h - c i r d l e n - - m s h - d s c h - n u m 个s l o t 分配给m s h - c s c h 消息，然后余下的分配给m s h d s c h 消息。 在数据子帧中的数据传输是面向连接的。一条链路应用于两节点间的双向 数据传输，没有独立的上下行链路。数据子帧被分为许多p h yb u r s t ，在i e e e 8 0 2 1 6 - 2 0 0 4 中也被称为m i n i s l o t 。如图2 5 。 p h y b u r s t 以2 个s y m b o l 大小的报头开始。m a cp d u 紧随其后，充分利 用分配的数据信道资源。m a cp d u 包含固定长度的m a c 头，固定长度的m e s h 子头和可选的c r c ( c y c l i cr e d u n d a n c yc h e c k ) 。由于载荷长度是可变的，因此 m a cp d u 的大小