高新成， 劉德聚， 王莉利， 馬樹軒

(1.東北石油大學(xué) 現(xiàn)代教育技術(shù)中心， 黑龍江 大慶 163318; 2.東北石油大學(xué) 計算機與信息技術(shù)學(xué)院， 黑龍江 大慶 163318)

隨著計算機網(wǎng)絡(luò)的飛速發(fā)展，當(dāng)前網(wǎng)絡(luò)的多樣化應(yīng)用對網(wǎng)絡(luò)傳輸?shù)母咝阅芎透哔|(zhì)量提出了更高的需求。傳統(tǒng)網(wǎng)絡(luò)采用“盡力而為”的傳輸方案很難保證數(shù)據(jù)的傳輸質(zhì)量，還會造成網(wǎng)絡(luò)資源的浪費，因此必須要對網(wǎng)絡(luò)進行優(yōu)化，使其在滿足多約束的前提下保障網(wǎng)絡(luò)資源的最大化配置[1-2]。QoS路由就是典型的一種路由優(yōu)化手段，它不僅能保證重要的業(yè)務(wù)數(shù)據(jù)進行及時可靠地傳輸，避免發(fā)生延遲和丟棄現(xiàn)象，同時還能保證網(wǎng)絡(luò)的高效流通[3]。QoS路由問題屬于特殊的組合優(yōu)化問題，用傳統(tǒng)的數(shù)學(xué)規(guī)劃和統(tǒng)籌的思想難以有效解決。通過研究發(fā)現(xiàn)，使用蟻群算法等元啟發(fā)式算法解決QoS路由問題已經(jīng)成為當(dāng)前網(wǎng)絡(luò)優(yōu)化領(lǐng)域的熱點之一[4-8]。本文以蟻群算法解決網(wǎng)絡(luò)路由問題為研究內(nèi)容，實現(xiàn)基于蟻群算法在網(wǎng)絡(luò)路由中的應(yīng)用。

1 蟻群算法模型

求解規(guī)模為n個城市、m只螞蟻的TSP問題，建立蟻群算法模型[9]。模型符號描述如下：

模型算法對每只螞蟻的行為要求如下：

(1)使用各條路徑上的信息素濃度作為指導(dǎo)值，通過計算各條可選路徑的轉(zhuǎn)移概率來決定下一步的行進方向；

(2)本次循環(huán)已經(jīng)走過的路徑禁止作為下一次被選擇的路徑，使用一個禁忌表(tabu list)來實現(xiàn)；

(3)每次循環(huán)結(jié)束，根據(jù)得到的路徑長度來指導(dǎo)信息素的釋放量，并根據(jù)更新規(guī)則完成走過路徑上的信息素濃度的更新。

1.1 轉(zhuǎn)移概率

每個螞蟻個體在開始進行搜索時，由于每條路徑上的信息素濃度都為設(shè)定的初始濃度，即πij(0)=C。螞蟻k(k=1,2,…,m)在搜索前進的過程中，通過各條可選路徑上的信息素濃度來決定下一次轉(zhuǎn)移的方向。在t時刻，位于某一城市的螞蟻k一次只能選擇一個城市作為下一個目標(biāo)城市，n次后返回起點完成一次循環(huán)。那么在t時刻，螞蟻k從城市i移動到城市j的轉(zhuǎn)移概率公式為

(1)

allowedk={C-tabuk}表示在t時刻螞蟻可以選擇的城市集合，即未訪問的城市集合；tabuk(k=1,2,…,m)記錄螞蟻k已經(jīng)走過的城市集合；α為信息啟發(fā)因子，表示存留下來的信息素相對重要程度；β為期望啟發(fā)因子，表示能見度的相對重要程度。

1.2 信息素的更新

為了避免信息素含量過多而影響啟發(fā)信息發(fā)揮作用，所以要求每只螞蟻完成對n個城市的遍歷后必須嚴(yán)格依照某個規(guī)則對路徑上的信息素進行更新，這樣才能保證隨著時間的推移，以前留下的信息素會逐漸消失。信息素的更新公式為

πij(t+n)=(1-ρ)πij(t)+Δπij(t)，

(2)

(3)

(4)

式中Q為常數(shù)，表示信息素增加的強度；Lk表示螞蟻k完成此次循環(huán)后經(jīng)過的路徑總長度。

2 基于ACO的QoS路由模型設(shè)計

2.1 QoS路由問題描述

網(wǎng)絡(luò)模型通常抽象為一個無向賦權(quán)圖G=，其中V表示無向賦權(quán)圖中的所有節(jié)點組成的集合，E表示無向賦權(quán)圖中節(jié)點間鏈路的集合，其中每一條鏈路代表相鄰兩節(jié)點間的直通路徑。QoS路由定義為從源節(jié)點到目的節(jié)點間找出一條滿足QoS約束，且代價最小的最佳路徑。實際問題中通常使用延時、延時抖動、帶寬、費用、丟包率5種度量參數(shù)作為網(wǎng)絡(luò)中的QoS約束[10-11]。對網(wǎng)絡(luò)拓?fù)渲械墓?jié)點V和鏈路E定義描述如下：

