劉 洋，王文國(guó)

0 引言

隨著網(wǎng)絡(luò)的發(fā)展，特別是多媒體數(shù)據(jù)在網(wǎng)絡(luò)中的大量傳輸，對(duì)網(wǎng)絡(luò)的服務(wù)質(zhì)量(QoS)提出了越來(lái)越高的要求，這些要求包括帶寬、時(shí)延、延時(shí)抖動(dòng)、丟包率［1］等。文獻(xiàn)［2］證明基于兩個(gè)或兩個(gè)以上不相關(guān)可加度量的路由選擇問(wèn)題是NPC問(wèn)題，傳統(tǒng)算法無(wú)法在有效時(shí)間內(nèi)找到最優(yōu)路由。目前大部分學(xué)者采用啟發(fā)式算法如遺傳算法、蟻群算法、模擬退火算法等來(lái)解決這一問(wèn)題。文獻(xiàn)［3］采用Grover量子搜索算法解決多約束QoS路由問(wèn)題，獲得較好的效果。文獻(xiàn)［4］利用自適應(yīng)蟻群算法來(lái)搜索最優(yōu)解，判斷搜索過(guò)程中是否陷入局部最優(yōu)，通過(guò)動(dòng)態(tài)調(diào)整蟻群算法的參數(shù)來(lái)跳出局部最優(yōu)。文獻(xiàn)［5］采用了蟻群算法與遺傳算法相結(jié)合的方式來(lái)解決QoS路由問(wèn)題，獲得了比使用單一算法更優(yōu)的效果。文獻(xiàn)［6］采用改進(jìn)遺傳算法來(lái)解決QoS路由問(wèn)題，修改了遺傳算法的編碼、交叉和變異方式。文獻(xiàn)［7］基于蟻群系統(tǒng)來(lái)解決多約束QoS路由問(wèn)題。文獻(xiàn)［8］通過(guò)路徑交換來(lái)構(gòu)造鄰域解，利用模擬退火操作來(lái)解決多約束QoS組播路由問(wèn)題。

蟻群算法作為一種群智能算法，通過(guò)螞蟻之間的協(xié)作，利用信息素的正反饋來(lái)搜索最優(yōu)解。但基本蟻群算法存在搜索時(shí)間長(zhǎng)，易停滯等缺點(diǎn)。本文提出一種改進(jìn)的蟻群算法，即將蟻群分為兩個(gè)種群，其中一個(gè)種群的螞蟻在尋路時(shí)將考慮到該鏈路螞蟻聚集度的影響，并且降低選擇螞蟻聚集度較高鏈路的概率，防止在算法初始階段螞蟻大量聚集某一鏈路而陷入局部最優(yōu);另一種群的螞蟻則按照基本蟻群算法來(lái)尋路。當(dāng)?shù)螖?shù)增加時(shí)，本文算法將逐漸增加采用基本蟻群算法搜索鏈路螞蟻的數(shù)量，直至最大值。對(duì)信息素進(jìn)行更新時(shí)，要保留每輪迭代后全局最優(yōu)路徑的更新，防止隨著時(shí)間的流逝，最優(yōu)路徑信息素?fù)]發(fā)殆盡而喪失了最優(yōu)解。對(duì)非優(yōu)路徑，則減少信息素的增量，加快算法收斂于最優(yōu)路徑。

1 問(wèn)題描述與網(wǎng)絡(luò)模型

網(wǎng)絡(luò)模型表示為賦權(quán)圖G=(V，E)，其中V為圖中所有網(wǎng)絡(luò)節(jié)點(diǎn)(交換機(jī)、路由器)組成的集合，E為網(wǎng)絡(luò)中鏈路的集合。s∈V為源節(jié)點(diǎn)，d∈{ V -{s} }為目的節(jié)點(diǎn)。對(duì)網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)n∈V定義4種度量:時(shí)延函數(shù) D elay( n)，延時(shí)抖動(dòng)函數(shù)Delay_ Jitter( n)，丟包率函數(shù) Pl( n)，代價(jià)函數(shù)Cost( n)。對(duì)每條鏈路e∈E定義4種度量:時(shí)延函數(shù) D elay( e)，延時(shí)抖動(dòng)函數(shù)Delay_ J itter( e)，帶寬函數(shù)BandWidth( e)，代價(jià)函數(shù) C ost( e)．

