一种基于动态约束发送门限退避算法

张长森　陈鹏鹏

(河南理工大学计算机科学与技术学院　河南 焦作 454000)



一种基于动态约束发送门限退避算法

张长森陈鹏鹏

(河南理工大学计算机科学与技术学院河南 焦作 454000)

为了改进IEEE 802.11 DCF协议的二进制退避算法，提出一种基于动态约束发送门限退避算法。算法根据网络中站点对信道资源的争用程度设置动态门限，适当地约束部分站点数据的发送。一方面，算法没有对二进制退避算法的竞争窗口调整机制进行修改，保留了其简单、容易实现的优点；另一方面，有效地解决了传统二进制退避算法在完成退避过程后，没有考察网络状况而直接进行数据传输，容易产生冲突的缺点。仿真结果表明，该算法能够提高饱和吞吐量和降低分组平均接入时延。

退避算法分布式协调功能动态门限

0　引　言

随着人们对便携电脑和移动工作站需求的日益增加，需要无线终端提供更加高效和可靠的通信。退避机制是无线网络MAC层协议中解决站点竞争信道资源发生碰撞的方法，目的是在多个站点争用同一信道时，保证接入的有效性，使得系统资源得到合理利用。算法既要抑制冲突的发生，又要避免因回退时间过长导致信道利用率的降低。

BEB机制为节点提供一种基于竞争窗口CW(Contention Window)解决冲突问题的方法。站点经历一个以时隙为单位的退避时间后，进行数据发送，当冲突发生时，CW增大为原来的二倍；当数据帧传输成功时，CW设置为初值。BEB算法在一定程度上抑制了冲突的发生。包括IEEE 802.11[1]、802.15.4标准在内的许多无线网络协议都采用二进制指数退避机制BEB(Binary Exponential Backoff)管理数据的重发。但是，当网络中存在大量动态站点尝试接入传输媒体时，其存在碰撞概率高、信道利用率低、接入公平性差等缺点[2-4]。针对算法的不足，一些研究者通过改进CW的调整方式来提高网络性能。在文献[5]提出的MIMD(Multiple Increase Multiple Decrease)算法中，发生碰撞时，CW按二进制指数方式逐级增加；发送成功时，CW按二进制指数方式减小。文献[6,7]在文献[5]的基础上提出GDCF(Gentle DCF)，GDCF设定了一个连续传输成功次数计数器，计数器达到阈值c时，CW减半。文献[8]发现在网络负载较重时，算法不能赋予站点充足的退避时间，将导致大量冲突。为此，提出根据网络规模调整站点对信道的争用策略。文献[9]提出一种适用于无线传感器网络的退避算法，使用工作模式切换机制管理网络中动态站点数量，进而制定相应的CW。文献[10]参照站点传输数据成功次数和失败次数对CW进行设定，提高了信道接入的公平性。在文献[11]中，无线站点利用接入点AP(Access Point)共享信息在分布式的网络环境中优化CW。文献[12]根据网络中竞争节点的数量自适应地调整最小竞争窗口，提高了网络吞吐量。

传统二进制指数退避算法在完成退避过程后，没有考察网络状况而直接进行数据传输，容易产生冲突。文献[13]的思想是站点完成退避后不是立即接入信道，而是通过一个和数据帧重传次数相关的传输概率P_T来竞争信道的使用权，并改进了数据发送成功时BEB算法的CW调整方式，但是却没有通过建立数学模型对传输概率的选取进行讨论。文献[14]延续了文献[13]的思想并通过数学建模求得传输概率P_T的理论最优值，但是没有考虑数据帧重传次数对站点接入信道概率的影响。为了便于表述，称之为CDCF。

在深入研究文献[13，14]的基础上，提出一种基于动态约束发送门限退避算法。算法设置了一个和网络中竞争站点数量密切相关的门限对数据的传输进行适当的约束，以达到灵活地配置站点退避时间的目的。门限值设置为关于数据帧重传次数的隐函数，并通过二维离散时间马尔科夫链建模分析其取值对网络性能的影响。和大多数改进算法不同的是，该算法完整地保留了BEB算法的CW调整策略，便于控制、容易实现。理论分析和仿真结果表明，该算法在网络饱和吞吐量等性能指标上都有不同程度的提高。

