波長分配方法

1、波長分配方法隨著波分復(fù)用技術(shù)的應(yīng)用，幾個(gè)光信號(hào)可在單根光纖傳輸。這種技術(shù)可以更有效的利用光纖的巨大力量，但也帶來了新的網(wǎng)絡(luò)設(shè)計(jì)和管理問題，尤其是當(dāng)波長轉(zhuǎn)換節(jié)點(diǎn)中沒有可能的。考慮在這樣的網(wǎng)絡(luò)中的路由和波長分配問題，一旦路線是固定的波長分配基本上是一個(gè)圖著色問題。對(duì)于一個(gè)給定的圖著色算法，在當(dāng)前的研究中較主流的有貪婪算法，窮舉搜索，模擬退火以及遺傳算法。都是相當(dāng)不錯(cuò)的路由和波長分配性能，本文主要介紹在路由選擇確定的情況下的波長分配問題，且著重從貪婪算法和窮舉搜索算法來講述波長分配方法。在本文中，我們集中在WDM網(wǎng)絡(luò)路由和波長分配問題。當(dāng)多個(gè)信號(hào)共享相同的纖維，他們必須使用不同的波長。現(xiàn)有的技術(shù)設(shè)置

2、了一個(gè)上限的波長數(shù)。因此，我們認(rèn)為，導(dǎo)致建立一個(gè)給定的連接在與最低數(shù)量的波長網(wǎng)絡(luò)設(shè)置的問題。在制定的最優(yōu)化問題，取決于是否有可能在波長轉(zhuǎn)換節(jié)點(diǎn)或沒有。如果波長轉(zhuǎn)換的最佳解決方案是可能的只是最大限度地減少了使用的通道的鏈接的最大數(shù)量。路由問題是在正常的電路交換網(wǎng)絡(luò)，在唯一的限制因素是對(duì)每一個(gè)環(huán)節(jié)通道數(shù)相同。 另一方面，如果波長轉(zhuǎn)換不能在節(jié)點(diǎn)完成后，這便產(chǎn)生了優(yōu)化問題新的約束。每個(gè)連接使用上沿線的各個(gè)環(huán)節(jié)相同的波長。一個(gè)可行的解決方案使用小于或等于各個(gè)環(huán)節(jié)的波長數(shù)比有可用的，沒有兩個(gè)連接共享一個(gè)共同的聯(lián)系具有相同的波長。 也可以使用波長轉(zhuǎn)換網(wǎng)絡(luò)。在本文中不討論這種網(wǎng)絡(luò)，因此，我們假定波長轉(zhuǎn)換不能在

3、任何節(jié)點(diǎn)完成。我們還假設(shè)沒有任何的網(wǎng)絡(luò)動(dòng)態(tài)重構(gòu)的需要，即連接設(shè)置是靜態(tài)的。 路由和波長分配問題是緊密聯(lián)系在一起。我們首先要確定每個(gè)連接的線路（即路由），然后嘗試使用最小數(shù)量的波長來進(jìn)行波長分配。這樣做，這樣反復(fù)的進(jìn)行著色嘗試目的在于對(duì)路由連接不改變的同時(shí)使用最少的顏色來完成全圖的著色。同時(shí)，在實(shí)踐中以求找到比現(xiàn)有技術(shù)使用更加少顏色的著色方案。在路由和波長分配過程是代表在圖1。在左邊是一個(gè)物理網(wǎng)絡(luò)。中間的是固定路由波長分配圖，右側(cè)的圖是圖著色方案，其中的節(jié)點(diǎn)表示連接，按來源目的地對(duì)應(yīng)表示，和鄰居節(jié)點(diǎn)的連接（表示之間存在共享），如果且僅當(dāng)相應(yīng)的連接有著一些共同的聯(lián)系。為了避免在網(wǎng)絡(luò)圖波長的沖突，鄰

