802.11DCF退避算法改进与仿真

王俊杰，李 达，刘守印

（华中师范大学 湖北 武汉 430079）

802.11DCF退避算法改进与仿真

王俊杰，李 达，刘守印

（华中师范大学 湖北 武汉 430079）

针对IEEE802.11DCF竞争窗口调整策略，提出了一种新的竞争窗口退避算法HBDCF（Hybrid Distributed Coordination Function）。算法利用了TCP（Transmission Control Protocol）拥塞控制的机制，发送失败时，竞争窗口采用先指数增长，达到阈值后线性增长；发送成功次数达到函数值时，竞争窗口采用先线性递减，后指数递减的方式。采用二维Markov chain模型进行理论分析和通过OPNET对改进算法进行仿真实验。研究结果表明，研究结果表明，该算法在规模较大的网络中能够有效地降低DCF碰撞概率和网络延时，提高系统的饱和吞吐量。

IEEE802.11 DCF；竞争窗口；退避算法；OPNET仿真

IEEE 802.11[1]标准定义了无线网络（WIFI）的物理层和MAC（介质访问控制）层[2]，MAC层的协议规定了两种信道接入机制，即分布式协调控制机制（DCF，Distributed Coordination Function）和无竞争的 点 协 调 控 制 机 制 （PCF，Point Coordination Function）。在实际的WIFI协议中，MAC层最常用的接入协议为DCF[3]，它主要采用了带冲突避免的载波侦听多路访问（CSMA/CA[4]）控制机制，利用虚拟载波侦听与物理载波侦听相结合的方式，通过二进制指数退避算法来实现不同节点的自适应接入。DCF接入协议还引入了RTS/CTS协议 （Request To Send/Clear To Send），有效地解决隐藏节点和暴露节点的问题。

MAC协议设计是无线局域网研究的关键技术之一[5]，对DCF协议的改进一直是一个研究热点。针对DCF算法的特点，通过Markov分析模型或仿真实验，得到各参数与网络性能之间的关系[6]，并对这些参数进行调整来优化网络性能。主要研究有：1）对DCF退避算法的竞争窗口的调整机制改进及优化；2）对DCF初始竞争窗口机制改进及优化。

针对退避算法竞争窗口的调整机制改进和优化，Bianchi[7]首先提出了二维Markov Chain模型，并证明了模型的正确性，为以后人们从理论上分析DCF性能提供了理论依据；Song等人[8]提出了发送成功通过乘以大于1的因子增加竞争窗口，发送失败则通过乘以小于 1的因子来减小竞争窗口的EIED算法来改进性能；Ni Q[9]提出了发送成功竞争窗口减半，发送失败竞争窗口加倍，改善了节点中数据的发送效率和公平性；Deng[10]利用已有的分析模型，提出了MILD （乘性增加线性减小）退避机制；Wang Chong gang等[11]提出了当发送冲突时，竞争窗口加倍，当连续传输成功C次后，竞争窗口减半的GDCF算法；徐颖[12]提出了WDCF算法，该算法在GDCF算法的基础上，增加了一个分段函数，连续传输成功的次数门限C（i）根据不同的退避阶段产生不同的连续传输次数。但是，以上算法在减少碰撞概率和网络延时的等方面还存在着一些不足，还有进一步的改进空间。

文中在充分分析和理解上述算法的基础上，比较了每种算法的优缺点，借鉴传统协议中拥塞控制算法的机制，在饱和吞吐量基本不变的情况下，为了降低规模较大的网络中碰撞概率和网络延时，提出了用分段函数来表示竞争窗口的改进算法HBDCF（Hybrid Distributed Coordination Function），并对它的碰撞概率等性能参数进行了理论和仿真分析。

1 算法设计思想及理论模型介绍

1.1 HBDCF算法设计思想介绍

