有效提高WLAN 吞吐量的数据帧发送策略

吴大鹏，武穆清，甄岩

(北京邮电大学 宽带通信网实验室，北京 100876)

1 引言

IEEE802.11协议规定了分布式协调功能(DCF,distributed coordination function)为节点提供信道接入[1]，其采用CSMA/CA侦听信道，当数据帧发生碰撞后根据二进制指数退避(BEB,binary exponential backoff)算法计算退避时间，进而执行重传。此机制无法充分利用有限的无线资源[2～4]，其原因主要包含2个方面：首先，当网络负载逐渐增加的时候，共享无线媒介的各个节点处于饱和状态，所发送的数据帧碰撞概率也随之上升，虽然 BEB算法能够通过竞争窗口加倍机制来降低碰撞概率，但是其调整速度较慢，在短时间段内，数据帧碰撞的情况没有明显的缓解；此外，节点成功发送数据帧之后，BEB算法将竞争窗口恢复到最小值，由于没考虑到当前碰撞情况，快速缩减竞争窗口将会导致碰撞概率显著增加。以上2个方面都将浪费无线资源。

减少退避过程中空闲时隙数量或者降低数据帧碰撞次数都能够提高网络的总体性能，而通过减少退避空闲时隙数量来增加网络资源利用率的方法又会增大数据帧的碰撞概率。诸多文献根据上述分析提出了各种退避机制，以被动地解决数据帧碰撞问题，文献[5]提出了一种分布式竞争控制机制，利用数据帧发送前的退避过程来估计网络当前的竞争状态，并根据结果决定退避结束后是否发送该数据分组。该算法在每次数据帧发送成功后立刻将退避寄存器的窗口置为最小竞争窗口，当网络进入高负载状态后，每次发送数据帧均需经历多次碰撞，导致数据帧时延增大，网络吞吐率下降。

文献[6]提出了一种“慢退避”机制用于解决多个节点竞争信道过程中出现的多次碰撞问题，其主要思想是在节点成功发送数据帧后，并不将竞争窗口的数值立即恢复为最小值，而按照固定速度缩减当前竞争窗口。但是该机制没有考虑发送成功后网络当前的竞争状态，进而无法合理地选取下一帧的竞争窗口以避免盲目的发送动作，使得其无法适用于各种网络环境。此外，文献[7～10]均采用被动方式调整竞争窗口，但当网络拥塞程度较高的时候，节点始终处于回退状态，这将导致业务产生的数据分组将会由于缓冲溢出而丢弃，另一方面，当信道处于相对空闲状态的时候，队列中数据帧较少，无法高效地利用当前空闲的网络资源。解决这个问题的关键点在于根据不同的网络状态调整数据分组的发送速率。

区别于各种退避机制，Clausen提出了一种随机发送时间机制[11]从网络层主动地来解决该问题，节点对其负责发送的数据分组进行分类，包括本地业务产生的数据分组和为其他节点转发的数据分组，然后按照不同的方式随机地改变各种数据分组发送到MAC队列的时间，从而有效地降低了数据帧同时发送所导致的碰撞问题。但是与前面所介绍的回退机制类似，其固定调整范围的方式无法适用于不同网络负载情况。

为了更加合理地利用有限的网络资源，本文提出了MAC层自适应退避机制和网络层数据分组发送时间调整的联合优化策略，该机制能够有效地根据网络当前的碰撞情况调整数据分组发送速率，同时还能够根据当前回退阶数调整竞争窗口，根据网络当前竞争状态充分利用网络资源。

2 网络吞吐率分析

若当前共享同一无线媒介的节点数量为 n，则至少有一个节点发送数据帧的概率为 Ptr，如式(1)所示，τ为一个时隙内节点发送数据帧的概率。

节点成功完成数据帧传输的概率为

节点成功传输数据帧概率与节点发送概率之间的关系可以按照图1中所示的各个曲线描述，在此选择了6种节点密度进行考虑。

图1 节点成功传输概率与节点发送概率关系

由Ps的定义和图1可知，碰撞发生过程中，较低的节点数据帧发送概率将会使得发送成功概率增加。

网络的归一化系统吞吐率S定义为单位时隙内传输数据净荷所用的时间与时隙长度的比例，可以按照下面的方式来描述：

其中，Ts和Tc分别为信道由于成功发送以及碰撞所导致的占用时间；E[P]表示平均数据帧长度，δ表示一个时隙所占用的时间，由于δ数值相对较小，则式(3)可以简化为

对于式(4)来说，E[P]、Ts和 Tc都是固定值，因此，网络归一化吞吐率将随Ps变化而单调变化。结合图1和式(2)的结果可知，在碰撞频繁的过程中，降低数据分组的发送概率将能够有效地提升网络吞吐率。

3 自适应回退机制

在检测到数据帧连续碰撞的时候，节点需要快速地增加竞争窗口以有效地避免该数据帧再次碰撞，其增加程度与连续碰撞次数明显相关。因此，在数据帧出现碰撞的时候，按照式(5)调整竞争窗口，其中k表示节点当前的回退阶数，即该数据帧碰撞次数。

