辉煌彩票下载

版权所有 ? 《光通信技术》编辑部

地址:桂林市七星区六合路98号(541004) ? ? ? ?电话:0773-6346107

引用本文:

张敏,许渤,蔡怡,等:基于遗传算法的大规模WDM光网络RWA算法[J]. 光通信技术,2018,42(11):1-4.

基于遗传算法的大规模WDM光网络RWA算法

张 敏,许 渤*,蔡 怡,武保剑,邱 昆
(电子科技大学 信息与通信工程学院, 成都 611731)

摘要:尽管小规模波分复用(WDM)光网络的路由与波长分配问题(RWA)已经被广泛研究,然而对于具有超过100个节点的大规模WDM光网络来说,RWA问题的研究却鲜有报道,因此提出了一种基于遗传算法解决大规模动态WDM光网络中RWA问题的方法。与传统遗传算法相比,通过采用不同的染色体编码方式、不同的种群初始化方法和不同的适应度函数,实现了交叉和变异中RWA分配结果的优化。大量仿真实验结果表明,在不同规模的网格网络拓扑中,遗传算法较传统算法具有更低的网络阻塞率。
关键词:大规模波分复用光网络;路由与波长分配;遗传算法
中图分类号:TN365 文献标识码:A 文章编号:1002-5561(2018)11-0001-04
DOI:10.13921/j.cnki.issn1002-5561.2018.11.001

0 引言
       随着网络数据的快速增长,光网络必将变得越来越灵活,同时网络规模也会变得越来越大[1]。2015年,文献[2]提出了一种大规模的美国骨干网络的建设方案,该网络包含 273个节点和2411条链路。路由与波长分配(RWA)问题是波分复用(WDM)光网络中的关键问题之一,在小规模网络中该问题已经得到了广泛的研究并且具有丰富的研究成果。但是,对于大规模WDM光网络,相关研究还鲜有报道[3]。RWA问题的实质是对给定的一个连接源节点和目的节点的光路请求,即在光网络中找到一条合适的路由并为其分配一个合适的波长,从而建立一个光通道。RWA问题通常有两类方法,第一类是通过线性规划(LP)求解,第二类是通过启发式算法进行求解[4]。然而,RWA问题已经被证明是NP-Hard问题[5]。随着网络规模的扩大,LP方法计算复杂度急剧上升[4,5],因此该方法不适合大规模光网络RWA问题的求解。
       遗传算法(Genetic Algorithm,GA)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法[6,7]。针对静态网络中的Max-RWA问题[8],文献[6,7]采用了遗传算法进行求解,即在已知一定数量的连接请求和光纤支持的波长数目的情况下,求解光网络支持的最大连接请求数。在传统的遗传算法中,染色体的每一个基因是一条成功建立连接的光路,一条染色体则代表了光网络支持的所有连接请求。在动态光网络中,由于连接请求随机到达且持续时间不同,因此需要进行在线求解,显然传统的GA并不适用。因此,本文对传统GA进行了改进,包括采用不同的染色体编码方式、不同的种群初始化方法和不同的适应度函数等,用于求解大规模动态WDM光网络中的RWA问题。

4 结束语
       随着网络数据增加导致的光网络规模的增大,在大规模WDM光网络中实现高效的路由和波长分配计算成为了亟待解决的问题。本文针对大规模WDM光网络提出了一种基于GA的RWA算法,根据动态RWA问题的特点对传统GA中的染色体编码方式、种群初始化方法和适应度函数进行了修改和优化,保证了RWA信息的有效交叉和变异,实现了RWA求解结果的优化。通过在不同规模的网格网络拓扑中(包括10×10、15×15、20×20)进行的大量仿真实验,结果证明遗传算法相对于传统方案具有明显的性能优势,能够有效降低网络链接的阻塞率。