Research On Target Coverage In Wireless Sensor Networks

Wireless sensor networks promise to usher in a new era of revolutionary computing and ultimately prove beneficial to areas as diverse as national security, surveillance, environmental monitoring, agriculture and healthcare. With the ability of interaction between physical world and digital world, wireless sensor networks can help people efficiently cover targets, gather information and react accordingly, especially in real-time target monitoring applications like forest monitoring or hostile territorial area coverage. However, target coverage problem, the core problem of these systems, remains a quite challenge due to lack of theoretic analysis. This jeopardizes the usage of WSNs in real-world systems. To fill in the blank, this thesis aims to design a general optimization architecture that can be applied to a set of similar target monitoring problems. Major contributions are listed as following,(1) The QoS-aware stationary target coverage problem is proposed and two theoretic results have been achieved. One is a lifetime upper bound developed based on relaxation techniques, in order to establish a benchmark for other algorithms. The other is an efficient column generation (CG) based approach, which has performance guarantee and outperforms heuristic and greed algorithms developed in previous literatures.Particularly, a linear programming based optimization is built via relaxation of coverage constraints, in order to achieve a polynomial time algorithm for the lifetime upper bound. This upper bound offers a benchmark for other algorithms. To conquer the problem complexity, a column generation based algorithm is proposed. The key idea is "divide-and-conquer". More specifically, by dividing the original complex optimization into two related sub problems, the problem can be optimally tackled by iteratively solving these two sub problems. The proposed algorithm outperforms other heuristic and greedy algorithm on this topic in terms of computational time and algorithm performance by bother simulations and theoretic analysis.(2)The real-time stationary target coverage problem is proposed and a cross-layer based efficient algorithm is developed. A column generation based algorithm is proposed to solve the optimization model.The objective is to maximize network lifetime while fulfilling diversified coverage constraints, i.e., different targets may require different sensing quality in terms of the number of transducers, sampling rate, sensing data rate, etc. Through extensive simulations, the effect of sampling rates, transmission energy consumption models, communication ranges, and sensing ranges on the lifetime are systematically studied. Several interesting insights have been revealed, which offered guidance when established real-world monitoring systems.Particularly, this chapter studies the coverage problem for heterogeneous wireless sensor networks where different targets need to be covered (sensed) by different types of wireless sensors running at possibly different sampling rates as well as different initial energy reserve. The objective is to maximize network lifetime while fulfilling diversified coverage constraints, i.e., different targets may require different sensing quality in terms of the number of transducers, sampling rate, sensing data rate, etc. The problem is particularly challenging since both connectivity and routing requirements should be considered.To conquer this combinational complexity, a cross-layer lifetime maximization problem has been formulated, which is general and allows unprecedented diversity in coverage requirements, sampling rates, transmission energy consumption models, communication ranges, and target sensing ranges. Furthermore, to efficiently solve the optimization problem, a column generation based approach is proposed, where a column corresponding to a feasible solution; the idea is to find a column with steepest ascent in lifetime, based on which we iteratively search for the solution of the maximum lifetime problem. To speed up the convergence rate, an initial solution is generated through a novel random selection algorithm.(3)The partial stationary target coverage problem is proposed. Based on the new coverage model, an optimal polynomial-time algorithm is developed. This part deals with the Partial Target Coverage (PTC) problem in wireless sensor networks with the objective of optimizing network lifetime, where stationary targets do not need to be under covered all the time, instead, a partial coverage (e.g. the coverage percentage is 80%) would satisfy system requirements. The most commonly used method in previous literatures on target coverage problem is to divide continuous time into discrete slots with different lengths, each of which is dominated by a subset of sensors while setting all the other sensors into sleep state to save energy. This method however is suffered from vital shortcomings such as highly computational complexity and no performance bound.It can be proved that with a novel and practical coverage model, the PTC problem can be optimally solved in polynomial time. First a linear programming formulation is built, which takes total time a sensor spends on covering some targets into consideration, in order to obtain a lifetime upper bound. Then, based on information derived in the previous formulation, a sensor assignment algorithm is developed to seek an optimal time table meeting the lifetime upper bound taking advantage of the new coverage model. A formal proof of optimality is given.The proposed algorithm is compared with a state-of-the-art algorithm:column generation approach and show that the proposed algorithm significantly outperforms in terms of computational time. Experiments have been conducted to study how different network parameters, like partial coverage requirement, number of sensor, number of targets and sensing range, affect network lifetime and several interesting insights have been offered.(4)The mobile targets tracking problem is proposed. A new prediction model is developed coupling with a two-layer communication protocol. To efficiently track moving objects in WSN, a novel prediction model has been built to predict the Potential Future Area (PFA) a target maybe presented via utilizing previously collected information, like moving direction, moving speed, etc. A two-step communication protocol has been proposed to ensure reliable and timely data delivery between the based station and sensor nodes. The key idea is clear:to save energy by turning on only sensor nodes in PFA. This scheme significantly outperforms other similar mechanisms from the aspects of total energy consumption and communication bandwidth requirement, proved by not only theoretical analysis but also simulation results.