無線Mesh網絡中基于鏈路負載估算的擁塞控制策略

夏漢鑄+劉輝元

摘 要： 針對無線Mesh網絡的網絡特性，提出了一種基于鏈路負載估算的擁塞控制策略LLECC。LLECC算法計算有效鏈路帶寬和鏈路負載估算確定RED算法中的調整因子，通過調整因子調整RED算法中的參數從而實現動態的對無線網絡擁塞控制。詳細討論了LLECC算法的實現過程和相關參數的計算方法，通過仿真分析驗證了該算法對無線Mesh網絡性能的提高。

關鍵詞： 無線Mesh網絡； 有效鏈路帶寬； 鏈路負載估算； 擁塞控制； RED算法

中圖分類號： TN711?34； TP393 文獻標識碼： A 文章編號： 1004?373X（2014）03?0027?04

Congestion control strategy based on link load estimation in wireless mesh networks

XIA Han?zhu1， LIU Hui?yuan2

（1. Department of Information Engineering， Zhongshan Torch Polytechnic， Zhongshan 528436， China； 2. Chongqing School of Industry， Chongqing 400043， China）

Abstract： Aiming at the network characteristics of wireless Mesh networks （WMNs）， an LLECC congestion control strategy based on link load estimation is proposed， which estimates the tuning factor of RED algorithm by calculating the available link bandwidth and link loads. The parameters in RED algorithm are adjusted by tuning factor to realize dynamic wireless network congestion control. The realization process of LLECC algorithm and computing method of parameters are discussed in detail. Through the analysis and simulation， it is proved that the LLECC algorithm can increase the performance of the wireless Mesh networks.

Keywords： wireless Mesh networks； available link bandwidth； link load estimation； congestion control； RED algorithm

0 引 言

隨著網絡技術的發展和應用，用戶對網絡的帶寬、移動性和可靠性要求越來越高。無線Mesh網絡WMN[1?3]（Wireless Mesh Networks）融合了WLAN網絡和Ad hoc網絡的技術特點，希望為用戶提供可靠的高速寬帶無線網絡服務。多信道WMN允許多個不重疊的信道可以同時傳輸數據，這樣就能滿足無線Mesh網絡對帶寬資源的要求。

在WMN中，移動節點獨立的爭用無線網絡資源，不考慮其他移動節點的實際狀態，這樣就會導致某一節點往無線網絡中大量發送數據，可能導致無線網絡擁塞的情況出現[4?7]。一旦無線網絡出現擁塞，勢必導致無線網絡中大量的數據丟失和重傳，嚴重影響無線網絡的網絡性能。而高層的擁塞控制策略（如TCP中的滑動窗口）無法滿足無線Mesh網絡擁塞控制的要求，無線網絡中移動節點的擁塞控制策略就變得極為重要。

RED算法[8?10]是有線網絡中擁塞控制的一種有效手段，RED算法采用低通濾波器模型來計算平均隊長，支持突發業務，使得路由器處理算法實現的更為合理，避免了路由器因根據變化的實際隊列長度而不斷地變更處理方法，該算法因其具有較低的時延，較高的吞吐量和較好的公平性而被廣泛采用。它通過在擁塞即將發生時丟棄部分數據，能夠有效地避免全局同步，體現了對突發業務流的公平性。在無線Mesh網絡中，由于網絡中的各節點動態變化導致可使用的網絡資源變化，而在RED算法中的預先設置的參數[wq，][minth，][maxth，][Pmax]不能與網絡資源的變化同步，這樣勢必導致RED算法無法滿足提高無線網絡性能的目的。

本文對RED算法進行了詳細的分析，對WMN中的有效鏈路帶寬和鏈路負載估算的重要性進行了分析，提出了一種基于鏈路負載估算的擁塞控制策略LLECC（Link?Load?Estimation?based Congestion Control）。LLECC算法通過對WMN中的鏈路帶寬和鏈路負載估算值動態地調整RED算法中的[minth，][maxth，][Pmax]三個參數實現網絡中的動態擁塞控制。從該策略的實現過程和仿真結果來看，LLECC可以對WMN的擁塞程度做出相應的速率控制策略，而且能夠提高無線網絡的性能和不同業務的QoS保證。

1 RED算法

RED算法的基本思想是通過監測路由器輸出端口隊列的平均長度來探測擁塞，采用相關的策略使隊列溢出導致丟包之前采用一定的丟包策略保證隊列不溢出，降低發送數據速度，從而緩解網絡擁塞。RED是基于FIFO隊列調度策略的，只是丟棄正進入路由器的數據包。RED算法的目的是最小化數據包丟失率和排隊延遲，避免對突發業務的不公平和全局同步現象。RED算法主要分兩部分：一是計算平均隊列長度；一是標記丟棄分組的概率，并對新到達的分組按照標記丟棄分組概率對該分組進行丟棄或排隊處理。

RED算法采用低通濾波器模型來計算平均隊列長度，突發業務對隊列的長度會導致隊列長度的短期增加，不會過大的影響平均隊列長度。

[avg=（1-wq）avg+wqQ]

即：

[avg=avg+wq（Q-avg）] （1）

式中：avg為平均隊列長度；[wq]為權值；[Q]為當前隊列長度。

當一個分組到達隊列[Q]時，通過計算標記丟棄概率來決定該分組被丟棄的可能性。