對(duì)于源節(jié)點(diǎn)s，目的節(jié)點(diǎn)d，各QoS度量存在以下關(guān)系:

QoS路由算法的目的就是在源節(jié)點(diǎn)s，目的節(jié)點(diǎn)d之間尋找一條路由使之滿足以下條件:

Delay( p ( s，d ) )≤D 為時(shí)延約束

BandWidth( p ( s，d ) )≥B B為帶寬約束

Delay_Jitter( p ( s，d ) )≤Dj Dj為延時(shí)抖動(dòng)約束

Pl( p ( s，d ) )≤Pl Pl為丟包率約束

Min( Cost( p ( s，d)))

2 基本蟻群算法

蟻群算法是意大利學(xué)者M(jìn)．Dorigo于1991年提出的一種新型優(yōu)化算法，并用該算法解決了一系列組合優(yōu)化問(wèn)題。蟻群算法是一種群體智能算法，單個(gè)螞蟻并不具有智能行為，通過(guò)螞蟻之間的協(xié)作機(jī)制，以信息素作為螞蟻之間交流的橋梁，來(lái)搜索全局最優(yōu)解。蟻群算法是通過(guò)信息素的正反饋來(lái)尋找最優(yōu)解，當(dāng)螞蟻在一輪迭代中搜索完需要解決的問(wèn)題時(shí)，根據(jù)解的優(yōu)劣程度來(lái)留下不同量的信息素。隨著搜索進(jìn)行較優(yōu)解問(wèn)題上的信息素越聚越多，最終越來(lái)越多的螞蟻選擇該路徑，于是算法收斂于最優(yōu)解。基本蟻群算法具有并行性、魯棒性、易與其他算法相結(jié)合的優(yōu)點(diǎn)，也存在收斂慢，易出現(xiàn)停滯現(xiàn)象的缺點(diǎn)。

2． 1 尋路規(guī)則

螞蟻k在t時(shí)刻由節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的概率公式如下:

式(1)中allowk= { V -tabuk}，tabuk為螞蟻已經(jīng)走過(guò)的節(jié)點(diǎn)，τij(t)為鏈路(i，j)上的信息素量，α為信息啟發(fā)因子，β為期望值啟發(fā)因子。式(2)中 ηij(t)為啟發(fā)函數(shù)，其值為鏈路 ( i ，j)代價(jià)的倒數(shù)。

2． 2 信息素的更新規(guī)則

所有的螞蟻完成一輪搜索后，鏈路(i，j)上的信息素的增量公式如下:

以上公式中ρ為信息素?fù)]發(fā)系數(shù)，Q為信息素濃度，Lk為螞蟻k搜索路徑的適應(yīng)度值。

3 改進(jìn)的蟻群算法在QoS路由中的應(yīng)用

3． 1 改進(jìn)蟻群算法的搜索路徑概率公式

基本蟻群算法在解決QoS路由問(wèn)題時(shí)，由于算法初期各鏈路上的信息素?cái)?shù)量差異不大，導(dǎo)致螞蟻在選擇鏈路時(shí)的隨機(jī)性比較強(qiáng)。由于蟻群算法的正反饋性，導(dǎo)致一些路徑上的信息素過(guò)多積累，越來(lái)越多的螞蟻選擇該路徑，而這些路徑并非全局最優(yōu)路徑，于是算法陷入了停滯。為了解決這個(gè)問(wèn)題，我們將蟻群分為兩個(gè)群體:一個(gè)群體的螞蟻按照基本蟻群算法的尋路概率公式進(jìn)行搜索，此群體為基本群體{ n ormal group}，此群體的螞蟻叫基本螞蟻;另一群體的螞蟻在尋路時(shí)，引入了螞蟻聚集度因子，此群體為開(kāi)拓群體{ d eploitation group}，此群體的螞蟻叫開(kāi)拓螞蟻。各群體螞蟻尋路概率公式如下:

當(dāng)螞蟻屬于基本群體時(shí):

