论基于NSGA-II算法的目标参数优化的主动队列管理新策略分析

.

.DOC资料.

论基于NSGA-II算法的目标参数优化的主动队列管理新策略

-----------------------作者：

-----------------------日期：

基于NSGA-II算法的多目标参数优化的主动队列管理新策略收稿日期：

基金项目：国家自然科学基金（60474076）,江苏省“六大人才高峰”项目（07-E-013）,南通市应用研究计划项目（K2007004）

陆锦军1,2李志权2王执铨1

(1南京理工大学自动化学院南京210094;

2南通职业大学现代教育技术中心南通226007)

摘要本文推导了基于流体流理论的网络简化模型，基于该模型将NSGA-II与PGA相结合的优化算法应用于PID控制器参数优化，提出了一种多目标PID优化设计方法——在满足系统鲁棒性的前提下，以超调量、上升时间和调整时间最小作为多目标优化的子目标，并将NSGA-Ⅱ与PGA相结合对其求解。该算法求得的Pareto最优解分布均匀，收敛性和鲁棒性好，根据网络主动队列管理控制系统的要求在Pareto解集中选择最终的满意解。仿真结果表明，在大时滞和突发业务流的冲击两种情况下,该方法设计的控制器的动静态性能优于RED、GA、SPSO、QDPSO算法的优化结果。

关键词主动队列管理网络拥塞PID控制NSGA-II

中图分类号TP273文献标志码A国家标准学科分类代码120.30

ANewTacticsofMulti-ObjectParameterOptimizationforActiveQueueManagementBasedonNSGA-IIAlgorithm

LUJin-jun1,2LIZhi-quan2WANGZhi-quan1

（1SchoolofAutomation,NanjingUniversityofScienceandTechnology,Nanjing210094,China;

2CenterofEducationandTechnology,NantongVocationalCollege,Nantong226007,China）

Abstract:Simplifiednetworkmodelbasedonfluidflowtheoryisderivedinthispaper,andbasedonthismodel,animprovedalgorithm,i.e.optimizationalgorithmcombiningNSGA-IIandPGAisappliedtooptimizationofPIDcontrollerparameters.Inthefollowing,amulti-objectPIDoptimizationdesignmethodisputforward,i.e.whenrobustnessofthesystemissatisfied,theminimumofovershoot,risetimeandadjustingtimeistakenasthesub-objectofmulti-objectoptimization,andsolveitbycombiningNSGA-IIandPGA.TheParetooptimalsolutiongotbythisalgorithmdistributeseven,andhasgoodconvergenceandrobustness.AccordingtorequestofnetworkedActiveQueueManagementcontrolsystem,asatisfyingsolutionischoseninParetosolutionset.Thesimulationexperimentalresultsshowthatunderthetwoconditionsoflargetimedelayandsuddenbusinessflow,thedynamicstateandsteadystateperformancesoftheproposedalgorithmareobviouslysuperiortothoseoftheexistingRED,GA,SPSOandQDPSOalgorithms.

Keywords:activequeuemanagement;networkcongestion;PIDcontrol;NSGA-II

1引言

IP网络拥塞控制是人们一直着力解决但未能很好解决的问题，相继产生了不少有影响力的算法，如RED[1]、ARED[2]、SRED[3]、BLUE[4]等，同时也出现了许多基于网络流量的控制模型，但较具影响力的是VMisra等人于2000年基于流体流理论提出的网络模型[5]，该模型较为恰当地描述了TCP传输流的行为[6]，为研究人员广为采用，根据该模型，产生了PID[7]等主动队列管理算法和相应的PID参数优化算法[8-11]，增强了对队列长度的控制能力，但这些方法难以兼顾系统对快速性、稳定性和鲁棒性的要求。针对这些缺陷，本文提出了一种多目标PID设计方法——在满足系统鲁棒性的前提下，以系统输出的超调量、上升时问和调整时间作为多目标优化的子目标，并将带精英策略的快速非支配排序遗传算法(NSGA-II)[12]和并行遗传算法(PGA)[13]相结合，提出基于伪并行NSGA-II算法的多目标鲁棒PID优化设计方法，并且将得到的优化PID目标参数应用于网络主动队列管理系统中。仿真结果表明,在大时滞和突发业务流的冲击两种情况下,该方法设计的控制器的动静态性能优于RED、GA、SPSO、QDPSO算法的优化结果。

