【作者】 张鼎兴；

【导师】 徐明；

【作者基本信息】 国防科学技术大学 ， 计算机科学与技术， 2009， 博士

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

【Abstract】 Wireless sensor networks are such kind of integrated wireless networks which perform sensoring, data processing, storage and delivering. There are wide applications for the networks in both military and civil affairs. The coverage problem is one of the important issues in wireless sensor networks and reflects the quality of service. With the energy constraint, one main requirement of the coverage problem is to find a small subset of sensor nodes such that this subset can independently perform the required tasks while other redundant nodes enter into the low energy sleep status.At present, researchers stress the central optimize algorithm which restrict practicality use to solve the point coverage problems. By exploring new application scenario in the point coverage issues, this dissertation aims to the point coverage problems to research the relevant algorithms based on Boolean sensoring model. Considering the restriction of the object distribution to the connectivity, this dissertation also studies the connected coverage problems to put forward a relevant algorithm.This dissertation first discusses the redundant nodes scheduling mechanism for wireless sensor networks. Furthermore, a distributed algorithm SRCA is put forward in the dissertation. This algorithm checks the redundant nodes in the network to make the redundant nodes sleep such that the redundant nodes are reduced obviously in the network. SRCA can effectively reduce the energy expense so to prolong the network lifetime.Toward an application scenario, this dissertation proposed a sensor node approximately scheduling algorithm NSAGA based on genetic algorithm. This algorithm utilizes the population characteristic to solve the coverage subset. NSAGA can not only produce a few of coverage subsets to satisfy the coverage requirements in an iterative but also suit to diverse application scenarios by changing the restriction according to the coverage requirement.Nowadays, the algorithms translate the point coverage problems into mathematic programming models, and then solve the mathematic programming by the central approximate algorithm. Although the method is of better precision, it is unsuitable for the large wireless sensor network. Therefore, this dissertation proposed a method to localize central algorithms, then a distributed algorithm LCACA is put forward. LCACA first elects the local central nodes to divide the network into a few of small scale subnets. Then, the central algorithm can be performed in these subnets. The algorithm can perform different scheduling algorithms in wireless sensor networks according to the sub-area coverage requirement.Since current point coverage algorithms which are proposed in case of coinciding the coverage with connectivity ignore the influence of the object distribution over connectivity. A central algorithm CCAST based on Steiner tree is proposed. CCAST first translates a connected cluster into a virtual node. Then, it constructs a weighted graph and calls current algorithm to pick out nodes which connect the network. Furthermore, a distributed algorithm DCAVIS is proposed. The algorithm first constructs a virtual independent set, and then finds out relay nodes.In summary, aiming at the point coverage issues, this dissertation discussed the point coverage problem in the distributed algorithm, central algorithm and the method to localize the central algorithm. The method to localize the central algorithm can be further exploited for future research.更多还原