（通信与信息系统专业论文）ieee80211e+mac协议性能优化.pdf

摘要 摘要 鉴于无线局域网w l a n 的快速发展和人们对于网络服务质量q o s 的需求， i e e e 8 0 2 1 l 小组提出了具有服务等级区分的i e e e 8 0 2 1 l e 协议草案，其核心m a c 方案e d c a ( e n h a n c e dd i s t r i b u t e dc o o r d i n a t i o n a c c e s s ) 在接入信道公平性以及优 先级划分方面性能还有很大的改进和增强的空间。 本文围绕国家自然科学基金项目“下一代互联网性能测量关键技术研究”展开 工作。首先介绍了传统“分布式协调功能”d c f ( d i s t r i b u t e dc o o r d i n a t i o n a c c e s s ) 、 i e e e 8 0 2 1 l e 协议草案，以及现有的改良方案，其次给出了在2 0 0 0 年由b i a n c h i 等人提出的经典的二维马尔科夫链分析模型。第三，在研究针对e d c a 协议提出 的基于三维马尔可夫链性能分析模型的数学描述和实现细节的基础上，加入公平 性的动态调整t x o p ( t r a n s m i s s i o no p p o r t u n i t y ) 算法，分析并通过仿真验证了其性 能的改善；第四，本文通过研究和分析现有无线局域网中为不同业务流设定优先 级的局限性，提出一种动态调整优先级的算法，将三个用来估算和调节优先级和 节点发送数据包速率的模块加入到标准e d c a 模块中，通过仿真验证，证明该算 法能够很好地根据网络的实际拥塞情况为数据流动态地进行优先级和发送速率的 调整，同时保证了业务流的带宽要求，也实现了业务区分，在丢包率和吞吐量等 性能方面较传统的e d c a 机制有了很大的改善。最后总结全文，并展望了未来的 研究方向。 关键词：无线局域网公平性服务质量i e e e 8 0 2 1 l e 动态优先级 a b s t r a c t 3 a b s 打a c t i nr e c e n ty e a r s ，i e e e 8 0 2 11w i r e l e s sl a nh a se m e r g e da sa p r e v a i l i n gt e c h n o l o g y f o rt h e ( i n d o o r ) b r o a d b a n dw i r e l e s sa c c e s s i e e e s 0 2 11c a r lb ec o n s i d e r e daw i r e l e s s v e r s i o no fe t h e m e tb yv i r t u eo fs u p p o r t i n gab e s t e f f o r ts e r v i c e ，b u tn o tg u a r a n t e e i n g a n ys e r v i c el e v e lt ou s e r s a p p l i c a t i o n s t h ei e e e 8 0 2 11w o r k i n gg r o u pi sc u r r e n t l y d e f i n i n gan e ws u p p l e m e n tt ot h ee x i s t i n gl e g a c y8 0 2 11m e d i u ma c c e s sc o n t r o l ( m a c ) s u b l a y e ri no r d e rt os u p p o r tq u a l i t yo fs e r v i c e ( q o s ) o “t h ei e e e 8 0 2 1 l ei sa n e x t e n s i o no ft h ei e e e 8 0 2 11t op r o v i d eq u a l i t yo fs e r v i c e ( q o s ) f o ra p p l i c a t i o n s r e q u i r i n gr e a lt i m es e r v i c e s h o w e v e r , w h e nu s e dw i t ht h em u l t i r a t es c h e m e ，t h e y s u f f e ru n f a i m e s sp r o b l e m o nt h eo t h e rh a n d ，t h ei e e e8 0 2 1 l ec o u l dn o te f f i c i e n t l y g u a r a n t e ean e g o t i a t e dq u a l i t yo fs e r v i c e ( q o s ) l e v e lt ou s e r sa n ds u p p o r tt h e m u l t i m e d i at r a f f i c i nt h i sp a p e r , w ea n a l y s i san o v e lm o d e lb a s e do nt h em a r k o vc h a i n ， w h i c ht a k e si n t oa c c o u n ta l m o s ta l lt h ei m p o r t a n tm a cp a r a m e t e r s ，a n du s ei tt o a n a l y s i st h ef a i m e s s - b a s e dt x o pt u r n i n gm e c h a n i s m a tt h es a m et i m e ，w ep r o p o s e da m e c h a n i s mt od y n a m i c a l l yt u r nt h ep r i o r i t yo rt h et r a n s m i s s i o nr a t eo ft h es t a t i o n ， s o l v e st h eu n f a i r n e s sp r o b l e mi nt h ei e e e 8 0 2 1l en e t w o r k se m p l o y i n gt h em u l t i - r a t e s c h e m e ，a n de n h a n c e st h et h r o u g h p u to f t h es y s t e m k e y w o r d s ：w l a n ，f a i r n e s s ，q o s ，i e e e 8 0 2 1 l e ，d y n a m i cp r i o r i t y 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我同工作的同志对本研究所做 的任何贡献均已在论文中作了明确的说明并表示谢意。 本人签名! 垄q 查塑 f 日期：妒。7 ，i ，岔 日期! 竺厶：堡 l 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属于西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。 本人签名! 二墅堑超 导师签名 日期! 日：! ：呈 日期：圭2 2 ：垒：丛 第一章绪论 第一章绪论 1 1 研究背景 近年来，以因特网为代表的新技术革命正在深刻地改变传统的电信概念和体 系，其迅猛发展的速度是人类历史上所有工业中最快的。一方面i n t e m e t 为人们 提供了大量的信息资源，另一方面移动通信解决了对通信的移动支持。 无线局域网w l a n ( w l r e l e s sl a n ) 是2 0 世纪9 0 年代计算机网络技术与移 动通信技术相结合的产物，它满足了人们对于宽带无线接入网络的迫切要求，同 时，通信网络所承载的业务也在不断地丰富。 随着i e e e 8 0 2 1 1 无线局域网( w l a n s ) 的快速发展，用户对于服务质量( q o s ) 的需求与日俱增，业务的多样化对于网络提出了不同的要求，这就需要网络为各 种不同的用户业务提供不同的服务质量q o s 保证。 所谓q o s ( q u a u t yo f s e r v i c e ) 指的是数据包在网络中传输时所要满足的一系 列的服务要求，有线网络里衡量q o s 的因素有：可用带宽( a v a i l a b l eb a n d w i d t h ) ， 数据包丢失率( p a c k e tl o s sr a t e ) ，时延估计( e s t i m a t e dd e l a y ) ，抖动( p a c k e t j i t t e r ) ， 跳数( h o pc o u n t ) 和路径可靠性( p a t hr e l i a b i l i t y ) 。然而这些因素并不完全适用于 无线网络中。这是因为，现在的有线q o s 的算法要求精确的连接状态和网络拓扑 信息，而无线连接的实时变化，有限的带宽资源和节点的移动性使得维持上述指 标异常困难。因此对无线网络来说，其q o s 保证不可能做到与有线网络中的一样。 在实际中广泛应用的无线局域网d c f 机制，对所有业务都没有q o s 保证， 为了满足无线网络中q o s 的需求，同时提高d c f 和p c f 的工作效率，为不同业 务划分不同的服务等级，i e e e 8 0 2 1 1 工作组提出了i e e e 8 0 2 1 l e 的草案，在 i e e e 8 0 2 1 l e 标准中，对d c f 进行了扩充，提出了“增强分布式协调访问”e d c a ( e n h a a c e dd i s t r i b u t e dc o o r d i n a t i o n a c c e s s ) 机制，以满足用户业务的q o s 要求。 其物理层采用的仍然是8 0 2 1 l a b g 的协议方案，其主要目标是提高其在m a c 层 的表现业务区分和服务质量保证。 1 2 无线局域网协议研究的意义与现状 无线局域网( w i 。a n ) 正在迅速地融入我们的生活，i e e e 8 0 2 1 1 标准作为 全世界部署最为广泛的w l a n 技术，被普遍认为将在下一代无线通信中发挥重要 的作用，随着近年来8 0 2 1 l w l a n 的物理层协议不断改进，无线传输带宽不断提 2 i e e e8 0 2 1 l em a c 协议性能优化 高，从最初的2 m b p s 的速率提高到现在i e e e 8 8 0 2 1 l g 和i e e e 9 0 2 1 l a 的最高 5 4 m b p s 的理论速率。与物理层带宽发展不断推进一样，媒体访问控制层( m a c ) 的协议也在不断改进和增强，由于m a c 层功能基本上是在软件上实现，所以m a c 层功能的增强可以得到更快的实现，从而可以使网络获得更高的性价比，这使得 m a c 层增强机制成为研究的一个热点。然而，由于i e e e s 0 2 1 1 技术并没有内建 对于q o s 的支持，使得i e e e 8 0 2 1 1w l a n 在提供音视频等需要q o s 保障的业务 方面遇到了极大的挑战。另一方面，由于无线带宽资源非常宝贵，为了提供尽可 能多的接入终端数，降低w l a n 部署成本，就需要提高网络的吞吐量。 近年来，各种针对w l a n 的q o s 增强技术不断的被提出，很多都提出了对 传统“分布式协调功能”d c f ( d i s t r i b u t e dc o o r d i n a t i o nf u n e t i o n ) 的协议改进方案， 其中有很多都涉及到退避算法的修改，比如d c t 2 1 算法使用两种退避算法分别对具 有两种优先级的节点，分布式公平调度( d 雷s ) 算法也采用多种退避算法等，目 的都是通过区分退避时间的大小来区分节点的优先级。然而，这些退避算法没有 全面考虑网络拥塞情况，同时其优先等级分级方法还不够细腻，尚有较大的改善 空间。事实上，作者所作之研究是基于最新的i e e e 8 0 2 1 1 协议草案i e e e 8 0 2 1 i e ， 将所有业务分为4 种接入类别a c ( a e e e s sc a t e g o r y ) ，并引入了8 种业务流( t r a f f i c s t r e a m ) 以区分优先级。利用为不同的业务流分配不同的t x o p ( t r a n s m i s s i o n o p p o r t u n i t y ) 来满足不同业务流对于传输的要求，同时综合考虑t x o p 分配时的 公平性问题。 另一方面，网络拥塞情况对于网络吞吐量的影响是巨大的。在网络拥塞的情 况下，经常不能够满足多媒体业务流的带宽要求，因此作者提出了一种通过预测 网络拥塞情况动态调整优先级和节点发送速率的算法，该算法能够在网络不同拥 塞情况下动态调整节点的发送速率以及接入的优先级，保证节点业务带宽需求。 经过仿真验证，该算法能够在吞吐量和丢包率方面提高网络性能，保证不同业务 流的服务质量。 1 3 主要内容以及章节安排 第一章，首先简要介绍了无线局域网m a c 层接入协议e d c a 的机制； 第二章，介绍了经典b i a n c h i 二维马尔科夫链分析模型，并且对其进行了改 进； 第三章，通过分析和数学公式推导，给出了基于公平性分配t x o p 的性能优 化方法，以及基于三维马尔可夫链的数学描述，通过仿真验证了其在公平性和吞 吐量上的优越性； 第四章，提出了动态调整优先级以满足不用业务流的吞吐量需求的算法，仿 第一章绪论 3 真验证了该算法能够保证不同多媒体业务流对于吞吐量的需求，同时还能够提高 网络性能，降低丢包率； 第五章，总结前述分析，并且展望了下一步的研究工作和未来研究的方向。 第二章i e e e8 0 2 1 l em a c 协议概述 5 第二章i e e e 8 0 2 1 1 em a c 协议概述 2 1i e e e 8 0 2 1 1 协议的发展 i e e e 8 0 2 1 1 无线局域网( w i ，a n ) 是一种新兴的宽带无线网络技术，因终端 的移动性和部署的灵活性而迅速普及【1 1 。1 9 9 7 年i e e e 8 0 2 1 1 标准的制定是无线局 域网发展的里程碑，它是由大量的无线局域网及计算机专家审定通过的标准。 i e e e 8 0 2 1 1 标准定义了单一的m a c 层和多样的物理层，其物理层标准主要有 i e e e 8 0 2 1 l b ，a 和g 。1 9 9 9 年9 月正式通过的i e e e 8 0 2 1 i b 标准是i e e e 8 0 2 1 1 协 议标准的扩展，它可以支持最高l l m b p s 的数据速率，运行在2 4 g h z 的i s m 频 段上，采用的调制技术是c c k ，但是随着用户不断增长的数据速率的要求，c c k 调制方式就不再是一种合适的方法了。因为对于直接序列扩频技术来说，为了取 得较高的数据速率，并达到扩频的目的，选取的码片的速率就要求更高，这对于 现有的码片来说比较困难；对于接受端的r a k e 接收机来说，在高速数据速率的 情况下，为了达到良好的时间分集效果，要求r a k e 接收机有更复杂的结构，在 硬件上不易实现。 i e e e 8 0 2 1l a 工作在5 g h z 频段上，使用o f d m 调制技术可支持5 4 m b p s 的 传输速率。8 0 2 1 l a 与8 0 2 1 l b 两个标准都存在着各自的优缺点，8 0 2 1 i b 的优势 在于价格低廉，但速度较低( 最高l l m b p s ) ：而8 0 2 1 l a 优势在于传输速率快( 最 高5 4 m b p s ) 且受干扰小，但是价格相对昂贵。另外，8 0 2 1 l a 与8 0 2 1 l b 工作在 不同的频段上，不能工作在同一a p 的网络里，因此8 0 2 1 l a 与8 0 2 1 l b 互不兼容， 为了解决上述问题，为了进一步推动无线局域网的发展，2 0 0 3 年7 月，8 0 2 1 1 工 作组批准了8 0 2 1 l g 标准，与以前的8 0 2 1 1 协议标准相比有以下两个特点： 1 ) 其在2 4 h z 频段使用o f d m 调制技术，使数据传输速率提高到2 0 m b p s 以上； 2 ) i e e e 8 0 2 1 l g 标准能够与8 0 2 1 i b 的w i f i 系统互相连通，共存在同一a p 的网络里，保障了后向兼容性。 这样原有的w l a n 系统可以平滑地向高速无线局域网过渡，延长了 i e e e 8 0 2 1 l b 产品的使用寿命，降低用户的投资。然而由于i e e e 8 0 2 1 1 系列协议 对q o s 几乎没有任何保障，为了有效支持q o s 以及服务等级区分，i e e e 8 0 2 1 1 任务组提出了i e e e 8 0 2 1 l e 协议草案。 6 i e e e8 0 2 1 l em a c 协议性能优化 2 2i e e e 8 0 2 1 1 协议介绍 2 2 1 传统i e e e 8 0 2 1 1 信道接入机制 i e e e 8 0 2 1 1 媒体接入控制( m a c ) 子层协议 3 1 定义了两种信道接入方式：基 本的分布式协作模式( d c f ) 和可选的点协作模式( p c f ) 。 1 、分布式协作模式 在分布式协作模式( 图2 1 ) 中，当一个节点检测到物理信道空闲时间超过 分布式协作模式帧间隔( d i f s ) 之后，节点进入退避状态，每个节点维护一个退 避计时器，此计时器从b a e k o f f t i m e = r a n d 0 ，c w 】* s l o t t i m e 中取值并按照时槽 递减，这里c w 为当前竞争窗口。当退避计时器为0 时，节点发出请求发送( r t s ) 信号。如果在规定时间内没有允许发送( c t s ) 信号返回，则节点认为发生了冲 突从而使竞争窗口加倍，选择新的退避计时器重复上面的操作。 图2 1 分布式协作模式d c f 2 、点协作模式 点协作模式是8 0 2 1 1 可选的工作方式，具有比分布式协作模式更高的优先级。 点协作模式使用接入点( a p ) 控制的轮询调度策略，在允许点协作模式工作的情 况下，接入点通过检测信道空闲点协作模式帧间隔( p i f s ) 来抢先捕获信道，通 过发送信标来发起信标间隔( 又被称为超级帧) 。在这个超级帧里，非竞争期和竞 争期交替进行。在非竞争期，接入点首先通知各个节点屏蔽各自的分布式协作模 式，并在自己的节点列表里选择一个节点给予发送数据的机会。最后接入点发送 c f - e n d 信号来结束非竞争期，进入竞争期周期。图2 2 表示了点协作模式的工作 方式。 3 、传统i e e e 8 0 2 1 1 协议q o s 的局限 传统的i e e e 8 0 2 1 1 协议对q o s 的支持非常糟糕，从上面的描述可以看出， 第二章i e e e8 0 2 1 l em a c 协议概述 7 分布式协作模式没有区分业务类型，各种业务在同一优先级下竞争信道，仅仅提 供了“尽力而为”型的服务，没有任何q o s 保证。 对于点协作模式，其q o s 支持也具有很大的局限性：由于竞争期节点发送的 数据长度不能控制，使得下一个目标信标传输时间( t b t t ) 的信标发送产生延迟； 而在非竞争期被轮询的节点发送的数据大小也不可控制，因此节点的传输时间也 不容易被接入节点所控制；接入点的轮询调度算法过于简单，同样没有区分业务 类型。 以上所述说明了i e e e 8 0 2 1 1 在q o s 保障方面还存在很大的改进空间。大量 的研究工作都针对其协议的q o s 性能增强工作，进行了多方面的探索和研究。 图2 2d c f p c f 协作模式 2 2 2 针对0 0 s 增强技术i e e e 8 0 2 1 l e 针对传统的i e e e s 0 2 1 1 协议的q o s 增强主要集中在以下几个方面：在分布式 协调模式中，通过修改协议参数，比如退避算法、帧间隔、最大最小竞争窗口， 最大帧长度等来区分优先级；在点协作模式中，通过修改调度算法等来实现q o s 的增强。 为了有效地支持q o s ，i e e e 8 0 2 1 1 任务组提出了i e e e s 0 2 1 l e 协议，在此协 议中，所有业务被分为4 种接入类别( a c c e s sc a t e g o r y ) ，并引入了8 种业务流 ( 1 m m cs t r e a m ) 以区分优先级。 l 、增强分布式协作模式 增强分布式协作模式( e d c f ) 引入了4 个队列，这4 个队列对应于8 个优先 级，每个队列都独立工作，首先在一个8 0 2 1 l e 节点内部争夺传输的机会( t x 0 p ) ， 获得传输机会的队列才能够真正获得信道接入的机会，如果有两个队列同时获得 传输机会，则通过一个调度器来根据优先级调度一个队列接入信道，见图2 3 1 4 1 。 8 e e e8 0 2 1 l em a c 协议性能优化 当节点竞争到数据传输的机会，e d c f 提供数据突发传输的机会，也就是给节点 传输设定t x o p ，只要节点的传输不超过t x o pl i m i t ，就可以以s i f s 时间间隔 持续发送数据包而无需再竞争信道，只有当碰撞发生时，才退出“突发数据传输”。 这种机制的提出旨在提高网络的吞吐量，减少不必要的竞争信道而浪费的带宽资 源，但是突发数据业务有可能增加抖动，因此t x o p a i m i t 的设定应该不超过发送 最长的数据包所需要的传输时间。 图2 3i e e e 8 0 2 1 l e 接入调度队列 在增强分布式协作模式中，还有一个重要的概念是仲裁帧间隔( m f s ) 。在节 点内部，不同队列所拥有的帧间隔、退避时间和竞争窗口各不相同。增强分布式 协作模式中的帧间隔用有优先级区分的 a i f s a c i 】= a i f s n a c , + s l o t t i m e + s i f s 来表示。每个接入类别队列的退避算法 为b a c k o f f t i m e a c 。】= r a n d ( 1 ，c w a c i 】) + s l o t t i m e ，其竞争窗口计算为： n e w c w a c i 】= ( ( o l d c w a c 。】+ 1 ) p i o - 1 图2 4 表明了增强分布式协作模式的 工作细节。 ， c m m t d 口- m _ l _ 曲d - d h 图2 4 增强分布式协作模式e d c a 第二章i e e e8 0 2 1 l em a c 协议概述 9 2 、混合协作模式 混合协作模式( h c f ) 的q o s 保障是基于接入点和节点间的业务量规范( t r a 伍c s p e c i f i c a t i o n ) 协商而建立的。在开始发送有q o s 要求的数据之前，在接入点和 节点之间建立一种叫做业务流的虚拟连接，将平均数据速率、时延限制等t s p e c 参数传递给接入点，接入点根据这些参数计算分配给各个节点的p o l l e d - t x o p ， 并将各个p o l l e d - t x o p 与节点关联起来。通过这种方式，每个节点中的调度器根 据不同的优先级将发送机会和业务流联系起来。 值得注意的是，在i e e e 8 0 2 1 l e 的竞争周期，接入点可以随时控制信道，这 个时间段称为控制接入状态( c a p ) ，在a p 控制时间内，当一个节点受到q o s c f - p o l l 帧之后，被允许以无竞争突发模式( c o n t c n t i o n - f i 宅eb u r s t ) 连续地发送多 个m a c 帧，其接入信道的时间总和不能超过接入机会t x o p 的时间限制。如果 节点没有数据发送，则发送一个q o s - n u l l 帧返回接入点，接入点接着轮询其他节 点。 2 3 二维马尔科夫链的数学描述 2 3 1b i a n c h i 的二维马尔科夫链数学模型 2 3 1 1 数学模型分析 b i a n c h i 在【5 】中介绍了一个简单的二维马尔科夫链模型来分析i e e e 8 0 2 1 1d c f ( d i s t r i b u t e dc o o r d i n a t i o nf u n c t i o n ) 在饱和情况下的性能表现，如吞吐量、时延 等重要性能指标。此二维马尔科夫链模型由于操作简单而广泛应用于关于 i e e e 8 0 2 1 1 协议的性能分析中。如【7 胴中应用其分析了变量对其退避算法的性能 影响；恻中在不同假设条件下对其分析的改进等。 性能评估一般有两种途径，其一是通过仿真，另外一个就是在特定退避算法 的基础上建立分析模型。b i a n c h i 的模型是建立在理想环境下的( 无隐藏终端，无 捕获效应) 对饱和吞吐量的分析。所谓饱和吞吐量是指，网络随着负载数量增多 在吞吐量下降前的最大值，是网络过载的吞吐量，也就是要保证发送队列中始终 有数据需要发送。首先以单一节点的二维马尔科夫链为分析的基础，然后假定网 络中有n 个节点，每个节点以概率f 试图接入信道。 假定b ( t ) 为表示退避计时器的一个随机过程，t 和t + 1 分别表示两个相邻的时 隙的开始时刻，在这些离散的时刻点，每个节点的b ( t ) 减1 ，其中假定时隙长度 1 0i e e e8 0 2 1 l em a c 协议性能优化 为盯。而遇到信道忙时，退避计时器“冷冻”起来，即保持其现有的值不再减少， 直到信道再次空闲，退避计时器从现有的值开始继续减少。由于退避计数器的值 与它以前的状态是有关的( 例如之前重传次数等等) ，所以它并不是一个马尔科夫 过程。随后，定义w = c w 血，而c w 一= 2 “+ w ，其中m 为最大退避阶。称 w i = 2 hw ，i ( o ，m ) 为退避阶。定义s c t ) 表示节点在t 时刻的退避阶( o ，m ) 的随机过程。 图2 5 退避窗口的二维马尔科夫链 b i a n c h i 二维马尔科夫链模型假定网络中的节点的碰撞概率为p ，此概率与节 点重传次数无关。这样的话，二维马尔科夫链就建立起来了，如图2 5 。 采用p i l ，k li i o , k o ) = p s ( t + 1 ) = i l ，b ( t + 1 ) = k lis ( t ) = i o ，b ( t ) = k o ) 的简略表示方 法，则上图二维马尔科夫链中一步转移概率不为零的为： p i ，k i i , k + 1 ) = 1 , k ( o ，w j 一2 ) ，i ( 0 ，m ) p 0 ，k l i ，0 = ( 1 一p ) w o ，k ( o ，w o 1 ) ，i ( 0 ，m ) p i ，k i i 一1 ，o = p w i ，k ( o ，w i 1 ) ，i ( 1 ，m ) p m ，k l m ，o ) = p w 二，k ( o ，w 二一1 ) ( 2 1 ) 对上述等式作如下解释：第一个等式描述了在每个时隙开始的时刻，退避计 时器减l 的情况；第二个描述了在成功传输了一个数据包之后，发送一个新的数 第二章i e e e8 0 2 1 i em a c 协议概述 据包需要从退避阶段0 开始退避的情况；第三个等式描述了当在退避阶段i 1 处 数据包传输失败，退避阶增加，而新的最初退避值从( o ，w i ) 中随机选取；最后一 个等式表示一旦退避阶到达其最大值m ，则它将在随后的数据包传输中不再增加。 本节以下所有的性能分析，都是基于上述二维马尔科夫链的描述。 定义b 址= l i m t 。p ( s ( t ) = i ，b ( t ) = 埘，i ( 0 ；m ) ，k e ( o ，w 一1 ) ，可以得到关于这 个二维马尔科夫链的闭合解。经过一系列推导，可以得出： b i - k = 鼍b i o , i ( o ，m ) ，k ( o ，w i 一1 ) ( 2 2 ) = 石面丽2 ( 雨1 - 万2 p ) ( 两1 - p 矿) b o o 西而( 2 - 3 )。石面丽雨万两矿西而 这样，节点在任一时隙发送数据的概率可以表示为： 仁 ；。b i o b oo 五= 而丽万丽2 ( 1 石- 2 p 丽) 丽 2 - 4 ) 经分析得，碰撞概率p 与节点发送数据包的概率f 之间的关系为： p 5 1 一o 一力” ( 2 5 ) 等式( 2 - 4 ) 和( 2 - 5 ) 构成了一个关于p 和f - 的非线性的方程组，通过数学方 法可以得到唯一解。 2 3 1 2 吞吐量分析 吞吐量t h r o u g h p u t 的定义为信道在单位时间内成功传输的数据比特数，这里 用s 表示。t h r o u g h p u t 是衡量网络性能的一项重要的指标，任何有关网络性能的 分析，都必须分析网络的吞吐量。 这里用k 表示在一个时隙内，至少有一个传输的情况。由于n 个节点竞争信 道，而每个节点接入的概率为f ，用p i 表示成功传输的概率，则 p ；= l 一( 1 一力4 ，。、 1 2i e e e8 0 2 1 i em a c 协议性能优化 只= 竿 按照吞吐量的定义， ：n r ( 1 - r ) q i - ( 1 - r ) “ ( 2 7 ) s ：堑全堕堕堕堕堕堡塑箜堡垦! ( 2 - 8 ) 。 e 【时隙长度】 用e 口】表示平均的数据包长度，则在一个时隙内成功传输的信息为气p i e p 1 ， 则时隙空闲的概率为1 - l ，时隙长度为o r ；成功传输的概率为k e ，平均时长 为t ；发生碰撞的概率为( 1 - p , ) ，平均时长为t c 则( 2 - 8 ) 式可以表示为： s = 两两糕 c 2 聊 ( 1 一p 灯炒+ p 3 t | + 凡( 1 一p i ) t c “7 上式中的t 和t c 根据接入模式的不同有不同的表达定义h = p h y b + m a c h 为包头长度，艿为传输时延，则在基本接入模式下，表达式为： 中= h + e p i + s 环s + 万+ a c k + d s + o ( 2 1 0 ) 中= h + e p + + d i f s + d 其中e p 】为在一次碰撞中最大包的平均长度。在传输包长都相同的情况下， e p 】= e 吲= p 。在般情况下，e p + 】是一个随机数 在r t s c t s 模式下，碰撞只会发生在r t s 帧中。上述表达式变为： f = r t s + s s + j + c t s + s s + 占+ h + e 唧+ s 巧s + 占+ a c k + 肼s + o ( 2 1 1 ) 王，= r t s + d i f s + 艿 2 3 2b i a n c h i 二维马尔科夫链的改进 尽管b i a n c h i 二维马尔科夫链由于其应用简单操作方便而在众多关于 i e e e s 0 2 1 1 的性能分析中得到应用，但是它也有一些明显的缺陷。首先，它仅仅 分析了吞吐量，并没有给出无线局域网中其它的重要参数的计算，如包处理速率， 平均包时延等等。其次，在6 次重发数据包之后，退避窗口的大小应该保持为最 大值( 1 0 2 4 b y t e ) 。同时，他没有考虑由于碰撞所因此的数据包的丢失情况，而这 第二章i e e e8 0 2 1 i em a c 协议橛述 1 3 种情况在文纠5 】被证明是非常重要的。最后，他的分析是基于前提“饱和”吞吐 量的，也就是说，网络能够达到的最大的吞吐量，而事实上网络并不总是饱和的。 在文章【9 】中，作者提出了考虑发送失败后的重发次数对b i n a n c h i 二维马尔科夫链 的改进；在文章1 1 0 1 中作者假定信道有误码的情况；在 1 1 】中指出了隐藏终端的影响， 这些分析都扩展了b i n a n c h i 二维马尔科夫链的分析，使得它的分析结果能够在更 接近于真实网络的情况。 这里提出一种网络在非饱和状态下( 有限状态) 的性能分析方法，饱和吞吐 量仅是这里分析的一个部分，或者说种极限的状态。假定： 1 、数据包只在碰撞情况下被丢弃( 忽略信道原因) ； 2 、忽略隐藏终端； 3 、数据包传输失败的概率定义为常数p ； 4 、数据包的到达服从参数为a 的泊松分布。 与b i a n c h i 的参数假定相同，我们假定竞争节点数为n ，b ( t ) 表示一个给定节点 退避计数器的随机过程，s ( 0 表示在时刻t 退避阶的随机过程。这里引入一个非饱 和( 有限状态) 的二维马尔科夫链。 假定口为数据包处理速率，而q l 为节点中等待队列长度，则应用m m i q i 分析模型，得到节点没有数据发送的概率q 为； i z 上f q。一i-(3j)q,+1 ( 2 - 1 2 ) 在网络有非饱和情况时，假定以下几种状态：在饱和情况下，节点试图第一 次接入信道时的状态为s o f i ；在非饱和状态下，当发送队列空( 其概率为q ) ，则 节点进入状态s 以。在状态s o 时，即节点处于第0 个退避阶，并且退避计时器 已经为0 ，而发送队列中又没有数据包时，如果此时有数据包到达，则节点退避 状态应转移为s ，其状态转移概率为珞o ，否则，此节点转移到状态s 幽，。下， 其状态转移概率为幽。在状态s 幽，。下，一旦一个数据包到达发送队列中，而 信道空闲时间大于d i f s ，则这个数据包可以立即发送，此事件发送的概率为 p 江。，否则，此节点转移到状态s o i ，其概率是。一而上述状态转移概率分 别计算如下： b 。：1 - e 忡，2 ( 2 - 1 3a ) 昂讪：e - j - w o o ，2 ( 2 1 3b ) 1 4i e e e8 0 2 1 l em a c 协议性能优化 k 。：( 1 一e x l p ) 一，一+ e - 如m ( 1 一匕( 。- 1 ) ) d - i n s ( 1 一e n ) 芝e m ( 1 一气。) ) ( t + n ( 2 1 3 c ) p l 蝴= 1 一。o ( 2 - 1 3 m 其中仃如( 2 - 9 ) 中分母所示，为时隙平均值，p 订( n - 1 ) 为( n - 1 ) 个节点中至少有一 个发送数据包的概率。 根据上述所有参数的计算，可以按照b i a n c h i 的方法来计算b ( o ，o ) p 和f ，最 终得到一个闭合解。这里给出b ( o ，o ) 的表达式： 由于 b ( i 一1 ，0 ) p = b ( i ，o ) ，0 i m ( 2 1 4 ) 则可以得出 姜b ( i ，o = ( 1 + + p 4 ) b ( o ，o ) = 皇学( 2 1 5 a ) ，o ) = ( 1 + + p 4 ) b ( o ，o ) = 型等等l ( 2 a ) i l 。r b ( m , o ) = p = + l b ( 0 ，0 ) ( 2 1 5b ) 对于k 1 ，w i - 1 ，可以得到： b = 等 m ，o ) 】，o i m 一1 ( 2 - 1 6 ) 当i = 0 时，可以得出： b ( o ，o ) = b ( o ，w ) + j + b ( i d l e ，o ) + l 唧+ b ( i d l e , 0 ) + 。(2-17) ( 1 - q ) b ( m ，o ) + ( 1 一p ) ( 1 一q ) b ( i ，o ) f = 善b ( i ，o ) = b ( o , o f ) ( 1 - p m + 2 ) ( 2 - 1 8 ) i o一上， 则根据( 2 1 6 ) ，( 2 - 1 7 ) 和( 2 5 ) 式，可以得到唯一的闭合解。 以下我们分析几个b i a a c h i 分析模型中没有涉及然而却是衡量网络性能的重 要的指标； 1 、数据包处理速率 对于一个给定的节点，在饱和情况下，在一个时隙成功传输一个数据包的概 率是f 。0 一q ) “，因此，处理速率是 第二章i e e e8 0 2 1 l em a c 协议概述 1 5 ：堡垡二三2 ： 以 ( 2 1 9 ) 2 、数据包丢失分析 数据包丢失有两种情况，一种是在状态s 。时，节点丢弃数据包，重设其退 避窗口，进入新的退避状态下。由于碰撞导致的数据包丢失的概率为： p k = p b ( m ，o ) - - p 4 + 2 b ( 0 ，0 ) ( 2 2 0 ) 另一种情况是由于队列溢出所导致的数据包丢失，此概率为： = 掣q 当黼( 2 - 2 1 ) 所以，总的数据包丢失概率应该为 p l = p k + 气 3 、延时分析 数据包的有效到达率应该为 五d = 五一2 ( 2 - 2 2 ) ( 2 - 2 3 ) 利用m m 1 q 。模型，结合式2 1 6 ，可以得到在系统中平均数据包数量为： n ：r ( 1 - i ( q i + = 1 ) r _ a 气+ q 五t r 一q + l r ) 萁中玎：生( 2 - 2 4 )( 1 一叩) ( 1 - r q l “) ”一。 4 、t h r o u g h p u t 再分析 这里我们再一次对公式( 2 - 9 ) 中的参数进行计算，在重新考虑了节点退避 计时器“冷冻”状态之后，分析如下：忽略捕获效应，一个成功传输就意味着其 它“侦听”节点的退避计时器的值在传输帧的时刻大于等于1 ( 否则将会发生碰 撞) 。根据d c f 的规定，在信道空闲d i f s 时间后，一个侦听节点将会再等待一 个退避时隙仃之后开始减少它的退避计时器的值，这样，只有成功传输的节点能 1 6 i e e e8 0 2 1 i em a c 协议性能优化 够在。i f s 时间后成功接入信道。而成功接入的节点将会以概率b e = 去且 退避计数器的值为0 而无竞争地接入信道。所以，成功传输的帧不应该只包含平 均载荷的数量，而应该是 明= e p 】+ 知i = 0e 【p 卜器 ( 2 _ 2 5 ) 。 一o 而成功传输一帧的时间应该是： t s 2 t i + 姜b ：t l + a - - - - 高i - 0一o t c = t c + 仃 ( 2 2 6 ) ( 2 - 2 7 ) 如果没有特殊说明，以后三维马尔科夫链的参数说明与本小节的相同a 2 4 小结 本章通过对经典的b i a n c h i 二维马尔科夫链模型分析，针对其局限性作出了改 进，给出了无线网络性能分析中除了吞吐量之外的更多的性能指标的分析。为后 面一章介绍三维马尔科夫链分析模型以及作者提出的公平分l e t x o p 算法做好了 理论准备 第三章基于公平性的协议改进方案 1 7 第三章基于公平性的协议改进方案 3 1 协议改进方案的提出 i e e e 8 0 2 1 1 的c s m a c a 机制给所有接入节点提供了公平接入信道的机会，当 所有节点发送的数据包长度相同时，他们就能够得到相同的吞吐量( 这就是基于 吞吐量的公平性) ，这种公平性方案也可以被继承到m e e 8 0 2 1 l e 的协议中去对 于同一优先级的各节点来说，他们接入信道的概率理论上是相同的，所以吞吐量 公平性在i e e e 8 0 2 1 l e 中就体现为对于同一优先级的不同速率的各节点享有相同 的吞吐量。在文章【1 2 1 1 3 】中，作者证实了在同一信道条件下，两个发送不同速率数 据包的节点的饱和吞吐量最终都会趋近于低速率节点的吞吐量。在吞吐量公平性 的原则下，发送一帧数据所需要的时间就取决于数据发送速率，而低速率的数据 包必然需要长一些的时间来发送。这就导致对于高速率节点的不公平一高速率 节点的吞吐量受到低速率数据包的“拖累”而变小，而网络信道利用不足，整体 吞吐量也在下降。 文章【1 4 1 中提出了一个“时间公平”的方案，即让高低速率的节点能够占据信道 的时间的统计平均值相同。这个方案被证明能够得到比“吞吐量公平”原则下更 大的吞吐量，同时每个节点的吞吐量也不会比单速率网络中节点的吞吐量小。 所以这里应用文章【1 4 】中提出的“时间公平性”来代替“吞吐量”公平性，并且根 据此原则动态调整t x o p ，试图达到q o s 保证和提高网络吞吐量的双重目标。 3 1 1 公平性的定义和讨论 公平性是一个包括优先级，应用服务要求等等内容在内，需