基于免疫粒子群算法的網(wǎng)絡(luò)擁塞控制策略

彭亦飛 ，張英杰

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

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

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

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

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

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

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

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

2 PID主動隊列管理算法原理

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

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

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

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

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

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

3 免疫雜交粒子群的 PID主動隊列管理算法

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

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

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

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

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

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

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

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

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

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

第1步：初始化種群。

I為個體空間。

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

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

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

第5步：克隆變異操作。

第6步：計算變異后的親合度。

第7步：克隆選擇

第8步：計算親合度。

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

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

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

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

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

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

3.4 算法流程

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

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

圖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為上升時間；w1，w2和w3為權(quán)值。

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

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

4 實驗

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

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

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

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

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

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

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

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

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

5 結(jié)論

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

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

(3) 免疫雜交粒子群算法具有較強(qiáng)的全局優(yōu)化能力；基于免疫雜交粒子群的PID主動隊列管理算法能夠適應(yī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é)報, 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)東. 主動隊列管理中PID控制器的解析設(shè)計方法[J]. 軟件學(xué)報, 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ù)測 PI時滯網(wǎng)絡(luò)擁塞控制算法設(shè)計及性能分析[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.