一种有效降低冲突概率的CSMA/CA退避算法

万小博，谭国平，马赛赛

（河海大学 计算机与信息学院，江苏 南京 210000）

802.11 是IEEE制定的一个无线局域网标准[1]，主要用于解决办公室局域网和校园网中用户终端的无线接入，该协议有802.11a、802.11b、802.11g等版本。

由于WLAN工作在ISM频段，此频段是不受保护的开放频段，随着时间的推移，会有越来越多的终端要求同时接入WLAN，而且，也会有其他系统的终端会工作在这个频段上，如LTE D2D通信系统[2]、Adhoc移动自组网通信系统[3]等。如此多的终端、各种不同的系统同时通信，竞争有限的无线资源，势必会引起严重的系统内部与系统间冲突。

CSMA/CA作为一个成熟运用的机制，人们对它进行了很多方面的研究，有基本原理方面的[4],也有性能分析方面的[5-6]。并且也提出了许多的优化方案来提高系统性能，如根据终端流量动态调整竞争窗口[7]、基于时槽机制的改进算法、基于优先级的改进，同时也有一些从硬件方面提出的改进,这些方法都很好的改善了系统的性能。

与以前研究不同，本文提出了一种新型的改进CAMA/CA机制的退避算法。经过仿真分析证明，此方法能够有效的降低系统冲突，提高系统容量。

1 IEEE 802.11 MAC 协议

在无线局域网中，同时进行通信的终端设备很多，会存在资源竞争的问题。这个问题在IEEE 802.11MAC协议里通过带冲突避免的载波侦听多路访问机制(CSMA/CA)得到了解决，其基本流程如图1所示。

图1 CSMA/CA流程示意图Fig. 1 CSMA/CA flow diagram

一个终端设备在传输数据之前，它需要首先侦听信道，如果信道空闲且经过一个分布式协调帧间间隔（DIFS）后，信道仍然空闲，则该站点开始传输数据。如果侦听到信道忙，那么站点就一直侦听信道，直到空闲且持续空闲DIFS时间后，开始执行一个二进制的指数退避机制，通常称为竞争窗口。然后侦听信道，如果信道空闲，则退避计数器减1，直到减为0时，开始传输数据；如果侦听到信道忙，那么退避计数器就挂起，直到信道空闲且持续DIFS时间长度后，计数器重新开始递减。

2 避免冲突的改进的CAMA/CA机制

2.1 原协议存在的问题

当ISM频段上引入更多的设备和其他的系统后，其他系统设备和WLAN设备共享无线局域网信道的一个可行方法就是，所有设备均使用802.11的MAC机制去竞争信道。该方法虽然简单，但是在站点多，业务量大的情况下，较多的帧间间隔和较大的竞争窗口容易导致整体效率低下，另外这种直接的方法也很难保证两个系统间的公平性和频谱资源利用率最大化。

当众多的终端进行通信时，在随机退避时间的选择上，选择相同退避时间的终端的概率会增加，当几个终端的退避时间同时归零时，它们会同时接入信道，进而导致通信失败。所以，为了避免通信的失败，应尽量让不同的设备选择不同的退避时间。

图2 传统的CSMA/CA退避机制Fig. 2 Traditional mechanism of CSMA/CA

2.2 改进方法

如图2所示，在一个用户完成通信后，WLAN用户1、2、3同时检测到信道空闲，并进入退避阶段。为表述的更加清楚，假设这3个用户通过传统的CSMA/CA机制随机选取一个相同的值作为退避时间。此时，这3个用户将不可避免的发生竞争冲突。为了避免冲突，可适当改进CSMA/CA机制。

保持WLAN用户2的退避时间不变，而用户1和3通过退避时间偏移量来调整退避时间。假设在WLAN用户1从（0,CW-1）随机选取一个值后，将减Tslot-t长度的时间作为该用户当前的退避时间，而WLAN用户2从（0,CW-1）随机选取一个同样的值后，将加t(0＜t＜Tslot)长度的时间作为该用户当前的退避时间，如图3所示。

