一種基于模糊控制的參數(shù)自適應(yīng)RED改進(jìn)算法*

任金霞，溫春暉，王水泉

(江西理工大學(xué) 電氣工程與自動化學(xué)院，江西 贛州 341000)

一種基于模糊控制的參數(shù)自適應(yīng)RED改進(jìn)算法*

任金霞，溫春暉，王水泉

(江西理工大學(xué) 電氣工程與自動化學(xué)院，江西 贛州 341000)

考慮到傳統(tǒng)隨機(jī)早期檢測(Random Early Detection,RED)算法在較強(qiáng)的業(yè)務(wù)突發(fā)度和較大流量抖動的情況下很難獲得令人滿意的吞吐量這一問題，基于模糊控制理論設(shè)計(jì)了一個模糊控制器，以提高系統(tǒng)在減少隊(duì)列長度、降低丟包率中的作用。同時由于在網(wǎng)絡(luò)擁塞控制中傳統(tǒng)RED算法存在著參數(shù)敏感、穩(wěn)定性差等問題，故在系統(tǒng)中加入一個參數(shù)自適應(yīng)算法，用來穩(wěn)定隊(duì)列長度。仿真結(jié)果表明該算法在減少隊(duì)列長度、降低丟包率、提高魯棒性方面的優(yōu)化有著明顯的效果。

擁塞控制;模糊控制;RED算法;自適應(yīng)

Abstract: Considering the problem that the traditional Random Early Detection (RED) algorithm in the stronger business under the condition of sudden and large flow jitter is difficult to obtain satisfying throughput, this article designs a fuzzy controller to improve the system performance in reduce the queue length and the reduce packet loss rate based on fuzzy control theory. At the same time, due to network congestion control in traditional RED algorithm has sensitive parameters baol instability, this paper introduces a parameter adaptive algorithm to the system to stabilize the queue length. The simulation results show that the algorithm has obvious effect in reducing queue length, reducing the packet loss rate, and improving the robustness of optimization.

Key words:congestion control; fuzzy controller; RED algorithm; self-adaptive

0 引言

主動隊(duì)列管理(Active Queue Management，AQM)是基于路由器的擁塞控制領(lǐng)域的研究熱點(diǎn)之一[1]。典型的AQM機(jī)制是隨機(jī)早期檢測(Random Early Detection，RED)算法[2]，RED算法根據(jù)平均隊(duì)列長度估計(jì)值，按概率隨機(jī)丟棄分組，實(shí)現(xiàn)早期擁塞通知，在保持高吞吐率和低延時的同時，能夠容納一定的突發(fā)數(shù)據(jù)[3]。RED算法對參數(shù)的設(shè)置異常敏感，同時隨著網(wǎng)絡(luò)的連接數(shù)增加，隊(duì)列長度變長，這會增加中間節(jié)點(diǎn)的延時，對一些網(wǎng)絡(luò)業(yè)務(wù)產(chǎn)生一定的影響[4]。所以有PI、PID、PD控制器廣泛用于AQM設(shè)計(jì)中，以求獲得更好的網(wǎng)絡(luò)性能。隨著智能控制理論的發(fā)展，將智能控制理論應(yīng)用于主動隊(duì)列管理(AQM)算法中也有了新的嘗試和突破。

基于以上分析，本文提出一種基于模糊邏輯的參數(shù)自適應(yīng)RED優(yōu)化算法設(shè)計(jì)。算法在傳統(tǒng)RED算法中加入改進(jìn)的模糊控制器，該模糊控制器可以根據(jù)當(dāng)前網(wǎng)絡(luò)流的狀況動態(tài)地推出數(shù)據(jù)包的丟棄率，同時由于加入了參數(shù)自適應(yīng)算法使得算法系統(tǒng)的性能得到提升，在降低隊(duì)列長度和丟包率的同時，其魯棒性也得到提高[5]。該算法在理論上可以獲得較低的丟包率，同時增加網(wǎng)絡(luò)吞吐量和減少延時，從而增加網(wǎng)絡(luò)服務(wù)性能[6]。

1 傳統(tǒng)RED算法

RED算法是最早也是最著名的一個有效緩解網(wǎng)絡(luò)擁塞的算法，RED算法通過網(wǎng)絡(luò)鏈路中的平均隊(duì)列長度大小來確定網(wǎng)絡(luò)運(yùn)行狀態(tài)以及判斷有無網(wǎng)絡(luò)擁塞的出現(xiàn)。當(dāng)平均隊(duì)列長度接近或達(dá)到設(shè)定的最大閾值時，說明網(wǎng)絡(luò)中發(fā)生了擁塞，這時發(fā)送端節(jié)點(diǎn)將收到擁塞信號，同時降低數(shù)據(jù)發(fā)送的速率，以達(dá)到緩解擁塞的效果。也就是RED算法是通過丟棄路由器中間節(jié)點(diǎn)中的緩存數(shù)據(jù)包來緩解擁塞。RED早期檢測的設(shè)計(jì)主要解決如下兩個問題[7]：

