基于图论的WSN虚拟骨干网算法研究

论文摘要

由于无线传感器网络具有独特的优点,因此其在军事和民用领域都具有广泛的应用前景。目前,无线传感器网络正在受到越来越多的关注,因此许多与无线传感器网络相关的研究正在成为学术界的研究热点,其中,作为网络路由基础的虚拟骨干网已经成为热门的研究课题之一。由于传感器节点在电池能量、存储空间和运算速度等方面受到严格的约束,因此在设计相关无线传感器网络的算法时应该综合地考虑这些制约因素。本文基于图论分别从能量高效、负载均衡和网络容错这三个方面对无线传感器网络的虚拟骨干网算法进行了研究,主要工作包括：(1)针对集中式虚拟骨干网算法的构造成本过大和分布式虚拟骨干网算法的骨干网规模过大的问题,本文提出了一种基于连通支配集的虚拟骨干网构造算法。该算法运用图论中的连通支配集理论以极低的成本构造了一个虚拟骨干网络,并且运用修剪规则缩小了虚拟骨干网的规模。算法综合考虑节点的能量和距离,使得虚拟骨干网的寿命更长。理论分析证明了在同构传感器网络环境下虚拟骨干网规模的最大值和算法的消息、时间复杂度。仿真分析显示了该算法在骨干网规模、消息总数和总能耗方面都要好于其它算法。(2)针对需要数据转发与融合的骨干节点会比非骨干节点因能量消耗过快而提早失效的问题,本文提出了一种基于连通坡面划分的多重虚拟骨干网轮换算法。该算法运用图论中的连通坡面划分理论构造了若干个没有公共节点的虚拟骨干网,并且使它们按照轮换周期依次承担数据转发与融合的任务,达到了均衡节点负载的目的。理论分析证明了在同构传感器网络环境下虚拟骨干网个数的最小值和算法的消息、时间复杂度。仿真分析显示了该算法在骨干网平均规模、骨干网总数和网络寿命方面都要好于其它算法。(3)针对在异构传感器网络环境下虚拟骨干网修复算法研究的不足,本文提出了一种基于连通支配树的异构虚拟骨干网修复算法。该算法运用图论中的连通支配树理论在异构传感器网络环境下构造了一个异构的虚拟骨干网。当失效的骨干节点造成虚拟骨干网不能连通和覆盖其它节点时,算法会对虚拟骨干网进行局部修复以恢复它的连通性和覆盖性。理论分析证明了初始虚拟骨干网规模的最大值、修复虚拟骨干网所需要的最大节点数和算法的消息、时间复杂度。仿真分析显示了该算法在骨干网规模、消息总数和网络寿命方面都要好于其它算法。本文虽然对无线传感器网络的虚拟骨干网算法进行了一些研究,也取得了—些成果,但是仍然还有一些尚未解决的问题,需要在今后的工作中进一步地研究。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景
• 1.2 研究虚拟骨干网的意义
• 1.3 国内外在该方向的研究现状
• 1.4 本文主要研究工作
• 1.5 论文组织结构
• 第2章 无线传感器网络概述
• 2.1 无线传感器网络的体系结构
• 2.1.1 网络结构
• 2.1.2 节点结构
• 2.1.3 通信协议栈
• 2.2 无线传感器网络的能耗模型
• 2.2.1 节能策略
• 2.2.2 能耗模型
• 2.3 无线传感器网络具有的特点
• 2.4 无线传感器网络应用的领域
• 2.5 无线传感器网络的关键技术
• 2.6 无线传感器网络面临的挑战
• 第3章 虚拟骨干网算法图论基础
• 3.1 图论概念
• 3.1.1 单位圆图
• 3.1.2 双向圆图
• 3.1.3 极大独立集
• 3.1.4 连通支配集
• 3.1.5 连通坡面划分
• 3.1.6 连通支配树
• 3.2 着色算法
• 3.2.1 三色算法
• 3.2.2 四色算法
• 3.3 评价标准
• 3.3.1 理论极限值
• 3.3.2 消息复杂度
• 3.3.3 时间复杂度
• 3.3.4 跳数信息
• 3.4 构造技术
• 3.4.1 基于生成树
• 3.4.2 基于极大独立集
• 3.4.3 基于连通支配集
• 第4章 基于连通支配集的虚拟骨干网构造算法
• 4.1 引言
• 4.2 相关工作
• 4.2.1 算法背景
• 4.2.2 A3算法
• 4.2.3 EECDS算法
• 4.2.4 CDS-Rule-K算法
• 4.3 算法描述
• 4.3.1 节点权值计算
• 4.3.2 算法执行步骤
• 4.3.3 节点状态转换图
• 4.4 理论分析
• 4.4.1 理论极限值
• 4.4.2 消息复杂度
• 4.4.3 时间复杂度
• 4.5 仿真分析
• 4.5.1 仿真环境
• 4.5.2 性能比较
• 4.6 本章小结
• 第5章 基于连通坡面划分的多重虚拟骨干网轮换算法
• 5.1 引言
• 5.2 相关工作
• 5.2.1 IDKDP算法
• 5.2.2 算法不足
• 5.2.3 算法改进
• 5.3 算法描述
• 5.3.1 节点权值计算
• 5.3.2 算法执行步骤
• 5.3.3 节点状态转换图
• 5.4 理论分析
• 5.4.1 论极限值
• 5.4.2 消息复杂度
• 5.4.3 时间复杂度
• 5.5 仿真分析
• 5.5.1 仿真环境
• 5.5.2 性能比较
• 5.6 本章小结
• 第6章 基于连通支配树的异构虚拟骨干网修复算法
• 6.1 引言
• 6.2 相关工作
• 6.2.1 DLEDSR算法
• 6.2.2 异构网络拓扑模型
• 6.3 算法描述
• 6.3.1 节点权值计算
• 6.3.2 算法执行步骤
• 6.3.3 节点状态转换图
• 6.4 理论分析
• 6.4.1 理论极限值
• 6.4.2 消息复杂度
• 6.4.3 时间复杂度
• 6.5 仿真分析
• 6.5.1 仿真环境
• 6.5.2 性能比较
• 6.6 本章小结
• 第7章 结束语
• 7.1 研究总结
• 7.2 下一步研究工作
• 参考文献
• 致谢
• 攻读硕士学位期间发表的论文和参加的科研项目