使用可调ADM的全光网络任务调度问题研究

摘要

全光传输网络以其稳定性好和传输容量大等优点，正迅速成为带宽需求较大的下一代通信网络主要发展方向之一。基于波分复用(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) 搭建了模拟实验环境，通过模拟实验验证了本文算法的有效性。

目录

文摘

英文文摘

论文说明：图表索引

中国科学技术大学学位学位论文相关声明

第一章绪论

1.1研究背景和发展现状

1.1.1全光网的发展沿革

1.1.2研究背景

1.1.3发展现状

1.2本文的研究内容和组织方式

1.2.1本文的研究内容

1.2.2本文的组织方式

第二章StADM的问题模型及相关工作

2.1波长可调的光网络模型的研究现状

2.1.1 TTFR模型

2.1.2 FTTR模型

2.1.3 TTTR模型

2.2使用可调ADM的全光网络结构

2.3 StADM问题的数学模型

2.3.1请求间的冲突关系

2.3.2简化模型

2.3.3优化波长数

2.4 StADM的相关工作

2.4.1对称树网上的StADM问题研究

2.4.2单向线网上的StADM问题研究

2.5本章小结

第三章全光有向环网上的StADM问题

3.1问题模型

3.1.1冲突关系

3.1.2问题复杂度

3.2近似算法

3.2.1 GCA算法

3.2.2 PPA算法

3.2.3 MFA算法

3.3优化波长数

3.4算法性能实验

3.4本章小结

第四章全光对称树网上的StADM问题

4.1问题模型

4.2近似算法

4.2.1 LPA算法

4.2.2 DRTA算法

4.3优化波长数

4.4算法性能实验

4.5本章小结

第五章总结

5.1本文的研究成果和贡献

5.2进一步的工作

参考文献

致谢

攻读硕士学位期间发表的学术论文