無線Mesh網(wǎng)絡(luò)中基于鏈路負(fù)載估算的擁塞控制策略

夏漢鑄+劉輝元

摘 要： 針對(duì)無線Mesh網(wǎng)絡(luò)的網(wǎng)絡(luò)特性，提出了一種基于鏈路負(fù)載估算的擁塞控制策略LLECC。LLECC算法計(jì)算有效鏈路帶寬和鏈路負(fù)載估算確定RED算法中的調(diào)整因子，通過調(diào)整因子調(diào)整RED算法中的參數(shù)從而實(shí)現(xiàn)動(dòng)態(tài)的對(duì)無線網(wǎng)絡(luò)擁塞控制。詳細(xì)討論了LLECC算法的實(shí)現(xiàn)過程和相關(guān)參數(shù)的計(jì)算方法，通過仿真分析驗(yàn)證了該算法對(duì)無線Mesh網(wǎng)絡(luò)性能的提高。

關(guān)鍵詞： 無線Mesh網(wǎng)絡(luò)； 有效鏈路帶寬； 鏈路負(fù)載估算； 擁塞控制； RED算法

中圖分類號(hào)： TN711?34； TP393 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 引 言

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展和應(yīng)用，用戶對(duì)網(wǎng)絡(luò)的帶寬、移動(dòng)性和可靠性要求越來越高。無線Mesh網(wǎng)絡(luò)WMN[1?3]（Wireless Mesh Networks）融合了WLAN網(wǎng)絡(luò)和Ad hoc網(wǎng)絡(luò)的技術(shù)特點(diǎn)，希望為用戶提供可靠的高速寬帶無線網(wǎng)絡(luò)服務(wù)。多信道WMN允許多個(gè)不重疊的信道可以同時(shí)傳輸數(shù)據(jù)，這樣就能滿足無線Mesh網(wǎng)絡(luò)對(duì)帶寬資源的要求。

在WMN中，移動(dòng)節(jié)點(diǎn)獨(dú)立的爭用無線網(wǎng)絡(luò)資源，不考慮其他移動(dòng)節(jié)點(diǎn)的實(shí)際狀態(tài)，這樣就會(huì)導(dǎo)致某一節(jié)點(diǎn)往無線網(wǎng)絡(luò)中大量發(fā)送數(shù)據(jù)，可能導(dǎo)致無線網(wǎng)絡(luò)擁塞的情況出現(xiàn)[4?7]。一旦無線網(wǎng)絡(luò)出現(xiàn)擁塞，勢必導(dǎo)致無線網(wǎng)絡(luò)中大量的數(shù)據(jù)丟失和重傳，嚴(yán)重影響無線網(wǎng)絡(luò)的網(wǎng)絡(luò)性能。而高層的擁塞控制策略（如TCP中的滑動(dòng)窗口）無法滿足無線Mesh網(wǎng)絡(luò)擁塞控制的要求，無線網(wǎng)絡(luò)中移動(dòng)節(jié)點(diǎn)的擁塞控制策略就變得極為重要。

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

本文對(duì)RED算法進(jìn)行了詳細(xì)的分析，對(duì)WMN中的有效鏈路帶寬和鏈路負(fù)載估算的重要性進(jìn)行了分析，提出了一種基于鏈路負(fù)載估算的擁塞控制策略LLECC（Link?Load?Estimation?based Congestion Control）。LLECC算法通過對(duì)WMN中的鏈路帶寬和鏈路負(fù)載估算值動(dòng)態(tài)地調(diào)整RED算法中的[minth，][maxth，][Pmax]三個(gè)參數(shù)實(shí)現(xiàn)網(wǎng)絡(luò)中的動(dòng)態(tài)擁塞控制。從該策略的實(shí)現(xiàn)過程和仿真結(jié)果來看，LLECC可以對(duì)WMN的擁塞程度做出相應(yīng)的速率控制策略，而且能夠提高無線網(wǎng)絡(luò)的性能和不同業(yè)務(wù)的QoS保證。

1 RED算法

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

RED算法采用低通濾波器模型來計(jì)算平均隊(duì)列長度，突發(fā)業(yè)務(wù)對(duì)隊(duì)列的長度會(huì)導(dǎo)致隊(duì)列長度的短期增加，不會(huì)過大的影響平均隊(duì)列長度。

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