HBDCF是在WDCF算法的基础上，依据TCP拥塞算法思想，提出一种新型退避算法的竞争窗口优化算法，它采用WDCF算法中设定连续传输次数门限C（i）的方法，并在此基础上引入分段函数来表示竞争窗口大小的变化。具体做法是，当每次数据发送失败之后，CW（Contention Window）随着退避阶段i加倍，若退避阶段达到规定的窗口阈值S时，CW开始线性增长。当连续成功传输次数没有达到C次，CW窗口大小不变；当连续成功传送次数达到C次，若CW大于窗口阈值，CW则线性减少，若小于窗口阈值，CW则指数减少。算法采用分段函数来表示竞争窗口的变化，在达到窗口阈值S之前指数增长，使得竞争窗口迅速接近最佳窗口值，达到阈值S之后线性增长，避免了窗口增长过快引起的网络时延等性能的降低。公式（1）、（2）分别给出了竞争窗口与连续传输次数C与退避阶段i的数学表达式。该算法的流程图如图1所示。

图1 HBDCF算法流程图

1.2 Markov Chain模型

目前，在IEEE 802.11 DCF的性能分析和建模的方法中，大家都是在Bian Chi提出的二维Markov链模型上进行相关理论研究。它通过对模型的稳态求解，近似的得到了任意时隙内节点的发送概率和发送数据的冲突概率，进而得到饱和吞吐量。但是，这个模型没有考虑到多跳网络中存在的隐藏终端和暴露终端的问题以及只考虑了数据发送失败没有考虑信道发生错误的情况；同时在建模过程中，没有考虑有限重传次数、退避冻结以及等情况。为了解决上述问题，许多研究学者都进行了相关的研究[13-16]。

由于本文主要研究DCF算法的改进对网络性能的影响，考虑到分析简单的基础上，采用了与文献[1]同样的假设：1）理想信道，不考虑信道的错误，只有冲突才引起丢包和重传；2）各站点均处于饱和状态，即每个站点始终都有数据包在缓存队列中等待发送；3）每个时隙发送数据时，可能产生冲突的概率值p，始终独立且为固定值。

如图2为二维Markov Chain模型，二维随机过程{S（t），B（t）}表示节点的退避计数器在t时刻所处的状态，其中S（t）表示在t时刻节点所处的退避阶段（0，1，2，…，m），m为最大退避阶数，b（t）表示节点在t时刻退避计数器的值，t和t+1表示两个连续时隙（slot）的起始时刻。

图2 二维Markov链模型

假设P{i1，k1|i0，k0}=P{S（t+1）=i1，B（t+1）=k1|S（t）= i0，B（t）=k0}

则图2所示的二维Markov链模型的单步转移概率p可以用以下公式来表示。

其中，P代表某站点尝试传送数据包时的发生碰撞的冲突概率。

指站点在随机选取的时隙里成功传输数据包的概率。Pi代表站点从第i个退避阶段回退到第i-1个退避阶段的概率

Markov链的稳态分布为：

bi，k代表阶段退避时隙位于第i个退避阶段的第k个时隙的概率。由图2和（3）式可得：

以此来推便可以得出：

将（1）和（5）代入（7）可得：

其中

由于对任意的k[1，Wi-1]，根据链式法则可得：

所有时隙的概率都可以用 表示，并且满足以下关系：

所有的数据成功传输都是在退避时隙计为0时发生的，所以

以上归纳总结，由方程（4）、（10）、（11）组成的方程可以得到b0，0，p，τ的非线程方程组，从而可以求借得到p，τ的值。

1.3 饱和吞吐量的计算

设S为归一化系统吞吐量，其定义为有效载荷在信道中占用的时间与总信道时间的比值。定义Pt1为在选取任一时隙时有至少一个节点在发送数据的概率，则Pt1的等式为

定义Ptx为在至少有一个节点发送数据的情况下有节点成功发送数据的概率

则归一化系统吞吐量公式:

其中，E[P]表示数据包平均有效载荷大小，在一个时隙中成功传输的有效载荷的平均大小Pt1PtxE[P]，Ts是因为数据包成功传输而导致其它节点检测到信道繁忙的平均时间；Tc是因为数据包发送碰撞而导致检测到信道繁忙的平均时间；σ表示空闲时隙持续时间。

若仅考虑只通过基本的接入机制管理的通信系统，设分组头部H=PHYhdr+MAChdr，另设δ为传输时延，则有关于Ts，Tc的如下关系式：

