【作者】 蒋杰；

【导师】 窦文华；

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

【摘要】 无线传感器网络是由低成本、低功耗、具备感知、数据处理、存储和无线通信能力的微型传感器节点通过自组织方式形成的网络。网络覆盖和能量消耗是无线传感器网络的两个核心问题。网络覆盖决定了无线传感器网络对物理世界的监测能力，能量消耗则决定了无线传感器网络的生存时间。网络覆盖与能量消耗密切相关，节点部署则是影响网络覆盖的重要因素。本文主要针对无线传感器网络的能量高效覆盖控制问题和传感器节点的自部署问题进行了深入研究。 本文首先提出了一种能够保持网络覆盖质量的分布式节点调度机制CPNSS。CPNSS机制通过减少任意时刻网络中的活跃节点数来降低网络覆盖冗余，可以有效地减少冗余数据传输导致的能量消耗，延长无线传感器网络的生存时间。结合基于(α，β)-边界覆盖的冗余节点判别方法和基于节点优先级的循环依赖解析方法，CPNSS机制能够在关闭部分冗余节点后保持网络的覆盖质量。仿真实验表明，CPNSS机制不但性能优于PEAS协议，而且能比SITE算法更有效地延长无线传感器网络的FDL生存时间和α-CL生存时间。 本文接着讨论了无线传感器网络的能量高效自组织问题。状态查询是无线传感器网络中一类非常重要而又频繁的操作。使用尽可能少的活跃节点来响应用户的查询请求，可以有效地延长无线传感器网络的生存时间。本文将计算能够完全覆盖目标区域并保证网络连通性的最小节点集的问题归结为MCCS问题，并提出了一种求解MCCS问题的集中式近似算法。该近似算法分两个阶段构造近似最小连通覆盖集。首先使用CVT算法构造目标区域的近似最小覆盖集。当节点通信半径大于等于2倍感知半径时，CVT算法构造的覆盖集是连通的。针对通信半径小于2倍感知半径的情况，本文提出了一种基于最小生成树(MST)的连通算法，以确保覆盖集的连通性。理论分析和仿真实验表明，CVT(+MST)算法在时间复杂性以及连通覆盖集的大小等方面均优于已有的Greedy算法。 考虑到微型传感器节点固有的易失效以及能量有限等特性，本文进一步讨论了无线传感器网络具有容错特性的能量高效自组织问题。如何使用尽可能少的活跃节点来保证目标区域的κ-覆盖以及通信网络的κ-连通是一个NP难问题。本文将上述问题归结为MKCCS问题，并提出了一种基于自剪枝思想的算法框架。在该算法框架中，可以根据应用需要分别指定连通度要求和覆盖度要求。任意能够检测κ-连通冗余或κ-覆盖冗余节点的分布式算法均可应用在该自剪枝框架中。同时，本文提出了一种基于κ-阶Voronoi划分的κ-覆盖冗余节点检测算法。并在此基础上，提出了求解MKCCS问题的分布式近似算法DSPA。仿真实验表明，DSPA算法能够可靠地构造κ-连通κ-覆盖集。由于MCCS问题是MKCCS问题在κ=1时的特例，DSPA算法同时为MCCS问题提供了一种分布式近似更多还原

【Abstract】 Wireless sensor networks (WSNs) consist of low-cost, low-power tiny sensor nodes that can communicate with each other to perform sensing and data processing cooperatively. Network coverage and energy consumption are two primary problems in wireless sensor networks. The performance of a sensor network depends to a large extent on the sensor field coverage and its lifetime is determined by its energy consumption. While network coverage is closely related to network energy consumption, the deployment of sensor nodes is an important factor affecting the coverage of a sensor network. This thesis focuses on energy-efficient coverage control in wireless sensor networks and movement-assisted self-deployment of sensor nodes. It presents methods for energy-efficient node scheduling and self-organization, as well as techniques for coverage-centric sensor node deployment.The thesis first presents a localized, distributed coverage-preserving node scheduling scheme (CPNSS) to improve the energy efficiency and prolong the network lifetime of densely deployed random sensor networks. In such a wireless sensor network, the inherent node coverage redundancy will cause a large amount of unnecessary energy waste, which is harmful to the network lifetime. The CPNSS scheme tries to extend the network lifetime by deactivating some unnecessary redundant sensor nodes, thus reducing the number of active sensor nodes and the coverage redundancy. Combining the (α,β)-perimeter coverage based rule for detecting coverage redundancy and the node priority based method for resolving cyclic dependency, the CPNSS scheme can preserve the network coverage after turning off unnecessary sensor nodes. Extensive simulation results show that the CPNSS scheme can not only outperform the PEAS protocol, but also achieve longer FDL lifetime and α-CL lifetime of sensor network than the SITE algorithm.The thesis next considers the energy-efficient self-organization of wireless sensor networks. Query execution is a kind of frequent and important operation in wireless sensor networks. One promising energy-saving technique is to activate a subset of sensor nodes to respond the specific user query, while these active sensor nodes must cover the target region completely and form a connected communication network. The problem of calculating the minimum number of sensor nodes satisfying the coverage and connectivity requirements simultaneously is formulated as a minimal connected cover set (MCCS) problem, which is NP hard. A centralized approximation algorithm is proposed for the MCCS problem in this thesis. This algorithm tries to solve the MCCS problem by constructing the near optimal cover set firstly and then making the cover set connected if necessary. A centralized, Voronoi tessellation (CVT) based algorithm is proposed to更多还原