Geodesic
Exact and heuristic approaches for the maximum lifetime problem in sensor networks with coverage and connectivity constraints
Carrabs, Francesco1  ; Cerulli, Raffaele1 ; D’Ambrosio, Ciriaco1  ; Raiconi, Andrea1 
1 Department of Mathematics, University of Salerno, via Giovanni Paolo II, 132, 84084 Fisciano, Italy.
RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 3, pp. 607-625

Voir la notice de l'article provenant de la source Numdam

The aim of the Connected Maximum Lifetime Problem is to define a schedule for the activation intervals of the sensors deployed inside a region of interest, such that at all times the activated sensors can monitor a set of interesting target locations and route the collected information to a central base station, while maximizing the total amount of time over which the sensor network can be operational. Complete or partial coverage of the targets are taken into account. To optimally solve the problem, we propose a column generation approach which makes use of an appropriately designed genetic algorithm to overcome the difficulty of solving the subproblem to optimality in each iteration. Moreover, we also devise a heuristic by stopping the column generation procedure as soon as the columns found by the genetic algorithm do not improve the incumbent solution. Comparisons with previous approaches proposed in the literature show our algorithms to be highly competitive, both in terms of solution quality and computational time.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2017032
Classification : 90C05, 90C06, 90C59
Keywords: Maximum lifetime, wireless sensor network, column generation, genetic algorithm, steiner tree, partial coverage

Carrabs, Francesco 1 ; Cerulli, Raffaele 1 ; D’Ambrosio, Ciriaco 1 ; Raiconi, Andrea 1

1 Department of Mathematics, University of Salerno, via Giovanni Paolo II, 132, 84084 Fisciano, Italy. 
@article{RO_2017__51_3_607_0,
     author = {Carrabs, Francesco and Cerulli, Raffaele and D{\textquoteright}Ambrosio, Ciriaco and Raiconi, Andrea},
     title = {Exact and heuristic approaches for the maximum lifetime problem in sensor networks with coverage and connectivity constraints},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {607--625},
     publisher = {EDP-Sciences},
     volume = {51},
     number = {3},
     year = {2017},
     doi = {10.1051/ro/2017032},
     mrnumber = {3880515},
     zbl = {1387.90123},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2017032/}
}
TY  - JOUR
AU  - Carrabs, Francesco
AU  - Cerulli, Raffaele
AU  - D’Ambrosio, Ciriaco
AU  - Raiconi, Andrea
TI  - Exact and heuristic approaches for the maximum lifetime problem in sensor networks with coverage and connectivity constraints
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2017
SP  - 607
EP  - 625
VL  - 51
IS  - 3
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ro/2017032/
DO  - 10.1051/ro/2017032
LA  - en
ID  - RO_2017__51_3_607_0
ER  - 
%0 Journal Article
%A Carrabs, Francesco
%A Cerulli, Raffaele
%A D’Ambrosio, Ciriaco
%A Raiconi, Andrea
%T Exact and heuristic approaches for the maximum lifetime problem in sensor networks with coverage and connectivity constraints
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2017
%P 607-625
%V 51
%N 3
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ro/2017032/
%R 10.1051/ro/2017032
%G en
%F RO_2017__51_3_607_0
Carrabs, Francesco; Cerulli, Raffaele; D’Ambrosio, Ciriaco; Raiconi, Andrea. Exact and heuristic approaches for the maximum lifetime problem in sensor networks with coverage and connectivity constraints. RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 3, pp. 607-625. doi: 10.1051/ro/2017032

Cité par Sources :