Avoiding starvation of Wi-Fi access points: the study of 1-extendable sets in graphs
Pierre Bergé  1@  , Thomas Begin  2@  , Anthony Busson  3@  , Carl Feghali  4@  , Rémi Watrigant  4@  
1 : Laboratoire dÍnformatique, de Modélisation et dÓptimisation des Systèmes
Université Clermont Auvergne : UMR6158
2 : LIP
CNRS 5280, Université Lyon 1, ENS Lyon
3 : Laboratoire d'Informatique du Parallélisme
Univ Lyon, ENS de Lyon, CNRS, Inria, UCB Lyon 1, IXXI, LIP, 69342 Lyon, France
4 : LIP
Université Claude Bernard et ENS Lyon

In this article, we present both structural and algorithmic questions on graphs, which are motivated by an application on Wi-Fi networks. In a CSMA/CA network, the fairness of each node is ensured when the subgraph induced by each channel is 1-extendable, i.e. each node belongs to a maximum independent set. We study two problems: the recognition of 1-extendable graphs, and then the assignation of channels such that each channel subgraph is 1-extendable. We propose not only theoretical answers (exact/approximation algorithms or hardness reductions) but also heuristics which allow us to output quickly a feasible solution for large instances.


Personnes connectées : 27 Vie privée
Chargement...