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

摘要

选播(Anycast)是IPv6中的一种标准通信模型，可以实现一台主机与一组具有相同选播地址的目的主机中“最近”的一台主机进行通信(这组目的主机提供相同的服务)。选播服务的主要功能是允许用户根据需要做出合适的选择，因此路由问题是选播技术的关键问题，它直接决定了网络服务的可用性和效率的高低。 具有时延约束和代价要求的选播路由问题是一个NP完全问题，遗传算法通常用于解决此类问题。“早熟”收敛是遗传算法在实际应用中常见的一个疑难问题，主要表现为种群中最优个体的适应度值得不到提高，种群在经过若干迭代后仍找不到最优解，而造成“早熟”的主要原因是群体多样性的过早缺失。 本文在深入分析和研究选播服务模型和选播路由算法的基础上，针对上述问题，给出了一种基于改进的遗传算法的选播QoS路由算法。该算法可以解决具有时延约束的条件下要求代价最小的选播路由问题。 本算法把遗传算法应用于选播QoS路由问题中，发挥其并行性和群体寻优的特点；引入相异度的思想改进交叉算子和变异算子来增加群体的多样性；利用模拟退火理论调整和改进适应度函数，使得种群中个体的适应度值在进化过程中得到明显提高；改进了初始种群的生成方法，使其生成多样化且“起点”较高的初始种群。从而抑制“早熟”收敛的发生。 为了验证算法的有效性和收敛性，本文有针对性地设计一个仿真实验平台，并实现了该算法的仿真。大量仿真实验表明，本算法能够从多个选播成员中找到满足选播QoS请求(满足时延限制，且代价最小)的最优路径为用户提供服务，且算法是有效和收敛的，较好的解决了“早熟”收敛问题。通过对比仿真实验数据，证明了本算法具有较快的收敛速度，且提高了找到最优解的成功率。

目录

文摘

英文文摘

声明

第1章绪论

1.1课题研究背景

1.2课题研究现状

1.3课题研究内容

第2章相关理论基础

2.1选播通信服务

2.1.1选播通信的网络模型

2.1.2传统的通信服务

2.1.3选播通信服务的功能

2.1.4选播通信服务的应用

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遗传算法的特点

2.3.4遗传算法的运算过程

2.4本章小结

第3章选播路由算法仿真平台

3.1 仿真平台的设计原则

3.2仿真平台的设计

3.3仿真平台的实现

3.3.1类和相关数据结构

3.3.2模块的实现

3.4本章小结

第4章选播路由算法的设计

4.1选播服务模型描述

4.2选播路由算法的描述

4.2.1编码机制

4.2.2初始种群的生成

4.2.3适应度函数

4.3遗传操作

4.3.1选择操作

4.3.2交叉操作

4.3.3变异操作

4.3.4避免循环操作

4.4算法整体描述

4.5本章小结

第5章选播路由算法的性能分析

5.1算法复杂性分析

5.2算法有效性分析

5.3算法收敛性分析

5.4算法成功率分析

5.5本章小结

第6章结语

6.1论文总结

6.2工作展望

参考文献

致谢

攻读学位期间科研情况