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-based approaches for the design of energy efficient wireless sensor networks

Bunch of WSN presentations at the ROADEF'2014 conference

This year, the OR-Group was heavily present at the French national OR conference (ROADEF'2014). In the domain of WSN, we have made several presentations in the field of Wireless Sensor Networks.

Fabian Castaño presented our work on WSN at ROADEF 2013

The problem presented here is "Maximizing network lifetime problem with connectivity constraint and QoS". Our method develops a matheuristics algorithm involving a column generation approach and two metaheuristics (GRASP and VNS). The combination has led to the best published results on a 100% QoS and achieved also the best results when the quality is lower.

The presentation can be downloaded here.

André Rossi presented our work on directional sensors for WSN at ROADEF 2013

In this work we address two versions of a lifetime maximization problem for target coverage with wireless directional sensor networks. The sensors used in these networks have a maximum sensing range and a limited sensing angle. In the first problem version, predefined sensing directions are assumed to be given, whereas sensing directions can be freely devised in the second problem version.

Wireless sensor networks presented at GOR-WS

On March 30 to April 1st, 2011, the Helmut-Schmidt-Universität, Hamburg, organized the Gemeinsamer Workshop der GOR-Arbeitsgruppen "Entscheidungstheorie und -praxis" und "Wirtschaftsinformatik". Marc Sevaux gave a presentation on the 1st of April on the Cover Scheduling Problem in Wireless Sensor Networks. You can download the presentation here.

Seminar on WSN at HSU

Just after his arrival at HSU, Marc Sevaux was asked to participate in the seminar cycle "Computaional logistics". He has presented a common work with André Rossi and Alok Singh on "Wireless Sensor Network: new optimization tools for a better efficiency".