基于量子遗传算法的无线传感器网络QoS路由选择算法研究

论文字数:35263,页数:70  信号与信息处理专业硕士论文

摘 要
 量子遗传算法(Quantum Genetic Algorithm)作为量子计算理论和遗传算法原理相结合的一种新兴的全局优化算法，因算法具有种群规模小、寻优能力强、收敛速度快和计算时间短的特点，在许多领域都得到了广泛应用。计算机网络技术的飞速发展产生了大量的实时多媒体多播应用，如视频点播和多媒体会议等。这些应用的一个共同特点是它们都需要从一个源节点或多个源节点将信息传输到一个或多个目的节点，在源点和目的节点之间找到一条能够同时满足多个约束条件且具有最小代价的路径。多约束QoS路由选择是指将信息从网络源节点发送到目的节点，同时要求源节点到目的节点的通信链路满足一定的约束条件，如链路传输带宽、链路时延和信息丢失率等。多约束QoS路由选择问题已被证明是一个NP完全问题。
 本文研究了基于量子并行计算的量子遗传算法并提出了一种基于量子遗传算法（QGA）的一种求解带宽、时延和丢失率等的多约束单播路由优化问题。
 本文首先介绍了量子遗传算法的主要思想、机理，且对量子遗传算法进行了性能测试分析。
 其次，提出了一种新的量子编码方法来利用量子遗传算法求解最短路径（shortest path, SP）问题，并通过计算机仿真实现了算法。
 最后，在基于量子遗传算法求解最短路径问题的基础上，考虑到带宽、时延的约束和网络负载均衡，提出了利用量子遗传算法求解多约束QoS路由选择，还将该算法应用到无线传感器网络中求解QoS路由，并仿真实现了该算法。仿真结果表明，文中提出的方法在综合性能方面明显优于经典遗传算法和传统的路由选择算法。

关键词：量子计算、量子遗传算法、最短路径路由、QoS路由、无线传感器网络
ABSTRACT
 Quantum genetic algorithm, as the combination of the quantum computing theory and the principle of genetic algorithm, is a new global optimization algorithm, which has the characteristics of smaller population size, stronger capability in the optimization, faster convergence and shorter time in computing. As the rapid development of computer network technology, a lot of real-time multimedia applications, such as video on demand and multimedia conferencing, are applied. We must find the path that has the minimum cost from the resource node to the destination node for these applications. Multi-constrained QoS routing selection means that while the information is transmitted from the resource node to the destination node, the communication link must satisfy certain constraints, such as bandwidth, delay and the information loss ration, etc. And multi-constrained QoS routing selection has been proved to be a NP complete problem.
 The dissertation makes some researches on the applications of quantum genetic algorithm on the basis of parallel quantum computation in multi-constrains QoS routing selection.
 First of all, the dissertation introduces the basic principle of quantum genetic algorithm. Secondly, this paper presents a quantum genetic algorithm approach to the shortest path (SP) routing problem. Finally, this paper presents a quantum genetic algorithm approach to the QoS routing problem. The network’s width, delay and balancing the network loads have been considered. And the algorithm is applied to the Wireless Sensor Networks (WSN) for solving QoS routing. Computer simulations show that the Quantum Genetic Algorithm (QGA) exhibits a better quality of solution (route optimality) than the conventional Genetic Algorithm (GA).
 
Keywords: Quantum computation; Quantum Genetic Algorithm; Shortest path routing; QoS Routing; Wireless Sensor Network

目 录
摘 要 I
ABSTRACT II
目 录 III
第一章 绪 论 1
1.1 研究背景和意义 1
1.2 本论文的研究工作 2
第二章 量子遗传算法 4
2.1 遗传算法的基本原理 4
2.2 遗传算法常见编码方法和基本操作 6
2.2.1 编码问题 6
2.2.2 基本操作 7
2.2.3 遗传算法的特点和应用 10
2.3 量子遗传算法 11
2.3.1 量子染色体 11
2.3.2 量子旋转门 12
2.3.3 量子变异操作 14
2.3.4 算法描述 15
2.4 算法性能测试 16
2.5 本章小结 17
第三章 基于量子遗传算法的最短路径算法研究 18
3.1 路由选择算法 18
3.2 基于遗传算法的最短路径问题方案 24
3.2.1 网络模型 24
3.2.2 编码 25
3.2.3 适应度函数 26
3.2.4 选择 26
3.2.5 交叉 26
3.2.6 变异 28
3.3 基于量子遗传算法的最短路径问题方案 29
3.3.1 量子比特编码 30
3.3.2 基于量子遗传算法的最短路径算法参数设计 31
3.4 仿真及结果分析 32
3.5 本章小结 34
第四章 基于量子遗传算法的QoS路由选择算法研究 35
4.1 QoS路由概念 35
4.2 基于量子遗传算法的QoS路由选择算法方案 36
4.2.1 QoS路由问题网络模型 36
4.2.2 基于量子遗传算法的QoS路由选择算法参数设计 39
4.3 仿真及结果分析 40
4.4 本章小结 44
第五章 基于量子遗传算法的无线传感器网络QoS路由选择算法研究 45
5.1 无线传感器网络的概念 45
5.1.1 无线传感器网络的关键技术 45
5.1.2 无线传感器网络节点特征 48
5.2 无线传感器网络路由协议概述 49
5.2.1 无线传感器网络路由协议的特点 50
5.2.2 无线传感器网络的分类 50
5.3 基于量子遗传算法的无线传感器网络QoS路由选择方案 52
5.3.1 系统模型 52
5.3.2 基于量子遗传算法的无线传感器网络QoS路由选择算法参数设计 55
5.4 仿真及结果分析 56
5.5 本章小结 59
第六章 总结和展望 60
6.1 课题研究总结 60
6.2 工作展望 61
致 谢 62
参考文献 63