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

孫文勝 ，景勇祥

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

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

1 EAS 算法模型

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

1.1 路徑的構建

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

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

1.2 信息素的更新

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

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

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

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

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

考慮到“波長連續(xù)性的限制”和“不同波長的限制”的限制，本文DWDM 光網(wǎng)絡以包交換的形式工作，網(wǎng)絡拓撲也提前預知，并設定DWDM 網(wǎng)絡中的每一個結點都具有相同的波長數(shù)目，且各個結點不具有波長轉換功能。

在仿真中使用了典型的美國國家科學基金會網(wǎng)絡NSFNET(National Science Foundation Network)，該網(wǎng)絡的拓撲具有14 個結點和21 個連接數(shù)，如圖1 所示。

圖1 擁有14 個結點、21 個連接數(shù)的虛擬網(wǎng)絡的拓撲圖

2.1 路徑的構建和路由表的更新

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

表1 NSF 網(wǎng)絡中結點5 的路由表

當源結點為5 和目的節(jié)點13 時并且連接請求到來時，鄰結點9 將會被選為下一跳的結點，因為通過概率比較可以明顯得到

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

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

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

圖2 EAS 算法的工作流程圖

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

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

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

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

表2 波長使用情況

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

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

3 仿真結果和分析

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

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

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

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

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

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

圖4 負載相同時3 種算法的阻塞率

4 結束語

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

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

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

［3］ 張仕俊.WDM 光網(wǎng)絡中路由與波長分配算法的研究［J］.杭州電子科技大學學報，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］ 段海濱. 蟻群算法原理及其應用［M］. 北京:科學出版社，2005.

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

［7］ 段亞偉，朱娜，李正茂.基于遺傳算法的動態(tài)RWA 問題的研究［J］.計算機工程與應用，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］ 陳旭，宋愛國.螞蟻算法與免疫算法結合求解TSP 問題［J］.傳感技術學報，2006(2):504-507.

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