无线传感器网络中两类覆盖问题的算法研究

摘要

无线传感器网络作为一种全新的信息获取和处理技术，能够广泛应用在反恐抗灾、国防军事、医疗卫生以及环境监测等诸多领域，被认为是二十一世纪最重要的技术之一。
　　目标覆盖问题是传感器网络进行目标识别、监控、跟踪等众多应用的前提，也是无线传感器网络研究中的热点问题之一。现有的目标覆盖类型大致可分为三类：点覆盖、线覆盖以及区域覆盖。
　　本文重点研究点覆盖和线段覆盖两类问题，论文结构主要包括以下三大部分。
　　第一部分，预备知识介绍和问题引入。该部分给出了图论、组合优化、计算复杂性、近似算法等相关定义，并介绍了无线传感器网络中覆盖问题的背景、应用、发展历程以及国内外相关研究成果。
　　第二部分，论文主要内容：对无线传感器网络中的线段覆盖和点覆盖两类问题进行研究。
　　第一类问题——线段覆盖问题，我们重点考虑目标线段处于水平放置或者竖直放置的情形。首先，讨论最大线段长度不超过传感器感应半径两倍的特殊情形，由于该问题是NP-困难的，我们主要从近似算法的角度来求解问题：利用平面分割的思想，设计了一个性能比为18、时间复杂度为(n log n)（n为线段数量）的多项式时间近似算法。其次，利用Java语言编程完成了算法仿真和稳定性检验，以图像形式形象地展示了算法结果，多组数据显示该算法基本稳定。最后，对该问题的一般情形进行了初步探讨。
　　第二类问题——点覆盖问题，重点考虑传感器部署位置不能越过某一条直线的情形（受地理环境或者其他因素的影响，传感器的部署位置可能存在一些禁区）。由于该问题也是NP-困难的，我们设计了一个性能比为2、时间复杂度为2(n)（n为点的数量）的多项式时间近似算法，且有实例表明该性能比是紧的。同样地，该部分也利用Java语言编程完成了算法仿真和稳定性检验，得到了多组算法解与最优解的图像示例，计算结果表明该算法也较为稳定。
　　第三部分，论文的总结和拓展。最后对论文主要内容作了总结，并展望进一步的研究方向。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1图论的相关概念

1.2组合优化问题

1.3 算法与时间复杂性

1.4 问题复杂性分类

1.5 近似算法和启发式算法

1.6 论文的组织结构

2无线传感器网络的相关介绍

2.1无线传感器网络

2.2无线传感器网络中的覆盖问题

3 无线传感器网络中线段覆盖问题的算法研究

3.1问题描述

3.2算法设计与分析

3.3算法仿真和稳定性检验

3.4问题延伸

3.5本章小结

4 无线网络中点覆盖问题的算法研究

4.1问题描述

4.2算法设计与分析

4.3算法仿真和稳定性检验

4.4本章小结

5 总结与展望

5.1总结

5.2问题展望

致谢

参考文献

附录1--线段覆盖算法的主要程序代码

附录2--点覆盖算法的主要程序代码

附 录3