當(dāng)螞蟻屬于開(kāi)拓群體時(shí):

其中:

式中，n為鏈路(i，j)螞蟻數(shù)量，MaxAntNumber為當(dāng)前所有鏈路路過(guò)螞蟻數(shù)量的最大值。上述改進(jìn)的蟻群算法，由于拓展螞蟻的尋路概率公式中引入了鏈路螞蟻密集度因子δ，降低了對(duì)螞蟻高密集度鏈路的選擇，擴(kuò)大了在算法初期螞蟻的搜索范圍，克服了因非優(yōu)路徑信息素的大量積累而使算法陷入停滯的傾向。

Mn為基本群體螞蟻的數(shù)量，則M-?Mn」為開(kāi)拓群體螞蟻的數(shù)量算法開(kāi)始時(shí)，Mn=?M/2」，每輪迭代完成后Mn按照以下公式增長(zhǎng):

式中，Nmax為算法最大迭代次數(shù)，θ參數(shù)控制拓展螞蟻在多少輪迭代時(shí)全部消失。

這樣隨著迭代搜索的進(jìn)行，基本群體螞蟻逐漸增加，算法的正反饋增強(qiáng)，直到全部螞蟻均為基本群體螞蟻，加快了算法的收斂速度。

3． 2 改進(jìn)蟻群算法信息素更新公式

當(dāng)所有螞蟻進(jìn)行一輪搜索后，記當(dāng)前迭代螞蟻?zhàn)哌^(guò)的最優(yōu)路徑為Iterbestpath，且此路徑的適應(yīng)值為L(zhǎng)iterbest;在算法的迭代過(guò)程中，記當(dāng)前全局最優(yōu)路徑為Gbestpath，且此路徑的適應(yīng)值為L(zhǎng)gbest。記非優(yōu)路徑為Kpath，其適應(yīng)值為L(zhǎng)k。

當(dāng)所有螞蟻進(jìn)行一輪迭代搜索后，各路徑信息素的更新公式如下:

若 Literbest＜ Lgbest，Gbestpath=Iterbestpath

當(dāng)前迭代最優(yōu)路徑上的信息素更新公式為:

非優(yōu)路徑上的信息素更新公式為:

若 Literbest≥Lgbest，

此時(shí)當(dāng)前全局最優(yōu)路徑上信息素的更新公式為:

當(dāng)前迭代最優(yōu)路徑信息素的更新公式為:

非優(yōu)路徑上信息素的更新公式為:

每輪迭代搜索完成后，通過(guò)與當(dāng)前全局最優(yōu)路徑適應(yīng)值對(duì)比，可以大幅減弱非優(yōu)路徑上信息素的增量，以此來(lái)淘汰劣質(zhì)解的路徑，使螞蟻在下一輪迭代中趨向最優(yōu)路徑搜索，同時(shí)保留當(dāng)前全局最優(yōu)路徑的更新，防止最優(yōu)路徑上的信息素蒸發(fā)或減弱。

3． 3 改進(jìn)蟻群算法在網(wǎng)絡(luò)QoS路由選擇中的應(yīng)用

螞蟻k在從源節(jié)點(diǎn)搜尋到目的節(jié)點(diǎn)得到的路徑記為kpath，其適應(yīng)值記為L(zhǎng)k，本文中適應(yīng)值采用越小越優(yōu)的原則，Lk采用懲罰函數(shù)，定義如下:

式中，Rd，Rdj，Rpl均為懲罰參數(shù)，大于 1，本文算法中取2。Lk越小，該解越優(yōu)。

算法步驟如下:

(1)初始化參數(shù)。設(shè)置螞蟻數(shù)量M，各鏈路度量值 ( d ，dj，c，b )，各頂點(diǎn)度量 ( d ，dj，c，pl)的值。設(shè)置基本群體螞蟻的數(shù)量?M/2」，拓展群體螞蟻的數(shù)M-?M/2」。設(shè)置蟻群算法各參數(shù):信息素啟發(fā)因子α，期望啟發(fā)式因子β，信息素?fù)]發(fā)因子ρ，各鏈路信息素濃度的初始量Q0，信息素濃度常量Q，初始化各鏈路螞蟻密集度δ=0，各個(gè)度量約束量［D，Dj，B，Pl］，初始節(jié)點(diǎn) s，目的節(jié)點(diǎn) d，最大迭代次數(shù) Nmax。

