Déploiement optimal d'un réseau de capteurs sous des contraintes de couverture et de connectivité / Sylvain Marie ; sous la direction de Sourour Elloumi et de Olivier Hudry

Date :

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : français / French

Catalogue Worldcat

Réseaux de capteurs (technologie) -- Modèles mathématiques

Graphes, Théorie des

Programmation (mathématiques) -- Informatique

Classification Dewey : 004.6

Classification Dewey : 519.7

Classification Dewey : 621.382 1

Elloumi, Sourour (19..-.... ; chercheuse en informatique) (Directeur de thèse / thesis advisor)

Hudry, Olivier (Directeur de thèse / thesis advisor)

Didi Biha, Mohamed (Président du jury de soutenance / praeses)

Gabrel, Virginie (1967-…) (Rapporteur de la thèse / thesis reporter)

Lobstein, Antoine (1958-....) (Rapporteur de la thèse / thesis reporter)

Chu, Feng (1965-....) (Membre du jury / opponent)

Plateau, Agnès (19..-....) (Membre du jury / opponent)

Rovedakis, Stéphane (Membre du jury / opponent)

Conservatoire national des arts et métiers (France) (Organisme de soutenance / degree-grantor)

École doctorale Informatique, télécommunications et électronique de Paris (Ecole doctorale associée à la thèse / doctoral school)

Centre d'études et de recherche en informatique et communications (Paris) (Laboratoire associé à la thèse / thesis associated laboratory)

Télécom Paris (Palaiseau) (Autre partenaire associé à la thèse / thesis associated third party)

Résumé / Abstract : L'objet de cette thèse sur les réseaux de capteurs est l'étude du déploiement minimal de capteurs lorsque ceux-ci doivent couvrir un ensemble discret de cibles plutôt que des superficies. Après la présentation des caractéristiques d'un réseau de capteurs, et l'intérêt d'un déploiement minimal, nous en proposons une modélisation en théorie des graphes. Nous présentons ensuite un état de l'art décrivant certaines techniques de résolution par la programmation mathématique de diverses problématiques dans ce type de réseau. Nous utilisons plusieurs programmes linéaires en variables mixtes afin de résoudre le problème du déploiement minimal des capteurs sous des contraintes de couverture de toutes les cibles et de connectivité des capteurs entre eux. Finalement, nous concevons une nouvelle heuristique de calcul de placement de capteurs lorsque les cibles sont placées sur une grille à motif carré et nous conjecturons que cette heuristique retourne une solution optimale dans tous les cas.

Résumé / Abstract : The objectif of this thesis on wireless sensor networks is to study the deployment of a minimal number of sensors to cover specific targets instead of continuous areas. After a presentation of the characteristics of wireless sensor networks, and after justifying the interest of an optimal sensor deployment, we propose a graph-theory based model for wireless sensor networks. We then present a state of the art describing various mathematical programming models and resolution techniques regarding a number of optimization problems in such networks. We formulate several Mixed Integer Linear programs to solve the optimal sensor deployment problem under contraints related to the coverage of all targets and connectivity between sensors. Finally, we conceive a new heuristic for sensor placement when targets are placed in a square grid graph, and we conjecture that this heuristic returns an optimal solution in all cases.