路由算法中若干优化问题的研究

论文摘要

互联网已成为现代社会最重要的信息基础设施和人们工作、生活的重要组成部分.但目前互联网中的传输模式“尽力而为”服务,无法满足多媒体应用和各种用户对网络传输质量的要求.因此,以提高网络资源利用效率、为用户提供高质量服务作为目标的服务质量(quality of service,QoS)研究是当前Internet领域的热点之一.近几年的研究表明网络路由算法对实现网络保证质量的服务起到了非常关键的作用.本文主要研究服务质量单播与组播路由问题,取得的主要结果概括如下:1.第三章将禁忌搜索法引入多约束单播QoSR计算中,首先通过能量函数把多个QoS度量转化成单一能量.然后在Dijkstra算法基础上,构造出禁忌搜索法的候选集与评价函数.通过禁忌搜索法的迭代方法寻找出近似最优解.仿真实验表明本算法性能稳定,并具有成功率高、低代价等特点.2.第四章首先定义了带时延约束最小代价组播问题,然后给出了分别基于遗传禁忌混合策略、蚁群算法的组播路由算法.仿真实验结果表明算法稳定,具有收敛速度快、代价性能良好等特性.对组播路由问题提供了比较好的解决方法.3.第五章对带节点CPU,缓冲区与带宽约束的最小代价组播路由问题,首先提出了统一模型,然后给出了分别基于模拟退火法、遗传算法、禁忌搜索法的三种QoS组播路由算法.仿真实验表明本算收敛较快,具有能够满足多QoS要求、低代价等特点.4.第六章针对多约束最小代价Steiner树问题,提出了一种基于CBT思想的多约束组播算法(CMCMRA)与一种基于SPH思想的多约束组播算法(SMCMRA).性能分析表明这两种算法具有易于实现、复杂度比较低等特点.最后,仿真试验说明算法具有低代价性能,且能够满足多约束QoS要求.5.第七章对基于核心节点的组播路由协议中带QoS约束的核心节点选择问题,提出了一种核心节点选择算法.从核心节点候选集里选择最少量的核心节点,使得组成员都满足端到端服务质量约束.仿真结果表明提出的算法具有选出核心节点少、能够满足端到端QoS约束等性能,可行的且有效的.

论文目录

• 摘要
• Abstract
• 目录
• 1 绪论
• 1.1 研究背景
• 1.2 研究现状
• 1.3 本文的主要工作
• 2 路由算法与路由协议概述
• 2.1 引言
• 2.2 经典路由算法和协议
• 2.3 QoS基础
• 2.4 单播QoSR算法
• 2.5 组播QoSR算法
• 3 一种基于禁忌搜索的单播路由算法
• 3.1 引言
• 3.2 算法基础
• 3.3 基于禁忌搜索的路由算法
• 3.4 仿真实验
• 3.5 本章小结
• 4 带时延约束的组播路由算法
• 4.1 引言
• 4.2 组播路由问题的网络模型
• 4.3 基于遗传禁忌混合策略的时延约束组播路由算法
• 4.4 蚁群算法的组播路由算法
• 5 基于神经网络的组播路由算法
• 5.1 引言
• 5.2 基于神经网络组播路由算法的统一模型
• 5.3 基于模拟退火算法的组播路由算法
• 5.4 基于遗传算法的组播路由算法
• 5.5 基于禁忌搜索法的组播路由算法
• 5.6 算法性能分析
• 5.7 本章小结
• 6 两种带QoS约束的组播路由算法
• 6.1 引言
• 6.2 路由问题描述
• 6.3 两种带多QoS约束的组播路由算法
• 6.4 仿真试验
• 6.5 本章小结
• 7 带QoS约束的核心节点选择算法
• 7.1 引言
• 7.2 带QoS约束的核心节点选择算法
• 7.3 算法性能分析
• 7.4 本章小结
• 8 结论与后续工作
• 8.1 结论
• 8.2 后续工作
• 参考文献
• 攻读博士学位期间发表学术论文情况
• 创新点摘要
• 致谢