en fr Weakly connected independent sets : algorithmic and polyhedral studies Lindépendant faiblement connexe : études algorithmiques et polyédrales Reportar como inadecuado




en fr Weakly connected independent sets : algorithmic and polyhedral studies Lindépendant faiblement connexe : études algorithmiques et polyédrales - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 LIMOS - Laboratoire d-Informatique, de Modélisation et d-optimisation des Systèmes 2 Laboratoire d-Informatique, de Modélisation et d-Optimisation des Systèmes

Abstract : In this work, we focus on a topology for Wireless Sensor Networks WSN. A wireless sensor network can be modeled as an undirected graph G = V,E. Each vertex of V represents a sensor and an edge e = {u, v} in E implies a direct transmission between the two sensors u and v. Unlike wired devices, wireless sensors are not a priori arranged in a network. Topology should be made by selecting some sensor as dominators nodes who manage transmissions. Architectures that have been studied in the literature are mainly based on connected dominating sets and weakly connected dominating sets.This study is devoted to weakly connected independent sets. An independent set S ⊂ V is said Weakly Connected if the graph GS = V, S, V \S is connected, where S, V \S is the set of edges with exactly one end in S. A sensor network topology based on weakly connected sets is partition into three groups, slaves, masters and bridges. The first performs the measurements, the second gathers the collected data and the later provides the inter-group communications. We first give some properties of this combinatorial structure when the undirected graph G is connected. Then we provide complexity results for the problem of finding the minimum weakly connected independent set problem MWCISP. We also describe an exact enumeration algorithm of complexity O∗1.4655|V | for the MWCISP. Numerical tests of this exact procedure are also presented. We then present an integer programming formulation for the minimum weakly connected independent set problem and discuss its associated polytope. Some classical graph operations are also used for defining new polyhedra from pieces. We give valid inequalities and describe heuristical separation algorithms for them. Finally, we develop a branch-and-cut algorithm and test it on two classes of graphs.

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 noeuds -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 ⊂ V est dit faiblement connexe si le graphe GS = V, S, V \S est connexe, où S, V \S est l’ensemble des arêtes e = {u, v} de E avec u ∈ S et v ∈ V \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.

en fr

Keywords : Branch-and-cut algorithm Exact algorithm Dominating set Weakly connected independent set Wireless networks

Mots-clés : Ensembles dominants Indépendant faiblement connexe Réseaux sans fil Algorithme d’énumération exact Polytope Algorithme de coupes et branchement





Autor: Djelloul Mameri -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados