基于精英螞蟻算法的動(dòng)態(tài)路由和波長(zhǎng)分配研究

孫文勝 ，景勇祥

(杭州電子科技大學(xué)通信工程學(xué)院，杭州310018)

下一代密集波分復(fù)用光網(wǎng)絡(luò)DWDM(Dense Wavelength Division Multiplexing)將會(huì)工作在擁有光分組交換、光波長(zhǎng)交換的混合模式中，而實(shí)現(xiàn)在混合模式下工作的關(guān)鍵技術(shù)之一就是路由和波長(zhǎng)分配RWA(Routing and Wavelength Assignment)［1］。在動(dòng)態(tài)路由和波長(zhǎng)分配DRWA(Dynamic Routing and Wavelength Assignment)問題中由于連接請(qǐng)求是動(dòng)態(tài)的，因此研究DRWA 問題的目的是如何在減少所需要的波長(zhǎng)數(shù)的同時(shí)降低光路連接請(qǐng)求的阻塞率［2-3］。同時(shí)在RWA 問題中還需要注意“波長(zhǎng)連續(xù)性的限制”和“不同波長(zhǎng)的限制”這兩個(gè)限制條件，這又為解決RWA 問題帶來了一定的困難。目前已經(jīng)有遺傳算法、蟻群算法等啟發(fā)式算法應(yīng)用到了DRWA 問題中［4-6］。文章將精英策略螞蟻系統(tǒng)EAS(Elite strategy Ant System)算法應(yīng)用到DRWA 問題中。通過與最短路徑算法和基本蟻群算法進(jìn)行比較后，可以發(fā)現(xiàn)EAS 算法在降低網(wǎng)絡(luò)阻塞率方面具有明顯的優(yōu)勢(shì)，當(dāng)波長(zhǎng)數(shù)目增多或者網(wǎng)絡(luò)負(fù)載增加時(shí)這種優(yōu)勢(shì)更加明顯，能有效提高DWDM 光網(wǎng)絡(luò)中帶寬資源利用率。

1 EAS 算法模型

蟻群算法應(yīng)按是一種受真實(shí)的螞蟻行為啟發(fā)的新型模擬進(jìn)化算法［7-9］。而精英策略螞蟻系統(tǒng)算法(EAS)是對(duì)基本螞蟻算法的改進(jìn)，它的思想是在基本螞蟻系統(tǒng)算法的基礎(chǔ)上，對(duì)到目前為止找到的最優(yōu)路徑實(shí)施一種精英策略，得到額外反饋信息的螞蟻將更加容易找到最優(yōu)路徑［10］。

1.1 路徑的構(gòu)建

每一只螞蟻都使用逐步?jīng)Q策方法從源點(diǎn)開始建立問題的解。在每一個(gè)結(jié)點(diǎn)上，螞蟻都會(huì)讀取存儲(chǔ)在結(jié)點(diǎn)上的局部信息，并根據(jù)路徑(i，j)在t 時(shí)刻的信息素τij來選擇移動(dòng)到哪一個(gè)結(jié)點(diǎn)。本文將所有邊上的信息素都固定為1，即τij=1，?(i，j)∈A，ηij為路徑(i，j)的啟發(fā)式信息，其一般為dij的倒數(shù)，dij為路徑(i，j)的長(zhǎng)度，α 和β 分別代表信息素和啟發(fā)式信息的相對(duì)影響力。假設(shè)螞蟻k 在t 時(shí)刻的轉(zhuǎn)移概率)為:

式中，U 為可行頂點(diǎn)集。當(dāng)α=0 時(shí)，此時(shí)EAS 算法相當(dāng)于經(jīng)典的隨機(jī)貪心算法;而當(dāng)β=0 時(shí)，此時(shí)只有信息素在起作用，而沒有利用任何啟發(fā)式信息帶來的偏向性，這將使得算法很快地陷入停滯的狀態(tài)，此時(shí)所有的螞蟻將按照同一條路線移動(dòng)，最后構(gòu)建出同一條路徑。目前構(gòu)建到的最優(yōu)路徑即為Tbs。

1.2 信息素的更新

當(dāng)螞蟻到達(dá)目的結(jié)點(diǎn)后，它就會(huì)從正向模式轉(zhuǎn)換為逆向模式，各邊上的信息素將會(huì)隨著螞蟻沿著原路徑返回時(shí)被更新。假設(shè)螞蟻k 在路徑(i，j)上釋放的信息素?cái)?shù)量為，任意一條邊的路徑長(zhǎng)度均設(shè)定為1，信息素的揮發(fā)度為ρ(0≤ρ≤1)。參數(shù)ρ 的作用是避免信息素的無(wú)限積累，而且還可以使算法“忘記”之前較差的路徑。事實(shí)上，如果一條邊沒有被任何一條螞蟻選擇，那么這條邊的信息素將會(huì)以迭代次數(shù)的指數(shù)級(jí)遞減。而針對(duì)路徑Tbs的格外強(qiáng)化是通過向Tbs中每一條邊增加e/Cbs大小的信息素，其中e 定義了給予路徑Tbs的權(quán)值大小，本文將其定義為e=16，而Cbs代表了Tbs的路徑長(zhǎng)度。