E[P*]表示最长数据包在有冲突的情况下平均有效载荷大小。

在分析采用RTS/CTS接入机制的通信系统时，根据协议约定，考虑到碰撞仅仅发生在RTS帧，此时关于Ts，Tc的关系式如下：

2 HBDCF算法的理论计算和仿真分析

上一节从理论上分析了算法，本节通过MATLAB和OPNET对标准DCF、WDCF和HBDCF三种算法从理论和实际情况进行仿真，比较在不同站点的情况下，各个算法的碰撞概率、饱和吞吐量和网络延迟。

首先，我们最关注的是碰撞概率，通过MATLAB对标准DCF、WDCF和HBDCF 3种算法的

碰撞概率进行了理论计算，计算结果如表1所示。

表1 不同站点3种算法包碰撞概率比较

表2 网络节点仿真参数

从表格可以看出，HBDCF算法在不同规模节点下的包碰撞概率值都是最小的，由此可以得出HBDCF算法减小了碰撞概率，并且在规模越大的网络中效果越明显。不过在达到减小碰撞概率的同时，也导致了节点接入延时的增大。

其次，为了更好地对验证算法在实际情况下的表现情况，我们利用OPNET仿真软件，通过OPNET对标准DCF、WDCF和HBDCF3种算法在相同的条件下进行仿真，获得各个算法的碰撞概率、饱和吞吐量和网络延迟的仿真值。仿真时，网络中所有节点的数据传输速率都设置为1Mbps，物理层采用Direct Sequence技术，网络中节点的WLAN参数设置如表2所示。

以下分别给出了HBDCF算法在RTS接入与非RTS接入方式下与DCF、WDCF在碰撞概率、网络时延、以及归一化吞吐量在不同节点数时的具体参数。

图3 非RTS接入方式碰撞概率的变化曲线

图4 RTS接入方式碰撞概率的变化曲线

从图3和图4可以看出，HBDCF算法的碰撞概率要优于其他算法，并且在网络规模越大是表现的越明显，从而印证了理论分析的正确性，并且可以看出，HBDCF算法在非RTS协议有更好的效果。

从图5和图6可以看出，HBDCF算法对吞吐量的改善不是很大，特别是在规模较小的网络中，不过在网络规模数大于50个节点时，吞吐量会有一些明显的改善。同时也可以看出，在非RTS情况下的吞吐量比RTS情况下的吞吐量要大。

图5 非RTS接入方式归一化饱和吞吐量的变化曲线

图6 图6 RTS接入方式的归一化饱和吞吐量的变化曲线

图7 非RTS接入方式网络延迟的变化曲线

图8 RTS接入方式网络延迟的变化曲线

从图7和图8可以看出，HBDCF算法对网络延时的没有很大的改善，不过还是有了一些优化，同时在我们仿真中部分节点延时反而比较大，也就是说，HBDCF算法并不能对网络的各个标准参数都进行了改善和提高，也可以看出该算法也具有一定的局限性。

从以上仿真图我们可以看出，HBDCF算法能够有效地降低WLAN网络中各节点发送包的碰撞概率，整个系统饱和吞吐量的性能也有所改善，并且在网络延时方面也有一定的优化。另外，HBDCF算法应用于RTS/CTS环境比应用于非RTS环境中，对网络整体性能有更好的改善。

3 结束语

文中是为了优化大规模网络下的包碰撞概率，提出了一种新型的竞争窗口动态调整退避算法，巧妙的在退避阶段增长时采用拥塞函数思想以及在退避门限减少时两次采用拥塞函数思想对DCF算法进行了优化。本文首先根据二维Markov链建立了理论模型，从理论上计算出了该算法在包碰撞概率；然后在OPNET上进行了实验仿真，仿真结果表明该算法在不仅仅在包碰撞概率有了很大的改善，在时延和网络吞吐量方面相对于DCF以及WDCF算法也都有所改善。并且可以通过阈值s和斜率k2，来动态改变碰撞概率和吞吐量等网络性能参数，使其能够符合特定的网络需求。然而，对不同规模网络的最佳阈值和最佳斜率等因素尚未得出结论，这些将是下一步研究的内容。

