波長(zhǎng)分配方法

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

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

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

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

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

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