《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 通信與網(wǎng)絡(luò) > 設(shè)計應(yīng)用 > 移動Ad Hoc網(wǎng)MAC協(xié)議的一種改進算法
移動Ad Hoc網(wǎng)MAC協(xié)議的一種改進算法
王 昆
(西南科技大學(xué) 計算機學(xué)院,四川 綿陽 621010)
摘要: 著重分析了影響公平性的退避算法,對用于無線局域網(wǎng)的乘性增加、線性減少(MILD)退避算法進行了改進。運用NS2仿真工具對改進算法后的信道接入的公平性進行了分析。結(jié)果表明,與BEB算法相比,改進后的MILD退避算法能大幅度提高信道接入的公平性。
Abstract:
Key words :

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

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

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

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

  從圖2可知,與BEB算法相比,改進后的I-MILD算法在鏈路負載較高的情況下,可大幅度提高信道接入的公平性,且b=2時的公平性比b=1時的公平性好,這是因為節(jié)點發(fā)送數(shù)據(jù)成功后,把競爭窗口增大了,減小了與發(fā)送失敗節(jié)點的競爭窗口的差距,從而使得節(jié)點之間能夠公平地競爭信道。
  本文對改進后的I-MILD退避算法進行了仿真,并適當(dāng)調(diào)整了I-MILD算法的參數(shù),與采用BEB退避算法相比, 采用I-MILD退避算法能在很大程度上提高信道接入的公平性。而且此項改進是在BEB退避算法的基礎(chǔ)上進行的,不用添加額外的硬件,實現(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)定性分析及改進.軟件學(xué)報,2003,14(6):1178-1186.
 

此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載。