WDM網(wǎng)絡(luò)中靜態(tài)路由和波長分配的隨機(jī)搜索算法研究（英文版）.pdf

1、隨著人們對高速高質(zhì)量數(shù)據(jù)傳輸，以及高容量、大帶寬需求的日益增加，每個超級通道以每秒太比特的速率傳輸成為發(fā)展趨勢，因此，基于波分復(fù)用(WDM)的光網(wǎng)絡(luò)成為研究熱點(diǎn)。在基于波分復(fù)用光網(wǎng)絡(luò)中，終端用戶通過全光WDM信道進(jìn)行通信，這樣需要建立有效的連接。在光網(wǎng)絡(luò)中，每條光路的路由選擇和波長分配受到約束條件的影響，在波長沖突約束的情況下，兩個光通道不能共享一個物理鏈路，且在一個鏈路上使用相同的波長。同時，在波長連續(xù)性約束的情況下，相同的波長必須分

2、配到整個光路的所有鏈接。因此，為了實(shí)現(xiàn)光纖連接的最大化，有必要對靜態(tài)路由和波長分配方法進(jìn)行研究。本文，在給定的連接矩陣下，我們對不需要波長轉(zhuǎn)換器的WDM網(wǎng)絡(luò)中的靜態(tài)最大路由和波長分配問題進(jìn)行研究，開展的主要創(chuàng)新工作如下:
　　建立了一種新的最大化路由和波長分配的數(shù)學(xué)模型，分析其制約因素。
　　實(shí)現(xiàn)了四種高效的隨機(jī)搜索算法，即:隨機(jī)優(yōu)化算法(ROA)，遺傳算法(GA)，Tabu搜索算法(TSA)和進(jìn)化規(guī)劃(EP)算法來解決最大

3、化路由和波長分配。
　　提出了一種新的高效的回溯算法，處理最大化路由和波長分配的路由子問題。由于采用回溯算法，初始搜索空間包含所有可能的候選光路，因此，每個連接請求都有機(jī)會得到處理。
　　對隨機(jī)優(yōu)化算法，遺傳算法，Tabu搜索算法和進(jìn)化規(guī)劃算法進(jìn)行實(shí)驗研究，分析比較了四種算法在光纖連接數(shù)目方面的性能和運(yùn)行時問。
　　通過對最大化路由和波長分配進(jìn)行建模，實(shí)驗研究隨機(jī)優(yōu)化算法，遺傳算法，Tabu搜索算法的性能，我們不僅說明

4、了實(shí)行啟發(fā)式算法的優(yōu)越性，而且顯示了每種算法達(dá)到最優(yōu)性能的條件。實(shí)驗結(jié)果表明，當(dāng)所有的需求總數(shù)分別為5，20或100時，相比GA算法，TSA算法性能提高可以達(dá)到23％，同時，相比ROA算法，TSA算法性能提高達(dá)到10％。當(dāng)所有的需求總數(shù)為1000時，相比TSA算法，GA算法性能提高6％，相比ROA算法，GA算法性能提高7％。然而，TSA算法花費(fèi)的平均時問是GA算法的5倍，是ROA算法的29倍。另外，我們對隨機(jī)優(yōu)化算法，遺傳算法，Tabu