(1)降低丟包率和延時；

(2)提高網(wǎng)絡(luò)資源的利用率以及提供較高的鏈路利用率。

RED算法中平均隊(duì)列長度是根據(jù)時間的變化發(fā)生變化的，并在擁塞發(fā)生的臨近期就會對鏈路中的數(shù)據(jù)包進(jìn)行隨機(jī)性丟棄，這樣既有效降低了網(wǎng)絡(luò)時延，又給算法的有效運(yùn)行提供了保障，使網(wǎng)絡(luò)的運(yùn)行更有效率。

2 基于模糊控制的參數(shù)自適應(yīng)RED算法

針對傳統(tǒng)RED算法對參數(shù)設(shè)置的敏感性問題，本文在模糊控制理論的基礎(chǔ)上提出一種在丟包發(fā)生之前對丟包率信號進(jìn)行處理的改進(jìn)的RED算法，該算法的結(jié)構(gòu)主要為兩個部分：模糊控制的RED算法和參數(shù)自適應(yīng)的RED算法。該算法的主要思想是加入?yún)?shù)自適應(yīng)算法來保持隊(duì)列的穩(wěn)定性，提高網(wǎng)絡(luò)系統(tǒng)的魯棒性，有效減少隊(duì)列的溢出和空閑。同時以傳統(tǒng)RED算法為基礎(chǔ)，加入一個以路由器中的緩沖區(qū)的平均隊(duì)列長度、平均隊(duì)列長度的變化率、時延作為網(wǎng)絡(luò)擁塞狀態(tài)檢測變量的模糊控制器，文獻(xiàn)[8]在RED算法中設(shè)計(jì)了一個以平均隊(duì)列長度、平均隊(duì)列長度變化率為狀態(tài)檢測變量的模糊控制器。本文在其基礎(chǔ)上多加入一個時延作為控制器輸入?yún)?shù)變量。該模糊控制器在減少丟包損失、降低丟包率上有更好的實(shí)驗(yàn)效果。

2.1基于模糊控制的RED算法

本文在傳統(tǒng)RED算法的基礎(chǔ)上加入一個模糊控制器，該模糊控制器以平均隊(duì)列長度、平均隊(duì)列長度變化率和延時作為輸入變量，通過該模糊控制器可以得到一個改進(jìn)的基于模糊控制的RED算法。

2.1.1模糊控制器的結(jié)構(gòu)

以路由緩沖區(qū)的平均隊(duì)列長度qavg、平均隊(duì)列長度變化Δqavg和時延RTT作為該模糊控制器網(wǎng)絡(luò)擁塞狀態(tài)的三個檢測變量，也是該算法的三個輸入變量，通過模糊控制器得到一個較理想的丟棄概率p。由此根據(jù)這三個輸入變量，本文設(shè)計(jì)的模糊控制RED算法的結(jié)構(gòu)圖如圖1所示。

圖1 模糊控制RED算法結(jié)構(gòu)圖

平均隊(duì)列長度的計(jì)算公式為：

qavg=(1-wq)qavg+qwq

(1)

式中qavg為平均隊(duì)列長度，q表示t時刻的隊(duì)列長度，wq為權(quán)重。

平均隊(duì)列長度變化的計(jì)算公式為：

Δqavg=qavg(t+1)-qavg(t)

(2)

式中：Δqavg為平均隊(duì)列長度變化，qavg(t)為t時刻的平均隊(duì)列長度。

時延的計(jì)算公式為:

(3)

其中RTT是回路時間，qt是緩沖器中的瞬時隊(duì)列長度，ct是鏈路容量，Tp是傳輸延時。

2.1.2模糊控制器的設(shè)計(jì)

考慮到三個變量對丟包率影響，本文把平均隊(duì)列長度、平均隊(duì)列長度變化、時延作為模糊邏輯控制器的輸入，丟包率作為輸出。設(shè)Q、VQ、D、P分別是平均隊(duì)列長度、平均隊(duì)列長度變化、時延和輸出量丟棄概率的模糊變量，其對應(yīng)的模糊語言值分別為:

Q={很長、長、中等、短、很短}={VL、L、M、S、}

VQ={很多、多、中等、少}={Very Lot、Lot、Medium、Few}={VA、A、M、F}

D={低、中等、高、非常高}={Low、Med、High、Very High}={L、M、H、VH}

P={非常少、少、中等、多、非常多}={Very Little、Little、Moderate、Much、Very Much}={VL、L、MD、MC、VMC}。

