无线传感器网络中k-连通k-支配集的集中式构造研究

论文摘要

无线传感器网络是计算、通信和传感器这三项技术相结合的产物,它随着微处理器和无线通信技术的发展,在军事、医疗、环境等方面具有广泛的应用潜力。由于传感器节点能量有限,节点的失效会导致网络链路失败,因此在无线传感器网络中,通常采用连通支配集来构成一个虚拟骨干网进行分层路由,对重要的目标或环境需要构造容错性高,可靠性好的虚拟骨干网。本文采用集中式算法研究连通支配集的构造,主要适用于具有中心控制或管理节点的无线传感器网络。对于1-连通1-支配集的构造,本文详细系统地比较了单方向搜索和多方向搜索两种集中式算法。通过比较得出,单方向搜索算法运行的时间短,多方向搜索算法构造的连通支配集小。为了提高网络的容错性和可靠性,本文提出两种2-连通2-支配集的集中式构造算法,分别是先回路后支配和先支配后回路。前一种算法是先形成一个由支配点组成的回路,然后以此回路为基础不断地扩充此回路,直到不在回路中的节点为2-被支配为止;后一种算法是首先保证每个非支配点的状态都为2-被支配,然后再使图中所有支配点构成回路。仿真结果表明算法先回路后支配适用于节点密度较低的网络,而算法先支配后回路适用于节点密度较高的网络。在某些特殊领域,需要构造容错性更高和可靠性更好的网络,本文提出k -连通k -支配集的集中式构造算法, k适用于任意自然数。该算法被称作先支配后连通,即首先保证图中所有节点都变为支配点或k-被支配点,其次选择一个边缘支配点着色,然后对其它支配点逐点着色,着色的条件是该点是已着色节点的邻接点,且和已着色节点均为k-连通,若不满足此条件,添加适当的支配点再接着着色,直到图中所有支配点均被着色为止。最后通过计算机编程实现,证明了该算法的有效性。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题背景
• 1.1.1 无线传感器网络的体系结构
• 1.1.2 无线传感器网络的特点
• 1.1.3 无线传感器网络的应用
• 1.2 国内外研究现状及分析
• 1.3 课题研究意义
• 1.4 本文研究的主要内容
• 第2章 构造连通支配集相关的图论知识
• 2.1 图论及其术语
• 2.1.1 图的定义
• 2.1.2 图的矩阵表示
• 2.1.3 连通支配集
• 2.1.4 最短路径问题
• 2.2 TopDisc算法
• 2.3 最大流最小割算法
• 2.4 本章小结
• 第3章 1-连通1-支配集的集中式构造算法
• 3.1 问题描述及符号说明
• 3.2 1-连通1-支配集的集中式构造算法
• 3.2.1 单方向搜索1-连通1-支配集的集中式构造算法
• 3.2.2 多方向搜索1-连通1-支配集的集中式构造算法
• 3.3 两种算法时间复杂度分析
• 3.4 两种算法仿真结果分析比较
• 3.5 本章小结
• 第4章 2-连通2-支配集的集中式构造算法
• 4.1 问题和规则描述及符号说明
• 4.2 先回路后支配算法
• 4.2.1 算法描述
• 4.2.2 算法正确性证明
• 4.3 先支配后回路算法
• 4.3.1 算法描述
• 4.3.2 算法正确性证明
• 4.4 两种算法时间复杂度分析
• 4.5 两种算法仿真结果分析比较
• 4.6 本章小结
• 第5章 k-连通k-支配集的集中式构造算法
• 5.1 问题描述及符号说明
• 5.2 k-连通k-支配集的集中式构造算法
• 5.2.1 算法描述
• 5.2.2 算法正确性证明
• 5.2.3 算法时间复杂度分析
• 5.2.4 算法仿真结果分析
• 5.3 本章小结
• 结论
• 参考文献
• 攻读学位期间发表的学术论文
• 致谢