基于蟻群改進(jìn)算法的服務(wù)質(zhì)量路由研究

孫佳林，王云松，龔躍

（長(zhǎng)春理工大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長(zhǎng)春 130022）

基于蟻群改進(jìn)算法的服務(wù)質(zhì)量路由研究

孫佳林，王云松，龔躍

（長(zhǎng)春理工大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長(zhǎng)春 130022）

針對(duì)傳統(tǒng)路由算法在多約束QoS（服務(wù)質(zhì)量）條件下尋優(yōu)能力不足的問(wèn)題，提出了一種基于改進(jìn)蟻群算法的多約束QoS路由模型。相比于傳統(tǒng)的路由算法，此方法在每次循環(huán)結(jié)束時(shí)，根據(jù)得到的不同結(jié)果動(dòng)態(tài)變化相關(guān)參數(shù)的值，并且結(jié)合最大最小螞蟻系統(tǒng)的理論，同時(shí)優(yōu)化啟發(fā)函數(shù)，以提高算法的尋優(yōu)能力。另外，除了考慮多個(gè)約束條件以外，在模型中還加入了故障率屬性，將其體現(xiàn)在目標(biāo)函數(shù)中，并優(yōu)化信息素更新方式。仿真實(shí)驗(yàn)結(jié)果表明改進(jìn)算法尋優(yōu)能力強(qiáng)，能有效避免早熟，并避開(kāi)故障率高的路徑。

蟻群算法；動(dòng)態(tài)參數(shù)；QoS路由；故障率

作為網(wǎng)絡(luò)通訊過(guò)程中的關(guān)鍵組成部分，QoS路由問(wèn)題的研究得到了重視［1］。QoS路由即是保證數(shù)據(jù)傳輸?shù)姆?wù)質(zhì)量，其中涉及到的網(wǎng)絡(luò)參數(shù)包括時(shí)延、通信開(kāi)銷、故障率等。多約束QoS路由問(wèn)題已經(jīng)被證明是一個(gè)NP完全問(wèn)題［2］，常用的求解算法包括遺傳算法［3］、蟻群算法［4-6］等。

蟻群算法是由Dorigo M等人提出的一種模仿蟻群覓食過(guò)程的尋優(yōu)算法。由于其具有適應(yīng)性強(qiáng)，魯棒性好等優(yōu)點(diǎn)，所以被應(yīng)用于解決任務(wù)調(diào)度、二次分配等各類組合優(yōu)化問(wèn)題［7，8］；但蟻群算法也有不足之處，其中，算法易陷入局部最優(yōu)解是其較為突出的缺點(diǎn)［9］。本文對(duì)傳統(tǒng)蟻群算法進(jìn)行改進(jìn)，提出了一種基于優(yōu)化蟻群算法的多約束QoS路由模型。

1 多約束QoS路由的數(shù)學(xué)模型

在通信網(wǎng)絡(luò)中，將網(wǎng)絡(luò)節(jié)點(diǎn)和通信鏈路的屬性綜合起來(lái)，可將其抽象成帶有屬性信息的賦權(quán)連通圖。用來(lái)表示該拓?fù)淠Ｐ?，其中V表示圖中所有節(jié)點(diǎn)的集合，E則表示鏈路的集合，分別代表圖中網(wǎng)絡(luò)節(jié)點(diǎn)以及鏈路的個(gè)數(shù)；設(shè)，源節(jié)點(diǎn)與目的節(jié)點(diǎn)分別用s、d來(lái)表示，從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路徑為P(s,d)。這里考慮的QoS約束參數(shù)及其數(shù)學(xué)表示如下：

（1）時(shí)延

（2）時(shí)延抖動(dòng)

（3）通信開(kāi)銷

通信開(kāi)銷是對(duì)在網(wǎng)絡(luò)傳輸過(guò)程中所耗費(fèi)的軟、硬件資源的綜合評(píng)價(jià)，是QoS路由約束條件中非常重要的一條，某路徑的總開(kāi)銷可表示為：

（4）帶寬

（5）故障率

即單位時(shí)間出現(xiàn)通信故障的時(shí)間的比值，相關(guān)數(shù)學(xué)公式為：