得到該模糊控制器的模糊規(guī)則如表1所示。

表1 模糊控制規(guī)則

設(shè)平均隊(duì)列長度Q和輸出量丟棄概率P的模糊論域?yàn)閧0,2,4,6,8,10,12,14,16}，平均隊(duì)列長度變化率VQ和延時D的模糊論域?yàn)閧0,0.2,0.4,0.6,0.8,1,1.2,1.4，1.6}。其隸屬度函數(shù)為三角形隸屬函數(shù)，以平均隊(duì)列長度Q的隸屬函數(shù)曲線為例，如圖2所示。

圖2 輸入變量隊(duì)列長度Q的隸屬函數(shù)曲線

其余三個參數(shù)變量的隸屬函數(shù)曲線與平均隊(duì)列長度Q的隸屬函數(shù)曲線類似，本文不一一畫出。

該模糊控制器的規(guī)則可以表示成：

ifQi,VQjandDk, ThenPijk(i=1,2,3,4;j=1,2,3,4;k=1,2,3,4)

本文是通過三個輸入變量即平均隊(duì)列長度、平均隊(duì)列長度變化和時延來控制模糊控制器，經(jīng)過模糊推理、解模糊化得到相對較低的丟包率P。

2.2基于參數(shù)自適應(yīng)的RED算法

由于傳統(tǒng)RED算法網(wǎng)絡(luò)擁塞控制中存在著非線性、參數(shù)時變、穩(wěn)定性等問題，無法有效保證隊(duì)列長度收斂在預(yù)期結(jié)果內(nèi)，為避免隊(duì)列的不穩(wěn)定、溢出或空閑，故本文在模糊控制的基礎(chǔ)上加入了一個參數(shù)自適應(yīng)的算法,用來保持隊(duì)列的穩(wěn)定。

算法借鑒RED算法的早期擁塞檢測機(jī)制，同樣根據(jù)平均隊(duì)列長度的變化來自適應(yīng)地調(diào)節(jié)丟包率，算法給隊(duì)列長度設(shè)定兩個控制閾值Min_th，Max_th。通過平均隊(duì)列長度和兩個控制閾值的比較可以得到以下三種網(wǎng)絡(luò)狀態(tài)。其中平均隊(duì)列長度的計(jì)算公式可通過式(1)來計(jì)算得到。

(1)當(dāng)隊(duì)列長度大于控制閾值Max_th時，隊(duì)列溢出，網(wǎng)絡(luò)處于重載區(qū)，這時需及時增大丟包率P，緩解網(wǎng)絡(luò)擁塞。

(4)

其中α為隊(duì)列溢出的調(diào)節(jié)系數(shù)；din是常量，用來調(diào)節(jié)丟包率P。

(2)當(dāng)隊(duì)列長度小于閾值最小值Min_th時，網(wǎng)絡(luò)處于輕載區(qū)，無需丟包，故丟包率P=0。

(3)當(dāng)隊(duì)列長度在Max_th和Min_th之間時，網(wǎng)絡(luò)狀態(tài)穩(wěn)定，隊(duì)列長度也較穩(wěn)定故無需較大改變丟包參數(shù)。

p=p+αdin，α>1

(5)

(5)為了防止空隊(duì)列的出現(xiàn)，當(dāng)鏈路空閑且隊(duì)列長度大于閾值最大值Max_th時有：

p=p+βdde，β>1

(6)

其中β為隊(duì)列空閑時的調(diào)節(jié)系數(shù)，雖然隊(duì)列長度大于Max_th，但因?yàn)殛?duì)列是空閑的，所以網(wǎng)絡(luò)也是處于輕載區(qū)，同樣采取較緩和的小概率丟包策略。算法實(shí)現(xiàn)可以參考文獻(xiàn)[9]。

3 仿真與分析

本文算法的一些參數(shù)設(shè)置:Min_th=80,Max_th=180,wq=0.002,α=3,β=2，其余參數(shù)設(shè)置同默認(rèn)RED算法。采用如圖3所示的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，由圖可知網(wǎng)絡(luò)由n個FTP傳輸源組成，這些節(jié)點(diǎn)到達(dá)節(jié)點(diǎn)A之間的帶寬均為10 Mb/s,延時均為5 ms,節(jié)點(diǎn)A、B之間的鏈路帶寬為15 Mb/s,延時為5 ms，節(jié)點(diǎn)B、C之間的的鏈路帶寬為45 Mb/s，在大時滯環(huán)境下時，時延為220 ms。

圖3 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

本文通過ns-2網(wǎng)絡(luò)模擬仿真軟件來驗(yàn)證本文模糊控制的RED優(yōu)化算法的優(yōu)越性，從隊(duì)列長度、丟包率兩方面將本文算法與傳統(tǒng)算法進(jìn)行對比分析，仿真結(jié)果如下。

