论文部分内容阅读
无线传感器网络是由低成本、低功耗、具备感知、数据处理、存储和无线通信能力的微型传感器节点通过自组织方式形成的网络。网络覆盖和能量消耗是无线传感器网络的两个核心问题。网络覆盖决定了无线传感器网络对物理世界的监测能力，能量消耗则决定了无线传感器网络的生存时间。网络覆盖与能量消耗密切相关，节点部署则是影响网络覆盖的重要因素。本文主要针对无线传感器网络的能量高效覆盖控制问题和传感器节点的自部署问题进行了深入研究。 本文首先提出了一种能够保持网络覆盖质量的分布式节点调度机制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问题提供了一种分布式近似