王文國，劉　洋

(曲阜師范大學 信息科學與工程學院，山東 日照 276826)

?

具有個體記憶的蟻群算法與網絡QoS路由研究* 1

王文國，劉洋

(曲阜師范大學 信息科學與工程學院，山東 日照 276826)

摘要：QoS路由算法的目的是在網絡中找到滿足一定帶寬、延時、延時抖動和丟包率等約束要求的路由，該問題是NPC問題。受自然螞蟻啟發(fā)，假設人工螞蟻具有短期記憶能力，使其選擇路徑時可把最近迭代搜索到的解與自己過去搜索的最優(yōu)最差解進行比較，動態(tài)調整其路徑選擇過程。蟻群信息素的變化則采用較優(yōu)解路徑更新策略，以加快算法的收斂。螞蟻將根據搜索到解的情況，判斷是否陷入局部最優(yōu)，若是則改變路徑信息素量上下限的大小，使算法跳出局部最優(yōu)。仿真實驗證明，改進的蟻群算法在解決QoS路由選擇問題時，能夠獲得比基本蟻群算法與最大-最小螞蟻系統更優(yōu)搜索性能。

關鍵詞：蟻群算法;QoS路由選擇;螞蟻個體記憶;動態(tài)選擇

0引言

隨著計算機網絡的發(fā)展，傳統盡力而為的服務已不能滿足各種網絡業(yè)務的需求。特別是網絡中多媒體的應用對帶寬、延時、延時抖動、丟包率等參數提出了嚴格要求[1]。網絡服務質量(QoS)就是提供用戶能夠滿足業(yè)務需求的、一致的、可預計的數據交付服務。網絡服務質量路由(QoSR)算法目的是在網絡中搜索最佳路由，該路由滿足帶寬、延時、延時抖動、丟包率等條件。由于包含兩個或兩個以上不相關可加或可乘性參數的路由選擇問題是NPC問題[2]，傳統路由算法無法在有效時間內找到最優(yōu)解，因而啟發(fā)式搜索算法成為解決多約束QoS路由問題的有效途徑[2-5]。

作為解決NPC問題的有效方法之一，人工蟻群算法可以用于優(yōu)化QoS路由選擇問題[3]。作為一種分布式算法，該算法通過螞蟻之間的相互協作來尋求最優(yōu)解，并通過螞蟻釋放的信息素作為螞蟻之間交流的媒介。螞蟻釋放信息素的量與它搜索到解的質量有關：搜索到解的質量優(yōu)，則釋放的信息素量多；反之則少。蟻群算法還具有并行性、魯棒性，易與其他算法相結合等優(yōu)點，但也存在收斂速度慢，易停滯于局部最優(yōu)解的缺點。該算法具有正反饋性，搜索到較優(yōu)解螞蟻釋放的信息素量多，這對后來的螞蟻搜索起到了導向作用。蟻群算法初期之所以收斂慢是由于在迭代初期，各路徑信息素量少并且信息素的分布不能體現解的優(yōu)劣程度，此時算法的正反饋較弱，需要經過一段時間的迭代搜索，各路徑信息素的差別才能體現出來。易收斂于局部最優(yōu)也是由于蟻群算法的正反饋性，導致某些路徑上信息素的量過大，螞蟻在以后的路徑選擇中失去了多樣性。目前已有多種人工蟻群算法的改進版本：如文獻[4]采用遺傳算法初期收斂快的特點，用收斂初期形成的較優(yōu)解來初始化算法初期路徑上信息素的量，算法后期利用蟻群算法的正反饋性來求解最優(yōu)，加快算法的收斂速度。文獻[5]通過路上經過的螞蟻數量的聚度來動態(tài)調整路徑選擇的概率范圍，調和算法的收斂速度與搜索的廣度。文獻[6]采用多個種群的螞蟻同時運行，采用路徑信息素的熵作為種群中蟻群算法進行程度的量，對不同進化程度的種群進行交流來克服單一蟻群算法出現的進化停滯現象。文獻[7]將兩個路徑的相似度作為一種參數，算法的運行過程中，使算法朝著與全局最優(yōu)解路徑相似度高的方向進化，提高了搜索到解的質量。文獻[8]采用粒子群算法來確定蟻群算法的參數，從而使蟻群算法獲得較好的性能。

