摘 要：著重分析了影響公平性的退避算法,，對用于無線局域網(wǎng)的乘性增加,、線性減少（MILD）退避算法進(jìn)行了改進(jìn)。運(yùn)用NS2仿真工具對改進(jìn)算法后的信道接入的公平性進(jìn)行了分析,。結(jié)果表明,，與BEB算法相比，改進(jìn)后的MILD退避算法能大幅度提高信道接入的公平性,。
關(guān)鍵詞：移動Ad Hoc網(wǎng)絡(luò),；MAC協(xié)議；退避算法

　　20世紀(jì)90年代中期,，隨著一些技術(shù)的公開,，移動Ad Hoc開始引起人們的關(guān)注，成為移動通信領(lǐng)域的一個研究熱點(diǎn),。PHIL K在其業(yè)余分組無線電的研究中提出了一種用于單信道網(wǎng)絡(luò)的信道接入控制協(xié)議——多址接入沖突避免協(xié)議MACA(Multiple Access with Collision Avoidance) [1],，它使用RTS/CTS握手機(jī)制，其目的是要解決移動Ad Hoc網(wǎng)絡(luò)中的隱藏終端問題,。為了提高網(wǎng)絡(luò)性能,，在無線環(huán)境下的多址接入沖突避免MACAW(MACA for Wireless)[2]協(xié)議中，BHARGHAVAN建議使用RTS-CTS-DS-DATA-ACK的消息交換機(jī)制發(fā)送數(shù)據(jù)分組。相比MACA而言,，MACAW增加了DS和ACK 2個控制分組,。通過使用ACK分組，盡量使節(jié)點(diǎn)在MAC層就快速重傳沖突的分組,，而不需要在傳輸層進(jìn)行重傳,。為了進(jìn)一步改善信道接入的公平性，學(xué)者們還在MACAW中引入了乘性增加,、線性減少M(fèi)ILD(Multiplicative Increase Linear Decrease)退避算法,。
1 移動Ad Hoc網(wǎng)MAC協(xié)議退避算法
1.1二進(jìn)制指數(shù)退避算法
 　　二進(jìn)制指數(shù)退避算法是IEEE 802.11 MAC協(xié)議中所采用的。該算法可以用以下2個函數(shù)來表述：
