遗传算法在多播格状网络流量疏导中的应用

摘要

随着光子通讯技术的进步,光网络的发展,网络中的信息流量随着信息用户的增长显指数增长.多播(Multicast)将成为网络中信息传播的一种重要形式,这些信息为大大小小的群体用户所用,并为现代生活提供了各种方便.格状网络(Mesh networks)是当今通信网络发展中的一种非常重要的形式.因为信息爆炸,如果没有适当的调整,就会造成了网络资源不能得到充分有效的利用并使网络运行成本的攀升.因此对网络中的信息流量进行疏导已成为建设高速高容量的光通信网络的关键环节.随着通信事业的发展,格状网上的流量疏导正已引起了国内外专家的关注.基于此,我们着手对格状网络中的多播信息流量疏导的这一难题进行了较为系统的研究.格状网络中的信息流量疏导(Traffic Grooming)的研究主要是对网络中的路由及波长分配(Routing and Wavelength Assignment,RWA)问题(不同信息之间的复用问题)进行优化.而格状网络中的RWA是个NP-难问题,它不可能在有限的时间内通过穷举搜索来获得其优化解,为此我们设计了一个启发性算法以解决这个问题.而启发性算法应用于大型网络时存在诸多的不足之处,为此我们通过研究对比各种智能算法和已有的有关流量疏导的文献,指出遗传算法是一种解决NP-难问题的利器.于是我们设计了一个独特的遗传算法来解决格状网中的流量疏导问题.通过对格状网络中的多播信息传播方式进行详细的研究,我们利用所设计的遗传算法来寻求网络中最佳的波长分配方案和流量疏导方案.通过对格状网中多播信息的静态任意形式流量的疏导表明,用遗传算法进行疏导之后得到了较为满意的结果.这个结果对WDM多播光网络的优化设计具有重要的参考价值.

目录

文摘

英文文摘

第一章绪论

第一节网络中信息流量疏导的概念

第二节本文的结构

第二章通信网络的结构

第一节信息传播方式

第二节节点结构

第三节网络的拓扑结构

第四节路由与波长分配

a) 重路由到源(Reroute-to-Source)

b) 重路由到任何节点(Reroute-to-Any)

c) 成员第一(Member-First)

d) 成员即可(Member-Only)

e) 从虚拟源扇出(Spawn-from-Virtual Source)

f) 能力优先(Capacity-Based-Priority)

g) 基于虚拟源的多播方法(Virtual Source Based Multicast Approach)

第五节本章小结

第三章遗传算法

第一节生物的进化

1、繁殖

2、变异

3、竞争

4、 进择

第二节遗传算法

第三节遗传算法在多播流量疏导中的应用

1.编码

2.交叉

3.变异

4.适应度计算

5. 选择

第四节算法的改进

第五节本章小结

第四章流量疏导

第一节网络中流量的疏导

第二节格状网的流量疏导的方式

第三节 格状网中流量疏导的一种启发性算法

一、网络结构及其路由和波长分配方法

二、静态的流量疏导及其算法实现

第四节疏导结果

第五节本章小结

第五章GA在多播格状网络流量疏导中的应用

第一节网络的构建

第二节路由及波长分配

第三节遗传算法对多播网的波长分配

一、 信息光树的编码

二、群体个体的产生

三、遗传和变异

四、适应度的计算及个体的选择

第四节计算机模拟结果及其结论

第五节本章小结

第六章本文小结及今后的研究工作

一、本文的工作

二、今后的研究工作

参考文献

致谢