在本文改進的蟻群算法中，螞蟻的狀態(tài)轉移規(guī)則不僅依賴于路徑信息素量的外部環(huán)境，而且與螞蟻自身的搜索狀態(tài)有關。每只螞蟻能夠保存自己搜索到的最優(yōu)解與最差解。螞蟻在接下來的路徑選擇中，將根據自己的搜索狀態(tài)與外界信息素的因素自主決定邊的選擇策略，克服螞蟻因面對同一環(huán)境信息而造成的選擇性單一，從而緩解蟻群算法的停滯現象。在信息素更新方面，只更新本輪迭代中較佳狀態(tài)的螞蟻搜索到解的各條邊上的信息素量與本輪循環(huán)最優(yōu)解的各條邊上的信息素量。

1基本蟻群算法模型

蟻群算法利用螞蟻之間的交流來尋找最優(yōu)解。蟻群算法中單個螞蟻并不具有智能性，而通過螞蟻釋放的信息素作為螞蟻之間交流的媒介，促進螞蟻之間的協作，使螞蟻朝著最優(yōu)解的方向進行搜索。算法本身主要包括路徑選擇部分與信息素的更新部分。

1.1路徑選擇公式

螞蟻k在t時刻由i節(jié)點選擇j節(jié)點的概率公式為：

(1)

(2)

式中，ηij(t)為期望值啟發(fā)函數，其值為路徑(i,j)距離的倒數。τij(t)為t時刻路徑(i,j)上信息素的量，allowk為螞蟻待選路徑的集合，α為信息素啟發(fā)因子，表示信息素在路徑選擇中所占的重要程度，β為期望值啟發(fā)因子，表示期望值在路徑選擇中的重要程度。

1.2信息素更新公式

τij(t+1)=(1-ρ)*τij(t)+Δτij(t)

(3)

(4)

(5)

式中，ρ為信息素揮發(fā)系數，Δτij(t)為路徑(i,j)信息素的增量，Q為信息素總量，Lk為螞蟻k搜索解的適應度值。本文信息素的更新方式為螞蟻進行遍歷完成后進行更新，更新信息素量的大小反映了全局解的優(yōu)劣。

路徑選擇公式表示解的構造過程，信息素更新公式體現了解的反饋信息。信息素更新公式決定了螞蟻在此后的搜索過程中選擇路徑的情況，而路徑選擇公式決定了信息素需要更新的路徑。這兩個公式相互作用，形成了蟻群算法搜索解的過程。

2改進的蟻群算法模型

基本蟻群算法在構造解的過程中，更多的依賴于路徑上信息素的量與期望啟發(fā)函數。這些因素都是外部因素，任何一只螞蟻在選擇路徑時，面對的外部環(huán)境都是一樣的。由于蟻群算法的正反饋性，當路徑上的信息素量越來越大時，螞蟻在此后的選擇過程中，失去了隨機性，大量的螞蟻會選擇同一條路徑，于是搜索到的路徑解失去了多樣性。此時算法容易陷入局部最優(yōu)解。

本文假設每只螞蟻能夠保存自己搜索到的最優(yōu)解與最差解。螞蟻在接下來的路徑選擇中，將根據自己的搜索狀態(tài)以及外界信息素分布情況綜合決定路徑的選擇，從而克服螞蟻因面對同一環(huán)境信息而造成的選擇單一性，進一步緩解蟻群算法的停滯現象。

2.1路徑選擇公式

螞蟻k在t+1輪搜索中，路徑選擇公式為：

(6)

(7)

μ1>10<μ2≤1λ≥1

(8)

(9)

(10)

2.2信息素更新公式

(12)

(13)

(14)

當螞蟻走完所有的路徑時，進行信息素的更新，Lk為螞蟻k構造解路徑的適應度值，本文中Lk越小越優(yōu)。

本文采用最大最小螞蟻系統[9]將路徑上的信息素量設置在一定的范圍之內。設信息素量的范圍為[τmin,τmax]。當路徑上的信息素更新完畢后，按照以下公式對路徑上的信息素量進行調整。

(15)