图3 改进的CSMA/CA退避机制Fig. 3 Improved mechanism of CSMA/CA

在T时刻，WLAN用户1的退避计数器减为零，同时检测到信道空闲，则WLAN用户1将发送RTS帧占用信道实现通信。经过一段很短的传输时延后，WLAN用户2与3将收到用户1发送的RTS帧，同时将信道状态信息标志为忙，并挂起退避计数器直到WLAN用户1完成传输。在WLAN用户1完成信息传输并等待一个DIFS时间后，WLAN用户2和3重新开始退避计数，此时WLAN用户2的退避时间比WLAN用户3的退避时间短，所以WLAN用户2将优先接入信道完成通信。

通过这样一个对退避时间的简单处理，发生在这3个用户之间的竞争冲突已完全被避免。除此之外，由于选取的退避时间偏移量t满足0＜t＜Tslot，所以此方法只有在多个WLAN用户选取了相同退避时间的情况下起作用。换句话说，当WLAN用户选取退避时间不同时，此方法不会对其竞争过程产生任何影响。因此，除了少量的信令开销外，不会对原有系统带来任何不利的影响。

2.3 时间偏移量t的选取

首先，将通信终端分为多个小组，并给一个小组分配一个唯一且固定的退避时间偏移量ti。不失一般性，假设将通信终端分为L个小组，每个小组分配一个退避时间偏移量ti(1≤i≤L)，同时确保每个退避时间偏移量是唯一的，即ti≠ tj（∀ i, j∈ [1,L]&i≠ j）。

在每一组中用户都可以随机选择推迟一个时间偏移量t或者提前一个时间偏移量t’。为了保证各个用户组之间不会发生碰撞，需确保 t+t’=Tslot(t≠ 0&t’≠ 0)。

其中，（t+t’=Tslot(t≠ 0&t’≠ 0)是十分必要的。假设用户平均分为3组，如图4所示，并且定义退避的起始时间为t0，每一组的退避时间偏移量分别设为1/4Tslot，2/4Tslot,和3/4Tslot。现有第2组的两个用户A和用户B通过传统CSMA/CA机制选取的随机退避时间相同，为t3-t0。根据改进的CSMA/CA机制，用户A和B将根据优先级选择提前或推迟一个时间偏移量。假设用户A提前一个时间偏移量t’，而用户B推迟一个时间偏移量t。显然，如果无法保证（t+t’=Tslot&t≠0&t’≠0)，那么这两个用户就很有可能会与其他组的用户发生竞争冲突。不妨设t=2/4Tslot,t’=1/4Tslot,那么经改进的CSMA/CA机制处理后，用户B最终的时间为t3-t0+2/4Tslot（即图4中的‘8’点），而用户A最终的退避时间为t3-t0-1/4Tslot（即图4中的‘6’点），这时用户A已经属于第3组。要使用户A仍然属于第2组，而不影响其他组用户的资源竞争，需确保t’的取值必须为Tslot-t，即t’=Tslot-t。可见，这个条件（t+t=Tslot&t≠0&t’≠0)是用户分组方法成败的关键，必须得到满足。

图4 用户分组方法举例Fig. 4 Example of user grouping method

如图4所示，部分用户组只能在整数倍slot time时刻（例如t1, t2, t3）接入信道，例如图中的‘a’、‘b’、‘c’点；而部分用户组只能非整数倍slot time时刻接入信道，例如第1组只能在 ‘1’、‘4’、‘7’点接入信道，第2组只能在‘2’、‘5’、‘8’点接入信道，第3组只能在‘3’、‘6’、‘9’点接入信道，这相当于将总的通信终端数量减少了一倍。很显然，通过这种方法很好解决了系统内部冲突的问题。而且如果把不同的用户组用于不同的通信系统，通过这种分组方法，不仅避免了系统内的竞争冲突，同时也很大程度上减小了系统间的碰撞概率。这种方法可以把原本因碰撞而浪费的大量频带资源利用起来，所以可以很大程度上提升频谱利用率。