(2)精簡(jiǎn)網(wǎng)絡(luò)，刪除不符合帶寬要求的鏈路。

(3)將M只螞蟻放在源節(jié)點(diǎn)。

(4)螞蟻k根據(jù)自己所在的群體，按照自己所在群體的尋路公式選擇下一節(jié)點(diǎn)N，

若N∈d，則k=k+1下一只螞蟻重復(fù)步(4);

若N∈φ，螞蟻k尋路無(wú)效，將該螞蟻放在源點(diǎn)s，重復(fù)步驟(4);

若N?φ且N≠d則螞蟻k重復(fù)步驟(4)。

(5)計(jì)算各只螞蟻?zhàn)哌^(guò)路徑的適應(yīng)度值Lk，選出本輪迭代最優(yōu)路徑Iterbestpath，以及對(duì)應(yīng)的適應(yīng)度Literbest，更新當(dāng)前全局最優(yōu)路徑Gbestpath，以及全局最優(yōu)路徑適應(yīng)值Lgbest，根據(jù)式(8)更新各鏈路δ的值，根據(jù)信息素更新公式更新各路徑上的信息素，更新各群體螞蟻的數(shù)量。

(6)重復(fù)步驟(3)，(4)，(5)直到最大迭代次數(shù)。

(7)輸出最優(yōu)路徑，算法結(jié)束。

4 仿真實(shí)驗(yàn)與結(jié)果分析

本文仿真實(shí)驗(yàn)所用的平臺(tái)為Matlab7．8，采用Salam網(wǎng)絡(luò)拓?fù)潆S機(jī)生成算法，生成網(wǎng)絡(luò)拓?fù)鋱D如圖1所示。

圖1 網(wǎng)絡(luò)拓?fù)?/p>

仿真實(shí)驗(yàn)網(wǎng)絡(luò)相關(guān)的參數(shù)選擇如表1所示。

表1 網(wǎng)絡(luò)相關(guān)參數(shù)

在仿真實(shí)驗(yàn)中，有關(guān)參數(shù)的設(shè)置如下:

QoS約束條件參數(shù):B=60，D=100 ms，DJ=40 ms，Pl=1e-2，

算法中各參數(shù)的設(shè)置:α=2，β=2，Q=1，M=50，Mn=25，ρ=0．1，q=1．01，源節(jié)點(diǎn) s=1，目的節(jié)點(diǎn)d=35，最大迭代次數(shù)Nmax=100。該問(wèn)題的最優(yōu)解路徑為(1，10，16，28，35)，代價(jià)為 29．1。

兩種算法每輪迭代搜索到解路徑各屬性的收斂曲線圖如圖2和圖3所示。

圖2 基本蟻群算法各屬性收斂曲線

圖3 改進(jìn)蟻群算法各屬性收斂曲線

由圖2和圖3的收斂曲線可以看出，改進(jìn)蟻群算法在迭代初始階段搜索到路徑代價(jià)較高，但能在較短的迭代次數(shù)內(nèi)搜索到代價(jià)較低的路徑，收斂曲線收斂到全局最優(yōu);而基本蟻群算法在初始階段搜索到次優(yōu)解后并沒(méi)有加大搜索力度，陷入了停滯狀態(tài)。這是由于改進(jìn)蟻群算法在迭代搜索初期階段通過(guò)兩種群體的螞蟻進(jìn)行搜索，避免了信息素在某一路徑的大量積累，擴(kuò)大了搜索范圍，同時(shí)通過(guò)保留當(dāng)前全局最優(yōu)路徑信息素的更新，減弱非優(yōu)解路徑信息素的更新量，淘汰掉大量劣質(zhì)解的路徑，使算法朝著全局最優(yōu)路徑搜索。

以路由請(qǐng)求源節(jié)點(diǎn)s=5，目的節(jié)點(diǎn)d=35，約束條件同上，進(jìn)行200次實(shí)驗(yàn)，該問(wèn)題的最優(yōu)路徑:為(5，9，17，23，29，35)，對(duì)應(yīng)代價(jià):32．8。實(shí)驗(yàn)結(jié)果如表2所示。

