We have now a long experience in cover optimization for the wireless sensor network problem. This page presents an overview of the general problem. Please click on the links below to get more details, references and instances on the different problems.
Problems addressed in this project:
On this topic we solve different types of problems related to the Wireless Sensor Network area. The first part of our study concerns the generation of covers to solve the "Minimum Cover Breach problem with Bandwidth constraint" (MCBB). We are also able to address the "Maximum Network Lifetime under Bandwidth constraint" (MNLB). With our global framework, we can offer the decision makers a bunch of solutions that are non-dominated (with these two objectives).
Since we are generating non-disjoint covers (to be better in the two previous objectives), some of the targets might not be correctly covered over time. Hence we also address the "Wireless Sensor Network Cover Scheduling Problem" (WSN-CSP) which consists in minimizing the maximum duration of non-covered targets.
Exact and approximate approaches have been proposed for addressing wireless sensor network problems MCBB nd MNLB. They both rely on the combination of a column generation algorithm, for which the auxiliary problem is solved using genetic algorithm, and ILP as a last resort technique for generating covers, or for proving optimality.
For the problem WSN-CSP, we have developped a non-linear programming model (NLP), a mixed-integer linear programming model (MILP) but both cannot be used in practice because of their inner complexity. We then developp an efficient heuristic and a GA-based metaheuristic. Both method are compared with a lower bound to measure their efficiency.
Here we solve the Minimum Cover Breach with Bandwidth constraint (MCBB). The network is composed of n=50 sensors for covering m=30 targets in a 500x500 square area. Each sensor operates on a battery whose lifetime is 100, and has a sensing range of 150. The bandwidth constraint is set to 5 (a maximum of 5 sensors can be activated at a time). A target is said to be covered by a sensor if it is located within its sensing range.
A cover is a set of sensors that will be activated at the same time. The breach of a cover is the number of targets that are not covered by any sensor in the cover. The problem is to design covers so as to minimize the total breach (i.e. the number of uncovered targets during the network life time). The network lifetime is a given T0 (here T0=1000). Consequently, the optimal average breach over time is 5.6 uncovered targets.