从理论上来讲，用户分组越多，带来的性能增益也越大。但是，过多的分组可能引发不可预测的后果，所以建议用户组分组不宜过多。

3 仿真分析

为了评估所提出的改进方案的性能，我们进行了仿真试验。主要用到的仿真参数如表1所示。所有的仿真都是在系统为饱和的条件下进行的，并且假设包错误率为0%。

表1 主要仿真参数Tab.1 Main simulation parameters

图5 冲突概率的比较Fig. 5 Comparison of collision probability

图5比较了传统方案和改进方案之间的碰撞概率。从图中可以看出，改进的方案有效的降低了整个系统的碰撞概率。随着用户数量的增加，系统的碰撞概率总是呈上升趋势的。但是我们也可以看出，随着用户数量的增加，两条曲线的距离有增大的趋势，这说明在用户数量较多的时候，本方案可以更加有效的降低系统的碰撞概率。

图5 冲突概率的比较Fig. 5 Comparison of collision probability

图6比较了两种方案下的系统的吞吐率。由于本方案有效的降低了系统的碰撞概率，所以其系统吞吐率相对于传统方案有了明显的提升。由于碰撞概率随着用户数量的增加而上升，所以吞吐率随着用户数量的增加而降低，从图中可以看到，与原有方案相比，本方案在用户数量较多时，吞吐率下降程度比传统方案要小很多。

4 结 论

随着入网需求的不断攀升，众多的设备如何能够有效的和公平的竞争有限的无线资源，这是运行在ISM频段的各种系统的主要问题之一。在标准的CSMA/CA协议中，各种设备，不管是相同系统的还是不同系统的，都是按照统一的竞争机制去竞争资源。这往往会导致严重的系统冲突和系统间不公平。

文中提出了一种改进的CSMA/CA机制，通过修改相同的随机退避时间，把可能发生的系统冲突降低。并且提出了用户分组的想法，并且可以在WLAN系统中引入优先级的概念。通过仿真分析可以看到本方法可以有效的避免系统冲突，提高系统容量。

[1] ANSI/IEEE Std.802.11.Wireless LAN Medium Access Control(MAC) and Physical Layer (PHY) specifications[S].1999.

[2] 徐同刚. D2D通信系统的工作模式的选择研究[D].南京:南京邮电大学,2013.

[3] 王付彩.多信道无线Adhoc网络协议设计与研究[D].长沙:国防科学技术大学,2011.

[4] 聂世群,田伟莉.IEEE802.11MAC层CSMA/CA机制的分析与研究[J].内江科技,2007(6):102-103.NIE Shi-qun,TIAN Wei-li. Analysis and research of IEEE802.11 MAC layer CSMA/CA mechanism[J].Neijiang Technology,2007(6):102-103.

[5] 黄仁.非时隙CSMA/CA性能分析与研究[J].计算机工程与应用,2009,45(7):108-110.HUANG Ren.Analysis and research of the performance of the unsoltted CSMA/CA[J]. Computer Engineering and Application,2009,45(7):108-110.

[6] 常大为.基于IEEE802.15.4的CSMA/CA性能分析与研究[J].电信工程技术与标准化,2006(1):28-32.CHANG Da-wei. Analysis and research of performance of CSMA/CA based on I EEE802.15.4[J].Telecommunication Engineering Technology and Standardization, 2006(1):28-32.

[7] 周林.IEEE802.15.4MAC协议CSMA_CA优化算法研究[J].广东通信技术,2012(2):66-69.ZHOU Lin.Research of optimization algorithm of IEEE802.15.4 MAC CSMA_CA protocol[J]. Guangdong Communication Technology,2012(2):66-69.