模拟退火算法解决静态RWA问题的研究

摘要

在WDM光网络中，业务量工程技术(TrafficEngineering，TE)是按用户的要求把业务量映射到光网络的物理拓扑上，从而达到优化网络资源利用率、避免拥塞和提高网络可靠性的目的。随着OXC(OpticalCrossConnect，光交叉连接设备)、OADM(OpticalAdd/DropMultiplexer，光分插复用设备)技术的不断成熟，基于DWDM(DenseWavelengthDivisionMultiplexing)技术的光传送网已不再局限于点对点传输，而是组网运用。既然是网络，就必然存在对网络资源的按需分配问题和优化问题。优化的目标是在实际的约束限制条件下，尽量合理配置资源，使得网络的总代价最小、资源占用率最少，以及在资源紧张时满足尽可能多的业务请求。为了更好地解决资源的按需分配问题和优化配置问题，必须在WDM光网络中引入业务量工程技术，更好地满足业务的要求。 在WDM光传送网中，给定一组光路连接需求，通过选路和波长分配算法来建立相应光路的问题称为路由与波长分配问题(RoutingandWavelengthAssignment，RWA)问题。WDM光网络中的一个核心问题就是如何选择有效的算法和协议来建立光路，也就是如何解决RWA问题。RWA问题的研究对网络资源的利用、网络管理和控制都有很大的影响。根据业务请求提出的方式不同，可以大致分为动态和静态RWA问题，本文主要对研究对象为静态RWA问题。目前在解决这种问题时，引入了多种算法，比如启发式算法，线性规划算法等等。 本文研究了用模拟退火算法解决光网络业务量工程中静态RWA问题，在已有网络上，根据多个业务需求，合理分配网络资源，完成端到端通路的建立，达到一定的优化目标。根据网络节点是否具有波长转换能力分为2种情况进行优化：1、所有节点都具有波长转换能力，2、所有节点都没有波长转换能力。为了衡量模拟退火算法解决静态RWA问题的结果，采用了一种启发性算法作为参考。首先考察实际的网络模型，根据业务需求，引入K路由算法的结果作为模拟退火算法和启发性算法备选路由集合，在链路带宽有限的约束下对网络资源进行分配，同时引入业务路由的通路保护问题的研究，实现了共享保护和专用保护两种通路保护方式；针对全波长转换网络和无波长转换能力网络，根据为所有连接请求所分配的总资源最少和满足请求的业务数目最多两种优化目标对资源分配进行优化，研究了备选路由集大小对模拟退火算法结果的影响；对模拟退火算法与启发性算法的性能在两个不同的网络中进行了比较。

目录

文摘

英文文摘

论文说明：简略字表

独创性声明和关于论文使用授权的说明

第一章绪论

1.1光波分复用技术的历史及发展

1.2网络节点设备及特点

1.3本文的主要贡献和内容安排

第二章静态RWA问题

2.1路由波长分配(RWA)问题

2.2静态RWA算法

2.3动态RWA算法

2.4波长变换对RWA算法的影响

第三章模拟退火算法解决静态RWA问题

3.1问题描述

3.1.1网络生存性问题

3.1.2共享风险链路组

3.1.3通路保护与链路保护

3.1.4专用保护与共享保护

3.1.5波长连续性限制

3.1.6数学描述

3.2模拟退火算法的背景和基本思想

3.3模拟退火算法在静态RWA问题中的应用

3.3.1算法在解决静态RWA问题时的目标和假设

3.3.2在全波长转换能力下的专用保护问题

3.3.3在全波长转换能力下的共享保护问题

3.3.4在无波长转换能力下的专用保护和共享保护

第四章算法程序设计

4.1程序结构及其主要流程

4.2程序的数据结构与算法

4.2.1类SA设计

4.2.2类Path设计

4.2.3类Graph设计

4.2.4类TR设计

第五章算法仿真结果及结论分析

5.1基本说明

5.2测试拓扑说明

5.3 K路由算法

5.4启发性算法解决静态RWA问题

5.4.1网络占用资源最少问题

5.4.2网络负载均衡问题

5.5备选路由集大小对算法的影响

5.5.1出现问题及分析

5.5.2改进方案及仿真结果

5.6共享保护在全波长转换能力网络中节省资源比较

5.6.1专用保护和共享保护的比较测试

5.6.2与启发式算法的比较

5.7无波长转换能力网络测试

第六章全文总结

参考文献

致谢

个人简历