2TCP/AQM简化模型及其AQM控制

VMisra等人在分析网络连续数据流和随机微分方程的基础上，建立了TCP的动态模

型[6]，用如下一组非线性微分方程来描述。

（1）

式中：W为预期的TCP拥塞窗口的大小（包）；q为预期的队列长度（包）；为往返时间；（秒），为传输延时（秒）；C为链路容量（包/秒）；N为激活TCP连接数；P为分组的丢弃概率，P的取值范围为[0，1]；q和W满足。其中，、分别表示缓存容量和最大窗口尺寸。式（1）中第一个方程描述的是TCP的窗口控制动态特性，其中式右端的1/R项模拟了窗口的加性增加，W/2项对应于包丢失概率p的窗口大小乘性降低。第二个方程描述的是瓶颈队列长度，它等于包到达率NW/R和链路容量C之间的差值。分析稳态工作点各参数之间的关系，主要研究低频性能，在W>>1时，，忽略高频性能,加入AQM控制，最终可得到如图1所示的基于简化模型AQM控制系统框图。

q(t)

AQM控制

p(t)

e(t)

q0

－

图1基于简化模型的AQM控制系统框图

令Gp(s)为AQM系统简化模型，

即Gp(S)=（2）

其中，T1=，。

若链路容量C、往返时间和连接数N分别为105packet/s、0.03s和30，

则Gp(S)=（3）

PID控制是一种具有负反馈的闭环控制系统，能够较好的根据系统实时状态快速作出控制反应，故不妨假设图5中的AQM控制器仍具有PID形式，它引入微分环节来增强系统的快速响应的能力，克服其他控制算法响应迟缓的弱点，根据偏差的变化趋势调节，具有超前作用，对系统的时滞具有补偿能力。

即Gc（S）=Kp++Kds（4）

其中Kp、Ki、Kp分别为PID控制器的比例、积分、微分增益系数，其离散的表达形式为

（5）

其中是第k时刻的队列长度采样值，q0为期望队列长度，p(k)为k时刻的丢包概率。

其增量形式为

（6）

其中，，T=0.00625s

（7）

分组丢包概率

（8）

3多目标鲁棒PID设计与Pareto解集

3.1多目标鲁棒PID优化模型

为了兼顾系统对快速性、稳定性和鲁棒性的要求，这里以系统输出的超调量、上升时间和调节时间作为优化目标，以频域鲁棒性为约束(当然也可以把它作为目标函数处理)，建立如下的多目标优化模型:

（9）

式中：为超调量；为上升时间(由终值2％第一次上升到终值98%的时间)；为调整时间(误差带取2％)；GM、PM为幅值裕度和相角裕度，下标min为约束下限。

3.2Pareto解集

多目标优化问题可以用函数来定义，该函数把决策向量映射到目标向量，其数学描述为：

（10）

式中：X=(,…,)由m个决策变量构成，由n个需同时优化的目标构成；约束g(X)由r个等式、不等式gi(X)≤0构成。

多目标优化问题(2)中的各目标往往处于冲突状态，因而不存在使所有目标同时达到最优的绝对最优解，只能获得满意解即Pareto解。对于极小值多目标优化问题，Pareto最优解定义为：在设计变量的可行域内，对于变量X，当且仅当不存在其他变量，在不违背约束的条件下满足，至少存在一个i使得成立，则称变量为非支配解，即Pareto最优解。Pareto最优解不是唯一的，多个Pareto最优解构成Pareto最优解集(也称Pareto前沿或非支配解集)。

4基于伪并行NSGA-II算法的PID优化

4.1NSGA-Ⅱ算法[12]

