---

II. BILAN 2009

Changements majeurs survenus concernant l'Equipe Associée: Les thématiques initialement envisagées en 2009 ont évolué principalement du au fait de départs et arrivées de chercheurs. Tout d'abord, Hervé Rivano a quitté le projet Mascotte et ses doctorants ont terminé leurs thèses. Ainsi, la thématique sur l'optimisation des buffers dans les réseaux maillés sans fil, qui était principalement menée par Hervé et ses doctorants, disparait. Deux étudiants brésiliens qui était en Master à Fortaleza vont commencer leur thèse dans Mascotte. L'un Julio Araujo a une bourse MESR et fera sa thèse en co-tutelle, l'autre Leonardo Sampaio a une bourse CAPES. Ceux-ci vont travailler sur des problèmes d'allocations de fréquences sous différents aspects. Nous avons donc décidé d'élargir la thématique "Allocation de fréquences et coloration de graphes".

 

Rapport scientifique de l'année 2009

Un des buts principaux de l'Equipe Associée EWIN est de favoriser l'échange d'étudiants. En 2009, ce but a été atteint. En effet, la majorité des missions engagées dans le cadre d'EWIN ont été effectuées par des étudiants de Master ou des doctorants. De plus, deux étudiants de Master de Fortaleza qui ont effectué une partie de leur stage au sein de Mascotte (L. Sampaio en 2008 et J. Araujo en 2009) ont soutenu leur Master. Ils ont de plus obtenu des bourses pour effectuer une thèse au sein de Mascotte. De plus, la thèse de J. Araujo se fera en co-tutelle avec l'Université Fédérale du Ceara.

Du point de vue des objectifs scientifiques, nous avons suivi le programme de travail prévu dans la demande 2009 modulo la réorientation thématique évoquée ci-dessus. En effet, notre équipe associée étant principalement basée sur des étudiants en Master et doctorant, il nous a paru peu judicieux d'orienter ceux-ci sur la thématique de l'optimisation des buffers sachant qu'elle allait disparaitre du projet Mascotte. Nous les avons donc plutôt dirigé vers de nouveaux problèmes d'allocation de fréquences.

• Allocation de fréquences et coloration de graphes Nous avons étudié le problème d'allocations de fréquences pour la diffusion d'un satellite vers des récepteurs terrestres, comme prévu dans le programme de travail, mais également un problème d'allocation de fréquence dans les réseaux WDM.
  
  
  • Réception satellitaire et coloration impropre
    Nous avons considéré le problème suivant posé par Alcatel Space Technologies. Un satellite envoie des informations à des récepteurs terrestres, chacun écoutant sur plusieurs fréquences, une par signal qu'il doit recevoir. Techniquement, il est impossible de concentrer le signal envoyé par le satellite exactement sur le récepteur destination. Ainsi une partie du signal se répartit sur une zone autour de la destination, créant du bruit pour les récepteurs présents dans cette zone et écoutant la même fréquence. Chaque récepteur est capable de distinguer un signal qui lui est envoyé des bruits qu'il reçoit, si la somme de ceux-ci n'est pas trop importante. Le problème consiste alors à allouer des fréquences aux récepteurs de manière à ce que chaque récepteur distingue les signaux qui lui sont destinés tout en minimisant le nombre total de fréquences utilisées. Ce problème se modélise en termes de coloration impropre pondérée du graphe de conflit. Celui-ci a pour sommets les récepteurs et deux sommets sont reliés par une arête si ces récepteurs interfèrent. Une coloration k-impropre est une coloration des sommets telles que chaque sommet ait au plus k voisins colorés comme lui.
    Nous avons prouvé des bornes et des résultats de complexité pour la coloration impropre des graphes planaires [CHS09]. Ces graphes sont intéressants car ce sont des graphes de conflits qui apparaissent souvent, puisque les récepteurs sont placés sur la terre. Nous avons également donné des classes de graphes pour lesquelles l'algorithme glouton marche de manière optimale ou quasi-optimale [ArLi09].
    Pour des raisons de dynamicité, nous avons étudié des algorithmes on-line. Pour débuter, nous avons étudié le cas simple de la coloration propre (0-impropre). En particulier, nous avons étudié l'algorithme glouton qui est l'algorithme on-line le plus simple. Nous avons montré qu'il est NP-dur de décider si ce résultat est approché à un facteur multiplicatif près [AHL].
    
    
  • Allocation de fréquences dans les réseaux WDM et arête-coloration Un des problèmes centraux dans les réseaux WDM est le problème du routage et d'allocation de longueur d'ondes. Il consiste à satisfaire un ensemble de requêtes en trouvant pour chacune d'entre elle un chemin et une longueur d'ondes, tout en minimisant le nombre total de longueur d'ondes utilisées. Souvent, ce problème est divisé en deux sous-problèmes. On cherche d'abord un routage et ensuite on attribue les longueurs d'ondes. Dans le cas, où le graphe orienté modélisant le réseau posssède la propriété de chemin unique (i.e. d'un sommet à un autre il existe au plus un chemin), le routage est facile car forcé et seul le problème d'allocation de fréquences demeure. Bermond et al. (Directed acyclic graphs with unique path property, manuscript) ont montré que résoudre ce problème d'allocation de fréquences revient à résoudre le problème de coloration sur la classe des graphes ayant une arête-coloration particulière appelée bonne arête-coloration. Nous avons étudié [ACGH09] cette classe de graphes afin de pouvoir utilisé les propriétés de celle-ci pour concevoir des algorithmes. Malheureusement, nous avons prouvé qu'ils étaient NP-complet de décider si un graphe avaitune bonne arête-coloration. Ceci implique qu'il n'existe pas de bonne caractérisation de la classe des graphes ayant une bonne arête-coloration. Cependant, nous avons exhibé de large sous-classes et donné quelques propriétés des graphes ayant une bonne arête-coloration.
  
  