（6）包丟失率

多約束QoS路由的目標(biāo)就是找到從s到d的路徑P，使其滿足約束條件：

并且使得cost(P(s,d))的取值最小。

上式中C_d，C_dj，C_fr，C_pl，C_b分別為對(duì)應(yīng)參數(shù)的約束上、下界。

2 蟻群算法的優(yōu)化策略

蟻群算法是模仿螞蟻覓食留下信息素的過(guò)程而得來(lái)，其經(jīng)典的應(yīng)用是求解TSP問(wèn)題［10-11］。設(shè)問(wèn)題的規(guī)模為n，螞蟻的數(shù)目為m，開(kāi)始時(shí)，將每只螞蟻隨機(jī)置于城市網(wǎng)絡(luò)的某一節(jié)點(diǎn)上，搜索過(guò)程中，t時(shí)刻，螞蟻 y 的轉(zhuǎn)移規(guī)則［12，13］可表示為：

式中，allowedy為螞蟻y下一步可選擇的節(jié)點(diǎn)集合；τij(t)為i、j兩節(jié)點(diǎn)間的路徑上信息素的量，變化過(guò)程中，其取值默認(rèn)為正；α為信息素啟發(fā)因子，反映的是轉(zhuǎn)移規(guī)則受到信息素濃度的影響程度；ηij(t)稱為啟發(fā)函數(shù)，其計(jì)算方式如式（9）所示；β為期望啟發(fā)因子，反映了啟發(fā)信息對(duì)轉(zhuǎn)移規(guī)則的影響程度。

式中，dij表示兩節(jié)點(diǎn)間的距離，在QoS路由模型中，用cost(i,j)表示［14］，算法開(kāi)始運(yùn)行后，為了防止信息素濃度累積過(guò)高，要對(duì)信息素濃度進(jìn)行更新，更新方式如下：

式中，ρ為揮發(fā)系數(shù)，取值為(0,1)；Δτij(t)為信息素增量；Q為信息素強(qiáng)度；Ly為螞蟻y在本次循環(huán)中走過(guò)的距離。這里Δτijy(t)的計(jì)算方式采用的是Ant-Cycle模型的理論。

下面針對(duì)傳統(tǒng)蟻群算法存在的不足，提出改進(jìn)策略。

信息素濃度的高低很大程度上影響了螞蟻對(duì)路徑的選擇，這使得信息素強(qiáng)度的取值會(huì)對(duì)算法的搜索過(guò)程造成很大影響：其取值過(guò)大時(shí)，算法易陷入局部循環(huán)；取值過(guò)小時(shí)，算法的正反饋?zhàn)饔脺p弱，尋優(yōu)能力變差?；谝陨侠碚摚瑢?duì)于Q1（本文模型用到兩個(gè)不同的信息素強(qiáng)度值，在信息素更新過(guò)程具體說(shuō)明）做如下變化：

Q1∈[Q1_min,Q1_max]，系數(shù) k∈(0,1)。算法剛開(kāi)始運(yùn)行時(shí)，各路徑上信息素濃度相差不大，為了提高算法的正反饋?zhàn)饔茫涌焓諗克俣?，Q1取區(qū)間上的最大值；若與前N次循環(huán)相比，未發(fā)現(xiàn)更好解，認(rèn)為算法可能陷入了局部最優(yōu)解，此時(shí)按照一定比例減小Q1值，使算法可以跳出當(dāng)前局部解，但Q1的取值不會(huì)小于區(qū)間下界。

同樣地，信息素濃度造成的影響使得一些特殊情況的存在成為可能，比如某條路徑是潛在最優(yōu)路徑，開(kāi)始時(shí)，正反饋?zhàn)饔萌?，沒(méi)有螞蟻?zhàn)哌^(guò)這條路徑，那么此路徑上就不會(huì)產(chǎn)生信息素的積累，后面的螞蟻以信息素濃度的高低為依據(jù)，同樣不會(huì)選擇這條路徑。為了避免這種情況的發(fā)生，對(duì)路徑上的信息素加以控制［15］：