NSGA是由Srinivas和Deb于20世纪90年代初期提出，它的高效性在于运用一个非支配分类程序，使多目标简化至一个适应度函数的方式。该方法能解决任意数目的目标问题，并且能够求最大和最小的问题。Deb于2002年对NSGA进行了改进，提出了NSGA-II，一种快速的非劣性排序方法：定义了拥挤距离估计某个点周围的解密度取代适应值共享。NSGA-II有效地克服了NSGA的三大缺陷：计算复杂性从O(mN3)降至O(mN2)，具备最优保留机制及无需确定一个共享参数。进一步提高了计算效率和算法的鲁棒性。该算法得到的非劣解在目标空间分布均匀，收敛性和鲁棒性好，已成为进化多目标优化领域的基准算法之一。其步骤如下：

(1)快速非支配排序。在选择运算之前，根据个体的非劣解水平对种群分级。具体方法为：将当前种群中所有非劣解个体划分为同一等级，令其等级为l；然后将这些个体从种群中移出，在剩余个体中找出新的非劣解，再令其等级为2；重复上述过程，直至种群中所有个体都被设定相应的等级。

(2)虚拟适应度。为了保持个体的多样性、防止个体在局部堆积，NSGA-II算法首次提出了虚拟适应度的概念。它指目标空间上的每一点与同级相邻2点之间的局部拥挤距离。例如，图1中目标空间第i点的拥挤距离等于它在同一等级相邻的点i-1和i+1组成的矩形2个边长之和。这一方法可自动调整小生境，使计算结果在目标空间比较均匀地散布，具有较好的鲁棒性。

图6局部拥挤距离示意图

具体实现时，首先解码染色体，然后计算每个个体相应的目标函数值，再根据目标函数值进行非劣分层，计算每层个体的虚拟适应度，计算步骤为：①对同层的个体初始化距离：L[i]d=0；②对同层的个体按第m个目标函数值升序排列：；③使得排序边缘上的个体具有选择优势，给定一个大数L[0]d=L[l]d=M；④对排序中间的个体，求拥挤距离：(为第i个体的第m个目标函数值)；⑤对不同的目标函数，重复步骤②～④。

(3)选择运算。选择过程使优化朝Pareto最优解的方向进行并使解均匀散布。经过排序和拥挤距离计算，群体中的每个个体i都得到2个属性：非支配序irank。和拥挤距离。id当irank<jrank或irank=jrank且id>jd时，i个体优于j个体。上式的意义为：如果2个个体的非支配排序不同，取序号低的个体(分级排序时，先被分离出来的个体)；如果2个个体在同一级，取周围较不拥挤的个体。

(4)精英策略。精英策略即保留父代中的优良个体直接进入子代。采用的方法是：①将父代Pt和子代Qt全部个体合成为一个种群，Rt的个体数为2N；②将种群Rt快速非支配排序并计算每一个体局部拥挤距离，依据等级的高低逐一选取个体，直到个体数量达到N就形成了新的父代种群Pt+1；③在基础上开始新一轮的选择、交叉和变异，形成新的子代种群Qt+1。

4.2并行遗传算法[13]

并行遗传算法与常规遗传算法的主要差别在于：它存在同时进化的多个种群，对多个种群轮流进行遗传操作，这样能够提高算法的性能和效率，有效地克服单种群算法的早熟现象。

“迁移策略”是并行遗传算法引入了一个新的算子，它是指在进化过程中子群体间交换个体的过程，迁移可以加快较好个体在群体中的传播，提高收敛速度和解的精度，与单种群相比可用较小的计算量达到同等性能，即使是在单一处理器上以串行(伪并行)的方式进行并行计算也能产生较好的效果。迁移策略的主要控制参数有：子群体的连接拓扑、迁移率、迁移间隔、迁移选择和替换。具体描述见文献[13]。

4.3基于伪并行NSGA-II算法的PID优化设计

本文将NSGA-II算法与并行遗传算法结合，在单一处理器上以串行(伪并行)的方式进行并行计算，其流程图如图2所示。基于伪并行NSGA-II算法的多目标鲁棒PID优化步骤为：