　　inc_cw()
　　{
　　cw_ = (cw_ << 1) + 1;
　　if(cw_ >CWMax)
　　cw_ = CWMax;
　　}
　　rst_cw()
　　{
　　cw_ = CWMin;
　　}
　　(1)當(dāng)節(jié)點(diǎn)發(fā)送數(shù)據(jù)成功時,，調(diào)用rst_cw( )，將競爭窗口cw_調(diào)整到最小值CWMin,。
　　(2)當(dāng)節(jié)點(diǎn)發(fā)送的數(shù)據(jù)發(fā)生沖突時,，調(diào)用inc_cw( )函數(shù)，將競爭窗口cw_加倍,。當(dāng)競爭窗口cw_超過最大值CWMax時,，將競爭窗口cw_設(shè)置為CWMax。
　　(3)當(dāng)節(jié)點(diǎn)連續(xù)7次發(fā)送數(shù)據(jù)失敗時,，也調(diào)用rst_cw( ),，將競爭窗口調(diào)整到最小值CWMin。
　　BEB算法將帶來嚴(yán)重的不公平性,，因?yàn)樵诠?jié)點(diǎn)一次發(fā)送成功后,，將其競爭窗口調(diào)整為最小值CWMin，而其他發(fā)送數(shù)據(jù)失敗的節(jié)點(diǎn)的競爭窗口值變?yōu)樵瓉淼?倍,，使競爭窗口值變得比較大,。在后續(xù)的競爭中，競爭窗口小的節(jié)點(diǎn)在競爭中獲勝的可能性大,。獲勝后,，競爭窗口又降為最小，其他發(fā)送失敗的節(jié)點(diǎn)的競爭窗口再次增大,，獲勝的節(jié)點(diǎn)更有優(yōu)勢,，而其他節(jié)點(diǎn)接入信道的概率很小。
1.2 乘性增加,、線性減少（MILD）退避算法
　　為了改進(jìn)IEEE 802.11 MAC協(xié)議中BEB算法的公平性問題,，在MACAW中提出了乘性增加、線性減少退避算法MILD,。該算法對BEB算法進(jìn)行了修改,，算法程序偽代碼如下：
　　inc_cw()
　　{
　　cw_ = a*cw_ ;
　　if(cw_ >CWMax)
　　cw_ = CWMax;
　　}
　　rst_cw()
　　{
　　cw_= cw_-b;
　　if（cw_< CWMin）
　　cw_ = CWMin;
　　}
　　其中，a和b是2個可調(diào)節(jié)的參數(shù)。在MILD退避算法中,，一次發(fā)送成功后,，競爭窗口減小b，若取適當(dāng)?shù)腷值,，則競爭窗口cw_不會大幅度減小,。當(dāng)節(jié)點(diǎn)發(fā)送的數(shù)據(jù)發(fā)生沖突時，競爭窗口增加a倍,，若a取值合理,，則競爭窗口cw_也不會急劇增加。在參考文獻(xiàn)[2]中,，a和b的值分別是2和1,，即倍數(shù)增加，線性減少,，并在無線局域網(wǎng)環(huán)境下進(jìn)行了仿真,。仿真結(jié)果表明，使用MILD算法比使用BEB算法的公平性要好,。參考文獻(xiàn)[3] 在無線局域網(wǎng)環(huán)境下對MILD進(jìn)行了進(jìn)一步研究,，結(jié)果表明，MILD在網(wǎng)絡(luò)負(fù)載很重的情況下,，性能比BEB算法要好很多,。但當(dāng)網(wǎng)絡(luò)的負(fù)載很小時，MILD的性能不如BEB算法,。這是因?yàn)樗枰荛L的時間才能從由偶然的碰撞引起的退避中恢復(fù)過來,，而且，當(dāng)激活的節(jié)點(diǎn)數(shù)量從很多急劇減少時,，由于MILD對競爭窗口是線性減小的,，不能很快地把競爭窗口cw_調(diào)整到最小，從而引起不必要的退避,。最極端的情況為：當(dāng)CWMin=31,， CWMax=1 023時，用MILD算法最多要經(jīng)歷992次成功發(fā)送,，競爭窗口cw_才能達(dá)到CWMin,，而BEB算法只經(jīng)歷一次成功發(fā)送，競爭窗口cw_就可達(dá)到CWMin,。當(dāng)信道競爭較激烈時,，各節(jié)點(diǎn)在發(fā)生沖突時按倍數(shù)增加退避時間，一段時間后,，各節(jié)點(diǎn)的退避計(jì)數(shù)器值都較大,，如果這時某個新節(jié)點(diǎn)加入網(wǎng)絡(luò),，因?yàn)樾录尤氲墓?jié)點(diǎn)不知道信道的競爭情況，它的退避計(jì)數(shù)器的值會比較小,。這樣競爭信道的各節(jié)點(diǎn)的退避計(jì)數(shù)器值就有了較大的差異,，嚴(yán)重的不公平現(xiàn)象就會產(chǎn)生。
2 乘性增加,、線性減少M(fèi)ILD退避算法的改進(jìn)
　　在MILD退避算法中,，當(dāng)節(jié)點(diǎn)發(fā)送數(shù)據(jù)失敗后，競爭窗口變?yōu)樵瓉淼腶（a=2）倍,；當(dāng)節(jié)點(diǎn)發(fā)送數(shù)據(jù)幀成功后,，競爭窗口減小b（b=1）。成功發(fā)送數(shù)據(jù)的節(jié)點(diǎn)的競爭窗口比發(fā)送失敗的節(jié)點(diǎn)的競爭窗口小得多,，進(jìn)而造成了信道接入的不公平性,。為了改善公平性，應(yīng)把成功發(fā)送數(shù)據(jù)的節(jié)點(diǎn)的競爭窗口增大,，讓發(fā)送失敗的節(jié)點(diǎn)有更多的機(jī)會接入信道,。根據(jù)這個思想，對MILD退避算法做出了改進(jìn),，以達(dá)到節(jié)點(diǎn)公平地共享信道的目的。
　　在改進(jìn)后的算法中,，MILD算法中乘性增加部分保持不變,，線性減少改為線性增加，當(dāng)競爭窗口超過最大值時,，把競爭窗口置為最小,。本文把這種算法稱為改進(jìn)的乘性增加、線性減少退避算法,。改進(jìn)后的偽代碼如下：
　　inc_cw()
　　{
　　cw_ = a*cw_ ;
　　if(cw_ >CWMax)
　　cw_ = CWMax;
　　}
　　rst_cw()
　　{
　　cw_= cw_+b;
　　if（cw_> CWMax）
　　cw_ = CWMin;
　　}
3仿真結(jié)果分析
　　在MAC協(xié)議研究中,，信道接入的公平性是一個最常用的指標(biāo)。公平性指數(shù)是衡量節(jié)點(diǎn)之間是否公平地共享信道的一個重要標(biāo)志,，在參考文獻(xiàn)[4]中使用了改進(jìn)的公平性指數(shù)IFI（Improved Fairless Index）,，表示最大鏈路的吞吐量Throughputmax與最小鏈路的吞吐量Throughputmin之差與總的吞吐量Throughputtotal的比值，其表達(dá)式為：
　　　

