基于同调理论的WSN覆盖空洞检测算法研究

摘要

本学位论文的研究课题来源于国家自然科学基金“基于同调理论的无线传感器网络k重覆盖若干算法研究”(批准号:61601122)。主要针对节点位置和节点间距离信息未知的场景，对无线传感器网络(WSN，Wireless Sensor Network)的覆盖空洞检测算法进行了深入研究。论文利用同调理论中的Rips复形对WSN的拓扑进行建模，在保证覆盖拓扑特性不变的前提下，休眠冗余节点，简化Rips复形，再根据简化后的Rips复形提出空洞检测算法。
　　论文的主要贡献如下:
　　(1)根据WSN的特点，提出了一种基于相对方位角(RDA，Relative Direction Angle)信息的覆盖空洞检测算法。首先，在节点位置和距离信息未知的情况下，根据同调理论，利用节点之间的连通信息构建网络拓扑的Rips复形。其次，计算节点的权重大小，利用节点之间的RDA信息，休眠部分节点，并且断开冗余节点之间的连接，从而达到简化Rips复形的目的。进而，提出了基于RDA信息的覆盖空洞检测算法，根据RDA信息找出所有的空洞边界(BE，Boundary Edge)，以检测出所有的覆盖空洞。仿真分析表明，所提算法能够在保持原有WSN拓扑特性的同时，减少网络中部署节点的个数，整个算法的复杂度为O(nm2)，覆盖空洞检测的正确率能达到99％，n为节点的个数，m为节点的平均邻节点个数。
　　(2)在RDA信息未知的情况下，通过在Rips复形中引入联合Laplacian算子(JLO，Joint Laplacian Operator)，提出了一种基于Laplacian矩阵(LM，Laplacian Matrix)的覆盖空洞检测算法。算法首先通过计算节点的权重大小，选择合适的候选休眠节点。其次，构建休眠节点的邻节点形成的子单纯复形，计算其LM零空间矩阵的维数，根据维数对节点进行休眠控制。由此，判断所有的候选节点，直到不再存在可以被休眠的节点，以达到简化拓扑的目的。然后，基于简化的Rips复形，先根据拓扑特性找出形成覆盖空洞的边界，再将空洞边界顺次连接即可检测出WSN中存在的覆盖空洞。仿真结果表明，所提算法能有效减少网络资源，复杂度为O(n2m4)，覆盖空洞检测的正确率为99％，n为节点的个数，m为平均邻节点的个数。

目录

声明

摘要

图表目录

缩略语

第1章 绪论

1．1 课题背景

1．2 国内外研究现状

1．3 主要工作及章节安排

1．3．1 主要研究工作

1．3．2 章节安排

第2章 无线传感器网络和同调理论概述

2．1 无线传感器网络

2．1．1 无线传感器网络结构

2．1．2 节点感知模型

2．1．3 无线传感器网络的特点

2．1．4 无线传感器网络的应用领域

2．1．5 无线传感器网络协议层次

2．2 同调理论

2．2．1 单纯复形

2．2．2 同调群

2．2．3 WSN中的单纯复形

2．3 本章小结

第3章 基于RDA信息的覆盖空洞检测算法

3．1 引言

3．2 系统模型

3．3 Rips复形简化

3．3．1 算法流程

3．3．2 休眠节点

3．3．3 计算节点权重

3．3．4 断开节点连通

3．4 覆盖空洞检测算法

3．4．1 算法流程

3．4．2 检测空洞边界

3．4．3 粗略空洞信息

3．4．4 精确空洞信息

3．5 仿真与分析

3．5．1 算法仿真

3．5．2 性能分析

3．6 本章小结

第4章 基于LM的覆盖空洞检测算法

4．1 引言

4．2 系统模型

4．3 覆盖空洞检测算法

4．3．1 算法流程

4．3．2 节点权重计算

4．3．3 节点休眠

4．3．4 检测覆盖空洞

4．4 仿真与分析

4．4．1 算法仿真

4．4．2 复杂度分析

4．5 本章小结

第5章 总结与展望

5．1 研究工作总结

5．2 后续工作展望

致谢

参考文献

攻读硕士学位期间的研究成果