基于QoS的选播路由算法研究

论文摘要

选播是一种新型的网络服务模型,它能够使用户通过一个选播地址访问到该地址所标示的一组服务器中对用户来说“最近的”一个。选播服务的应用能够增强网络服务的可用性、提高网络的服务质量。QoS（Quality-of-Service）路由被认为是保证网络服务质量的一个不可缺少的路由技术,其目标是寻找满足约束条件的路径同时有效利用网络资源。选播一经提出,它的QoS保证即引起了研究者的兴趣。本文首先介绍了课题的研究背景及意义,详细介绍了选播通信服务的研究现状,然后阐述了选播通信服务、QoS路由及遗传算法的相关理论基础知识。在分析国内外现有QoS选播路由算法的基础上,针对时延约束代价最小的QoS选播路由问题,改进了基于遗传算法有时延约束的QoS选播路由算法,算法中采用加权深度优先搜索和轮盘赌相结合的方法来保证初始种群的多样性;算法中设计了一种新的适应度函数,函数的设计充分考虑了时延和代价的关系,满足时延约束且时延和代价最小的个体适应度值大,反之适应度值则较小;算法中采用了指导变异的方法,通过指导变异操作加速算法的收敛速度。为了均衡网络资源的利用、减少网络拥塞的发生,改进了基于随机方法负载均衡的QoS选播路由算法,算法中利用网路均衡度和服务器负载这两种度量作为路由选择的依据,即通过对网路均衡度和服务器负载进行线性加权,进而把这两种度量转化为一种度量作为选择目的节点的依据,然后通过随机策略实现路由选择和网路资源的均衡利用。最后,对算法进行了仿真实验。实验结果表明:第一种算法在较小的进化代数内能够收敛到全局最优解或次优解;第二种算法所求得路径的时延与Anycat-Routing算法相差不多,但它能够较好地平衡网络资源的利用,减少网络拥塞的发生并具有较高的请求接受率。因此,两种算法都是有效的和可行的。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景及意义
• 1.2 国内外研究现状
• 1.3 本文的研究内容
• 1.4 本文的组织结构
• 第二章 QoS选播路由的理论基础
• 2.1 选播通信服务
• 2.1.1 选播服务的概念
• 2.1.2 选播通信服务的应用
• 2.1.3 选播服务应用中的困难
• 2.2 QoS路由
• 2.2.1 QoS路由概述
• 2.2.2 QoS路由的网络模型和度量
• 2.2.3 QoS路由算法的分类
• 2.3 遗传算法的基础理论
• 2.3.1 遗传算法的基本概念
• 2.3.2 遗传算法的基本流程
• 2.3.3 遗传算法的优点和不足
• 第三章 基于遗传算法的QoS选播路由算法
• 3.1 引言
• 3.2 有时延约束的QoS选播路由问题描述
• 3.3 基于遗传算法有时延约束的QoS选播路由算法
• 3.3.1 算法描述
• 3.3.2 算法性能分析
• 3.4 仿真实验与结果分析
• 3.4.1 仿真实验设计
• 3.4.2 实验结果分析
• 3.5 小结
• 第四章 基于随机方法负载均衡的QoS选播路由算法
• 4.1 引言
• 4.2 研究模型及问题
• 4.3 负载均衡的QoS选播路由算法
• 4.3.1 算法描述
• 4.3.2 算法性能分析
• 4.4 仿真实验与结果分析
• 4.4.1 仿真实验设计
• 4.4.2 实验结果分析
• 4.5 小结
• 总结
• 参考文献
• 攻读硕士学位期间取得的学术成果
• 致谢