τij(t)∈[τmin,τmax]，τ(0)=τ0。將路徑上信息素濃度控制在一個(gè)特定范圍內(nèi)，這樣做的好處是防止信息素濃度過(guò)高時(shí)造成正反饋?zhàn)饔眠^(guò)強(qiáng)，并避免潛在的最優(yōu)路徑因信息素濃度過(guò)低而被忽略，擴(kuò)大了算法的解空間，提升了其全局尋優(yōu)能力。

影響算法的另一個(gè)因素就是路徑的啟發(fā)信息，優(yōu)化算法中，啟發(fā)函數(shù)的計(jì)算方式為：

其中，R為調(diào)節(jié)系數(shù)，通過(guò)變化R的值調(diào)節(jié)啟發(fā)函數(shù)值的大小，進(jìn)而變化啟發(fā)函數(shù)對(duì)轉(zhuǎn)移規(guī)則的影響程度。

3 路由算法與多約束QoS模型

（1）目標(biāo)函數(shù)

每次循環(huán)結(jié)束時(shí)，對(duì)于每只螞蟻按如下公式計(jì)算其走過(guò)路徑的目標(biāo)函數(shù)：

多約束QoS路由模型的目標(biāo)是找到滿足多個(gè)約束條件并且通信開(kāi)銷最小的路徑，F(xiàn)c按下式計(jì)算：

而Ffr，F(xiàn)d，F(xiàn)dj與Fpl的值決定了對(duì)應(yīng)參數(shù)對(duì)函數(shù)影響的程度，F(xiàn)fr計(jì)算方式為：

另外三個(gè)值的計(jì)算方式為［16］：

rd，rdj與rpl代表對(duì)應(yīng)參數(shù)值超過(guò)上界時(shí)，對(duì)目標(biāo)函數(shù)造成不利影響的程度。

此函數(shù)的確定，將原問(wèn)題轉(zhuǎn)化為了無(wú)約束多目標(biāo)優(yōu)化問(wèn)題。

（2）信息素更新過(guò)程

對(duì)于信息素的更新，本文采用的策略主要分兩步進(jìn)行。

第一步：當(dāng)循環(huán)結(jié)束時(shí)，對(duì)所有路徑上的信息素進(jìn)行更新，更新方式同式（10）。同時(shí)，在此模型中，Δτijy(t)的計(jì)算方式改為：

第二步：完成第一步更新后，對(duì)取得最大目標(biāo)函數(shù)值的路徑再進(jìn)行一次更新，方式如下：

通過(guò)以上理論，將改進(jìn)算法的步驟總結(jié)如下：

步驟1：對(duì)算法中涉及到的參數(shù)以及網(wǎng)絡(luò)鏈路、節(jié)點(diǎn)的QoS參數(shù)值初始化。

步驟2：根據(jù)帶寬的約束條件刪除不滿足條件的網(wǎng)絡(luò)鏈路。

步驟3：將m只螞蟻放到源節(jié)點(diǎn)，對(duì)于每只螞蟻，生成各自的禁忌表，并將源節(jié)點(diǎn)加入禁忌表中。

步驟4：螞蟻按照優(yōu)化算法的計(jì)算策略進(jìn)行路徑選擇，并將訪問(wèn)過(guò)的節(jié)點(diǎn)加入禁忌表。

步驟5：對(duì)螞蟻是否到達(dá)目的節(jié)點(diǎn)進(jìn)行判斷，若到達(dá)則記錄相關(guān)屬性值，并計(jì)算目標(biāo)函數(shù)；否則轉(zhuǎn)步驟4繼續(xù)執(zhí)行，直到所有螞蟻完成搜索。

步驟6：比較所有螞蟻所走過(guò)路徑的目標(biāo)函數(shù)值，根據(jù)信息素更新規(guī)則變化路徑上的信息素濃度。

步驟7：下次循環(huán)開(kāi)始前動(dòng)態(tài)變化算法中相關(guān)參數(shù)的值，接著將循環(huán)次數(shù)加1。

步驟8：重復(fù)執(zhí)行算法的第3-7步直至算法運(yùn)行結(jié)束。

4 實(shí)驗(yàn)仿真

