非饱和无线局域网环境中Idle Sense 机制研究

马治杰，赵庆林，刘 莹

MA Zhijie,ZHAO Qinglin,LIU Ying

澳门科技大学 资讯科技学院，澳门999078

Faculty of Information and Technology,Macau University of Science and Technology,Macau 999078,China

1 引言

IEEE 802.11 DCF（Distributed Coordination Function，分布式协调功能）[1]是无线局域网中最常用的媒体访问控制机制，它采用CSMA/CA（Carrier Sense Multiple Access/Collision Avoidance，带有冲突避免的载波侦听多路访问）原理和Exponential Back-off（指数后退）算法来减少分组发送冲突。然而，在饱和（每个节点时刻有分组发送）的无线局域网中，随着节点数目的增多，DCF机制存在吞吐量迅速降低和延时迅速增大两个问题。

目前，已有很多相关工作对DCF机制进行了改进（如参考文献[2-9]）。Idle Sense（文献[2]）是一种非常著名的MAC 层访问机制，它在饱和环境中表现出了比IEEE 802.11 DCF更好的性能。在该机制中，每个节点将不执行指数后退算法，而是根据相邻两次传输之间的平均连续空闲时隙数与最优空闲时隙数的大小关系，用AIMD（Additive Increase Multiplicative Decrease，和式增加积式减少）算法[10]动态地调整CW（Contention Window，竞争窗口），使CW最终收敛到一个最优值，从而达到提高吞吐量和降低延时的目的。

然而，Idle Sense机制是在饱和环境中提出的。根据本文的实验结果发现，Idle Sense机制并不适用于更为实际的非饱和无线环境中。因此，本文提出了新的Idle Sense 机制，使其既适用于饱和环境，又适用于非饱和环境。最后，本文通过NS-2（Network Simulator Version 2）验证了新Idle Sense机制的有效性。

2 原Idle Sense 机制分析

2.1 Idle Sense 原理

定义ni为相邻两次传输之间的连续空闲时隙数，navg为相邻两次传输之间的平均连续空闲时隙数；nopt为最优连续空闲时隙数。

Idle Sense 原理可总结为：每个节点先根据ni计算出navg，然后根据navg与nopt的大小关系，用AIMD 算法动态的调整CW，使之最终能收敛到一个最优值。AIMD 算法可简单归纳如下：

即当navg＞nopt时，CW将减小，反之CW将增大。其中α和ε为固定系数。

2.2 Idle Sense 在非饱和环境中存在的问题

Idle Sense机制在非饱和环境中存在两个问题。

问题1在饱和环境中计算出来的nopt不能用于非饱和环境中。

在饱和环境中，β=1。但是在非饱和环境中，β≠1。所以，Idle Sense 机制在饱和环境中计算出来的nopt不能用在非饱和环境中。

问题2CW在非饱和环境中会递减为零。

在非饱和环境中，由于节点获得的空闲时隙数一直比较大，所以计算出的navg也比较大，且navg始终大于在饱和环境中计算出来的nopt。最终，在通过AIMD 算法调节CW时，CW会一直递减，直到为零。图1 画出了一个节点的CW在饱和（图1（a））与非饱和（图1（b））环境中的变化。其中图1（b）显示了随着传输次数的增多，CW最终递减为零的现象。

上述问题恶化了Idle Sense机制在非饱和情况下的性能。图3 和图4 分别比较了Idle Sense 和DCF 的吞吐量和延时。由这两幅图可知，当流量强度ρ较小（比如0.2 ＜ρ＜0.3）时，Idle Sense 的吞吐量低于DCF，而延时高于DCF。

图1 一个节点在饱和（a）与非饱和（b）环境中的CW 对比

3 新Idle Sense机制分析

3.1 ni 的计算

在非饱和环境中，因为缓冲区中很可能没有要发送的分组，此时系统将一直处于空闲状态，所以本文提出新的机制来统计该空闲时段。

新Idle Sense 机制将通过连续重启Back-off 计时器的方法来记录连续空闲时隙数ni。所以ni的计算方法可表示为：

3.2 新Idle Sense 机制

针对原Idle Sense 机制在非饱和环境中存在的两个问题，新Idle Sense 机制做了如下两方面的改进（如图2中的两个虚线框所示）。

图2 显示了新Idle Sense 机制的执行过程。在该机制中，每个节点在执行完maxtrans次之后，将更新平均连续空闲时隙数navg，然后再根据AIMD 算法动态地调整CW。其中两处改进如下。

改进1nopt的取值（参见图2 中的第一个虚线框）。

在新Idle Sense 机制中，每个节点通过比较其分组到达率λ与一个临界值λ′的大小关系来区分饱和与非饱和环境。根据参考文献[13-14]，λ′的表达式为：其中σ表示空闲时隙长度，Tc表示发送分组的冲突时间，Tc可根据文献[13]中的表1 来计算。

如果λ≥λ′，则说明该节点处于饱和状态。此时，新机制会选择nopt_sat作为最优空闲时隙数nopt。nopt_sat可通过公式和计算：

其中公式中的ς是公式的根。

如果λ＜λ′，则说明该节点处在非饱和状态。此时，为了避免由于存在过多的空闲时隙而导致CW连续递减，新机制会选择比nopt_sat更大的nopt_nonsat来作为非饱和情况下的最优空闲时隙数。本文根据多次实验结果观察可知，当nopt_nonsat为30 时，能适应于大多数情况。因此，本文采用nopt_nonsat=30 作为最优空闲值。

改进2避免CW递减为0（参见图2的第二个虚线框）。

