基于遗传算法的计算机网络选播路由算法的研究

• 作 者: 李旻朔
• 发表日期: 2003年期
• 关键词: 计算机网络 选播路由 选播路由算法 遗传算法 随机方法 全局搜索 局部搜索

如何在下一代Internet上实现高质量的网络服务是计算机网络技术研究的前沿课题，本文在对网络选播路由的基本概念和技术研究前提作了比较充分的理解和分析的基础上，建立了选播路由算法的问题模型，研究如何将遗传算法引入选播路由算法。 论文探讨利用遗传算法和随机方法研究选播路由算法的关键技术问题，设计实现了基于遗传算法的选播路由算法，解决了算法中的编码模式、初始种群选择、适应度函数、交叉策略、变异规则，以及算法的收敛、路由死循环的避免和负载均衡等问题。我们针对不同的网络规模，设计了两种选播路由算法。第一种选播路由算法针对较小规模的网络，是基于遗传算法的全局搜索算法，算法以选播路由为基础，在生成全局候选路径的前提下，通过演化，得到全局最优解；第二种选播路由算法针对规模较大的网络，算法做了相应的改进，是一个利用局部信息的选播路由算法，算法确定路由时无需源节点具有全网拓扑，每个节点只需同邻接节点交换信息就可进行路由计算，下一节点的演化基因及候选路径做相应的延伸，候选路径的生成与演化同时进行，以较短的时延达到局部最优，并可节省大量的内存。 为验证算法的有效性，我们设计了网络模拟平台，构造网络的拓扑结构及各条链路的容量，生成相关的服务源／目的组节点。利用网络模拟平台，对设计的选播路由算法进行了大量的网络仿真实验。模拟结果表明我们的算法是有效的，搜索效率得到了显著提高，网络负载达到充分平衡，大大提高了网络资源的利用率。 本文的研究为优化网络资源，提高服务质量提供了理论依据，在计算机网络中为提供高质量的选播路由服务的算法设计具有科学的参考价值。