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

论文摘要

随着Internet和宽带网络技术的日益发展,传统的以文字和图片为主的服务已不能满足用户的需要,具有视频和音频的多媒体服务成为主流。近几年嵌入式网络数字视频监控系统正在得到广泛应用。由于嵌入式网络数字视频监控系统传输的数据量大而系统资源有限,采用点对点的传输方式会增加服务器的负担,造成网络拥塞。而组播技术可以将相同的数据从嵌入式网络视频服务器同时并行地发送到接收者,大大节省了网络带宽,减少了数据冗余,即使用户数量成倍增加,主干网络带宽也不会随之增加。同时视频监控系统对信息传送的时延和时延抖动有严格的要求,要求传输的数据必须在一定的时延限制内到达所有的接收者,并且接收者之间的延迟差别也需在一定的范围内,即满足一定服务质量(QoS)的要求。因此在嵌入式网络数字视频监控系统中我们需要解决Qos组播路由问题。该问题的目标是寻找一棵满足QoS要求的组播树,使该树覆盖所有的组成员,同时使网络费用达到最小。遗传算法是近几年提出的一种模拟生物界自然选择和遗传机制,具有高度并行,群体寻优的新型最优化搜索算法,近年来已有一些学者采用遗传算法来求解QoS组播路由问题。本文在分析现有遗传算法的基础上,提出了两种改进的遗传算法。第一个改进算法针对遗传算法运行初期易陷入早熟,运行后期收敛缓慢的问题进行了改进,采用初始群体均衡生成法和自适应变异操作可以很好地抑制早熟现象,引入排序对适应度进行拉伸,从而加快了算法的收敛速度。仿真实验结果表明改进后的遗传算法收敛速度快,性能好,可以满足系统资源有限和实时性的要求。第二种改进算法是在分析了遗传算法和蚁群算法各自优缺点的基础上,将两种算法进行融合来求解QoS组播路由问题,算法的前一阶段利用遗传算法的快速性、随机性、全局收敛性产生后一阶段蚁群算法所需要的初始信息素,加快了蚁群算法利用正反馈特性进行搜索的速度。经融合后的算法,在时间效率上优于蚁群算法,在求解效率上优于遗传算法,形成了一种时间效率和求解效率都比较好的启发式算法。本文最后针对现有视频监控系统单播传输存在的问题,将组播技术应用到网络视频监控系统中,可以有效地节省网络资源,降低时延,减少网络堵塞的几率,较好地保证了数字视频传输的实时性和服务质量。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 论文的选题背景
• 1.2 国内外研究现状
• 1.3 论文的主要工作
• 第二章 QoS组播路由问题
• 2.1 QoS概述
• 2.1.1 QoS主要参数
• 2.1.2 QoS度量
• 2.2 组播概述
• 2.2.1 组播的工作原理
• 2.2.2 组播实现方式
• 2.2.3 组播应用
• 2.3 组播路由算法
• 2.3.1 组播路由算法分类
• 2.3.2 组播路由算法简介
• 2.4 QoS组播路由问题
• 2.5 本章小结
• 第三章 一种改进遗传算法求解QoS组播路由问题
• 3.1 遗传算法
• 3.1.1 遗传算法的基本思想
• 3.1.2 遗传算法的设计基本步骤
• 3.1.3 遗传算法流程
• 3.1.4 遗传算法的特点
• 3.1.5 遗传算法的应用
• 3.2 Qos组播路由的数学模型
• 3.3 改进的遗传算法
• 3.3.1 引言
• 3.3.2 算法描述
• 3.4 实验结果与分析
• 3.4.1 算法收敛性分析
• 3.4.2 随机网络产生模型
• 3.4.3 实验结果比较
• 3.5 本章小结
• 第四章 遗传蚁群融合算法在Qos组播路由中的应用
• 4.1 蚁群算法
• 4.1.1 蚁群算法的基本原理
• 4.1.2 蚁群算法数学描述
• 4.1.3 蚁群算法的特点
• 4.1.4 蚁群算法的应用
• 4.2 遗传算法与蚁群算法融合的基本思想
• 4.3 遗传算法在本算法中的应用设计
• 4.3.1 群体初始化
• 4.3.2 适应度函数
• 4.3.3 选择操作
• 4.3.4 交叉变异
• 4.4 蚁群算法在本算法中的应用设计
• 4.4.1 下一节点的选择
• 4.4.2 信息素强度的调整
• 4.5 实验结果分析
• 4.6 本章小结
• 第五章 组播技术在网络视频监控系统的应用研究
• 5.1 视频监控系统的发展
• 5.2 网络视频监控系统总体设计
• 5.2.1 硬件系统架构
• 5.2.2 服务器软件体系结构
• 5.3 系统主要功能模块设计
• 5.3.1 视频采集及图像压缩模块
• 5.3.2 嵌入式web服务器模块
• 5.3.3 网络传输模块
• 5.4 本章小结
• 第六章 总结与展望
• 6.1 全文总结
• 6.2 课题展望
• 参考文献
• 致谢
• 攻读硕士学位期间发表的学术论文目录
• 学位论文评阅及答辩情况表