如前所述，与标准中规定的数据帧成功传输后的竞争窗口调整策略不同，若当前数据帧在传输过程中连续出现碰撞，则表明共享相同无线媒介的节点数量较大，且多个节点都处于饱和状态，此时，若各个成功发送数据帧节点都将竞争窗口恢复到最小，数据帧的碰撞情况无法得到明显改善，因此，连续碰撞多次的数据帧成功传输之后，各个节点应将竞争窗口维持在较大的范围以有效地降低数据帧碰撞概率，调整方法如式(6)所示，其中m为最大重传次数。

按照上述竞争窗口调整策略，节点竞争窗口的状态转移情况如图2所示，由于基于碰撞感知的竞争窗口增加速度和节点成功传输数据分组后竞争窗口的缩减速度并不相同，因此，为了简洁，只对主要状态进行描述。

4 动态发送时间调整策略

主动调节注入到队列中的数据分组数量能够从根本上提高无线资源利用率，将节点所需要传输的数据分组分为两类：节点本地业务数据分组和为其他节点转发的数据分组，2个类型的数据分组所对应的发送时间偏移量均匀分布在区间[0,Jg]和[0,Jf]，其中Jg和Jf分别为用于调整本地业务数据分组和转发数据分组发送时间的计时器，满足

对于本地产生的数据分组来说，按照式(7)的方式调整其发送间隔，其中Jc为均匀分布在[0,Jg]的数值，Io为原始数据分组间隔。

节点可以获知应用层所产生的数据流情况，其中包括带宽、数据分组长度、数据分组间隔等信息，因此，当碰撞发生的时候，节点需要减小发送速率，而当数据帧成功发送的时候，节点则需要加大发送速率以有效地使用无线资源，为了加快节点的调整速度，采用加性增加乘性减小(AIMD,additive increase multiplicative decrease)的方式，具体如式(8)和式(9)所示。

对于转发数据分组来说，节点无法获得其业务产生数据分组的速率，从而无法计算数据分组之间的间隔，因此，在数据分组转发过程中对其接收到的数据分组采用延迟发送的方式，在区间[0,Jf]上均匀地选取具体的延迟时间数值。与发送本地数据分组类似，当转发的数据分组出现碰撞的时候，节点需要降低其转发速率，否则，增加转发速率。类似地，采用了乘性增加加性减小(MIAD,multiplicative increase additive decrease)的方式来加速节点的调整速度，具体如式(10)和式(11)所示。

5 算法性能分析

文中所提出的基于竞争感知的联合调整(CAA,contention aware adjusting)策略的伪代码如下：

图2 自适应回退机制

对于IEEE 802.11标准中的二进制指数退避算法来说，其复杂度分析过程如表1所示，假设平均重传次数为mBEB。

表1 二进制指数回退机制复杂度分析

由表1结果可知，IEEE802.11标准中所采用的二进制指数退避算法的时间复杂度仅与平均重传次数有关，即O(mBEB)。

对于文献[6]中所提出的EIED算法来说，其时间复杂度分析过程如表2所示，假设平均重传次数为mEIED。

表2 EIED机制复杂度分析

由上述分析过程可知，EIED算法的时间复杂度也仅与平均重传次数有关，即O(mEIED)。

对于本文所提出的基于竞争感知的联合调整策略来说，假设平均重传次数为madaptive，最大重传次数为m，复杂度分析过程如表3所示。

表3 CAA复杂度分析

为了衡量采用了碰撞感知技术之后，节点退避算法对网络吞吐率的改进情况，本文采用二维Markov模型分析稳态条件下的吞吐率。W(t)、b(t)分别为描述节点竞争窗口和退避计数器数值的随机过程，该二维Markov{W(t),b(t)}模型如图3所示，其中p表示数据帧传输过程中的碰撞概率，L为最大重传次数。

最大竞争窗口和最小竞争窗口分别为CWmin和CWmax，当重传次数达到某个数值的时候，竞争窗口将增加至CWmax而不再继续增长，令该数值为m，则BEB退避策略可以按照式(12)进行描述。

而所提出的碰撞感知的节点回退算法可以按照式(13)描述。

则图3所示的状态转移关系可以用下面等式描述：

图3 退避过程的二维Markov链

上述状态转移事件的意义如下：

1) 退避计数器减少；

2) 发送数据帧成功后，新数据帧的计数器需要从退避阶段0开始；

3) 数据帧之间发生碰撞导致发送不成功，调整竞争窗口；

4) 碰撞次数达到最大值，无论数据帧成功发送还是再次碰撞，都直接开始下一个数据帧传输过程。

令bi,k表示稳态分布{i,k}的概率，则有：

由Markov模型归一化条件可知：

经整理可得：

可以获得系统初始状态b0,0的表达式：

任意一个站点发送的概率τ可表示为

当采用BEB算法的时候，则节点发送概率为

因此，两者在相同碰撞概率情况下的节点发送数据帧概率如图4所示。

