无线传感器网络是由具备感知、数据处理、存储和数据传输的传感器节点自组织而形成的无线网络,在军用和民用领域有着广泛的应用前景。覆盖问题是无线传感器网络的重要问题之一,它是反映无线传感器网络服务质量的一项重要性能指标。由于受到能量的约束,覆盖问题的主要任务是找出较小的覆盖集,并使这些集合能独立完成所需要的任务,而其它节点则处于低功耗的休眠状态。目前,点覆盖问题研究一般着重于设计集中式优化算法,这些算法对无线传感器网络的实际应用存在一定的局限性。本文以布尔感知模型为基础,通过发掘点覆盖问题中应用场景,研究分布式、集中式以及集中式算法的局部化处理算法。针对点覆盖问题中目标点分布对覆盖集连通性的制约,本文也系统地研究了覆盖连通问题,并提出了相应的连通算法。本文首先讨论了无线传感器网络节点冗余覆盖调度机制,进而提出了一种分布式算法SRCA。该算法通过检测网络中的覆盖冗余节点,让部分冗余节点休眠,从而降低网络的冗余覆盖程度。SRCA算法在保证网络初始覆盖的同时,能够有效地降低系统能量消耗,延长网络的生存时间。面向无线传感器网络的一种应用场景,本文提出了一种基于遗传算法的传感器节点调度的一种集中式近似算法—NSAGA算法。该算法期望利用遗传算法的种群特性,求解无线传感器网络覆盖子集。该算法每次迭代可以同时产生多个满足条件的覆盖子集,还可以根据覆盖要求改变约束条件,满足不同的应用场景。针对目前点覆盖调度的算法一般都将覆盖问题转化为数学规划模型,然后采用集中式算法近似算法求解。虽然这种求解方式比分布式算法的精度高,但不适合大规模无线传感器网络。为此,本文提出了一种将集中式算法进行局部化的思想,并提出了一种分布式LCACA算法。该算法首先选举局部中心节点将整个网络划分成多个规模较小的网络。然后在每个划分的网络中再运行集中式算法,完成传感器节点的调度。而且,该算法还可以根据不同子区域的目标的覆盖要求,通过划分网络后,在每个划分的网络上运行不同的调度算法。一般点覆盖算法大多假设覆盖与连通是一致的,并没有考虑被监测的目标分布情况对网络连通性的影响。为此本文讨论了点覆盖与连通性的关系,提出了一种基于Steiner树集中式连通算法—CCAST算法。该算法首先将所有连通簇看成一个虚拟节点,然后构建加权通信图并调用已有构造Steiner树的算法挑选出Steiner点,使得所有的覆盖节点保持连通。接着,本文又进一步提出了一种分布式连通算法DCAVIS。该算法首先构造虚拟独立集,然后寻找使覆盖集成为连通集的中继节点。DCAVIS算法为解决点覆盖连通问题可提供了一种分布式近似求解算法,同时可以有效延长无线传感器网络的生存时间。综上所述,本文以无线传感器网络点覆盖问题为主要目标,从分布式、集中式以及集中式算法的局部化三方面研究了点覆盖算法,其中,集中式算法的局部化还可做为以后的工作进一步研究。