(1)编码：、、（分别为比例、积分和微分系数)采用实数编码方式，取值的上、下限视具体工程应用背景确定。

(2)初始种群的产生。取5个子种群，规模依次为50、30、30、40、50，随机产生子种群的个体。

(3)遗传操作。每个子种群采用NSGA-II算法进行遗传操作，NSGA-II参数设置为：

图7伪并行NSGA-II算法流程图

①选择：联赛选择，选择规模为2；

②重组：实值重组，重组率为0.9。为了提高算法的搜索能力，5个子种群采用不同的方式，依次为：离散重组、中间重组、线性重组、离散重组、中间重组；

③变异。均匀变异，变异率为0.1。各子种群的变异步长依次为：0.1、0.03、0.01、0.003、0.001；

(4)迁移策略。子群体问采用网络拓扑，按照排列比例来选择迁移个体，每运行8代迁移1次，迁移率为0.1。

(5)迭代次数加1，返回步骤(3)，直至达到最大迭代次数为止，大种群中的所有非支配解即构成Pareto最优解集。最大迭代数设为50。

5算例分析

我们以前述的主动队列管理系统，即式(10)进行仿真。伪并行NSGA-II算法的参数设置如上文所述，式(1)中Gmin取2，Pmin取60，、、的取值范围为：[1，3]、[1，2]、[1，1.5]。

(1)优化结果

本文的最大迭代次数设为50，实际运行到30代时，Pareto最优解集已基本保持不变，收敛速度很快。表1列出了部分具有代表性的Pareto最优解。

由表l可知本文方法求得的Pareto解集可满足系统对快速性、稳定性和鲁棒性不同偏好的需求——当系统要求超调量很低时，可选择第1组解；当系统要求上升时间较小时，可选择第8组解；在各种偏好下，其他性能指标也能很好地兼顾。当系统没有偏好时即无偏最优解在第4组解。这为快速性、稳定性与鲁棒性的权衡分析提供了有效的工具，解决了现有PID优化方法难以兼顾的问题，避免了对多个指标进行加权求解的盲目性。

表1一组Pareto最优解(的误差带取2％)

序号

/

/

/

1

2.1847

0.9140

1.4954

0.01

0.70

3.43

2.40

71.01

2

2.1990

1.0419

1.4998

0.75

0.75

3.06

2.49

71.76

3

2.0547

1.0416

1.4683

0.87

0.69

3.16

2.40

69.08

4

2.1239

1.1212

1.4751

1.12

0.72

2.88

2.46

68.92

5

2.2558

0.9788

1.4951

2.11

0.68

3.29

2.38

68.27

6

2.3018

0.9545

1.4987

3.30

0.66

3.33

2.35

67.39

7

2.2065

1.1583

1.3332

3.61

0.74

2.14

2.60

63.19

8

2.4465

0.9964

1.5003

6.62

0.63

3.90

2.29

63.20

(2)与原有优化设计方法的比较

表2列出了GA、SPSO、QDPSO、NSGA-II等设计方法的优化结果，不难发现，本文算法所得的Pareto解集中无偏最优解（即第4组解）比其更优，GA，SPSO，QDPSO等原有优化设计方法每次运行只能得到一个解，而本文的设计方法一次运行能得到多个Pareto最优解，便于决策者根据实际系统的要求进行选择。

表2不同设计方法的比较(ts的误差带取2％)

优化算法

/

/

/

GA

2.66

3.14

3.76

2.82

2.8

4.7

2.27

54.20

SPSO

2.48

2.95

3.50

2.74

2.7

4.5

2.25

54.32

QDPSO

2.38

2.84

3.35

2.73

2.6

4.4

2.20

55.74

NSGA-II

2.12

1.12

1.47

1.12

0.7

2.8

2.46

68.92

6仿真实验

运用NS2网络仿真器验证本算法性能。网络拓扑结构如图8所示，仿真实验结果与RED、PID(GA)、PID(SPSO),PID(QDPSO)等算法进行比较。

1

2

i

n-1

