Génération de colonnes pour le routage et l'ordonnancement dans les réseaux radio maillés

Christelle Molle (1) , Fabrice Peix (1) , Hervé Rivano (1)

1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications

Dans cet article, nous étudions la capacité des réseaux radio maillés dédiés à l'accès à Internet. Nous nous plaçons dans l'hypothèse d'un réseau synchrone fonctionnant en régime permanent où les transmissions partagent un même canal radio. Le routage et l'ordonnancement des transmissions ont un impact majeur sur la capacité fournie aux clients. Une optimisation jointe de ces deux problèmes permet de prendre en compte dans le routage les contentions dues aux interférences radio. Nous en développons des formulations exactes en programmation linéaire. Nous présentons ensuite un processus de génération de colonnes résolvant une relaxation du problème. Ainsi, nous contournons l'écueil de la combinatoire des transmissions réalisables simultanément pour permettre de calculer des solutions sur des réseaux de grande taille. Des simulations sont effectuées sur des topologies aléatoires. L'évolution de la capacité d'un réseau maillé avec ses paramètres, ainsi que la complexité algorithmique du problème sont discutées.

Mots clés: Génération de Colonnes; Réseaux Radio Maillés; Capacité; Routage; Ordonnancement; Programmation Linéaire; Génération de Colonnes.

Domaines: Réseaux et télécommunications [cs.NI]

Christelle Molle, Fabrice Peix, Hervé Rivano. Génération de colonnes pour le routage et l'ordonnancement dans les réseaux radio maillés. Colloque Francophone sur l'Ingénierie des Protocoles (CFIP) - Best student paper award, Mar 2008, Les Arcs, France. pp.119-130. ⟨hal-00250166⟩