Skip to Main content Skip to Navigation
New interface
Journal articles

Optimization of wireless sensor networks deployment with coverage and connectivity constraints

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 ≥ 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 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.
Complete list of metadata
Contributor : Olivier Hudry Connect in order to contact the contributor
Submitted on : Monday, April 5, 2021 - 10:35:26 AM
Last modification on : Wednesday, September 28, 2022 - 5:56:03 AM
Long-term archiving on: : Tuesday, July 6, 2021 - 6:02:35 PM


ANOR-CODIT_revision (1).pdf
Files produced by the author(s)



Sourour Elloumi, Olivier Hudry, Estel Marie, Agathe Martin, Agnès Plateau, et al.. Optimization of wireless sensor networks deployment with coverage and connectivity constraints. Annals of Operations Research, 2021, 298 (1-2), pp.183-206. ⟨10.1007/s10479-018-2943-7⟩. ⟨hal-03189488⟩



Record views


Files downloads