仿真實(shí)驗(yàn)用到的網(wǎng)絡(luò)拓?fù)淠Ｐ图皵?shù)據(jù)如圖1所示，其中節(jié)點(diǎn)的屬性依次為：包丟失率、傳輸時(shí)延、時(shí)延抖動(dòng)、通信開(kāi)銷；鏈路上的屬性依次為：故障率（%）、時(shí)延、時(shí)延抖動(dòng)、通信開(kāi)銷以及帶寬。

圖1 網(wǎng)絡(luò)拓?fù)浼皵?shù)據(jù)

優(yōu)化算法中的參數(shù)取值分別為：m=23，α=1，β=2，ρ=0.2，Q1_min=10，Q1_max=200，N=10，k=0.75，τmin=1，τmax=100，τ0=20，R=1，Q2=20，rd=rdj=rpl=0.5；蟻群算法中，參數(shù)值為Q1=100，其余參數(shù)的設(shè)置同優(yōu)化算法。

設(shè)路由請(qǐng)求R(s,d,C_d,C_dj,C_b,C_fr,C_pl)=(1,15,45,16,70,0.98,5×10-4)，分別用蟻群算法與改進(jìn)算法進(jìn)行實(shí)驗(yàn)，得到的結(jié)果如下：

表1 兩種算法的運(yùn)行結(jié)果

比較以下兩圖中算法的計(jì)算過(guò)程可以看出，優(yōu)化算法的尋優(yōu)過(guò)程解的取值波動(dòng)范圍更廣，波動(dòng)的次數(shù)也更多，很好地避免了算法陷入局部循環(huán)的情況（為了顯示清晰，顯示時(shí)將故障率的值放大20倍）。

圖2 蟻群算法尋優(yōu)過(guò)程

圖3 優(yōu)化算法尋優(yōu)過(guò)程

圖4 蟻群算法尋優(yōu)過(guò)程（50代時(shí)增大故障率）

圖5 優(yōu)化算法尋優(yōu)過(guò)程（50代時(shí)增大故障率）

兩算法通過(guò)運(yùn)算得到最優(yōu)路徑，當(dāng)算法迭代達(dá)到50次時(shí)，增大鏈路（6.9）的故障率值（由0.33變?yōu)?.93）。此時(shí)，不滿足約束條件，發(fā)生此情況后，優(yōu)化算法經(jīng)過(guò)調(diào)整，在目標(biāo)函數(shù)與信息素濃度變化的綜合作用下，算法跳出當(dāng)前循環(huán)，數(shù)據(jù)的傳輸轉(zhuǎn)到其他路徑上進(jìn)行，而后算法再經(jīng)過(guò)調(diào)整，回到原路徑上。實(shí)驗(yàn)500次，算法跳出當(dāng)前路徑的比例為96.6%，證明了優(yōu)化算法可以有效地避開(kāi)故障率高的路徑；而蟻群算法雖然也能跳出當(dāng)前解，但隨著循環(huán)次數(shù)的增加，其返回先前路徑的概率非常低，這是由于算法沒(méi)有通過(guò)變化相關(guān)參數(shù)來(lái)控制信息素濃度，當(dāng)循環(huán)轉(zhuǎn)到其他路徑上時(shí)，這時(shí)所在路徑的信息素濃度隨著時(shí)間的推移迅速增加，最終會(huì)淹沒(méi)其他因素的影響，這和其容易陷入局部最優(yōu)解是類似的道理。

5 結(jié)束語(yǔ)

蟻群算法由于其自身的特性適用于解決有約束條件的網(wǎng)絡(luò)路徑尋優(yōu)問(wèn)題。經(jīng)過(guò)對(duì)傳統(tǒng)蟻群算法的改進(jìn)，提升了其性能，并構(gòu)造了基于優(yōu)化算法的QoS路由模型。經(jīng)過(guò)仿真，得到了比較理想的結(jié)果。

［1］朱慧玲，杭大明，馬正新，等.QoS路由選擇：?jiǎn)栴}與解決方法綜述［J］.電子學(xué)報(bào)，2003，31（1）：109-116.

