基于粒子群优化的网络拥塞控制新算法

基于NSGAII算法的多目标参数优化的主动队列管理新策略摘要本文推导了基于流体流理论的网络简化模型，基于该模型将NSGAII与PGA相结合的优化算法应用于PID控制器参数优化，提出了一种多目标PID优化设计方法在满足系统鲁棒性的前提下，以超调量、上升时间和调整时间最小作为多目标优化的子目标，并将NSGA与PGA相结合对其求解。该算法求得的PARETO最优解分布均匀，收敛性和鲁棒性好，根据网络主动队列管理控制系统的要求在PARETO解集中选择最终的满意解。仿真结果表明，在大时滞和突发业务流的冲击两种情况下,该方法设计的控制器的动静态性能优于RED、GA、SPSO、QDPSO算法的优化结果。关键词主动队列管理网络拥塞PID控制NSGAII中图分类号TP273文献标志码A国家标准学科分类代码12030ANEWTACTICSOFMULTIOBJECTPARAMETEROPTIMIZATIONFORACTIVEQUEUEMANAGEMENTBASEDONNSGAIIALGORITHM（1SCHOOLOFAUTOMATION,NANJINGUNIVERSITYOFSCIENCEANDTECHNOLOGY,NANJING210094,CHINA2CENTEROFEDUCATIONANDTECHNOLOGY,NANTONGVOCATIONALCOLLEGE,NANTONG226007,CHINA）ABSTRACTSIMPLIFIEDNETWORKMODELBASEDONFLUIDFLOWTHEORYISDERIVEDINTHISPAPER,ANDBASEDONTHISMODEL,ANIMPROVEDALGORITHM,IEOPTIMIZATIONALGORITHMCOMBININGNSGAIIANDPGAISAPPLIEDTOOPTIMIZATIONOFPIDCONTROLLERPARAMETERSINTHEFOLLOWING,AMULTIOBJECTPIDOPTIMIZATIONDESIGNMETHODISPUTFORWARD,IEWHENROBUSTNESSOFTHESYSTEMISSATISFIED,THEMINIMUMOFOVERSHOOT,RISETIMEANDADJUSTINGTIMEISTAKENASTHESUBOBJECTOFMULTIOBJECTOPTIMIZATION,ANDSOLVEITBYCOMBININGNSGAIIANDPGATHEPARETOOPTIMALSOLUTIONGOTBYTHISALGORITHMDISTRIBUTESEVEN,ANDHASGOODCONVERGENCEANDROBUSTNESSACCORDINGTOREQUESTOFNETWORKEDACTIVEQUEUEMANAGEMENTCONTROLSYSTEM,ASATISFYINGSOLUTIONISCHOSENINPARETOSOLUTIONSETTHESIMULATIONEXPERIMENTALRESULTSSHOWTHATUNDERTHETWOCONDITIONSOFLARGETIMEDELAYANDSUDDENBUSINESSFLOW,THEDYNAMICSTATEANDSTEADYSTATEPERFORMANCESOFTHEPROPOSEDALGORITHMAREOBVIOUSLYSUPERIORTOTHOSEOFTHEEXISTINGRED,GA,SPSOANDQDPSOALGORITHMSKEYWORDSACTIVEQUEUEMANAGEMENTNETWORKCONGESTIONPIDCONTROLNSGAII1引言IP网络拥塞控制是人们一直着力解决但未能很好解决的问题，相继产生了不少有影响力的算法，如RED1、ARED2、SRED3、BLUE4等，同时也出现了许多基于网络流量的控制模型，但较具影响力的是VMISRA等人于2000年基于流体流理论提出的网络模型5，该模型较为恰当地描述了TCP传输流的行为6，为研究人员广为采用，根据该模型，产生了PID7等主动队列管理算法和相应的PID参数优化算法811，增强了对队列长度的控制能力，但这些方法难以兼顾系统对快速性、稳定性和鲁棒性的要求。针对这些缺陷，本文提出了一种多目标PID设计方法在满足系统鲁棒性的前提下，以系统输出的超调量、上升时问和调整时间作为多目标优化的子目标，并将带精英策略的快速非支配排序遗传算法NSGAII12和并行遗传算法PGA13相结合，提出基于伪并行NSGAII算法的多目标鲁棒PID优化设计方法，并且将得到的优化PID目标参数应用于网络主动队列管理系统中。仿真结果表明,在大时滞和突发业务流的冲击两种情况下,该方法设计的控制器的动静态性能优于RED、GA、SPSO、QDPSO算法的优化结果。2TCP/AQM简化模型及其AQM控制VMISRA等人在分析网络连续数据流和随机微分方程的基础上，建立了TCP的动态模型6，用如下一组非线性微分方程来描述。（1）21TRPTRWTTTCTNQ式中W为预期的TCP拥塞窗口的大小（包）；Q为预期的队列长度（包）；为往返时间；TR（秒），为传输延时（秒）；C为链路容量（包/秒）；N为激活TCP连接数；P为PTTCQRP分组的丢弃概率，P的取值范围为0，1；Q和W满足。其中，、分别表WQ,0,Q示缓存容量和最大窗口尺寸。式（1）中第一个方程描述的是TCP的窗口控制动态特性，其中式右端的1/R项模拟了窗口的加性增加，W/2项对应于包丢失概率P的窗口大小乘性降低。第二个方程描述的是瓶颈队列长度，它等于包到达率NW/R和链路容量C之间的差值。分析稳态工作点各参数之间的关系，主要研究低频性能，在W1时，忽略高频性能,加入AQM控制，最终可得到如1SROE图1所示的基于简化模型AQM控制系统框图。QTAQM控制1210STKERPTETQ0图1基于简化模型的AQM控制系统框图令GPS为AQM系统简化模型，即GPS（2）1210STKER其中，T1，。3024CKN020CN若链路容量C、往返时间和连接数N分别为105PACKET/S、003S和30，0R则GPS（3）1530736SEPID控制是一种具有负反馈的闭环控制系统，能够较好的根据系统实时状态快速作出控制反应，故不妨假设图5中的AQM控制器仍具有PID形式，它引入微分环节来增强系统的快速响应的能力，克服其他控制算法响应迟缓的弱点，根据偏差的变化趋势调节，具有超前作用，对系统的时滞具有补偿能力。即GC（S）KPKDS（4）I其中KP、KI、KP分别为PID控制器的比例、积分、微分增益系数，其离散的表达形式为（5）TKEKJEKEDKJI10其中是第K时刻的队列长度采样值，Q0为期望队列长度，PK为K时刻的丢,0QKE包概率。其增量形式为（6）21211KETKEKETKKPDDDIP其中，T000625SIITPD（7）1KPK分组丢包概率（8）110KCKP3多目标鲁棒PID设计与PARETO解集31多目标鲁棒PID优化模型为了兼顾系统对快速性、稳定性和鲁棒性的要求，这里以系统输出的超调量、上升时间和调节时间作为优化目标，以频域鲁棒性为约束当然也可以把它作为目标函数处理，建立如下的多目标优化模型（9）MINMIN,PGTFMMSR式中为超调量；为上升时间由终值2第一次上升到终值98的时间；为调整时间误差RTST带取2；GM、PM为幅值裕度和相角裕度，下标MIN为约束下限。32PARETO解集多目标优化问题可以用函数来定义，该函数把决策向量映射到目标向量，其数学描述为FXY（10）TRXGXGFFY,MIN21N式中X,由M个决策变量构成，由N个需同时优化的目标构成；约束2X,IXYXFIGX由R个等式、不等式GIX0构成。多目标优化问题2中的各目标往往处于冲突状态，因而不存在使所有目标同时达到最优的绝对最优解，只能获得满意解即PARETO解。对于极小值多目标优化问题，PARETO最优解定义为在设计MINXF变量的可行域内，对于变量X，当且仅当不存在其他变量，在不违背约束的条件下满足，至少存在一个I使得成立，则称变量为非支配解，即PARETO最FXFIIFFII优解。PARETO最优解不是唯一的，多个PARETO最优解构成PARETO最优解集也称PARETO前沿或非支配解集。4基于伪并行NSGAII算法的PID优化41NSGA算法12NSGA是由SRINIVAS和DEB于20世纪90年代初期提出，它的高效性在于运用一个非支配分类程序，使多目标简化至一个适应度函数的方式。该方法能解决任意数目的目标问题，并且能够求最大和最小的问题。DEB于2002年对NSGA进行了改进，提出了NSGAII，一种快速的非劣性排序方法定义了拥挤距离估计某个点周围的解密度取代适应值共享。NSGAII有效地克服了NSGA的三大缺陷计算复杂性从OMN3降至OMN2，具备最优保留机制及无需确定一个共享参数。进一步提高了计算效率和算法的鲁棒性。该算法得到的非劣解在目标空间分布均匀，收敛性和鲁棒性好，已成为进化多目标优化领域的基准算法之一。其步骤如下1快速非支配排序。在选择运算之前，根据个体的非劣解水平对种群分级。具体方法为将当前种群中所有非劣解个体划分为同一等级，令其等级为L；然后将这些个体从种群中移出，在剩余个体中找出新的非劣解，再令其等级为2；重复上述过程，直至种群中所有个体都被设定相应的等级。2虚拟适应度。为了保持个体的多样性、防止个体在局部堆积，NSGAII算法首次提出了虚拟适应度的概念。它指目标空间上的每一点与同级相邻2点之间的局部拥挤距离。例如，图1中目标空间第I点的拥挤距离等于它在同一等级相邻的点I1和I1组成的矩形2个边长之和。这一方法可自动调整小生境，使计算结果在目标空间比较均匀地散布，具有较好的鲁棒性。图6局部拥挤距离示意图具体实现时，首先解码染色体，然后计算每个个体相应的目标函数值，再根据目标函数值进行非劣分层，计算每层个体的虚拟适应度，计算步骤为对同层的个体初始化距离LID0；对同层的个体按第M个目标函数值升序排列；使得排序边缘上的个体具有选择优势，给定一个,MLSORT大数L0DLLDM；对排序中间的个体，求拥挤距离1MDDILIILI为第I个体的第M个目标函数值；对不同的目标函数，重复步骤。MI3选择运算。选择过程使优化朝PARETO最优解的方向进行并使解均匀散布。经过排序和拥挤距离计算，群体中的每个个体I都得到2个属性非支配序IRANK。和拥挤距离。ID当IRANKJD时，I个体优于J个体。上式的意义为如果2个个体的非支配排序不同，取序号低的个体分级排序时，先被分离出来的个体；如果2个个体在同一级，取周围较不拥挤的个体。4精英策略。精英策略即保留父代中的优良个体直接进入子代。采用的方法是将父代PT和子代QT全部个体合成为一个种群，RT的个体数为2N；将种群RT快速非支配排序并计算每TTTQP一个体局部拥挤距离，依据等级的高低逐一选取个体，直到个体数量达到N就形成了新的父代种群PT1；在基础上开始新一轮的选择、交叉和变异，形成新的子代种群QT1。42并行遗传算法13并行遗传算法与常规遗传算法的主要差别在于它存在同时进化的多个种群，对多个种群轮流进行遗传操作，这样能够提高算法的性能和效率，有效地克服单种群算法的早熟现象。“迁移策略”是并行遗传算法引入了一个新的算子，它是指在进化过程中子群体间交换个体的过程，迁移可以加快较好个体在群体中的传播，提高收敛速度和解的精度，与单种群相比可用较小的计算量达到同等性能，即使是在单一处理器上以串行伪并行的方式进行并行计算也能产生较好的效果。迁移策略的主要控制参数有子群体的连接拓扑、迁移率、迁移间隔、迁移选择和替换。具体描述见文献13。43基于伪并行NSGAII算法的PID优化设计本文将NSGAII算法与并行遗传算法结合，在单一处理器上以串行伪并行的方式进行并行计算，其流程图如图2所示。基于伪并行NSGAII算法的多目标鲁棒PID优化步骤为1编码、（分别为比例、积分和微分系数采用实数编码方式，取值的上、下限视具PKID体工程应用背景确定。2初始种群的产生。取5个子种群，规模依次为50、30、30、40、50，随机产生子种群的个体。3遗传操作。每个子种群采用NSGAII算法进行遗传操作，NSGAII参数设置为图7伪并行NSGAII算法流程图选择联赛选择，选择规模为2；重组实值重组，重组率为09。为了提高算法的搜索能力，5个子种群采用不同的方式，依次为离散重组、中间重组、线性重组、离散重组、中间重组；变异。均匀变异，变异率为01。各子种群的变异步长依次为01、003、001、0003、0001；4迁移策略。子群体问采用网络拓扑，按照排列比例来选择迁移个体，每运行8代迁移1次，迁移率为01。5迭代次数加1，返回步骤3，直至达到最大迭代次数为止，大种群中的所有非支配解即构成PARETO最优解集。最大迭代数设为50。5算例分析我们以前述的主动队列管理系统，即式10进行仿真。伪并行NSGAII算法的参数设置如上文所述，式1中GMIN取2，PMIN取60，、的取值范围为1，3、1，2、1，15。PKID1优化结果本文的最大迭代次数设为50，实际运行到30代时，PARETO最优解集已基本保持不变，收敛速度很快。表1列出了部分具有代表性的PARETO最优解。由表L可知本文方法求得的PARETO解集可满足系统对快速性、稳定性和鲁棒性不同偏好的需求当系统要求超调量很低时，可选择第1组解；当系统要求上升时间较小时，可选择第8组解；在各种偏好下，其他性能指标也能很好地兼顾。当系统没有偏好时即无偏最优解在第4组解。这为快速性、稳定性与鲁棒性的权衡分析提供了有效的工具，解决了现有PID优化方法难以兼顾的问题，避免了对多个指标进行加权求解的盲目性。表1一组PARETO最优解的误差带取2ST序号/PK60/I5/DK80R/ST/MGP12184709140149540010703432407101221990104191499807507530624971763205471041614683087069316240690842123911212147511120722882466892522558097881495121106832923868276230180954514987330066333235673972206511583133323610742142606319824465099641500366206339022963202与原有优化设计方法的比较表2列出了GA、SPSO、QDPSO、NSGAII等设计方法的优化结果，不难发现，本文算法所得的PARETO解集中无偏最优解（即第4组解）比其更优，GA，SPSO，QDPSO等原有优化设计方法每次运行只能得到一个解，而本文的设计方法一次运行能得到多个PARETO最优解，便于决策者根据实际系统的要求进行选择。表2不同设计方法的比较TS的误差带取2优化算法/PK610/I5/DK810TR/ST/MGPGA26631437628228472275420SPSO24829535027427452255432QDPSO23828433527326442205574NSGAII212112147112072824668926仿真实验运用NS2网络仿真器验证本算法性能。网络拓扑结构如图8所示，仿真实验结果与RED、PIDGA、PIDSPSO,PIDQDPSO等算法进行比较。12IN1NAB10MBPS15MBPS5MS5MSDMS45MBPSCI图8网络拓扑结构节点A和节点B之间的瓶颈链路容量15MBPS，延时5MS。N个持久性的FTP业务源与节点A之间的链路容量均为10MBPS，通常情况之下延时5MS，节点B和节点C之间的时延为DMS。RED高低门限值分别为100PACKETS和200PACKETS，PID的队列长度的期望值为150PACKETS；各节点缓存大小均为300PACKETS。实验1考察大时滞对算法性能的影响。N取60，时延D取220MS，所有FTP业务源均在0时刻启动。瓶颈链路的容量为15MBPS，RTT时间约为06S，主要包括传播时延、排队时延等。采用前述方法，实验仿真结果如图9（A）、（B）、（C）、（D）、（E）所示。图9ARED队列长度（D220MS）图9BPID（GA）队列长度（D220MS）图9CPID（SPSO）队列长度（D220MS）图9DPID（QDPSO）队列长度（D220MS）图9EPID（NSGAII）队列长度（D220MS）从实验结果可以看出，RED在大时滞中出现了持续震荡，相比之下，基于GA、PSO、QDPSO、NSGAII优化的PID算法响应速度较快，但基于NSGAII的优化算法的响应速度最快，动静态综合性能最好。各算法性能比较如表3所示，其中为超调量，TS为调节时间，ESS为稳态误差。表3大时滞条件下各算法性能比较/TS/SESS/PACKETSRED趋向系统不稳定，不求ESS值PIDGA763PIDPSO552PIDQDPSO442PIDNSGAII332实验2考察突发业务流的冲击对算法的影响，N取70，时延D取220MS，有60个FTP业务源均在0S时刻启动，还有10个在15S时刻启动，有60个FTP业务源均在0时刻启动，还有10个在15S时刻启动，发送100K字节后停止。仿真结果如图10（A）、（B）、（C）、（D）、（E）所示。由图看出，当引入突发业务流时，RED、PI影响最大，队列长度有所上升，而这些突发业务量终止时，其队列有所下降，出现较大振荡，相比之下，基于GA、PSO、QDPSO、NSGAII的PID算法体现了一定的抗干扰能力，但基于NSGAII算法抗干扰能力最强，性能最好。各算法性能比较如表4所示。表4突发业务流的冲击对各算法性能影响比较/TS/SESS/PACKETSRED趋向40系统不稳定，不求ESS值PIDGA754PIDPSO543PIDQDPSO442PIDNSGAII332性能指标算法性能指标算法图10ARED队列长度（N增长至70）图10BPID（GA）队列长度（N增长至70）图10CPID（SPSO）队列长度（N增长至70）图10DPID（QDPSO）队列长度（N增长至70）图10EPID（NSGAII）队列长度（N增长至70）7结论本文基于网络简化模型将PID控制器应用于网络AQM控制系统中，将NSGAII与PGA相结合的优化算法应用于PID控制器参数进行组合优化。仿真结果表明，该PID控制算法具有较好的综合性能，比RED、基于GA优化的PID控制算法、基于标准PSO优化的PID控制算法、基于QDPSO优化的PID控制算法更合适于AQM控制，性能表现为平均队列长度更趋于期望值；超调量更小；调节时间更短；队列长度的抖动更小；自适应能力更强。参考文献1CHRISTIANSENM,JEFFAYK,OTTD,SMITHFDTURINGREDFORWEBTRAFFICJACMCOMPUTERCOMMUNICATIONREVIEW,2000,3041391502FENGW,KANDLURD,SAHAD,SHINKASELFCONFIGURATIONREDGATEWAYAPROCEEDINGSOFTHEINFOCOM99CNEWYORKIEEECOMPUTERSOCIETY,1999132013283OTTTJ,LAKSHMANTV,WONGLHSREDSTABILIZEDREDAPROCEEDINGSOFTHEINFOCOM99CNEWYORKIEEECOMPUTERSOCIETY,1999134613554ATHURALIYAS,LOWS,LIVH,YINQHREMACTIVEQUEUEMANAGEMENTJIEEENETWORK,2001,15348535MISRAV,GONGWB,TOWSLEYDFLUIDBASEDANALYSISOFANETWORKOFAQMROUTERSSUPPORTINGTCPFLOWSWITHANAPPLICATIONTOREDAPROCACM/SIGCOMMC2000,1511606HOLLOTCV,MISRAV,OWSLEYTD,ETALACONTROLTHEORETICANALYSISOFREDAPROCIEEEINFOCOMCALASKA,USA,2001,151015197HOLLOTCV,MISRAV,TOWSLEYD,ETALONDESIGNINGIMPROVEDCONTROLLERSFORAQMROUTERSSUPPORTINGTCPFLOWSAPROCIEEEINFOCOMCALASKA,USA,2001,172617348WUTB,LIUZR,WANGJNOPTIMIZING