面向节能和容错的异构无线传感器网络分布式拓扑控制算法研究

摘要

随着物联网的快速发展，无线传感器网络受到了国内外广泛的关注。由于受到成本和体积的限制，传感器节点的能量一直是值得高度关注的重要问题。拓扑控制是无线传感器网络中节约能量、增加运行时间的关键技术，在保障网络连通的基础上，通过优化网络的拓扑结构，降低节点之间的通信干扰，使得网络能量均衡消耗，最终达到延长网络生命时间的目的。此外，节点可能部署在危险或无人值守区域，容易受到外界因素影响而失效，在考虑节能的同时还必须关注网络的容错性，当部分节点失效时仍能保证网络正常运行是无线传感器网络中另外一个值得研究的重要课题。
　　本文考虑传感器节点具有不同的计算能力、通信能力和能量水平的特点，主要对拓扑控制在异构无线传感器网络中的节能和容错问题进行研究。面向节能的拓扑控制研究先从拓扑构建方法入手，进而结合拓扑维护策略以完整的拓扑控制过程阐述如何构建并维护网络的拓扑结构;然后，在优化的网络拓扑上研究面向节能和高覆盖率的能量平衡的路由协议，对于延长无线传感器网络生命时间起到重要作用;最后，考虑节点容易失效的特性，从理论研究和实际应用两个方面分别对容错拓扑控制算法进行研究，在保障网络容错的基础上尽可能地节省能量，本文的主要工作和成果如下:
　　(1)针对当前研究普遍将拓扑控制作为拓扑构建或拓扑维护单独进行研究的问题，提出了启发式算法将两个过程进行结合，通过改进A3G算法中的适应度函数、发送消息格式和算法流程，在拓扑构建过程中优化求解最小连通支配集的NP-Hard问题。然后，通过定义时间、能量和故障三种不同的触发机制，提出了一种与拓扑构建过程相结合的拓扑维护方法A3GM。当现有网络性能严重下降时，由Sink节点决定执行局部拓扑修复或全局拓扑维护策略以保障网络的稳定运行。
　　(2)为了减少路径能耗和均衡支配节点的能量消耗，在优化的拓扑上提出了一种由Sink节点发起的能量平衡的分布式路由协议EEVB，有效解决了ViTAMin协议只能适用于同构网络、产生支配节点数量过大、可能会出现非连通的网络拓扑以及支配节点能耗不均衡问题。此外，考虑到高覆盖率需求的场景，通过增加适当的支配节点对EEVB进行扩展，提出了一种满足高覆盖率需求的能量平衡的路由协议EEVBCov，在关闭部分网络节点的基础上，尽可能地覆盖整个网络监控区域。
　　(3)针对实际环境中拓扑容易频繁重构的特性，提出了一种具有较小通信开销的异构无线传感器网络分布式拓扑控制算法HELM，算法在所有节点都只发送一次消息的情况下就能快速构建连通支配集，具有较高的能效性。此外，考虑到高覆盖率需求的应用场景，HELMCov算法可以在HELM基础上进行扩展，从而得到更高的网络覆盖率。
　　(4)针对连通支配集还需要具有一定的容错性以应对节点失效或链路错误的问题，提出了任意k和m取值的完全分布式的k-连通m-支配集构建算法(k,m)-HELM和(k,m)-HELMCov，k-连通保证了网络中支配节点之间的容错性，m-支配则保证了普通节点与支配节点之间的容错性。算法首先以较小的通信代价构建节能或高覆盖需求的连通支配集，然后采用最大独立集的思想从剩余节点中选择合适的节点将普通节点进行m-支配，最后在局部拓扑中通过公共邻居节点将支配节点扩展为k-连通。
　　(5)在带有少量能量自补给能力节点的新型异构无线传感器网络模型中对容错拓扑控制算法进行研究，针对算法(k,m)-HELM和(k,m)-HELMCov产生活跃节点过多的问题，提出了面向节能和高覆盖需求的分布式容错拓扑控制算法EBFT和EBFTCov。算法在不需要节点位置信息的情况下首先选择权值较优的节点构建连通支配集，然后选择容错度较大的节点作为备份节点，最后在数据收集过程对支配节点的能耗进行均衡，不但减少了活跃节点的数量，而且保证了容错性，同时通过平衡节点的能量消耗以延长网络的生命时间。
　　理论分析和仿真实验均证明了上述研究结果的有效性，通过与同类协议或算法进行对比，本文所提出的算法能够更好地减少生成的活跃节点数量并降低通信开销，有效促进了全网节点的负载均衡，最终延长了网络的生命时间。

