Habilitation à Diriger les Recherches

Modélisation et optimisation du partage de ressources dans les réseaux radio multi-sauts

23 Juin 2014

Récupérer la thèse (fr) »

Récupérer la présentation (en) »

Résumé

Cette habilitation à diriger les recherches couvre une grande part des travaux que j’ai mené depuis 2004. Après un doctorat centré sur l’algorithmique aléatoire et d’approximation pour les problématiques issues des réseaux optiques, j’ai changé d’objet d’étude pour m’intéresser à la capacité des réseaux radio multisaut. En particulier, j’ai fait le choix d’utiliser des méthodes d’optimisation, principalement la programmation linéaire, pour modéliser et analyser les structures optimales qui émergent dans ce contexte.

Le constat en 2004 est que la compréhension des problèmes est trop faible et les approches classiques consistent à dénaturer les phénomènes physiques dans des modèles qui permettent une expression combinatoire des réseaux. En associant optimisation et simulation, on obtient des encadrements de la capacité, mais cela reste insuffisant. Pour aller plus loin, il faut une modélisation plus fine des interférences, ce qui amène à une explosion combinatoire de la taille des programmes linéaires.

Néanmoins, la technique de génération de colonne permet à la fois de revenir à des modèles d’interférences réalistes, fondées sur les équations de SINR, et d’obtenir des résolutions extrêmement rapides. Il est déjà possible de comprendre certains phénomènes réseaux comme la structure des zones d’engorgements qui apparaissent autour des passerelles quand le trafic est convergeant. Les gains en temps de calcul permettent aussi d’envisager de complexifier les modèles. Nous introduisons alors les mécanismes de contrôle continu de puissance d’émission et le choix du taux de transmission sur chaque lien. Si les calculs sont plus longs, il est possible d’étudier les fronts de Pareto entre la capacité et la consommation énergétique des réseaux, et de comprendre la structure des routages optimaux dans ces situations. La présentation se conclut sur un ensemble de perspectives de recherche autour de la dynamique des réseaux, de leur environnement et usage, et de l’architecture des réseaux capillaires.

Jury

Rapporteurs:
Examinateurs:

PhD in computer sciences

Algorithms and telecommunications :
Approximate coloring and multicommodity flows Applications to infrastructure networks

Supervised by Afonso Ferreira and Jérôme Galtier

Defended in Novembre 2003 at University of Nice Sophia Antipolis

Get the manuscript »

Abstract

This thesis deals with fundamental combinatorial optimization problems yielded by structural and algorithmic models of optical backbone networks design. Telecommunication operators require the optimization of these networks and a guaranted efficient use of the resources they deploy.

We give a new model for multifiber WDM optical networks. Through the use of aggregated cable-wise routing, we chose a new way for considering the wavelength assignment constraint which is rooted on a group conflict notion.

We also study the path coloring problem which stem from the wavelength assignment in monofiber optical networks. We develop, for the linear relaxation of this problem, an efficient polynomial algorithm in bounded degree trees and extend it to the graphs with bounded treewidth. We upper-bound the cost of such a coloring in binary trees and provide a randomized (1+5/(3e)+o(1))-approximation for  the integral path coloring in bounded degree trees, which improve on the best known algorithm for this case.

We finally present algorithmic improvements for the integral and fractional multicommodity flow problems. We give an incremental randomized rounding algorithm to approximate the integral multicommodity flow. Motivated by the need for fast fractional multicommodity flow computations for the previous algorithm, we consider the combinatorial approximations of this problem. By using dynamic shortest paths computation techniques, we improve on one of the best algorithm of the literature.

Jury

President: Michel Habib   Professor U. Montpellier II

Supervisors:
Reviewers:
Referee: Michel Cosnard   Professor UNSA