论文部分内容阅读
随着人们对高速高质量数据传输,以及高容量、大带宽需求的日益增加,每个超级通道以每秒太比特的速率传输成为发展趋势,因此,基于波分复用(WDM)的光网络成为研究热点。在基于波分复用光网络中,终端用户通过全光WDM信道进行通信,这样需要建立有效的连接。在光网络中,每条光路的路由选择和波长分配受到约束条件的影响,在波长冲突约束的情况下,两个光通道不能共享一个物理链路,且在一个链路上使用相同的波长。同时,在波长连续性约束的情况下,相同的波长必须分配到整个光路的所有链接。因此,为了实现光纤连接的最大化,有必要对静态路由和波长分配方法进行研究。本文,在给定的连接矩阵下,我们对不需要波长转换器的WDM网络中的静态最大路由和波长分配问题进行研究,开展的主要创新工作如下: 建立了一种新的最大化路由和波长分配的数学模型,分析其制约因素。 实现了四种高效的随机搜索算法,即:随机优化算法(ROA),遗传算法(GA),Tabu搜索算法(TSA)和进化规划(EP)算法来解决最大化路由和波长分配。 提出了一种新的高效的回溯算法,处理最大化路由和波长分配的路由子问题。由于采用回溯算法,初始搜索空间包含所有可能的候选光路,因此,每个连接请求都有机会得到处理。 对随机优化算法,遗传算法,Tabu搜索算法和进化规划算法进行实验研究,分析比较了四种算法在光纤连接数目方面的性能和运行时问。 通过对最大化路由和波长分配进行建模,实验研究随机优化算法,遗传算法,Tabu搜索算法的性能,我们不仅说明了实行启发式算法的优越性,而且显示了每种算法达到最优性能的条件。实验结果表明,当所有的需求总数分别为5,20或100时,相比GA算法,TSA算法性能提高可以达到23%,同时,相比ROA算法,TSA算法性能提高达到10%。当所有的需求总数为1000时,相比TSA算法,GA算法性能提高6%,相比ROA算法,GA算法性能提高7%。然而,TSA算法花费的平均时问是GA算法的5倍,是ROA算法的29倍。另外,我们对随机优化算法,遗传算法,Tabu搜索算法和进化规划算法进行了比较和实验研究,实验结果表明,TSA算法的性能比GA算法提高了11%,比ROA算法提高了5%,比EP算法提高仅为1%。而且,TSA算法花费的平均时问是EP算法的10倍,是ROA算法的2倍,是GA算法的3倍。通过对四种算法进行实验研究和比较分析,TSA算法的性能最好,可是,在最大化路由和波长分配时,该算法需要的运行时间长。