为了避免出现图1（b）的情况，新Idle Sense 机制在每次动态调整CW之后，判断当前CW值是否为零。如若CW已经为零，则将其重新赋值为当前系统内节点数目N，即CW=N。从而使得CW在下次可以根据该值进行动态调节，调节方法如图2 中两个虚线框中间所示。本文的模拟结果显示，在非饱和环境中，当CW=N时，新机制的性能最优。

相对于原Idle Sense机制而言，新Idle Sense机制仅仅是在原机制算法上加了两个判断语句（详见图2 中的两个虚线框），其时间复杂度是O(1)，即新增加的额外开销可以忽略。

4 模拟结果

本章将通过NS-2 软件（版本2.28）（http：//www.isi.edu/nsnam/ns/ns-build.html）对新Idle Sense 机制在吞吐量和延时两方面进行模拟验证。

表1 802.11b 标准参数

4.1 吞吐量

图3表示执行标准DCF机制、原Idle Sense和新Idle Sense 机制后所得的吞吐量模拟结果。横坐标表示分组流量强度ρ，纵坐标表示吞吐量。其中ρ的表达式为：

其中B表示系统总带宽。

图3 三种机制的吞吐量比较

根据模拟结果可以看出，当流量强度较小（ρ＜0.3，即非饱和情况）时，由于原Idle Sense 在非饱和环境中存在的问题，使得原Idle Sense 机制获得的吞吐量最低，且低于标准DCF 获得的吞吐量。而改进后的新Idle Sense 机制明显地提高了吞吐量，且其获得的吞吐量和DCF 的吞吐量相同。

当流量强度较大（ρ＞0.3，即饱和情况）时，由于新Idle Sense 机制执行方法和原Idle Sense一样，所以两者获得了相等的吞吐量，且均高于标准DCF 机制。

4.2 延时

图4表示执行标准DCF机制、原Idle Sense和新Idle Sense机制后所得到的延时模拟结果，横坐标表示分组流量强度，纵坐标表示分组发送延时。

图4 三种机制的延时比较

根据模拟结果可以看出，当流量强度较小（ρ＜0.3，即非饱和情况）时，原Idle Sense 机制获得的延时最高，且高于标准DCF 获得的延时。而改进后的新Idle Sense机制降低了延时，并几乎与DCF 获得的延时相同。

当流量强度较大（ρ＞0.3，即饱和情况）时，两种Idle Sense 机制获得同样的延时，且均小于标准DCF 机制的延时。

5 结束语

本文针对原Idle Sense机制在非饱和环境中存在的问题，提出了新的Idle Sense 机制。新机制不仅保留了原机制在饱和环境中高吞吐量和低延时的特点，也提高了原机制在非饱和环境中的吞吐量，同时也降低了延时。本文提出的新Idle Sense 机制增强了其在无线局域网中的实用性。

[1] IEEE 802.11 WG.Standard 802.11 Part 11：Wireless LAN medium access control and physical layer specifications[S].New York：IEEE，2003.

[2] Heusse M，Rousseau F，Guilier R，et al.Idle sense：an optimal access method for high throughput and fairness in rate diverse wireless LANs[C]//SIGCOMM’05，2005，35（4）：121-132.

[3] Cali F，Conti M，Gregori E.Dynamic tuning of the IEEE 802.11 protocol to achieve a theoretical throughput limit[J].ACM/IEEE Trans on Networking，2000，8（6）：785-799.

[4] Ma H，Li H，Zhang P，et al.Dynamic optimization of IEEE 802.11 CSMA/CA based on the number of competing stations[C]//Proc of ICC’04，2004，1：191-195.

[5] Ni Q，Aad I，Barakat C，Turlette T.Modeling and analysis of slow CW decrease for IEEE 802.11 WLAN[C]//2003，2：1717-1721.

[6] Song N O，Kwak B J，Song J，et al.Enhancement of IEEE 802.11 distributed coordination function with exponential increase exponential decrease backoff algorithm[C]//Proc of VTC，2003，4：2775-2778.

[7] Barghavan V，Demers A，Shenker S，et al.MACAW：a media access protocol for wireless LAN’s[C]//Proc of ACM SIGCOMM，1994，24（4）：212-225.

[8] Ho T S，Chen K C.Performance analysis of IEEE 802.11 CSMA/CA medium access control protocol[C]//PIMRC，Seventh IEEE International Symposium，1996，2：407-411.

[9] Heusse M，Rousseau F，Berger-Sabbatel G，et al.Performance anomaly of 802.11b[C]//Proc of INFOCOM，2003，2：836-843.

[10] Chiu D，Jain R.Analysis of the increase and decrease algorithms for congestion avoidance in computer networks[J].Journal of Computer Networks and ISDN，1989，17（1）：1-14.

[11] Bianchi G.Performance analysis of IEEE 802.11 distributed coordination function[J].Selected Areas in Communications.2000，18（3）：535-547.

[12] Ramaiyan V，Kumar A，Altman E.Fixed point analysis of single cell IEEE 802.11e WLANs：Uniqueness，multistability and throughput differentiation[J].ACM/IEEE Trans on Networking，2008，16（5）：1080-1093.

[13] Zhao Qinglin，Tsang D H K，Sakurai T.A novel CAC scheme for homogeneous 802.11 networks[J].Trans on Wireless Communications，2010：1168-1174.

[14] Zhao Qinglin，Tsang D H K，Sakurai T.A simple criticalload-based CAC scheme for IEEE 802.11 DCF networks[J].ACM/IEEE Trans on Networking，2011 19（5）：1485-1498.