螞蟻k解的構造過程中，根據上輪迭代循環(huán)搜索到的解的適應度值與自己搜索到存儲的值相對比。當上輪循環(huán)搜索到解優(yōu)于自己搜索到的最優(yōu)解，螞蟻在本次循環(huán)狀態(tài)轉移時，只考慮邊上信息素量的因素，即所有螞蟻搜索的經驗。若候選的節(jié)點屬于自己搜索到最優(yōu)路徑的一部分，則加大選擇此節(jié)點的概率；其他節(jié)點將減少被選擇的概率。此時，每只螞蟻搜索的范圍將集中到自身搜索到的最優(yōu)解附近。這樣將搜索區(qū)域集中到某一區(qū)域，避免搜索區(qū)域過大而造成的無效搜索。

若螞蟻上輪搜索到解差于螞蟻自身己搜索到的最差解，在本次循環(huán)螞蟻進行狀態(tài)轉移時，若候選邊屬于自己搜索到最差路徑的一部分，將不選擇該邊；其他邊按照信息素量與期望啟發(fā)值乘積所占的比例進行概率搜索。

若螞蟻上輪搜索到解處于自己搜索到最優(yōu)解與最差解之間，螞蟻狀態(tài)轉移公式按照基本蟻群算法的狀態(tài)轉移策略，此時螞蟻會依靠信息素作為螞蟻之間交流的中間橋梁進行搜索。

當所有的螞蟻完成一次搜索后，進行信息素的更新。信息素的更新采用較優(yōu)路徑更新策略。較優(yōu)路徑包括兩部分：(1)當前迭代最優(yōu)解的路徑；(2)螞蟻在當前迭代搜索到解的路徑比自己最優(yōu)解更優(yōu)的路徑。路徑(1)信息素的更新能夠使局部最優(yōu)路徑信息素保留住，使以后螞蟻的搜索方向集中于較優(yōu)方向。路徑(2)信息素的更新，能夠使本次搜索成績較好的螞蟻之經驗在群體之間進行交流，有利于在下一次的迭代搜索中發(fā)現更好的解。

設第t輪迭代搜索后得到的當前迭代最優(yōu)解為Literbest(t)，第t輪迭代搜索完成時，算法已搜索到的最優(yōu)解為Lgbest。若Literbest(t)

τmin=τmin*(1+θ1)

(16)

τmax=τmax*(1-θ2)

(17)

0<θ1<1 , 0<θ2<1

按照上述改進后的蟻群算法，螞蟻在構造解的過程中，首先通過縱向比較，與自己的搜索到的最優(yōu)最差解進行對比，動態(tài)地選擇路徑計算公式，以加強或減弱蟻群算法的正反饋性；然后通過與其它螞蟻之間的橫向交流，加強螞蟻之間相互協作，使算法向著最優(yōu)解方向進化。

3改進蟻群算法在QoS路由選擇中的應用

3.1多約束QoS路由數學模型

計算機網絡可以抽象成帶權圖G(V,E), 其中V為網絡中節(jié)點(路由器，交換機)的集合，E為網絡中鏈路的集合。不失一般性，設該圖為無向圖。圖中的每個節(jié)點的屬性為：代價，延時，延時抖動，丟包率；鏈路的屬性為：代價，帶寬，延時，延時抖動。設網絡中的源節(jié)點為s, 目的節(jié)點為d，s∈V，d∈V。定義源節(jié)點s到目的節(jié)點d的代價、延時、延時抖動、丟包率，帶寬屬性如下：

代價：

延時：

延時抖動：

帶寬：

BandWidth(R(s,d))=min{BandWidth(e),e∈R(s,d)}

其中n為節(jié)點，e為鏈路。

QoS路由選擇問題如下：以s為源節(jié)點，d為目的節(jié)點。在網絡中找到一條路由R(s,d)，使之滿足以下條件：

其中D，Dj，Pl，B為保障服務質量所需的延時，延時抖動，丟包率，帶寬要求。QoS路徑選擇問題即在保障服務質量要求下，所求路由的代價最小。

3.2改進蟻群算法在QoS路由選擇中的應用

將m只螞蟻放于網絡中的源節(jié)點s，各只螞蟻按照各自的尋路公式進行選擇路徑，直到找到目的節(jié)點d。設螞蟻k找到的一條路由為Routek，該路由的使用度函數值為Lk，Lk定義如下：