[1]by IEEE eD.11:Wireless LAN Medium Access Control （MAC） and Physicallayer （PHY）specifications:Medium Access Control（MAC）Enhancements for Quality of Service（QoS），Draft Supplement to[C]//IEEE 802.11 Standard，Draft 13.0.2010.

[2]MATTBEW S.GAST.802.11无线网络权威指南[M].2版.南京：东南大学，2007.

[3]范谦.IEEE 802.11 MAC机制性能分析及其改进[D].杭州：浙江大学，2003.

[4]Ni J，Srikant R.Distributed CSMA/CA algorithms for achieving maximum throughput in wireless networks[C]//Information Theory and Applications Workshop,2009（2015）:250.

[5]熊春兰.IEEE802.11DCF协议性能分析及退避算法改进[D].广州：中山大学，2009.

[6]张南.无线网络MAC层接入控制研究[D].北京：北京交通大学，2013.

[7]Bianchi Giuseppe.Performance analysis of the IEEE 802.11 distributed coordination function[J]. IEEE Journal on Selected Areas in Communications，2000，18（3）:535-547.

[8]Song N O，Kwak B J，Song J，et al.Enhancement of IEEE 802.11 distributed coordination function with exponential increase exponential decrease back off algorithm [C]//Vehicular Technology Conference, 2003.VTC 2003-Spring.The 57th IEEE Semiannual.IEEE，2003，4:2775-2778.

[9]Decrease Ni Q,Aad I,Barakat C,et al.Modeling and analysis of slow CW decrease IEEE 802.11 WLAN[C]//14th IEEE Proceedings on Personal, Indoor and Mobile Radio Communications（PIMRC 2003）.IEEE，2003，2:1717-1721.

[10]Deng J,Varshney P K,Haas Z J.A new back off algorithm for the IEEE 802.11 distributed coordination function[EB/OL].（2017-03-20）.http：//www.docin.com/p-854815510.html.

[11]WANG Chong-gang，LI Bo.A new collision resolution mechanism to enhance the performance of IEEE 802.11 DCF[J].IEEE Transactions on Vehicular Technology，2004，53（4）:1235-1246.

[12]徐颖，白光伟，王明超.基于竞争窗口动态调整的802.11 DCF改进算法 [J].计算机工程与设计，2009，30（23）:5308-5310.

[13]钟萍，施海彬，庄玉祥，等.IEEE 802.11DCF协议性能分析模型[J].应用科学学报，2013，31（1）:41-47.

[14]唐伦，刘益富，刘青海，等.一种改进IEEE 802.11 DCF的建模与分析 [J].北京邮电大学学报，2014（5）:96-99.

[15]冯鑫，党幼云，向乾，等.基于物联网的电量采集及分析系统设计 [J].陕西电力，2014（2）：80-84.

[16]申定辉，刘坤，刘宇滕，等.基于统计学指标的配电网状态估计目标函数的性能分析[J].陕西电力，2015（7）：43-47.

New improved back-off algorithm and simulation for 802.11DCF

WANG Jun-jie，LI Da，LIU Shou-yin
（Central China Normal University，Wuhan 430079，China）

In this paper，Hybrid Distributed Coordination Function algorithm for 802.11DCF is proposed. We begin with the read of existing strategies on back-off methods.Similar to the traditional Transmission Control Protocol congestion control，after consecutive failure transmission，contention window increases exponentially with back-off stage initially，then turns to increase linearly when the threshold is arrived；after successful transmission，if the consecutive successfully transmission times reach to the function value，contention window decreases linearly initially，then turns to decrease with back-off stage when the threshold is arrived.We use a Markov chain model to analyze the impact of the HBDCF and Through OPNET Simulation Tools to simulate.The simulation demonstrate that this algorithm reduce the probability of collision and delay，improve the saturation throughput effectively in large wireless net.

IEEE802.11 DCF；contention window；back-off algorithm；OPNET simulation

TN923

A

1674－6236（2017）10-0148-06

2016-04-23稿件编号：201604230

王俊杰（1989—），男，山西阳泉人，硕士。研究方向：WIFI稳定性研究、物联网。