Optimization of wireless sensor networks deployment with coverage and connectivity constraints

Sourour Elloumi (), Olivier Hudry (), Estel Marie (), Agathe Martin (), Agnès Plateau () and Stéphane Rovedakis ()
Additional contact information
Sourour Elloumi: ENSTA-ParisTech/UMA
Olivier Hudry: Télécom-ParisTech/LTCI
Estel Marie: Conservatoire National des Arts et Métiers/CEDRIC
Agathe Martin: Conservatoire National des Arts et Métiers/CEDRIC
Agnès Plateau: Conservatoire National des Arts et Métiers/CEDRIC
Stéphane Rovedakis: Conservatoire National des Arts et Métiers/CEDRIC

Annals of Operations Research, 2021, vol. 298, issue 1, No 10, 183-206

Abstract: Abstract Wireless sensor networks have been widely deployed in the last decades to provide various services, like environmental monitoring or object tracking. Such a network is composed of a set of sensor nodes which are used to sense and transmit collected information to a base station. To achieve this goal, two properties have to be guaranteed: (i) the sensor nodes must be placed such that the whole environment of interest (represented by a set of targets) is covered, and (ii) every sensor node can transmit its data to the base station (through other sensor nodes). In this paper, we consider the Minimum Connected k-Coverage (MCkC) problem, where a positive integer $$k \ge 1$$ k ≥ 1 defines the coverage multiplicity of the targets. We propose two mathematical programming formulations for the MCkC problem on square grid graphs and random graphs. We compare them to a recent model proposed by Rebai et al. (Comput Oper Res 59:11–21, 2015). We use a standard mixed integer linear programming solver to solve several instances with different formulations. In our results, we point out the quality of the LP-bound of each formulation as well as the total CPU time or the proportion of solved instances to optimality within a given CPU time.

Keywords: Wireless sensor networks; Grid networks; Random graphs; Sensor deployment; Minimum connected k-coverage; Mixed integer linear programming; Formulations (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-018-2943-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:298:y:2021:i:1:d:10.1007_s10479-018-2943-7

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-018-2943-7

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().