基于蟻群算法的QoS路由模型的設(shè)計(jì)與優(yōu)化

高新成， 劉德聚， 王莉利， 馬樹(shù)軒

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

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

1 蟻群算法模型

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

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

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

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

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

1.1 轉(zhuǎn)移概率

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

(1)

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

1.2 信息素的更新

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

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

(2)

(3)

(4)

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

2 基于A(yíng)CO的QoS路由模型設(shè)計(jì)

2.1 QoS路由問(wèn)題描述

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

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

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

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

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

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

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

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

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

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

(3)給定一個(gè)源節(jié)點(diǎn)和目的節(jié)點(diǎn)，通過(guò)算法如果能找到一條費(fèi)用最小的路徑即路由請(qǐng)求L，同時(shí)滿(mǎn)足下述條件，則該條路由請(qǐng)求可被接受。

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

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

D、DJ、B和PL分別表示QoS路由中對(duì)延時(shí)、延時(shí)抖動(dòng)、帶寬、丟包率的約束值；VL為路由請(qǐng)求L上的節(jié)點(diǎn)集合，EL為路由請(qǐng)求L上的鏈路集合。

2.2 QoS路由模型建立

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

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

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

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

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

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

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

2.3 基于A(yíng)CO的QoS路由算法

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

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

Set t=0

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

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

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

Path=s {路線(xiàn)初始化}

PD=0 {路線(xiàn)延時(shí)初始化}

cost=0 {路線(xiàn)費(fèi)用初始化}

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

For NC=1 to NC_max

For k=1 to m

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

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

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

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

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

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

Else

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

If不滿(mǎn)足約束條件

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

Else

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

End

End

End

End

Step3：迭代尋找最短費(fèi)用的路徑cost，輸出最短費(fèi)用的路徑path。

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

if costs(p,k,m)

cost=cost(p,k,m)

path=routes{p,k,m} {找出最短費(fèi)用路徑}

3 仿真實(shí)驗(yàn)與優(yōu)化分析

3.1 實(shí)驗(yàn)參數(shù)設(shè)置

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

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

表2 QoS路由參數(shù)

3.2 實(shí)驗(yàn)結(jié)果分析

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

表3 實(shí)驗(yàn)運(yùn)行結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 論

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