基于同调理论的无线传感器网络k重覆盖若干算法研究

This project aims to study in-depth the homology theory based coverage problems in wireless sensor networks (WSNs). Some innovations in related theories and key technologies of k-coverage in WSNs are expected to be obtained by studying some algorithms for coverage hole detection, coverage hole healing and coverage optimization in the scenarios without information of node location and information of distances between nodes. The detailed research contents and objectives are as follows. Firstly, Rips complex will be used to model wireless sensor networks. An efficient distributed reduction algorithm for Rips complex will be proposed. Then the number and the boundary nodes of coverage holes will be obtained by computing the dimension and minimum generators of the first homology group for the reduced Rips complex. Secondly, homology based coverage hole healing algorithms will be studied. By adjusting the sensing and communication ranges of boundary nodes, the new Rips complex constructed by the boundary nodes will contain no coverage holes. The coverage holes are consequently healed. Finally, homology based coverage optimization algorithms will be proposed. Some independent cover sets are selected, and each set covers the target region by turns in order to optimize the coverage and extend the lifetime of wireless sensor networks. Through in-depth theoretical analysis, computer simulations and some necessary experiments, this project tries to make the proposed algorithms applicable in real wireless sensor networks in the future.

本项目拟深入研究基于同调理论的无线传感器网络覆盖问题，通过对节点位置信息和节点间距离信息未知场景下的覆盖空洞检测、覆盖空洞修复和覆盖优化控制等算法的研究，能够在无线传感器网络的k重覆盖相关理论和关键技术方面有所创新。具体研究内容及目标是：利用同调理论中的Rips复形对无线传感器网络建模，提出高效的分布式Rips复形简化算法，通过计算简化后Rips复形的1阶同调群的维数和最小生成元，得到覆盖空洞的个数及其边界节点；研究基于同调理论的覆盖空洞修复算法，通过调节覆盖空洞边界节点的感知范围和通信范围，使得由边界节点组成的新Rips复形中不存在覆盖空洞，从而实现对覆盖空洞的修复；提出基于同调理论的覆盖优化控制算法，选择出多组独立节点覆盖子集，让每组节点轮流覆盖，从而实现对目标区域的覆盖优化，延长网络的生命周期。通过深入的理论分析、计算机仿真和必要的实验，使所提算法将来能用于实际的无线传感器网络中。

无线传感器网络由于其在战场监视、环境监测、精准农业等领域的应用而受到国内外学者的广泛关注，在这些应用中，覆盖是无线传感器网络的一个重要问题。本项目针对节点位置未知场景下的无线传感器网络，研究了“无线传感器网络覆盖空洞检测算法”、“无线传感器网络覆盖空洞修复算法”和“无线传感器网络覆盖优化算法”等内容，并通过仿真分析验证了所提算法的可行性。具体研究内容包括：提出了基于节点间距离的无线传感器网络k-覆盖空洞检测算法，得到了覆盖空洞的边界圆周；提出了单纯复形简化算法，进而提出了基于同调理论的无线传感器网络k-覆盖空洞检测算法，分析了所提算法的复杂度和空洞检测性能，结果表明所提算法可以准确检测95%以上的非三角形空洞的边界圆周；提出了利用移动节点，基于波达角的覆盖空洞修复算法，通过与相关算法的性能进行比较，得出所提算法在空洞修复和节点移动的总距离方面具有更好的性能；利用单纯复形简化的思想，提出了基于复形扩张的无线传感器网络覆盖优化算法，并通过仿真比较了所提算法与相关算法的性能，结果表明所提算法复杂度较低、覆盖优化性能较好，能够大大节省节点能耗从而延长网络生命周期。本项目通过深入的理论分析、计算机仿真以及相关的实验，在无线传感器网络的覆盖方面进行了探索性的研究，提出的若干覆盖算法能够优化网络的节点部署以及能耗，延长网络的生命周期，为将所提算法应用于实际的无线传感器网络提供了有力的理论支持。