论文总字数：25685字

摘 要

无线传感器网络（Wireless Sensor Networks，WSNs）由于其在军事、医疗卫生、智能交通等多个领域的广泛应用而引起广泛关注。在某些应用中，由于节点的随机分布、能量消耗、节点损坏等原因会产生覆盖空洞，从而影响无线传感器网络的服务质量。因此，研究无线传感器网络的覆盖空洞修复算法具有重要意义。

针对节点随机部署的场景，本文提出了一种覆盖空洞修复算法。在已知区域内空洞的边界圆周的具体分布的情况下，利用深度优先搜索（Depth-First-Search，DFS）算法对边界圆周多边形的各个顶点进行遍历，并利用顶点信息求出形心具体位置。修复无线传感器网络空洞时，在形心处新增加传感器节点，覆盖原本的空洞。同时，在空洞未修复完全的情况下，迭代多次实现区域全覆盖。仿真结果表明所提算法可以完全修复无线传感器网络中的覆盖空洞，从而实现区域的全覆盖。

关键词：无线传感器网络，覆盖空洞修复，深度优先搜索

Abstract

Wireless Sensor Networks (WSNs) have attracted wide attention due to their wide applications in many fields such as military, medical and health, and intelligent transportation. In some applications, due to random distribution of nodes, energy consumption, node damage, etc., coverage holes may appear, thereby affecting the quality of the service of wireless sensor networks. Therefore, it is of great significance to study the coverage healing algorithm for wireless sensor networks.

For the scenario where nodes are randomly deployed, this paper proposes a coverage hole healing algorithm. Using the Depth-First-Search (DFS) algorithm to traverse each vertex of the boundary circle polygon in the case of the specific distribution of the boundary circle of the known region, and use the vertex information to find the exact position of the centroid. When healing a hole in a wireless sensor network, a new sensor node is added at the centroid to cover the original hole. At the same time, it is iterative to implement full coverage of the area multiple times without complete healing of the hole. The simulation results show that the proposed algorithm can completely heal the coverage hole in the wireless sensor network, so as to achieve full coverage of the area.

KEY WORDS: Wireless sensor networks, Coverage hole healing, Depth first search

目录

摘要 I

Abstract II

第一章 绪论 1

1.1 引言 1

1.2 覆盖空洞修复算法研究现状 1

1.2.1 基于移动节点的空洞修复算法 1

1.2.2 基于三角形网格的空洞检测和修复算法 2

1.2.3 激活冗余节点空洞修复算法 3

1.2.4 利用机器人实现覆盖空洞修复算法 4

1.3 研究思路 4

1.4 章节安排 5

第二章 理论基础 6

2.1 无线传感器网络感知模型 6

2.1.1 布尔感知模型 6

2.1.2 概率感知模型 6

2.1.3 有向感知模型 6

2.2 覆盖问题 7

2.2.1 确定性覆盖与随机覆盖 7

2.2.2 目标覆盖、栅栏覆盖与区域覆盖 8

2.3 相关概念介绍 9

2.3.1 性能指标 9

2.3.2 相关术语 9

2.4 本章总结 12

第三章 覆盖空洞修复算法 3

3.1 问题描述与研究思路 13

3.2 覆盖空洞检测算法 13

3.3 覆盖空洞修复算法 14

3.3.1 深度优先搜索 14

3.3.2 基于DFS的覆盖空洞修复算法 18

3.4 本章总结 23

第四章 算法验证与分析 25

4.1 算法验证 25

4.1.1 边界圆周多边形离散分布 25

4.1.2 边界圆周多边形存在公共点与公共边 28

4.2 算法迭代次数分析 30

4.3 本章总结 31

第五章 总结与展望 32

5.1 总结 32

5.2 展望 32

致谢 34

参考文献 35

第一章 绪论

引言

无线传感器网络（Wireless Sensor Network，WSN）是集传感器技术、无线传输技术、网络通信技术、分布式信息处理技术与编程技术于一体的全新的信息获取和处理系统^[1]。无线传感器网络具有大规模、自组织、动态性、可靠性、以数据为中心等特点。在现代社会中，无线传感器网络应用广泛，在军事、医疗卫生、智能交通等多个领域发挥着重要的作用，缩短了世界各地的“距离”，降低了人们获取信息的难度，便利了人们的生活。

无线传感器网络中的传感器节点可以感知周围环境，彼此之间可以实现无线通信，甚至某些传感器节点可以任意移动位置，以应对不同的地貌，灵活多变。而在某些情况下，由于部署区域环境恶劣，传感器节点分布不合理或者传感器功能失效等原因，无线传感器网络覆盖区域出现了空洞，严重影响了无线传感器网络服务质量^[2]。因此，解决网络覆盖空洞问题对于完善无线传感器网络功能而言是十分重要的。

由于人力物力自然条件等多方面因素的限制，作为网络的管理者，不可能对待测区域内每一个传感器节点进行有效监管。所以这就要求无线传感器网络具有一定的自我调整和恢复能力^[3]。本文提出的无线传感器网络空洞修复算法主要可以分为两块：第一步检测出网络中的覆盖空洞，并图形化描述空洞。第二步利用第一步得出的图形顶点与边界的位置信息，结合深度优先搜索（Depth-First-Search，DFS）算法得到放置新增传感器节点位置信息，并在该位置放置新的传感器节点，其感知区域将空洞覆盖住，从而实现修复的效果。

覆盖空洞修复算法研究现状

无线传感器网络在现实生活中应用广泛，因此保证网络稳定、维护网络的安全也成为人们研究的重中之重。完善无线传感器网络功能领域，网络覆盖空洞修复也取得了不错的成果。空洞修复可以分为两部分：第一步空洞检测也就是目标区域的覆盖问题，第二步空洞修复。在众多的覆盖空洞修复方案中，有以下几类：基于移动内点、基于三角形网格、激活冗余节点以及利用机器人的空洞修复算法。但是需要注意的是，关于空洞修复的算法很多，各有优势和局限，因此在实际应用中，面对不同的区域情况，选择与之相适应的算法。

基于移动节点的空洞修复算法

在无线传感器网络中，由于部署区域环境恶劣，传感器节点分布不合理或者传感器功能失效等原因，目标区域一部分未被传感器节点感知，无线传感器网络覆盖区域出现了空洞，降低了传感器网络的精确率和效率。在传感器节点可以移动的情况下，基于移动节点的空洞修复算法为空洞修复提供了新思路。文献[4]给出了该算法在K-覆盖确认算法的基础上得到覆盖空洞的具体位置，之后利用几何计算学的知识，利用节点传感器覆盖弧性质求出空洞边界最佳内点位置。如图1-1所示，节点与相邻节点相交，形成的覆盖弧的表示形式。而在已知覆盖空洞边界内的最佳内点的具体位置的情况下，移动覆盖空洞边缘节点，从而减少邻居节点传感器感知圆周的重叠面积，扩大覆盖面积，实现空洞修复。这种算法在传感器节点移动较小距离的情况下可以有效提高目标区域的覆盖率。

剩余内容已隐藏，请支付后下载全文，论文总字数：25685字