彭亦飛 ，張英杰

(1. 邵陽(yáng)學(xué)院 信息工程系，湖南 邵陽(yáng)，422000；2. 湖南大學(xué) 計(jì)算機(jī)與通信學(xué)院，湖南 長(zhǎng)沙，410082)

主動(dòng)隊(duì)列管理(Active queue management, AQM)是一種基于路由器的擁塞控制機(jī)制，是一種端到端的擁塞控制手段，既可減小排隊(duì)時(shí)延，又可保證較高的吞吐量，從而達(dá)到抑制擁塞的目的[1]。近年來(lái)，主動(dòng)隊(duì)列管理技術(shù)業(yè)已成為網(wǎng)絡(luò)研究領(lǐng)域中的焦點(diǎn)，相關(guān)研究人員進(jìn)行了一些研究與探索，提出多種AQM算法，如RED[2]，ARED[3]和SRED[4]等。與此同時(shí)，人們也研究出一些基于網(wǎng)絡(luò)流量的控制模型[5]，其中最具有影響力的是Misra等[6]于2000年提出的一種基于流體流理論的網(wǎng)絡(luò)模型，該模型較準(zhǔn)確地描述了TCP傳輸?shù)男袨?。此外，人們將控制理論方法?yīng)用于網(wǎng)絡(luò)擁塞控制，在現(xiàn)實(shí)工業(yè)領(lǐng)域中應(yīng)用率最廣的PID控制逐漸被應(yīng)用到網(wǎng)絡(luò)主動(dòng)隊(duì)列管理控制中，產(chǎn)生了PID[7]等主動(dòng)隊(duì)列管理算法，加強(qiáng)隊(duì)列長(zhǎng)度的控制能力，具有讓人滿意的暫態(tài)響應(yīng)和較小的穩(wěn)態(tài)誤差，然而，PID控制器參數(shù)的整定比較困難。PID控制器的參數(shù)整定與優(yōu)化已成為控制界研究的焦點(diǎn)。粒子群算法(Particle swarm optimization, PSO)是由Kennedy等于 1995年提出的一種基于群體智能的全局優(yōu)化進(jìn)化算法[8]，它源于對(duì)鳥(niǎo)類捕食行為的模擬。目前該算法已經(jīng)成功地應(yīng)用于函數(shù)參數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、模糊系統(tǒng)控制優(yōu)化等領(lǐng)域[9]。由于粒子群自身不具備變異能力，隨著進(jìn)化的進(jìn)行，粒子群算法容易陷入局部極值點(diǎn)。人工免疫系統(tǒng)是基于高等脊椎生物免疫系統(tǒng)機(jī)理發(fā)展而來(lái)的，它是人工智能研究的一個(gè)新領(lǐng)域[10-11]，具有多樣性好、變異能力強(qiáng)、克隆復(fù)制與記憶力強(qiáng)等功能，使算法最終能逃逸出局部最優(yōu)解，獲得全局最優(yōu)理想解。在此，本文作者基于以上分析，在流體理論的網(wǎng)絡(luò)簡(jiǎn)化模型基礎(chǔ)上，將PID控制器應(yīng)用于計(jì)算機(jī)網(wǎng)絡(luò)AQM中，應(yīng)用免疫雜交粒子群算法，對(duì)控制器參數(shù)進(jìn)行組合優(yōu)化；在給定的搜索空間找到使性能指標(biāo)優(yōu)化函數(shù)極小化的一組PID控制器參數(shù)，構(gòu)造一種基于免疫雜交粒子群算子的網(wǎng)絡(luò)擁塞PID控制。

1 TCP/AQM模型

Misra等[11]基于流體流(Fluid flow)理論建立了AQM作用下TCP連接擁塞窗口的動(dòng)態(tài)模型。用如下非線性流體流模型來(lái)描述TCP網(wǎng)絡(luò)AQM控制系統(tǒng)：

式中：w(t)為TCP流的窗口大??；q(t)為瞬時(shí)隊(duì)列長(zhǎng)度；TP為傳播時(shí)延；R=q/C+TP，為傳輸 RTT(Round-trip time，往返時(shí)延)；C為鏈路容量；N為TCP連接數(shù)目；p為丟包概率。

