（通信与信息系统专业论文）ieee+80211无线网络媒体接入层性能改进与增强.pdf

北京邮j 自大学博士论文中史摘篮 中文摘要 近年来，无线局域网以其廉价、方便、快捷的无线接入方式日益为越来越多的 人所青睐，关于无线局域网的技术也逐渐引起了各方面包括学术界和工业界的广 泛关注和深入探讨研究。目前业界无线局域网比较成熟的技术包括 g e g8 0 2 1 l 协议簇和e t s ih i p e r l a n 协议簇。由于i e e e8 0 2 1 1 实现简单且在通常单跳网络 环境下性能较高，日益发展成为无线局域网的主流协议和工业界主流标准。然而 在某些情况下协议性能较差，需要改进。本文主要对基于i e e e8 0 2 1l 胁议的无 线网络进行了以下研究： ( i ) 通过剥无线局域网负载因子( 即平均碰撞时长与空闲时长之比) 与竞争站 点数的理论分析观察到：在重负载下调节站点接入概率使得链路吞吐量达到最优 时，负载因子从数值上具有与当前竞争信道站点数以及碰撞时长近似无关的特性。 据此本文设计了神全分布式的自适应媒体接入协议n s a d 以提高重负载下系统性 能。仿真表明算法相比原来i e e e8 0 2 1 ld c f 协议n s a d 可以达到较高的吞吐量和 公平性。 ( 2 ) 基于n s a d 协议，在建模分析的基础上提出了一种可提供高优先级用户带 宽保证的新算法q o s - n s a d 。q o s - n s a d 采用赋予高优先级站点和低优先级站点不同 的自适应特性的方法 w 。ow = w 。； c ) 退避时长计算：b a c k o f ft i m e = r a n d o m 0 + a s l o t t i m e ，r a n d o m ( ) 均匀分布于 o ， w 。a s l o t t i m e 是代表一个时隙的时长。i e e e8 0 2 1 l 中如果使用直扩系统 ( d s s s ) 作为物理层，时隙长度在协议中为2 0 u s 。 上述协议规程只是对d c f 协议工作的机制作了简单描述，为后续行文稍作锱 垫。在之后章节论及具体问题时还将仔细分析相关的i e e e8 0 2 ，1 1 协议细节。 i e e e 8 0 2 1 l 协议标准可以参见 1 。 由于d c f 是基于c s m a c a 的共享信道接入方式，是以尽力而为的方式传送数 据包，因此难以对实时业务提供任何时延、丢包率等0 0 s 保证。由于应用的需要， 在d c f 的基础上形成了p c f 类似于基站控制的接入方式。 点协调功能( p c f ) 点协调功能p c f ( p o i n tc o o r d i n a t i o nf u n c t i o n ) 是一个可选项，需要有a p 的 支持。p c f 提供了面向连接无需竞争的轮询传输方式。轮询表的维护以及轮询序列 的确定可以根据不同的算法实现有所不同。图卜4 表明了d c f 和p c f 的共存。 s o u r 望叵 j 婴匝 j e ! 一 r 1r 1 f型 | 型 一 图卜4 ：d c f 和p c f 的共存 - 1 3 北京邮电大学博士论文第一章绪论 l 一无竞争阶段一 图1 - 5 ：p c f 数据帧的传送 图1 - 5 中显示了无竞争阶段p c f 下数据包的传送流程。图中d 和u 分别表示 下行数据包和上行数据包。首先，如果信道空闲超过p i f s ( p c fi n t e r f r a m e s p a c e ) ，则a p ( a c c e s sp o i n t ) 发出b e a c o n 表明c f p ( c o n t e n t i o n f r e ep e r i o d ) 开始。接着a p 以轮询的方式在a p 和主机之间进行数据包的交换。在这个时期主 机发包是完全被动的。由于p c f 是通过a p 集中式控制接入信道，相对分布式的d c f 较容易实现q o s 的保证。但是有研究表明，在许多情况下p c f 由于其轮询的特性 整体性能低于d c f 。同时由于p c f 实现比较复杂，也不能支持多跳通信，通常研究 和实现得较多的还是d c f 媒体接入规程。本文的改进机制也都是基于i e e e 8 0 2 1i d c f 媒体接入规程的。 1 2本论文的主要贡献 1 - 2 1重负载下i e e e8 0 2 1 1 无线局域网媒体接入层自适应随机接入 机制的设计 如前所述，i e e e8 0 2 1 1 无线局域网协议是基于p - p e r s i s t e n tc s m a 所有站点以 相同概率接入信道对等竞争从而达到无线资源共享的目的。具体实现机制是以一 定竞争窗口( c c o n t e n t i o nw i n d o w ) 太小接入信道并使用窗口二进指数退避( b e b ， b i n a r y e x p o n e n t i a l b a c k o 蚰，即一遇碰撞窗口值加倍。这种机制具有一定自适应特 性。当站点数较少、竞争不是很剧烈时由于碰撞退避使得站点在接入概率上减小， 能够达到减小碰撞提高吞吐量的目的，使得系统吞吐量接近最优。然而当站点数 较多时，b e b 的机制会引起吞吐量和公平性的问题。通常的解决手段是增强协议 北京酆电主学博论交 第一审绪论 的自适应特性。本章内容通过引入一个反映网络负荷的参量负载因子，此参量具 有在所有站点以近似最优的概率接入信道的情况下基本保持不变的优照特性。通 过调节所有站点接入概率使负载因予达到最优值就可以达到减小碰撞，提高当前 网络吞吐量的目的。仿真结果验证了所提出的算法的有效性。 1 2 2i e e e8 0 2 1 1 无线局域网提供带宽保证的相关机制的研究 传统的网络中服务质量的保证是通过交换节点调度实现的。然而在无线局域网 的环境下，所有站点分布式的按入信道。在这种环境下由于用户之间的竞争碰撞， 服务质量保证难以实现。由于上层业务( 比如多媒体业务等) 的需要，在分布式 的竞争换，x 、环境下针对不同的业务和不同的用户提供一定的q o s 保障( 例如带宽 保证) 成为无线局域网中需要解决的问题。在这一部分中，我们通过为不同优先 级的用户设定不同的自适应参数调节范围使得在系统容限范围内高优先级的用户 能够保证自己的吞吐量不随其他站点的接入而发生变化。在此为了推导系统饱和 吞吐量性能，我们针对以不同概率接入从而达到区分优先级的分布式多优先级随 机接入系统引入了一种多优先级站点依概率接入共享信道的近似建模方法。通过 建模分析和仿真试验我们验证了算法的有效性，高优先级用户即使在低优先级用 户较多的情况下依然能够保证自己的带宽。 1 2 3i e e e8 0 2 i i 协议在噪声信道环境下性能建模与增强 无线局域网应用场景经常是室内或者机场等环境。这种环境下往往存在其他无 线系统( 比如蓝牙系统) ，环境噪声较大信道衰落严重。因此，研究环境噪声以及 底层误码对协议性能的影响是很有必要的。这部分内容首先在建模基础上分析研 究了i e e e8 0 2 1 1 无线局域网在噪声环境下的吞吐量性能。从误码丢包和碰撞丢包 对协议性能影响的角度分析了d c f 的r t s c t s d a t a a c k 握手机制，并指出了 在无线局域网环境下r t s c t s 握手失败和d a t a a c k 握手失败所包含的不同语 义。在此基础上我们提出了背靠背重传( b b a c k t o b a c kr e t r y ) 机制。这种机制避 免了不必要的退避握手等协议开销从而达到提高吞吐量的目的。通过理论建模和 仿真试验我们看到b r 机制能够较好地提高系统性能。 北京衄电太学博士论文第一芾绪论 1 2 4i e e e8 0 2 1 1 协议多跳下性能建模与增强 在这一部分中我们主要提出了一种媒体接入层的机制r 2 d p d ，以改进基于 i e e e8 0 2 1 l 无线网络在扩展到多跳情况下，当网络站点竞争分布不均匀时的网络 整体性能。采用的主要思想是利用媒体接入子层所获取的碰撞信息与路由协议交 互，从而使得路由层的选路智能化。为此，与以往协议不同，我们在媒体接入层 利用了前面所述与竞争相关的参数负载因子，并通过设计媒体接入层的丢包机制 对路由包进行随机丢弃。我们的机制主要是在媒体接入层设计，能够较好感知底 层碰撞，同时独立于上层具体的选路协议。仿真结果表明r 2 d p d 能够明显提高系 统整体性能。 1 3本文的结构和安排 本文内容安排如下： 在第二章引入了一个与站点竞争碰撞相关的参数负载因子，通过理论分析我 们观察到，在站点接入概率达到最优时负载因子数值解近似稳定在个确定值附 近。在此基础上，我们提出了一种新型的自适应媒体接入协议( n e w s e l f - a d a p t d c f a l g o r i t h m ，n s a d ) 。 之后的第三章基于前一章的自适应无线局域网m a c 仂汶在一种新的近似建 模分析的基础上提出了一种提供高优先级用户带宽保证的新算法q o s n s a d 。 q o s n s a d 采用赋予高优先级站点和低优先级站点不同的自适应特性的方法，很 好地保证高负载环境高优先级用户的q o s 特性。 第四章的内容主要是从i e e e8 0 2 1 1d c f 在误码情况下的性能分析与增强入 手。通过对噪声信道环境下i e e e8 0 2 ，1 1d c f 的建模，以及对i e e e 8 0 2 1 1d c f 机 制在噪声环境下的缺陷的仔细分析，提出了背靠背重传( b a c k t ob a c kr e t r y , b r ) 以 及简单噪声感知( s i m p l en o i s e a w a r e ，s a ) 两种机制。 第五章我们主要目的是提高i e e e8 0 2 1 1 扩展到多跳环境下的性能。在这一部 分里我们在媒体接入层利用了前面所述与竞争相关的参数负载因子，并通过设计 媒体接入层的丢包机制对路由包进行随机丢弃。由于我们的机制主要是在媒体接 1 6 苎要塑曼查兰兰主兰兰 笙二：兰堕笙 入层设计，能够较好感知底层碰撞，同时独立于上层具体的选路协议，可以作为 i e e e8 0 2 1 1 无线局域网扩展到多跳中继时的媒体接入层机制。 最后是结束语，对全文进行了总结，指出了目前在研究中还存在的一些问题 和不足，并给出了下步可能的研究课题和相应的一些设想。 1 4 本章参考文献 【2 】 【8 9 1 0 】 1 1 】 1 2 】 1 3 】 【1 4 】 i e e es t a n d a r d ，p a r t1l ：w i r e l e s sl a nm e d i u ma c c e s sc o n t r o l ( m a c ) a n dp h y s i c a ll a y e r ( p i t y ) s p e c i f i c a t i o n s ，i s o h e c8 8 0 2 1 1 ：1 9 9 9 ( e ) ，a u g 1 9 9 9 l k l e i n r o c ka n dea t o b a g i ，p a c k e ts w i t c h i n gi nr a d i oc h a n n e l s ：p a r tl - - c a r r i e rs e n s e m u l t i p l e - a c c e s sm o d e sa n dt h e i rt h r o u g h p u t d e l a yc h a r a c t e r i s t i c s ，i e e et r a n s a c t i o n so n c o 盘溉嚣垃0 2 ：，、， 1 ：c 盘2 ：，n o 1 2 ，d e c 1 9 7 5 a m u q a t t a s ha n dm k h m z ，c d m a - b a s e dm a c p r o t o c o lf o rw i r e l e s sa dh o cn e t w o r k s ， a c mm o b i h o c 2 0 0 3 ，j u n e1 - 3 ，2 0 0 3 ，a n n a p o l i s ，m a r y l a n d ，u s a 陈如明，中国3 g 演进市场前景及相关发展策略，电信科学，2 0 0 3 1 2 范志峰，w i 。f i 与3 g 的无缝融合一业务和应用的融合，电信科学，2 0 0 3 1 0 e t s i ，h i g hp e r f o r m a n c er a d i ol o c a la r e an e t w o r k ( h i p e r l a n ) t y p e1 ；f u n c t i o n a l s p e c i f i c a t i o n ，e n3 0 0 6 5 2v 1 2 1 ( 1 9 9 8 - 0 7 ) g i u s e p p ea n a s t a s i ，l u c i a n o l e n z i n ia n de n z om i n g o z z i ，h i p e r l a n 1m a cp r o t o c o l ： s t a b i l i t ya n dp e r f o r m a n c ea n a l y s i s ，i e e ej o u r n a lo ns e l e c t e da r e ao fc o m m u n i c a t i o n s v 0 1 1 8 ，n o 9 ，s e p t 2 0 0 0 ，p p l 7 8 7 2 0 0 0 j o s tw e i m 茁d l l e r , m o r l 龆s c h l a g e r , 。h d 】浩鹊f e s t a ga n da d a mw o l i s z p e r f o r m a n c es t u d yo f a c c e s sc o n t r o li nw i r e l e s sl a n s - i e e e8 0 21 1d f w m a ca n de t s ir e s1 0h i p e r l a n ，m o b i l e n e t w o r k sa n d a p p l i c a t i o n s2f 1 9 9 7 ) 5 5 6 7 e es t a n d a r d ，p a r t1 5 1 ：w i r e l e s sm e d i u ma c c e s sc o n t r o l ( m a c ) a n d p h y s i c a ll a y e r ( p h y ) s p e c i f i c a t i o n sf o rw i r e l e s sp e r s o n a la an e t w o r k s ( w p m , s ) , 2 0 0 2 正e es t a n d a r d ，p a r t1 6 ：a i ri n t e r f a c ef o rf i x e db m a d b a n dw i r e l e s sa c c e s ss y s t e m s ，2 0 0 l m a r kk l e r e r , i n t r o d u c t i o nt o 砸e e8 0 2 2 0 - t e c h n i c a la n dp r o c e d u r a lo r i e n t a t i o n 正e e 8 0 2 2 0 - p dp d - 0 4 p i y u s l lg u p t aa n dp r k u m a r , t h ec a p a c i t yo fw i r e l e s sn e t w o r k s ，i e e et r a n s a c t i o n s0 n h f f o r m a d o nt h e o r y , v 0 1 4 6 ，n o 2 ，m a r 2 0 0 0 v b h a r g h a v a n ，a d e m e r s ，s ，s h e n k e gl i x i az h a n g ，“m a c a w ：a m e d i aa c c e s sp r o t o c o lf o r w i r e l e s sl a n s ”，a c ms i g c o m m 1 9 9 4 ，p a g e s2 1 2 - 2 2 5 ，l o n d o n ，e n g l a n d ，u k ，a u g 3 1 一 s e p t 0 2 ，1 9 9 4 fc a l l ，m c o n t i ，a n de g r e g o r i ，“i e e e8 0 2 1 1p r o t o c o l ：d e s i g na n dp e r f o r m a n c ee v a l u a t i o n - 1 7 3 4 5 6 7 北京邮电大学博士论文第一章绪论 o f a n a d a p t i v eb a c k o f f m e c h a n i s m ”，i e e ej s a cv 0 1 1 8 ，n o 9 ，2 0 0 0 1 5 】d o u g l a ss j d ec o u t o ，d a n i e la g u a y o j o h nb i c k e t ，r o b e r tm o r r i s ，ah i 呈h t h j v t j | t t h p u ! p a t h m e t r i cf o rm u l t i h o pw i r e l e s sr o u t i n g ，a c mm o b i e o m 2 0 0 3 s e p t 1 4 1 9 ，2 0 0 3 、：i nl i qo c a l l f o m i a ，u s a 1 6 】d a q i n gg u ，j i n y u nz h a n g ，q o se n h a n c e m e n ti ni e e e8 0 2 1 1w i r e l e s s o c a a t ( _ i t e t v , - | 、r k s ， i e e ec o m m u n i c a t i o n m a g a z i n e ，j u n e ，2 0 0 3 1 7 】s x u ，ts a a d a w i ，d o e st h ei e e e8 0 2 1 1m a c p r o t o c o lw o r kw e l li nm u l t i h o pw i r e l e s sa d h o cn e t w o r k s ? ，i e e ec o m m u n i c a t i o n m a g a n i z e ，j u n e ，2 0 0 l 1 8 】r a mr a m a n a t h a na n dj a s o nr e d i ，ab d e fo v e r v i e wo fa dh o cn e r w 0 1 k s ：c h a l l e n g a n 【1 d i r e c t i o n s ，i e e ec o m m u n i c a t i o nm a g a z i n e ，m a y , 2 0 0 2 1 9 】s a t y a b r a t ac h a k r a b a r t ia n d a m i t a b h m i s h r a ，q o si s s u e si na dh o cw i ) e l e s sn e t w o r k si e e e e o n a r n u n i c a f i o nm a g a z i n e ，f e b 2 0 0 1 2 0 】w a s a np a t t a r a a t i k o ma n dp r a s h a n tk r i s h n a m u r t h y , d i s t r i b u t e dm e c h a n i s m si j o rq u a l i t yo f s e r v i c ei nw i r e l e s sl a n s ，i e e ew i r e l e s sc o m m u n i c a t i o n s ，j u n e2 0 0 3 2 1 tsr a p p a p o r t ，w i r e l e s sc o m m u n i c a t i o n s ：p r i n c i p l e sa n dp r a c t i c e ，p r o ：d i c e a 1 1 、j ，9 9 【2 2 】j o h ngp r o a k i s ，d i g i t a lc o m m u n i c a t i o n s f o u r t he d i t i o n ，p r e n t i c eh a l l ，2 0 0 l 2 3 】b pc r o w n ，i w i d j n a ，j gk i ma n dps a k a i ，i n v e s t i g a t i o no ft h ei e e e8 0 2l1 m 、d l l l l l l a c c e s sc o n t r o l ( m a c ) s u b l a y e rf u n c t i o n s ，i e e ei n f o c o m1 9 9 7 ，a p r 1 9 9 7 ，k o b e ，j a p a n - 1 8 - 北京邮电大学博士论文第二章重负载下吞吐量提高机制的研究 第二章重负载下吞吐量提高机制的研究 在无线局域网环境下，由于采用竞争接入的p p e r s i s t a n tc s m a 机 制，不可避免的会造成不同站点数据包之间的碰撞。当站点数较多竞 争剧烈时，这种碰撞会造成吞吐量下降。同时，由于i e e e8 0 211 窗 口指数退避机制，使得数据包一旦发生碰撞受影响的站点由于退避短 期内竞争窗口保持在较大值，难以竞争到信道。因此，站点之间碰撞 的加剧也会造成公平性指数降低。本文引入了一个与站点竞争碰撞相 关的参数负载因子，通过理论分析我们观察到，在站点接入概率 达到最优的时候负载因子数值解近似稳定在一个确定值刚近。换言之， 只要调节站点接入参数使得负载因子稳定在此确定值，站点接入概率 即可达到最优，使系统吞吐量最大。在此基础上，我们提出了种新 型的自适应媒体接入协议( n e ws e l f - a d a p td c fa l g o r i t h m ，n s a d ) 。 n s a d 不需要知道站点数量即可将系统性能调节接近最大。同时， n s a d 是全分布式的，不需要接入点a p ( a c c e s sp o i n t ) 的协助。仿真结 果表明算法可以有效提高吞吐量，同时公平性也得到改善。 2 1引言 关于随机接入信道吞吐量与负载之间关系的研究国外的经典文献可以追溯到 l k l e i n r o c k 等人1 9 7 5 年文【2 。在文章中 2 】，作者推导了c s m a 各变种协议吞吐 量与当前网络负载之间关系，对于无线分组网协议设计具有指导性的意义。之后 又有许多学者提出相关增强型技术，例如利用忙音信道克服隐藏终端和暴露终端 的问题 4 ，利用接受者发出竞争请求克服隐藏终端 5 1 。v at - n 种协t r 4 1 1 5 主要是 对于多跳下无线链路的性能增强。i e e e 8 0 2 1 1d c f 协议是基于p - p e r s i s t e n tc s m a 的一种协议，基本上是针对无线局域网的特定环境作了许多优化 6 】。由于无线局 域网中解决的问题主要集中在终端用户的单跳接入，不需要考虑通常无线分组自 北京邮电大学博论文 第二章重负载下吞吐量提商机制的州究 组织网的路由问题。因此如何设计一种高效健壮的媒体接入协议是无线局域网研 究中需要首先解决的问题。 为了提高i e e e8 0 2 1 1 d c f 在单跳局域网环境下吞吐量和公平性，近年来的文 献提出了一些改进机制 2 6 】【9 1 2 。目前的研究主要是从以下两个方向入手：一是 通过随机过程分析推导对协议建模，从而获取网络吞吐量与网络负载之间的关系 2 , 9 1 1 。主要实现手段是通过预测当前竞争信道的站点数量调整站点接入概率， 从而达到减小站点之间碰撞的目的。然而，由于数据传输的突发性，预测站点数 的方法在实用上存在难以准确预测、算法复杂的问题。另类文献主要是分析协 议在不同情况下出现的问题来优化协议的性能特性。例如存在不同速率的情况， 重负载、竞争站点数较多的情况、存在隐藏终端的情况、双向数据流情况等等 4 - 6 t 2 1 4 。主要实现手段是通过改变窗口调节机制和各种d c f 参数以及握手机 制的改进来控制站点的接入，以达到网络性能的优化。 本章所描述的算法结合了以上这两种研究思想。首先引入一个与链路负荷状态 相关的参数负载因子，通过分析推导和数值计算，发现调节站点接入概率使得链 路吞吐量达到最大，系统性能达到最优时，f 的最优值毛。与当前竞争站点数n 以 及碰撞时长近似无关。然而在传统d c f 下，负载因子f 随当前网络中竞争信道站 点个数的增加呈线性增长的趋势。以上特性为评判站点接入概率是否最优提供了 评判准则。我们利用这个特性通过调整所有站点的初始竞争窗口值改进d c f 的自 适应性，提出了一种新型自适应算法n s a d ( n e ws e l f - a d a p t d c fa l g o r i t h m ) 。大量 仿真结果表明，n s a d 协议的窗口调节机制能够自适应当前链路状况，在站点较 多时依然保持较高的吞吐量和较好的公平性。 在下一节中介绍了算法相关的技术背景，即无线局域网随机信道接入吞吐量最 大化准则。第2 3 节描述了n s a d 的具体实现流程，并利用数学建模分析推导了 l o p ，在竞争站点数较多时具有与当前竞争站点数量近似无关的特性a 第2 4 节和第 2 5 节描述了仿真环境和仿真模型的参数并对仿真结果作了分析和说明。最后在第 2 6 节中得出结论。 北京邮电大学博士论文第二章重负载下吞畦量提高机制的铆f 究 2 2 无线局域网随机信道接入吞吐量最大化准则 设当前所有主机通过d c f 方式接入自发组成单跳网络。以前的一些文献 9 - 1 0 1 1 2 2 曾经涉及到在这种环境下的吞吐量最大化的准则，并通过数学建模分析 和仿真等手段得出了一些结论。 1 0 的创新点在于用马尔科夫模型描述i e e e8 0 2 1 1 竞争窗口退避接入信道机制，并推导了以固定窗口接入信道时站点数和近似最优 窗口值的关系式。 9 2 2 采用了以下思路推导最优化吞吐量。如图2 1 所示，t - v 是成功传送一个数据包所经历的时长。t c o u 代表在tv 时间段内碰撞所花费的时 间，tf r e e 代表tv 时间段内由于退避丽产生的空闲时间段长度，tp a c k 代表成功 发送数据帧的开销，ts u c c 代表其他站点成功发送的开销。显然，tc o i l 和tf r e e 是c s m k c a 共享信道竞争所带来的开销。在这样的定义下，网络利用率不高表 现为以下两种情况： c a s e1 ：信道过于空闲。此时tf r e e 相对于tc o l l 过多。出现这种情况的原因 是当前竞争窗口相对于当前信道的竞争站点数过大，站点之间碰撞概率很小，会 造成不必要的退避时延。由于i e e e 8 0 2 1 1 d c f 方式初始窗口值较小( 物理层为d s s s 时最大为3 2 2 0 = 6 4 0 u s ) ，依初始窗口值计算得到的退避时长相对数据包时长 ( 2 m b p s 时最大为2 3 4 6 8 2 = 9 3 8 4 u s ) 来说很短，因此即使出现这种情况信道利用率 也通常能保持在较高值。 c a s e2 ：信道过于拥塞。此时tc o l l 相对于tf r e e 过多。出现这种情况的原因 是竞争窗口相对于当前信道的竞争站点数过小，在一个窗口时间内过多的主机竞 争信道，造成碰撞过于频繁。碰撞可能是发生在数据包与控制包之间，而在无线 局域网i e e e8 0 2 1 1 中判断一个碰撞通常要等到发出r t s 没有收到c t s 或者是发 出数据包没有收到a c k 再来判断。因此一次碰撞所浪费的带宽相当大。同时在这 种情况下，发生退避的主机竞争窗口在短期内往往保持在一个较高值，使主机成 功接入的概率偏小：成功发送的主机竞争窗口由于经常重置刷新，总保持一个相 对较低的值，因此该主机在短期内总能以较大概率接入信道，最终导致链路公平 性急剧下降。 为了避免以上情况发生，应该使t i d l e 和t f r e e 的比值趋向最优值。当我们调 节站点接入信道的概率( 在本文中为初始窗口大小) 使得这个比值趋向最优值时 网络能够获得最大吞吐量。我们下面的设计就是依据以上原则进行的。 2 j 。 北京邮电大学博士论文第二章重负载下吞吐量提高机制的川究 图2 ，1 ：i e e e 8 0 2 “无线局域网中一次数据包成功发送所经历的过程 2 3改进的d c f 协议：n s a d 2 3 1n s a d 协议总体描述 传统的d c f 协议在包的传送时并没有估计当前链路的拥塞状况。在网络竞争 站点数较多时，站点依然使用相同的初始竞争窗口接入信道，造成碰撞过多和频 繁退避，最终导致链路的吞吐量和公平性恶化明显f 8 。 为了让协议能够自适应当前链路负载状况，我们提出了新的自适应d c f 协议 n s a d ( n e ws e l f - a d a p td c fa l g o r i t h m ) ，引入了一个与链路碰撞密切相关的参数一 一负载因子，以反映当前链路负载状况。每个移动站点独立地根据当前网络碰撞时 长和空闲时长计算f 参数的数值，并将获得的z 与最优的负载值f o 。相比较，通过 比较结果来进一步调节站点初始接入窗口的大小。新算法的内容包括负载因子值 的分布式计算和新的窗口退避规则。 足义：链路负载因子( l o a df a c t o r ) 定义为：一次成功传送数据包所经历的碰撞 平均时长e ( tc o l d 与空闲平均时长e ( t 之比。_free) tc o l la v g 和q f r e e a v g 分别表示成功传送数据所经历的平均碰撞时长和空闲 时长。本次数据传送过程( 即图2 1 中v i r t u a l t r a n s m i s s i o n t i m e ) 中经历的碰撞时 长和空闲时长分别表示为tc o u 和t _ f r e e 。每次成功的数据传输会触发f 的计算。f 值的计算方法如下： l c o l l a v g = x * l c o l l a v g + ( 1 的t _ e o l l ； t _ f r e e a v g = k * t _ f r e ea v g + ( 1 一+ t _ f r e e ； z = l e o l l _ a v g t _ f r e v _ a v g ； ( 2 ，1 ) ( 2 2 ) ( 2 3 ) f 初始值设为优化值厶。( 厶。，的计算在2 3 2 中有详细说明) 。如图2 2 所示，每 当主机利用r t s c t s 竞争获得信道时。根据收集信道状况所得的t c o l l 和t f r e e 2 2 北京邮电大学博士论文 第二章重负载下吞吐量提高机制的酬究 分别计算其平均值t _ c o u _ a v g 和t _ f r e e a v g 以及当前网络负载，值，并与最优值，o 。， 比较，判断当前网络竞争碰撞状况并调节竞争窗口大小。我们设定门限值盯以判 断当前网络的，值是否在期望范围以内。并设定游动计数器c o u n t e r ，其初始值为0 。 如果( pk t + f f ) ，则触发c o u n t e r 增加1 ；如果( ， k f + 仃) c o u n t e r = c o u n t e r + l ； i i oi st h et h r e s h o l dt h a ts t i m u l a t ec o u n t e r c h a n g e i f ( k 一叻c o u n t e r = c o u n t e r l ； c o u n t e rm o v ef o r w a r do rb a c k w a r d a c c o r d i n g t ot h ev a l u eo f i f ( t m a x _ c o u n t e r ) c o n t c n t i o nw i n d o wi st 0 0s m a l l w i n ic = ( w m l t + 1 ) + 2 1 ； ) e l s ei f ( c o u n t e r w ) 、m 。i t = w m 蕊 u pb o u n d o f i n i t i a lw i n d o w i f ( w i n i t w 晌) i t w 曲； l o wb o u n do f i n i t i a lw i n d o w p i g g y b a c k ( v 、_ r i n i t ) ； p i g g y b a c kt h e n e wi n i t i a lw i n d o wt oo t h e ra c t i v es t a t i o r ) s 图2 4 ：初始竞争窗口调节算法伪代码 2 4 第二章重负载下奁吐量捉赢机制的研究 2 3 2 厶。的确定 首先设定当前单跳网络竞争站点数为n 。所有站点以w 的初始窗口大小接入 无线信道。站点在每个空闲时槽试图接入信道的概率为7 。显然，t 随w 的不同而 改变。最大化吞吐量时最优窗口值为w 。，对应的接入概率为砩。我们首先来推 导l o p ，应该满足的条件。t 。”t 。分别代表碰撞的平均时长和碰撞平均时槽数，t ；。t 代表一个时槽的时长，t d 。t d 分别为数据帧的时长和时槽数，t n 。；y 、t e 4 分别为 成功竞争到信道后由于传送数据占用的总时长和时槽数。p 。1 1 为碰撞发生的概率， p f r c 。是时槽空闲概率。p ；。是某竞争站点在一个空闲时槽成功竞争到信道的概率， 亦即只有一个站点在此空闲时槽竞争信道的概率。 依概率显然有： = 1 一n r 0 一r ) “1 一( 1 一r ) ” = ( 1 一r ) “ ( 2 ，4 ) 匕。= 1 一圪旷。 负载因子依概翠司计算为： ，：嬲= t c o l l 虿 p c o l l 坐果1 丛- e 亿s ， e ( f 一) t 。，。 ( 一r ) “ 吞吐量s 可以表示如下： s ：g l 型出一 f 2 6 ) 。瓦。+ 正。，+ 吃。毛“ 、 由于gb i a n c h i 在【l o 】中得到站点接入概率满足下述条件时吞吐量s 达到最大： 一，；正筹筹半z 而1 b ， 扣。 瓦丽j 广2 习历 联合( 2 5 ) ( 2 7 ) 可得在吞吐量达到最大，站点接入概率为最优值丁。p t 时，负载【园子此 时与站点接入概率以及碰撞时长之间的关系式如下： ，：坐坐型掣c ( 2 s )一”一 ( 1 一r o t , 。) ” 1 。 。 由( 2 7 ) ( 2 8 ) 通过数值计算我们可以得到以下站点数与负载因子最优值f 叩c 之间关系 图2 - 5 以及碰撞时槽数t 。与k ，之间关系图2 - 6 。由图中不难观察到：当站点接入 北甫招啕大学博十诒寸 第二章重负载下吞吐量提高机制的研究 概率调至最优时，负载因子k 。此时数值上始终保持在1 以内，且随站点数增长以 及碰撞时长增大趋向一个固定值，这是一个很好的特性，在前面一节的算法中我 们利用这个特性来解决重负载下站点碰撞过大的问题。然而在图2 7 中是未采用调 至最优站点接入的d c f 中利用 1 0 】建模计算的负载因子值。我们可以看到，原先 的d c f 中随竞争信道站点数增加负载因子急剧增大。 负载因子上述特性的重要性在于：为当前共享竞争信道的所有站点提供了一个 衡量当前网络是否过载的尺度。与以往一些算法不同的是，我们的算法不需要预 测当前网络中的具体竞争站点个数，直接感知当前网络中忙的时长和空闲的时长， 从而避免了预测站点所带来的的不准确性。当使用r t s c t s 选项时，依据i e e e 8 0 2 1 l 标准碰撞时长可以计算为r t s + e i f s 的时长。当采用d s s s2 m b p s 的物理链 路传输时，t c * = 2 9 0 ( s l o t s ) ，根据图2 - 6 ，k ；o ，8 6 。当1 5 0 0 字节的t c p 数据帧发 生碰撞时，碰撞时长可计算为：d a r a + s m s + a c k + d s ，于是t c * = 3 3 1 8f s l o t s ) 。 根据图2 - 6 ，l o p t 硼9 5 。尽管上述讨论中是以使用r t s c t s 选项为例讨论的，但是 我们的机制也适用于不使用r t s c t s 选项的环境。由于在当前单跳网络中，只有 成功传送的数据包可以将新的优化窗口值捎带给所有的相邻活动站点，所以不论 数据包是否成功传送，我们都可以将优化窗口值写入数据包。如果数据包成功传 送，发送方会收到a c k 并知道新的优化窗口值被带给所有其他相邻站点，此时发 送方可重置计数器准备下一轮网络状态测量：如果数据包发送失败，则发送方在 等待a c k 超时后得知发送失败，将碰撞加入时长计数并继续本轮时长统计。 、to=3318 to=290 、 图2 - 5 ：k 和当前竞争站点数的关系曲线( t 。= 2 9 0 和t e * = 3 3 1 8 ) 2 6 北京邮电大学博士论文第二章重负载下吞吐量提高机制的 i ；| 咒 1 。9 5 。9 如s 毛 扣s 一 f i 图2 - 6 ：厶。和平均碰撞时槽数关系曲线( 竞争站点数为1 4 0 ) 图2 7 ：d c f 下负载因子，和当前竞争站点数的关系曲线 由于k ，是一个与活动站点数以及碰撞时长近似无关的值，我们利用这一点来 调节初始竞争窗i z iw 的大小，使得f 接近最优值k 。调节的结果使得w 收敛到 最优值w 。同时站点接入概率达到使得网络吞吐量最大的接入概率丁0 p 【口 2 3 3 最优初始竞争窗口值w 。与竞争站点数n 的关系 在这一部分中，我们主要研究了i e e e8 0 2 11 协议中最优初始竞争窗口值w 。p f 与当前无线局域网竞争站点数n 之间的关系。主要目的是为评判2 3 1 调整初始竞 2 7 北京邮电大学博士论文第二章重负载下+ 提高机制的研宄 争窗口算法的准确性提供参照，同时对于合理利用网络资源哕i 不同局域网之 间设计合理的负载均衡算法提供了便利。 初始竞争窗口值为w i m b i窗口上界和下届分别为w 。和w 。令 n = l 0 9 2 ( w 。+ 1 ) ( w m + 1 ) ，实际上n 是在发生碰撞退避时竞争窗口两倍增大的次 数。n 是系统预设的最大退避次数( i e e e8 0 2 1 1 中短帧重传次数为7 ) 。p 是站 点竞争信道遭遇碰撞的条件概率。关于站点调节至稳态时最优的初始竞争窗口 w 。和n ，我们有以下结论； 定理211 当前活动站点数n 和优化初始竞争窗口值w l i 。之间的关系式可以 用下列方程表示。详细证明见附录2 2 。 n n - i 一p + ( + 1 ) ( 2 p ) + ( + 1 ) p n - , 2 r ：= 盥l 型 j ! 。 ( 2 9 ) y p 站点接入信道碰撞概率就等于存在其他站点在同一时槽试图接入信道的概率。显 然依概率有： p = 卜( 1 一r ) “1 ( 2 1 0 ) 亿聊械佣谚猷r ，硝叫 1 一1 1 。志j 趟眦锨吼侵 f1 、o 用近似：l i i n i l + k i = g ，于是得到： 竺工 p ；l e 拉7 2 ( 2 1 1 ) n k 2 7 q n q t ( 2 9 ) ( 2 1 1 ) ，我们可以获得最优初始窗口值w i 。“与当前无线网络竞 点个数n 的关系。令初始窗i z l 值为w t = 3 1 ，6 3 ，1 2 7 ，2 5 5 ，5 1 1 ，窗口倍增次数i t ， 2 ，5 ，w r 。