简述移动Ad Hoc网MAC协议的改进算法

　　20世纪90年代中期，随着一些技术的公开，移动Ad Hoc开始引起人们的关注，成为移动通信领域的一个研究热点Ad-Hoc（点对点）模式：ad-hoc模式就和以前的直连双绞线概念一样，是P2P的连接，所以也就无法与其它网络沟通了。一般无线终端设备像PMP、PSP、DMA等用的就是ad-hoc模式。 在家庭无线局域网的组建，我想大家都知道简单的莫过于两台安装有无线网卡的计算机实施无线互联，其中一台计算机连接Internet就可以共享带宽。如下图所示，一个基于Ad-Hoc结构的无线局域网便完成了组建。为了提高网络性能，在无线环境下的多址接入冲突避免MACAW（MACA for Wireless）协议中，BHARGHAVAN建议使用RTS-CTS-DS-DATA-ACK的消息交换机制发送数据分组。MACA（multiple access with collision avoidance ）避免冲突的多路访问，其基本思想是发送方刺激一下接收方，让他输出一个短帧，因此，接收方附近的站可以检测到该帧，从而在接下去的数据帧（较大）传输过程中它们不再发送数据了。

　　Ad hoc网络的前身是分组无线网（Packet Radio Network）。对分组无线网的研究源于军事通信的需要，并已经持续了近20年。早在1972年，美国DARPA（Defense Advanced Research Project Agency）就启动了分组无线网（PRNET,Packet Radio NETwork）项目，研究分组无线网在战场环境下数据通信中的应用。项目完成之后，DAPRA又在1993年启动了高残存性自适应网络（SURAN,SURvivable Adaptive Network）项目。研究如何将prnet的成果加以扩展，以支持更大规模的网络，还要开发能够适应战场快速变化环境下的自适应网络协议。1994年，DARPA又启动了移动信息系统（GloMo,Globle Mobile Information Systems）项目。在分组无线网已有成果的基础上对能够满足军事应用需要的、可快速展开、高抗毁性的移动信息系统进行全面深入的研究，并一直持续至今。1991年成立的IEEE802.11标准委员会采用了“Ad hoc网络”一词来描述这种特殊的对等式无线移动网络。

　　1 移动Ad Hoc网MAC协议退避算法

　　1.1二进制指数退避算法

　　退避算法就是网络上的节点在发送数据冲突后，等待一定时间后再发，等待时间是随指数增长主要用于CSMA的冲突分解用二进制指数退避可以取得较好的分解效果。在共用信道的情况下，当冲突发生以后，每个节点都进行一个随机时延t,0<t<Tt服从（0~T）上的以二为底的指数分布。

　　二进制指数退避算法是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退避算法能在很大程度上提高信道接入的公平性。