1　相关工作

1.1IEEE 802.11 DCF

分布式协调功能(DCF)是IEEE802.11中重要的信道接入机制。DCF描述了两种数据帧发送方式：基本方式和RTS/CTS方式。RTS/CTS方式可以解决隐藏终端和数据帧过大引起的信道利用率降低等问题。DCF采用BEB机制解决节点冲突问题，在高负荷的无线网络中，站点都要经历一个和CW相关的退避时间。具体方法是每个站点在尝试发送报文之前，以CW表示CW的大小，按照均匀分布在竞争窗口[0,CW-1]中取一个退避时隙数T作为退避计数器的初值。每次站点侦听到一个空闲时隙，T自减1。当 T减小到0时，站点以基本方式或者RTS/CTS方式发送数据。CW按照数据是否传输成功进行更新，如下式所示：

(1)

需要指出的是，CWmax表示当CW最大时T的最大取值，由于T是按照均匀分布在[0,CW-1]中取值的，CW的最大取值比CWmax大1；CWmin表示CW最小时T的最大取值，同理，CW的最小值比CWmin大1。

以Wi表示节点各个递增阶段CW的大小，则Wi满足：

(2)

其中，W=W0=CWmin+1 表示CW的最小值，2mW=CWmax+1表示CW的最大值，i为数据帧所经历的重传次数，即节点所处退避阶段，m为最大重传次数或最大退避阶段。可见，网络中碰撞越频繁，重传次数越大，节点所处退避阶段越高。

1.2饱和吞吐量

假定1在网络中有n个站点竞争一个无线信道，信道条件是理想的(不考虑隐藏终端和信道捕获)，系统工作在饱和状态，即每个站的发送队列总是非空的。

以τ表示某个随机选定的时隙，每个站点发送数据帧的概率对于整个网络中的n个站点，可能有以下三个事件发生：

(1) 网络中没有站点尝试接入信道，其概率pidl为:

pidl=(1-τ)n

(3)

(2) 网络中有一个节点成功接入信道，其概率psuc为:

(4)

(3) 网络中有两个或者更多的站点尝试接入信道发生碰撞，其概率pcol为:

pcol=1-psuc-pidl=1-(1-τ)n-nτ(1-τ)n-1

(5)

整个网络的归一化饱和吞吐量可以定义为成功传输数据分组(不包含头部)的信道时间与总的信道时间的比值[15]。以符号S表示归一化饱和吞吐量。可以把S表示成下面的形式：

(6)

其中，Ts是一次传输成功导致信道被侦听到繁忙的平均时长，Tc是一次冲突而导致信道被侦听到繁忙平均时长，E[L]是数据分组平均有效长度，σ是一个空闲时隙的长度。

图1　饱和吞吐量S和节点发送概率τ的关系

图1参照标准[1]中相关参数描述了在基本发送方式和RTS/CTS方式下，网络中竞争站点数量为10到30时，饱和吞吐量S与节点发送概率τ的关系。其中，数据分组平均有效长度E[L]为1000 Byte。从图中发现，在相同条件下，基本方式下饱和吞吐量的曲线比RTS/CTS方式更为陡峭。两种方式中，均存在一个使得S取得最大值的发送概率τ0，在τ0两侧S均呈现下降趋势。设计退避算法时，应该使得发送概率τ尽量接近τ0，这样可以提升网络性能。

2　基于动态约束发送门限退避算法

2.1算法描述

在动态分布式的网络环境中，动态竞争站点数量反映了网络当前的竞争状态。站点的竞争接入碰撞概率随着网络中竞争站点数量的增多而增大，当碰撞概率很大时,盲目地发送数据包会导致网络状况恶化。为了能够根据动态竞争站点数量调整门限值从而达到特定的性能需求，把门限值定义成一个容易实现的非线性函数，以表现站点在不同退避阶段所侦听到信道的拥塞程度。定义约束发送门限如下式所示：

Ci=θii∈[0,m]

(7)

