摘 要：着重分析了影响公平性的退避算法，对用于无线局域网的乘性增加、线性减少（MILD）退避算法进行了改进。运用NS2仿真工具对改进算法后的信道接入的公平性进行了分析。结果表明，与BEB算法相比，改进后的MILD退避算法能大幅度提高信道接入的公平性。
关键词：移动Ad Hoc网络；MAC协议；退避算法

　　20世纪90年代中期，随着一些技术的公开，移动Ad Hoc开始引起人们的关注，成为移动通信领域的一个研究热点。PHIL K在其业余分组无线电的研究中提出了一种用于单信道网络的信道接入控制协议——多址接入冲突避免协议MACA(Multiple Access with Collision Avoidance) [1]，它使用RTS/CTS握手机制，其目的是要解决移动Ad Hoc网络中的隐藏终端问题。为了提高网络性能，在无线环境下的多址接入冲突避免MACAW(MACA for Wireless)[2]协议中，BHARGHAVAN建议使用RTS-CTS-DS-DATA-ACK的消息交换机制发送数据分组。相比MACA而言，MACAW增加了DS和ACK 2个控制分组。通过使用ACK分组，尽量使节点在MAC层就快速重传冲突的分组，而不需要在传输层进行重传。为了进一步改善信道接入的公平性，学者们还在MACAW中引入了乘性增加、线性减少MILD(Multiplicative Increase Linear Decrease)退避算法。
1 移动Ad Hoc网MAC协议退避算法
1.1二进制指数退避算法
 　　二进制指数退避算法是IEEE 802.11 MAC协议中所采用的。该算法可以用以下2个函数来表述：
　　inc_cw()
　　{
　　cw_ = (cw_ << 1) + 1;
　　if(cw_ >CWMax)
　　cw_ = CWMax;
　　}
　　rst_cw()
　　{
　　cw_ = CWMin;
　　}
　　(1)当节点发送数据成功时，调用rst_cw( )，将竞争窗口cw_调整到最小值CWMin。
　　(2)当节点发送的数据发生冲突时，调用inc_cw( )函数，将竞争窗口cw_加倍。当竞争窗口cw_超过最大值CWMax时，将竞争窗口cw_设置为CWMax。
　　(3)当节点连续7次发送数据失败时，也调用rst_cw( )，将竞争窗口调整到最小值CWMin。
　　BEB算法将带来严重的不公平性，因为在节点一次发送成功后，将其竞争窗口调整为最小值CWMin，而其他发送数据失败的节点的竞争窗口值变为原来的2倍，使竞争窗口值变得比较大。在后续的竞争中，竞争窗口小的节点在竞争中获胜的可能性大。获胜后，竞争窗口又降为最小，其他发送失败的节点的竞争窗口再次增大，获胜的节点更有优势，而其他节点接入信道的概率很小。
1.2 乘性增加、线性减少（MILD）退避算法
　　为了改进IEEE 802.11 MAC协议中BEB算法的公平性问题，在MACAW中提出了乘性增加、线性减少退避算法MILD。该算法对BEB算法进行了修改，算法程序伪代码如下：
　　inc_cw()
　　{
　　cw_ = a*cw_ ;
　　if(cw_ >CWMax)
　　cw_ = CWMax;
　　}
　　rst_cw()
　　{
　　cw_= cw_-b;
　　if（cw_< CWMin）
　　cw_ = CWMin;
　　}
　　其中，a和b是2个可调节的参数。在MILD退避算法中，一次发送成功后，竞争窗口减小b，若取适当的b值，则竞争窗口cw_不会大幅度减小。当节点发送的数据发生冲突时，竞争窗口增加a倍，若a取值合理，则竞争窗口cw_也不会急剧增加。在参考文献[2]中，a和b的值分别是2和1，即倍数增加，线性减少，并在无线局域网环境下进行了仿真。仿真结果表明，使用MILD算法比使用BEB算法的公平性要好。参考文献[3] 在无线局域网环境下对MILD进行了进一步研究，结果表明，MILD在网络负载很重的情况下，性能比BEB算法要好很多。但当网络的负载很小时，MILD的性能不如BEB算法。这是因为它需要很长的时间才能从由偶然的碰撞引起的退避中恢复过来，而且，当激活的节点数量从很多急剧减少时，由于MILD对竞争窗口是线性减小的，不能很快地把竞争窗口cw_调整到最小，从而引起不必要的退避。最极端的情况为：当CWMin=31， CWMax=1 023时，用MILD算法最多要经历992次成功发送，竞争窗口cw_才能达到CWMin，而BEB算法只经历一次成功发送，竞争窗口cw_就可达到CWMin。当信道竞争较激烈时，各节点在发生冲突时按倍数增加退避时间，一段时间后，各节点的退避计数器值都较大，如果这时某个新节点加入网络，因为新加入的节点不知道信道的竞争情况，它的退避计数器的值会比较小。这样竞争信道的各节点的退避计数器值就有了较大的差异，严重的不公平现象就会产生。
2 乘性增加、线性减少MILD退避算法的改进
　　在MILD退避算法中，当节点发送数据失败后，竞争窗口变为原来的a（a=2）倍；当节点发送数据帧成功后，竞争窗口减小b（b=1）。成功发送数据的节点的竞争窗口比发送失败的节点的竞争窗口小得多，进而造成了信道接入的不公平性。为了改善公平性，应把成功发送数据的节点的竞争窗口增大，让发送失败的节点有更多的机会接入信道。根据这个思想，对MILD退避算法做出了改进，以达到节点公平地共享信道的目的。
　　在改进后的算法中，MILD算法中乘性增加部分保持不变，线性减少改为线性增加，当竞争窗口超过最大值时，把竞争窗口置为最小。本文把这种算法称为改进的乘性增加、线性减少退避算法。改进后的伪代码如下：
　　inc_cw()
　　{
　　cw_ = a*cw_ ;
　　if(cw_ >CWMax)
　　cw_ = CWMax;
　　}
　　rst_cw()
　　{
　　cw_= cw_+b;
　　if（cw_> CWMax）
　　cw_ = CWMin;
　　}
3仿真结果分析
　　在MAC协议研究中，信道接入的公平性是一个最常用的指标。公平性指数是衡量节点之间是否公平地共享信道的一个重要标志，在参考文献[4]中使用了改进的公平性指数IFI（Improved Fairless Index），表示最大链路的吞吐量Throughputmax与最小链路的吞吐量Throughputmin之差与总的吞吐量Throughputtotal的比值，其表达式为：
　　　

