基于最大傳輸機會的無線網(wǎng)格網(wǎng)絡(luò)擁塞緩解策略

李 帥, 曾曉麗, 胡 偉

(成都信息工程學(xué)院網(wǎng)絡(luò)工程學(xué)院,四川成都610225)

0 引 言

近年來,無線局域網(wǎng)(WLAN)在接入領(lǐng)域中得到了迅速發(fā)展,依據(jù)其數(shù)據(jù)傳輸速率的較大優(yōu)勢,WLAN被認(rèn)為是3G或后3G移動數(shù)據(jù)通信的一個主要競爭者。但WLAN也有不足之處,其中最主要的一個就是接入點(AP)的覆蓋范圍有限,若要在一個相對較大的區(qū)域提供無線覆蓋,就需要配置多個接入點,因而增加了網(wǎng)絡(luò)建設(shè)成本。因此近年來人們把目光轉(zhuǎn)向一種新的網(wǎng)絡(luò)結(jié)構(gòu)——無線Mesh網(wǎng)絡(luò)(WMN)。WMN是一種高容量、高速率的分布式網(wǎng)絡(luò)。從組網(wǎng)方式講,WMN可以看成是WLAN和移動Ad hoc網(wǎng)絡(luò)的融合,具有較強的靈活性和健壯性。自IEEE802.11WLAN工作組于2004年成立Mesh任務(wù)組以來,針對WMN的802.11s協(xié)議草案已經(jīng)成功問世,預(yù)計在2012年年底正式的協(xié)議標(biāo)準(zhǔn)可以出臺。

早期的無線網(wǎng)絡(luò)擁塞控制研究都把注意力集中在甄別數(shù)據(jù)包的丟失是由無線信道沖突還是擁塞造成的[1-2]。文獻[1]提出一種間接的TCP協(xié)議,針對無線網(wǎng)絡(luò)采用改進的協(xié)議可以通知上層無線網(wǎng)絡(luò)斷開、移動和其他的無線鏈路參數(shù),如可用信道容量等,但是方案破壞了TCP連接的端對端語義。

目前關(guān)于無線網(wǎng)絡(luò)的擁塞控制主要是在TCP擁塞控制的基礎(chǔ)上進行一些改進,多是在傳輸層實現(xiàn)或者在傳輸層結(jié)合底層的一些信息進行跨層設(shè)計,如文獻[3-4]。文獻[5]使用跨層設(shè)計將擁塞控制移至MAC層,提出NTCP的算法,基于802.11 DCF的MAC層修改添加了兩種新幀NTR(Not to Receive)和FRTS(Future Request To Send)。擁塞節(jié)點用NT R幀告訴鄰居節(jié)點發(fā)生擁塞,不在接受數(shù)據(jù),之后立刻進行發(fā)送數(shù)據(jù),擁塞節(jié)點采用FRTS代替RTS告訴鄰居節(jié)點還有多少數(shù)據(jù)未發(fā)送完畢。方法采用對流入數(shù)據(jù)和流出數(shù)據(jù)對比的方法獲取擁塞狀態(tài),當(dāng)流入數(shù)據(jù)大于流出數(shù)據(jù)是即認(rèn)為發(fā)生擁塞。算法對擁塞反應(yīng)靈敏,能夠很快的對擁塞節(jié)點作出反應(yīng)。相比傳統(tǒng)的TCP-Reno,NTCP吞吐量更加穩(wěn)定,端到端的延時也明顯小于傳統(tǒng)TCP層的擁塞控制算法。但算法沒有實現(xiàn)不同業(yè)務(wù)不同區(qū)分,無法提供Qos。文獻[6]也采用跨層設(shè)計的方法,MAC層同樣采用802.11 DCF,針對節(jié)點上通過的數(shù)據(jù)流建立輕量級的數(shù)據(jù)庫用于記錄流的源地址和最后一次的更新時間,設(shè)計了兩個新的模塊,擁塞評估模塊和速率調(diào)整模塊。擁塞控制模塊利用存放流信息的數(shù)據(jù)庫和MAC層的丟包信息對當(dāng)前節(jié)點的擁塞狀態(tài)進行評估,如果出現(xiàn)擁塞將向應(yīng)用層發(fā)送擁塞報告,并觸發(fā)速率調(diào)整模塊,速率調(diào)整模塊根據(jù)擁塞評估信息進行計算決定需要調(diào)整的速率,應(yīng)用層修改新的發(fā)送速率。該策略利用跨層設(shè)計,將MAC的丟包信息迅速的反映到上層的速率調(diào)整,擁塞控制靈敏迅速,網(wǎng)絡(luò)的性能指標(biāo)吞吐量、延時、丟包等都得到了顯著的提高,是跨層擁塞控制設(shè)計的代表。但研究沒有采用最新的802.11e里面的EDCA接入機制,無法在MAC層接入的時候就對不同的業(yè)務(wù)提供Qos服務(wù)。