目录

声明

摘要

第1章 绪论

1．1 研究背景及意义

1．2 无线传感器网络简介

1．2．1 网络的系统结构

1．2．2 传感器节点结构

1．2．3 网络的特点

1．2．4 关键技术

1．2．5 应用领域

1．3 拓扑控制理论

1．3．1 拓扑控制概述

1．3．2 拓扑控制研究的主要问题

1．3．3 拓扑控制算法的设计目标

1．3．4 拓扑控制算法的研究现状

1．4 本文研究的主要内容及创新点

1．5 本文的组织结构

第2章 面向节能的异构WSNs分布式拓扑控制方法研究

2．1 引言

2．2 相关研究工作

2．3 A3G算法分析

2．4 系统模型与定义

2．4．1 网络模型

2．4．2 相关定义

2．4．3 无线通信能量模型

2．5 基于反向生成CDS树的拓扑构建算法

2．5．1 数据结构和选择标准

2．5．2 算法描述

2．6 基于Sink节点决策的拓扑维护算法

2．6．1 触发机制

2．6．2 算法描述

2．7 理论分析

2．8 仿真实验

2．8．1 实验环境及参数设置

2．8．2 具体实验设计

2．8．3 实验结果分析

2．9 本章小结

第3章 面向高覆盖率的异构WSNs能量平衡路由协议研究

3．1 引言

3．2 相关研究工作

3．3 ViTAMin协议分析

3．4 基于CDS的分布式能量平衡路由协议

3．4．1 节点的适应度函数

3．4．2 虚拟骨干的构建算法描述

3．4．3 基于能耗均衡的路由选择策略描述

3．5 面向高覆盖需求场景的路由协议扩展

3．5．1 算法描述

3．5．2 覆盖度的求解方法

3．6 理论分析

3．7 仿真实验

3．7．1 实验环境及参数设置

3．7．2 具体实验设计

3．7．3 实验结果分析

3．8 本章小结

第4章 面向容错的异构WSNs的k-连通m-支配集构建

4．1 引言

4．2 相关研究工作

4．3 相关定义

4．4 面向容错的分布式k-连通-m支配集算法

4．4．1 面向节能的分布式拓扑构建方法

4．4．2 面向高覆盖需求场景的算法扩展

4．4．3 m-支配集的分布式生成

4．4．4 k-连通网络的分布式扩展

4．5 理论分析

4．6 仿真实验及分析

4．6．1 实验环境及参数设置

4．6．2 具体实验设计

4．6．3 实验结果分析

4．7 本章小结

第5章 带有能量补给异构WSNs容错拓扑控制算法研究

5．1 引言

5．2 相关研究工作

5．3 相关模型

5．3．1 新型异构网络模型

5．3．2 节点能量采集模型

5．3．3 数据收集应用模型

5．4 算法描述

5．4．1 节点的属性定义

5．4．2 面向节能的连通支配集分布式构建

5．4．3 面向覆盖的连通支配集分布式扩展

5．4．4 面向容错的备份节点集分布式构建

5．4．5 面向节能的数据收集过程优化

5．5 理论分析

5．6 仿真实验及分析

5．6．1 实验环境及参数设置

5．6．2 具体实验设计

5．6．3 实验结果分析

5．7 本章小结

第6章 总论与展望

6．1 本文总结

6．2 后期展望

参考文献

致谢

攻读学位期间参加的科研项目和成果