基于蟻群改進算法的服務質量路由研究

孫佳林，王云松，龔躍

（長春理工大學 計算機科學技術學院，長春 130022）

基于蟻群改進算法的服務質量路由研究

孫佳林，王云松，龔躍

（長春理工大學 計算機科學技術學院，長春 130022）

針對傳統路由算法在多約束QoS（服務質量）條件下尋優能力不足的問題，提出了一種基于改進蟻群算法的多約束QoS路由模型。相比于傳統的路由算法，此方法在每次循環結束時，根據得到的不同結果動態變化相關參數的值，并且結合最大最小螞蟻系統的理論，同時優化啟發函數，以提高算法的尋優能力。另外，除了考慮多個約束條件以外，在模型中還加入了故障率屬性，將其體現在目標函數中，并優化信息素更新方式。仿真實驗結果表明改進算法尋優能力強，能有效避免早熟，并避開故障率高的路徑。

蟻群算法；動態參數；QoS路由；故障率

作為網絡通訊過程中的關鍵組成部分，QoS路由問題的研究得到了重視［1］。QoS路由即是保證數據傳輸的服務質量，其中涉及到的網絡參數包括時延、通信開銷、故障率等。多約束QoS路由問題已經被證明是一個NP完全問題［2］，常用的求解算法包括遺傳算法［3］、蟻群算法［4-6］等。

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

1 多約束QoS路由的數學模型

在通信網絡中，將網絡節點和通信鏈路的屬性綜合起來，可將其抽象成帶有屬性信息的賦權連通圖。用來表示該拓撲模型，其中V表示圖中所有節點的集合，E則表示鏈路的集合，分別代表圖中網絡節點以及鏈路的個數；設，源節點與目的節點分別用s、d來表示，從源節點到目的節點的路徑為P(s,d)。這里考慮的QoS約束參數及其數學表示如下：

（1）時延

（2）時延抖動

（3）通信開銷

通信開銷是對在網絡傳輸過程中所耗費的軟、硬件資源的綜合評價，是QoS路由約束條件中非常重要的一條，某路徑的總開銷可表示為：

（4）帶寬

（5）故障率

即單位時間出現通信故障的時間的比值，相關數學公式為：

（6）包丟失率

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

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

上式中C_d，C_dj，C_fr，C_pl，C_b分別為對應參數的約束上、下界。

2 蟻群算法的優化策略

蟻群算法是模仿螞蟻覓食留下信息素的過程而得來，其經典的應用是求解TSP問題［10-11］。設問題的規模為n，螞蟻的數目為m，開始時，將每只螞蟻隨機置于城市網絡的某一節點上，搜索過程中，t時刻，螞蟻 y 的轉移規則［12，13］可表示為：

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

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

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

下面針對傳統蟻群算法存在的不足，提出改進策略。

信息素濃度的高低很大程度上影響了螞蟻對路徑的選擇，這使得信息素強度的取值會對算法的搜索過程造成很大影響：其取值過大時，算法易陷入局部循環；取值過小時，算法的正反饋作用減弱，尋優能力變差。基于以上理論，對于Q1（本文模型用到兩個不同的信息素強度值，在信息素更新過程具體說明）做如下變化：

Q1∈[Q1_min,Q1_max]，系數 k∈(0,1)。算法剛開始運行時，各路徑上信息素濃度相差不大，為了提高算法的正反饋作用，加快收斂速度，Q1取區間上的最大值；若與前N次循環相比，未發現更好解，認為算法可能陷入了局部最優解，此時按照一定比例減小Q1值，使算法可以跳出當前局部解，但Q1的取值不會小于區間下界。

同樣地，信息素濃度造成的影響使得一些特殊情況的存在成為可能，比如某條路徑是潛在最優路徑，開始時，正反饋作用弱，沒有螞蟻走過這條路徑，那么此路徑上就不會產生信息素的積累，后面的螞蟻以信息素濃度的高低為依據，同樣不會選擇這條路徑。為了避免這種情況的發生，對路徑上的信息素加以控制［15］：

τij(t)∈[τmin,τmax]，τ(0)=τ0。將路徑上信息素濃度控制在一個特定范圍內，這樣做的好處是防止信息素濃度過高時造成正反饋作用過強，并避免潛在的最優路徑因信息素濃度過低而被忽略，擴大了算法的解空間，提升了其全局尋優能力。

影響算法的另一個因素就是路徑的啟發信息，優化算法中，啟發函數的計算方式為：

其中，R為調節系數，通過變化R的值調節啟發函數值的大小，進而變化啟發函數對轉移規則的影響程度。

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

（1）目標函數