式(1)描述了TCP的擁塞窗口調(diào)節(jié)機(jī)制，采用加式增加/乘式減少(AIMD)擁塞控制算法，估計(jì)TCP流的擁塞窗口大小，其中右邊第1項(xiàng)描述了AIMD的加式增加部分，若沒(méi)有報(bào)文丟失，則每經(jīng)過(guò)一個(gè)RTT，TCP擁塞窗口加1；第2項(xiàng)描述了AIMD的乘式減少部分，當(dāng)檢測(cè)到報(bào)文丟失時(shí)，擁塞窗口減少為原來(lái)的一半。式(2)描述了路由器中隊(duì)列隨時(shí)間變化的模型，瞬時(shí)隊(duì)列長(zhǎng)度 q(t)由報(bào)文到達(dá)速率和鏈路帶寬之間的差值決定。當(dāng)隊(duì)列長(zhǎng)度大于0時(shí)，路由器轉(zhuǎn)發(fā)報(bào)文，隊(duì)列長(zhǎng)度不斷減少；否則，TCP連接發(fā)送報(bào)文到路由器，隊(duì)列長(zhǎng)度累積增大。因?yàn)閬G包概率0＜p＜1，式(1)可由如下具有飽和輸入特性的非線性時(shí)滯微分方程[12]描述：