這樣，信息素的更新規(guī)則就變?yōu)?

設(shè)CK為第k 只螞蟻在本次循環(huán)中所走的路徑長(zhǎng)度，Q 表示一只螞蟻經(jīng)過一次循環(huán)后代表的所有信息，為一固定常數(shù)，文中選定Q 為常數(shù)1，則:

可以發(fā)現(xiàn)螞蟻構(gòu)建的路徑越好，那么路徑上的各條邊就會(huì)獲得更多的信息素，從而在螞蟻?zhàn)罱K選路的過程中尋找到最短路徑。

2 EAS 算法與DRWA 問題結(jié)合和實(shí)現(xiàn)

考慮到“波長(zhǎng)連續(xù)性的限制”和“不同波長(zhǎng)的限制”的限制，本文DWDM 光網(wǎng)絡(luò)以包交換的形式工作，網(wǎng)絡(luò)拓?fù)湟蔡崆邦A(yù)知，并設(shè)定DWDM 網(wǎng)絡(luò)中的每一個(gè)結(jié)點(diǎn)都具有相同的波長(zhǎng)數(shù)目，且各個(gè)結(jié)點(diǎn)不具有波長(zhǎng)轉(zhuǎn)換功能。

在仿真中使用了典型的美國(guó)國(guó)家科學(xué)基金會(huì)網(wǎng)絡(luò)NSFNET(National Science Foundation Network)，該網(wǎng)絡(luò)的拓?fù)渚哂?4 個(gè)結(jié)點(diǎn)和21 個(gè)連接數(shù)，如圖1 所示。

圖1 擁有14 個(gè)結(jié)點(diǎn)、21 個(gè)連接數(shù)的虛擬網(wǎng)絡(luò)的拓?fù)鋱D

2.1 路徑的構(gòu)建和路由表的更新

為了利用螞蟻能根據(jù)信息素來進(jìn)行路由選擇，網(wǎng)絡(luò)中的每個(gè)結(jié)點(diǎn)的路由表用信息素表來代替。信息素表中的信息素濃度以概率值的形式來表示，這樣的選擇路由的方式與螞蟻根據(jù)信息素多少選擇路徑具有本質(zhì)上的一致性。為了支持動(dòng)態(tài)路由選擇，一個(gè)擁有ki個(gè)鄰結(jié)點(diǎn)的結(jié)點(diǎn)i 擁有路由表該路由表具有N-1 行、ki列，每一行對(duì)應(yīng)的是目的結(jié)點(diǎn)，每一列對(duì)應(yīng)的是鄰結(jié)點(diǎn)，其中N 為結(jié)點(diǎn)個(gè)數(shù)。在路由表中代表的是一個(gè)螞蟻在尋找目的節(jié)點(diǎn)d 的過程中選擇n 作為下一跳的可能性，這個(gè)概率也就是前面所提到的螞蟻k 在t 時(shí)刻的轉(zhuǎn)移概率為NSF 網(wǎng)絡(luò)中結(jié)點(diǎn)5 的路由表如表1 所示。

表1 NSF 網(wǎng)絡(luò)中結(jié)點(diǎn)5 的路由表

當(dāng)源結(jié)點(diǎn)為5 和目的節(jié)點(diǎn)13 時(shí)并且連接請(qǐng)求到來時(shí)，鄰結(jié)點(diǎn)9 將會(huì)被選為下一跳的結(jié)點(diǎn)，因?yàn)橥ㄟ^概率比較可以明顯得到

同時(shí)對(duì)于任一的一個(gè)目的節(jié)點(diǎn)，始終滿足這樣一個(gè)規(guī)律:所有的鄰結(jié)點(diǎn)都必須滿足相加總和為1，也就是每行元素相加都為1，即:

對(duì)于路由表的更新，當(dāng)螞蟻到達(dá)目的結(jié)點(diǎn)之后，它就會(huì)從正向模式改為逆向模式，然后一步一步地按原路返回到源結(jié)點(diǎn)處。在螞蟻開始返回之前，會(huì)先消除在向目的結(jié)點(diǎn)尋找過程中所經(jīng)過路徑上的環(huán)路，以此來優(yōu)化路徑。在返回過程中，螞蟻通過釋放大小為Δτ的信息素，來改變轉(zhuǎn)移概率，最終完成對(duì)路由表的更新。

EAS 算法的工作流程如圖2 所示。

