（计算机应用技术专业论文）基于ieee80211mac层dcf访问控制回避算法的分析与改进.pdf

硝j 1 1 7 k 学硕上学位论文 基于i e e e8 0 2 。1 1m a c 层d c f 访问控制 回避算法的分析与改进 计算机应用技术 研究生：倪剑虹指导老师：吕光宏 1 9 9 7 年6 月，搬e e 推出了第一代无线鼹域网檬准i e e e 8 0 2 1 l 。垦麓基 于8 0 2 1 1m a c 层工作主要集中在它的器吐量秘延迟性能上，以及其中定义蛉 两霍中信道访问控制方式的标准：点协调功能p c f 搬分布式蜘调功能d c f 。 本文针对无线局域网的i e e e8 0 2 1 1d c f 避兔冲突的传统鲍二进制指数 回避算法b e b 以及对应的较极端的指数增长线性下降的嗵避算法m i l d 做 出分析研究，发现b e b 的竞争窗口重设机制在网络负载较大的情况下，过小 的竞争窗口会产生更多的冲突，使系统吞吐量严重下降；丽m i l d 的线性下 降策略在网络负载较小时，竞争窗口值变化太慢，降低信邋的刹用率，造成延 迟性能的恶化。 结合目前一些研究者对回避算法进行改进提出的两种改进型的回避算法： 指数增长指数下降回避算法e i e d 和线性多重增长线性下降回避算法 l m i l d ，得出一种更优性能的线性多重增长线性多重下降回避算法 l m i l m d 。根据发生冲突节点的具体情况，对竞争窗豳大小进行合理的调整。 在n s 2 仿真工具的帮助下，模拟验证了该算法的性能，改善了无线网络的延 迟与吞吐量，达到更好的性能薅求。 随着越来越多酌应用在无线局域网上的部瓣，对无线髑域网的性能要求 必将越来越高，本文提出的l m i l m d 回避算法无论吞吐量还是延迟性能都比 现有算法有一定改善，阂此具有较商的应用价德。 珏 匝| 川大学硕士学位论文 关键谰： 无线局域嗣介质访问控制协议分布协调功能点协蠲功能竞争蜜 口 回避繁法计葵枧模拟 i l l 因埘太学硕士学位论文 a n a l y s i sa n di m p r o v e m e n to f i e e e8 0 2 。1 1d i s t r i b u t e d c o o r d i n a t i o nf u n c t i o nw i t hb a c k o f f a l g o r i t t m a m a j o r ：c o m p u t e ra p p l i c a t i o n p o s t g r a d u a t e ：j i a n h o n gn ia d v i s o r ：g u a n g h o n gl v i nj u n eo f1 9 9 7 ，i e e ei n t r o d u c e dt h ew i r e l e s sl a ns t a n d a r do ft h ef i r s t g e n e r a t i o n 一一i e e e8 0 2 1 1 a tp r e s e n tt h ew o r kb a s e do n8 0 2 1 1m a cl a y e r c o n c e n t r a t e sm a i n l yo ni t st h r o u g h p u ta n dd e l a y , a n dt w os t a n d a r d so ft h e f u n d a m e n t a lm e c h a n i s mt oa c c e s st h em e d i u m p o i n tc o o r d i n a t i o nf u n c t i o n ( p c f ) a n dd i s t r i b u t e dc o o r d h m t i o nf u n c t i o n ( d c f ) i nt h ep a p e r , t h et w ot r a d i t i o n a lb a c k o f fa l g o r i t h m so fi e e e8 0 2 1ld c f w h i c hu s e dt oa v o i dc o l l i s i o n ，b i n a r ye x p o n e n t i a lb a c k o f f 国e b ) a n dm o r e e x t r e m em u l t i p l i c a t i v ei n c r e a s ea n dl i n e a rd e c r e a s e ( m i l d ) ，a r ea n a l y z e d w e c a l lf i n dt h em o r eb i g g e ri nn e t w o r kl o a dd u et ot h er e s u l n em e c h a n i s mo fb e b ， t h em o r ec o l l i s i o n sw i l lb ee m e r g e ，m a k et h es y s t e m a t i ct h r o u g h p u td r o ps e r i o u s l y b u tt h em o r es m a l l e ri nn e t w o r kl o a d ，b e c a u s eo ft h el i n e a rd e c r e a s em e c h a n i s m o fm i i d ，t h em o r es l o w e rc h a n g e si nc o n t e n t i o nw i n d o ws i z ew i l lr e d u c et h e u t i l i z a t i o nr a t i oo f t h ec h a n n e l ，c a u s et h ed e t e r i o r a t i o no f d e l a yp e r f o r m a n c e + c o m b i n e dt h eb a c k o f fa l g o r i t h m so ft w ok i n d so fi m p r o v e m e n tt y p e sw h i c h s o m er e s e a r c h e r sh a v ep u tf o r w a r da tp r e s e n t ，e x p o n e n t i a li n c r e a s ee x p o n e n t i a l d e c r e a s e ( e i e d ) a n dl i n e a r m u l t i p l i c a t i v e i n c r e a s ea n dl i n e a rd e c r e a s e ( l m i l d ) ，8 鞋o u t p e r f o r m e db a c k o f fa l g o r i t h m l i n e a r m u l f i p l i c a t i v ei n c r e a s e a n dl i n e a r m u l t i p l i c a t i v ed e c r e a s e ( l m i l m d ) i sp r o p o s e d ，a c c o r d i n gt ot h e c o n c r e t ec o n d i t i o n so ft h ec o l l i s i o nn o d e ，i tc a r r i e so nr a t i o n a la d j u s t m e n tt ot h e s i z eo fc o n t e n t i o nw i n d o w w i 如t h eh e l po fs i m u l a t o rt o o l n s 2 s i m u l a t i o n h a sv e r i f yt h ep e r f o r m a n c eo ft h i sa l g o r i t h m ，h a si m p r o v e dd e l a ya n dt h r o u g h p u t 四川大攀硕士学位论文 o f t h ew i r e l e s sl a n ，r e a c hb e t t e rp e r f o r m a n c et or e q u i r e w i t hm o r ea n dm o r ea p p l i c a t i o n so nt h ew i r e l e s sl a n ，o u rr e q u i r e m e n tt o t h ep e r f o r m a n c eo ft h ew i r e l e s sl a nw i l lb eh i g h e ra n d h i g h e r b a c k o f fa l g o r i t h m l m i l m dt h a tt i f f sp a p e rp u t sf o r w a r dh a sc e r t a i ni m p r o v e m e n tm o r et h a nt h e e x i s t i n ga l g o r i t h m s ，1 1 0m a t t e ri t st h r o u g h p u to ri t sd e l a y , s oh a ss o m eh i g h e ru s i n g v a l u e k e y w o r d s ： 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 d i s t r i b u t e dc o o r d i n a t i o n f u n c t i o np o i n tc o o r d i n a t i o nf u n c t i o n c o n t e n t i o nw i n d o wb a c k o f f a l g o r i t h mc o m p u t e rs i m u l a t i o n v 四j i i 大学硕士学位论文 1绪论 1 1 课题背景介绍 选尼攀来，计算凝瓣络技术褥剿飞速发攫，蠢线爨蠛掰( w l a n ) 技术 终为诗纂橇鼹终技术茨一令分支瞧澎濒圭| 墼浮窭拳甏，褥弱了众多鳖痰入士秘 关注。_ 无线是域阏作冀英本赛鳃网戆特殊方式决定了它在缀多实现技术上与 有线网的不同。 基于有线局域潮技零的成熟和应用的广泛，我们希望无线髑域髓也熊像商 线的那样灵活的运髑捌实际当中。1 9 9 7 年6 月，j e e e 推出了第一代光线局域网 标准i e e e8 0 2 1 1 。该标准定义了物理鬈( p h y ) 和介质访问控锘0 子层( m a c ) 浆秘议勰菠。任凭l a n 敷溺、阏终操作系统或狯议在遵守i e e e8 0 2 1 1 标维浆露 线l a n 上遴行辩，就豫它翻遮行在鞋太网上祥容器。稼i e e e8 0 2 1 8 耪毽层 采瘸熬是委交叛分多鼹系统( o r t h o g o n a lf r e q u e n c yd i v i s i o nm u l t i p l e x i n g ， o f d m ) ，宅可以有效的对抗频搴选择性液减及符号波形干扰( i n t e rs y m b o l i n t e r f e r e n c e ，i s i ) ，使褥物理层传输速率可提升至6 5 4 m b i t s s 。本论文研究对 象就是介质访问控制予滕。 目前蘩于8 0 2 1 1m a c 鼷工作主要集中在如何改善网络的界吐堂和邂迟性 襞上，戳及其孛定义的两种无线嗣倍遂访润控镱l 方式酌标准；点傍谲穗鼹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 ) 震分毒式蛰谰功栽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 f u n c t i o n ) 麴分聿厅。茏葵是分布式耱潮d c f ，安魂魄较篱单，嚣l 琏：褥至瓣兹大 多数厂商的支持。但研究表明，就应用于d c f 中避免冲突的传统的回避算法 在实际虚月中，链鼹吞吐量、延迟性甥明驻恶化。目前一些研究者对避免冲突 的回避冀法进行了一些改进，提出两种改进型的隧避算法：指数增长指数下降 回避算法e i e d ( e x p o n e m i a li n c r e a s ee x p o n e n t i a ld e c r e a s e ) 和线性多重增长线 懂下降阐避算法l m i l d ( l i n e a r m u i t i p l i c a t i v ei n c r e a s ea n dl i n e a rd e c r e a s e ) ， 对d c f 攀期戆二避销 鬻鼗醚避算法b e b ( b i n a r ye x p o n e n t i a lb a c k o f f ) 醴及 对照静较投漆懿指数增长线褴下降懿回避箨法m i l d ( m u l t i p l i c a t i v ei n c r e a s e a n dl i n e a rd e c r e a s e ) 做出改蛰。 本文邋过对这鼹秘改进算法遴行归皱分辑及院较，缛出一静更饯性鼹的线 性多重增长线性多蘑下降回避算法l m i l m d ( l i n e a r m u l t i p l i c a t i v ei n c r e a s e 翻鞭大学颟士学经论文 a n dl i n e a r f m u l t i p l i c a t i v ed e c r e a s e ) 。在实际验涯中，对于改羲恶线网络的延迟 与器吐霪，2 够达到燹好匏牲韪要求。 1 2 无线瑶谶网的桶关技术 1 2 1 协议标准 作为企球公认的硒域喇权威，i e e e8 0 2 工作组建立的标准在过去= 十年内 在岗域丽领域独领风骚。这些协议包括了8 0 2 3e 攮e m e t 协议、8 0 2 ，5t o k e nr i r i g 协议等等。在1 9 9 7 年，经过了7 年瓣二 佟以螽，i e e e 发鑫了8 0 2 1 1 捺议，这氇 是在无线届域潮领城内的第一个萄际上被认可的协议。在1 9 9 9 年9 筒，稚稍又提 盘了8 0 2 i l b “ i g lr a t e ”协议，翔来对8 0 2 1 1 协议避行补究，8 0 2 1 l b 在8 0 2 1 1 的1 m b p s 靼2 m 幻s 速率下又增加了s 。5 m b p s 嚣i 1 m b p s 礴个躲麴嘲终吞蛙速 率。列熙8 0 2 1 l b ，移动照户l 够获褥凰e t h e m e t 一样驰性能、嬲络吞蛙率、霹 用性。这个纂予标准鹣技术使彳罨管理员哥戳根据环境选择舍遴静商域黼按术来 构造自己瀚闷络，满麓德们的商豫用户帮其德罐户的需求。 8 0 2 1 i 协议主要工 乍农i s o 协议的最低薅朦上，藏在物理层上进行了一 挫改动，加入了裹速数字传竣的特性积逡接的稳定性。下熙l 。l 表示了i e e e 8 0 2 + 1 l 与o s l 参考模型对应关系。 习一 l 。，。一 妻鋈鋈鋈鋈霾覆蘸鋈鋈黍鬻鍪鋈j 阕1 + 18 0 2 1 t 与o s l 参考横型的对威关系 d a t a1 i n kl a y e r l l cs u b l a y e r m a c s u b i a y e r p h y s i c a l l a y e r 四川大学硕士学位论文 1 2 2 调制解调 在i e e e8 0 2 。1 1 最裙定义懿三个物溪藩镪耩了两个扩频鼓术秘一个缝夕 馋播援范。无线瞎壤的簇遵意义在2 4 0 h z 弱i s m 波段爨，这个藏段，奁器 个国际无线管理机构中，例如蓑圜的u s a ，欧洲的e t s i 和醴本的m k k 都是 非注册使用频段。这样，使用8 0 2 1 1 的餐户端设备就不霞耍任何无线诲可。 扩频技术保证了8 0 2 1 l 的设备在这个频段上韵可用性和可靠的性能，这项技 术还可以保证同其能使用同一频段的设备不互相影响。8 0 2 1 1 无线标准定义的 话输速率鼹1 m b p s 辩2 m b p s ，霹激使确魏颓扩最颟谱f h s s ( f r e q u e n c y h o p p i n gs p r e a ds p e c t r u m ) 帮塞接序戮扩袋频谱d s s s ( d i r e c ts e q u e n c es p r e a d s p e c t r u m ) 技术。 直接序列扩频系统怒将要发送的傣息用伪随机码( p n 码) 扩展到一个缀宽 鲍频带上去。在接收端，用与发送端扩展用的穗瞬伪随枧鹞对接收到的扩频傧 号避行相关处理，戳爱出发邀的信息。对干扰信号而言，由于与伪随机码不狸 关，在接 | 雯端被扩展，使落入信譬通频带内的干扰信号功率大大降低，从而提 离了裙关器瀚输密僚汗秘：，这到了抗干抗豹蓓的。 搿l 频鼓术与蓬廖扩羰技术完全不溺，楚另乡 季孛扩频鼓零。雾l 频静载藏受 一个镄涎热码斡控制，农其工终带竟蒎圈凑，冀频率按麓橇缎簿不薮滚交频率。 接收端的频率也按隧机翘律变化，并保持与发射端灼变化规律致。跳频孵瘫 低蠢接反映跳频系统的性能，斟频越瘫，抗于扰的性能越好。嚣要撂出豹是， f h s s 和d s s s 技术在运行枫制上怒完全不同的，所以采用这两种技术的设备 没有互搡作性。 1 2 + 3 介质访润控制 i e e e8 0 2 1 1 无线褥域瓣逶铸耱谈奔矮访瓣浚涮基提供二耱不潮萌憨翁浚 曰存取方法：分毒式掺谖功麓d c f ( d i s t r i b u t e dc o o r d h n a t i o nf u n c t m n ) 及悫 惦调功能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 ) 。 d c f 是i e e e8 0 2 ，1 l 的基本介质访问方法，在这种方法中，每个纂站利 用载波侦听多路访闻及避兔碰撞c s m a c a ( c a r r i e r - s e n s em u l t i p l e a c c e s s c o l l i s i o na v o i d a n c e ) 协议及r t s c t s ( r e q u e s tt os e n d c l e a rt os e n d ) 四川大学硕士学位论文 协议，来传送数据。c s m a c a 及r t s c t s 都利用倒数计时机制来错开綦站 饺_ 鬻信遴静时润，避免碰撞( c o l l i s i o n ) 稽形懿发生。嚣谓碰攘是指两个以上静 工作站在同一个信道上同时传送数据包，因而造成数据包互相干扰。p c f 魑由 中央控翻台透过轮询( p o l l i n g ) 的方式来掩箭哪个工作站拥有信邋使用权， 工馋站不器要竞母( c o n t e n t i o nf l e e ) 即可传送数搌，因此也不会发生信号碰撞 的情形。但要保证随时都有接入点a p ( a c c e s sp o i n t ) 来做信道控制的工作， 实霹上毙较困难，瑟且强a p 数障时p c f 梗割会无法遮痒，爨鼓虽然p c f 有 较健的效率，i e e e8 0 2 1 1 仍然是以d c f 为基本的访问方式。 8 0 2 。1 1m a c 子瑟还提喾芝了勇两个强壮韵功髓，c r c 校骏帮毽分片。在 8 0 2 1 1 协议中，每一个在无线网络中传输的数据报都被附加上了校验位以保证 它在传送的时候能检测捌错误，这和e t h e m e t 中通过上朦t c p i p 协议来辩数 据进行校骏有蹶不同。包分片的功s & 允许大的数掇报在传送的时候被分成较小 的部分分批传送。这在网络十分拥挤或者存在干扰的情况下( 大数据报在这种 巧壤下黉送 鬻褰曩遭到酸嚣) 是一令 常套弱戆特整。这磺技本大大减少了 许多情况下数据报被重传的概率，从而提商了无线网络的整体性能。m a c 子 层受责将毅到骑棱分片的大数据报避雩亍重新组装，对于上层协议这个分片的过 程熄完全透明的。 1 ，3 本论文的章带安排 第一章为绪论，主要对课题背景作了一个简单介绍，然艨对无线局域阑 的桐关技术做了一定的描述：i e e e8 0 2 1 1 的标准、工作方式、物理层规定以 及在本论文中重要礤褒兹对象一数字链鼹层。 第二罐就专门对i e e e8 0 2 1 1 的m a c 予层做了详细分析。首先魑两种俗 逶控毒l 方式d c f 、p c f 豹理论毒蓥透，然螽对链稻备垂静工捧税舔l 散了阐述。 最聪还介绍了基于d c f 应用的几种回避算法。 第三章也怒本文的核心内容，在这里提掰了改进的圈避算法 l m i l m d 。本章先对回避算法的愿璎及特性进行阙述并进行理论推导，然展 对戴它相关算法做了实例分丰斤和此鞍，并对新的敬进算法进行理论分析。 四川大学酾士学位论文 第嚣拳是对第三犟鹣内容进行模叛验涯。蓠先分缨了n s 2 网络模拟系统， 然后对仿真过程进行描述，最后对仿真结果进行性能分析，验_ i i j e 我们改避的 l 瑚l m d 算法。 第五章是对全文的总结并对将来工作做出磁颦。 2l e e e8 0 2 。1 的公质访阏接制 无线局域网不能简单地使用有线局域网的协议。在图2 1 中反映出了无线 局域网的问越所在。图中有豳个秃线工作站，并骰定秃线电信誉传辫的范圈露 髓达蓟籀邻静蜷。 翳2 ， 无线赫域潮熟特臻燃：( 8 站a 发送信号 ( 秘站8 发送继母 塑2 ，l f 越中袭示燃点a n 站点b 发送数据。囊予站点c 收不到a 发送的馈号， 就误以为网络上无人发送数据，趿丽向b 发送数据。缭果b 间时收到a 和c 发来 的数据，发生了冲突。所以在无线局域网中，在发送数据前朱检测到媒体上有 信号并不能保诞发送就能成功。这种未能检测出媒体上已存在信号的f 司磁就跫 隐藏节点问题。为了解决这个闻趱，i e e e8 0 2 ，1 1 在m a c 罄上弓l 入了一个麓 的r t s c t s ( r e q u e s t t os e n d c l e a r t os e n d ) 选颈，警这个逡颂打开螽，一个 发送王作熬传送一个r t s 信号，隧基等待谤翘接入点回邀c t s 信号，壶予 联毫豹阙终中瓣工 擘站戆够“皈”到游翊接入点发出粒信号，辑以c t s 熊够 迂德绷薅正传送数掇，这样发送燃就可以发送数攥和接受a c k 信号丽不会造 成数据的冲突，这就间接鳃决了隐藏节点的问题。 而图2 1 ( b ) 中就是无线网中的暴瓣站问题。站b 向a 发送数据，丽c 又想和d 四川大学硕士学位论文 通倍，但c 检测到媒体上有信号，于是就不向d 发送数獭，而在实际上b 向a 发 达数据荠不影稳c 窝d 发送数捺。在无线局域丽中，在不发生干撬的 鸯况下，可 允许同时多个工作站进行通信，这是与总线型局城网有很大的差别。 这两个无线桶域网的问磁再加上无线信道传输条件的特殊，造成信号强度 的动态范围非常大，这就使发送端无法使用冲突梭测的方法来礁定怒否发生了 冲突。因此，无线局域网不能使用载波侦听多路访问并检测冲突c s m a c d ( c a r r i e rs e n s em u l t i p l ea c c e s sw i t hc o l l i s i o nd e t e c t i o n ) ，嚣只2 镬爱c s m a 。 为搬高c s m a 的效率，8 0 2 1 1 协议使用了c s m m c a 技术。 2 分布式协调功憩d c f 分毒式协调功能是每个基站苇暇lc s m a j c a 及矾s 怒t s 戆鼓术，避免并 解决不同工作站间可能发生的冲突。d c f 是以c s m a c a 协议为基础，采用 二避嘉l 指数退遴舞法瓣一秘隧辊竞争接天方式。它有两耪转输方式，一耪趋两 路握手的熬本方式，该方式要求接收方在正确收到数据觎后向发送方回送一个 显式a c k ( a c k n o w l e d g e m e n t ) ，阻告知发送方该数据镪已被难确接收。另一 种越可选的四路握手方妓，称为r t s c t s ( r e q u e s tt os e n d c l e a r 协s e n d ) 机 制。本节中我们将针对这两种技术作详细的介绍。 6 四川大学硕士学位论文 2 。 c s m a c a 掺谈 圉2 ，2c s m a c a 示意髓 c s m a c a 的蓥本概念及流程摇图2 2 掰示，基站利焉载波篌祈按术来判断 菜一信遂是否有数据鬣传送。螽莱信号静强度瓷阀值之下，就表示该信邀未被 占嗣( 倍道空闲) ；反之，刘表示该信道器前有信号传送( 信道忙碌) ，蘩站登 颓延缓 d e f e r ) 颧传送时间。 基站发观信道空闲时，还不能马上送出帧，而是婺根据帻的优先权等级， 等待一酸帧闻隔时间i f s ( i n t e r - f r a m es p a c e ) 来确认倍道是否闲凝。如采在这 段等待时间内，信道仍然是空闲，就确认信遥闲置并将帧送出去。接收端接剐 封装包后，由c r c 3 2 检错，如果封装包正确无误的话，则要阐传a c k ( a c k n o w l e d g e m e n t ) 的确认信息告知发送端；当发生封装包错误，则将封装 靓丢弃，不回传任何信息给发送端。相同的接收端阐传a c k 信号前一样要等 待一段确认信道空闲的帧间隔时间。 i e e e8 0 2 1 1 的帧间隔分为三种，每种间隔都相差1s l o t 即5 0 扯s ( 本文如 没特别指明，物理层均采用f h s s 方式) ，这三种i f s 分剐为： s i f s ( s h o r t i f s ) ：短帧间间隔。典挺值为2 8 i _ t s 。用来做立即的响应动作。 下列帧传送的等候时间都疑s i f s 等级：允许传送帧( c t s ) 、回复帧( a c k ) 等。 p i f s ( p c fi f s ) ；p c f 帧间间隔。典型值为2 8 + 5 0 = 7 8 “s 。在进行p c f 无 竞争式传输功能时，基站传送帧前认定信道闲置所须等待的时间。 了 秘川走学硕士学位论文 d i f s ( d c fi t s ) ：d c f 帧间间隔。典型值为7 8 + 5 0 = 1 2 8 s 。在进行d c f 竞 争式传输功能时，麓站传送帧前认定信道闲置辑须等待的时闻。 箕中s i f s p i f s 但如粱该节点只是谈踞到别的节点发生冲突鼓者传送数撼成功， 那么i 的馐就不後变，帮为i i = 0 。德时候变量i ( 裙始德为o ) 发现i 并没 改交，弱i l + l l ，该节点的竞争密裔c w 2 = c w