　　IFI的值界于0與1之間,。理想情況下,，每條鏈路有相同的吞吐量，這時IFI=0,；如果一個節(jié)點(diǎn)占據(jù)共享信道,，而其他節(jié)點(diǎn)不能接入信道，則IFI=1,，這是最不公平的情況,。IFI越小,，則所獲得的信道接入公平性越高。在本文中,，采用式(1)來計(jì)算公平性,。
　　仿真拓?fù)洳捎脜⒖嘉墨I(xiàn)[5]中所使用的線性拓?fù)洌鐖D1所示,。節(jié)點(diǎn)之間的間隔為150 m,，在彼此的通信范圍（250 m）之內(nèi)，在節(jié)點(diǎn)A,、B之間,，C、D之間分別有一條承載于UDP上的CBR流,。假定節(jié)點(diǎn)A在0 s的時刻向節(jié)點(diǎn)B發(fā)送CBR流,，節(jié)點(diǎn)C也在0 s的時刻向節(jié)點(diǎn)D發(fā)送CBR流，仿真時間為100 s,，包的大小設(shè)置為1 000 B,，信道速率為2 Mb/s。

　　由于MILD退避算法的參數(shù)可以調(diào)整,，在仿真中,，取a=2、b=1和a=2,、b=2進(jìn)行仿真,，結(jié)果如圖2所示。

　　從圖2可知,，與BEB算法相比,，改進(jìn)后的I-MILD算法在鏈路負(fù)載較高的情況下，可大幅度提高信道接入的公平性,，且b=2時的公平性比b=1時的公平性好,，這是因?yàn)楣?jié)點(diǎn)發(fā)送數(shù)據(jù)成功后，把競爭窗口增大了,，減小了與發(fā)送失敗節(jié)點(diǎn)的競爭窗口的差距,，從而使得節(jié)點(diǎn)之間能夠公平地競爭信道。
　　本文對改進(jìn)后的I-MILD退避算法進(jìn)行了仿真,，并適當(dāng)調(diào)整了I-MILD算法的參數(shù),，與采用BEB退避算法相比， 采用I-MILD退避算法能在很大程度上提高信道接入的公平性,。而且此項(xiàng)改進(jìn)是在BEB退避算法的基礎(chǔ)上進(jìn)行的,，不用添加額外的硬件，實(shí)現(xiàn)簡單,，運(yùn)用靈活,，具有較高的實(shí)用價值,。
參考文獻(xiàn)
[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] 李云,陳前斌,隆克平,等.無線自組織網(wǎng)絡(luò)中TCP穩(wěn)定性分析及改進(jìn).軟件學(xué)報(bào),2003,14(6):1178-1186.