即：

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

式中：avg為平均隊(duì)列長度；[wq]為權(quán)值；[Q]為當(dāng)前隊(duì)列長度。

當(dāng)一個(gè)分組到達(dá)隊(duì)列[Q]時(shí)，通過計(jì)算標(biāo)記丟棄概率來決定該分組被丟棄的可能性。

當(dāng)[avgminth，][Pd]=0，該分組不被丟棄，直接進(jìn)入到隊(duì)列中；

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

當(dāng)[avgmaxth，][Pd]=1，該分組將直接被丟棄。

2 LLCEE擁塞控制策略

在無線Mesh網(wǎng)絡(luò)中，由于用戶的移動(dòng)性、網(wǎng)絡(luò)鏈路質(zhì)量及網(wǎng)絡(luò)擁塞水平等因素導(dǎo)致在無線網(wǎng)絡(luò)環(huán)境下的擁塞控制策略極為復(fù)雜。LLCEE擁塞控制算法通過對(duì)WMN中的鏈路帶寬和鏈路負(fù)載估算值動(dòng)態(tài)地調(diào)整RED算法中的[minth、][maxth、][Pmax]三個(gè)參數(shù)實(shí)現(xiàn)網(wǎng)絡(luò)中的擁塞控制。

2.1 LLCEE算法實(shí)現(xiàn)

LLCEE擁塞控制算法通過4個(gè)過程來實(shí)現(xiàn)無線網(wǎng)絡(luò)的擁塞控制：計(jì)算鏈路的有效帶寬；對(duì)本節(jié)點(diǎn)的鏈路負(fù)載進(jìn)行估算；通過以上2個(gè)計(jì)算結(jié)果確定調(diào)整因子[α；]通過調(diào)整因子[α]值確定RED算法中的參數(shù)[minth、][maxth、][Pmax]實(shí)現(xiàn)本移動(dòng)節(jié)點(diǎn)的擁塞控制。本算法的實(shí)現(xiàn)過程如圖1所示，偽代碼如下：

初始化參數(shù)：

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

經(jīng)過ΔT時(shí)間間隔

用公式（1）計(jì)算 有效鏈路帶寬

用公式（2）計(jì)算 鏈路負(fù)載估算

用公式（3）計(jì)算 調(diào)整因子

用公式（4）計(jì)算 minth，maxth，Pmax

時(shí)刻t，某一分組到達(dá)每一隊(duì)列：

if avg≤minth Pd=0

else if （minth≤avg≤maxth） 計(jì)算Pd

else Pd=1

根據(jù)Pd決定該分組插入隊(duì)列或丟棄

圖1 LLCEE算法流程圖

（1） 有效鏈路帶寬的計(jì)算

在多信道無線Mesh網(wǎng)絡(luò)中，由于節(jié)點(diǎn)的移動(dòng)性和設(shè)備的差異性等因素的影響導(dǎo)致無線信道的實(shí)際有效帶寬與系統(tǒng)表明的標(biāo)準(zhǔn)帶寬存在一定的差異（如由于網(wǎng)絡(luò)信號(hào)的衰減導(dǎo)致信號(hào)傳輸出現(xiàn)誤碼），而無線網(wǎng)絡(luò)中擁塞控制策略必須準(zhǔn)確的知道本節(jié)點(diǎn)實(shí)際可用帶寬資源，也就是有效鏈路帶寬（Available Link BandWidth，ALBW）。LLECC策略就是通過對(duì)變化的無線網(wǎng)絡(luò)鏈路通過虛擬化量化的方式計(jì)算出該移動(dòng)節(jié)點(diǎn)的實(shí)際有效鏈路的帶寬。

某一移動(dòng)節(jié)點(diǎn)的有效鏈路帶寬是該節(jié)點(diǎn)所有輸出鏈路中的每一條輸出鏈路標(biāo)準(zhǔn)帶寬LBWi與帶寬因子[βi]的乘積之和：

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

其中[βi=ΔT成功傳輸?shù)姆纸M數(shù)ΔT傳輸總分組數(shù)，]由該鏈路的實(shí)際傳輸狀態(tài)決定。

