二进制指数退避算法

第 26卷第 10期 2004年 10月 电子与信息学报 Journal of Electronics&Information Technology V01 26N0．10 Oct．2004 IEEE 802．11网络中增强的退避算法 徐志江 李式巨 官 军 (浙江大学信息与通信工程研究所杭州310027) 摘 要： IEEE 802．11 协议 离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载 的MAC层通过二进制指数退避货：法实现对媒体的争用，该文提出一种增 强的退避算法，对网络中的动态站点数进行估计，自适应改变退避 法的竞争窗口，以提高网络的性能． 关键词： IEEE 802．11，竞争窗口(CW)，吞吐量，动态站点 中图分类号： TN919．2 文献标识码： A 文章编号： 1009·5896(2004)10·1527·07 Enhanced Backoff Algorithm of IEEE 802．11 Network Xu Zhi—jiang Li Shi-ju Guan Jun (Dept of』咖 ．and Electron．En9．，Zh~iang University，Hangzhou 310027，China) Abstract The MAC layer of the IEEE 802．11 standard adopts an exponential backoff scheme to access media．This paper provides an enhanced backoff scheme，which changes Contending Windows(CW)adaptively by estimating the number of active stations in network to improve the efficiency of network． Key words IEEE 802．11，Contending Windows(CW)，Throughput，Active stations 1引言 在无线局域网中，媒体访问控制(MAC)协议是主体部分，因为它决定了在有限的无线信道 带宽下共享信道的方式和效率。本文讨论问题主要集中在IEEE 802．11标准的效率上。 IEEE 802．11标准【 j中，规定了两种媒体访问方式：DCF(Distributed Coordination Func． tion)方式和PCF(Point Coordination Function)方式。DCF是一种异步数据传输方式，适 用于时延要求低的数据服务，采用的．是载波监听多路访问／冲突防止(CSMA／CA)机制．当数 据报发送产生冲突时，则由二进制指数退避算法来管理数据报的重发。DCF方式中又描述了两 种数据报发送时所采用的方法。一种为基本访问方法，另一种为可选的RTS／CTS(Request To Send／Clear To Send)方法。RTS／CTS方法可解决隐藏终端和数据报过大时信道效率下降等的 问题。PCF方式为可选择的服务方式，提供无竞争的帧传送。它采用轮询的方式来降低冲突， 适用于时延要求高的数据服务，如：语音，图像等。 在IEEE 802．11标准中CSMA／CA机制由二进制指数退避算法来实现。采用冲突防止而非 冲突检测(CSMA／CD)是因为无线设备在发送时不能同时监听，通常发送和接受数据报都由一 根天线来完成 。退避算法是在(0， 一1)中，随机选择一个数作为退避时间计数，计数为0 时则发送数据报；如果数据报发生冲突，则 乘以2后重新开始退避。其中 为竞争窗口，其 值与数据报发送失败重发的次数有关，取值范围为(CW。 i ，CW )。文献[3】的分析给出， 系统的吞吐量是与站点的数量和 的选取有关的，本文的主要目的就是提出一种方法，通过对 当前动态站点数量的估计来选取 ，来提高系统的性能和吞吐量。 0 2003—06—21收到， 2003—11-25改回 国家863计划 (2001AA413610)资助课题 维普资讯 http://www.cqvip.com Administrator 高亮 1528 电 子 与 信 息 学 报 第26卷 本文的内容如下：第 2节，简要描述二进制指数退避算法；第 3节，给出最佳竞争窗口 CW。。 与当前动态站点的关系；第 4节提出一种估计当前动态站点数量的算法，第 5节是仿 真结果和结论。 2二进制指数退避算法 本文以下部分都是对DCF中基本访问方法的讨论。DCF的基本访问方法是：源站发出数 据，目的站接收到数据后，回复 ACK确认帧。如果源站没有正确接收ACK帧， 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明数据发生 冲突，必须重发。其他站点在此期间无权访问媒体，直到数据发送完毕，各个站点重新进入争 用期．每个数据报传送时，在(0，u一1)中随机选择一个数作为退避时间计数。在第一次传送尝 试时，u=CW i ，如果数据报发送产生冲突，u则乘以2，重新退避，直到一个最大值 CW =2mCW i (1) 式(1)中，m表示退避计数所能达到的最大阶数。退避时间计数C可以表示为【4】_ C=int(Rnd(．) (2i-1CW i 一1)) (2) 式(2)中，i表示数据报第i次尝试发送，Rnd(·)表示一个(0，1)之间的平均分布的伪随机数 函数，int(．)表示对括号内的数取整。退避时间计数器是以 (标准l J所定义slot time)为单 位。当信道检测到空闲时，退避时间计数器递减；当信道检测到忙时，则停止计数，直到信道重 新空闲的时间超过标准【 】所定义时间段DIFS(Distrmuted InterFrame Space)时，重新递减。 当 递减到 0时，站点发送数据报。 图1描述了二进制指数退避算法。图中SIFS(Short InterFrame Space)也为标准【l】所定义 时间段，比DIFS时间间隔短。A，B两个站点共享信道。A站检测到信道空闲时间大于DIFS 时，发送数据报，B站此时停止退避时间计数，直NY-检测到信道空闲时间大于DIFS时，重 新计数．当B站的退避时间计数器为0时，则B站发送数据报。 DlFS SIFS DIFS 站点A l数据报I ．． ~'／／／／,I ACK Il Il DlFS 站点B 、、 ，／／／／／／ ，A I l I l I I I 似 蚍 l ll J 32lO 3最佳竞争窗口CW。pt 图 1 二进制指数退避算法 系统的性能可以由饱和吞吐量来衡量。所谓饱和吞吐量即是：在系统达到稳定的条件下， 随着整个系统数据报传输负荷量的增加，吞吐量所达到的上限。文献[4，5]提出一种马尔可夫 链的模型来分析无线局域网 MAC层性能。在以下的分析中，我们假定系统内站点的数目固定 不变，同时，每个站点总有数据报要发送。 文献f41的马尔可夫链的模型的分析中，假定在每次数据报发送尝试时，不论该数据报此前 重传过几次，可能发生冲突的概率为一恒定且独立的值 p。定义一个站点在随机选择的一个单 位时间 内可能发送数据报的概率为Pf，则由文献[4]的分析结果可得： 2(1—2p) — (1—-—2p—)—(C—W—m—in—+ 1)—+ p CW——ml—n(—1-——(2p一)m) 维普资讯 http://www.cqvip.com Administrator 高亮 Administrator 高亮 Administrator 高亮 Administrator 高亮 Administrator 高亮 Administrator 高亮 第10期 徐志江等： IEEE 802．11网络中增强的退避算法 1529 式(3)中，m为式(1)所示退避时问的阶数。假定在理想状态下，站点在第一次数据报发送尝试 时，数据报成功得以发送，则退避时间的阶数 m=0，竞争窗口W 为最佳竞争窗口cw。。t， 得在一次发送就成功的理想状态下， 尸￡(0p 丽 (4) 而在一个有 几个站点的系统中，如果n一1个站点不发送数据，则无论另一个站点是否有数据 报要发送，此系统都不会产生冲突，可得： P=1一(1一尸￡) (5) ． 由文献[4]可得，系统中所有站点都不发送即系统空闲的概率P 为 P =(1一 )“ (6) 那么，至少有一个站点发送数据报的概率P 为 Pt ：1一P =1一(1一尸￡) (7) 因此，由文献[4]分析可得在系统不空闲的条件下，有一个站点发送数据成功的概率P 为 Ps：堕 塑 ： ：堕 鱼 (8) 一 ———————————————— ————————————————————————————————⋯ 一 —————————— ——————————————一 ⋯ [系统不空闲的概率】 Pt 一 定义归一化的吞吐量 S如下： 一 E[单位时问内发送的有效载荷信息] ㈨ E[单位时间长度1 令ElF]为在一个单位时间段内，平均有效载荷量。则在一个单位时间段内，平均成功发 送的有效载荷量为Pt P ElF]。令 为数据报成功发送所需的时间， 为数据报发送产生冲 突所耗费的时间，则 S的分母部分由3部分组成：没有数据报发送的时间即标准 【 1所定义的 ， 概率为(1一Pt )；数据报成功发送的时问 ，概率为PtrP ；数据报发送产生冲突的时间 ， 概率为 (1一P。)。由此，得 一 ! 墨圈 (1一ptr) +PtrP +Ptr(1一ps) 如图2，不考虑传输时延，我们可得 = PHYhd +MAChd +ElF]+SIFS+ACK+DIFS] = PHYhd +MAChd +ElF ]+DIFS J 匝巫 匝 圈 图2 基本访问方法下的 和 (10) (11) ∽1 维普资讯 http://www.cqvip.com 1530 电 子 与 信 息 学 报 第26卷 此处，E[P 1为产生冲突的数据报中，最长的数据报的平均值。在分析中，假定数据报的大小 恒定，则 、 、ElF]=E[P ]均趋向于恒定值。由式(4)，(7)，(8)来推导式(10)中s在 cw 条件下的最大值，令 旦 = dS ． =。 (12dCW dCW ) d (。pt) 把式(7)，(8)代入式(10)，化简整理得(详细化简过程参考文献[5]及[6]的附录部分)： (1一Pt) 一 {几Pt一[1一(1一 ) ])=0 (13) 此处 = ／ 。当满足Pt<<1时， (1一 ) ≈1一n +[n(n一1)／2] (14) 把式(14)代入式(13)，得 Pt=[v =_ 二1了 一n]／[n(n～1)( 一1)]≈、／互／(nv ) (15) 代入式 (4)，整理得 cw。pt≈n 2V~：‘ (16) 4增强的退避算法 式(16)说明，如果一个站点对当前的网络状态有一个确切的认识，就可以通过改变竞争窗 口CW ，以使系统的性能趋于最佳。然而在实际情况中，站点并不能确切知道当前的网络状态， 但是可以进行估计。许多文章提到了通过估计来改进退避算法的方法 L5一 。一种方法是站点在 确定退避时间竞争窗口时，取上次数据报成功发送时的竞争窗口的一半。还有一种方法是通过 估计动态站点数量来估计信道利用率的方法。本文也是基于此方法。 在对动态站点估计时，如图 3所示： 1 6 6 3 c 2ll , ．1-l'uq 图3 动态站点的数目估计 图3中，每一格代表一个 or，实线表示此后的一个 时间段内有站点要发送数据报，忽 略数据报发送时间及DIFS，ACK，SIFS等时间段。由图可知，如果某站点准备发送数据报时， CW 取在 a点，在前 8个 中系统没有数据报要发送，则如果此站点发送数据报产生冲突的概 率为0；CW 取在b点，前 16个 中系统有 4个 时间内有数据报发送，则如果此站点发送 数据报产生冲突的概率为 0．25； cw 取在 C点， 32个 中系统有 20个 时间内有数据报 发送，则如果此站点发送数据报产生冲突的概率为0．625。因此，并非 CW 越大，产生冲突的 概率越小。所以在估计动态站点数目时，估计动态站点所取的时间段非常重要，我们更关心的 是某一时间段内的动态站点数目，而非系统内全部的动态站点数目。当一个系统达到动态平衡 时，动态站点的数目也会趋于稳定。 令 为所取估计动态站点数目的时间段 (单位为 )，开始估计时， 按每个 逐渐递 减，每次检测到信道忙 (即有站点发送数据报时)，便停止递减并计数一次，当 递减为0时， 维普资讯 http://www.cqvip.com 第 10期 徐志江等： IEEE 802．11网络中增强的退避算法 1531 所计次数便为该时间内动态站点的估计值 Ⅳ ，则定义信道利用率 (即站点发送数据报发生冲突 的概率)的估计值为： o^=N e 由此可得 cw ≈ (17) (18) 式 (18)所得的CW 在理想状态下，可以使站点发送数据报时不产生冲突，然而在实际情况 下，考虑到数据报发送时产生冲突的可能性，必须对估计值进行修正。令数据报重新尝试 m次 才发送成功，则m=0时，数据报不需重发就发送成功。 由式 (15)，系统内实际的动态站点数目： n≈ ／( ) (19) 本算法中，希望通过对动态站点的估计，得到动态站点的修正值 Nopt，再由此修正值和式 (18)，得到最佳的竞争窗El。如果最佳竞争窗El选择合适，可以达到式(4)的理想状态，即数据 报只需一次即可发送成功 (退避时间价数m=0)。即 (。pt)=2／(W+1) (20) 由式 (19)可知，n与 成反比关系。得 Nop =Pt t0op 把式(3)，(4)代入式(21)，得 [ + [ + (21) +[ (22 此处m表示数据报发送成功时，重复发送的次数。在本算法中，每次站点对当前动态站点的估 计值都不能作为最终的结果，应该以前一次数据报的结果来修正，也即由前一次数据报重复传 送的次数m，前一次动态站点的修正值 (Ⅳ(。。)) 一1来修正本次估计值 ，所以对式(22)作 相应的修改得出下列的增强型退避算法。 本文引入对动态站点数目的估计，根据式 (22)，自适应调节数据报第一次发送尝试时竞争 窗口大小，以增强系统的性能。算法如下： (1)初始化，取( )0为CW i ； (2)在 时间内估计动态站点的数目 ，得信道利用率的估计值为p ； (3)动态站点的修正值为( opt)) = + 筹 ( opt)) 一 ，(m 一 为根据 第n一1次估计，发送数据报时重复尝试的次数)； (4)(CW。pt) =(Nopt) 、／／2 ； (5)( ) 1=(CWopt) ； (6)令 为系统空闲的时间， ， 为本算法所定义一个最大的时间段。如果 < 重复 (2)～(5)步；否则重复(1)～(5)步。 由于IEEE 802．11标准规定，当检测到信道忙时，退避计数便停止计数．所以，在第(2)步 中，只需记录下在 时间内，退避计数停止计数的次数即可。而第(4)步所得的CW。pt是数 维普资讯 http://www.cqvip.com 1532 电 子 与 信 息 学 报 第26卷 据报在第一次发送尝试时，退避算法所确定的竞争窗口。当数据报发送产生冲突时，退避算法 对 CW。。t乘以2重新退避。 第 (3)步的修正值与前一次估计的结果有偏差，即重复尝试的次数m 一l不为0时，表明 上一次的估计值与实际值有偏差，那么此次的估计值做相应的修正，修正的站点数增加，意味 着发生冲突的概率减少。 对于本算法，考虑的是站点一直有数据报需要发送的情况，这只是一种理想的情况。如果 站点长时间处于空闲状态，则这种算法要做相应改变。先给出一个71m(>DIFS)时间参数，当站 点空闲时间正大于 71m时，若有新的数据报需要发送，则本算法从第 (1)步重新开始。 5仿真结果和结论 5。1仿真结果 本文采用事件驱动随机仿真(Event—driven stochastic simulations)的方法进行仿真，如无 特别说明，仿真的条件都是基于数据报大小为常数 P=1024bit，信道传输速率为 2Mbps的 DSSS物理层，系统达到饱和情况下的仿真。本文的主要目的就是要考察在相同情况下，标准算 法和改进算法所体现的系统的性能的差异。 图4表示在站点数目不同的情况下，标准算法和本文所给出增强算法的饱和吞吐量。由图 可知，增强算法的吞吐量明显比标准算法的吞吐量大。而且随着站点数目的增加，标准算法的 吞吐量会逐渐下降；而增强算法的系统饱和吞吐量下降趋于平缓。因此，改进的算法使得系统 的性能，在动态站点数目变化时，趋于稳定。 图5表示在站点数目不同的情况下，两种算法站点每秒的数据报发送量。标准算法的系统， 数据报的发送量在刚开始时，随着站点数目的增加而增大，在 12个站点处达到最大值；而后随 着站点数目的增加而减少。而增强算法的系统，数据报的发送量在刚开始时，也是随着站点数 目的增加而增大；到达 12个站点以后，数据报的发送量随着站点数目的增加趋于平稳。因此， 增强的算法能够在站点数目增加时，每秒仍能保持一定的数据报发送量。 图6表示在站点数目不同的情况下，两种算法数据报成功发送前的延时。Mae层的访问延 时指的是数据报从进入到Mae层的消息队列直到成功发送到目的站点的延时。增强算法的系统 延时随着动态站点数目增加的速率比标准算法的系统延时要低。说明，增强算法系统的站点比 标准算法系统的站点更容易争用到信道，数据报更容易成功发送。 o．90 O 85 O 8O o 75 o．7O 0．65 O 6O O．55 O 5O 动态站点数 图4 饱和吞吐量对动态站点数目 上 篇 e =j 寒 动态站点数 图5 每秒的数据报发送量对动态站点数目 ∞∞ ∞如∞如加 ∞∞ 维普资讯 http://www.cqvip.com 第 10期 徐志江等： IEEE 802．11网络中增强的退避算法 1533 一 捌 豆 ： O lO 2O 3O 40 5O 6O 动态站点数 图6 媒体访问延时对动态站点数 5．2结论 综上所述，增强算法的系统，其性能更稳定，吞吐量和每秒数据发送量随动态站点数量变化 的波动比标准算法的系统小；吞吐量大，且基本稳定在一定范围内；每秒的数据报发送量大， 在动态站点很多时，增强算法系统内的站点仍能保持一定的数据通信量；容易争用到信道。 要注意到的是，本文提到的对动态站点估计的算法中，Te并没有取每次式(2)所得的退避 时间计数器值。因为 为『O， 1内一随机选择的数，当C很小时，N和 很不准确；同时， 如果站点很长时间不发送数据报的话，估计值不能反映实时性。 参 考 文 献 [1】 IEEE Standard for Wireless LAN Medium Access Control(MAC)and PHYsical Layer(PHY) Specifications，Nov．1997．P802．11 Cal i F，Conti M，Gregori E．IEEE 802．11 Protocol：Design and performance evaluation of an adaptive backoff mechanism．IEEE J．on Selected Areas in Communication 2000 18(9、：1774— 1786． Natkaniec M．Pach A R．An analysis of the backoff mechanism used in IEEE 802．1 1 networks． Computers and Communications．2000．Proceedings．ISCC 2000．Fifth IEEE Symposium 2000： 444 449． Bianchi G．Performance analysis of the IEEE 802．11 distributed coordination function．埘 EE|，． on Selected Areas饥 Communications，2000，18(3)：535—547． Ⅵ^l H，Cheng S，Peng Y，Long K，Ma J．IEEE 802．11 distributed coordination function(DCF)： Analysis and enhancement 2002．ICC 2002．IEEE International Conference on Communications． 2002．vo1．1：605-609． Bianchi G，Fratta L，0liveri M．Perfo·rmance evaluation and enhancement of the CSMA／CA MAC protocol for 802．1 1 wireless LANs．IEEE International Symposium on Persona1．Indoor and Mobile Radio Communications，PIMRC’96．Taipei，Taiwan，1996，vo1．2：392—396． Bononi L，Conti M，Gregori E．Design and performance evaluation of an asymptotically opttimal backoff algorithm for IEEE 802．1 1 wireless LANs．Proceedings of the 33rd Hawaii International Conference on System Sciences．Hawaii．2000：103-1 1 2． 徐志江： 李式巨： 官 军： 男， 1973年生，博士生，主要从事OFDM 、信息论及编码等方面的研究． 男，1947年生，博士生导师，研究领域为：数字通信系统、通信网络．移动通信． 男， 1977年生，硕士生，主要从事无线局域网的研究、Wind0wsCE嵌入式操作系统及其应用 4 2 O 8 6 4 2 O 维普资讯 http://www.cqvip.com Administrator 高亮