每次循環結束時，對于每只螞蟻按如下公式計算其走過路徑的目標函數：

多約束QoS路由模型的目標是找到滿足多個約束條件并且通信開銷最小的路徑，Fc按下式計算：

而Ffr，Fd，Fdj與Fpl的值決定了對應參數對函數影響的程度，Ffr計算方式為：

另外三個值的計算方式為［16］：

rd，rdj與rpl代表對應參數值超過上界時，對目標函數造成不利影響的程度。

此函數的確定，將原問題轉化為了無約束多目標優化問題。

（2）信息素更新過程

對于信息素的更新，本文采用的策略主要分兩步進行。

第一步：當循環結束時，對所有路徑上的信息素進行更新，更新方式同式（10）。同時，在此模型中，Δτijy(t)的計算方式改為：

第二步：完成第一步更新后，對取得最大目標函數值的路徑再進行一次更新，方式如下：

通過以上理論，將改進算法的步驟總結如下：

步驟1：對算法中涉及到的參數以及網絡鏈路、節點的QoS參數值初始化。

步驟2：根據帶寬的約束條件刪除不滿足條件的網絡鏈路。

步驟3：將m只螞蟻放到源節點，對于每只螞蟻，生成各自的禁忌表，并將源節點加入禁忌表中。

步驟4：螞蟻按照優化算法的計算策略進行路徑選擇，并將訪問過的節點加入禁忌表。

步驟5：對螞蟻是否到達目的節點進行判斷，若到達則記錄相關屬性值，并計算目標函數；否則轉步驟4繼續執行，直到所有螞蟻完成搜索。

步驟6：比較所有螞蟻所走過路徑的目標函數值，根據信息素更新規則變化路徑上的信息素濃度。

步驟7：下次循環開始前動態變化算法中相關參數的值，接著將循環次數加1。

步驟8：重復執行算法的第3-7步直至算法運行結束。

4 實驗仿真

仿真實驗用到的網絡拓撲模型及數據如圖1所示，其中節點的屬性依次為：包丟失率、傳輸時延、時延抖動、通信開銷；鏈路上的屬性依次為：故障率（%）、時延、時延抖動、通信開銷以及帶寬。

圖1 網絡拓撲及數據

優化算法中的參數取值分別為：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；蟻群算法中，參數值為Q1=100，其余參數的設置同優化算法。

設路由請求R(s,d,C_d,C_dj,C_b,C_fr,C_pl)=(1,15,45,16,70,0.98,5×10-4)，分別用蟻群算法與改進算法進行實驗，得到的結果如下：

表1 兩種算法的運行結果

比較以下兩圖中算法的計算過程可以看出，優化算法的尋優過程解的取值波動范圍更廣，波動的次數也更多，很好地避免了算法陷入局部循環的情況（為了顯示清晰，顯示時將故障率的值放大20倍）。

圖2 蟻群算法尋優過程

圖3 優化算法尋優過程

圖4 蟻群算法尋優過程（50代時增大故障率）

圖5 優化算法尋優過程（50代時增大故障率）

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

5 結束語

蟻群算法由于其自身的特性適用于解決有約束條件的網絡路徑尋優問題。經過對傳統蟻群算法的改進，提升了其性能，并構造了基于優化算法的QoS路由模型。經過仿真，得到了比較理想的結果。

［1］朱慧玲，杭大明，馬正新，等.QoS路由選擇：問題與解決方法綜述［J］.電子學報，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］董建民，周明全，耿國華，等.基于遺傳算法的Qos的路由算法［J］.西北大學學報：自然科學版，2005，35（4）：383-387.

［4］孫力娟，王良俊.蟻群算法在QoS網絡路由中的應用［J］.計算機應用，2004，24（9）：65-68.

［5］冉敏，高隨祥，徐葆.一種基于蟻群系統的多約束Qos路由算法［J］.計算機工程與應用，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］趙飛，吳航，龔躍.蟻群算法解決網格環境下任務調度問題的研究［J］.長春理工大學學報：自然科學版，2013，36（1-2）：97-100.

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

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

［11］郭平，鄢文晉.基于TSP問題的蟻群算法綜述[J].計算機科學，2007，34（10）：181-184.

［12］何志東.引入中間路由技術的蟻群算法在QoS路由的應用研究［D］.廣州：華南理工大學，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］黃小珂.基于蟻群優化算法的數據包路由技術研究［D］.長春：長春理工大學，2010.

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

［16］黃曉雯，賀細平，唐賢英.基于遺傳算法的QoS路由選擇與仿真［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-），男，教授，博士生導師，E-mail：gongyue888878@sina.com