在鏈路層實現(xiàn)擁塞控制最早是在802.11s草案[7]中提出。武昌盛,方旭明等[8]將經(jīng)濟學(xué)的定價理論應(yīng)用到無線多跳網(wǎng)絡(luò)的擁塞控制中,基于IEEE802.11s提出了基于定價理論的擁塞控制策略,通過統(tǒng)計4類業(yè)務(wù)接收發(fā)送速率差,對業(yè)務(wù)定價,將定價信息反饋到上游節(jié)點,調(diào)整競爭窗口達到擁塞控制,在網(wǎng)絡(luò)擁塞比較嚴(yán)重的時候會加劇信道競爭,增加信道競爭造成的時間開銷。文中研究的無線Mesh網(wǎng)絡(luò)中的擁塞控制策略是在802.11s協(xié)議草案的基礎(chǔ)上進行改進,針對前人研究調(diào)整信道競爭參數(shù)存在加劇擁塞的情況,根據(jù)擁塞情況動態(tài)分配發(fā)送機會TXOP。

1 IEEE802.11s中的EDCA接入機制

在802.11s草案中采用802.11e EDCA(Enhanced Distributed Channel Access),定義了4種不同的信道接入類別AC(Access Category),每個接入類別對應(yīng)不同優(yōu)先級的業(yè)務(wù)數(shù)據(jù)。為了針對不同優(yōu)先級的業(yè)務(wù)數(shù)據(jù)提供有區(qū)別的服務(wù)質(zhì)量,EDCA規(guī)定每個AC都有一個獨立的分組發(fā)送隊列,并且不同的AC執(zhí)行相互獨立的退避算法為其隊列中分組競爭信道的接入使用權(quán)。每個AC的使用不同的接入?yún)?shù)來競爭信道。這些參數(shù)包括:最小競爭窗口(Congestion Window min[AC])、最大競爭窗口(Congestion Window max[AC])、AIFS[AC](Arbitration Inter Frame Space)、TXOP[AC]。

當(dāng)節(jié)點某個AC隊列中有數(shù)據(jù)要發(fā)送并且當(dāng)前信道處于忙碌狀態(tài),節(jié)點啟動對應(yīng)AC的退避計數(shù)器,計數(shù)器的初始值在[0,CW[AC]]區(qū)間上隨機選擇一個整數(shù)值,每檢測到信道連續(xù)空閑達到AISF[AC]時間后減1,減到0時,節(jié)點開始發(fā)送數(shù)據(jù)或者RTS(Require To Send)幀。如果節(jié)點內(nèi)多個AC退避計數(shù)同時減為0,優(yōu)先級高的節(jié)點先發(fā)送,低的按發(fā)送碰撞處理再次退避。節(jié)點內(nèi)的AC是否成功競爭到信道的使用權(quán)取決于是否在發(fā)送RTS幀后的短幀間隔內(nèi)收到CTS(Clear To Send),收到CTS的AC將在TXOP[AC]長的時間里可以連續(xù)發(fā)送多個數(shù)據(jù)分組而無需再次競爭信道。

在EDCA競爭機制下信道的競爭變成了節(jié)點內(nèi)不同優(yōu)先級AC的競爭和節(jié)點間AC的競爭。因此擁塞的檢測和擁塞控制對象都需要從節(jié)點轉(zhuǎn)移到節(jié)點內(nèi)各個AC隊列。TXOP值不隨著轉(zhuǎn)發(fā)節(jié)點的擁塞程度改變,會帶來業(yè)務(wù)間和節(jié)點間的不公平的性[9]。因此提出一種根據(jù)節(jié)點各個AC發(fā)送隊列狀態(tài)動態(tài)改變TXOP[AC]的擁塞控制策略。

2 擁塞控制策略

2.1 802.11s草案中的擁塞控制策略

