基于免疫遗传算法的QoS组播路由算法

论文摘要

随着网络技术的迅速发展,通信网络带宽和处理能力的提高使网络能够提供更多的多媒体业务,也使得支持“点对多点”或“多点多点”的组播通信方式成为网络支持多媒体业务的必要形式。多媒体通信和分布式环境下的协同工作等应用促使了组播通信的发展。组播问题的关键在于组播路由的确定,即寻找简单、高效、健壮的组播路由算法,组播路由算法主要是用来建立一棵性能良好的组播树,并使它能够满足各种业务的服务质量（Quality of Service,QoS）需求,由于QoS组播路由带有多个QoS约束参数,而这种多约束条件下的QoS组播路由问题属于NP完全问题。这使得它与传统的路由过程不同,难以用经典的最短路径优先算法（如Bellman-Ford和Dijkstra算法）求解。对于QoS组播路由问题的研究大多都集中在采用启发式算法和遗传算法求解无约束组播路由问题和延时受限组播路由优化问题,然而由于这些算法要么具有较高的时间复杂度而不能满足实际应用的需要,要么算法早熟收敛,陷入局部,不能求得全局最优解。针对遗传算法的缺陷,本文将生物免疫系统中的浓度调节机制引入遗传算法,形成一种改进的免疫遗传算法。以具有精英保留的免疫遗传算法ⅡGAE为基础,提出了一种新的用来求解带宽、延时、延时抖动受限,费用最小的QoS组播路由选择问题的方法。文中,首先采用预处理机制,将网络结构中不满足带宽约束的链路去掉,利用Dijkstra前N最短路径算法建立ⅡGAE算法编码空间的备选路径集;然后采用基于路径的树结构编码来随机产生初始群体,使种群中的每个个体都代表组播路由问题的一个候选解（即一棵组播树）。最后利用ⅡGAE算法对种群进行优化,最终求得满足QoS要求的组播路由。计算机仿真实验的结果证实了这种方法的有效性。此外,仿真实验中,通过与精英保留遗传算法、基于信息熵的精英保留免疫遗传算法进行比较,结果表明该算法具有较好的性能,以较快的速度搜索到满足QoS要求的费用最小的组播树。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 组播技术产生的背景
• 1.2 组播的特点
• 1.3 组播路由技术概述
• 1.4 组播路由选择协议
• 1.5 组播路由算法研究现状
• 1.5.1 静态和动态组播路由算法
• 1.5.2 分布式算法和集中式算法
• 1.5.3 Steiner树算法和CBT算法
• 1.5.4 分层组播路由算法
• 1.5.5 QoS组播路由算法
• 1.6 本文主要研究内容和组织结构
• 第二章 QoS组播路由问题
• 2.1 QoS路由的度量选择
• 2.1.1 常用网络性能度量
• 2.1.2 路由的度量选择原则
• 2.1.3 QoS路由的度量选择思想
• 2.2 QoS组播路由
• 2.2.1 组播原理
• 2.2.2 QoS组播原理
• 2.2.3 QoS组播路由的数学模型
• 2.2.4 QoS多约束 QoS组播路由是NP完全问题
• 2.3 QoS组播路由算法的研究现状
• 2.3.1 QoS约束Steiner树问题及其启发式算法
• 2.3.2 启发式算法分析
• 2.3.3 QoS组播路由问题相关遗传算法
• 2.4 本章小节
• 第三章 基于遗传算法的QoS的组播路由算法
• 3.1 随机网络拓扑图的生成算法
• 3.2 遗传算法概述
• 3.2.1 遗传算法简介
• 3.2.2 遗传算法的特点
• 3.3 基于遗传算法的QoS组播路由选择
• 3.3.1 编码与产生初始群体
• 3.3.2 遗传路由算法的算子设计方法
• 3.3.3 遗传路由算法的实现过程
• 3.4 基于遗传算法的延时受限的组播路由算法
• 3.4.1 求解备选路径集
• 3.4.2 编码与产生初始群体
• 3.4.3 适应度函数的建立
• 3.4.4 选择方法
• 3.4.5 交叉操作和变异操作
• 3.4.6 仿真实验
• 3.5 遗传算法求解组播路由的研究现状及发展趋势
• 3.5.1 遗传算法求解 QoS组播路由问题的难点
• 3.5.2 遗传算法的改进技术
• 3.6 基于模拟退火遗传算法的延时受限的组播路由算法
• 3.6.1 模拟退火遗传算法主要思想
• 3.6.2 利用 SAGA求解延时受限的组播路由的流程
• 3.6.3 仿真实验结果和分析
• 3.7 本章小节
• 第四章 免疫遗传算法
• 4.1 自然免疫学基本原理
• 4.1.1 生物免疫机制简介
• 4.1.2 抗体与抗原
• 4.1.3 获得性免疫应答
• 4.1.4 生物免疫机制的抽取
• 4.2 已经提出的免疫遗传算法
• 4.2.1 免疫遗传算法基本原理
• 4.2.2 基于信息嫡的免疫遗传算法
• 4.2.3 基于欧式距离的免疫遗传算法
• 4.3 一种改进的免疫遗传算法
• 4.3.1 改进的免疫遗传算法中的几个重要定义
• 4.3.2 精英保留策略
• 4.3.3 改进的免疫遗传算法
• 4.4 本章小节
• 第五章 基于免疫遗传算法的QoS组播路由算法
• 5.1 免疫遗传算法的基本步骤设计
• 5.2 基于免疫遗传算法的多约束 QoS组播路由选择算法
• 5.2.1 QoS组播路由问题的描述
• 5.2.2 网络结构预处理
• 5.2.3 求解备选路径集及编码
• 5.2.4 群体初始化
• 5.2.5 适应度函数的建立
• 5.2.6 遗传算子
• 5.2.7 QoS组播路由选择算法流程
• 5.2.8 算法计算复杂度分析
• 5.3 仿真实验研究
• 5.3.1 实验结果
• 5.3.2 HGAE与其他算法性能的比较
• 5.4 本章小结
• 第六章 总结与展望
• 6.1 总结
• 6.2 展望
• 参考文献
• 致谢
• 攻读硕士学位期间发表的学术论文