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