Optimization of wireless sensor networks deployment with coverage and connectivity constraints - Equipe Mathématiques discrètes, codage et cryptographie Accéder directement au contenu
Article Dans Une Revue Annals of Operations Research Année : 2021

Optimization of wireless sensor networks deployment with coverage and connectivity constraints

Résumé

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.
Fichier principal
Vignette du fichier
ANOR-CODIT_revision (1).pdf (378.36 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03189488 , version 1 (05-04-2021)

Identifiants

Citer

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⟩
301 Consultations
260 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More