基于混合遺傳免疫粒群優(yōu)化的網(wǎng)絡(luò)擁塞控制方法

孔金生，肖 天，徐 津

(1.鄭州大學(xué)電氣工程學(xué)院，河南鄭州450001;2.華中科技大學(xué)電子與信息工程系，湖北武漢430074)

0 引言

近年來，經(jīng)濟的飛速發(fā)展已經(jīng)帶動了網(wǎng)絡(luò)技術(shù)的巨大進步，而Internet作為發(fā)展最廣泛、最迅速的計算機網(wǎng)絡(luò)，在人類的生活中有著不可替代的作用.當(dāng)過多的數(shù)據(jù)包存在網(wǎng)絡(luò)中時，網(wǎng)絡(luò)的整體性能就會下降，這種現(xiàn)象稱為擁塞.擁塞會降低吞吐量、延時等一些性能指標(biāo)，影響網(wǎng)絡(luò)運行的穩(wěn)定性和服務(wù)質(zhì)量，因此，通過適當(dāng)?shù)姆椒▉眍A(yù)防和控制擁塞是目前網(wǎng)絡(luò)研究的一個熱點問題［1-2］.利用全局搜索尋優(yōu)技術(shù)的智能優(yōu)化算法在網(wǎng)絡(luò)優(yōu)化領(lǐng)域得到了廣泛應(yīng)用，包括微粒群算法(PSO)、遺傳算法(Genetic Algorithm，GA)、免疫算法(Immune Algorithm，IA)等優(yōu)化算法［3-4］.微粒群算法實現(xiàn)方便，具有良好的收斂性［5］;遺傳算法的全局搜索能力強，具有較好的魯棒性，不易陷入局部最優(yōu)［6］;免疫算法具有種群多樣性，速度相對快，易獲得全局最優(yōu)解等優(yōu)越性.這些優(yōu)化算法還存在一些問題，例如微粒群算法在處理復(fù)雜優(yōu)化問題時出現(xiàn)過早收斂，不能盡快找到最優(yōu)解;遺傳算法初始種群往往是隨機生成的，導(dǎo)致算法的收斂時間長［7］;免疫算法易陷入局部最優(yōu)，這些優(yōu)化算法在解決實際問題時會受到一定的限制.

筆者將遺傳算法和免疫算法引入到微粒群算法中，形成了遺傳免疫粒群優(yōu)化算法(簡稱IGAPSO)，這種混合的策略并不是對3種算法的簡單拼湊，也不是機械的繼承，通過理論分析研究，IGAPSO算法既提高了跳出局部最優(yōu)的能力，又保證了群體的多樣性，提高了尋優(yōu)效率.仿真結(jié)果驗證了該優(yōu)化算法的可行性，最后將遺傳免疫粒群算法應(yīng)用到網(wǎng)絡(luò)擁塞控制中，提出一種基于混合遺傳免疫粒群優(yōu)化的網(wǎng)絡(luò)擁塞控制方法.

1 混合的遺傳免疫粒群優(yōu)化算法

1.1 算法設(shè)計

遺傳免疫粒群算法通過將遺傳算法中的交叉變異機制和免疫算法中的識別選擇思想引入PSO，提高適應(yīng)度好的個體機率，并利用已經(jīng)產(chǎn)生的優(yōu)秀個體與隨機產(chǎn)生的微粒個體進行交叉變異產(chǎn)生新微粒，與此同時微粒的多樣性也不會受到影響［8］.具體算法如下

①對微粒群進行初始化，(含n個微粒);

②算出每個粒子的適應(yīng)度值;

③判斷每個粒子的當(dāng)前適應(yīng)度值，若優(yōu)于個體極值，則用當(dāng)前適應(yīng)度值替換個體極值，再將每個粒子的當(dāng)前個體極值與全局極值做比較，若優(yōu)于全局極值，則用該個體極值替換全局極值，并將當(dāng)前粒子保存至記憶庫;

④基于個體最優(yōu)和全體最優(yōu)值更新粒子;

⑤判斷是否滿足終止條件，若滿足則結(jié)束，不滿足則進行下一步;

⑥判定是否出現(xiàn)“早熟”現(xiàn)象，若沒有，轉(zhuǎn)②，否則進行下一步;

⑦隨機生成n/2個粒子，再在記憶庫中隨機選出n/2個粒子，兩部分粒子共同構(gòu)成新的微粒群，對新微粒群中的各微粒，基于其適應(yīng)度大小和濃度賦予各自參與交叉和變異運算的選擇概率，粒子依概率進行交叉變異運算，得到下一代粒子群，然后返回進行②.

1.2 性能測試

采用IGAPSO和標(biāo)準PSO針對一個標(biāo)準的多峰測試函數(shù)進行優(yōu)化，來比較兩者在“逃逸”局部極值方面的能力［9］.

圖1 測試函數(shù)圖像Fig.1 Image of test function

2種算法中均取粒子數(shù)40，設(shè)置循環(huán)結(jié)束條件為達到最大迭代次數(shù)10 000.2種算法的性能測試結(jié)果如圖2、圖3所示，結(jié)果表明標(biāo)準PSO在第607代陷入了局部最優(yōu)值15.919 4，全程耗時653.812 000 s，而IGAPSO則在第4 451代得到了全局最優(yōu)值 1.7764×10-15，全程耗時538.609 000 s.可見，經(jīng)過改進，遺傳免疫粒群算法在“逃逸”局部極值方面的能力得到了顯著增強.

