基于免疫粒子群算法的网络拥塞控制策略

彭亦飞^{1, 2}，张英杰²

(1. 邵阳学院 信息工程系，湖南 邵阳，422000；

2. 湖南大学 计算机与通信学院，湖南 长沙，410082)

摘要：为避免Internet路由器主动队列管理中PID参数整定试凑法的盲目性，提出免疫杂交粒子群算法用于PID控制器参数优化，构造一种基于免疫杂交粒子群的智能主动队列PID算法。仿真结果表明，基于免疫杂交粒子群的PID主动队列管理算法能够适应动态变化的网络环境，具有较好的网络控制性能。

关键词：主动队列管理；网络拥塞；PID控制；粒子群优化；人工免疫算法

中图分类号：TP393          文献标志码：A         文章编号：1672-7207(2011)07-2042-06

Novel strategy of network congestion control based on

 immune particle swarm algorithm

PENG Yi-fei^{1, 2}, ZHANG Ying-jie²

(1. Department of Information Engineering, Shaoyang University, Shaoyang 422000, China;

2. College of Computer and Communication, Hunan University, Changsha 410082, China)

Abstract: To avoid the blindness of PID parameters trial and error tuning during the Internet router active queue management，an immune crossbreeding particle swarm optimization algorithm (ICPSOA) was proposed to optimize PID controller parameters, and then an intelligent active queue PID algorithm was designed based on immune crossbreeding particle swarm. The simulation experimental results show that the proposed algorithm can be adapted the dynamic network environment, and has the better network control performance.

Key words: active queue management; network congestion; PID control; particle swarm optimization; artificial immune algorithm

主动队列管理(Active queue management, AQM)是一种基于路由器的拥塞控制机制，是一种端到端的拥塞控制手段，既可减小排队时延，又可保证较高的吞吐量，从而达到抑制拥塞的目的^[1]。近年来，主动队列管理技术业已成为网络研究领域中的焦点，相关研究人员进行了一些研究与探索，提出多种AQM算法，如RED^[2]，ARED^[3]和SRED^[4]等。与此同时，人们也研究出一些基于网络流量的控制模型^[5]，其中最具有影响力的是Misra等^[6]于2000年提出的一种基于流体流理论的网络模型，该模型较准确地描述了TCP传输的行为。此外，人们将控制理论方法应用于网络拥塞控制，在现实工业领域中应用率最广的PID控制逐渐被应用到网络主动队列管理控制中，产生了PID^[7]等主动队列管理算法，加强队列长度的控制能力，具有让人满意的暂态响应和较小的稳态误差，然而，PID控制器参数的整定比较困难。PID控制器的参数整定与优化已成为控制界研究的焦点。粒子群算法(Particle swarm optimization, PSO)是由Kennedy等于1995年提出的一种基于群体智能的全局优化进化算法^[8]，它源于对鸟类捕食行为的模拟。目前该算法已经成功地应用于函数参数优化、神经网络训练、模糊系统控制优化等领域^[9]。由于粒子群自身不具备变异能力，随着进化的进行，粒子群算法容易陷入局部极值点。人工免疫系统是基于高等脊椎生物免疫系统机理发展而来的，它是人工智能研究的一个新领    域^[10-11]，具有多样性好、变异能力强、克隆复制与记忆力强等功能，使算法最终能逃逸出局部最优解，获得全局最优理想解。在此，本文作者基于以上分析，在流体理论的网络简化模型基础上，将PID控制器应用于计算机网络AQM中，应用免疫杂交粒子群算法，对控制器参数进行组合优化；在给定的搜索空间找到使性能指标优化函数极小化的一组PID控制器参数，构造一种基于免疫杂交粒子群算子的网络拥塞PID控制。

1  TCP/AQM模型

Misra等^[11]基于流体流(Fluid flow)理论建立了AQM作用下TCP连接拥塞窗口的动态模型。用如下非线性流体流模型来描述TCP网络AQM控制系统：

 (1)

  (2)

式中：w(t)为TCP流的窗口大小；q(t)为瞬时队列长度；T_P为传播时延；R=q/C+T_P，为传输RTT(Round-trip time，往返时延)；C为链路容量；N为TCP连接数目；p为丢包概率。

式(1)描述了TCP的拥塞窗口调节机制，采用加式增加/乘式减少(AIMD)拥塞控制算法，估计TCP流的拥塞窗口大小，其中右边第1项描述了AIMD的加式增加部分，若没有报文丢失，则每经过一个RTT，TCP拥塞窗口加1；第2项描述了AIMD的乘式减少部分，当检测到报文丢失时，拥塞窗口减少为原来的一半。式(2)描述了路由器中队列随时间变化的模型，瞬时队列长度q(t)由报文到达速率和链路带宽之间的差值决定。当队列长度大于0时，路由器转发报文，队列长度不断减少；否则，TCP连接发送报文到路由器，队列长度累积增大。因为丢包概率0＜p＜1，式(1)可由如下具有饱和输入特性的非线性时滞微分方程^[12]描述：

   (3)

其中，饱和输入可由如下非线性函数描述：

       (4)

