Research On Coverage Algorithms In Wireless Sensor Networks

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.