论文部分内容阅读
全光传输网络以其稳定性好和传输容量大等优点，正迅速成为带宽需求较大的下一代通信网络主要发展方向之一。基于波分复用(Wavelength DivisionMultiplexing-WDM)技术，可以在一根光纤中同时传输多个不同波长的光信号，从而可以在不需重新铺设物理网络的情况下，大大提高光纤的传输容量。
本文研究了在为每个光节点配置一个可调加载/下载复用器(Add/DropMultiplexer-ADM)的WDM全光网络上的任务调度问题(StADM问题)，针对有向环网和对称树网这两种拓扑结构提出了几个新颖的算法。本文的主要工作和贡献如下：
(1) 证明了全光有向环网上的StADM问题是NP-Hard的。根据证明的归约过程，设计了一个近似算法GCA(Graph Coloring Algorithm)，分析了它的理论上界为「 2．2Opt(R)+1．9 」，其中Opt(R)是调度请求的最优解：接着进一步剖析了有向环网上的请求冲突关系，提出了一种按照请求的次序奇偶划分的贪心算法PPA(Parity Pattition Algorithm)，该算法的理论上界为3Opt(R)；随后又提出了一种改进的算法MFA(MinimumFetching Algotithm)，MFA能保证消除请求冲突的代价最小。
(2) 研究了有向环网上优化波长数的问题，提出了一个为调度子集分配波长的近似算法PWAA(Page Wavelength Assignment Algorithm)。该算法通过环的切割技术为请求分配波长。
(3) 针对全光对称树网上的已有算法，提出了一个改进的调度算法DRTA(Depth-based RT Algorithm)，通过二分图的最大匹配，使调度的性能比原有算法提高了「1．2+1．6/Opt(R)」。
(4) 搭建了模拟实验环境，通过模拟实验验证了本文算法的有效性。