基于自适应逃逸粒子群算法的ASON多业务保护容量研究

论文摘要

ASON（Automatically Switched Optical Network自动交换光网络）赋予了传统光网络前所未有的灵活性和可扩展性，代表了下一代光网络的发展方向。对多种恢复机制的支持是ASON的一个重要特点，也是目前ASON研究的一个重点。在网络容量日益增长的今天，智能化动态恢复算法的研究对提高ASON的生存性具有重要意义，一个良好的恢复算法能够合理高效地提高网络空闲资源的利用率和受损业务的恢复率，从而有效减少因网络故障而造成的社会影响和经济损失。ASON比较公认的优势包括：快速提供业务，提供多种保护恢复机制，提供新的业务类型等等，其中提供多种保护恢复机制是目前运营商规划建设ASON网络时重点关注的问题。相对传统光传送网设计的一系列恢复机制，ASON对生存性的要求主要体现为全面考虑网络空闲资源的合理分配、能满足业务恢复的多样化、算法可扩展性等一系列问题。自适应逃逸粒子群算法（AEPSO，Self-Adaptive Escape Particle Swarm Optimization）是一种引入自适应调节参数和变异算子的改进的粒子群算（PSO，Particle Swarm Optimization），受到生物界中物种发现生存密度过大时会自动分家迁移的习性启发，该算法引入逃逸行为的这种简化的确定的变异操作，来增强全局和局部搜索能力，减弱了随机变异操作带来的不稳定性，避免了目前大多数随机迭代算法的“早熟收敛”和“收敛较慢”两大问题，提高算法解决组合优化问题的效率和性能。而ASON网络的保护容量问题本质上也是组合优化问题，因此作为尝试性的研究，本文基于自适应粒子群算法基本原理设计了一种适合于ASON的动态多业务保护容量算法。目标是在确保单点故障发生后对多受损业务的100％快速恢复下，如何确定每条光纤链路的波长信道保护容量，使得网络保护的造价达到或接近最低，更合理地利用网络空闲资源。论文分析了ASON中保护容量问题的相关技术体系，包括ASON的路由体系、动态路由和波长分配技术以及自适应逃逸粒子群算法的基本思想。提出并构建了基于自适应逃逸粒子群算法的动态多业务保护容量问题的算法模型，并设计了基于上述相关技术的仿真平台，基于仿真平台对算法进行了仿真测试和改进。主要成果如下：（1）分析和归纳了ASON网络的路由体系和相关动态路由和波长分配技术。包括路由模式、分布式波长分配、路由分发拓扑、不同实现方式（集中式或分布式）等与保护问题有关的功能模块，以及ASON中实现保护问题的相关影响因素及关键技术。（2）将ASON动态多业务保护容量问题以及约束条件抽象成数学模型，为将自适应逃逸粒子群算法运用到ASON动态多业务保护容量问题奠定了数学基础，该数学模型可以有效描述ASON动态多业务保护容量问题。同时基于该数学模型上对该问题进行相应数学分析。（3）研究了自适应逃逸粒子群算法的基本思想，创新性地将自适应逃逸粒子群算法应用到ASON动态多业务保护容量问题中。该算法在运行中能综合考虑网络资源状态和不同业务保护的优先等级，较之已有的基于线性规划和遗传算法的求解ASON网络保护容量问题，该算法能取得更好时间效率，适合于实时动态保护，具有较强的实用性。（4）编程实现了基于自适应逃逸粒子群算法的ASON多业务保护容量分配问题的算法，并模拟网络环境，与文献中提出的算法做了仿真测试比较。（5）仿真测试了自适应逃逸粒子群算法的实际运行性能，并根据测试结果确定算法参数组合，使算法在同等资源开销下取得了较好的效果。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.2 论文研究意义
• 1.3 论文的研究内容和关键技术
• 1.4 全文的组织安排
• 第二章 ASON中的生存性问题及保护相关技术分析
• 2.1 ASON中的路由体系结构
• 2.1.1 路由功能结构
• 2.1.2 路由方式
• 2.1.3 路由属性和路由消息分发拓扑
• 2.2 ASON中的生存性
• 2.2.1 ASON中的生存性特点
• 2.2.2 ASON保护/恢复比较和分析
• 2.2.3 ASON中的保护机制
• 2.2.4 ASON中的保护方案
• 2.3 ASON中的优化保护算法分析
• 2.3.1 ASON中的动态RWA技术
• 2.3.1.1 已有的动态业务路由选择策略及性能分析
• 2.3.1.2 已有的动态业务波长分配策略及性能分析
• 2.3.2 分层图模型及RWA结合算法
• 2.3.3 ASON中动态保护算法的影响因素分析
• 第三章 基于自适应逃逸粒子群算法的ASON多业务保护算法的研究
• 3.1 研究背景
• 3.2 内联的分层图模型
• 3.3 光网络矩阵模型
• 3.3.1 节点-链路结构矩阵模型
• 3.3.2 链路-波长矩阵模型
• 3.4 自适应逃逸粒子群算法（AEPSO）的基本思想和特点
• 3.5 基于AEPSO的保护算法的数学模型分析和算法描述
• 3.5.1 分层图中保护问题的算法数学模型分析
• 3.5.2 算法描述
• 3.5.2.1 编码设计
• 3.5.2.2 群体设定
• 3.5.2.3 适应值函数设计
• 3.5.2.4 选择
• 3.5.2.5 粒子速度更新
• 3.5.2.6 群体位置更新策略
• 3.5.2.7 算法终止条件
• 3.5.3 分布式实现的算法时间复杂度分析
• 3.5.4 算法全局收敛性能分析
• 第四章 算法仿真系统设计
• 4.1 概述
• 4.2 总体设计
• 4.2.1 算法仿真的流程图
• 4.2.2 实验网络拓扑
• 4.2.3 输入参数和输出信息
• 4.2.4 路由协议
• 4.3 详细设计
• 4.3.1 主通道和保护通道的确定策略（FindPathPop方法）
• 4.3.2 业务需求产生策略（ConnectionRequestPop方法）
• 4.3.3 初始群体随机化策略（initializePop方法）
• 4.3.4 适应度统计模块（fitnessPop方法）
• 4.3.5 选择策略（choicePop方法）
• 4.3.6 群体更新策略（updatePop方法）
• Road方法）'>4.3.7 具有波长转换器模块（WavelengthConversion_Road方法）
• Road方法）'>4.3.8 无波长转换器模块（No WavelengthConversion_Road方法）
• 4.3.9 总控程序（main函数）
• 第五章:仿真结果与分析
• 5.1 部分仿真结果输出
• 1,c₂的确定'>5.2 参数w,c₁,c₂的确定
• 5.3 群体规模和迭代次数对求解结果的影响及分析
• 5.4 遗传算法、整数线性规划和自适应逃逸粒子群算法的比较及分析
• 5.5 含波长转换器和不含波长转换器的比较与分析
• 第六章 结束语
• 6.1 结论
• 6.2 展望
• 致谢
• 参考文献
• 攻读硕士学位期间发表的论文