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

《使用可调adm全光网络任务调度问题的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中国科学技术大学硕士学位论文使用可调A删的全光网络任务调度问题研究摘要全光传输网络以其稳定性好和传输容量大等优点，正迅速成为带宽需求较大的下一代通信网络主要发展方向之一。基于波分复用(WavelengthDivisionMultiplexing—WDM)技术，可以在一根光纤中同时传输多个不同波长的光信号，从而可以在不需重新铺设物理网络的情况下，大大提高光纤的传输容量。本文研究了在为每个光节点配置一个可调加载，下载复用器(Add／DropMultiplexer．ADM)的WDM全光网络上的任务调度问题(StADM问题)，针对有向环网和对称树网这两种拓扑结构提出了几个新颖的算法。本文的主要工作

2、和贡献如下：(1)证明了全光有向环网上的S认DM问题是NP．Hard的。根据证明的归约过程，设计了一个近似算法GCA(GraphColoringAlgorithm)，分析了它的理论上界为l2．20pf(R)+1．9l，其tgOpt(R)是调度请求的最优解：接着进一步剖析了有向环网上的请求冲突关系，提出了一种按照请求的次序奇偶划分的贪心算法PPA(ParityPartitionAlgorithm)，该算法的理论上界为30pt(R)；随后又提出了一种改进的算法MFA(MinimumFetchingAlgorithm)，MFA能保证消除请求冲突的代价最小。(2)研究了有向环网上优化波长数的问题，

3、提出了一个为调度子集分配波长的近似算法PWAA(PageWavelengthAssignmentAlgorithm)。该算法通过环的切割技术为请求分配波长。(3)针对全光对称树网上的已有算法，提出了一个改进的调度算法DRTA(Depth．basedRTAlgorithm)，通过二分图的最大匹配，使调度的性能比原有算法提高了I1．2+1．6／opt(R)I。(4)搭建了模拟实验环境，通过模拟实验验证了本文算法的有效性。关键词：全光网络，可调ADM，边着色，波长分配，任务调度。中国科学技术大学硕士学位论文使用可调^晰的全光网络任务调度问题研究AbstractTheall-opticalcomm

4、unicationisbecomingoneofthemostpromisingtechniquesforthenextgenerationnetworksduetoitslli曲stabilityandhightransmissionbandwidth．Multipleopticalsignalsoverdifferentwavelengthscouldbetransmittedthroughasinglefiberthroughwavelengthdivisionmultiplexing(WDM)，whichcouldgreatlyincreasethebandwidthofall—o

5、pticalnetworks．Efficientschedulingalgorithmiscriticalforachievinghighpe而衄anceinall—opticalnetworkswithtunablewavelengthconverters，nlispaperstudiescommunicationrequestschedulingonWDMall·opticalnetworkswithonetunableadd／dropmultiplexer(tADM)pernode．Forrequestschedulingonunidirectionalringandsymmetri

6、ctreenetworks，weproposeseveralefficientalgorithms．Thefollowingsarethemajorcontributionsinthispaper．(1)WeprovethattheStADMonunidirectionaltingsisNP-Hard，andproposeoueapproximatealgorithmOCA(GraphColoringAlgorithm)，whichisinspiredbythereductionoftheproogandILlSI2．20pt(R)+1．9{pagesalmost,whereOpt(R)i

7、stheminimalpagesoftheoptimalscheduling．Thenbyorderingtherequestsintoodd-evensequences，weproposetheotheralgorithmPPA(ParityPartitionAlgorithm)，using30pt(R)pagesatmost．Basedonthis，wedesignanotherbeReralgorithmMFA(M