4、居節(jié)點(diǎn)總是有不同的顏色。 圖 1 實(shí)例網(wǎng)絡(luò)以及波長分配過程兩個(gè)節(jié)點(diǎn)之間的最短路徑可以通過使用如Dijkstra算法或Floyd算法。這兩種算法具有相同的復(fù)雜度為O，如果每個(gè)節(jié)點(diǎn)對(duì)之間的路徑進(jìn)行搜索。在實(shí)踐中，F(xiàn)loyd算法通常會(huì)好一點(diǎn)，由于常系數(shù)較小。 一旦路由是固定的，波長分配問題便是是盡量減少使用的波長數(shù)的圖著色問題。如上所述，波長分配可以映射到一個(gè)圖節(jié)點(diǎn)著色問題，下面從貪婪算法和窮舉搜索算法來講述圖著色的波長分配問題。 2波長分配 當(dāng)路由是固定的，我們的任務(wù)是盡量減少所用的波長數(shù)。這個(gè)問題可以表示為圖節(jié)點(diǎn)著色問題。在著色圖中每個(gè)節(jié)點(diǎn)代表一個(gè)點(diǎn)到點(diǎn)的連接見上圖1。這些連接共用某些環(huán)節(jié)是在著

5、色圖的鄰居，即一個(gè)邊緣連接，因此必須用不同的顏色著色。在這里，我們假設(shè)是完全一樣的鏈接，鏈接即能力是相同的。因此，我們唯一的目標(biāo)是盡量減少所需的不同波長數(shù)。對(duì)應(yīng)著色圖，一種顏色對(duì)應(yīng)一種波長，整個(gè)圖中最終使用的顏色總數(shù)便是網(wǎng)絡(luò)需要使用的最少波長數(shù)。 由于圖節(jié)點(diǎn)著色問題是NP完全啟發(fā)式方法必須用于實(shí)際的解決辦法。許多的啟發(fā)式方法已被提出。其中一些是基于眾所周知的通用方法，如模擬退火和遺傳算法。其中最具代表的是貪婪算法和窮舉搜索算法。2.1貪心算法 貪婪算法在于通過選擇度最大的節(jié)點(diǎn)，然后給予其一種顏色，然后再在其相鄰節(jié)點(diǎn)中選擇度最大的節(jié)點(diǎn)，對(duì)其和與其不相鄰的節(jié)點(diǎn)給予另一種顏色，依次類推，整個(gè)過程在選

6、擇顏色要注意的有兩點(diǎn)：1) 下一步的節(jié)點(diǎn)選擇的依據(jù)根據(jù)其相鄰節(jié)點(diǎn)數(shù)(即度的數(shù)目)；2) 在給予顏色的時(shí)候不能引起沖突(及相鄰節(jié)點(diǎn)的顏色不能相同)。整過貪婪算法的過程圖解如下：1 確定路由以及網(wǎng)絡(luò)連接圖2 連接圖著色迭代過程3 波長分配結(jié)果 有上面的著色圖可知，實(shí)例的光網(wǎng)絡(luò)需要最少分配3種波長來進(jìn)行業(yè)務(wù)連接傳輸。2.2窮舉搜索 該算法總能找到最佳的著色結(jié)果過程如圖2。該算法在每一步中的隨機(jī)選定一個(gè)節(jié)點(diǎn)（一般為圖的葉子節(jié)點(diǎn)）然后對(duì)不是其相鄰節(jié)點(diǎn)的節(jié)點(diǎn)進(jìn)行搜索。這些節(jié)點(diǎn)可以使用相同的顏色，節(jié)點(diǎn)被賦予相同的顏色后，我們便可以將他們合并成一個(gè)節(jié)點(diǎn)，同時(shí)繼承其中所有的關(guān)系。以此類推，直到最后，我們選擇其中獲得具有最小的節(jié)點(diǎn)號(hào)的圖（即每個(gè)節(jié)點(diǎn)是所有其他節(jié)點(diǎn)的相鄰節(jié)點(diǎn)）。 隨著處理的節(jié)點(diǎn)數(shù)目的增加，算法的復(fù)雜度也隨之成倍數(shù)增加，一個(gè)較好的方法是圖的分解，將著色圖分