遗传算法在QoS组播路由优化中的应用研究

摘要

随着Internet的发展,多媒体通信和分布式环境下的协同工作等应用促使了组播通信的发展.组播问题的关键在于组播路由的确定,即寻找简单、高效、健壮的组播路由算法,组播路由算法主要是用来建立一棵性能良好的组播树,并使它能够满足各种业务的服务质量(Quality of Service,QoS)需求,由于QoS组播路由带有多个QoS约束参数,而这种多约束条件下的QoS组播路由问题属于NP完全问题.这使得它与传统的路由过程不同,难以用经典的最短路径优先算法(如Bellman-Ford和Dijkstra算法)求解.对于QoS组播路由问题的研究大多都集中在采用启发式算法求解无约束组播路由问题和时延受限组播路由优化问题,然而由于这些算法都具有较高的时间复杂度而不能满足实际应用的需要.本文利用遗传算法作为求解QoS组播路由优化的算法,主要研究了四类典型的QoS组播路由问题.首先,根据组播路由问题的特点,建立了候选路由表,采用了等长节点序列串的编码方式,针对标准遗传算法的缺点,引入模拟退火思想,该算法既提高了算法的全局收敛能力也提高了收敛速度.其次,针对目前的单约束(或无约束)组播路由问题的局限性,用遗传算法实现了一种通用的多约束QoS组播路由问题,采用基于路径的树结构编码方式,遗传算子操作过程简单,算法体现了遗传算法较强的搜索能力.再次,通过分析遗传算法和组播路由问题的特点,提出一种双种群遗传算法,通过嫁接种群来指导种群的进化方向,大大提高了算法的收敛速度.最后提出一种双染色体遗传算法来求解时延——带宽约束组播路由问题,同时在产生初始群体时,引入了求解组播路由问题的经典启发式算法思想,设计遗传算子时,采用了双变异率算子,而交叉算子是在两种染色体之间进行的,通过仿真结果验证了该算法的有效性.

目录

文摘

英文文摘

本人声明

1.绪论

1.1引言

1.2网络路由选择问题

1.2.1路由技术

1.2.2基本分类

1.3 QoS组播路由选择方法

1.3.1组播通信概述

1.3.2服务质量要求

1.3.3 QoS组播路由

1.4组播路由选择算法

1.4.1组播路由算法分类

1.4.2组播路由算法

1.5本文的主要研究内容

2.遗传算法求解QoS组播路由问题

2.1仿真网络模型

2.2遗传算法概述

2.2.1遗传算法求解组播路由问题的研究背景

2.2.2遗传算法介绍

2.3基于遗传算法的QoS组播路由选择

2.3.1网络拓扑图的数据结构及初始群体的构建

2.3.2遗传路由算法的编码方法

2.3.3遗传路由算法的算子设计方法

2.3.4遗传路由算法的实现过程

2.4遗传算法求解组播路由的研究现状及发展趋势

2.4.1遗传算法求解QoS组播路由问题的难点

2.4.2国内外研究历史及现状

2.4.3发展趋势

3.基于模拟退火遗传算法的时延受限组播路由优化

3.1模拟退火遗传算法的实现步骤

3.2时延受限组播路由问题的数学模型

3.3相关算法介绍

3.4创建初始群体并对其编码

3.5模拟退火遗传路由算法描述

3.5.1目标函数

3.5.2遗传算子的设计

3.5.3停止准则

3.6仿真结果

3.7总结

4.基于遗传算法的多约束QoS组播路由优化

4.1引言

4.2多约束QoS组播路由的网络模型

4.3初始群体的构建和编码

4.3.1组播路由问题的编码

4.3.2群体的初始化

4.4遗传算法的实现

4.4.1适应度函数

4.4.2遗传算子设计

4.4.3算法停止准则

4.5实验研究及仿真结果

4.6结论

5.用嫁接遗传算法求解QoS组播路由选择问题

5.1引言

5.2基于双种群协同竞争的嫁接遗传算法

5.3组播路由模型的构建

5.4嫁接遗传算法的实现过程

5.4.1进化种群和嫁接种群的创建和编码

5.4.2适应度函数的构造

5.4.3遗传算子的实现

5.4.4算法实现流程图

5.5仿真结果及其分析

5.6结论

6.一种改进遗传算法求解时延-带宽约束组播路由

6.1引言

6.2组播路由的数学模型

6.3双染色体的构造和编码

6.4算法实现

6.4.1适应度函数

6.4.2算法流程图

6.43交叉算子

6.4.4双变异率算子

6.5算法详细实现过程图例

6.6实验结果分析

6.7小结

结论

参考文献

攻读硕士期间发表的论文

致谢