表2 源節(jié)點(diǎn)s=5的實(shí)驗(yàn)結(jié)果

由表2可以看出，改進(jìn)蟻群算法的收斂速度比基本蟻群算法快，并且具有良好的尋優(yōu)性能。

5 結(jié)語(yǔ)

由于基本蟻群算法初始階段，信息素量的分布缺乏優(yōu)劣解的差別，導(dǎo)致算法收斂慢。本文改進(jìn)算法加大優(yōu)劣解的區(qū)分度，引入鏈路螞蟻密集度來(lái)克服基本蟻群算法缺點(diǎn)。仿真實(shí)驗(yàn)表明，改進(jìn)算法搜索到路徑的代價(jià)平均值得到改善。在實(shí)驗(yàn)中，單個(gè)螞蟻的尋路由于尋路規(guī)則會(huì)出現(xiàn)無(wú)法選擇下一點(diǎn)的現(xiàn)象，本文通過(guò)螞蟻重新搜索來(lái)解決這一問(wèn)題。與其他改進(jìn)算法相比，本文采用螞蟻分工來(lái)改進(jìn)算法，盡量平衡搜索的深度與速度。在下一步工作中，將研究蟻群算法在QoS組播路由中的應(yīng)用。

［1］ Crawley E，Nair R，Rajagopalan B，and Sandiek H．A Frameework for QoS-based Routing in the Internet［S］，RFCno．2386，InternetRFC，Aug．1998．

［2］ WANG Z，Crowcroft J．Quality-of-Service for Routing Supporting Multimedia Applications［J］．IEEE Journal of Selected Areas in Communications1996，14(7):1228-1234．

［3］ 劉永廣．基于Grover搜索的多約束路由算法［J］．通信技術(shù)，2015，48(05):594-597．

LIU Yong-guang．A Multi-Constrained Routing Algorithm based on Grover Search［J］．Communications Technology，2015，48(05):594-597．

［4］ 王健安．基于蟻群優(yōu)化算法的分布式多約束QoS路由算法研究［D］．長(zhǎng)春:長(zhǎng)春理工大學(xué)，2014．

WANG Jian-an．Research of Multiple Constrained Distributed QoSRouting based on Improved Ant Colony Algorithm［D］．Changchun:Changchun University of Science and Technology，2014．

［5］ 陳西宏，劉少偉，胡茂凱等．基于蟻群遺傳混合算法的QoS 組播路由［J］．計(jì)算機(jī)工程，2011，37(04):99-101．

CHEN Xi-Hong，LIU Shao-wei，HUMao-kai，et al．QoSMulticast Routing based on Ant Colony Genetic Hybrid Algorithm［J］．Computer Engineering，2011，37(04):99-101．

［6］ 史長(zhǎng)瓊，黃輝，王大衛(wèi)等．基于改進(jìn)遺傳算法的QoS路由優(yōu)化［J］．計(jì)算機(jī)工程與設(shè)計(jì)，2009，30(07):1615-1617．

SHI Chang-qiong，HUANG Hui，WANG Da-wei，et al．QoSRouting Optimization based on Improved Genetic Algorithms［J］．Computer Engineering and Design，2009，30(07):1615-1617．

［7］ 馬立肖，趙占芳，王楠等．一種基于蟻群系統(tǒng)的多約束QoS路由模型［J］．微計(jì)算機(jī)信息，2007(03):133-13．

MA Li-xiao，ZHAO Zhan-fang，WANG Nan，et al．A Multi-Constraints QoS Routing Model on Ant Colony System［J］．Microcomputer Information，2007(3):133-13．

［8］ 張琨，王珩，劉鳳玉．一種基于模擬退火方法的多約束QoS組播路由算法［J］．計(jì)算機(jī)科學(xué)，2005，32(05):41-45．

ZHANG Kun，WANG Heng，LIU Feng-Yu．A Multi-Constrained QoS Multicast Routing Algorithmbased on Simulated Annealing［J］．Computer Science，2005，32(05):41-45．