802.11s草案中提出的擁塞控制是在數(shù)據(jù)鏈路層實現(xiàn)的,采用hop-by-hop的逐跳擁塞控制方式,擁塞控制分為“本地?fù)砣麢z測”、“擁塞控制信令交互”和“目標(biāo)速率控制”,通過檢測本地各個AC業(yè)務(wù)的發(fā)送速率和接收速率差來判斷是否向上游節(jié)點發(fā)送擁塞控制信令,如果接收速率大于發(fā)送速率就通過擁塞交互信令通知上游節(jié)點提高AIFS來減緩CW(競爭窗口)的減小速度以達到降低節(jié)點信道接入優(yōu)先級,相反的接收速率小于發(fā)送速率就降低AIFS來加快上游節(jié)點CW的減小速度從而提高上游節(jié)點的信道接入優(yōu)先級。

草案中的擁塞控制策略在網(wǎng)絡(luò)初始階段各個節(jié)點的AC發(fā)送隊列中待發(fā)送的數(shù)據(jù)分組不多的時候能夠起到很好的擁塞控制效果,網(wǎng)絡(luò)運行一段時間后處于無線Mesh網(wǎng)中間轉(zhuǎn)發(fā)節(jié)點中的各個AC發(fā)送隊列被需要轉(zhuǎn)發(fā)的數(shù)據(jù)分組幾乎充滿,單純的調(diào)整上游節(jié)點的AIFS提高中間節(jié)點有接入信道機會是不夠的,競爭到一次信道的使用權(quán)后,發(fā)送少量數(shù)據(jù)就釋放信道,不足以改變中間節(jié)點某類AC隊列仍然擁塞的狀態(tài)。需要給擁塞的AC業(yè)務(wù)較大的TXOP,讓該類業(yè)務(wù)在最大傳輸機會這段時間內(nèi)不用競爭信道把更多緩存的數(shù)據(jù)分組發(fā)送出去,從而緩解擁塞。

2.2 基于TXOP的擁塞控制策略

上面已經(jīng)提到提高TXOP[AC]在網(wǎng)絡(luò)嚴(yán)重?fù)砣闆r下的潛在效果,文獻[8]聚焦TXOP提出的一種無線局域網(wǎng)中TXOP動態(tài)分配方法,不適用無線Mesh網(wǎng)。受文獻[8]啟發(fā),在802.11s基本擁塞控制基礎(chǔ)上提出了一種修改擁塞業(yè)務(wù)TXOP的擁塞控制策略TCC。

EDCA接入機制為各個業(yè)務(wù)單獨分配有限空間的發(fā)送隊列,因此TCC通過檢測各類業(yè)務(wù)的發(fā)送隊列的剩余空間來判斷是否發(fā)生擁塞。802.11s草案中沒有明確各類業(yè)務(wù)發(fā)送隊列分配的具體參數(shù),研究過程中為了消除不同發(fā)送隊列造成的干擾,為4類業(yè)務(wù)分配相同的發(fā)送隊列緩存空間,大部分基于隊列的擁塞控制研究都直接把發(fā)送隊列中緩存的數(shù)據(jù)占用預(yù)分配空間的百分比做為擁塞程度的表征,按照慣例用這個百分比表示擁塞程度Congestion Level(CL)。一般基于隊列的擁塞控制研究中,隊列中緩存數(shù)據(jù)占到隊列預(yù)分配空間的80%～90%即視為發(fā)生擁塞,依此從90%開始劃分出兩個擁塞等級(CL1,CL2),p定義為TXOP的分配額度,在不同的擁塞級別下分配不同的額度,同時為了保證原有業(yè)務(wù)優(yōu)先級的一致性,不同的業(yè)務(wù)在發(fā)生擁塞時TXOP分配額度pac也加以區(qū)分,pac1、pac2分別表示特定業(yè)務(wù)在兩種擁塞級別下分配的最大傳輸機會額度百分比,pac1、pac2的確定目前沒有足夠的理論依據(jù),通過大量仿真選擇可以使系統(tǒng)性能最佳的經(jīng)驗值作分配,如表1所示。

表1 擁塞程度與分配額度

pac1,pac2都是定值,實際的額度百分比p由擁塞程度和各類業(yè)務(wù)發(fā)送隊列狀態(tài)決定,根據(jù)發(fā)送隊列狀態(tài)調(diào)整,按照以上要求把待發(fā)送隊列中所有分組大小Qac和隊列中來自別的節(jié)點的數(shù)據(jù)分組Qrac納入p的公式設(shè)計:

在達到CL1之前所有業(yè)務(wù)都使用802.11e默認(rèn)TXOP作為信道接入?yún)?shù),一旦某類業(yè)務(wù)被判定為擁塞將根據(jù)CL和p分配最大傳輸機會,最大傳輸機會是一個時間Qac和p確定在分配的時間內(nèi)要發(fā)送多少數(shù)據(jù),通過網(wǎng)卡的傳輸速率確定TXOP:

公式(2)中TXOPAC是將要分配給擁塞隊列的最大傳輸機會,dr是網(wǎng)卡的傳輸速率仿真中采用802.11b網(wǎng)卡0＜dr＜11(單位Mb/s)。如果隊列中緩存的其它節(jié)點的數(shù)據(jù)增多就會分配更多的發(fā)送機會。提出的擁塞控制策略是通過監(jiān)測發(fā)送隊列來判定擁塞程度,中轉(zhuǎn)節(jié)點接收或發(fā)送數(shù)據(jù)都會改變發(fā)送隊列的擁塞情況,因此TCC的執(zhí)行過程如圖1所示。

在一次接收數(shù)據(jù)過程中統(tǒng)計更新發(fā)送隊列擁塞程度,在一次接收完成后通過TCC策略調(diào)整TXOP;轉(zhuǎn)發(fā)節(jié)點獲得信道使用權(quán)限,開始使用調(diào)整后的TXOP發(fā)送某類業(yè)務(wù)數(shù)據(jù),并統(tǒng)計發(fā)送隊列擁塞情況,發(fā)送完數(shù)據(jù)后臺更新TXOP。競爭到信道的使用權(quán),使用TCC策略分配的傳輸機會發(fā)送數(shù)據(jù)。

TCC根據(jù)轉(zhuǎn)發(fā)節(jié)點某類業(yè)務(wù)發(fā)送隊列實時情況分配競爭到信道后信道使用時間TXOP。

圖1 TCC擁塞控制策略流程圖

3 仿真和分析

仿真在NS2仿真軟件中進行,采用的網(wǎng)絡(luò)拓?fù)淙鐖D3所示。節(jié)點1發(fā)送業(yè)務(wù)到節(jié)點0,中間需要節(jié)點2轉(zhuǎn)發(fā)。節(jié)點5到節(jié)點6是干擾節(jié)點,造成節(jié)點2信道資源不足。節(jié)點4到節(jié)點3也有業(yè)務(wù),用來造成節(jié)點0信道資源不足。

仿真中設(shè)定的節(jié)點1到節(jié)點0之間的業(yè)務(wù)見表2。其他節(jié)點之間(5到6、4到3)的業(yè)務(wù)也做了類似的定義。其中Voice業(yè)務(wù)優(yōu)先級最高,定義為prio-0等級,Video業(yè)務(wù)和Date業(yè)務(wù)分別為prio-1和prio-2業(yè)務(wù)。表中各種業(yè)務(wù)的業(yè)務(wù)量都比較大,屬于網(wǎng)絡(luò)負(fù)載較大的情況。

圖2 網(wǎng)絡(luò)仿真拓?fù)?/p>

表2 節(jié)點1和節(jié)點0之間的業(yè)務(wù)結(jié)構(gòu)

仿真結(jié)果見圖3～圖5。圖3中A、C、E柱體表示在不使用TCC擁塞策略情況下信道競爭所造成的時間消耗比,B、D、F柱體代表TCC擁塞策略下的時間消耗比,未發(fā)生擁塞時,兩種策略沒有明顯的差別,隨著擁塞程度加劇TCC按節(jié)點某類業(yè)務(wù)發(fā)送隊列擁塞程度動態(tài)分配TXOP的優(yōu)勢逐漸顯露,當(dāng)擁塞達到CL2時TCC策略的優(yōu)勢已經(jīng)非常明顯。

由圖4可知,淺色曲線表示在不使用TCC擁塞策略情況下,節(jié)點1和節(jié)點0之間的總吞吐量。其吞吐量穩(wěn)定在1.2Mbps左右。藍色曲線表示在使用TCC擁塞控制策略情況下節(jié)點1和節(jié)點0之間的總吞吐量。由以上結(jié)果可知,在使用TCC策略情況下,網(wǎng)絡(luò)總吞吐量得到明顯提高。這首先是由于本策略中轉(zhuǎn)發(fā)節(jié)點根據(jù)自身某類業(yè)務(wù)擁塞情況動態(tài)地調(diào)整自身TXOP提高了擁塞情況下某類業(yè)務(wù)的最大傳輸機會,有效地通過增加擁塞業(yè)務(wù)的發(fā)送時間緩解了轉(zhuǎn)發(fā)節(jié)點附近的信道因過度競爭造成的時間消耗問題,降低了上游節(jié)點信道使用時間。