式中符号Ci表示站点处于退避阶段i时的约束发送门限。在2.2节中，将根据网络中竞争站点数量确定θ的最优值。基于动态门限约束发送门限退避算法描述如下所示：

if (reach the slot of transmission)

//到达发送时隙

then { obtain θ based on the information of competition stations,then calculate Ci}

//根据竞争站点数量确定θ，从而得到门限值Ci

if (R≤Ci)

//按照均匀分布在[0,1]中随机取一个值R和Ci进行比较

then {send frames or RTS packet }

//发送数据帧

else { back off in current back-off stage}

//若R>Ci，不进行数据发送，在当前退避阶段重新退避

if (the node fails to access the channel)

then {CWnew=min(CWmax+1,CWold×2) }

//把竞争窗口更新为原来的2倍，直到达到最大

else {CWnew=CWmin+1}

//把竞争窗口设置为最小值

在上述对改进算法的描述中容易发现，站点完成退避过程后，需要通过门限值Ci判断是否对数据进行发送。由均匀分布的性质可得，站点完成退避后，有Ci的概率进行数据发送，有1-Ci的概率约束发送，在当前退避阶段重新退避。

2.2算法性能分析

这一节主要是通过建立二维离散时间马尔科夫链模型，分析当网络中竞争节点数量变化时θ和网络饱和吞吐量的关系，求得θ的最优值。

假定2某一个站点在某个时隙发送的数据帧发生冲突的概率pc为常数，和数据帧经历过多少次冲突无关[15]。

其余参数定义如下：

k为退避计数器的值;

马尔科夫链的二维状态空间为：{(0,0)，(0,1)，(1,0)，…，(i,k)},i∈[0,m],k∈[0,Wi-1]；

P{i,k|i-1,k-1}表示从状态(i-1,k-1)转移到状态(i,k)的转移概率；

bi,k表示站点处于退避阶段为i,退避计数器的值为k这一状态的稳态概率。

改进算法保留BEB算法的竞争窗口调整策略，以Wi表示站点处于各个退避阶段的竞争窗口CW，则Wi同样满足式(2)，CWmax、CWmin和W的定义均和1.1节中相同。在假定1和假定2的条件下，可以得到改进算法的二维离散时间马尔科夫链模型，如图2所示。其一步非空状态转移关系，如式(8)所示：

(8)

式(8)中第一个式子表示在退避过程中，站点每次侦听到一个空闲时隙，退避计数器的值自减1；第二个式子表示站点退避计数器的值减至0，站点以Ci的概率进行数据发送，且发送成功，退避阶段设置为0，退避计数器按均匀分布在[0,W0-1]中取值；第三个式子表示如果发生冲突，退避阶段增加1，退避计数器按均匀分布在[Wi-1]中取值；第四个式子表示站点在完成退避过程后，以1-Ci的概率不进行数据发送，根据原退避阶段所对应的竞争窗口确定退避计数器的值，重新进行退避；第五个式子表示当退避阶段达到最大值m时，被约束发送或者发送数据失败都不会使得退避阶段增加。

图2　改进算法的二维马尔科夫链模型

由状态转移关系得各稳态概率满足式(9):

(9)

将式(7)代入式(9)，经过化简，得到：

(10)

由于遍历状态空间中所有状态的稳态概率分布之和为1，得到：

(11)

联立式(2)、式(10)、式(11)，得到：

(12)

由式(10)可以把某个时隙站点的发送概率τ表示为:

(13)

联立式(6)、式(12)和式(13)，可以把系统饱和吞吐量表示成只含有θ、W和n的函数 。在W和竞争站点数量n为常量的情况下，使得系统归一化饱和吞吐量S最大化需要满足S对θ的偏导数为0。

(14)

在MATLAB中使用迭代法可以得到在竞争节点数量n为10到100，θ在两种接入方式下的最优值，如表1所示。其中，W=32，E[L]=1000 Byte。

表1　θ的最优解