當[avgminth，][Pd]=0，該分組不被丟棄，直接進入到隊列中；

[當minthavgmaxth，Pd=Pmax（avg-minth）（maxth-avg），]到達分組以[Pd]概率丟棄；

當[avgmaxth，][Pd]=1，該分組將直接被丟棄。

2 LLCEE擁塞控制策略

在無線Mesh網絡中，由于用戶的移動性、網絡鏈路質量及網絡擁塞水平等因素導致在無線網絡環境下的擁塞控制策略極為復雜。LLCEE擁塞控制算法通過對WMN中的鏈路帶寬和鏈路負載估算值動態地調整RED算法中的[minth、][maxth、][Pmax]三個參數實現網絡中的擁塞控制。

2.1 LLCEE算法實現

LLCEE擁塞控制算法通過4個過程來實現無線網絡的擁塞控制：計算鏈路的有效帶寬；對本節點的鏈路負載進行估算；通過以上2個計算結果確定調整因子[α；]通過調整因子[α]值確定RED算法中的參數[minth、][maxth、][Pmax]實現本移動節點的擁塞控制。本算法的實現過程如圖1所示，偽代碼如下：

初始化參數：

α=0 ALBW=[i=1nBWi] LL=0

經過ΔT時間間隔

用公式（1）計算 有效鏈路帶寬

用公式（2）計算 鏈路負載估算

用公式（3）計算 調整因子

用公式（4）計算 minth，maxth，Pmax

時刻t，某一分組到達每一隊列：

if avg≤minth Pd=0

else if （minth≤avg≤maxth） 計算Pd

else Pd=1

根據Pd決定該分組插入隊列或丟棄

圖1 LLCEE算法流程圖

（1） 有效鏈路帶寬的計算

在多信道無線Mesh網絡中，由于節點的移動性和設備的差異性等因素的影響導致無線信道的實際有效帶寬與系統表明的標準帶寬存在一定的差異（如由于網絡信號的衰減導致信號傳輸出現誤碼），而無線網絡中擁塞控制策略必須準確的知道本節點實際可用帶寬資源，也就是有效鏈路帶寬（Available Link BandWidth，ALBW）。LLECC策略就是通過對變化的無線網絡鏈路通過虛擬化量化的方式計算出該移動節點的實際有效鏈路的帶寬。

某一移動節點的有效鏈路帶寬是該節點所有輸出鏈路中的每一條輸出鏈路標準帶寬LBWi與帶寬因子[βi]的乘積之和：

[ALBW=iβi×LBWi] （1）

其中[βi=ΔT成功傳輸的分組數ΔT傳輸總分組數，]由該鏈路的實際傳輸狀態決定。

（2） 鏈路負載估算

LLECC策略通過鏈路負載估算計算出該節點實際可能的鏈路負載，具體計算方法如下：

[φ（s，d）=（s，d）pl（s，d）P（s，d）×B（s，d）]

式中：[pl（s，d）]表示節點對[（s，d）]間通過本節點鏈路[L]的路徑數；[P（s，d）]表示節點對[（s，d）]通過本節點鏈路[L]的總路徑數，[B（s，d）]表示節點對[（s，d）]之間的業務流量；[φ（s，d）]表示節點對[（s，d）]間通過本節點鏈路[L]的實際業務流量。

[LL=φ（s，d）] （2）

式中LL表示通過本節點的實際估算流量。通過以上2個公式就可對通過本節點的實際可能負載進行估算。鏈路負載估算取決于本節點采用的路由算法，通過路由算法可計算出通過某一無線鏈路的負載。但本算法適應于任何路由協議（如采用最短路徑協議，[P（s，d）]=1，[pl（s，d）]=1或0；如采用負載均衡協議[P（s，d）]=實際路徑數，[pl（s，d）]=通過本節點的鏈路數）。

（3） 調整因子

通過計算的有效鏈路帶寬和鏈路負載估算就可以確定RED算法的調整因子：

[α=LLALBW] （3）

（4） RED參數的確定

確定RED算法的參數：

當[α1，][minth，][maxth]不變，[Pmax=α?Pmax；]

當[α>1，][minth=][α?minth，][maxth=α?maxth，Pmax=α?Pmax；]

（4）

通過確定的RED參數對移動節點中的數據進行擁塞控制。

2.2 LLCEE算法討論

LLCEE算法主要用于解決無線Mesh網絡由于節點的變化引起鏈路狀態變化所帶來可用網絡資源變化，動態調整RED算法中的擁塞控制參數實施擁塞控制。為使LLCEE算法更適合解決無線網絡的擁塞問題，需注意一下幾點：

（1） 有效鏈路帶寬ALBW。在無線網絡中物理層包括多種傳輸技術（如：定向天線、智能天線、TDM、FDM、OFDM等），網絡中每一個鏈路的傳輸帶寬各不相同；同時在無線網絡中無線信號存在多種衰減，致使節點距離和移動性成為影響節點間可靠傳輸的重要因素，導致該信道的實際可利用的帶寬下降。LLECC算法通過[ΔT]時間間隔內正確傳輸的數據比例帶寬因子[βi]作為衡量該信道可用帶寬惟一依據，能反映該信道的實際情況。同時[ΔT]時間間隔設置不宜太長（無法及時反映信道現狀）或太短（易受瞬時干擾的影響，不利于系統穩定），可以根據網絡管理員的偏好設定，建議在0.1～1 s之間取值。