圖2 標(biāo)準PSO算法性能測試結(jié)果Fig.2 Performance test result of standard PSO

圖3 IGAPSO算法性能測試結(jié)果Fig.3 Performance test result of

2 遺傳免疫粒群算法在網(wǎng)絡(luò)擁塞控制中的應(yīng)用

仿真采用的網(wǎng)絡(luò)拓撲模型是隨機產(chǎn)生的，結(jié)構(gòu)如圖4所示，共有15個節(jié)點.每條鏈路設(shè)置帶寬和延遲兩個QoS(Quality of Service)參數(shù)點，分別用B和D表示.假設(shè)現(xiàn)在有2個業(yè)務(wù)流分別應(yīng)用到網(wǎng)絡(luò)中，共同經(jīng)過鏈路9—13，業(yè)務(wù)流1所需B1=70，D1=10;業(yè)務(wù)流2 所需 B2=80，D2=12;鏈路9-13的鏈路帶寬B3=70.

圖4 網(wǎng)絡(luò)拓撲結(jié)構(gòu)Fig.4 Image of network topology

由于遺傳免疫粒群優(yōu)化算法選擇網(wǎng)絡(luò)資源較為充足的鏈路，而傳統(tǒng)算法選擇網(wǎng)絡(luò)中最短的路徑.2個業(yè)務(wù)流同時發(fā)送請求，遺傳免疫粒群算法與傳統(tǒng)算法優(yōu)化結(jié)果比較如表1所示.

表1 IGAPSO與傳統(tǒng)算法的比較結(jié)果Tab.1 Comparison result of IGAPSO and tradition algorithm

由表1可以看出采用遺傳免疫粒群優(yōu)化算法的業(yè)務(wù)流1、2都會選擇最適合的路徑，使網(wǎng)絡(luò)負載利用得更加均勻，而傳統(tǒng)算法只選擇最短路徑，造成丟包率很高，網(wǎng)絡(luò)無法滿足業(yè)務(wù)流對帶寬的需求，也浪費了其它合適路徑的網(wǎng)絡(luò)資源.圖5反映了網(wǎng)絡(luò)優(yōu)化前后鏈路9—13的吞吐量，顯然優(yōu)化后的網(wǎng)絡(luò)資源利用更合理，吞吐量更高，也保證了以后的業(yè)務(wù)請求.因此，遺傳免疫粒群算法在避免出現(xiàn)網(wǎng)絡(luò)擁塞的前提下合理利用網(wǎng)絡(luò)負載，盡量降低網(wǎng)絡(luò)資源消耗，提高吞吐量.

圖5 鏈路9—13的吞吐量Fig.5 Throughput of link 9—13

3 結(jié)論

筆者將遺傳算法和免疫算法引入到微粒群算法中，形成了基于遺傳免疫粒群的優(yōu)化算法(IGAPSO)，該算法既提高了算法跳出局部最優(yōu)的能力，又保證了群體的多樣性，在克服各個算法缺點的同時能更大發(fā)揮各自的優(yōu)點.最后將遺傳免疫粒群算法應(yīng)用到網(wǎng)絡(luò)擁塞控制中，提出一種基于混合的遺傳免疫粒群優(yōu)化的網(wǎng)絡(luò)擁塞控制方法來解決網(wǎng)絡(luò)擁塞現(xiàn)象，通過仿真研究，驗證了該方法的可行性.

［1］楊新宇，曾明，江曉，等.一種新的自適應(yīng)網(wǎng)絡(luò)擁塞控制算法［J］.計算機工程，2004，30(8):17-18.

［2］劉紅，白棟，丁煒，等.多目標(biāo)的 Internet路由優(yōu)化控制算法［J］.電子學(xué)報，2004，32(2):306-308.

［3］王小平，曹立明.遺傳算法—理論、應(yīng)用與軟件實現(xiàn)［M］.西安:西安交通大學(xué)出版社，2002.

［4］EAGELS P K，NOCOL V M.Recent approaches to global optimization problems through particle swam optimization［J］.Natural Computing，2002，12(1):235-306.

［5］謝曉峰，張文俊，楊之廉.微粒群算法綜述［J］.控制與決策，2003，18(2):129-134.

［6］玄光男，程潤偉，汪定偉，等.遺傳算法與工程設(shè)計［M］.北京:科學(xué)出版社，2000.

［7］趙靜，孔金生.基于遺傳算法和禁忌搜索的混合優(yōu)化策略［J］.計算機工程與設(shè)計，2009，30(23):5489-5491.

［8］朱洪程.基于遺傳免疫微粒群算法的工程項目多目標(biāo)綜合優(yōu)化研究［D］.天津:天津大學(xué)管理與經(jīng)濟學(xué)院，2010.

［9］ALFI A.PSO with adaptive mutation and inertia weight and its application in parameter estimation of dynamic systems［J］.Acta Automatica Sinica.2011，37(5):541-549.

［10］金超，葉春明.基于QPSO算法的模糊流水車間調(diào)度問題［J］.計算機工程與應(yīng)用.2012，48(2):238-240.