可见，采用碰撞感知的回退机制之后，节点能够有效地根据碰撞情况调整数据帧发送情况。碰撞发生比较频繁的时候，采用碰撞感知的方法能够有效地降低节点发送数据帧的概率，从而降低碰撞发生次数，达到增加系统吞吐率的目的。可见，所提出的 CAA机制能够在不改变原有网络物理结构以及拓扑关系的情况下，通过更新终端驱动软件，即可在维持原算法复杂度的情况下，实现网络性能的改善。

图4 碰撞概率与传输概率关系

6 网络性能仿真

采用OPNET平台对CAA机制进行了计算机仿真，与文献[9]类似，选取 Jmin为 1ms，Jmax为10ms，仿真场景为1 000m×1 000m，数据分组长度为1 024byte，仿真时间为300s，数据速率为11Mbit/s，其他参数使用标准中推荐的数值，文中以每秒数据分组数量为参数描述网络负载。

如前所述，数据帧碰撞将导致网络资源浪费，因此，碰撞次数是衡量调整机制的重要指标，如图5所示，对于各种网络负载情况来说，CAA机制都能够有效地降低碰撞次数，并且性能改善程度随负载上升而增加，总体来说，相比于BEB算法，CAA机制能够使得整个网络的数据帧碰撞次数降低27.5%，同时也明显优于EIED机制。

图5 碰撞次数

网络吞吐量是衡量资源利用率的有效指标，采用CAA机制之后的网络吞吐量如图6所示，从整体来说，相比于BEB算法，网络吞吐量平均提高30%以上，可见，采用CAA机制能够更加合理地利用网络资源；此外，结果表明，当网络达到饱和之后，增加注入到网络的数据分组数量并不能提高网络吞吐量，同时，CAA机制的性能也优于EIED机制。

图6 网络吞吐量

CAA调整策略能够降低数据帧碰撞次数，对特定数据帧来说，连续发生碰撞的概率小于标准中所使用的 BEB机制，因此，其成功传输的概率也就高于使用BEB机制的情况。仿真结果如图7所示，通过使用 CAA调整策略，网络中分组投递率上升接近13%。

图7 分组投递率

CAA机制采用主动和被动 2种方式调整数据分组发送过程中的相关参数，其在各种网络负载以及节点密度情况下的数据分组平均时延如图8所示，从结果中可知，当网络负载较小时，采用CAA机制对数据分组时延改善程度并不明显，但是当网络负载逐渐增加的时候，相比于EIED机制和BEB机制来说，采用CAA机制能够获得较小的平均时延。

图8 数据分组平均时延

7 结束语

以被动方式调整竞争窗口变化情况无法从根本上改善当前网络中资源竞争情况，文中提出了一种结合主动和被动的数据分组传输过程调整机制，节点根据数据帧碰撞情况被动地调整竞争窗口增加和缩减的速度，同时采用主动的方式，动态地控制进入到节点队列中的数据分组速率。结果表明，该联合调整策略能够有效地提高网络吞吐量，为业务提供更好的服务质量保障。

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

[2] GUANG L,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.

[3] 黎宁,史诚光.一种802.11DCF性能分析的简单方法[J].电子科技大学学报,2006,35(3): 339-342.LI N,SHI C G.An easy way for 802.11 DCF performance analysis[J].Journal of University of Electronic Science and Technology of China,2006,35(3): 339-342.

[4] SAKURAI T,VU H L.MAC access delay of IEEE 802.11 DCF[J].IEEE Transactions on Wireless Communications,2007,6(5): 1702- 1710.

[5] BONONI L,CONTI M.Runtime optimization of IEEE 802.11 wireless LANs performance [J].IEEE Transactions on Parallel and Distributed Systems,2004 ,15(1):66-80.

[6] SONG N,KWAK B,SONG J,et al.Enhancement of IEEE 802.11 distributed coordination function with exponential increase exponential decrease backoff algorithm[A].Proceedings of Vehicular Technology Conference[C].2003.2775-2778.

[7] XIAO Y,LI F H,WU K.On optimizing backoff counter reservation and classifying stations for the IEEE 802.11 distributed wireless LANs[J].IEEE Transactions on Parallel and Distributed Systems,2006,17(7):713 – 722.

[8] 朱颖,夏海轮,武穆清.一种最小竞争窗口自适应调整的802.11退避算法[J].电子与信息学报,2008,30(4): 961-965.ZHU Y,XIA H L,WU M Q.A self-adaptive minimum contention window adjusting backoff algorithm in IEEE 802.11 DCF[J].Journal of Electronics and Information Technology,2008,30(4): 961-965.

[9] 王朝翔,苗建松,丁炜.模糊逻辑控制的 MAC协议[J].北京邮电大学学报,2007,30(6): 131-134.WANG Z X,MIAO J S,DING W.A fuzzy logic MAC protocol[J].Journal of Beijing University of Posts and Telecommunications,2007,30(6): 131-134.

[10] IBRAHIM M,ALOUF S.Design and analysis of an adaptive backoff algorithm for IEEE 802.11 DCF mechanism[J].Lecture Notes in Computer Science,2006,3976:184-196.

[11] CLAUSEN T,DEARLOVE C.Jitter considerations in mobile ad hoc networks [EB/OL].http://www.ietf.org/rfc/rfc5148.txt.2008-07-10.