Lk=Cost(Routek)*{φD(Delay(Routek))*

φDj(Delay_jitter(Routek))*φPl(Pl(Routek))}

(18)

(19)

(20)

(21)

其中rd,rdj,rpl,分別為懲罰系數，rd>1，rdj>1,rpl>1。適應度函數使用懲罰函數，對不符合服務質量要求的解路由，其適應度值加大，以形成劣質解。

算法過程如下：

第二步： 將m只螞蟻放在源節(jié)點s，t=t+1,設置螞蟻序號k=1。

第三步 螞蟻k按照上次搜到的解，選擇合適的路徑選擇公式，選擇下一節(jié)點j。

若j=d，則k=k+1，螞蟻k本次搜索完畢，轉向第三步。

若j≠d且j?φ，則螞蟻k繼續(xù)搜索，轉向第三步。

若j≠d且j∈φ，螞蟻k無法選擇下一路徑，本次搜索無效，將螞蟻放在源節(jié)點s，轉向第三步。

第五步：更新本次迭代路徑上信息素的量，根據式(15)調整路徑信息素量。

第六步：根據Literbest(t)，Lgbest判斷算法是否陷入局部最優(yōu)。若陷入局部最優(yōu)，根據式(16)，式(17)調整τmin，τmax。轉向第二步。

第七步：若t=Nc，則輸出最優(yōu)值，算法結束。

4仿真實驗分析

仿真實驗平臺采用MatLab7.8, 采用改進的Salam網絡拓撲隨機生成算法，生成網絡拓撲見圖1。

圖1　網絡拓撲

網絡中各參數設置如下：節(jié)點數量N=40, 網絡中各節(jié)點的參數范圍如表1所示。

表1　參數取值范圍

設仿真實驗參數如下：螞蟻數量m=20，α=1，β=2，ρ=0.1，Q=10，τmin=0.01，τmax=1，μ1=2，μ2=0.4，λ=2，θ1=0.01，θ2=0.01，迭代最大次數Nc=200。網絡服務質量各參數[B,D,Dj,Pl]要求為[40 Mb/s,100 ms,40 ms,10e-3]。以下對5個路由請求進行仿真實驗，分別采用基本蟻群算法，最大-最小蟻群算法，本文改進的蟻群算法進行實驗，每個實驗運行200次，相關實驗結果總結在表2、表3、表4中。

表2　基本蟻群算法實驗結果

表3　最大-最小蟻群算法實驗結果

表4　本文改進的蟻群算法實驗結果

由表2，表3，表4可以看出，基本蟻群算法，最大-最小蟻群算法，本文改進蟻群算法都能取得最優(yōu)解。本文改進蟻群算法多次實驗所求解方差比基本蟻群算法與最大-最小蟻群算法小，說明改進算法比基本蟻群算法與最大-最小蟻群算法穩(wěn)定，每次實驗所求解的差別不大。改進蟻群算法所求最優(yōu)解的比率比基本蟻群算法高，并且所求解的平均值比基本蟻群算法優(yōu)，說明我們改進的蟻群算法尋優(yōu)性能好于基本蟻群算法。通過改進的蟻群算法與最大-最小蟻群算法的實驗結果做對比，改進蟻群算法搜索性能優(yōu)于最大-最小蟻群算法。

以路由請求，源節(jié)點s=4，目的節(jié)點d=33, 服務質量約束要求如上實驗為例，分別運行以上三種算法，得到的最優(yōu)代價進化曲線圖如圖2所示。

圖2　三種算法最優(yōu)解進化曲線

由三種算法最優(yōu)代價進化曲線可以看出，基本蟻群算法陷入了局部最優(yōu)解，改進蟻群算法與最大-最小蟻群算法收斂到全局最優(yōu)解。由于改進蟻群算法在運行過程中路徑信息素上下限會改變，導致其收斂速度稍慢于最大-最小蟻群算法。

5結語

本文提出了一種改進的蟻群算法，使螞蟻在構造解的過程中，將路徑上的信息素，期望值等外部因素與自身的搜索狀態(tài)相結合：上次迭代循環(huán)搜索狀態(tài)佳的螞蟻在本次搜索選擇轉移的邊時，將在自己搜索到的最優(yōu)解附近進行搜索，力圖獲取更優(yōu)的解；上次迭代搜索狀態(tài)差的螞蟻在本次搜索路徑選擇時，將避開自己搜索到的最差解，提高螞蟻在當前迭代循環(huán)中搜索到解的質量。仿真實驗表明具有個體記憶的蟻群算法能夠獲得比最大-最小螞蟻系統與基本蟻群算法更優(yōu)的搜索性能。