饱和下界和上界分别为u_min=0和u_max=1。

TCP流量AQM控制示意图见图1。其中：c(s)为所使用的控制机制；p(s)代表被控对象的非时滞部分；由式(4)可以得出整个系统的开环传递函数G(s)：

        (5)

图1  TCP流量AQM控制示意图

Fig.1  Flow diagram of TCP AQM control

2  PID主动队列管理算法原理

PID控制器算法是依照误差的比例、积分、微分进行控制，它的输出值p取决于系统给定值q₀和系统输出值q的偏差e、偏差的积分、偏差的微分的线性加权组合；PID控制器中3个参数k_i，k_p和k_d需要调整。其控制系统原理如图2所示。基于PID的队列控制模型如图3所示。

图2  PID控制系统原理框图

Fig.2  Diagram of PID control system

图3  基于PID的队列控制模型

Fig.3  Queue control model based on PID

用连续域传递函数形式表述为：

           (6)

离散形式的增量控制算式为：

         (7)

基于PID的主动队列管理算法具有算法简单、容易实现的优点，简单的线性单变量系统中具有较好的控制效果。但是，对于复杂的网络非线性系统(如参数随时间变化、随机的时延以及外部随机信号的干扰等)，若PID控制器的参数难于得到合理配置，不能实时在线调整，则将导致其适应性差，影响系统的控制质量。于是，引入免疫杂交粒子群算法对主动队列管理PID控制器进行在线实时优化，以增强其自适应能力。

3  免疫杂交粒子群的PID主动队列管理算法

3.1  基本的粒子群优化算法

粒子群算法是一种新兴的进化计算技术，它的思想来源于鱼群和鸟群等社会群体生物的觅食现象，最先由Kennedy和Eberhart提出^[13]。粒子群算法具有参数较少、结构简单、易于计算机实现、收敛速度快、群体信息交互能力强等优点；在PSO算法中，粒子群在1个n维的空间中搜索，其中每个粒子所处的位置都表示问题的1个潜在解。粒子通过不断调整自己的位置X来搜索新解。每个粒子都记住自己搜索到的最好解，记作P_id。种群经历过的最好位置即目前搜索到的最优解记作P_gd。每个粒子都具有1个速度，记作v，定义为：

           (8)

其中：v_id表示第i个粒子第d维上的速度，ω为惯性权重；c₁和c₂分别为调节P_id和P_gd相对重要性的参数；rand( )为介于0和1之间的随机数。这样，可以得到粒子的下一个位置：

        (9)

由式(8)和(9)可以看出：粒子的移动速度由3部分(即自己原有的速度v_id、与自己最佳经历的距离(P_id-X_id)和与群体最佳经历的距离(P_gd-X_id))来决定，并分别由权重系数ω，c₁和c₂来决定其相对重要性。

3.2  人工免疫系统

人工免疫系统^[14-15]是基于生物免疫系统机理发展而来的。人工免疫系统存在高频变异、免疫记忆、克隆复制等优势，使系统最终能逃逸出局部最优解，获得全局最优解。

克隆免疫算法是人工免疫系统中最主要的算法之一，其机制中存在克隆扩增选择、交叉、超变异、进化替代以及局部灭绝5部分。克隆扩增算子：

            (10)

其中：β为克隆系数，一般取小于1.0大于0.5的数；i为初始群体在按适应度排序后染色体所处的序列号；round为取整操作；Y(k)为克隆扩增后的种群规模。

对于克隆扩增后的子体种群，进行概率很高的超变异，以获得新的个体。再将变异后的子体与它之前母体的适应度进行比较，若适应度比母体的高，则覆盖替代母体的基因值；若子体的适应度比其母体的低，则不执行任何操作。

抗体种群A(k)在克隆选择算子的作用下演化过程表示为：

其中：为克隆操作；为免疫基因操作，此过程主要包括交叉和变异；为克隆选择操作，通过此过程选出亲合度高的抗体，亲合度低的抗体将被淘汰，同时实现了种群的空间压缩。免疫克隆选择算法步骤如下。

第1步：初始化种群。

I为个体空间。

第2步：根据初始化值计算亲合度。

第3步：判断亲合度判断A(k)中是否有最优个体出现，即是否达到停止条件(终止条件判断)，若是，则停止。

第4步：克隆种群，亲合度高的克隆数量多，亲合度低的克隆数量少。

第5步：克隆变异操作。

第6步：计算变异后的亲合度。

第7步：克隆选择

第8步：计算亲合度。

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

3.3  杂交粒子群优化算法

为了更有利于群体间信息进行交互，提高群体协作能力，引用免疫系统中的交叉极值对微粒群个体间进行交叉。在群体进化过程中随机两两粒子进行杂交，产生同样数目的孩子粒子，并用孩子粒子代替父母粒子，以保持种群的粒子数目不变。孩子粒子的位置由父母粒子的位置的算数加权来计算。交叉算子如下：

       (11)

       (12)

