【作者】 李小龙；

【导师】 林亚平；

【作者基本信息】 湖南大学 ， 计算机应用技术， 2008， 博士

【摘要】 无线传感器网络是由大量计算、通信及存储能力有限的传感器节点组成的特殊Ad-hoc网络,在军事和民用领域具有广泛的应用,是目前一个非常活跃的研究领域。覆盖问题是无线传感器网络中的一个核心问题。网络覆盖反映了网络所能提供的感知服务质量,可以使无线传感器网络的空间资源得到优化分配。节点调度和密度控制是减少能量消耗、延长网络生存时间的有效手段。本文针对无线传感器网络的覆盖问题展开了深入地研究,目标是在满足服务质量的前提下,节约节点能量,最大化网络生命周期。主要工作包括以下几个方面:(1)针对高密度、大规模的传感器网络,首先讨论了活跃节点的节点分布问题,指出了在局部小区域节点分布过于稠密和过于稀疏对传感器网络性能造成的影响。建立了传感器网络极大相似分布模型,用来量化传感器网络分组之间的节点分布均匀程度。证明了传感器网络极大相似分布问题属于NP-Hard问题,提出了两种近似求解算法,即基于分组的集中式和分布式节点调度覆盖算法,并给出了传感器网络为随机分布时,采用分组调度时平均覆盖率的理论上界值。对于合适范围的分组数,基于分组的节点调度覆盖算法能使各个组内的传感器节点较为均匀地分布在目标区域,得到的平均覆盖率接近理论上界值。(2)由于硬件成本、能耗以及误差范围等因素的限制,现有的定位技术难以满足传感器网络中覆盖算法的要求。提出了一种不依赖节点位置信息的节点调度覆盖算法LCSS。建立了参照节点和虚拟坐标的概念,并给出了选择参照节点以及生成节点虚拟坐标的方法。对于不同的传感半径、通信半径以及应用要求,给出了参照节点个数的最小临界值。分析表明当网络中存在一定个数的参照节点时,节点的虚拟坐标能够代替节点的绝对坐标,并指出了它的适用范围。理论分析和仿真实验表明,LCSS算法对节点的时钟异步有很好的鲁棒性。和其它的与节点位置无关、基于分组的覆盖方案相比,不依赖节点位置信息的节点调度覆盖算法有更好的覆盖性能,组内节点分布更加均匀。(3)对于传感器网络在军事监测等方面的应用,目标区域内若存在着盲点区域可能导致极其严重的后果,要求任意时刻传感器网络能够完全覆盖目标区域,并保证网络的连通性。在保证完全覆盖和网络连通的前提下,设计了一种基于网格的密度控制算法GDCA。仿真实验表明,和其它连通覆盖集求解算法相比,GDCA算法能够获得更小的连通覆盖集。且这种算法属于分布式算法,具有良好的扩展性,节点的传感区域可为任意凸形区域,更符合实际情况。(4)当传感器网络应用于灾难援助等领域,要求传感器网络对空间数据查询消息进行快速的回应,以帮助进行灾难救援。而快速的生成连通覆盖集是传感器网络快速回应空间数据查询消息的前提。从快速回应用户或者其他指令中心发出的空间数据查询的应用需求出发,讨论了如何快速有效的构造查询区域的连通覆盖集问题,并提出了一种基于正方形的连通覆盖集快速实现算法SFAMCCS。通过将查询区域按一定尺寸的正方形剖分,节点利用临近节点的位置及覆盖的格点等信息构造查询区域的连通覆盖集。理论分析和仿真实验表明,SFAMCCS算法通过节点协作的方式,在较短的时间内得到的连通覆盖集大小可与已有集中式算法相当,与类似的其他算法相比,在运行时间和连通覆盖集大小等方面具有更优的性能。(5)在节点不能获取准确位置信息的条件下,如何进行节点调度以满足传感器网络长时间充分均匀的覆盖目标区域并确保网络连通,是当前具有挑战性的问题。在覆盖算法LCSS的基础上,本文提出了基于虚拟坐标的节点调度方案SSVC。SSVC方案通过将传感器节点中的某一些节点划分到几个不同的分组,保证了各个分组的连通。算法分析和仿真实验表明,本文提出的方案在覆盖率、维持分组连通时额外加入到分组内的节点个数,以及网络生存时间等性能上均优于与节点位置无关的节点随机调度协议。更多还原

