QoS‐aware target coverage in wireless sensor networks
Authors:
Open Access
- 16 January 2009
- journal article
- research article
- Published by Wiley in Wireless Communications and Mobile Computing
- Vol. 9 (12) , 1645-1659
Abstract
Wireless sensor networks have emerged recently as an effective way of monitoring remote or inhospitable physical targets, which usually have different quality of service (QoS) constraints, i.e., different targets may need different sensing quality in terms of the number of transducers, sampling rate, etc. In this paper, we address the problem of optimizing network lifetime while capturing those diversified QoS coverage constraints in such surveillance sensor networks. We show that this problem belongs to NP‐complete class. We define a subset of sensors meeting QoS requirements as acoverage pattern, and if the full set of coverage patterns is given, we can mathematically formulate the problem. Directly solving this formulation however is difficult since number of coverage patterns may be exponential to number of sensors and targets. Hence, a column generation (CG)‐based approach is proposed to decompose the original formulation into two subproblems and solve them iteratively. Here a column corresponds to a feasible coverage pattern, and the idea is to find a column with steepest ascent in lifetime, based on which we iteratively search for the maximum lifetime solution. An initial feasible set of patterns is generated through a novel random selection algorithm (RSA), in order to launch our approach. Experimental data demonstrate that the proposed CG‐based approach is an efficient solution, even in a harsh environment. Simulation results also reveal the impact of different network parameters on network lifetime, giving certain guidance on designing and maintaining such surveillance sensor networks. Copyright © 2009 John Wiley & Sons, Ltd.Keywords
This publication has 15 references indexed in Scilit:
- Maximal lifetime scheduling for K to 1 sensor–target surveillance networksComputer Networks, 2006
- VigilNetACM Transactions on Sensor Networks, 2006
- Energy-efficient coverage problems in wireless ad-hoc sensor networksComputer Communications, 2006
- Improving Wireless Sensor Network Lifetime through Power Aware OrganizationWireless Networks, 2005
- A minimum cost heterogeneous sensor network with a lifetime constraintIEEE Transactions on Mobile Computing, 2005
- Energy-Efficient Connected Coverage of Discrete Targets in Wireless Sensor Networks2005
- Column Generation2005
- The coverage problem in a wireless sensor network2003
- On the capacity of hybrid wireless networks2003
- Global Optimization1996