［2］Wang Z，Crowcroft J.Quality-of-service routing for supporting multimedia applications［J］.IEEE Journal on Selected Areas in Communications，1996，14（7）：1228-1234.

［3］董建民，周明全，耿國(guó)華，等.基于遺傳算法的Qos的路由算法［J］.西北大學(xué)學(xué)報(bào)：自然科學(xué)版，2005，35（4）：383-387.

［4］孫力娟，王良俊.蟻群算法在QoS網(wǎng)絡(luò)路由中的應(yīng)用［J］.計(jì)算機(jī)應(yīng)用，2004，24（9）：65-68.

［5］冉敏，高隨祥，徐葆.一種基于蟻群系統(tǒng)的多約束Qos路由算法［J］.計(jì)算機(jī)工程與應(yīng)用，2005，41（7）：142-144+186.

［6］Wang H，Xu H，Yi S，et al.A tree-growth based antcolony algorithm for QoS multicast routing problem［J］.Expert Systems with Applications，2011，38（9）：11787-11795.

［7］Dorigo M，Maniezzo V，Colorni A.Ant system：optimization by a colony of cooperating agents［J］.IEEE Transactions on Systems，Man，and Cybernetics，Part B（Cybernetics），1996，26（1）：29-41.

［8］趙飛，吳航，龔躍.蟻群算法解決網(wǎng)格環(huán)境下任務(wù)調(diào)度問(wèn)題的研究［J］.長(zhǎng)春理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，36（1-2）：97-100.

［9］段海濱，王道波，朱家強(qiáng)等.蟻群算法理論及應(yīng)用研究的進(jìn)展［J］.控制與決策，2004，19（12）：1321-1326+1340.

［10］韓成，趙斌，白寶興，等.基于集群的蟻群算法在TSP中的應(yīng)用研究[J].長(zhǎng)春理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2008，31（4）：109-112.

［11］郭平，鄢文晉.基于TSP問(wèn)題的蟻群算法綜述[J].計(jì)算機(jī)科學(xué)，2007，34（10）：181-184.

［12］何志東.引入中間路由技術(shù)的蟻群算法在QoS路由的應(yīng)用研究［D］.廣州：華南理工大學(xué)，2011.

［13］Stützle T，Dorigo M.A short convergence proof for a class of ant colony optimization algorithms［J］.IEEE Transactions on Evolutionary Computation，2002，6（4）：358-365.

［14］黃小珂.基于蟻群優(yōu)化算法的數(shù)據(jù)包路由技術(shù)研究［D］.長(zhǎng)春：長(zhǎng)春理工大學(xué)，2010.

［15］Stützle T，Hoos H H.MAX-MIN ant system［J］.Future Generation Computer Systems，2000，16（8）：889-914.

［16］黃曉雯，賀細(xì)平，唐賢英.基于遺傳算法的QoS路由選擇與仿真［J］.計(jì)算機(jī)仿真，2003，20（6）：43-45.

QoS Routing Research Based on Ant Colony Improved Algorithm

SUN Jialin，WANG Yunsong，GONG Yue
（School of Computer Science and Technology，Changchun University of Science and Technology，Changchun 130022）

In order to solve the problem that the searching ability of the traditional routing algorithm is insufficient under the condition of multi-constrained QoS（Quality of Service），the model of multi-constrained QoS routing based on the improved ant colony algorithm is proposed.Compared with the traditional routing algorithm，this method dynamically changes the value of related parameters according to the different results when each loop ends，combines the theory of the Max-Min ant system and the heuristic function is optimized to improve the optimizing ability of the algorithm.In addition，the failure rate is added to the model except the multiple constraints，and is presented in the objective function，and the pheromone update mode is optimized.The simulation results show that the improved algorithm has strong optimization ability，and can effectively avoid premature and avoid the path with high failure rate.

Ant Colony Algorithm；dynamic parameter；QoS routing；failure rate

TP393

A

1672-9870（2017）05-0104-05

2017-09-11

孫佳林（1992-），男，碩士研究生，E-mail：yaandblw1219@126.com

龔躍（1960-），男，教授，博士生導(dǎo)師，E-mail：gongyue888878@sina.com