　　IFI的值界于0与1之间。理想情况下，每条链路有相同的吞吐量，这时IFI=0；如果一个节点占据共享信道，而其他节点不能接入信道，则IFI=1，这是最不公平的情况。IFI越小，则所获得的信道接入公平性越高。在本文中，采用式(1)来计算公平性。
　　仿真拓扑采用参考文献[5]中所使用的线性拓扑，如图1所示。节点之间的间隔为150 m，在彼此的通信范围（250 m）之内，在节点A、B之间，C、D之间分别有一条承载于UDP上的CBR流。假定节点A在0 s的时刻向节点B发送CBR流，节点C也在0 s的时刻向节点D发送CBR流，仿真时间为100 s，包的大小设置为1 000 B，信道速率为2 Mb/s。

　　由于MILD退避算法的参数可以调整，在仿真中，取a=2、b=1和a=2、b=2进行仿真，结果如图2所示。

　　从图2可知，与BEB算法相比，改进后的I-MILD算法在链路负载较高的情况下，可大幅度提高信道接入的公平性，且b=2时的公平性比b=1时的公平性好，这是因为节点发送数据成功后，把竞争窗口增大了，减小了与发送失败节点的竞争窗口的差距，从而使得节点之间能够公平地竞争信道。
　　本文对改进后的I-MILD退避算法进行了仿真，并适当调整了I-MILD算法的参数，与采用BEB退避算法相比， 采用I-MILD退避算法能在很大程度上提高信道接入的公平性。而且此项改进是在BEB退避算法的基础上进行的，不用添加额外的硬件，实现简单，运用灵活，具有较高的实用价值。
参考文献
[1] PHIL K. MACA-A new channel access method for packet  Radio.ARRL/CRRL Amateur Radio 9th computer Networking  Conference1990:134-140.
[2] BHARGHAVAN V, DEMERS A, SHENKER S.et al. MACAW: a media access protocol for wireless LANs. ACM Sigcomm'94, 1994.
[3] SONG N O. KWAK B J. SONG J. et al.Enhancement of IEEE 802.11 distributed coordination function with exponential increase exponential decrease backoffAlgorithm.Vehicular Technology Conference(VTC).2003(4):22-25.
[4] WUChuan Xia, FENGJun Huan,FAN Ping Zhi.On a new  queue backoff fair algorithm for Ad Hoc Networks. Proceedings of IEEE PDCAT'2003，2003:335-339.
[5] 李云,陈前斌,隆克平,等.无线自组织网络中TCP稳定性分析及改进.软件学报,2003,14(6):1178-1186.