（2） 鏈路負(fù)載估算

LLECC策略通過鏈路負(fù)載估算計(jì)算出該節(jié)點(diǎn)實(shí)際可能的鏈路負(fù)載，具體計(jì)算方法如下：

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

式中：[pl（s，d）]表示節(jié)點(diǎn)對(duì)[（s，d）]間通過本節(jié)點(diǎn)鏈路[L]的路徑數(shù)；[P（s，d）]表示節(jié)點(diǎn)對(duì)[（s，d）]通過本節(jié)點(diǎn)鏈路[L]的總路徑數(shù)，[B（s，d）]表示節(jié)點(diǎn)對(duì)[（s，d）]之間的業(yè)務(wù)流量；[φ（s，d）]表示節(jié)點(diǎn)對(duì)[（s，d）]間通過本節(jié)點(diǎn)鏈路[L]的實(shí)際業(yè)務(wù)流量。

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

式中LL表示通過本節(jié)點(diǎn)的實(shí)際估算流量。通過以上2個(gè)公式就可對(duì)通過本節(jié)點(diǎn)的實(shí)際可能負(fù)載進(jìn)行估算。鏈路負(fù)載估算取決于本節(jié)點(diǎn)采用的路由算法，通過路由算法可計(jì)算出通過某一無線鏈路的負(fù)載。但本算法適應(yīng)于任何路由協(xié)議（如采用最短路徑協(xié)議，[P（s，d）]=1，[pl（s，d）]=1或0；如采用負(fù)載均衡協(xié)議[P（s，d）]=實(shí)際路徑數(shù)，[pl（s，d）]=通過本節(jié)點(diǎn)的鏈路數(shù)）。

（3） 調(diào)整因子

通過計(jì)算的有效鏈路帶寬和鏈路負(fù)載估算就可以確定RED算法的調(diào)整因子：

[α=LLALBW] （3）

（4） RED參數(shù)的確定

確定RED算法的參數(shù)：

當(dāng)[α1，][minth，][maxth]不變，[Pmax=α?Pmax；]

當(dāng)[α>1，][minth=][α?minth，][maxth=α?maxth，Pmax=α?Pmax；]

（4）

通過確定的RED參數(shù)對(duì)移動(dòng)節(jié)點(diǎn)中的數(shù)據(jù)進(jìn)行擁塞控制。

2.2 LLCEE算法討論

LLCEE算法主要用于解決無線Mesh網(wǎng)絡(luò)由于節(jié)點(diǎn)的變化引起鏈路狀態(tài)變化所帶來可用網(wǎng)絡(luò)資源變化，動(dòng)態(tài)調(diào)整RED算法中的擁塞控制參數(shù)實(shí)施擁塞控制。為使LLCEE算法更適合解決無線網(wǎng)絡(luò)的擁塞問題，需注意一下幾點(diǎn)：

（1） 有效鏈路帶寬ALBW。在無線網(wǎng)絡(luò)中物理層包括多種傳輸技術(shù)（如：定向天線、智能天線、TDM、FDM、OFDM等），網(wǎng)絡(luò)中每一個(gè)鏈路的傳輸帶寬各不相同；同時(shí)在無線網(wǎng)絡(luò)中無線信號(hào)存在多種衰減，致使節(jié)點(diǎn)距離和移動(dòng)性成為影響節(jié)點(diǎn)間可靠傳輸?shù)闹匾蛩?，?dǎo)致該信道的實(shí)際可利用的帶寬下降。LLECC算法通過[ΔT]時(shí)間間隔內(nèi)正確傳輸?shù)臄?shù)據(jù)比例帶寬因子[βi]作為衡量該信道可用帶寬惟一依據(jù)，能反映該信道的實(shí)際情況。同時(shí)[ΔT]時(shí)間間隔設(shè)置不宜太長（無法及時(shí)反映信道現(xiàn)狀）或太短（易受瞬時(shí)干擾的影響，不利于系統(tǒng)穩(wěn)定），可以根據(jù)網(wǎng)絡(luò)管理員的偏好設(shè)定，建議在0.1～1 s之間取值。