IEEE 802.11 DCF的一种改进退避算法-不知不识网

　　摘要：IEEE 802.11中的分布式协调功能(DCF)通常采用二进制指数退避(BEB)算法。为了提高该算法的性能，在BEB算法的基础上提出了一种改进的退避算法，该算法考虑前一数据包的冲突情况，指数减小竞争窗口(CW)，并尽可能减小退避过程中的分布式帧间间隔(DIFS)开销。基于OPNET网络仿真平台，对改进算法的性能进行了仿真评估。仿真结果表明，改进后的退避算法在吞吐量和时延方面，其性能优于BEB算法和指数增加指数减小(EIED)算法。
　　关键词：无线局域网；分布式协调功能；退避算法；二进制指数退避
　　中图分类号：TN915-34文献标识码：A
　　文章编号：1004-373X(2011)01-0011-03
　　
　　Improved Back-off Algorithm for IEEE 802.11 DCF
　　ZHENG Wen-jun1, ZHOU Kai2, MA Dong-tang2
　　(1. Career Training Center, Bureau of Ningbo Labour and Social Security, Ningbo 315000, China;
　　2. Electronic Science and Engineering College, National University of Defense Technology, Changsha 410073, China)
　　Abstract： The binary exponential back-off (BEB) algorithm is used for the distributed coordination function (DCF) in the IEEE802.11 WLAN. An improved back-off algorithm is proposed to enhance the performance of the algorithm. In the proposed algorithm, the collision history of the previous packets is considered and the collision window (CW) is reduced exponentially，and the distributed inter-frame space (DIFS) overhead resulting in DIFS periods in the back-off procedure is minimized. Based on network simulation platform of OPNET, the performance of the improved algorithm is simulated and evaluated. Simulation results show that the improved algorithm has higher throughput and lower delay than the BEB algorithm and the exponential increase and exponential decrease (EIED) algorithm.
　　Keywords： WLAN; distributed coordination function; back-off algorithm; binary exponential back-off
　　
　　0 引言
　　IEEE 802.11［1］是目前广泛应用的无线局域网(WLAN)标准，它提供了WLAN物理层(PHY)和媒体接入控制层(MAC)的详细规范。MAC层规范定义了两种媒质接入协调机制，分别是分布式协调功能(Distribution Coordination Function，DCF)和点协调功能(Point Coordination Function，PCF)，其中DCF是随机接入机制。
　　随机接入协议中的一个重要内容就是如何解决碰撞问题。IEEE 802.11 DCF采用二进制指数退避策略(BEB)，当节点发生碰撞，竞争窗口(CW)按二进制指数规律增长时，随着网络中节点数的增加，碰撞概率越来越大，这就造成网络性能(如吞吐量、时延等)的下降。为了提高网络性能，很多文献都提出了一些新的算法。文献［2］通过对IEEE 802.11 DCF中退避算法的仿真分析发现，适当的CWopt可以改进网络的性能。文献［3］介绍了利用卡尔曼滤波器估计网络中节点数目的方法，为计算CWopt提供数据。文献［4］利用文献［3］的结果推导出CWopt的计算公式，在成功传输后将CW设为CWopt，以此改进提高网络吞吐量。文献［5］提出的算法思想是将［CWmin,CWmax］均匀分为几个小的长度，各个长度彼此间不重叠，当发生冲突时，节点将在更大的范围内选择退避值；反之，节点将根据网络负载的情况从较小的范围内选择退避值。这样可以有效地降低碰撞概率，从而提高系统性能。文献［6-8］提出指数增加指数减小(EIED)算法，其主要思想是通过改变CW值来达到改进系统性能的目的。当发送成功时，CW=CW/rD；发送失败后，CW=CW*rI。此外从理论分析和仿真方面，验证了EIED退避算法，并提供更好的吞吐量和时延。文献［9-10］分别通过减少slot_time和DIFS开销，提高了系统的吞吐量，降低了系统时延。
　　以上改进算法均在一定程度上改进了系统的性能，但都是某一方面的改进，如降低碰撞概率，减小开销(DIFS,退避时间)等。本文综合以上两个方面，提出了一种新的改进的退避算法，并且对其性能进行了仿真分析。下面首先简短阐述IEEE 802.11 DCF的基本原理，然后提出改进的退避算法，最后进行网络仿真，给出仿真结果和结论。
　　1 IEEE 802.11 DCF工作原理
　　DCF包括两种工作模式，即基本工作模式和RTS/CTS工作模式。在基本工作模式中，节点在传输数据前必须侦听信道是否空闲，如果信道空闲时间大于DIFS，则开始传输数据包。换句话说，如果信道忙，节点必须等待当前传输结束后才能开始它的传输。这意味着节点在传输数据前需要等待DIFS间隔，并且随机选择一个退避值B开始其退避过程。当信道空闲时，退避计数器线性减小。当侦听到信道上有数据传输时，冻结退避计数器，并且等到信道空闲时间超过DIFS间隔后重新开始退避计数。只有在退避计数器值为零时，节点才开始传输。
　　在IEEE 802.11中，时间以slot_time为基本单位，其定义为：当某个站在一个slot_time内开始接入媒体时，那么在下一slot_time开始时，其他站就都能够检测出信道已转变为忙态。退避值B是从［0,CW－1］中随机取得的一个整数值，退避时间为：backoff_time=B*slot_time。CW的初始值为CWmin+1。如果有两个或两个以上的节点在同一时刻退避结束时(即backoff_time为零)，冲突将不可避免发生。此种情况下，各个节点将再等待DIFS间隔后重新从［0,CW*2］中随机选择一个退避值，并开始其重传前的新一轮退避。当源节点在发送数据包后的SIFS间隔后收到目的节点发送的确认帧(ACK)时,表明此次传输成功，源节点将CW设为CWmin。其原理如图1所示。
　　
　　图1 IEEE 802.11 DCF基本接入模式
　　在RTS/CTS模式中，节点在发送数据包前先发送RTS帧，目的节点在收到RTS帧后等待SIFS间隔，再发送CTS帧。节点只有在正确收到CTS帧后才开始发送数据包。显然，使用RTS和CTS帧会使整个网络的效率下降。但这两种控制帧都很短，其长度分别为20 B和14 B，与数据帧(最长为2 346 B)相比，开销不算大。因此，在传输的数据包较大时，采用RTS/CTS模式可以提高系统性能。
　　2 改进的退避算法
　　在BEB中，当节点成功传输后，将CW设为CWmin，一方面由于CW减小的速度太快，节点随机选取的退避值较小，从而增加了碰撞概率，降低了公平性；另一方面忽略了成功传输前的CW值，在慢衰落环境中系统状态基本保持不变。因此在选择新的CW时,要考虑前一次的CW值。另外，IEEE 802.11 DCF规定,节点在退避过程中，信道从忙变为空闲后需要等待DIFS间隔才继续其退避过程。在高负载的网络中，以上两个方面会大幅降低系统的性能。因此，在改进的算法中，节点在成功传输后将CW设为CW=CW/rD，在失败后同BEB一样将CW设为CW=CW*2。在给定CWmin和CWmax值后，通过改变rD值，可以获得最大的饱和吞吐量。同时，新的算法规定在退避过程中，信道从忙变为空闲时节点不需要等待DIFS间隔而继续退避。当退避结束时，节点开始传送数据。改进的算法一方面可以改进网络中节点接入媒质的公平性，另一方面可以显著提高系统的吞吐量，并降低系统时延，其原理如图2所示。
　　图2 改进的接入模式
　　3 算法性能仿真
　　为了评估本文提出的退避算法，利用OPNET 10.5搭建了网络仿真平台，在有限的网络负载条件下，仿真分析了系统的吞吐量和时延性能。为了简化仿真复杂度，假设信道为理想的，即没有暴露终端和隐藏终端的影响，且节点的数目有限。具体参数设置如表1所示。
　　表1 网络仿真参数
　　参数名参数值参数名参数值
　　数据包长度 /B200传播延时 /μs1
　　时隙大小/μs9仿真时间 /s20
　　DIFS /μs34SIFS /μs16
　　CWmin16CWmax1 024
　　rD1.414节点数目20
　　图3给出了改进算法与BEB,EIED的吞吐量比较。从图中可以看出,在饱和吞吐量的条件下，改进的退避算法比BEB退避算法在吞吐量性能上有很大的提升，与EIED算法相比较也有一定的改进。此时，网络中的节点数目较多，发生碰撞的概率较大，指数减小CW可以有效地降低节点间的碰撞概率，从而大幅度提高吞吐量。另外，由于减小在退避过程中引起的DIFS开销，可以在一定程度上提升吞吐量的性能。可以看出，随着节点数目的增加，减小DIFS开销可以更大地提高系统的吞吐量。
　　图4给出了改进算法与BEB,EIED的时延比较。从图4可以看出，在非饱和吞吐量的条件下，EIED算法和BEB算法的时延性能基本一样，但改进的算法的时延却明显小于BEB算法的时延。由于在非饱和条件下，节点间相互冲突的概率较小，此时EIED采用指数降低CW值，对减小碰撞概率的作用很小，因此它的时延与BEB算法的时延基本一致。由于网络中的节点数目较多，节点在退避过程中侦听信道忙的概率很大，因此造成的DIFS开销较多。改进的算法降低了在退避过程中引起的DIFS开销，因此可以明显地降低时延。
　　图3 改进算法与BEB,EIED的吞吐量比较
　　图4 改进算法与BEB,EIED的时延比较
　　4 结语
　　经过分析比较，提出了一种改进的退避算法，通过指数减小CW值和最小DIFS开销,在吞吐量和时延指标上提高了IEEE 802.11 DCF基本接入方式的性能。将改进的算法同BEB算法、EIED算法进行了性能的仿真比较，其结果表明,改进的算法在吞吐量和时延方面都优于BEB算法和EIED算法。另外，该算法简单，有效，易于实现。
　　
　　参考文献
　　［1］IEEE Computer Society LAN MAN Standards Committee. IEEE 802.11-1999 wireless LAN medium access control (MAC) and physical layer (PHY) specifications[S]. 
　　［2］NATKANIEE M, PATCH A R. An analysis of the backoff mechanism used in IEEE 802.11 networks[C]// Proceedings of Fifth IEEE Symposium on Computers and Communications. Antibes, France: ISCC , 2000: 444-449.
　　［3］ALBERTO L T, TOM V, WANG Xiao-dong. Adaptive optimization of IEEE 802.11 DCF based on Bayesian estimation of the number of competing terminals[J]. Proceeding of IEEE Transactions on Mobile Computing, 2006, 5(9): 1283-1296.
　　［4］JIN B K, JEONG H K, YOUNG A S, et al. A self-tuning contention resolution scheme for IEEE 802.11 wireless LAN[C]// Proceeding of ICACT 2006. Phoenix Park: ICACT, 2006: 565-569.
　　［5］ADLEN K, ABDELHAMID N, ABDELHAK G, et al. Determinist contention window algorithm for IEEE 802.11[C]// Proceeding of 2005 IEEE 16th International Symposium on Personal, Indoor and Mobile Radio Communication. Berlin: IEEE, 2005, 4: 2712-2716.
　　［6］NAH-OAK S, BYUNG-JAE K, LEONARD E M. Analysis of EIED backoff algorithm for IEEE 802.11 DCF[C]// 2005 IEEE 62nd Vehicular Technology Conference.[S.l.]: IEEE, 2005, 4: 2182-2186.
　　［7］NAH-OAK S, BYUNG-JAE K, LEONARD E M. Enhancement of IEEE 802.11 distributed coordination function with exponential increase exponential decrease backoff algorithm[C]// The 57th IEEE Semiannual Vehicular Technology Conference. MD, USA: IEEE, 2003, 4: 2775-2778.
　　［8］WEN-KUANG K, JAY C C. Enhanced backoff scheme in CSMA/CA for IEEE802.11[C]// 2003 IEEE 58th Vehicular Technology Conference.[S.l.]: IEEE, 2003, 5: 2809-2813.
　　［9］YOUNGGOO K, YUGUANG F, HANIPH L. Design of MAC protocols with fast collision resolution for wireless local area networks[J]. IEEE Transactions on Wireless Communications, 2004, 3 (3): 793-807.
　　［10］BHANDARI B N, KUMAR R V R. MASKARA S L. A Modified Back-off Algorithm for the IEEE802.11 DCF[C]// 2005 13th IEEE International Conference on Networks. India: IEEE, 2005: 51-54.
　　作者简介：郑文俊男，1967年出生，浙江宁波人，工程师。主要研究方向为通信与计算机网络技术。
　　周凯男，1985年出生，安徽巢湖人，硕士研究生。主要研究方向为通信网络技术。
　　马东堂男，1969年出生，安徽灵璧人，博士，教授。主要研究方向为宽带通信与网络技术。
　　注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文
　　