Le jury est constitué de :Rapporteurs :M. Ali Ridha MAHJOUB. Professeur des Universités, Université Paris Dauphine, LAMSADE.M. Arnaud PECHER. Professeur des Universités, Université Bordeaux 1. LaBRIExaminateurs :M. Mohamed DIDI BIHA. Professeur des Universités, Université de Caen. LAMNO CNRS UMR 6139.M. Alain QUILLIOT. Professeur des Universités. Université Blaise Pascal, LIMOS.M. Alexandre GUITTON. Maître de conférences HDR. Université Blaise Pascal, LIMOS.Directrice de thèse :Mme Fatiha BENDALI-MAILFERT. Maître de conférences HDR. Université Blaise Pascal, LIMOS.Codirecteur :M. Jean MAILFERT. Maître de conférences. Université d’Auvergne, LIMOS.Résumé :Dans ce travail, nous nous intéressons à une topologie pour les réseaux de capteurs sans fil.Un réseau de capteurs sans fil peut être modélisé comme un graphe non orienté $G = (V, E)$.Chaque sommet de $ V $ représente un capteur et une arête $ e = {u, v } $ dans $ E $ indique une transmission directe possible entre deux capteurs $ u $ et $ v $.Contrairement aux dispositifs filaires, les capteurs sans fil ne sont pas a priori agencé en réseau. Une topologie doit être créée en sélectionnant des nœuds « dominants » qui vont gérer les transmissions. Les architectures qui ont été examinées dans la littérature reposent essentiellement sur les ensembles dominants connexes et les ensembles dominants faiblement connexes.Cette étude est consacrée aux ensembles indépendants faiblement connexes.Un indépendant $S\subset V$ est dit faiblement connexe si le graphe$G_{S}=(V, [S,V\backslash S])$ est connexe, où $[S,V\backslash S]$ est l’ensemble des arêtes $e=\{u, v\}$ de $E$ avec $u\in S$ et $v\in V\backslash S$.Une topologie basée sur les ensembles faiblement connexes permet de partitionner l’ensemble des capteurs en trois groupes, les esclaves, les maîtres et les intermédiaires.Les premiers effectuent les mesures, les seconds rassemblent les données collectées et les troisièmes assurent les communications inter-groupes.Nous donnons d’abord quelques propriétés de cette structure combinatoire lorsque le graphe non orienté $G$ est connexe.Puis nous proposons des résultats de complexité pour le problème de la recherche de l’indépendant faiblement connexe de cardinalité minimale (MWCISP).Nous décrivons également un algorithme d’énumération exact de complexité $O^{*}(1.4655^{|V|})$ pour le MWCISP. Des tests numériques de cette procédure exacte sont présentés.Nous formulons ensuite le $MWCISP$ comme un programme linéaire en nombres entiers.Le polytope associé aux solutions de ce problème est complètement caractérisé lorsque $G$ est un cycle impair. Nous étudions des opérations de composition de graphes et leurs conséquences polyédrales.Nous introduisons des inégalités valides notamment les contraintes dites de multibord.Par la suite, nous développons un algorithme de coupes et branchement sous CPLEX pour résoudre ce problème en utilisant des heuristiques pour la séparation de nos familles de contraintes. Des résultats expérimentaux de ce programme sont exposés.
Aller au contenu