(1)對于任意網(wǎng)絡(luò)節(jié)點n∈V，定義延時、延時抖動、丟包率如下所示(R+表示非負(fù)實數(shù)集)。

延時函數(shù)delay(n):E→R+，表示IP包每次在網(wǎng)絡(luò)中傳送花費的平均時長。

延時抖動函數(shù)delay_jitter(n):V→R+，表示IP包傳送時間的長短變化。延時和延時抖動均可能會造成網(wǎng)絡(luò)傳輸質(zhì)量的下降。

丟包率函數(shù)packet_loss(n):V→R+，表示在傳送的過程中可能會出現(xiàn)IP包的損壞或丟失，該參數(shù)值越高表示數(shù)據(jù)受到的損害概率就越大。

(2)對于任意網(wǎng)絡(luò)中鏈路e∈E，定義延時、延時抖動、帶寬、費用4種度量，如下所示。

延時函數(shù)delay(e):E→R+。

延時抖動函數(shù)delay_jitter(e):E→R+。

帶寬函數(shù)bandwidth(e):E→R+。

費用函數(shù)cost(e):E→R+。

(3)給定一個源節(jié)點和目的節(jié)點，通過算法如果能找到一條費用最小的路徑即路由請求L，同時滿足下述條件，則該條路由請求可被接受。

帶寬約束：在路由請求L上的每條鏈路上，bandwidth(e)≥B。

丟包率約束：在路由請求L的每個節(jié)點n上，packet_loss(n)≤PL。

D、DJ、B和PL分別表示QoS路由中對延時、延時抖動、帶寬、丟包率的約束值；VL為路由請求L上的節(jié)點集合，EL為路由請求L上的鏈路集合。

2.2 QoS路由模型建立

QoS路由模型定義G中節(jié)點總數(shù)為n=|V|，給定源節(jié)點s∈V，目的節(jié)點d∈|V-|s||[12]。對無向賦權(quán)圖G中任意一個節(jié)點n∈V，定義3種度量屬性:延時函數(shù)delay(n)、延時抖動函數(shù)delay_jitter(n)和丟包率函數(shù)packet_loss(n)。對于途中任意一條鏈路e∈E，定義4種度量屬性，即延時函數(shù)delay(e)、延時抖動函數(shù)delay_jitter(e)、帶寬函數(shù)bandwidth(e)和費用函數(shù)cost(e)。

路徑p(s,d)上的總延時函數(shù)定義為

路徑p(s,d)上的最小帶寬定義為

路徑p(s,d)上的延時抖動定義為

路徑p(s,d)上的丟包率定義為

路徑p(s,d)上的費用定義為

路徑p(s,d)表示源節(jié)點s與目的節(jié)點d之間所有滿足QoS約束的路徑，則QoS路由問題為找到滿足條件delay(p(s,d))≤D、delay_jitter(p(s,d))≤DJ、bandwidth(p(s,d))≥B和packet_loss(p(s,d))≤PL的最佳路徑。

2.3 基于ACO的QoS路由算法

應(yīng)用蟻群算法模型求解QoS路由算法的具體實現(xiàn)過程如下。

Step1:給出指定網(wǎng)絡(luò)拓?fù)鋱D，設(shè)置圖中各節(jié)點和每條邊的參數(shù)值，以及QoS約束中的D、DJ、B、PL的取值，并對蟻群算法中相關(guān)參數(shù)進行如下設(shè)置。

Set t=0

NC=0 {NC是循環(huán)計數(shù)器}

NC_max，m {NC_max為循環(huán)最大次數(shù)，m為螞蟻個數(shù)}

W=s {當(dāng)前節(jié)點為起始點}

Path=s {路線初始化}

PD=0 {路線延時初始化}

cost=0 {路線費用初始化}

Step2：尋找蟻群中每只螞蟻尋找的最優(yōu)路徑。

For NC=1 to NC_max

For k=1 to m

初始化禁忌表tabu及相應(yīng)參數(shù)；

尋找可選節(jié)點集；

計算螞蟻k向各可選節(jié)點的轉(zhuǎn)移概率；

用轉(zhuǎn)盤賭法確定轉(zhuǎn)移節(jié)點j；

If節(jié)點j是目的節(jié)點d

則清空所有tabu列表，進行下一只螞蟻的遍歷；

Else

計算出螞蟻k移動到節(jié)點j之后的D、DJ和B等參數(shù)進行比較；

If不滿足約束條件

則重新選擇節(jié)點j；

Else

將螞蟻k移動到節(jié)點j，將節(jié)點j插入tabuk(s)，并進行信息素濃度的更新；

End

End

End

End

Step3：迭代尋找最短費用的路徑cost，輸出最短費用的路徑path。

