基于最大傳輸機會的無線網格網絡擁塞緩解策略

李 帥, 曾曉麗, 胡 偉

(成都信息工程學院網絡工程學院,四川成都610225)

0 引 言

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

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

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

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

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

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

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

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

2 擁塞控制策略

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

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

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

2.2 基于TXOP的擁塞控制策略

上面已經提到提高TXOP[AC]在網絡嚴重擁塞情況下的潛在效果,文獻[8]聚焦TXOP提出的一種無線局域網中TXOP動態分配方法,不適用無線Mesh網。受文獻[8]啟發,在802.11s基本擁塞控制基礎上提出了一種修改擁塞業務TXOP的擁塞控制策略TCC。

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

表1 擁塞程度與分配額度

pac1,pac2都是定值,實際的額度百分比p由擁塞程度和各類業務發送隊列狀態決定,根據發送隊列狀態調整,按照以上要求把待發送隊列中所有分組大小Qac和隊列中來自別的節點的數據分組Qrac納入p的公式設計:

在達到CL1之前所有業務都使用802.11e默認TXOP作為信道接入參數,一旦某類業務被判定為擁塞將根據CL和p分配最大傳輸機會,最大傳輸機會是一個時間Qac和p確定在分配的時間內要發送多少數據,通過網卡的傳輸速率確定TXOP:

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

在一次接收數據過程中統計更新發送隊列擁塞程度,在一次接收完成后通過TCC策略調整TXOP;轉發節點獲得信道使用權限,開始使用調整后的TXOP發送某類業務數據,并統計發送隊列擁塞情況,發送完數據后臺更新TXOP。競爭到信道的使用權,使用TCC策略分配的傳輸機會發送數據。

TCC根據轉發節點某類業務發送隊列實時情況分配競爭到信道后信道使用時間TXOP。

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

3 仿真和分析

仿真在NS2仿真軟件中進行,采用的網絡拓撲如圖3所示。節點1發送業務到節點0,中間需要節點2轉發。節點5到節點6是干擾節點,造成節點2信道資源不足。節點4到節點3也有業務,用來造成節點0信道資源不足。

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

圖2 網絡仿真拓撲

表2 節點1和節點0之間的業務結構

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

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

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

圖5 兩種策略下轉發節點2丟包率對比

5 結束語

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

[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] 劉擁民,蔣新華,年曉紅,等.無線網絡擁塞控制最新研究進展[J].計算機工程與應用,2007,43(24).

[6] 宋文,方旭明.無線Mesh網絡公平感知路由算法設計與仿真[J].系統仿真學報,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] 龐前娟,李精華,嵇建波,等.改進無線網絡TCP協議的跨層設計方法[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協議的公平擁塞控制策略研究[D].成都:西南交通大學,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] 陳晨,高新波,張素兵.無線局域網中TXOP動態分配方法[J].計算機工程,2010,36(7).