求得θ的最优解后，联立式(12)和式(13)，得到某个随机选定的时隙，某个站点发送数据帧的概率τ。图3描绘了在两种发送方式下，改进算法和BEB算法的发送概率τ随着竞争站点数量的变化曲线。为了进行比较，在图3中还给出了当归一化饱和吞吐量取得最大值时发送概率τ0的取值随着竞争站点数量的变化曲线。在图中可以看到，在两种方式中发送概率τ都是随着竞争站点数量的递增而减小。在两种方式下，BEB算法的发送概率是相同的，改进算法的发送概率τ都小于BEB算法。随着竞争站点数量的增加，改进算法的发送概率τ越来越接近于饱和吞吐量最大时发送概率τ0的曲线。通过前面的结论可知，改进算法通过约束站点数据帧的发送减小站点的发送概率，可以使得网络稳态性能得到提升。

图3　站点发送概率与竞争站点数量的关系

3　仿真分析

为了验证改进算法的效果以及上述理论分析的正确性，利用Matlab R2009a进行仿真实验。仿真时间为300 s。网络中竞争站点数目分别取10到100，随机选取一个站点为目的站点，其余站点均向其发送数据分组。任意两个站点之间均是一跳可达的。数据分组的平均有效长度为1000 Byte，其他仿真参数参照文献[1]中基于DSSS PHY的DCF协议，如表2所示。下面仿真分析了改进算法在不同竞争站点数量下的网络性能。

表2　主要仿真参数

图4和图5给出了两种方式下，不同算法的饱和吞吐量随着竞争站点数量增大的变化曲线。从图中可以看到，在RTS/CTS方式下，当竞争站点数量较少时，BEB算法和其他算法的饱和吞吐量差距较小。随着竞争站点数量的增大，其他算法的饱和吞吐量开始均高于BEB算法，其中，改进算法的网络饱和吞吐量是所有算法中最高的。在基本发送方式下，网络饱和吞吐量随着竞争站点的增多呈现下降趋势，其中，BEB算法的网络饱和吞吐量随着竞争站点数目的增加下降最为明显，改进算法的饱和吞吐量随着竞争站点数量的增加基本保持平稳，下降幅度很小。改进算法的饱和吞吐量始终高于其他算法，随着竞争站点数目的增大这种趋势越来越明显。在竞争站点数目为100时，改进算法的网络饱和吞吐量比BEB算法提高了69.35%。

图4　基本发送方式网络饱和吞吐量

图5　RTS/CTS方式网络饱和吞吐量

分组的平均接入时延为数据帧从进入MAC层缓存到完成发送所需的时间。图6给出了两种发送方式下平均接入时延随着竞争站点数量的变化曲线。

图6　两种方式平均接入时延

从图中可以看出，在两种发送方式下，随着竞争站点数量的增大不同算法的平均接入时延曲线均呈现上升趋势。在两种发送方式下，对于不同竞争站点数目，改进算法的平均接入时延始终低于BEB算法，随着站点数量的增加，它们之间的差距有扩大的趋势。在基本发送方式下，当竞争站点数量为100时，改进算法的平均接入时延不到BEB算法的一半。这表明改进算法可以有效地降低网络中节点竞争有限资源发生碰撞的概率，提高了站点接入信道的效率。

4　结　语

为了改进BEB机制，提出一种基于动态约束发送门限退避算法。算法中设置了一个和网络中竞争站点数量密切相关的门限对数据的传输进行适当的约束,并通过二维离散时间马尔科夫链建模求得其最优值。以相同的物理层参数在802.11 DCF协议中进行仿真，在两种发送方式下，该算法的网络饱和吞吐量和平均接入时延均优于BEB算法。在基本发送方式下，改进算法网络性能的提升更加明显，和其他改进算法相比该算法也有不同程度的性能提升。和大多数改进算法不同的是，该算法完整地保留了BEB算法的CW调整策略，便于控制、容易实现。

[1] IEEE Std 802.11.Part 11:Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications[S].New York:IEEE Press,2007.

[2] Xinghua S,Dai L.Backoff Design for IEEE 802.11 DCF Networks:Fundamental Tradeoff and Design Criterion[J].IEEE/ACM Transactions on Networking,2015,23(1):300-316.

[3] Lei G,Assi C M,Benslimane A.Enhancing IEEE 802.11 Random Backoff in Selfish Environments[J].IEEE Transactions on Vehicular Technology,2008,57(3):1806-1822.