(1)隊(duì)列長度

實(shí)驗(yàn)仿真結(jié)果的對比如圖4、圖5所示，可以看出改進(jìn)的模糊RED算法隊(duì)列長度明顯降低了，同時具有較原始RED算法有更高的鏈路利用率，更好地保持了隊(duì)列長度的穩(wěn)定性，具有更高的魯棒性。

圖4 傳統(tǒng)RED算法隊(duì)列長度

圖5 改進(jìn)的模糊RED算法隊(duì)列長度

(2)丟包率

為了較為全面地衡量本算法的性能，給出兩種算法的網(wǎng)絡(luò)數(shù)據(jù)丟包率分析對比情況如圖6所示。可以看出在前4 s時兩種算法丟包率相差不大，隨著時間的增加雖然兩種算法丟包率均呈上升趨勢，但本文提出算法的丟包上升坡度較原始算法相對平緩，丟包率整體小于原始算法，說明本算法在網(wǎng)絡(luò)的數(shù)據(jù)丟包率方面較原始算法有一定提升。

圖6 網(wǎng)絡(luò)數(shù)據(jù)丟包率

4 結(jié)論

本文針對傳統(tǒng)RED在FTP突發(fā)較強(qiáng)或大時滯網(wǎng)絡(luò)環(huán)境下不能得到較滿意的吞吐量這一問題，提出基于模糊控制理論參數(shù)自適應(yīng)RED優(yōu)化算法。仿真結(jié)果表明該算法較傳統(tǒng)算法相隊(duì)列長度的波動更加穩(wěn)定，同時，增強(qiáng)了網(wǎng)絡(luò)系統(tǒng)的魯棒性，提高了鏈路利用率，降低了數(shù)據(jù)傳輸?shù)膩G包率。

[1] Liu Weiyan, Zhang Shunyi, Zhang Mu, et al. A fuzzy-logic control algorithm for active Queue Management in IP networks[J]. Journal of Electronics (China), 2008, 25(1):102-107.

[2] NASSAR K A, ABDULLAH A A. Fuzzy RED to reduce packet loss in computer network[J]. Journal of Qadisiyah Computer Science and Mathematics, 2016, 8(1):107-114.

[3] Ren Fengyuan, Ren Yong, Shan Xiuming. Design of a fuzzy controller for active queue management[J]. Computer Communications, 2002, 25(9):874-883.

[4] 黃迎春,李向麗,邱保志.一種改進(jìn)的RED算法[J].計(jì)算機(jī)工程,2007, 33(1):117-121.

[5] ABBASOV B, KORUKOGLU S. Effective RED: an algorithm to improve RED’s performance by reducing packet loss rate[J]. Journal of Network and Computer Applications, 2009, 32(3):703-709.

[6] 黃海利，王曉喃.一種基于UDP的擁塞控制方案[J].電子技術(shù)應(yīng)用，2013,39(1)：109-115.

[7] RASTOGI S, ZAHEER H. Comparative analysis of queuing mechanisms: Droptail, RED and NLRED[J]. Social Network Analysis and Mining, 2016, 6(1):123-232.

[8] 李文帥,張忠林,徐洞成.基于模糊控制理論的RED改進(jìn)算法[J].空軍雷達(dá)學(xué)院學(xué)報(bào),2009, 23(2):124-126.

[9] 劉偉彥，孫雁飛，張順頤，等.一種參數(shù)自適應(yīng)的主動隊(duì)列管理算法——自適應(yīng)BLUE[J].電子與信息學(xué)報(bào),2009,31(2)：462-466.

An improved parameter adaptive RED algorithm based on fuzzy control

Ren Jinxia, Wen Chunhui , Wang Shuiquan

(School of Electrical Engineering and Automation,Jiangxi University of Science and Technology, Ganzhou 341000, China)

TP393

A

10.19358/j.issn.1674- 7720.2017.18.023

任金霞，溫春暉，王水泉.一種基于模糊控制的參數(shù)自適應(yīng)RED改進(jìn)算法[J].微型機(jī)與應(yīng)用，2017,36(18)：77-79,83.

江西省自然科學(xué)基金項(xiàng)目(20151BAB207041)

2017-02-28)

任金霞(1970-),通信作者,女，碩士，副教授，主要研究方向: 智能控制、機(jī)器學(xué)習(xí)。E-mail:dxzghyqq@sina.com。

溫春暉(1992-),男,碩士研究生,主要研究方向:智能優(yōu)化算法。

王水泉(1991-),男,碩士研究生,主要研究方向:計(jì)算機(jī)網(wǎng)絡(luò)、優(yōu)化算法。