cost=costs(1,1,1) {最短費用路徑初值}

if costs(p,k,m)

cost=cost(p,k,m)

path=routes{p,k,m} {找出最短費用路徑}

3 仿真實驗與優(yōu)化分析

3.1 實驗參數(shù)設(shè)置

針對QoS路由模型進行仿真實驗，預(yù)定網(wǎng)絡(luò)拓?fù)淙鐖D1所示。圖中每個節(jié)點特征用三元組(d,DJ,PL)表示，即延時、延時抖動、丟包率，每一條鏈路特征用四元組(d,DJ,B,cost)表示，即延時、延時抖動、帶寬、費用[10]。參數(shù)設(shè)置如表1、表2所示。

表1 蟻群算法參數(shù)

表2 QoS路由參數(shù)

3.2 實驗結(jié)果分析

實驗給定的路由請求為源節(jié)點1到目的節(jié)點6，實驗中預(yù)定網(wǎng)絡(luò)拓?fù)涞慕⑹峭ㄟ^鄰接矩陣的形式繪制，如圖1所示。程序運行繪制的實驗拓?fù)淙鐖D2所示，其中節(jié)點間鏈路的數(shù)值為該條鏈路的費用。實驗運行共30次，產(chǎn)生最優(yōu)解(1→5→6)的仿真結(jié)果如圖3所示。產(chǎn)生次優(yōu)解(1→3→5→6)的仿真結(jié)果如圖4所示。

表3 實驗運行結(jié)果

圖1 預(yù)定網(wǎng)絡(luò)拓?fù)鋱D 圖2 實驗網(wǎng)絡(luò)拓?fù)鋱D

圖3 最優(yōu)路徑(1→5→6) 圖4 次最優(yōu)路徑(1→3→5→6)

運行程序30次所得的仿真結(jié)果，如表3所示。

通過算例仿真實驗結(jié)果表明：本文設(shè)計的基于蟻群的QoS路由算法在實際網(wǎng)絡(luò)路由中能夠準(zhǔn)確發(fā)現(xiàn)最優(yōu)解和次優(yōu)解，同時也驗證了該算法在求解QoS網(wǎng)絡(luò)路由問題上應(yīng)用效果良好。

3.3 參數(shù)優(yōu)化分析

在實驗過程中，針對影響算法解質(zhì)量的參數(shù)進行不同的設(shè)置并進行仿真實驗，實驗參數(shù)的不同取值仿真結(jié)果，如表4所示。

通過實驗結(jié)果可知，蟻群算法參數(shù)值設(shè)置對精確求解影響較大，優(yōu)化參數(shù)選擇能夠提高最優(yōu)解和次優(yōu)解的出現(xiàn)概率，保證質(zhì)量較差解出現(xiàn)的概率最小，具體參數(shù)優(yōu)化分析如下：

(1)信息啟發(fā)因子α的取值越大表示螞蟻個體選擇之前經(jīng)過的路徑的概率就越高，降低算法搜索路徑的隨機性，加快了算法的收斂速度，導(dǎo)致算法容易過早的進入局部最優(yōu)狀態(tài)。

(2)期望啟發(fā)因子β的取值越大表示螞蟻選擇局部最優(yōu)路徑的概率就越高，降低算法搜索的隨機性，同時造成算法的收斂速度加快，使算法容易進入局部最優(yōu)的狀態(tài)。

(3)信息素?fù)]發(fā)度ρ的取值過大時，將會導(dǎo)致信息素消失過快，容易導(dǎo)致之前選擇過的路徑被再次搜索到，造成算法搜索隨機性和全局搜索能力降低。當(dāng)ρ的取值過小時，隨著時間推移信息素含量變化很小，算法搜索的隨機性和全局搜索能力雖然有所提高，但會造成算法的收斂速度降低。通過實驗反復(fù)測試得到ρ的取值在0.5～0.9之間最佳。

表4 不同參數(shù)值得仿真結(jié)果

(4)螞蟻個體數(shù)m取值較大，信息素的正反饋效應(yīng)得不到很好體現(xiàn)，雖能提高搜索的隨機性，但收斂速度得不到保證；反之，m取值較少，在解決規(guī)模較大的問題時，雖然會加快收斂速度，但會導(dǎo)致算法搜索的隨機性下降，造成算法穩(wěn)定性的降低，提高了算法早熟的概率。

4 結(jié) 論

針對蟻群算法求解QoS網(wǎng)絡(luò)路由優(yōu)化問題，通過分析QoS網(wǎng)絡(luò)路由具體問題，建立相應(yīng)QoS路由模型，并進行仿真實驗。實驗結(jié)果表明，本文提出的基于蟻群算法解決QoS路由問題的方法是有效的，并具有很好的求解效果。同時對蟻群算法信息啟發(fā)因子、期望啟發(fā)因子、信息素的揮發(fā)程度等參數(shù)取值進行優(yōu)化分析，給出最佳取值范圍，提高了求解精度與運算效率。