基于量子遗传算法的路由选择算法研究

摘要

量子遗传算法是融合量子计算和遗传算法的一种新兴的全局优化算法，因算法具有种群规模小、寻优能力强和收敛速度快的特点，在许多领域都得到了广泛应用。通信网络技术的飞速发展产生了大量的实时多媒体多播应用，如视频点播和多媒体会议等。这些应用的一个共同特点是它们都需要从一个源节点或多个源节点将信息传输到一个或多个目的节点，在源点和目的节点之间找到一条能够同时满足多个约束条件且具有最小代价的路径。多约束QoS路由选择是指将信息从网络源节点发送到目的节点，同时要求源节点到目的节点的通信链路满足一定的约束条件，如链路传输带宽、链路时延和信息丢失率等。多约束QoS路由选择问题已被证明是一个NP完全问题。
　　 本文研究了量子遗传算法及其在通信网络路由选择中的应用。
　　 第一，量子遗传算法及其在求解最短路径问题中的应用研究。研究了量子遗传算法的原理；提出了基于量子遗传算法的最短路径问题求解方案。计算机仿真表明，使用量子遗传算法可以获得比传统遗传算法更优的最短路径。
　　 第二，量子遗传算法在QoS路由选择问题中的应用研究。提出了基于量子遗传算法的在带宽、时延和网络负载均衡等多约束条件下的单播路由选择方案，并对其进行了计算机仿真。仿真结果表明了基于量子遗传算法的QoS路由选择算法具有较好的收敛效果和较高的最优路径获取成功率。
　　 第三，量子遗传算法在无线传感器网络QoS路由选择问题中的应用研究。提出了基于量子遗传算法的无线传感器网络QoS路由选择方案，仿真结果表明，基于量子遗传算法的无线传感器网络QoS路由选择算法使得网络节点耗能更低，有利于节省节点的能量来延长网络的生存期。