You are here

Wireless sensor networks

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

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.

Solutions

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.

Video

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.

Related presentations

Ahcène Bounceur has presented his last research at GDR-RO

At the occasion of the GDR-RO meeting dedicated to electronic activities, Dr. Ahcène Bounceur has presented his last research topic. The title is related to "PHFP : Polygon Hull Finding Problem & PHVP : Polygon Hull Visiting Problem" which is an important activity in the field of Wireless Sensor Networks. The presentation has been given in French for the French research group.

Marc Sevaux was plenary speaker at ORBEL 2015

ORBEL, despite its small size in a well recognized conference in OR in Europe. Marc Sevaux was invited to give a talk as a plenary speaker. This presentation was dedicated to a general presentation on Wireless Sensor Networks, and more specifically, a survey on maximizing lifetime in sensor coverage problems.

Fabian Castaño has defended his PhD thesis with success

On October 1st, Fabian Castaño has defended his PhD thesis with success. His presentation lasted for 45 minutes and has been followed by 1h of hard questions where Fabian was able to answer with precision. The jury deliberated for a short time and concluded that Fabian deserved the title of PhD. Please call him "Doctor Fabian Castaño" from now on ;-)

Title: Decomposition