[4] Shugong X,Saadawi T.Does the IEEE 802.11 MAC protocol work well in multihop wireless ad hoc networks?[J].Communications Magazine,IEEE,2001,39(6):130-137.

[5] Haitao W,Shiduan C,Yong P,et al.IEEE 802.11 distributed coordination function (DCF):analysis and enhancement[C]//Procedings of IEEE International Conference on Communications,New York,NY,2002(1):605-609.

[6] Chonggang W,Weiwen T,Sohraby K,et al.A simple mechanism on MAC layer to improve the performance of IEEE 802.11 DCF[C]//Proceedings of the First International Conference on Broadband Networks,2004:365-374.

[7] Chonggang W,Bo L,Lemin L.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.

[8] Cali F,Conti M,Gregori E.Dynamic tuning of the IEEE 802.11 protocol to achieve a theoretical throughput limit [J].IEEE/ACM Transactions on Networking,2000,8(6):785-799.

[9] Haosong G,Younghwan Y.An Energy Efficient MAC Protocol Based on IEEE 802.11 DCF for Wireless Sensor Networks in Port Logistics[C]//Proceedings of High Performance Computing and Communication & 2012 IEEE 9th International Conference on Embedded Software and Systems (HPCC-ICESS),Liverpool.2012:728-733.

[10] Shurman M,Al-Shua’B B,Alsaedeen M,et al.N-BEB:New backoff algorithm for IEEE 802.11 MAC protocol[C]//Proceedings of 2014 37th International Convention on Information and Communication Technology,Electronics and Microelectronics,Opatija.2014:540-544.

[11] Krishnan M N,Shicong Y,Zakhor A.Contention window adaptation using the busy-idle signal in 802.11 WLANs[C]//Proceedings of Global Communications Conference (GLOBECOM),IEEE:Austin,TX,2014:4794-4800.

[12] Yubin X,Minghe H,Ma L,et al.A self-adaptive minimum contention window adjusting backoff algorithm in IEEE 802.11 DCF[C]//Proceedings of Consumer Electronics,Communications and Networks,Yichang,2012:1577-1582.

[13] 何宏,李建东,盛敏,等.一种基于慢退避思想的SD_DCC退避算法及其性能分析[J].计算机学报,2005,28(11):151-158.

[14] Guo W,Xiaofeng Z,Shunliang Mei,et al.A new constrained-send mechanism to enhance the performance of IEEE 802.11 DCF[C]//Proceedings of Communications and Networking in China (CHINACOM).IEEE:Harbin,2011:448-452.

[15] Bianchi G.Performance analysis of the IEEE 802.11 distributed coordination function[J].IEEE Journal on Selected Areas in Communications,2000,18(3):535-547.

A BACK-OFF ALGORITHM BASED ON DYNAMIC SENDING-CONSTRAINED THRESHOLD

Zhang ChangsenChen Pengpeng

(College of Computer Science and Technology,Henan Polytechnic University,Jiaozuo 454000,Henan,China)

In order to improve the binary back-off algorithm of IEEE 802.11 DCF protocol,this paper proposes a dynamic sending-constrained threshold-based back-off algorithm.According to contention degree of sites in networks on the use of channel resources the algorithm sets the dynamic threshold,and appropriately constrains the data sending of part sites.On the one hand,the algorithm does not modify the adjustment mechanism of competition window of binary back-off algorithm but retains its advantages of simplicity and convenience in implementation;on the other hand,it effectively solves the shortcomings of traditional binary back-off algorithm that it directly transmits data without inspecting the network status after the completion of back-off process and thus is prone to cause conflicts.Simulation results demonstrate that this algorithm can improve the saturation throughput and reduce the average access delay.

Back-off algorithmDistributed coordination functionDynamic threshold

2015-05-21。国家自然科学基金项目(51174263)；教育部博士点基金项目(20124116120004);河南省基础与前沿技术研究项目(142300410144)。张长森，教授，主研领域：矿井监控与通信，无线传感器网络。陈鹏鹏，硕士。

TP393.04

A

10.3969/j.issn.1000-386x.2016.09.026