基于量子遗传算法的无线传感器网络QoS路由选择算法研究 第2页
第一章 绪 论
1.1 研究背景和意义
近年来，量子信息技术的发展越来越向我们展示出了这一新兴领域独特的魅力，它从量子力学的角度出发研究和解决问题，同时对传统的算法加以改进并取得了较好的效果。
遗传算法(GA-Genetic Algorithm)是在模拟达尔文进化论和孟德尔遗传学理论的基础上，形成和发展起来的一种优化问题求解的随机优化方法，算法仅用目标函数在概率准则引导下进行并行全局自适应搜索，就能够处理许多传统优化方法难以解决的复杂问题，因而算法在各个优化领域得到了广泛应用并成为跨学科研究的重点[1][2][3]。量子遗传算法(QGA-Quantum Genetic Algorithm)[4]是量子计算理论和遗传算法原理相结合的产物，量子计算最本质的特征就是利用了量子态的叠加性和相干性，以及量子比特之间的纠缠性。量子计算的优越性主要体现在它的指数级的存储容量以及量子并行处理上，量子遗传算法作为一种新兴的全局优化算法有着巨大的应用前景。QGA以量子计算原理为基础，将量子比特的几率幅表示应用于染色体的编码，使得一条染色体可以表达多个态的叠加，因此比GA具有更好的种群多样性和收敛性，并利用引入动态和静态调整旋转角机制的量子旋转门和量子非门实现染色体的量子变异更新操作，从而实现了目标的优化求解。因而QGA具有种群规模小、寻优能力强、收敛速度快和计算时间短的特点[5][6][7][8]。
当前Intemet中的路由算法主要是保证基本的连通性，路由协议是基于单一度量(metric)优化，难以满足多样的QoS需求。QoS路由经常使用的优化条件是最大吞吐量或最小延迟。优化路由的一般方法是：给定一条路由的代价，使得网络的收入最大。通常，全局优化的解决方案难以实施，因为它依赖于对业务特征的一些假设，约束条件多，计算复杂。目前对QoS路由的研究主要集中于：高效率NP完全路由算法的搜索性算法、多QoS度量参数的状态聚合问题、不精确信息下的层次路由、QoS数据和尽力而为数据的融合问题等。如何在IP网络中引入QoS机制，已是一个十分迫切的应用问题。RFC2676提供了一种思路，从对其引入开销的分析可以看到，QoS路由机制的开销是在目前中等能力处理器的处理能力之内的[9]。因而，QoS路由的研究从理论和实践上都是比较适宜的。
本文主要研究量子遗传算法的机理，提出一种新的量子比特编码方法将量子遗传算法应用到求解多约束QoS路由选择问题。
1.2 本论文的研究工作
本文将对量子遗传算法进行研究、实现，对其特性进行分析。除此之外要对现有的基于量子遗传算法的应用进行分析和改进，提出了一种量子遗传算法（QGA）用于多约束QoS路由选择问题新方案，利用量子计算的一些优点特别是量子并行计算、量子纠缠特性[10]，使QGA具有比遗传算法（GA）更强的并行处理能力和更快的收敛速度，使得QGA具有比传统路由选择算法更好的搜索性能。
本论文结构安排及主要内容如下：
第二章：介绍了经典遗传算法(GA)和量子遗传算法(QGA)的主要思想、算法的流程和机理，详细介绍了量子比特的染色体编码及旋转门策略，并对算法进行了性能测试分析，通过实验测试可知，量子遗传算法比经典遗传算法要具有更好的收敛效果、更快的收敛速度，能够更快地接近目标值。
第三章：介绍了传统路由选择的基本理论，给出了求解网络最短路径的模型，设计了一种新的量子比特编码方法将量子遗传算法应用于求解网络最短路径模型，并进行了系统仿真和性能分析，从仿真结果可知，基于量子遗传算法的最短路径路由选择算法计算时间优于传统的最短路径算法——Dijkstra算法，找到最优路径的成功率大于基于经典遗传算法的最短路径路由选择算法。
第四章：介绍了服务质量(QoS)和服务质量路由(QoS Routing，QoSR)的基本概念，给出了求解网络多约束QoS的模型，设计了一种新的量子比特编码方法将量子遗传算法应用于求解网络多约束QoS路由模型，并进行了系统仿真和性能分析。从仿真结果可知，基于量子遗传算法的QoS路由选择算法计算时间优于传统的算法，找到最优路径的成功率大于基于经典遗传算法的QoS路由选择算法。
第五章：介绍了无线传感器网络（WSN）的基本概念、关键技术和路由协议基本概念，给出无线传感器网络的系统模型，包括网络模型、节点能量模型和节点选择模型，采用第三章设计的量子比特编码方法将量子遗传算法应用无线传感器网络的系统模型，并进行了计算机仿真和分析。从仿真结果可知，基于量子遗传算法的最短路径路由选择算法求得路径的全网能量消耗要低于基于遗传算法所求解，从而达到延长网络生存期的目的。另外，基于量子遗传算法的无线传感器的QoS路由选择算法找到最优路径的成功率大于基于经典遗传算法的无线传感器的QoS路由选择算法。
第六章：对论文工作的总结，并对下一步的工作进行了展望。

上一页  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]  ... 下一页  >>