其中，飽和輸入 ))(()( tRtptu -= 可由如下非線性函數(shù)描述：

飽和下界和上界分別為umin=0和umax=1。

TCP流量AQM控制示意圖見(jiàn)圖1。其中：c(s)為所使用的控制機(jī)制；p(s)代表被控對(duì)象的非時(shí)滯部分；由式(4)可以得出整個(gè)系統(tǒng)的開(kāi)環(huán)傳遞函數(shù)G(s)：

圖1 TCP流量AQM控制示意圖Fig.1 Flow diagram of TCP AQM control

2 PID主動(dòng)隊(duì)列管理算法原理

PID控制器算法是依照誤差的比例、積分、微分進(jìn)行控制，它的輸出值p取決于系統(tǒng)給定值q0和系統(tǒng)輸出值q的偏差e、偏差的積分、偏差的微分的線性加權(quán)組合；PID控制器中3個(gè)參數(shù)ki，kp和kd需要調(diào)整。其控制系統(tǒng)原理如圖2所示?；赑ID的隊(duì)列控制模型如圖3所示。

圖2 PID控制系統(tǒng)原理框圖Fig.2 Diagram of PID control system

圖3 基于PID的隊(duì)列控制模型Fig.3 Queue control model based on PID

用連續(xù)域傳遞函數(shù)形式表述為：

離散形式的增量控制算式為：

基于PID的主動(dòng)隊(duì)列管理算法具有算法簡(jiǎn)單、容易實(shí)現(xiàn)的優(yōu)點(diǎn)，簡(jiǎn)單的線性單變量系統(tǒng)中具有較好的控制效果。但是，對(duì)于復(fù)雜的網(wǎng)絡(luò)非線性系統(tǒng)(如參數(shù)隨時(shí)間變化、隨機(jī)的時(shí)延以及外部隨機(jī)信號(hào)的干擾等)，若PID控制器的參數(shù)難于得到合理配置，不能實(shí)時(shí)在線調(diào)整，則將導(dǎo)致其適應(yīng)性差，影響系統(tǒng)的控制質(zhì)量。于是，引入免疫雜交粒子群算法對(duì)主動(dòng)隊(duì)列管理PID控制器進(jìn)行在線實(shí)時(shí)優(yōu)化，以增強(qiáng)其自適應(yīng)能力。

3 免疫雜交粒子群的 PID主動(dòng)隊(duì)列管理算法

3.1 基本的粒子群優(yōu)化算法

粒子群算法是一種新興的進(jìn)化計(jì)算技術(shù)，它的思想來(lái)源于魚群和鳥(niǎo)群等社會(huì)群體生物的覓食現(xiàn)象，最先由Kennedy和Eberhart提出[13]。粒子群算法具有參數(shù)較少、結(jié)構(gòu)簡(jiǎn)單、易于計(jì)算機(jī)實(shí)現(xiàn)、收斂速度快、群體信息交互能力強(qiáng)等優(yōu)點(diǎn)；在PSO算法中，粒子群在1個(gè)n維的空間中搜索，其中每個(gè)粒子所處的位置都表示問(wèn)題的1個(gè)潛在解。粒子通過(guò)不斷調(diào)整自己的位置X來(lái)搜索新解。每個(gè)粒子都記住自己搜索到的最好解，記作Pid。種群經(jīng)歷過(guò)的最好位置即目前搜索到的最優(yōu)解記作Pgd。每個(gè)粒子都具有1個(gè)速度，記作v，定義為：

其中：vid表示第i個(gè)粒子第d維上的速度，ω為慣性權(quán)重；c1和c2分別為調(diào)節(jié)Pid和Pgd相對(duì)重要性的參數(shù)；rand( )為介于0和1之間的隨機(jī)數(shù)。這樣，可以得到粒子的下一個(gè)位置：

由式(8)和(9)可以看出：粒子的移動(dòng)速度由 3部分(即自己原有的速度 vid、與自己最佳經(jīng)歷的距離(Pid-Xid)和與群體最佳經(jīng)歷的距離(Pgd-Xid))來(lái)決定，并分別由權(quán)重系數(shù)ω，c1和c2來(lái)決定其相對(duì)重要性。

3.2 人工免疫系統(tǒng)

人工免疫系統(tǒng)[14-15]是基于生物免疫系統(tǒng)機(jī)理發(fā)展而來(lái)的。人工免疫系統(tǒng)存在高頻變異、免疫記憶、克隆復(fù)制等優(yōu)勢(shì)，使系統(tǒng)最終能逃逸出局部最優(yōu)解，獲得全局最優(yōu)解。

克隆免疫算法是人工免疫系統(tǒng)中最主要的算法之一，其機(jī)制中存在克隆擴(kuò)增選擇、交叉、超變異、進(jìn)化替代以及局部滅絕5部分?？寺U(kuò)增算子：

其中：β為克隆系數(shù)，一般取小于1.0大于0.5的數(shù)；i為初始群體在按適應(yīng)度排序后染色體所處的序列號(hào)；round為取整操作；Y(k)為克隆擴(kuò)增后的種群規(guī)模。

對(duì)于克隆擴(kuò)增后的子體種群，進(jìn)行概率很高的超變異，以獲得新的個(gè)體。再將變異后的子體與它之前母體的適應(yīng)度進(jìn)行比較，若適應(yīng)度比母體的高，則覆蓋替代母體的基因值；若子體的適應(yīng)度比其母體的低，則不執(zhí)行任何操作。

抗體種群A(k)在克隆選擇算子的作用下演化過(guò)程表示為：

第1步：初始化種群。

I為個(gè)體空間。

第2步：根據(jù)初始化值計(jì)算親合度。

第3步：判斷親合度判斷A(k)中是否有最優(yōu)個(gè)體出現(xiàn)，即是否達(dá)到停止條件(終止條件判斷)，若是，則停止。

第4步：克隆種群，親合度高的克隆數(shù)量多，親合度低的克隆數(shù)量少。

第5步：克隆變異操作。

第6步：計(jì)算變異后的親合度。

第7步：克隆選擇

第8步：計(jì)算親合度。

第9步：k=k+1，返回第3步。

3.3 雜交粒子群優(yōu)化算法

為了更有利于群體間信息進(jìn)行交互，提高群體協(xié)作能力，引用免疫系統(tǒng)中的交叉極值對(duì)微粒群個(gè)體間進(jìn)行交叉。在群體進(jìn)化過(guò)程中隨機(jī)兩兩粒子進(jìn)行雜交，產(chǎn)生同樣數(shù)目的孩子粒子，并用孩子粒子代替父母粒子，以保持種群的粒子數(shù)目不變。孩子粒子的位置由父母粒子的位置的算數(shù)加權(quán)來(lái)計(jì)算。交叉算子如下：

其中：X為d維的位置向量；X1(t)和X2(t)為選擇進(jìn)行雜交操作的粒子；r為d維均勻分布且每個(gè)分量都在[0, 1]取值的隨機(jī)向量。

孩子粒子的速度分別由下列公式得到：

其中：v1(t)和v2(t)為進(jìn)行雜交操作的粒子速度。

3.4 算法流程

將免疫系統(tǒng)中的克隆選擇、高頻變異、雜交機(jī)制融入粒子群算法中，構(gòu)成一種高效的混合智能算法-免疫雜交粒子群算法。然后，將免疫雜交粒子群算法應(yīng)用于網(wǎng)絡(luò)擁塞PID控制中，對(duì)控制器進(jìn)行優(yōu)化。其流程圖和控制器結(jié)構(gòu)圖分別如圖4和圖5所示。

控制參數(shù)的優(yōu)化目的是使階躍響應(yīng)的控制誤差趨近于 0，有較快的響應(yīng)速度和較小的響應(yīng)誤差。采用誤差絕對(duì)值時(shí)間積分性能指標(biāo)作為參數(shù)選擇的最小目標(biāo)函數(shù)，為了防止控制能量過(guò)大，在目標(biāo)函數(shù)中加入控制輸入的平方項(xiàng)。

圖4 免疫雜交粒子群優(yōu)化方法(ICPSOA)流程Fig.4 Process of immune crossbreeding particle swarm optimization (ICPSOA)

圖5 控制器結(jié)構(gòu)Fig.5 Controller structure

式中：e(t)為系統(tǒng)誤差；u(t)為控制器輸出；tu為上升時(shí)間；w1，w2和w3為權(quán)值。

為了避免超調(diào)，采用懲罰功能，即一旦產(chǎn)生超調(diào)，將超調(diào)作為最優(yōu)指標(biāo)的1項(xiàng)，此時(shí)，最優(yōu)指標(biāo)為：

式中：w3為權(quán)值，且 w4＞＞ w1； yE(t)=yout(t)-yout( t-1)；yout(t)為被控對(duì)象輸出。

4 實(shí)驗(yàn)

為了驗(yàn)證文中提出的算法的有效性，通過(guò)MATLAB實(shí)驗(yàn)仿真進(jìn)行驗(yàn)證。實(shí)驗(yàn)設(shè)置以隊(duì)列長(zhǎng)度能否穩(wěn)定在參考值q0附近為主要觀察目標(biāo)。這是因?yàn)閷㈥?duì)列長(zhǎng)度穩(wěn)定在參考值附近，可以獲得較高的吞吐量、低延時(shí)和低抖動(dòng)。實(shí)驗(yàn)中設(shè)緩沖區(qū)隊(duì)列長(zhǎng)度q=200，參考隊(duì)列長(zhǎng)度q0=150。