【Abstract】 Wireless sensor networks have been the targets of active research in the recent past due to their military and civil applications. One of the most fundamental problems in wireless sensor networks is coverage problem, which reflects how well a region is apperceived. The coverage control theories and algorithms can result in network resources’optimial allocation. Recent research has found that node scheduling and density control are able to save significant energy and prolong network lifetime. This dissertation focuses on the coverage problem in wireless sensor networks, aiming at saving network energy and prolonging network lifetime under the condition of meeting service requirements. The main works are as follows:(1) For large-scale dense sensor networks, we discuss the active node distribution problem, and analyse the effect of node being sparse in some sub-regions and nodes being dense in other sub-regions on network performance. We set up a maximum similarity distribution model, which quantifies the degree of distribution similarity among subsets, and prove that it is equivalent to an NP-hard problem. We propose two approximation algorithms, the subset-based coverage-preserving centralized scheduling algorithm and the subset-based coverage-preserving distributed scheduling algorithm. In addition, this paper presents the analytical results for the theoretical upper bound of average coverage rate while nodes are randomly distributed over the target region. The experimental simulations demonstrate that the algorithms have the ability that sensor nodes in each subset are rather uniformly distributed over the target area, and available coverage rate approaches the upper bound.(2) Due to the constraints of hardware cost, energy consuming, and unavoidable error, existing localization mechanisms are difficult to make low-cost nodes obtain accurate location information. Without accurate location information, we propose a location-indepent coverage-preserving node scheduling scheme (LCSS). We give two new definitions, reference node and virtual coordinate, and introduce how to select reference nodes and construct the virtual coordinates of nodes in a sensor network. Analytical results illustrate that the virtual coordinate of a node could be instead of its physical coordinate of the node when there are a certain number of reference nodes. Besides, we point out the suitable domain for the virtual coordinate, present the analytical results to disclose the relationship between the number of reference nodes, sensing range and communication range of nodes. The theory analysis and simulation demonstrate LCSS outperforms other subset-based location-indepent coverage algorithms with respect to coverage performance, and more uniformly distributed subsets are obtained under LCSS.(3) For one sensor network utilized in the scenario of military suiveillance, if there is some blind region over a target region, it will might results in extremely severe consequences. In the scenario, the sensor network is required to completely cover the target region and remain connected at any time. Under the premise of complete coverage and guaranteed connectivity, we propose a grid-based density control algorithm (GDCA). Experimental simulations show that GDCA outperforms other algorithm for minimum connected cover set problem in terms of the size of constructed connected cover set. GDCA is totally distributed. In addition, the algorithm is applicable to scenarios where the sensing area of a sensor does not follow the unit disk model, but have any convex area.(4) Recent years has seen that sensor networks must support real-time spatial data query. Representive examples include emergence response and disaster aid. Quickly constructing connected cover set is the premise that sensor networks can respond in time to spatial data query. Considering this kind of application requirements,it deserves further study how to quickly construct the connected cover set of a query region. We propose a square tessellation based fast algorithm for minimum connected cover set problem (SFAMCCS). After making tessellation by a certain size of squares, nodes utililze their local information, including the location of neighboring nodes and their covered grid set, to construct the connected cover set of the query region. Experimental simulations show, compared to other similar algorithms, SFAMCCS has better joint performance in terms of the algorithm runtime and the size of the connected cover set.(5) Without accurate location information, it is challenging to schedule sensor nodes to meet both constraints of sufficient uniform sensing coverage, network connectivity and long network lifetime. Based on the LCSS, we propose a node scheduling scheme based on virtual coordinate for sensor networks (SSVC). SSVC is composed of two algorithms: a coverage algorithm LCSS, for maintaining sensing coverage and a connection algorithm for constructing a connected network. By assigning some nodes into several different subsets, the connection algorithm can guarantee network connectivity. Without the location information, this scheduling scheme not only has the ability that makes sensor nodes in subsets more uniformly distributed in the target region than other subset-based schemes, but also guarantees each subset to be connected. The simulation results demonstrate that SSVC outperforms the randomized sensor scheduling scheme with guaranteed connectivity (RSGC) on the coverage quality and network lifetime, as well as the number of external nodes when maintaining subsets to be connective.更多还原