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

任金霞，溫春暉，王水泉

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

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

任金霞，溫春暉，王水泉

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

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

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

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

1 傳統(tǒng)RED算法

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

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

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

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

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

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

2.1基于模糊控制的RED算法

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

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

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

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

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

qavg=(1-wq)qavg+qwq

(1)

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

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

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

(2)

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

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

(3)

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

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

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

Q={很長(zhǎng)、長(zhǎng)、中等、短、很短}={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ì)列長(zhǎng)度Q和輸出量丟棄概率P的模糊論域?yàn)閧0,2,4,6,8,10,12,14,16}，平均隊(duì)列長(zhǎng)度變化率VQ和延時(shí)D的模糊論域?yàn)閧0,0.2,0.4,0.6,0.8,1,1.2,1.4，1.6}。其隸屬度函數(shù)為三角形隸屬函數(shù)，以平均隊(duì)列長(zhǎng)度Q的隸屬函數(shù)曲線為例，如圖2所示。

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

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

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

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

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

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

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

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

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

(4)

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

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

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

p=p+αdin，α>1

(5)

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

p=p+βdde，β>1

(6)

其中β為隊(duì)列空閑時(shí)的調(diào)節(jié)系數(shù)，雖然隊(duì)列長(zhǎng)度大于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個(gè)FTP傳輸源組成，這些節(jié)點(diǎn)到達(dá)節(jié)點(diǎn)A之間的帶寬均為10 Mb/s,延時(shí)均為5 ms,節(jié)點(diǎn)A、B之間的鏈路帶寬為15 Mb/s,延時(shí)為5 ms，節(jié)點(diǎn)B、C之間的的鏈路帶寬為45 Mb/s，在大時(shí)滯環(huán)境下時(shí)，時(shí)延為220 ms。

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

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

(1)隊(duì)列長(zhǎng)度

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

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

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

(2)丟包率

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

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

4 結(jié)論

本文針對(duì)傳統(tǒng)RED在FTP突發(fā)較強(qiáng)或大時(shí)滯網(wǎng)絡(luò)環(huán)境下不能得到較滿意的吞吐量這一問(wèn)題，提出基于模糊控制理論參數(shù)自適應(yīng)RED優(yōu)化算法。仿真結(jié)果表明該算法較傳統(tǒng)算法相隊(duì)列長(zhǎng)度的波動(dòng)更加穩(wěn)定，同時(shí)，增強(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)的主動(dò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)化算法。