（电磁场与微波技术专业论文）基于比例分配的无线分布式网络跨层调度.pdf

摘要 近年来，作为一种新兴的宽带无线接入技术，w i m a x 受到业界的 普遍关注。它的主要技术特点是传输速率高、覆盖范围大、支持移动 性、提供q o s 保证并采用基于全i p 的网络架构，实现了数据分组化、 接入宽带化和终端移动化三者合一，因而具有广泛的应用前景。作为 w i m a x 技术一大特征的m e s h 无线网络，它的最大优点则是在于组网 的灵活性，在一些地理位置偏远用户稀少的地区，组建m e s h 型的无 线网络显然要比p m p 网络更加方便而且节约成本。现有的m e s h 网络 调度方式有两种：集中式和分布式，其中分布式调度的优越性大于集 中式。在分布式调度中，现有的尽力而为的调度，分布式选举调度都 存在一定的缺陷，而且对时隙分配没有做出任何明确的规定。 因此在这篇文章中我们提出了一种在比例分配调度算法基础上 衍生而来的分布式无线网络的调度算法基于比例分配调度的无 线网络跨层调度算法( p r o p o r t i o n a l b a s e dd i s t r i b u t e dw i r e l e s s n e t w o r kc r o s sl a y e rs c h e d u l i n ga l g o r i t h m ，p d c s ) 。整个算法的 核心思想在于引入跨层设计的概念，实施的方案是在数据链路层中综 合考察物理信道的传输条件，从而进一步的把有限的无线资源更加合 理的分配给用户。基于比例式算法的原因则是从用户的公平性出发。 我们对新的算法从许多方面进行了仿真来证明它的优越性。 关键词 w i m a xm e s h p d c $ a b s t r a c t i nr e c e n t y e a r s ，a s a l l e m e r g i n g b r o a d b a n dw i r e l e s sa c c e s s t e c h n o l o g y ，w i m a xi sg e n e r a lc o n c e r n e db yt h ei n d u s t r y i t sm a i n t e c h n i c a lf e a t u r e sa r et h eh i g ht r a n s m i s s i o ns p e e d ，c o v e r a g e ，a n ds u p p o r t f o r m o b i l i t y ，t op r o v i d eq o sg u a r a n t e e a n da l l - i p - b a s e dn e t w o r k a r c h i t e c t u r e ，t h er e a l i z a t i o no ft h ed a t ap a c k e t ，b r o a d b a n da c c e s sa n d m o b i l et e r m i n a l so ft h et h r e e o n e ，s ot h e yh a v eaw i d ea p p l i c a t i o n p r o s p e c t a s a m a j o r f e a t u r eo fw i m a xt e c h n o l o g y ，t h e b i g g e s t a d v a n t a g eo fm e s hw i r e l e s sn e t w o r kl i e si nt h ef l e x i b i l i t yo fn e t w o r k i n g ， i nt h er e m o t ea r e a ，t h ef o r m a t i o n o fm e s h b a s e dw i r e l e s sn e t w o r ki s o b v i o u s l y m o r ec o n v e n i e n tt h a nt h ep m pn e t w o r ka n dc o s t s a v i n g s t h e r ea r et w od i f f e r e n t s c h e d u l i n gm o d e i nm e s h ：c e n t r a l i z e da n d d i s t r i b u t e d ，a n dd i s t r i b u t e ds c h e d u l i n gi sg r e a t e rt h a nt h ea d v a n t a g e so f c e n t r a l i z e d t h e r ea r es o m ed e f e c t so f p r e s e n t t h eb e s t e x i s t i n g s c h e d u l i n g ，d i s t r i b u t e ds c h e d u l i n go fd i s t r i b u t e ds c h e d u l i n g ，e s p e c i a l l y ， t h e r ei sn os p e c i f i cd e t a i li nt i m es l o ta l l o c a t i o n h e n c ew ep r o p o s ean e ws c h e d u l i n g a l g o r i t h mb a s e do nt h e o l d p r o p o r t i o n a ls c h e d u l i n ga l g o r i t h m c a l l e d d c s ( d i s t r i b u t e d w i r e l e s s n e t w o r k c r o s s l a y e rs c h e d u l i n ga l g o r i t h m ) p r o p o r t i o n a l b a s e dd i s t r i b u t e dw i r e l e s sn e t w o r kc r o s sl a y e rs c h e d u l i n g a l g o r i t h m ，p d c s t h ec o r eo ft h i sa l g o r i t h mi st h ec o n c e p to fc r o s s l a y e r d e s i g n ，m e a n i n g t h a ti no r d e rt od i s t r i b u t et h ew i r e l e s sr e s o u r c e s e f f i c i e n t l y , s c h e d u l i n ga l g o r i t h ms h o u l dc o n s i d e rn o to n l yt h es t a t eo fm a c l a y e rb u ta l s ot h eo n eo fp h y s i cl a y e r , w h i c hi sa l s oah u g ei m p r o v e m e n t i nt h ef a i r n e s so ft h en e t w o r k i nt h ee n d ，s i m u l a t i o ni st a k e nt op r o v et h e b e n e f i t so ft h i sa l g o r i t h m s i n c eag r e a tp a r to ft h er e s e a r c ho nt h em e s h n e t w o r kf o c u s e do nt h ec o o r d i n a t e do n ea n dm u c hl e s so nt h ed i s t r i b u t e d o n e ，t h i sa l g o r i t h mi sa sf a ra sw ek n o wt h ef i r s tc r o s s l a y e rs c h e d u l i n g a l g o r i t h mf o rt h ed i s t r i b u t e dw i m a xn e t w o r k k e yw o r d s ：w i n 【a xm e s hp d c s 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 蕊宝 煞日期：丝盟：主：! ! 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名： 愈空遨一 日期： 导师签名：二多扛写琴轧日期： 第一章概述 w i m a x 无线网络调度算法 无线通信是通信领域中发展最快的通信方式，它的发展趋势是宽带化、i p 化、多业务化和泛在化。作为一种新兴的宽带无线接入技术，w i m a x 近年来受 到了业界的普遍关注。它的主要技术特点是传输速率高、覆盖范围大、支持移动 性、提供q o s 保证并采用基于全l p 的网络架构，实现了数据分组化、接入宽带 化和终端移动化三者合一，因而具有广泛的应用前景 w i m a x 技术已经同w c d m a ，c d m a 2 0 0 0 以及t d s c d m a 技术一起成为 了3 g 标准之一。这就已经证明了w i m a x 在下一代无线接入技术中举足轻重的 地位。同其他的3 g 技术不同，在w i m a x 协议中除去标准的p m p 网络结构之 外，也定义了类似于a dh o c 网络的m e s h 网络模型。 调度算法是无线网络数据链路层协议的重要实现机制，它直接关系到整个网 络的服务质量( q o s ) 表现。相比m e s h 网络，p m p 网络的调度算法一直都是 研究的热点，许许多多的调度算法都已经被提了出来。这些算法的相似之处都在 于由b s 来统一的管理调度，调度优先级的确定则是通过s s 的比较来完成，只不 过每一个算法选取的比较参数都不尽相同 二本文研究的内容 作为w i m a x 技术一大特征的m e s h 无线网络，它的最大优点则是在于组网 的灵活性，在一些地理位置偏远月j ，_ 稀少的地区，组建m e s h 型的无线网络显然 要比p m p 网络更加方便而且节约成本。近些年来m e s h 网络正在慢慢成为研究 所关注的热点。因为在m e s h 网络中点到点通信不仅仅发生在s s 和b s 之间， 它同样也存在于s s 之间，所以这给调度算法的设计带来了新的挑战。8 0 2 16 协 议把m e s h 网络划分为两种类型：集中式和分布式。在集中式网络中，虽然s s 之i 日j 也能直接通信，但是网络的许多管理还是要通过b s 来完成，所以这种网络 模型比较类似于p m p 网络，现今大部分的m e s h 研究也集中在这种网络模型上， 而在另外一种分布式网络中则完全打破了b s 和s s 的区分，网络中没有节点作统 一的管理，更加类似于a dh o c 型网络。因为这种形式的网络更加能发挥m e s h 网络的优点：灵活性 在这篇文章中我们提出了一种适用于w i m a x 分布式网络的调度算法 p d c s 。这个算法有效的结合了跨层设计的思想和自适应调制( a m c ) 技术来提高 网络的性能。仿真的结果也证明了网络的吞吐量和公平性都得到了明显的提升。 三本文研究内容的意义 在这篇文章中我们提出了一种在比例分配调度算法基础上衍生而来的分布 式无线网络的调度算法。整个算法的核心思想在于引入跨层设计的概念，实施的 方案是在数据链路层中综合考察物理信道的传输条件，从而进一步的把有限的无 线资源更加合理的分配给用户。基于比例式算法的原因则是从用户的公平性出 发。我t f l x , r 新的算法从许多方面进行了仿真来证明它的优越性。 四本文的结构安排 根据，本论文将按照以下的顺序介绍：第一章概述；第二章现有调度算法 分析，详细介绍当前的w i m a xm e s h 网络调度算法和理论方面的研究；第三章 p d c s 理论，从时隙分配和业务区分两个方面详细介绍本文提出的基于比例分配 的分布式无线网络跨层调度算法；第四章p d c s 在n s 2 中的实现方案，着重介 绍在n s 2 平台上如何实现p d c s 算法；第五章仿真结果分析，从仿真结果中分 析p d c s 算法的性能。第六章展望，介绍一些调度算法的研究方法和本文提出 的p d c s 算法改进思路，最后是参考文献和致谢。 2 2 1w i m a x 技术介绍 第二章现有调度算法分析 2 1 1w i m a x 现状概况 无线通信是通信领域中发展最快的通信方式，它的发展趋势是宽带化、i p 化、多业务化和泛在化。除已广泛应用的蜂窝网技术外，宽带无线接入技术还包 括无线局域网技术、无线城域网技术和新兴的无线广域网技术，为了获得更大的 覆盖范围、更高的传输速率和更好的服务质量，i e e e8 0 2 1 6 工作组自1 9 9 9 年 成立以来制定了一系列的无线城域网标准。i n t e l 、富士通和诺基亚等公司于 9 0 0 1 年共同成立了非营利性工业贸易联盟全球微波接入互操作( w i m a x ) 论 坛，旨在推动与保证基于i e e e8 0 2 1 6 系列标准的宽带无线设备的兼容性和互操 作性从此以后，l l i m a x 就成为了i e e e8 0 2 1 6 系列标准技术的代名词。 i e e e8 0 2 1 6 ( 以下简称8 0 2 1 6 ) 工作组相继推出的空中接口标准包括 8 0 2 1 6 、8 0 2 1 6 a 、8 0 2 1 6 d 、8 0 2 1 6 e 。目前的两个主流标准是8 0 2 1 6 d 和8 0 2 1 6 e ， 分别应用于固定和移动通信。8 0 2 1 6 d 是对8 0 2 1 6 和8 0 2 1 6 a 标准的整合和修 订，定义了支持多种业务类型的固定宽带无线接入系统的媒体接入控制( m a c ) 层 和相对应的多个物理层框架。8 0 2 1 6 e 在8 0 2 1 6 d 的基础上增加了部分新的功能， 以支持用户的移动性总的来说，作为一种以无线方式实现“最后一公里 宽带 接入的技术解决方案，8 0 2 1 6 系列标准规范了一个支持语音和视频等低时延应 用的协议，可以为用户提供固定、移动、便携形式的高速数据、语音和视频传输 服务。 与其他无线通信技术相比，w i m a x 有传输速率高、覆盖范围大，o o s 机制完 善，数据安全性高，网络架构全i p 等优势： ( 1 ) 传输速率高，覆盖范围大 通过在物理层采用先进的正交频分复用、多天线技术以及灵活的编码调制方 式，w i m a x 系统的频谱利用率得到显著提高，同时可支持非视距通信和无缝覆盖。 使用2 0m h z 带宽时最高数据传输速率达7 5m b s ，是3 g 所能提供的3 0 倍。同 时，w i m a x 采用宏小区方式，视距传输下每个基站的最远覆盖半径可达5 0k m ， 典型覆盖半径为6k m 1 0k m ，只要建设少数基站就能实现全城覆盖。 ( 2 ) 完善的o o s 机制 w i m a x 采用面向连接的方式，其m a c 层定义了较为完整的o o s 机制和4 种不 同的业务类型。w i m a x 可分别为用户提供高质量的视频和语音业务、普通质量的 视频和语音业务、以及无质量保证的i n t e r n e t 等业务，并可根据业务的实际需 3 要动态按需分配带宽，灵活性较大。 ( 3 ) 较高的数据安全性 安全性是无线网络需要考虑的一个重要问题。8 0 2 1 6 在m a c 层中定义了一 个加密子层，为信息传输提供鉴权、加密和保密的管理机制。 ( 4 ) 基于全i p 的网络架构 8 0 2 1 6 设备可以作为一个路由器接入现有的i p 网络，与现有网络实现互联 互通，同时也可与下一代网络进行无缝融合。 ( 5 ) 开销及投资风险小 标准化的空中接口和技术规范，使不同设备制造商的产品可以进行互通，降 低了运营商对单一厂商设备的依赖性，降低了投资成本和风险。 ( 6 )部署灵活，配置伸缩性强，可平滑升级 总之，在实现了数据分组化、接入宽带化和终端移动化三者合一的基础上， w i m a x 技术提供了比其他无线系统更具优势的覆盖范围、传输速率和q o s 保障。 因此，w i m a x 一推出便受到业界的广泛关注，成为宽带无线接入领域的研究和开 发热点本文后面就将以8 0 2 1 6 d e 标准为基础，详细介绍w i m a x 物理层和m a c 层的特性及关键技术，分析其网络架构、组网模式及其应用，并展望w i m a x 未来 的发展趋势 2 1 28 0 2 1 6 d 协议栈参考模型 i e e e8 0 2 1 6 标准定义的空中接口由物理层和m a c 层组成。m a c 层独立于物 理层，能支持多种不同的物理层规范，以适应各种应用环境。物理层由传输汇 聚子层( t c l ) 和物理媒质依赖子层( p m d ) 组成，通常说的物理层主要是指其中的 p m d 。t c l 将收到的m a c 层数据分段，封装成t c l 协议数据单元( p d u ) 。p m d 则具 体执行信道编码、调制解调等一系列处理过程。 2 1 2 1m a c 层性能 i e e e 8 0 2 1 6 媒体访问控制( m a c ) 层的核心是公共部分子层( c p s ) ，其最大特 点是面向连接。该子层实现的操作包括系统接入控制、调度服务、带宽的请求与 分配、连接的建立与维护、网络接入与初始化、初始测距与周期性测距等。为了 支持移动性，8 0 2 1 6 e 在m a c 层还引入了一些新的特性，例如切换支持、可节电 的休眠模式和空闲模式等。m a c 层采用分层结构，分为特定服务汇聚子层( c s ) 、 公共部分子层( c f ) s ) 和安全子层： ( 1 ) c s 子层负责和高层接口，汇聚上层不同业务它将通过服务访问点( s a p ) 收到的外部网络数据转换和映射为m a c 业务数据单元，并传递到m a c 层的s a p 。 4 协议提供了多个c s 规范作为与外部各种协议的接口，可实现对异步传输模式 ( a t m ) 、i p 等协议数据的透明传输。 ( 2 )c p s 子层实现主要的m a c 功能，包括系统接入、带宽分配、连接建立和 连接维护等。它通过m a c 层s a p 接收来自各种c s 层的数据并分类到特定的m a c 连接，同时对物理层上传输和调度的数据实施q o s 控制。 ( 3 ) 安全子层的主要功能是提供认证，密钥交换和加解密处理。该子层支持 1 2 8 位、1 9 2 位及2 5 6 位加密系统，并采用数字证书的认证方式，以保证信息的 安全传输。 2 1 2 2网络拓扑 w i m a x 定义了点对多点( p m p ) 和可选的网状网( m e s h ) 两种拓扑结构。两者的 主要区别在于p m p 模式下通信只能在用户站( s s ) 和基站( b s ) 之间进行，m e s h 模 式下通信可以直接在s s 之间进行。目前i e e e 8 0 2 1 6m a c 层规范主要针对p m p 方式定义，w i m a x 系统部署实施中也大多采用该方式。 2 1 2 3 媒体访问机制 与i e e e 8 0 2 1 1 的载波监听冲突避免( c s m a c a ) 策略不同，i e e e 8 0 2 1 6 采取 的方式是在物理层将时间资源进行分片，通过时间区分上行和下行。每个物理帧 的帧长度固定，由上行和下行两部分组成，上行和下行的切换点可以通过m a c 层的控制自适应调整。在t d d 模式下，每一帧由n 个时隙组成。下行是广播的， 上行是s s 发向b s 的。下行在先，上行在后。以正交频分复用( o f d m ) 物理层的帧 结构为例，每个下行子帧以用于物理层同步的前导开始，其后是帧控制头( f c h ) 。 f c h 之后的第一个下行突发中包含下行链路映射( d l m a p ) 、上行链路映射 ( u l m a p ) 以及下行链路信道描述符( d c d ) 和上行链路信道描述符( u c d ) 等m a c 层 管理消息，用于说明其后的下行数据都属于哪个s s ，调制编码方式如何；本帧 的上行时间怎么分配，采用何种调制编码方式。通过这样的设计，不但杜绝了上 行方向的竞争，还可以在b s 上对所有系统资源的调度和分配进行集中控制。 对于宽带无线接入系统而言，这种媒体访问机制兼顾了灵活性和公平性，每 个s s 都有机会发送数据，避免了长期竞争不到信道的现象出现；其次，每个s s 都只在属于自己的发送时段内才发送数据，可以保证任何时刻，媒体上只有一个 数据流传输；再次，这种机制便于进行o o s 、业务优先级以及带宽等方面的控制。 2 1 3调度服务 5 所谓的发送调度是指选择数据在特定的帧分配的带宽中发送。它在下行由 b s 实现，在上行由s s 实现，调度时考虑的因素包括服务流指定的调度服务类型、 服务流的q o s 参数值、可以发送的数据、授权带宽大小等等其中调度服务代表 m a c 调度器所支持的数据处理机制。每种调度服务都取决于一组q o s 参数，这些 参数决定了数据传输在各个方面的质量。每条连接与一种特定的调度服务相关 联，使得数据包在调度之前就具有了相应的q o s 要求 针对上行的服务流，i e e e 8 0 2 1 6 d 定义了4 种类型的调度服务，分别为主动 授权服务( u g s ) 、实时轮询服务( r t p s ) 、非实时轮询服务( n r t p s ) 和尽力而为服务 ( b e ) ( 1 ) 主动授权服务 u g s 用于支持传输周期性定长数据分组的实时服务流，例如t 1 e 1 和无静默 压缩的v o l p 业务。在这种服务中，b s 周期性地为s s 授予固定大小的带宽，该 带宽应足够容纳与服务流关联的固定长度数据。这种主动授予方式避免了s s 发 送请求所产生的开销和时延，并且能确保满足服务流的实时性要求。u g s 必选的 q o s 参数包括最大持续业务速率、最大时延、可容忍时延抖动、上行授权调度类 型以及请求传输策略。 ( 2 )实时轮询服务 r t p s 用于支持传输周期性变长数据分组的实时服务流，例如m p e g 视频流。 该服务可以提供实时的周期性单播请求机会来满足服务流的实时要求，同时允许 用户指定所需带宽的大小与u g s 相比，r t p s 需要更大的请求开销，但是支持 可变授权带宽，从而优化数据传输效率。r t p s 必选的q o s 参数包括最小预留业 务速率、最大持续业务速率、最大时延、上行授权调度类型以及请求传输策略。 ( 3 )非实时轮询服务 n r t p s 用于支持有最小数据速率要求、数据分组长度可变且对时延不敏感的 服务流，例如f t p 业务。该服务也提供固定时间间隔的单播轮询，以保证即使在 网络拥塞时服务流也可以获得带宽请求机会。通常b s 会在数秒或更短的时间内 轮询一遍所有的n r t p s 连接。n r t p s 必选的q o s 参数包括最小预留业务速率、最 大持续业务速率、业务优先级、上行授权调度类型以及请求传输策略。 ( 4 )尽力而为服务 b e 用于支持无最小数据速率要求的服务流，例如i n t e r n e t 等业务。该类服 务仅在空闲时才进行处理。b e 必选的q o s 参数包括最大持续业务速率、业务优 先级、上行授权调度类型以及请求传输策略。 为了提高带宽使用效率，8 0 2 1 6 e 增加定义了扩展的实时轮询业务( e r t p s ) 类型，支持诸如带静默压缩的v o l p 业务等。与u g s 类似，此时b s 将主动为s s 6 分配带宽。不过u g s 分配的带宽为固定长度，而e r t p s 分配的带宽是动态和可变 长度的。 2 1 4 带宽分配与请求机制 除u g s 连接的带宽需求是固定的之外，其他所有服务在连接持续期间都可能 会有增加或减少带宽的要求因此，不同于传统移动通信系统的固定信道分配， i e e e8 0 2 1 6 采用了按需分配多址接入( d a m a ) 方式。在连接有需求时，系统根 据请求动态分配带宽，以便在满足q o s 要求的前提下尽可能地提高资源的利用 率。按照协议规定，s s 可以有多种方式向b s 申请带宽。 ( 1 )请求 请求指的是s s 直接向b s 申请分配上行带宽的机制。请求信息可以通过一个 独立的带宽请求( b r ) 消息发送，也可以在数据传输过程中捎带。请求的带宽可以 是增量带宽或总量带宽，但是捎带请求只能是增量b r 。s s 在入网、由空闲模式 重新接入网络以及切换之后，使用增量b r 之前必须先进行一次总量带宽请求。 同时，带宽请求授权协议的自校j 下特性要求s s 周期性地根据服务的o o s 特性和 链路质量发出总量b r 。 ( 2 )授权 虽然s s 发出的b r 总是基于单个连接，但是b s 进行带宽授权时指向的将是 s s 的基本c i d ，而不是各个连接的c i d 。由于无法判断哪个请求被授权，因此当 授权带宽比期望值小时，s s 将根据从b s 收到的最新信息和请求的状态，决定是 进行退避后重发还是丢弃协议数据单元( s d u ) 。 ( 3 )轮询 轮询指的是b s 专门为s s 分配一定的带宽，用于s s 发送b r 。如果资源充足， 这种分配可以针对当前未活动的每个s s 单独进行，即单播轮询。当前具有活动 u g s 连接的s s 也可以通过设置u g s 连接m a c 包头中的p m 位来申请加入单播轮询。 如果没有足够的带宽进行单播轮询，可使用多播或广播的方式，为一组s s 分配 一个公共的带宽资源，用于发送b r 。为了减少冲突，只有需要请求带宽的s s 才 会作出响应，并根据协议中规定的竞争处理算法决定在哪一个时隙发出初始b r 。 ( 4 )基于竞争的集中式带宽请求 此种机制用于o f d m 物理层。s s 可以在数据帧的注册项( r e g ) 域内发送集中 式的竞争请求消息，其实现方式是在由4 个子载波组成的竞争信道上等概率选取 8 个竞争码中的一个发送。b s 检测到该消息之后，将为该s s 分配一定的带宽用 于发送b r 。 ( 5 )基于竞争的c d m a 带宽请求 7 此种机制用于o f d m a 物理层。o f d m a 定义了一个测距子信道和3 个伪随机测 距码子集，分别用于带宽请求、初始测距和周期性测距s s 需要申请带宽时， 可以从用于带宽请求的测距码子集中随机选择一个c d m a 测距码通过测距子信道 发送。b s 检测到该消息之后，将为该s s 分配一定的带宽用于发送b r 。 2 1 5w i m a x 物理层基本特性 根据使用频段的不同，8 0 2 1 6 定义了5 种不同的物理层技术，即单载波调 制( s c ) 、单载波接入( s e a ) 、正交频分复用( o f d m ) 、正交频分多址接入( o f d m a ) 以及高速且免许可使用的城域网络( h u m a n ) 。其中，s c 适用于1 0 - - - - 6 6g h z 频段， s e a 、o f d m 和o f d m a 适用于1 1g h z 以下许可频段，t l u m a n 则用于1 lg h z 以下免 许可频段。由于o f d m 和o f d m a 具有较高的频谱利用率，在抵抗多径效应、频率 选择性衰落和窄带干扰方面具有明显优势，因此是目前在1 lg h z 以下许可频段 中采用的两种主流技术。 物理层定义了两种双工方式：时分双工( t d d ) 和频分双工( f d d ) ，以适应不同 国家或地区电信体制的要求。f i ) d 需要成对的频率，t d d 则不需要，而且可以自 适应地调整上下行传输时间，从而调整带宽。这两种方式都使用突发数据传输格 式，支持自适应的突发业务数据，在m a c 层协助下，可以动态调整传输参数( 调 制方式、编码方式、发射功率等) 。8 0 2 1 6 e 中还规定f d d 模式下可支持半双工 终端，降低了对终端的要求。 在多址方面，8 0 2 1 6 d e 在上行采用时分多址( t d m a ) ，上行信道被划分为 多个时隙。初始化、竞争、维护、业务传输等应用都是通过占用一定数量的时隙 来完成，其占用的数量由基站的m a c 层统一控制，并根据系统性能优化要求而动 态改变。下行信道采用时分复用( t d m ) ，基站送给不同用户的信息被复用成单个 的数据流，通过下行信道广播发送给扇区内的所有终端。 2 1 5 1 自适应调制编码技术 无线信道的时变和衰落特性决定了信道容量是一个时变的随机变量，要最大 限度地利用信道容量，只有使发送速率也随之相应地变化，也就是说编码调制方 式应该具有自适应特性。自适应调制编码( 6 t c ) 技术就是根据信道条件动态调整 编码和调制方式，以提高传输速率或系统吞吐量。基本方法是根据对信道质量的 测量结果，在信道条件较好时使用高阶调制和高编码速率( 例如6 4 0 a m ，5 6 码 率) ，以实现更高的峰值速率；而在信道条件较差时使用低阶调制和低编码速率 ( 例如q p s k ，1 2 码率) ，以保证传输性能。通过改变调制编码方式而不是发射功 率来改善性能，还可以在很大程度上降低因发射功率提高而引入的额外干扰。 8 综上所述，我们介绍了w i m a x 网络的优越性，重点描述了其网络拓扑分类，数 据链路层，物理层的相关技术，这些都是这篇论文重点讨论和研究的东西。当然 w i m a x 还有很多其他重要的技术，比如多天线接收，功率控制技术等等本论文 由于着重于数据链路层和物理层的跨层调度算法设计和优化，因此只对媒体访问 机制，调度服务，带宽分配与请求机制，物理层基本特性，而对其他技术不做详细 的介绍。下面对m e s h 模式下的调度机制进行详细的介绍 2 2m e s h 模式及其调度机制分析 2 2 1m e s h 模式的特点 在i e e e 8 0 2 1 6 d 定义中，网络拓扑结构一般采用p m p ( 点到多点) 方式，此时， 网络系统只能在b s 与s s 之间进行数据的通信，如果要达到更远的覆盖距离就必 然要牺牲数据传输速率，降低吞吐量。为了能够在保证网络吞吐量，保证网络有 效利用率的基础上最大限度地扩大无线网络的覆盖范围，i e e e s 0 2 1 6 d 定义了 m e s h 拓扑结构。相对于p m p 模式，m e s h 模式有以下几个特点： 1 ) 高带宽：无线通信的物理特性表明在短距离内的数据传输带宽最高。随 着传输设备之间距离的增加，干扰和衰减等因素也会逐渐增强，导致数据丢失， 数据的传输率急剧下降。m e s h 模式与p m p 模式最大的不同点在于，不仅b s 与s s 之间能够直接通信，并且s s 之间也可以通过多跳的方式实现多点到多点的无线 连接。此时，由于邻近节点之间距离相对较短，数据的传输速率相对于b s 和较 远s s 之间的直接通信有很大提升，具有较大的吞吐量。 2 ) 覆盖面积广：p m p 模式现在还不支持中间节点的接力m e s h 模式通过中 间节点进行接力，可以极大地扩大基站信号的覆盖范围。 3 ) 稳健性：使用m e s h 模式的无线网络比p m p 模式的无线网络拥有更高的稳 定性。在p m p 模式中，基站作为网络的中心节点，成为网络稳定性的瓶颈。如果 基站崩溃了，周边的用户站节点也同时失效。而当m e s h 模式中的节点崩溃时， 在源节点和目的节点问存在多条路径可以选择。 4 ) m e s h 模式只支持时分双工( t d d ) 方式，没有明确的、独立的上下行链路 子帧，从而使得各个站之间可以与网络中其他站建立直接的通信链路。 2 2 2m e s h 模式下的帧结构 模式下的帧包括控制子帧和数据子帧两个部分。控制子帧完成网络控制和调 度控制，因此，控制子帧又分为网络控制子帧和调度控制子帧两种 9 网络控制子帧通过发送m s h - e n t r y ( 网络接入) 消息和m s h n c f g ( 网络配置) 消息来使得不同系统之间能够协调一致工作。m s h e n t r y 消息提供了新节点接入 网络同步和初始化的方法；m s h n c f g 消息则提供了不同系统节点之间进行通信 的一些参数。在调度控制子帧中，n e t w o r kd e s c r i p t i o ni e 中m s h d s c h n u m 参 数定义分配给m s h - d s c h 消息的时隙单位数量。前( m s h 埘r l l e nm s h d s c h - n u m ) 个时隙单位用于发送m s h - c s c h 消息，其余的用于发送m s h d s c h 消息。 数据子帧被分为2 5 6 个微时隙单位，而控制子帧可分为多个时隙单位，其数量 由m s h - n c f g 消息中的n e t w o r kd e s c r i p t i o ni e 中的m s h - c t r l t e n 参数来决定 每个控制子帧中包含了( 时隙x 时隙数量x 7 ) 个o f d m 符号，控制子帧发送信息都 采用q p s k l 2 调制编码。协议中定义了网络控制子帧中第一个时隙单位必须用来 发送网络接入消息，剩下( m s h 稍r l l e n 一1 ) 个时隙单位用来发送网络配置消息。 m e s h 模式下的帧结构如图2 一l 所示 m s i i - c t 1 1 1 1 ，e n 千：s 6 夸 图2 1m e s h 模式下的帧结构 2 2 3m e s h 模式下调度机制分析 i e e e 8 0 2 1 6 d 标准定义了m e s h 模式下的两种调度方式：集中式调度和分布 式调度。 ( 1 )集中式调度 在集中式调度方式下，一方面，b s 在调度过程中处于中心位置，并协调s s 的接入问题；另一方面，由于m e s h 模式下没有独立的上下行子帧，b s 和s s 之 间在通信过程中不必建立直接链路，可以通过中问s s 中继来建立连接。在该调 l o 度模式中，b s 和s s 可以视为处于同一棵调度树中，b s 处于调度树的根部。b s 在确定链路的b u r s t 分配以及相关参数后，根据s s 的请求统一安排网络资源。 图2 - 2 集中式调度示意图 b s 在i l i s h - c s c h 消息中广播调度信息；在m s h - c s c f 消息中广播各条链路的 b u r s t 分配以及相关参数，各个节点根据m s h - c s c f 消息中的调度树来进行链路 更新。由于集中式调度机制中b s 负责整个网络通信过程中s s 之间的关系，在一 定程度上可以避免碰撞问题，可以有效解决s s 之间对于资源的竞争。但是，在 集中式调度机制下，容易出现以下几个方面的问题：由于s s 之间需要通过b s 来进行通信，一旦b s 与某s s 之间无法建立连接将导致该s s 无法与网络中其他 节点进行通信；b s 需要大量的额外丌销来维护整个网络中节点的状态信息表； 整个网络的通信效率较低；由于网络通信对于b s 的过度依赖，b s 必须保证工作 的稳定性。为了解决以上问题，分布式调度机制就显得尤为重要。 ( 2 )分布式调度 在分布式调度方式中，网络中各个s s 可以直接进行通信，这使得整个网络 的通信效率大大提高，也有效规避了过度依赖b s 带来的通信风险。分布式调度 如图2 - - 3 所示。 图2 3 分布式调度示意图 依据在传输调度过程中是否存在碰撞现象，i e e e 8 0 2 1 6 d 进一步将分布式调 度划分为协同分布式调度和非协同分布式调度。根据m s h d s c h 消息中特定位的 比特值来标志调度类型：0 为协调调度，l 为非协调调度。 ( 3 )协调分布式调度 当s s 节点需要传输数据时，它必须首先获得信道时隙的使用许可，即它要 通过公共控制信道向距离自己跳范围的邻居节点发送请求发送帧r t s 来获得某 个时隙或多个时隙的使用许可。当且仅当该节点跳范围内的所有s s 节点均不使 用此时隙时，请求节点才能获得此时隙的使用权。如果邻居节点同意该节点使用 此时隙时，邻居节点将保持沉默，不会作出任何响应当其他邻居节点也想使用 这些时隙时，该节点会在一定时i 日j 间隔内向请求节点返回确认帧，通知请求节点 它们在竞争此时隙时发生了冲突，然后各自调用截短二进制退避算法再随机选择 一个或多个时隙来重新请求时隙。在分布式协调调度算法中每个节点均将在本地 数据库里维持一个邻居节点的链接标志( c o n n e c t i o ni d e n t i t y ，c i d ) 数据表。 ( 4 )非协调分布式调度 分布式带宽调度的另一种方式是非协调分布式调度( n o n - c o o r d i n a t i o n d i s t r i b u t e dm e s hs c h e d u l ea l g o r i t h m ，n c d m s a ) 。它与早期的a l o h a 时隙系统 相似，节点有数据要发送它就直接发送，在传输前无须对自己邻居节点是否在发 送数据进行帧听。当数据成功地被发送时，发送节点将会收到一个从接收节点发 送的a c k 确认帧。如果数据冲突或损坏，发送站点也会调用截短二进制退避算法 再随机选择一个时隙来发送数据。如果传输过程再次出现冲突，发送节点继续随 机选择时隙发送数据。当冲突的次数达到特定的阈值时，发送节点就放弃此次数 据传输。非协调分布式调度方式的信道利用率会随着节点密度增加而显著降低 1 2 i e e e 8 0 2 1 6 dm e s h 模式中的分布式调度，采用请求、答复和确认三次握手 的方式来建立发送数据前的链接：首先由请求发送节点发送m s h - d s c h 消息中的 r e q u e s ti e 来指明要发送数据的属性以及可用的时隙，然后目标节点则根据请 求寻找合适的时隙并回复请求节点数据微时隙位置；最后，请求节点收到目标节 点回复后发送m s h - d s c h 许可消息来完成链接的建立过程。 三次握手的过程如图4 所示在该过程中，i e e e 8 0 2 1 6 d 提供了各个节点计 算自己发送机会的调度算法，以实现各个节点之自j 发送机会的公平性。 请 求 指 点 图2 4 分布式调度中三次握手示意 f i 椿 访 点 2 2 4 m e s h 模式下的分布式调度具有如下特征 ( 1 )无明确的协商：在多跳网状网络无明确调度协商的情况下支持常规广播 传输的调度，对于网络配置消息是有用的。 ( 2 )冲突避免：每个节点的扩展邻域内的调度是无碰撞的。 ( 3 )分布式：算法是完全无需中心控制的分布式的。 ( 4 ) 公平性：调度分配平等对待所有节点。 ( 5 )稳健性：调度除了是分布式之外，针对每一帧，调度种子伪随机地改变，因 此任何碰撞( 比如，由瞬时条件引起的碰撞) 都不会长存。 2 2 5 分布式方法的优点： ( 1 )使用分布式方法，当节点不能与一些节点通信时，仍然可以发包给其它节 点，但在集中式方法中，如果节点不能与基站通信，则不能传输任何包。 ( 2 )在分布式方法中，无需基站跟踪网内所有节点的状态信息”所有节点共同 维护一张状态表，但在集中式方法中，需要基站来做这种额外开销。 ( 3 )在集中式方法中，基站不能是使用电池的节点因为一旦电池用完基站就 不起作用了，此时其它节点就必须检测出该基站，并选择一个新的基站 1 3 2 3 比例分配式调度 虽然w i m a x 支持o f d m a 的模式，但是在8 0 2 1 6 d 版本协议中已经明确的规定 m e s h 型的网络采用的还是t d m a 的接入模式，所以在m e s h 网络中需要分配的无 线资源其实就是时隙。 在集中式的m e s h 网络当中，当b s 收集了整个网络的状况之后，可以通过 m s c h - c s c h 消息来对时隙的划分作统一的管理。而在分布式m e s h 网络当中，调 度信息的传递则是通过节点之问传递m s c h - d s c h 消息来实现的。m s c h - d s c h 包含 三种信息：时隙请求，时隙可用和时隙授予在8 0 2 1 6 协议中规定了一个三次 握手的过程：首先节点向网络中广播时隙请求信息，然后接收节点通过回复把可 用时隙告知请求节点，最后发送节点再次向接收节点发送时隙授予的确认信息。 调