圖5展示了擁塞策略對網(wǎng)絡(luò)在丟包方面的明顯改善,這得益于TCC擁塞控制策略在發(fā)生丟包之前就對擁塞節(jié)點進行調(diào)整,一定程度上減輕了由丟包所造成的信道消耗,從而提高了網(wǎng)絡(luò)資源的利用率。

圖5 兩種策略下轉(zhuǎn)發(fā)節(jié)點2丟包率對比

5 結(jié)束語

在IEEE 802.11s的擁塞控制策略的基礎(chǔ)上提出了一種根據(jù)轉(zhuǎn)發(fā)節(jié)點發(fā)送隊列擁塞情況動態(tài)分配最大傳輸機會TXOP的擁塞控制策略TCC。策略避開了同類研究中信道競爭參數(shù)的調(diào)整,主要針對無線Mesh網(wǎng)中的中間轉(zhuǎn)發(fā)節(jié)點,將擁塞判別定位于4類業(yè)務(wù)的發(fā)送隊列,針對不同業(yè)務(wù)的特性提出了不同的擁塞判定,依擁塞程度分配最大傳輸機會。通過仿真可以看出擁塞控制策略降低了擁塞節(jié)點附近信道競爭所造成的時間消耗,網(wǎng)絡(luò)吞吐也有改善,丟包得到了顯著改善。不過由于策略只針對擁塞的轉(zhuǎn)發(fā)節(jié)點調(diào)整競爭到信道后才能生效的TXOP,并沒有增加擁塞節(jié)點的信道接入機會,網(wǎng)絡(luò)吞吐抖動比較明顯。策略仍需進一步改進,將轉(zhuǎn)發(fā)節(jié)點擁塞信息反饋周邊節(jié)點,在擁塞時適當(dāng)提高擁塞業(yè)務(wù)的信道接入機會。

[1] A Bakre,B Badrinath.I-TCP:indirect TCP for mobile hosts[C].In Proc.of IEEE ICDCS,1995.

[2] H Balakrishnan,S Seshan,R H Katz.Improving reliable trans-port and handoff performance in cellular wireless networks[J].Wireless Networks,1995.

[3] Yung Yi,Sanjay Shakkottai.Hop-by-hop Congestion Control over a Wireless Multi-hop Network[C].INFOCOM 2004.

[4] Dzmitry Kliazovich,Fabrizio Granelli.Cross-Layer Congestion Control in Multi-hop Wireless Local Area Networks[C].First International Conference on Wireless Internet,2005,164-171.

[5] 劉擁民,蔣新華,年曉紅,等.無線網(wǎng)絡(luò)擁塞控制最新研究進展[J].計算機工程與應(yīng)用,2007,43(24).

[6] 宋文,方旭明.無線Mesh網(wǎng)絡(luò)公平感知路由算法設(shè)計與仿真[J].系統(tǒng)仿真學(xué)報,2007,19(18):4320-4355.

[7] Vijoy Pandey,Dipak Ghosal,Biswanath Mukherjee.Pricing-Based Approaches in the Design of Next-Generation Wireless Networks[J].IEEE,Communications suwey and tutorials,2007.

[8] Hiroki Nishiyama,Nirwan Ansari,Nei Kato.Wireless Loss-Tolerant Congestion Control protocol based on dynamic aimd theory[J].IEEE,Wireless Communications,2010.

[9] Anita Kanavall,Jayashree M,P Deepa Shenoy.Hop by Hop Congestion Control System for Adhoc Networks[C].TENCON IEEE Region 10 Conference 2008.

[10] 龐前娟,李精華,嵇建波,等.改進無線網(wǎng)絡(luò)TCP協(xié)議的跨層設(shè)計方法[J].計算機工程,2010,36.

[11] Christos Antonopoulos,Stavros Koubias.Congestion Control FrameWork for Ad-hoc Wireless Networks[J].Wireless Per Commun 2010,52:753-755.

[12] Draft P802.11s:D11.0,[EB/OL]http://goo.gl/kbmmu,2011-04.

[13] 武昌盛,方旭明.基于IEEE802.11s協(xié)議的公平擁塞控制策略研究[D].成都:西南交通大學(xué),2008.

[14] Li Tianji,Leith D.Achieving End-to-End Fairnessin 802.11e-based Wireless Multi-hop Mesh Network[C].Proc.Of the 3rd Int'1 Conf.

[15] 陳晨,高新波,張素兵.無線局域網(wǎng)中TXOP動態(tài)分配方法[J].計算機工程,2010,36(7).