移動(dòng)Ad Hoc網(wǎng)MAC協(xié)議的I-MILD退避算法的改進(jìn)方案

20世紀(jì)90年代中期，隨著一些技術(shù)的公開，移動(dòng)Ad Hoc開始引起人們的關(guān)注，成為移動(dòng)通信領(lǐng)域的一個(gè)研究熱點(diǎn)Ad-Hoc（點(diǎn)對(duì)點(diǎn)）模式：ad-hoc模式就和以前的直連雙絞線概念一樣，是P2P的連接，所以也就無法與其它網(wǎng)絡(luò)溝通了。一般無線終端設(shè)備像PMP、PSP、DMA等用的就是ad-hoc模式。 在家庭無線局域網(wǎng)的組建，我想大家都知道最簡(jiǎn)單的莫過于兩臺(tái)安裝有無線網(wǎng)卡的計(jì)算機(jī)實(shí)施無線互聯(lián)，其中一臺(tái)計(jì)算機(jī)連接Internet就可以共享帶寬。如下圖所示，一個(gè)基于Ad-Hoc結(jié)構(gòu)的無線局域網(wǎng)便完成了組建。為了提高網(wǎng)絡(luò)性能，在無線環(huán)境下的多址接入沖突避免MACAW（MACA for Wireless）協(xié)議中，BHARGHAVAN建議使用RTS-CTS-DS-DATA-ACK的消息交換機(jī)制發(fā)送數(shù)據(jù)分組。MACA（multiple access with collision avoidance ）避免沖突的多路訪問，其基本思想是發(fā)送方刺激一下接收方，讓他輸出一個(gè)短幀，因此，接收方附近的站可以檢測(cè)到該幀，從而在接下去的數(shù)據(jù)幀（較大）傳輸過程中它們不再發(fā)送數(shù)據(jù)了。

Ad hoc網(wǎng)絡(luò)的前身是分組無線網(wǎng)（Packet Radio Network）。對(duì)分組無線網(wǎng)的研究源于軍事通信的需要，并已經(jīng)持續(xù)了近20年。早在1972年，美國(guó)DARPA（Defense Advanced Research Project Agency）就啟動(dòng)了分組無線網(wǎng)（PRNET,Packet Radio NETwork）項(xiàng)目，研究分組無線網(wǎng)在戰(zhàn)場(chǎng)環(huán)境下數(shù)據(jù)通信中的應(yīng)用。項(xiàng)目完成之后，DAPRA又在1993年啟動(dòng)了高殘存性自適應(yīng)網(wǎng)絡(luò)（SURAN,SURvivable Adaptive Network）項(xiàng)目。研究如何將prnet的成果加以擴(kuò)展，以支持更大規(guī)模的網(wǎng)絡(luò)，還要開發(fā)能夠適應(yīng)戰(zhàn)場(chǎng)快速變化環(huán)境下的自適應(yīng)網(wǎng)絡(luò)協(xié)議。1994年，DARPA又啟動(dòng)了全球移動(dòng)信息系統(tǒng)（GloMo,Globle Mobile Information Systems）項(xiàng)目。在分組無線網(wǎng)已有成果的基礎(chǔ)上對(duì)能夠滿足軍事應(yīng)用需要的、可快速展開、高抗毀性的移動(dòng)信息系統(tǒng)進(jìn)行全面深入的研究，并一直持續(xù)至今。1991年成立的IEEE802.11標(biāo)準(zhǔn)委員會(huì)采用了“Ad hoc網(wǎng)絡(luò)”一詞來描述這種特殊的對(duì)等式無線移動(dòng)網(wǎng)絡(luò)。

1 移動(dòng)Ad Hoc網(wǎng)MAC協(xié)議退避算法

1.1二進(jìn)制指數(shù)退避算法

退避算法就是網(wǎng)絡(luò)上的節(jié)點(diǎn)在發(fā)送數(shù)據(jù)沖突后，等待一定時(shí)間后再發(fā)，等待時(shí)間是隨指數(shù)增長(zhǎng)主要用于CSMA的沖突分解用二進(jìn)制指數(shù)退避可以取得較好的分解效果。在共用信道的情況下，當(dāng)沖突發(fā)生以后，每個(gè)節(jié)點(diǎn)都進(jìn)行一個(gè)隨機(jī)時(shí)延t,0

