基于NSGAII算法的多目標參數優(yōu)化的主動隊列管理新策略摘要本文推導了基于流體流理論的網絡簡化模型，基于該模型將NSGAII與PGA相結合的優(yōu)化算法應用于PID控制器參數優(yōu)化，提出了一種多目標PID優(yōu)化設計方法在滿足系統(tǒng)魯棒性的前提下，以超調量、上升時間和調整時間最小作為多目標優(yōu)化的子目標，并將NSGA與PGA相結合對其求解。該算法求得的PARETO最優(yōu)解分布均勻，收斂性和魯棒性好，根據網絡主動隊列管理控制系統(tǒng)的要求在PARETO解集中選擇最終的滿意解。仿真結果表明，在大時滯和突發(fā)業(yè)務流的沖擊兩種情況下,該方法設計的控制器的動靜態(tài)性能優(yōu)于RED、GA、SPSO、QDPSO算法的優(yōu)化結果。關鍵詞主動隊列管理網絡擁塞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參數優(yōu)化算法811，增強了對隊列長度的控制能力，但這些方法難以兼顧系統(tǒng)對快速性、穩(wěn)定性和魯棒性的要求。針對這些缺陷，本文提出了一種多目標PID設計方法在滿足系統(tǒng)魯棒性的前提下，以系統(tǒng)輸出的超調量、上升時問和調整時間作為多目標優(yōu)化的子目標，并將帶精英策略的快速非支配排序遺傳算法NSGAII12和并行遺傳算法PGA13相結合，提出基于偽并行NSGAII算法的多目標魯棒PID優(yōu)化設計方法，并且將得到的優(yōu)化PID目標參數應用于網絡主動隊列管理系統(tǒng)中。仿真結果表明,在大時滯和突發(fā)業(yè)務流的沖擊兩種情況下,該方法設計的控制器的動靜態(tài)性能優(yōu)于RED、GA、SPSO、QDPSO算法的優(yōu)化結果。2TCP/AQM簡化模型及其AQM控制VMISRA等人在分析網絡連續(xù)數據流和隨機微分方程的基礎上，建立了TCP的動態(tài)模型6，用如下一組非線性微分方程來描述。（1）21TRPTRWTTTCTNQ式中W為預期的TCP擁塞窗口的大?。ò籕為預期的隊列長度（包）；為往返時間；TR（秒），為傳輸延時（秒）；C為鏈路容量（包/秒）；N為激活TCP連接數；P為PTTCQRP分組的丟棄概率，P的取值范圍為0，1；Q和W滿足。其中，、分別表WQ,0,Q示緩存容量和最大窗口尺寸。式（1）中第一個方程描述的是TCP的窗口控制動態(tài)特性，其中式右端的1/R項模擬了窗口的加性增加，W/2項對應于包丟失概率P的窗口大小乘性降低。第二個方程描述的是瓶頸隊列長度，它等于包到達率NW/R和鏈路容量C之間的差值。分析穩(wěn)態(tài)工作點各參數之間的關系，主要研究低頻性能，在W1時，忽略高頻性能,加入AQM控制，最終可得到如1SROE圖1所示的基于簡化模型AQM控制系統(tǒng)框圖。QTAQM控制1210STKERPTETQ0圖1基于簡化模型的AQM控制系統(tǒng)框圖令GPS為AQM系統(tǒng)簡化模型，即GPS（2）1210STKER其中，T1，。3024CKN020CN若鏈路容量C、往返時間和連接數N分別為105PACKET/S、003S和30，0R則GPS（3）1530736SEPID控制是一種具有負反饋的閉環(huán)控制系統(tǒng)，能夠較好的根據系統(tǒng)實時狀態(tài)快速作出控制反應，故不妨假設圖5中的AQM控制器仍具有PID形式，它引入微分環(huán)節(jié)來增強系統(tǒng)的快速響應的能力，克服其他控制算法響應遲緩的弱點，根據偏差的變化趨勢調節(jié)，具有超前作用，對系統(tǒng)的時滯具有補償能力。即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優(yōu)化模型為了兼顧系統(tǒng)對快速性、穩(wěn)定性和魯棒性的要求，這里以系統(tǒng)輸出的超調量、上升時間和調節(jié)時間作為優(yōu)化目標，以頻域魯棒性為約束當然也可以把它作為目標函數處理，建立如下的多目標優(yōu)化模型（9）MINMIN,PGTFMMSR式中為超調量；為上升時間由終值2第一次上升到終值98的時間；為調整時間誤差RTST帶取2；GM、PM為幅值裕度和相角裕度，下標MIN為約束下限。32PARETO解集多目標優(yōu)化問題可以用函數來定義，該函數把決策向量映射到目標向量，其數學描述為FXY（10）TRXGXGFFY,MIN21N式中X,由M個決策變量構成，由N個需同時優(yōu)化的目標構成；約束2X,IXYXFIGX由R個等式、不等式GIX0構成。多目標優(yōu)化問題2中的各目標往往處于沖突狀態(tài)，因而不存在使所有目標同時達到最優(yōu)的絕對最優(yōu)解，只能獲得滿意解即PARETO解。對于極小值多目標優(yōu)化問題，PARETO最優(yōu)解定義為在設計MINXF變量的可行域內，對于變量X，當且僅當不存在其他變量，在不違背約束的條件下滿足，至少存在一個I使得成立，則稱變量為非支配解，即PARETO最FXFIIFFII優(yōu)解。PARETO最優(yōu)解不是唯一的，多個PARETO最優(yōu)解構成PARETO最優(yōu)解集也稱PARETO前沿或非支配解集。4基于偽并行NSGAII算法的PID優(yōu)化41NSGA算法12NSGA是由SRINIVAS和DEB于20世紀90年代初期提出，它的高效性在于運用一個非支配分類程序，使多目標簡化至一個適應度函數的方式。該方法能解決任意數目的目標問題，并且能夠求最大和最小的問題。DEB于2002年對NSGA進行了改進，提出了NSGAII，一種快速的非劣性排序方法定義了擁擠距離估計某個點周圍的解密度取代適應值共享。NSGAII有效地克服了NSGA的三大缺陷計算復雜性從OMN3降至OMN2，具備最優(yōu)保留機制及無需確定一個共享參數。進一步提高了計算效率和算法的魯棒性。該算法得到的非劣解在目標空間分布均勻，收斂性和魯棒性好，已成為進化多目標優(yōu)化領域的基準算法之一。其步驟如下1快速非支配排序。在選擇運算之前，根據個體的非劣解水平對種群分級。具體方法為將當前種群中所有非劣解個體劃分為同一等級，令其等級為L；然后將這些個體從種群中移出，在剩余個體中找出新的非劣解，再令其等級為2；重復上述過程，直至種群中所有個體都被設定相應的等級。2虛擬適應度。為了保持個體的多樣性、防止個體在局部堆積，NSGAII算法首次提出了虛擬適應度的概念。它指目標空間上的每一點與同級相鄰2點之間的局部擁擠距離。例如，圖1中目標空間第I點的擁擠距離等于它在同一等級相鄰的點I1和I1組成的矩形2個邊長之和。這一方法可自動調整小生境，使計算結果在目標空間比較均勻地散布，具有較好的魯棒性。圖6局部擁擠距離示意圖具體實現時，首先解碼染色體，然后計算每個個體相應的目標函數值，再根據目標函數值進行非劣分層，計算每層個體的虛擬適應度，計算步驟為對同層的個體初始化距離LID0；對同層的個體按第M個目標函數值升序排列；使得排序邊緣上的個體具有選擇優(yōu)勢，給定一個,MLSORT大數L0DLLDM；對排序中間的個體，求擁擠距離1MDDILIILI為第I個體的第M個目標函數值；對不同的目標函數，重復步驟。MI3選擇運算。選擇過程使優(yōu)化朝PARETO最優(yōu)解的方向進行并使解均勻散布。經過排序和擁擠距離計算，群體中的每個個體I都得到2個屬性非支配序IRANK。和擁擠距離。ID當IRANKJD時，I個體優(yōu)于J個體。上式的意義為如果2個個體的非支配排序不同，取序號低的個體分級排序時，先被分離出來的個體；如果2個個體在同一級，取周圍較不擁擠的個體。4精英策略。精英策略即保留父代中的優(yōu)良個體直接進入子代。采用的方法是將父代PT和子代QT全部個體合成為一個種群，RT的個體數為2N；將種群RT快速非支配排序并計算每TTTQP一個體局部擁擠距離，依據等級的高低逐一選取個體，直到個體數量達到N就形成了新的父代種群PT1；在基礎上開始新一輪的選擇、交叉和變異，形成新的子代種群QT1。42并行遺傳算法13并行遺傳算法與常規(guī)遺傳算法的主要差別在于它存在同時進化的多個種群，對多個種群輪流進行遺傳操作，這樣能夠提高算法的性能和效率，有效地克服單種群算法的早熟現象?！斑w移策略”是并行遺傳算法引入了一個新的算子，它是指在進化過程中子群體間交換個體的過程，遷移可以加快較好個體在群體中的傳播，提高收斂速度和解的精度，與單種群相比可用較小的計算量達到同等性能，即使是在單一處理器上以串行偽并行的方式進行并行計算也能產生較好的效果。遷移策略的主要控制參數有子群體的連接拓撲、遷移率、遷移間隔、遷移選擇和替換。具體描述見文獻13。43基于偽并行NSGAII算法的PID優(yōu)化設計本文將NSGAII算法與并行遺傳算法結合，在單一處理器上以串行偽并行的方式進行并行計算，其流程圖如圖2所示?；趥尾⑿蠳SGAII算法的多目標魯棒PID優(yōu)化步驟為1編碼、（分別為比例、積分和微分系數采用實數編碼方式，取值的上、下限視具PKID體工程應用背景確定。2初始種群的產生。取5個子種群，規(guī)模依次為50、30、30、40、50，隨機產生子種群的個體。3遺傳操作。每個子種群采用NSGAII算法進行遺傳操作，NSGAII參數設置為圖7偽并行NSGAII算法流程圖選擇聯賽選擇，選擇規(guī)模為2；重組實值重組，重組率為09。為了提高算法的搜索能力，5個子種群采用不同的方式，依次為離散重組、中間重組、線性重組、離散重組、中間重組；變異。均勻變異，變異率為01。各子種群的變異步長依次為01、003、001、0003、0001；4遷移策略。子群體問采用網絡拓撲，按照排列比例來選擇遷移個體，每運行8代遷移1次，遷移率為01。5迭代次數加1，返回步驟3，直至達到最大迭代次數為止，大種群中的所有非支配解即構成PARETO最優(yōu)解集。最大迭代數設為50。5算例分析我們以前述的主動隊列管理系統(tǒng)，即式10進行仿真。偽并行NSGAII算法的參數設置如上文所述，式1中GMIN取2，PMIN取60，、的取值范圍為1，3、1，2、1，15。PKID1優(yōu)化結果本文的最大迭代次數設為50，實際運行到30代時，PARETO最優(yōu)解集已基本保持不變，收斂速度很快。表1列出了部分具有代表性的PARETO最優(yōu)解。由表L可知本文方法求得的PARETO解集可滿足系統(tǒng)對快速性、穩(wěn)定性和魯棒性不同偏好的需求當系統(tǒng)要求超調量很低時，可選擇第1組解；當系統(tǒng)要求上升時間較小時，可選擇第8組解；在各種偏好下，其他性能指標也能很好地兼顧。當系統(tǒng)沒有偏好時即無偏最優(yōu)解在第4組解。這為快速性、穩(wěn)定性與魯棒性的權衡分析提供了有效的工具，解決了現有PID優(yōu)化方法難以兼顧的問題，避免了對多個指標進行加權求解的盲目性。表1一組PARETO最優(yōu)解的誤差帶取2ST序號/PK60/I5/DK80R/ST/MGP12184709140149540010703432407101221990104191499807507530624971763205471041614683087069316240690842123911212147511120722882466892522558097881495121106832923868276230180954514987330066333235673972206511583133323610742142606319824465099641500366206339022963202與原有優(yōu)化設計方法的比較表2列出了GA、SPSO、QDPSO、NSGAII等設計方法的優(yōu)化結果，不難發(fā)現，本文算法所得的PARETO解集中無偏最優(yōu)解（即第4組解）比其更優(yōu)，GA，SPSO，QDPSO等原有優(yōu)化設計方法每次運行只能得到一個解，而本文的設計方法一次運行能得到多個PARETO最優(yōu)解，便于決策者根據實際系統(tǒng)的要求進行選擇。表2不同設計方法的比較TS的誤差帶取2優(yōu)化算法/PK610/I5/DK810TR/ST/MGPGA26631437628228472275420SPSO24829535027427452255432QDPSO23828433527326442205574NSGAII212112147112072824668926仿真實驗運用NS2網絡仿真器驗證本算法性能。網絡拓撲結構如圖8所示，仿真實驗結果與RED、PIDGA、PIDSPSO,PIDQDPSO等算法進行比較。12IN1NAB10MBPS15MBPS5MS5MSDMS45MBPSCI圖8網絡拓撲結構節(jié)點A和節(jié)點B之間的瓶頸鏈路容量15MBPS，延時5MS。N個持久性的FTP業(yè)務源與節(jié)點A之間的鏈路容量均為10MBPS，通常情況之下延時5MS，節(jié)點B和節(jié)點C之間的時延為DMS。RED高低門限值分別為100PACKETS和200PACKETS，PID的隊列長度的期望值為150PACKETS；各節(jié)點緩存大小均為300PACKETS。實驗1考察大時滯對算法性能的影響。N取60，時延D取220MS，所有FTP業(yè)務源均在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在大時滯中出現了持續(xù)震蕩，相比之下，基于GA、PSO、QDPSO、NSGAII優(yōu)化的PID算法響應速度較快，但基于NSGAII的優(yōu)化算法的響應速度最快，動靜態(tài)綜合性能最好。各算法性能比較如表3所示，其中為超調量，TS為調節(jié)時間，ESS為穩(wěn)態(tài)誤差。表3大時滯條件下各算法性能比較/TS/SESS/PACKETSRED趨向系統(tǒng)不穩(wěn)定，不求ESS值PIDGA763PIDPSO552PIDQDPSO442PIDNSGAII332實驗2考察突發(fā)業(yè)務流的沖擊對算法的影響，N取70，時延D取220MS，有60個FTP業(yè)務源均在0S時刻啟動，還有10個在15S時刻啟動，有60個FTP業(yè)務源均在0時刻啟動，還有10個在15S時刻啟動，發(fā)送100K字節(jié)后停止。仿真結果如圖10（A）、（B）、（C）、（D）、（E）所示。由圖看出，當引入突發(fā)業(yè)務流時，RED、PI影響最大，隊列長度有所上升，而這些突發(fā)業(yè)務量終止時，其隊列有所下降，出現較大振蕩，相比之下，基于GA、PSO、QDPSO、NSGAII的PID算法體現了一定的抗干擾能力，但基于NSGAII算法抗干擾能力最強，性能最好。各算法性能比較如表4所示。表4突發(fā)業(yè)務流的沖擊對各算法性能影響比較/TS/SESS/PACKETSRED趨向40系統(tǒng)不穩(wěn)定，不求ESS值PIDGA754PIDPSO543PIDQDPSO442PIDNSGAII332性能指標算法性能指標算法圖10ARED隊列長度（N增長至70）圖10BPID（GA）隊列長度（N增長至70）圖10CPID（SPSO）隊列長度（N增長至70）圖10DPID（QDPSO）隊列長度（N增長至70）圖10EPID（NSGAII）隊列長度（N增長至70）7結論本文基于網絡簡化模型將PID控制器應用于網絡AQM控制系統(tǒng)中，將NSGAII與PGA相結合的優(yōu)化算法應用于PID控制器參數進行組合優(yōu)化。仿真結果表明，該PID控制算法具有較好的綜合性能，比RED、基于GA優(yōu)化的PID控制算法、基于標準PSO優(yōu)化的PID控制算法、基于QDPSO優(yōu)化的PID控制算法更合適于AQM控制，性能表現為平均隊列長度更趨于期望值；超調量更小；調節(jié)時間更短；隊列長度的抖動更??；自適應能力更強。參考文獻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