實(shí)驗(yàn)Ⅰ：假定網(wǎng)絡(luò)狀況為持續(xù)無(wú)變化的，有固定的TCP連接數(shù)N=60，鏈路容量C=3 750 /s，往返時(shí)間為80 ms，由式(5)可得被控對(duì)象：

其仿真結(jié)果如圖6所示。當(dāng)網(wǎng)絡(luò)條件恒定時(shí)，基于免疫雜交粒子群優(yōu)化方法的 PID(ICPSOA-PID)比普通PID收斂速度更快，ICPSOA-PID的上升速度較快，且超調(diào)量少，誤差??；而基于常規(guī)PID的主動(dòng)隊(duì)列管理具有很明顯的震動(dòng)，且收斂速度慢，有誤差。

實(shí)驗(yàn)Ⅱ：考查在變化的網(wǎng)絡(luò)條件下，比較研究 2種主動(dòng)隊(duì)列管理方法的性能。此時(shí)，TCP連接數(shù)N下降至30，往返時(shí)間為80 ms，鏈路容量C=2 800 /s，仿真結(jié)果如圖7所示。從圖7可見(jiàn)：ICPSOA-PID主動(dòng)隊(duì)列管理算法較常規(guī)PID主動(dòng)隊(duì)列管理算法更快地收斂于參考值 150。這是由于免疫雜交粒子群算法(ICPSOA)全局尋優(yōu)能力強(qiáng)，基于免疫雜交粒子群算法(ICPSOA)優(yōu)化的PID具有更快的響應(yīng)速度，自適應(yīng)能力強(qiáng)，適應(yīng)于實(shí)時(shí)動(dòng)態(tài)系統(tǒng)控制；同時(shí)，ICPSOA-PID較常規(guī)PID算法能夠更快地適應(yīng)網(wǎng)絡(luò)條件的變化，提高了適應(yīng)性和實(shí)時(shí)性。

圖6 實(shí)驗(yàn)1仿真結(jié)果Fig.6 Simulation results of Experiment Ⅰ

圖7 實(shí)驗(yàn)2仿真結(jié)果Fig.7 Simulation results of Experiment Ⅱ

實(shí)驗(yàn)Ⅲ：考查在變化的網(wǎng)絡(luò)條件下，比較研究多種主動(dòng)隊(duì)列管理方法的性能。此時(shí)，TCP連接數(shù)N下降為40，往返時(shí)間為90 ms，鏈路容量C=2 900 /s。其實(shí)驗(yàn)比較結(jié)果如表1所示。

表1 多種AQM算法性能比較Table 1 Performance comparisons of AQM

表1中：RED[2]為早期隨機(jī)檢測(cè)方法，PI為比例積分方法，PPI[16]為預(yù)測(cè)PI控制方法。從表1可以看出：文中ICPSOA-PID在隊(duì)列長(zhǎng)度、標(biāo)準(zhǔn)差、吞吐率及其丟棄率均比其他3種方法的優(yōu)。

5 結(jié)論

(1) 提出的一種免疫雜交粒子群算法提高了算法的全局尋優(yōu)能力。