（1）當(dāng)節(jié)點(diǎn)發(fā)送數(shù)據(jù)成功時(shí)，調(diào)用rst_cw（ ），將競(jìng)爭(zhēng)窗口cw_調(diào)整到最小值CWMin。

（2）當(dāng)節(jié)點(diǎn)發(fā)送的數(shù)據(jù)發(fā)生沖突時(shí)，調(diào)用inc_cw（ ）函數(shù)，將競(jìng)爭(zhēng)窗口cw_加倍。當(dāng)競(jìng)爭(zhēng)窗口cw_超過最大值CWMax時(shí)，將競(jìng)爭(zhēng)窗口cw_設(shè)置為CWMax。

（3）當(dāng)節(jié)點(diǎn)連續(xù)7次發(fā)送數(shù)據(jù)失敗時(shí)，也調(diào)用rst_cw（ ），將競(jìng)爭(zhēng)窗口調(diào)整到最小值CWMin。

BEB算法將帶來嚴(yán)重的不公平性，因?yàn)樵诠?jié)點(diǎn)一次發(fā)送成功后，將其競(jìng)爭(zhēng)窗口調(diào)整為最小值CWMin，而其他發(fā)送數(shù)據(jù)失敗的節(jié)點(diǎn)的競(jìng)爭(zhēng)窗口值變?yōu)樵瓉淼?倍，使競(jìng)爭(zhēng)窗口值變得比較大。在后續(xù)的競(jìng)爭(zhēng)中，競(jìng)爭(zhēng)窗口小的節(jié)點(diǎn)在競(jìng)爭(zhēng)中獲勝的可能性大。

1.2 乘性增加、線性減少（MILD）退避算法

為了改進(jìn)IEEE 802.11 MAC協(xié)議中BEB算法的公平性問題，在MACAW中提出了乘性增加、線性減少退避算法MILD。該算法對(duì)BEB算法進(jìn)行了修改，算法程序偽代碼如下：

其中，a和b是2個(gè)可調(diào)節(jié)的參數(shù)。在MILD退避算法中，一次發(fā)送成功后，競(jìng)爭(zhēng)窗口減小b，若取適當(dāng)?shù)腷值，則競(jìng)爭(zhēng)窗口cw_不會(huì)大幅度減小。當(dāng)節(jié)點(diǎn)發(fā)送的數(shù)據(jù)發(fā)生沖突時(shí)，競(jìng)爭(zhēng)窗口增加a倍，若a取值合理，則競(jìng)爭(zhēng)窗口cw_也不會(huì)急劇增加。在參考文獻(xiàn)[2]中，a和b的值分別是2和1，即倍數(shù)增加，線性減少，并在無線局域網(wǎng)環(huán)境下進(jìn)行了仿真。仿真結(jié)果表明，使用MILD算法比使用BEB算法的公平性要好。參考文獻(xiàn)[3] 在無線局域網(wǎng)環(huán)境下對(duì)MILD進(jìn)行了進(jìn)一步研究，結(jié)果表明，MILD在網(wǎng)絡(luò)負(fù)載很重的情況下，性能比BEB算法要好很多。但當(dāng)網(wǎng)絡(luò)的負(fù)載很小時(shí)，MILD的性能不如BEB算法。這是因?yàn)樗枰荛L(zhǎng)的時(shí)間才能從由偶然的碰撞引起的退避中恢復(fù)過來，而且，當(dāng)激活的節(jié)點(diǎn)數(shù)量從很多急劇減少時(shí)，由于MILD對(duì)競(jìng)爭(zhēng)窗口是線性減小的，不能很快地把競(jìng)爭(zhēng)窗口cw_調(diào)整到最小，從而引起不必要的退避。最極端的情況為：當(dāng)CWMin=31， CWMax=1 023時(shí)，用MILD算法最多要經(jīng)歷992次成功發(fā)送，競(jìng)爭(zhēng)窗口cw_才能達(dá)到CWMin，而BEB算法只經(jīng)歷一次成功發(fā)送，競(jìng)爭(zhēng)窗口cw_就可達(dá)到CWMin。