其中：X为d维的位置向量；X₁(t)和X₂(t)为选择进行杂交操作的粒子；r为d维均匀分布且每个分量都在 [0, 1]取值的随机向量。

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

          (13)

         (14)

其中：v₁(t)和v₂(t)为进行杂交操作的粒子速度。

3.4  算法流程

将免疫系统中的克隆选择、高频变异、杂交机制融入粒子群算法中，构成一种高效的混合智能算法-免疫杂交粒子群算法。然后，将免疫杂交粒子群算法应用于网络拥塞PID控制中，对控制器进行优化。其流程图和控制器结构图分别如图4和图5所示。

控制参数的优化目的是使阶跃响应的控制误差趋近于0，有较快的响应速度和较小的响应误差。采用误差绝对值时间积分性能指标作为参数选择的最小目标函数，为了防止控制能量过大，在目标函数中加入控制输入的平方项。

      (15)

式中：e(t)为系统误差；u(t)为控制器输出；t_u为上升时间；w₁，w₂和w₃为权值。

图4  免疫杂交粒子群优化方法(ICPSOA)流程

Fig.4  Process of immune crossbreeding particle swarm optimization (ICPSOA)

图5  控制器结构

Fig.5  Controller structure

为了避免超调，采用惩罚功能，即一旦产生超调，将超调作为最优指标的1项，此时，最优指标为：

If  y_E(t)＜0

  (16)

式中：w₃为权值，且； ；y_out(t)为被控对象输出。

4  实验

为了验证文中提出的算法的有效性，通过MATLAB实验仿真进行验证。实验设置以队列长度能否稳定在参考值q₀附近为主要观察目标。这是因为将队列长度稳定在参考值附近，可以获得较高的吞吐量、低延时和低抖动。实验中设缓冲区队列长度q=200，参考队列长度q₀=150。

实验Ⅰ：假定网络状况为持续无变化的，有固定的TCP连接数N=60，链路容量C=3 750 /s，往返时间为80 ms，由式(5)可得被控对象：

          (17)

其仿真结果如图6所示。当网络条件恒定时，基于免疫杂交粒子群优化方法的PID(ICPSOA-PID)比普通PID收敛速度更快，ICPSOA-PID的上升速度较快，且超调量少，误差小；而基于常规PID的主动队列管理具有很明显的震动，且收敛速度慢，有误差。

实验Ⅱ：考查在变化的网络条件下，比较研究2种主动队列管理方法的性能。此时，TCP连接数N下降至30，往返时间为80 ms，链路容量C=2 800 /s，仿真结果如图7所示。从图7可见：ICPSOA-PID主动队列管理算法较常规PID主动队列管理算法更快地收敛于参考值150。这是由于免疫杂交粒子群算法(ICPSOA)全局寻优能力强，基于免疫杂交粒子群算法(ICPSOA)优化的PID具有更快的响应速度，自适应能力强，适应于实时动态系统控制；同时，ICPSOA-PID较常规PID算法能够更快地适应网络条件的变化，提高了适应性和实时性。

图6  实验1仿真结果

Fig.6  Simulation results of Experiment Ⅰ

图7  实验2仿真结果

Fig.7  Simulation results of Experiment Ⅱ

实验Ⅲ：考查在变化的网络条件下，比较研究多种主动队列管理方法的性能。此时，TCP连接数N下降为40，往返时间为90 ms，链路容量C=2 900 /s。其实验比较结果如表1所示。

表1  多种AQM算法性能比较

Table 1  Performance comparisons of AQM

表1中：RED^[2]为早期随机检测方法，PI为比例积分方法，PPI^[16]为预测PI控制方法。从表1可以看出：文中ICPSOA-PID在队列长度、标准差、吞吐率及其丢弃率均比其他3种方法的优。

5  结论

(1) 提出的一种免疫杂交粒子群算法提高了算法的全局寻优能力。

(2) 构造了一种基于免疫杂交粒子群的智能主动队列PID算法。免疫杂交粒子群算法对PID控制器参数进行优化，提高了PID控制器的自适应能力。

(3) 免疫杂交粒子群算法具有较强的全局优化能力；基于免疫杂交粒子群的PID主动队列管理算法能够适应动态变化的网络环境，与常规PID相比具有较好的网络控制性能。

参考文献：

[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] 陆锦军, 王执铨. 基于粒子群优化的网络拥塞控制新算法[J]. 电子学报, 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] 杨吉文, 顾诞英, 张卫东. 主动队列管理中PID控制器的解析设计方法[J]. 软件学报, 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] 钱艳平, 李奇, 刁翔. 预测PI时滞网络拥塞控制算法设计及性能分析[J]. 控制理论与应用, 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.

(编辑 陈灿华)

收稿日期：2010-12-15；修回日期：2011-03-08

基金项目：湖南省科技计划重点项目(2010GK2022)；湖南省科技计划一般资助项目(2008GK3075)；湖南省教育厅基金资助项目(08C788)；长沙市科技计划重点课题(K1005018-11)

通信作者：彭亦飞(1969-)，男，湖南邵阳人，副教授，从事网络技术研究；电话：13973561205；E-mail: pyfhj2@163.com