(2) 構(gòu)造了一種基于免疫雜交粒子群的智能主動(dòng)隊(duì)列PID算法。免疫雜交粒子群算法對(duì)PID控制器參數(shù)進(jìn)行優(yōu)化，提高了PID控制器的自適應(yīng)能力。

(3) 免疫雜交粒子群算法具有較強(qiáng)的全局優(yōu)化能力；基于免疫雜交粒子群的PID主動(dòng)隊(duì)列管理算法能夠適應(yīng)動(dòng)態(tài)變化的網(wǎng)絡(luò)環(huán)境，與常規(guī)PID相比具有較好的網(wǎng)絡(luò)控制性能。

[1] RFC 2309. Recommendations on queue management and congestion avoidance in the Internet[S].

[2] Christiansen M, Jeffay K, Ott D, et al. Turing RED for traffic[J].ACM Computer Communication Review, 2000, 30(4): 139-150.[3] Feng W, Kandlur D, Saha D, et al. A self-configuration RED gateway[C]//Proceedings of the INFOCOMp99. New York:IEEE Computer Society, 1999: 1320-1328.

[4] Ott T J, Lakshman T V, Wong L H. SRED: Stabilized RED[C]//Proceedings of the INFOCOMp99. New York: IEEE Computer Society, 1999: 1346-1355.

[5] 陸錦軍, 王執(zhí)銓. 基于粒子群優(yōu)化的網(wǎng)絡(luò)擁塞控制新算法[J].電子學(xué)報(bào), 2007, 35(8): 1446-1451.LU Jin-jun, WANG Zhi-quan. A new network cogestion control algorithm based on particle swarm optimization[J]. Acta Electronical Sinica, 2007, 35(8): 1446-1451.

[6] Misra V, Gong W B, Towsley D. Fluid-based analysis of a network of AQM routers supporting TCP flows with an application to RED[C]//Proc ACM/SIGCOMM. Stockholm,2000: 151-160.

[7] 楊吉文, 顧誕英, 張衛(wèi)東. 主動(dòng)隊(duì)列管理中PID控制器的解析設(shè)計(jì)方法[J]. 軟件學(xué)報(bào), 2006, 17(9): 1989-1995.YANG Ji-wen, GU Dan-ying, ZHANG Wei-dong. An analytical design method of PID controller based on AQM/ARQ[J]. Journal of Software, 2006, 17(9): 1989-1995.

[8] Zhan Z H, Zhang J, Li Y, Chung H. Adaptive particle swarm optimization[J]. IEEE Transactions on Systems, Man, and Cybernetics: Part B, 2009, 39(6): 1362-1381.

[9] Ho S Y, Lin H S, Liauh W H, et al. OPSO: Orthogonal particles warm optimization and its application to task assignment problems[J]. IEEE Transactions on Systems, Man, and Cybernetics: Part A, 2008, 38(2): 28-298.

[10] Whitbrook A M, Aickelin U, Garibaldi J M, et al. Idiotypic immune networks in mobile-robot control[J]. IEEE Transactions on Systems, Man, and Cybernetics: Part B, 2007, 37(6):1581-1597.

[11] Misra V, Gong W B, Towsley D. Fluid-Based analysis of a network of AQM routers supporting TCP flows with an application to RED[C]//Proc of the ACM SIGCOMM 2000.Stockholm, 2000: 151-160.

[12] Hollot C V, Misra V, Towsley D, et al. On designing improved controllers for AQM routers supporting TCP flows[C]//Proc of the IEEE INFOCOM. Anchorage: IEEE Communications Society, 2001: 1726-1734.

[13] Ling S H, Iu H H, Chan K Y, et al. Hybrid particle swarm optimization with wavelet mutation and its industrial applications[J]. IEEE Transactions on Systems, Man, and Cybernetics: Part B, 2008, 38(3): 743-63.

[14] Dasgupta D. Advances in artificial immune systems[J]. IEEE Computational Intelligence Magazine, 2006, 1(4): 40-49.

[15] De Castro L N, Zuben F J V. Learning and optimization using the clonal selection principle[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(1): 239-251.

[16] 錢艷平, 李奇, 刁翔. 預(yù)測(cè) PI時(shí)滯網(wǎng)絡(luò)擁塞控制算法設(shè)計(jì)及性能分析[J]. 控制理論與應(yīng)用, 2006, 23(2): 161-168.QIAN Yan-ping, LI Qi, DIAO Xiang. Design and analysis of predictive PI algorithm for congestion control in time-delay network[J]. Control Theory & Applications, 2006, 23(2):161-168.