使用可調ADM的全光網(wǎng)絡任務調度問題研究.pdf

1、全光傳輸網(wǎng)絡以其穩(wěn)定性好和傳輸容量大等優(yōu)點，正迅速成為帶寬需求較大的下一代通信網(wǎng)絡主要發(fā)展方向之一。基于波分復用(Wavelength DivisionMultiplexing-WDM)技術，可以在一根光纖中同時傳輸多個不同波長的光信號，從而可以在不需重新鋪設物理網(wǎng)絡的情況下，大大提高光纖的傳輸容量。 本文研究了在為每個光節(jié)點配置一個可調加載/下載復用器(Add/DropMultiplexer-ADM)的WDM全光網(wǎng)絡上的任務調

2、度問題(StADM問題)，針對有向環(huán)網(wǎng)和對稱樹網(wǎng)這兩種拓撲結構提出了幾個新穎的算法。本文的主要工作和貢獻如下： (1) 證明了全光有向環(huán)網(wǎng)上的StADM問題是NP-Hard的。根據(jù)證明的歸約過程，設計了一個近似算法GCA(Graph Coloring Algorithm)，分析了它的理論上界為「 2．2Opt(R)+1．9 」，其中Opt(R)是調度請求的最優(yōu)解：接著進一步剖析了有向環(huán)網(wǎng)上的請求沖突關系，提出了一種按照請求的次序

3、奇偶劃分的貪心算法PPA(Parity Pattition Algorithm)，該算法的理論上界為3Opt(R)；隨后又提出了一種改進的算法MFA(MinimumFetching Algotithm)，MFA能保證消除請求沖突的代價最小。 (2) 研究了有向環(huán)網(wǎng)上優(yōu)化波長數(shù)的問題，提出了一個為調度子集分配波長的近似算法PWAA(Page Wavelength Assignment Algorithm)。該算法通過環(huán)的切割技術為