n

A

B

10Mbps

15Mbps

5ms

5ms

dms

45Mbps

ci

图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时间约为0.6s，主要包括传播时延、排队时延等。采用前述方法，实验仿真结果如图9（a）、（b）、（c）、（d）、（e）所示。

图9(a)RED队列长度（d=220ms）图9(b)PID（GA）队列长度（d=220ms）

图9(c)PID（SPSO）队列长度（d=220ms）图9(d)PID（QDPSO）队列长度（d=220ms）

图9(e)PID（NSGA-II）队列长度（d=220ms）

从实验结果可以看出，RED在大时滞中出现了持续震荡，相比之下，基于GA、PSO、QDPSO、NSGA-II优化的PID算法响应速度较快，但基于NSGA-II的优化算法的响应速度最快，动静态综合性能最好。各算法性能比较如表3所示，其中为超调量，ts为调节时间，ess为稳态误差。

表3大时滞条件下各算法性能比较

性

能

指

标

算

法

ts/s

ess/packets

RED

趋向

系统不稳定，不求ess值

PID(GA)

7

6

3

PID(PSO)

5

5

2

PID(QDPSO)

4

4

2

PID(NSGA-II)

3

3

2

实验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、NSGA-II的PID算法体现了一定的抗干扰能力，但基于NSGA-II算法抗干扰能力最强，性能最好。各算法性能比较如表4所示。

表4突发业务流的冲击对各算法性能影响比较

性

能

指

标

算

法

ts/s

ess/packets

RED

趋向

40

系统不稳定，不求ess值

PID(GA)

7

5

4

PID(PSO)

5

4

3

PID(QDPSO)

4

4

2

PID(NSGA-II)

3

3

2

图10(a)RED队列长度（n增长至70）图10(b)PID（GA）队列长度（n增长至70）

图10(c)PID（SPSO）队列长度（n增长至70）图10(d)PID（QDPSO）队列长度（n增长至70）

图10(e)PID（NSGA-II）队列长度（n增长至70）

7结论

本文基于网络简化模型将PID控制器应用于网络AQM控制系统中，将NSGA-II与PGA相结合的优化算法应用于PID控制器参数进行组合优化。仿真结果表明，该PID控制算法具有较好的综合性能，比RED、基于GA优化的PID控制算法、基于标准PSO优化的PID控制算法、基于QDPSO优化的PID控制算法更合适于AQM控制，性能表现为平均队列长度更趋于期望值；超调量更小；调节时间更短；队列长度的抖动更小；自适应能力更强。

参考文献

[1]ChristiansenM,JeffayK,OttD,SmithFD.TuringREDforWebTraffic[J].ACMComputerCommunicationReview,2000,30(4):139-150.

[2]FengW,KandlurD,SahaD,ShinK.ASelf-configurationREDgateway[A].ProceedingsoftheINFOCOM’99[C].NewYork:IEEEComputerSociety,1999.1320-1328.

[3]OttTj,LakshmanTV,WongLH.SRED:stabilizedRED[A].ProceedingsoftheINFOCOM’99[C].NewYork:IEEEComputerSociety,1999.1346-1355.

[4]AthuraliyaS,LowS,LiVH,YinQH.REM:Activequeuemanagement[J].IEEENetwork,2001,15(3):48-53.

[5]MisraV,GongWB,TowsleyD.Fluid-basedAnalysisofaNetworkofAQMRoutersSupportingTCPFlowswithanApplicationtoRED[A].Proc.ACM/SIGCOMM[C].2000,151-160.

[6]HollotCV,MisraV,owsleyTD,etal.AControlTheoreticAnalysisofRED[A].Proc.IEEEINFOCOM[C].Alaska,USA,2001,1510-1519.

[7]HollotCV,MisraV,TowsleyD,etal.OnDesigningImprovedControllersforAQMRoutersSupportingTCPFlows[A].Proc.IEEEINFOCOM[C].Alaska,USA,2001,1726-1734.

[8]WUTB,LIUZR,WANGJN.OptimizingPIDpar