圖2 EAS 算法的工作流程圖

2.2 數(shù)據(jù)包的傳輸和更新

螞蟻在尋找最短路徑的過程中，它會(huì)采集兩種信息:路徑的長(zhǎng)度和擁塞信息。每一個(gè)“螞蟻”(即數(shù)據(jù)包)攜帶以下的信息:源結(jié)點(diǎn)、目的結(jié)點(diǎn)、二進(jìn)制碼序列M、阻塞信息、路徑信息和TTL。

由于每一個(gè)結(jié)點(diǎn)有擁有相同的波長(zhǎng)數(shù)目，因此該文用1 個(gè)二進(jìn)制碼序列m 來一一對(duì)應(yīng)結(jié)點(diǎn)中的各個(gè)波長(zhǎng)，其中0 表示該波長(zhǎng)不可用，1 表示該波長(zhǎng)可用。而每一個(gè)螞蟻攜帶的二進(jìn)制碼序列M 反應(yīng)的是經(jīng)過之前結(jié)點(diǎn)后各個(gè)波長(zhǎng)的使用狀態(tài)，其中0也表示某波長(zhǎng)不可用，1 表示該波長(zhǎng)可用。然后將數(shù)據(jù)包M 和結(jié)點(diǎn)m 進(jìn)行“與”運(yùn)算，那么就可以得到最新的波長(zhǎng)使用情況。

假如在WDM 網(wǎng)絡(luò)中擁有5 個(gè)波長(zhǎng)800 nm、900 nm、1 000 nm、1 100 nm、1 200 nm。在某結(jié)點(diǎn)假如只有1 000 nm 和1 200 nm 可用，那么二進(jìn)制碼序列M1結(jié)點(diǎn)則為00101，而螞蟻攜帶的數(shù)據(jù)包中的二進(jìn)制序列M1中為900 nm 和1 200 nm 可用，其二進(jìn)制碼序列為01001，那么將二者進(jìn)行與運(yùn)算以后，可以得到更新后的M1為00001，即只剩下1 200 nm 波長(zhǎng)可用，如表2 所示。

表2 波長(zhǎng)使用情況

路徑信息中不僅包含經(jīng)過路徑的長(zhǎng)度，還包括該螞蟻所經(jīng)過的所有結(jié)點(diǎn)名稱。在算法中，當(dāng)螞蟻到達(dá)其目的節(jié)點(diǎn)或者無(wú)法為新路徑尋找到一個(gè)可分配的波長(zhǎng)的時(shí)候，螞蟻將會(huì)被殺死，以此避免對(duì)網(wǎng)絡(luò)造成擁塞。同時(shí)還設(shè)置了一個(gè)生存時(shí)間TTL，每經(jīng)過一個(gè)結(jié)點(diǎn)，其TTL 減少1，當(dāng)TTL 減少為0 時(shí)，螞蟻將被殺死，以此提高算法的運(yùn)算效率。

在EAS 算法中，還加入了一個(gè)判斷機(jī)制，用來避免當(dāng)多次找到最優(yōu)路徑后算法迭代次數(shù)遠(yuǎn)遠(yuǎn)小于最大迭代次數(shù)時(shí)造成的資源浪費(fèi)。在螞蟻找到路徑T 后，會(huì)將其與之前存儲(chǔ)的最優(yōu)路徑Tbs進(jìn)行對(duì)比，在這里、會(huì)設(shè)置一個(gè)計(jì)數(shù)值P，當(dāng)螞蟻尋找到最優(yōu)路徑，計(jì)數(shù)值P 都會(huì)減去1，當(dāng)P＜0 即認(rèn)為其已經(jīng)找到最優(yōu)路徑，算法結(jié)束。

3 仿真結(jié)果和分析

由于DRWA 問題中，連接數(shù)是動(dòng)態(tài)的，因此該文將NSF 網(wǎng)絡(luò)看成一個(gè)話務(wù)網(wǎng)絡(luò)，則其網(wǎng)絡(luò)負(fù)載就可以表示為:

式中話務(wù)量A 也就是相當(dāng)于DWDM 網(wǎng)絡(luò)的負(fù)載，而話務(wù)呼叫次數(shù)C 也就是DWDM 光網(wǎng)絡(luò)中的連接請(qǐng)求數(shù)目。在仿真中我們將話務(wù)持續(xù)時(shí)間T 固定，取值為5 s，只改變連接請(qǐng)求數(shù)目C。

對(duì)于DRWA 問題，文獻(xiàn)中往往將優(yōu)化目標(biāo)選定為最大化網(wǎng)絡(luò)收益或者最小化網(wǎng)絡(luò)損失，將優(yōu)化目標(biāo)簡(jiǎn)化為最大化網(wǎng)絡(luò)的連接數(shù)或者最小化網(wǎng)絡(luò)的擁塞率，本文選擇最小化網(wǎng)絡(luò)的擁塞率。鏈路中的擁塞率定義為該鏈路上可用的波長(zhǎng)數(shù)目與總波長(zhǎng)數(shù)目之比，即:

那么可用波長(zhǎng)數(shù)目越多，則該鏈路的擁塞也就越小。

在仿真中，將各項(xiàng)參數(shù)設(shè)置如下:信息素影響力α=1，啟發(fā)式信息β=1，信息素?fù)]發(fā)系數(shù)ρ=0.5，最優(yōu)路徑影響因子e=16，螞蟻數(shù)目m=25，計(jì)算值p=10，最大的迭代次數(shù)為50。為了保證數(shù)據(jù)的可靠性，將每種算法運(yùn)行20 次，取其阻塞率的平均值。仿真結(jié)果如圖3 所示。然后，選擇負(fù)載相同的情況，其仿真結(jié)果如圖4 所示。對(duì)于不同的波長(zhǎng)數(shù)目，隨著波長(zhǎng)數(shù)目的增多，網(wǎng)絡(luò)阻塞率都會(huì)明顯地下降。而當(dāng)波長(zhǎng)數(shù)目選擇一定的時(shí)候EAS 算法都比最短路徑路由算法和基本蟻群算法擁有更低的阻塞率，而當(dāng)波長(zhǎng)數(shù)目越多時(shí)，這種優(yōu)勢(shì)越發(fā)明顯。

圖3 波長(zhǎng)數(shù)W=16 時(shí)3 種算法的阻塞率

圖4 負(fù)載相同時(shí)3 種算法的阻塞率

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

作為DWDM 光網(wǎng)絡(luò)中首要解決的DRWA 問題，由于其連接請(qǐng)求的動(dòng)態(tài)性，以及受到DWDM 光網(wǎng)絡(luò)的兩個(gè)限制條件的限制，文章將用于模擬自然界螞蟻尋找最短路徑行為的EAS 算法應(yīng)用到解決DRWA 問題中，可以發(fā)現(xiàn)與最短路徑路由算法和基本蟻群算法相比，EAS 算法能夠更加有效地降低光網(wǎng)絡(luò)阻塞率，提高網(wǎng)絡(luò)中帶寬資源的利用效率。同時(shí)在實(shí)驗(yàn)中增加蟻群數(shù)目能夠提高螞蟻正確選擇最短路徑的概率，但同時(shí)網(wǎng)絡(luò)開銷也會(huì)增大。因此如何處理好蟻群數(shù)目和網(wǎng)絡(luò)開銷的動(dòng)態(tài)平衡問題，以及在仿真中對(duì)各個(gè)參數(shù)的選取設(shè)定和解決算法計(jì)算開銷大的諸多問題，這些都有待于以后在算法的改進(jìn)和實(shí)驗(yàn)的驗(yàn)證。

［1］ 付明磊.波長(zhǎng)路由光網(wǎng)絡(luò)中的路由和波長(zhǎng)分配算法研究［D］.杭州:浙江工業(yè)大學(xué)，2007.

［2］ 樂孜純，張明，全必勝. 光網(wǎng)絡(luò)實(shí)用組網(wǎng)技術(shù)［M］. 西安:西安電子科技大學(xué)出版社，2008:20-45.

［3］ 張仕俊.WDM 光網(wǎng)絡(luò)中路由與波長(zhǎng)分配算法的研究［J］.杭州電子科技大學(xué)學(xué)報(bào)，2010，26(3):156-158.

［4］ Joan Triay，Cristina Cervello-Pastor. An Ant-Based Algorithm for Distributed Routing and Wavelength Assignment in Dynamic Optical Networks［J］.IEEE Journal on Selected Areas in Communications，2010，28(4):542-552.

［5］ 段海濱. 蟻群算法原理及其應(yīng)用［M］. 北京:科學(xué)出版社，2005.

［6］ 張穎，朱娜，朱士芬. 基于D ～* 思想的動(dòng)態(tài)RWA 算法研究［J］.光通信研究，2007(2):4-7.

［7］ 段亞偉，朱娜，李正茂.基于遺傳算法的動(dòng)態(tài)RWA 問題的研究［J］.計(jì)算機(jī)工程與應(yīng)用，2005，23:132-134.

［8］ Dorigo M. Heuristic from Nature for Hard Combinatorial Optimization Problems［J］. International Transactions in Operational Research，1996，3(1):1-21.

［9］ 陳旭，宋愛國(guó).螞蟻算法與免疫算法結(jié)合求解TSP 問題［J］.傳感技術(shù)學(xué)報(bào)，2006(2):504-507.

［10］ Marco Dorigo，Thomas Stuitizle.Ant Colony Optimization.［M］.北京:清華大學(xué)出版社，2007:30-51.