• Configuration et routage dans les réseaux sans fil
  

  Un des grands challenges actuels est d'offrir l'accès à internet pour tous. Le déploiement d'un réseau haut débit utilisant de la fibre optique peut cependant être prohibitif pour relier des zones rurales et d'autres solutions sont envisagées. Nous regardons les solutions avec des liens radio micro-ondes en collaboration avec la société 3ROAM, basée à Sophia-Antipolis, qui conçoit des équipements pour ce type de réseaux et leur interconnexion avec les réseaux IP. Ceux-ci permettent de transporter des flux de communications sur de longues distances (jusqu'à 50 kilomètres) à haut débit (plusieurs centaines de méga-bits par secondes). De tels réseaux permettent donc de relier une partie des utilisateurs internet (typiquement des villages éloignés ou peu accessibles mais aussi des utilisateurs en ville) au réseau optique dorsal. Le développement et la maintenance de ce type de réseau pose de nombreuses questions qui n'ont pas encore été résolues. En particulier il faut inventer des algorithmes distribués de routage et de reconfiguration dynamique du réseau.
  Une des spécificités de ces réseaux est que les liens de communication radio micro-ondes ont une bande passante variable. En effet, la qualité de la transmission peut-être affectée par les changements météorologique, ce qui peut réduire considérablement la bande passante utilisable. Il faut alors adapter la configuration des liens (puissance d'émission, modulation, codage, taux d'erreurs,...) et le routage des informations dans le réseau. D'autre part, il est possible de modifier dynamiquement la configuration de chaque lien en fonction des besoins en bande passante (variation au cours de la journée) et des conditions environnementales. Ceci permet en outre de choisir la configuration la plus efficace en énergie et donc de réduire la consommation globale d'énergie du réseau. Il faut là encore modifier le routage pour par exemple éteindre certains liens ou au contraire répartir la charge.
  Nous avons construit un modèle de lien de communication radio (en relation avec la PME 3ROAM). Ce modèle est utilisé pour déterminer les différentes configurations qui sont efficaces du point de vue énergétique, en fonction des différentes caractéristiques du scénario de communication (fréquence, bande passante, distance entre antennes, ...). Chaque configuration est associée à un format de modulation et une puissance d'émission. Cela nous donne une relation entre la capacité du lien et son coût énergétique.
  A l'aide de ce modèle, nous avons présenté deux formulations mathématiques pour optimiser conjointement le routage et la configuration dans les réseaux sans fil ''backhaul'' [CNR09a,CNR09b]. En particulier, nous avons proposé une nouvelle approche qui permet de considérer une fonction de coût énergétique linéaire par morceaux. A partir d'un modèle de relaxation linéaire, nous avons conçu une heuristique qui s'accorde bien avec nos simulations.

  
  
  
• Reconfiguration du routage
  

  Le problème de reconfiguration de routage dans les réseaux MPLS ou WDM consiste à ordonnancer les changements de route de chaque connexion pour passer d'un routage initial à un routage cible. L'objectif est d'une part de minimiser le nombre de changements de route à effectuer sur chaque connexion pour passer du routage initial au routage cible, et d'autre part de minimiser nombre de connexions devant éventuellement être temporairement stoppées. Nous cherchons donc à réduire l'impact sur le trafic du changement de routage. Ce problème peut se modéliser comme un jeu sur un graphe orienté modélisant les dépendances entre les routes utilisées dans le routage initial et celles utilisées dans le routage final. Dans, ce graphe orienté, les sommets sont les connexions et il y a un arc d'une connexion u à une connexion v si u utilise dans le routage initial des ressources que u souhaiterait utiliser dans le routage final. En utilisant des agents pour modéliser l'interruption de connexions, une stratégie de reconfiguration est une succession de mouvements suivant l'une des règles suivantes: (i) placer un agent sur un sommet (interrompre une connexion et libérer les ressources associées); (ii) nettoyer un sommet si tous ses voisins sortants sont nettoyés ou couverts par un agent. (réserver la route cible d'une connexion lorsque les ressources sont disponibles, puis libérer les ressources de la route initiale); et (iii) ôter un agent d'un sommet si tous ses voisins sortants sont nettoyés ou couverts par un agent (rétablir une connexion sur sa route cible).
  Lors du stage de Ronan Soares, nous avons étudié le compromis entre le nombre d'agents utilisés pour la reconfiguration et le nombre d'étapes pour effectuer cette reconfiguration. Plus précisément, nous nous intéressons au problème qui consiste à déterminer si x agents sont capables de traiter un graphe orienté en y étapes. Nous avons montré que ce problème est NP-complet en général si soit x soit y est fixé. Nous avons également donné des bornes inférieures et supérieures pour des classes de graphes particulières: graphes orientés acycliques, arborescences (sortantes et entrantes), pieuvres orientées, chemins disjoints. Pour certaines de ces classes nous avons donné des algorithmes optimaux.

Articles dans des revues internationales

[AHL] M. Asté, F. Havet and C. Linhares Sales. Grundy number and products of graphs. Discrete Mathematics, to appear. PDF

[BCY09] J.-C. Bermond, R. Correa and J. Yu. Optimal Gathering Algorithms on Paths under Interference Constraints. Discrete Mathematics309(18):5574-5587, 2009. PDF

[CHS09] R. Correa, F. Havet, J.-S. Sereni. About a Brooks-type theorem for improper colouring. The Australasian Journal of Combinatorics 43:219-230, 2009. PDF

Communications dans des conférences avec comité de lecture

[ACGH09] J. Araujo, N. Cohen, F. Giroire and F. Havet. Good edge-labelling of graphs. In V Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS 2009), Electronic Notes on Discrete Mathematics, 2009. PDF

[ArLi09] J. Araujo and C. Linhares Sales Grundy number on P4-classes. In V Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS 2009), Electronic Notes on Discrete Mathematics, 2009.

[CNR09a] D. Coudert, N. Nepomuceno, and H. Rivano. Minimizing Energy Consumption by Power-Efficient Radio Configuration in Fixed Broadband Wireless Networks. In First IEEE WoWMoM Workshop on Hot Topics in Mesh Networking (HotMESH), Kos, Greece, June 2009. IEEE. PDF

[CNR09b] D. Coudert, N. Nepomuceno, and H. Rivano. Joint Optimization of Routing and Radio Configuration in Fixed Wireless Networks. In A. Chaintreau and C. Magnien, editors, 11ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'09), Carry le Rouet, June 2009. PDF

[HaLi09] F. Havet and C. Linhares Sales. Combinatória e Problemas em Redes de Telecomunicacoes. In Colibri 2009, Rio Grande do Sul, Brasil, July 2009. PDF

[LiSa09] C. Linhares Sales and L. Sampaio. B-coloring of m-tight graphs. In V Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS 2009), Electronic Notes on Discrete Mathematics, 2009.

Mémoires de Master

[Ara09] J. Araujo Coloracao gulosa e coloracao poderada. Master thesis, Federal University of Fortaleza, 2009.

[Sam09] L. Sampaio b-coloracoes de grafos. Master thesis, Federal University of Fortaleza, 2009.