基于遗传算法的QoS组播路由算法优化研究

论文摘要

视频广播、IPTV等应用的出现,使得传统的Internet所提供的“尽力而为”的服务已经无法满足新应用在QoS方面的要求,因此,近年来业界广泛地将研究的关注点放在了组播应用环境下如何确保用户的服务质量（QoS）这个难题上。QoS组播路由算法已经被证明是一个NPC问题,从而使得其成为组播进一步应用的症结。基于启发式算法的路由方法随着网络节点以及链路数量的增加,计算时间代价会急剧增加而且在处理多约束的条件下显得无能为力。遗传算法的诸多特点为QoS组播路由计算带来了新的动力,然而由于“早熟收敛”现象以及适应度函数设定等方面的原因造成收敛到最优解概率较低以及速度较慢的问题。针对上述传统遗传算法的不足,本文的主要研究工作如下:1.预防“早熟收敛”现象改进算法,主要是针对造成“早熟收敛”现象的“超级个体”和固定交叉、变异概率两方面原因进行改进,选择机制优化在出现“超级个体”时通过对种群进行对数化处理来提高低适应度个体被选择的几率,从而预防“超级个体”对种群进化的消极影响。自适应交叉、变异操作改进则通过侦测种群进化的情况来动态调整交叉、变异概率,从而在机制上预防了种群过早收敛。此改进算法提高了整体进化收敛到最优组播路由的概率。2.适应度函数改进方面,原适应度函数公式f（P）=（Afb+Bfd+Cfdj+Dfpl）/Efc虽明确了适应度值与四大QoS约束参数以及网络代价之间的关系,但并不能保证满足QoS约束是搜索最优组播路由的前提。改进后的适应度函数表达式f（P）=（Afb*Bfd*Cfdj*Dfpl）-Efc,不但明确了满足QoS约束是前提的地位,避免了产生不合理解的情况,更是提高了选择压,从而加快了种群进化的速度。3.初始群体生成预处理方面,通过对传统遗传算法的分析,初始群体中是否包含有符合QoS约束的组播路径个体直接影响到最优路径算法的收敛性。预处理改进算法就能够通过对初始群体进行侦测,若包含有有效路径则进入选择、交叉和变异操作,反之,则需重新进行初始群体生成操作。此改进能够有效降低收敛到最优解所需的平均代数。4.在上述三方面改进的基础上,本文提出了一种新的基于优化遗传算法的QoS组播路由算法,并从遗传算法设计基本步骤、编码表示、适应度函数设定、初始群体生成、选择算子设计、交叉算子设计、变异算子设计、遗传参数自适应优化以及终止条件设计等九个环节详细阐述了算法的实现方法。本文提出的优化算法均经过仿真验证。本文通过在预防“早熟收敛”现象改进算法、适应度函数改进以及初始群体生成预处理三方面的改进切实地提高了进化过程的动态性,促使算法能够收敛到质量更高的解,提升了算法的性能。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 概述
• 1.2 组播的特点
• 1.3 组播技术的应用
• 1.4 组播路由算法研究现状
• 1.5 本文的主要研究内容
• 1.6 本章小结
• 第二章 QoS 组播路由技术原理
• 2.1 组播路由技术概述
• 2.1.1 IGMP
• 2.1.2 组播路由选择方式
• 2.1.3 组播路由算法协议
• 2.2 QOS 路由概述
• 2.2.1 QOS 的定义
• 2.2.2 QOS 路由的定义
• 2.2.3 IP QOS 的基本结构
• 2.3 QOS 组播路由的数学模型
• 2.4 本章小结
• 第三章 遗传算法原理
• 3.1 遗传算法概述
• 3.1.1 遗传算法的发展历史
• 3.1.2 遗传算法的基本思想
• 3.1.3 遗传算法的特点
• 3.2 遗传算法的基本流程
• 3.3 遗传算法基本操作
• 3.4 遗传算法的收敛性分析
• 3.4.1 收敛的定义
• 3.4.2 遗传算法的Markov 链分析
• 3.5 遗传算法的种类
• 3.6 本章小结
• 第四章 “早熟”现象的优化算法研究
• 4.1 传统遗传算法中的“早熟”现象的概念
• 4.2 传统遗传算法“早熟”现象的产生原因
• 4.3 “早熟”现象的数学分析
• 4.3.1 相关定义
• 4.3.2 选择算子分析
• 4.3.3 交叉算子分析
• 4.3.4 变异阶段
• 4.4 预防传统遗传算法早熟收敛的策略
• 4.5 预防早熟收敛策略的算法
• 4.5.1 交叉、变异概率动态选择
• 4.5.2 选择机制优化算法
• 4.6 预防早熟收敛的算法仿真验证
• 4.6.1 仿真试验环境简介
• 4.6.2 降低“早熟”现象对整个算法的影响试验
• 4.7 本章小结
• 第五章 提高收敛速度的关键环节优化研究
• 5.1 适应度函数的优化设定
• 5.1.1 QoS 组播路由适应度函数的一般定义
• 5.1.2 本文提出的适应度函数
• 5.1.3 改进后的适应度函数公式如何设定各加权系数
• 5.1.4 仿真试验
• 5.1.5 结论
• 5.2 初始群体生成预处理
• 5.2.1 预处理算法描述
• 5.2.2 初始群体生成预处理仿真验证
• 5.3 本章小结
• 第六章 基于优化遗传算法的QoS 组播路由算法
• 6.1 遗传算法设计的基本步骤
• 6.2 编码表示
• 6.2.1 组播树编码的特征要求
• 6.2.2 常用的组播树编码方式
• 6.2.3 各种组播树编码的特点
• 6.3 适应度函数
• 6.3.1 本文中适应度函数的数学表示
• 6.3.2 适应度函数计算算法
• 6.3.3 算法在种群计算中的关键点
• 6.4 初始群体生成
• 6.4.1 现有的组播数生成方法
• 6.4.2 构成初始群体的组播树生成算法
• 6.4.3 初始群体生成算法
• 6.5 选择算子的设计
• 6.5.1 标准轮盘赌选择策略算法
• 6.5.2 选择机制优化
• 6.5.3 最优个体保持策略
• 6.6 交叉算子的设计
• 6.7 变异算子的设计
• 6.8 算法中遗传参数的自适应选择
• 6.9 算法终止条件
• 6.10 算法的具体描述
• 6.11 本章小结
• 第七章 试验与仿真
• 7.1 随机网络产生模型简介
• 7.2 本文仿真试验简介
• 7.3 仿真试验研究与结果分析
• 7.3.1 仿真试验环境简介
• 7.3.2 仿真测试结果分析
• 7.4 本章小结
• 结束语
• 参考文献
• 致谢
• 攻读硕士学位期间录用的论文