參考文獻：

[1]Crawley E, Nair R, Rajagopalan B and Sandiek H. A Frameework for QoS-based Routing in the Internet[S], RFC no.2386, Internet RFC, Aug.1998.

[2]WANG Z, Crowcroft J. Quality-of-Service for Routing Supporting Multimedia Applications[J]. IEEE Journal of Selected Areas in Communications, 1996;14(7):1228-1234.

[3]劉洋,王文國. 差異化密集蟻群算法與網絡QoS路由選擇[J]. 通信技術，2015,48(08)：949-953.

LIU Yang, WANG Wen-guo. Differentiated Dense Ant Colony Algorithm and Network QoS Routing Selection[J].Communications Technology, 2015, 48(08): 949-953.

[4]楊原. 基于群智能優(yōu)化算法的QoS組播路由算法研究[D]. 西安：西安科技大學，2014.

YANG Yuan. Research on QoS Multicast Routing Algorithm based on Swarm Intelligence Optimization Algorithm[D]. Xi′an: Xi′an University of Science and Technology, 2014.

[5]陳峻,沈潔,秦玲等. 基于分布均勻度的自適應蟻群算法[J]. 軟件學報, 2003,14(08):1379-1387.CHEN Ling, SHEN Jie, QIN Ling, et al. An Adaptive Ant Colony Algorithm based on Equilibrium of Distribution[J]. Journal of Software,2003,14(08):1379-1387.

[6]鄧可,林杰,張鵬. 基于信息熵的異類多種群蟻群算法[J]. 計算機工程與應用, 2008,44(36):16-19.

DENG Ke, LIN Jie, ZHANG Peng. Multiple Heterogeneous Ant Colonies Algorithm based on Information Entropy[J].Computer Engineering and Applications, 2008, 44(36):16-19.

[7]張鵬,林杰,鄧可.一種基于路徑相似度的蟻群算法[J]. 計算機工程與應用，2007,43(32):28-33.

ZHANG Peng, LIN Jie, DENG Ke. Ant Colony Algorithm based on Similarity of Paths[J].Computer Engineering and Application,2007,43(32):28-33.

[8]姜秋霞. 混合蟻群算法及其應用研究[D]. 上海：同濟大學，2008.

JIANG Qiu-Xia. Research on Hybrid Ant Colony Algorithm and Its Application[D]. Shanghai: Tongji University,2008.

[9]Stutzle T, HH Hoos. MAX-MIN Ant System[J]. Future Gener. Comput. Syst, 2001,16(8):889-914.

Ant Colony Algorithm with Individual Memory and Its Application in QoS Routing

WANG Wen-guo, LIU Yang

(Dept. of Info. Science & Engineering, Qufu Normal University, Rizhao Shandong 276826, China)

Abstract：QoS routing aims to find a route satisfying restraint requirements of bandwidth, delay, delay jitter, and packet-loss rate in modern network. Artificial ant colony algorithm is one of the effective methods to solve QoS routing problems. Similar to real ants in nature, artificial ants with short term memory could compare current search result with its best/worst paths in the past, and then adjust its selection behavior dynamically. Simulation with Matlab indicates that the modified ant colony algorithm could acquire better searching performances as compared to the basic ant colony algorithm and max-min ant system.

Key words：ant colony algorithm; QoS routing; individual memory; dynamic selection

doi:10.3969/j.issn.1002-0802.2016.05.011

* 收稿日期：2015-12-20；修回日期：2016-04-02Received date:2015-12-20；Revised date：2016-04-02

基金項目：國家人事部高層次留學人員回國工作資助項目(No.200461)

Foundation Item：National High Level Talents Attracting Program of China(No.200461)

中圖分類號：TP311

文獻標志碼：A

文章編號：1002-0802(2016)05-0563-06

作者簡介：

王文國(1960—)，男，博士，教授，主要研究方向為網絡與信息安全;

劉洋(1981—) 男，碩士，主要研究方向為計算機網絡。