Home // SENSORCOMM 2011, The Fifth International Conference on Sensor Technologies and Applications // View article

A Column Generation based Heuristic for Maximum Lifetime Coverage in Wireless Sensor Networks

Authors:
Karine Deschinkel

Keywords: target coverage; wireless sensor networks; centralised method; column generation;

Abstract:
Several studies in recent years have considered many strategies for increasing sensor network lifetime. We focus on a centralised management scheme where a large number of sensors are randomly deployed in a region of interest to monitor a set of targets and we propose an adaptive scheduling by dividing sensors into non-disjoint cover sets, each cover set being active in different period of time. In this paper, we design a column generation (CG) method based heuristic for efficiently solving the maximum lifetime coverage problem. We first model the problem with a linear programming (LP) formulation for non-disjoint cover sets where the objective is to maximise the sum of activation times of cover sets, with respect the sensor's battery lifetime. As the number of cover sets may be exponential to the number of sensors and targets, an initial set of cover sets is constructed and other cover sets are generated through the resolution of an auxiliary problem formulated as a integer programming (IP) problem. This problem is either solved at optimality by standard branch-and-bound or solved sub-optimally by a heuristic. Simulation results show the efficiency of the proposed heuristic which provides near optimal solutions while saving computational time.

Pages: 209 to 214

Copyright: Copyright (c) IARIA, 2011

Publication date: August 21, 2011

Published in: conference

ISSN: 2308-4405

ISBN: 978-1-61208-144-1

Location: Nice/Saint Laurent du Var, France

Dates: from August 21, 2011 to August 27, 2011