2 乘性增加、線性減少M(fèi)ILD退避算法的改進(jìn)

在MILD退避算法中，當(dāng)節(jié)點(diǎn)發(fā)送數(shù)據(jù)失敗后，競(jìng)爭(zhēng)窗口變?yōu)樵瓉淼腶（a=2）倍；當(dāng)節(jié)點(diǎn)發(fā)送數(shù)據(jù)幀成功后，競(jìng)爭(zhēng)窗口減小b（b=1）。成功發(fā)送數(shù)據(jù)的節(jié)點(diǎn)的競(jìng)爭(zhēng)窗口比發(fā)送失敗的節(jié)點(diǎn)的競(jìng)爭(zhēng)窗口小得多，進(jìn)而造成了信道接入的不公平性。為了改善公平性，應(yīng)把成功發(fā)送數(shù)據(jù)的節(jié)點(diǎn)的競(jìng)爭(zhēng)窗口增大，讓發(fā)送失敗的節(jié)點(diǎn)有更多的機(jī)會(huì)接入信道。根據(jù)這個(gè)思想，對(duì)MILD退避算法做出了改進(jìn)，以達(dá)到節(jié)點(diǎn)公平地共享信道的目的。

在改進(jìn)后的算法中，MILD算法中乘性增加部分保持不變，線性減少改為線性增加，當(dāng)競(jìng)爭(zhēng)窗口超過最大值時(shí)，把競(jìng)爭(zhēng)窗口置為最小。本文把這種算法稱為改進(jìn)的乘性增加、線性減少退避算法。改進(jìn)后的偽代碼如下：

3仿真結(jié)果分析

在MAC協(xié)議研究中，信道接入的公平性是一個(gè)最常用的指標(biāo)。公平性指數(shù)是衡量節(jié)點(diǎn)之間是否公平地共享信道的一個(gè)重要標(biāo)志，在參考文獻(xiàn)[4]中使用了改進(jìn)的公平性指數(shù)IFI（Improved Fairless Index），表示最大鏈路的吞吐量Throughputmax與最小鏈路的吞吐量Throughputmin之差與總的吞吐量Throughputtotal的比值，其表達(dá)式為：

IFI的值界于0與1之間。理想情況下，每條鏈路有相同的吞吐量，這時(shí)IFI=0；如果一個(gè)節(jié)點(diǎn)占據(jù)共享信道，而其他節(jié)點(diǎn)不能接入信道，則IFI=1，這是最不公平的情況。IFI越小，則所獲得的信道接入公平性越高。在本文中，采用式（1）來計(jì)算公平性。

仿真拓?fù)洳捎脜⒖嘉墨I(xiàn)[5]中所使用的線性拓?fù)?，如圖1所示。節(jié)點(diǎn)之間的間隔為150 m，在彼此的通信范圍（250 m）之內(nèi)，在節(jié)點(diǎn)A、B之間，C、D之間分別有一條承載于UDP上的CBR流。假定節(jié)點(diǎn)A在0 s的時(shí)刻向節(jié)點(diǎn)B發(fā)送CBR流，節(jié)點(diǎn)C也在0 s的時(shí)刻向節(jié)點(diǎn)D發(fā)送CBR流，仿真時(shí)間為100 s，包的大小設(shè)置為1 000 B，信道速率為2 Mb/s。

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

與BEB算法相比，改進(jìn)后的I-MILD算法在鏈路負(fù)載較高的情況下，可大幅度提高信道接入的公平性，且b=2時(shí)的公平性比b=1時(shí)的公平性好。

本文對(duì)改進(jìn)后的I-MILD退避算法進(jìn)行了仿真，并適當(dāng)調(diào)整了I-MILD算法的參數(shù)，與采用BEB退避算法相比， 采用I-MILD退避算法能在很大程度上提高信道接入的公平性。