Skip to Main content Skip to Navigation
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 <>
Submitted on : Monday, April 5, 2021 - 10:35:26 AM
Last modification on : Tuesday, April 20, 2021 - 10:20:33 AM


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


  • HAL Id : hal-03189488, version 1


Sourour Elloumi, Olivier Hudry, E. Marie, A. Martin, Agnès Plateau, et al.. Optimization of wireless sensor networks deployment with coverage and connectivity constraints. Annals of Operations Research, Springer Verlag, 2021, 298 (1-2), pp.183-206. ⟨hal-03189488⟩



Record views


Files downloads