摘 要：著重分析了影響公平性的退避算法，對用于無線局域網的乘性增加、線性減少（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.