Programme INRIA "Equipes Associées"

EQUIPE ASSOCIEE	EWIN
sélection	2009

Equipe-Projet INRIA : Mascotte	Organisme étranger partenaire : Universidade Federal do Ceará
Centre de recherche INRIA : INRIA Sophia Antipolis Thème INRIA : Com B	Pays : Brésil

 

	Coordinateur français	Coordinateur étranger
Nom, prénom	Frédéric Havet	Claudia Linhares Sales
Grade/statut	Chargé de recherche	Professeur en Informatique
Organisme d'appartenance	projet MASCOTTE, projet commun (INRIA Sophia Antipolis - I3S (UMR 6070 of the CNRS and the University of Nice-Sophia Antipolis)	Departamento de Computação Laboratório de Inteligência Artificial, Universidade Federal do Ceará, Fortaleza, Brasil.
Adresse postale	Projet Mascotte, commun I3S(CNRS/UNSA)-INRIA INRIA Sophia-Antipolis 2004, route des Lucioles -- B.P. 93 06902 Sophia-Antipolis Cedex France	Department of Computer Science, Federal University of Ceará Bloco 910 - Campus do Pici CEP 60455-760, Fortaleza-CE Brasil
URL	http://www.inria.fr/mascotte	http://www.lia.ufc.br/~linhares/
Téléphone	+33 4 92 38 50 18	+55 85 3366-9842
Télécopie	+33 4 89 73 24 00	+55 85 3366-9837
Courriel	Frédéric.Havet@sophia.inria.fr	linhares@lia.ufc.br

Titre de la thématique de collaboration : Algorithmes efficaces dans les réseaux sans fil Efficient algorithms in WIreless Networks

Descriptif : Les thèmes de recherche sont la conception d'algorithmes, exacts ou approchés, pour la résolution de problèmes dans les réseaux, en particulier les réseaux sans fils. Les problèmes que nous considérerons peuvent être modélisés en terme de coloration de graphes ou de décomposition de graphes. Nous comptons plus spécifiquement aborder les problèmes suivants: L'optimisation des buffers dans les réseaux maillés sans fil dont une des modélisation est la coloration proportionnelle des arêtes d'un graphe; L'allocation de fréquences dans les réseaux radios qui peut se modéliser par de la coloration impropre d'un graphe; Le routage dynamique dans les réseaux sans fil utilisant des liens microondes. La reconfiguration du routage dans les réseaux MPLS ou WDM dont certains modèles rappellent les problèmes de recherche dans les graphes et sont fortement reliés aux décompositions arborescentes ou linéaire (tree et path decomposition). En parallèle de ces recherches, nous développerons les librairies Mascopt et Parego dont une interface commune a été conjointement implémentée. Nous y intégreront différents algorithmes obtenus lors de nos recherches afin de comparer leurs efficacités pratique et théorique.

Présentation détaillée de l'Équipe Associée

1. Objectifs scientifiques de la proposition Les objectifs de cette Équipe Associée sont la conception d'algorithmes, exacts ou approchés, pour la résolution de problèmes dans les réseaux sans fils. Pour cela, nous modélisons les problèmes en termes de graphes. Nous présentons ci-dessous quelques problèmes que nous comptons étudier.

Optimisation des buffers dans les réseaux maillés sans fil
Nous considérons un réseau maillé sans fil multiplexé en temps qui relie des routeurs à l'aide d'antennes directionnelles. Afin d'éviter les interférences, chaque routeur ne peut être impliqué que dans au plus une communication à la fois. Ainsi un ensemble de communications réalisables simultanément est un ensemble de paires de routeurs communicants entre eux et qui n'interfèrent pas avec ceux des autres paires. Le problème classique d'allocation de créneaux de temps (time-slots) consiste alors à décomposer l'ensemble des communications en le plus petit nombre d'ensembles de communications réalisables simultanément. Ceci se modélise alors par de l'arête-coloration propre.
La nécessité d'optimiser les buffers apparaît lorsque nous considérons des requêtes un à débit constant (Constant Bit Rate ou CBR). Dans ce cas, chaque requête (i.e. chemin dans le réseau) possède un débit. Pour acheminer ce débit suivant ce chemin, il faut que chaque communication sur celui-ci soit activée périodiquement dans une certaine proportion du temps. Il nous faut donc trouver un ordonnancement périodique qui satisfasse les requêtes CBR, c'est-à-dire tel que chaque communication se voit assigner un nombre de créneaux proportionnel à son poids (la somme des débits des requêtes utilisant cette communications). De plus, la longueur de la période est proportionnelle à la taille du buffer requise à chaque routeur qui est un paramètre important du coût du réseau. Ce problème se modélise alors par de l'arête-coloration proportionnelle. Dans [HLR07], nous avons donné un encadrement sur la taille des buffers et décrit deux classes d'instances pour lesquelles le problème est soluble en temps polynomial. Nous poursuivrons ces premiers travaux. En particulier, nous voudrions concevoir des algorithmes approchés pour des classes de graphes correspondant à des réseaux réels (e.g. graphes arc-circulaires, sous-graphes du réseau triangulaire).

Allocation de fréquences et coloration impropre pondérée
Nous considérons 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. Pour un graphe de conflit général, ce problème est difficile (NP-dur) et non-approximable car il généralise la coloration classique. Il le reste également sur des graphes de conflits particuliers qui apparaissent souvent comme les graphes planaires [CHS09], les graphes d'intersections de disques et les sous-graphes du réseau triangulaire [Havet,Kang and Sereni, Improper colouring of unit disk graphs, Networks, to appear]. Ces derniers, qui forment une sous-classe des deux précédentes, sont intéressants parce qu'ils sont très souvent utilisés car le réseau triangulaire réalise une couverture optimale du plan. Pour ces derniers nous avons donné [BHLL07] des algorithmes approchés en temps polynomial. Nous chercherons à trouver des algorithmes plus performants ainsi que des algorithmes approchés pour des classes plus grandes notamment les graphes planaires ou d'intersection de disques. De plus, pour des raisons de dynamicité, nous étudierons des algorithmes on-line. En particulier, nous étudierons l'algorithme glouton qui est l'algorithme on-line le plus simple. Dans le cas de la coloration classique (coloration propre), l'algorithme glouton peut donner un résultat très mauvais et il est NP-dur de décider si ce résultat est approché à un facteur multiplicatif près [AHL08, AHL08b]. Cependant, avec grande probabilité, il donne un résultat approché à un facteur d'au plus 2 (voir [Balogh et al. SIAM J. Discrete Math. 22(3):887­900, 2008]). Nous essaierons d'établir des résultats similaires pour la coloration impropre.

Reroutage dynamique 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 est cependant prohibitif pour de nombreuses collectivités locales ou régionales, voire certains pays. Ainsi d'autres solutions sont envisagées. Les partenaires ont par le passé travaillé sur des modèles proposés par l'opérateur Orange consistant à utiliser des réseaux WiFi avec la présence d'interférences (articles BCY06, BCY08). Nous proposons dans l'équipe associée de regarder les solutions avec des liens radio microondes en collaboration avec la société 3 Roam 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 (plusieurs kilomètres) à haut débit (plusieurs méga-octets, voire giga-octets). De tels réseaux permettraient 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 faudra inventer des algorithmes distribués de reroutage pour la reconfiguration dynamique du réseau. En effet, les systèmes radio permettent de réduire la consommation d'énergie en modulant la puissance d'émission et le débit. L'objectif étant d'acheminer les paquets mais aussi d'économiser l'énergie consommée pour la transmission des signaux et de mieux répartir les flux de trafic. Il faudra également que le réseau soit suffisamment maillé pour tolérer des pannes multiples. La demande de bande passante n'étant pas constante au cours d'une même journée, on pourra par exemple éteindre certains liens ou détourner du trafic. Nous travaillons actuellement sur la construction d'un modèle de lien de communication radio (en relation avec la PME 3ROAM) pour déterminer les capacités d'un lien radio en fonction de différents paramètres tels que la largeur de bande, la modulation, le codage et la puissance de transmission. Ce modèle est la brique de base dont nous avons besoin pour les algorithmes d'optimisation envisagés. La thèse de Napoleao Nepomuceno en co-tutelle entre Mascotte et Parego porte sur ce sujet.

Décomposition de graphes et reconfiguration du routage
Les membres des deux partenaires travaillent sur les décompositions de graphe de type arborescente introduite par Robertson et Seymour dans leur série de papiers "Graph Minors". Celles-ci sont d'un grand intérêt aussi bien d'un point de vue théorique qu'algorithmique. En particulier, de nombreux problèmes NP-complets peuvent être résolus en temps polynomial pour les graphes admettant une telle décomposition ayant une petite largeur. De plus, la largeur des différentes décompositions arborescentes (pathwith, treewidth, ...) est égale au nombre d'agents nécessaires dans les différentes variantes des problèmes de recherche dans un graphe, également connus comme les jeux de gendarmes et voleurs.
Récemment, nous avons proposé dans [Coudert et al, Rerouting requests in WDM networks. In AlgoTel'05, Presqu'île de Giens, France, pages 17-20, mai 2005] une modélisation d'un problème de reconfiguration de routage dans un réseau MPLS ou WDM comme un problème particulier de recherche dans un graphe orienté. Le problème initial consiste à ordonnancer les changements des requêtes de façon à minimiser le nombre de celles-ci qui doivent être reroutés simultanément sur des ressources temporaires (ou éventuellement stoppées temporairement). Pour l'instant le cas des arbres a été abordé Coudert Huc and Mazauric. A distributed algorithm for computing and updating the process number of a forest. Research Report 6560, INRIA. Nous comptons étudier des classes plus générales et complexes.
Claudia Linhares et Bruce Reed ont co-organisé le workshop GRASTA'08 sur cette thématique à laquelle de nombreux membres des deux partenaires ont participé. A cette occasion plusieurs problèmes ont été identifiés sur lesquels les deux équipes souhaitent travailler. Par exemple, nous étudions la recherche connexe dans les graphes. Dans cette variante, on impose que la partie propre (contrôlée par les agents ou gendarmes) soit connexe. Une question est de déterminer le rapport entre le nombre minimum d'agents pour nettoyer un graphe de manière connexe, et la pathwidth. Dans le cas des arbres, le rapport (atteint) est 2 [Barriere, Fraigniaud, Santoro, Thilikos, WG 03]. Dans le cas général, le meilleur raport est log(n+1) [Fraigniaud et Nisse, LATIN 06] mais on ne connaît pas de graphe pour lequel le rapport est supérieur à 2. Nous cherchons donc à déterminer le meilleur rapport possible. Une autre est de savoir quelle est le coût de la monotonie, (une fois nettoyée une arête doit le rester). On sait que pour certains graphes, le nombre minimum nécessaire d'agents avec monotonie est strictement supérieur à celui nécessaire sans monotonie. Mais combien d'agents supplémentaires la monotonie impose-t-elle ? En particulier, est ce que ce problème appartient à la classe NP?

Librairie Mascopt et Parego
Mascopt est une librairie Java libre sous licence LGPL dédiée aux graphes et aux réseaux. Elle inclut une collection d'interfaces et classes JAVA qui implémentent les structures de données et algorithmes fondamentaux. Parego est une librairie de graphes dédiée à la représentation de relations entre ensembles. Nous avons d'ores et déjà implémenté une interface commune aux deux librairies et avons commencé l'implémentation d'algorithmes de graphes ne utilisant cette interface. Le but final est de faciliter la conception de logiciels d'optimisation dans les réseaux. Nous comptons notamment implémenter les algorithmes obtenus sur les problématiques décrites précédemment à l'aide de ces librairies. Ceci nous permettra de comparer les efficacités pratique et théorique de ces algorithmes.

2. Présentation des partenaires
Partenaire francais: projet Mascotte
Mascotte est un projet commun entre l'INRIA Sophia-Antipolis et le laboratoire I3S qui est une unité mixte CNRS -- Université de Nice-Sophia Antipolis (UNSA). Les objectifs du projet Mascotte sont la conception de réseaux et d'algorithmes de communications. Pour cela, cette équipe développe différents outils aussi bien théoriques (Mathématiques discrètes, théorie des graphes, algorithmique) que pratiques (Optimisation combinatoire, Simulation). Ces outils ont été utilisés ces dernières années à la conception de divers types de réseaux tel que les réseaux WDM, SDH, sans fil, satellitaires, overlay, pair-à-pair ou de transport. Des logiciels de pointe ont également été produits: la librairie Mascopt et le logiciel de simulation OSA notamment.
Le responsable de cette Equipe Associée pour le projet Mascotte est Frédéric Havet. Cliquez ici pour obtenir son CV. Six autres chercheurs permanents de Mascotte sont également impliqués, Jean-Claude Bermond, David Coudert, Stéphane Pérennes, Bruce Reed, Hervé Rivano et Michel Syska ainsi qu'un post-doctorant Nicolas Nisse et 6 doctorants: Marie Asté, Nathann Cohen, Dorian Mazauric, Christelle Molle, Napoleao Vieira Nepomuceno et Ignasi Sau-Valls. En particulier, Napoleao Nepomuceno fait sa thèse en co-tutelle entre les deux partenaires.

Partenaire brésilien: Equipe ParGO (Parallélisme, Graphes et Optimisation), Laboratoire d'Intelligence Artificielle, Université Fédérale du Ceara
L'équipe a été créé il y a une dizaine d'années. Ses activités tournent autour de problèmes liés à la résolution de problèmes en mathématiques discrètes avec des techniques algorithmiques combinatoires et de programmation linéaire en nombres entiers. Elle a une grande expérience dans les domaines de l'algorithmique séquentielle, parallèle et distribuée, ainsi qu'en théorie des graphes et l'optimisation combinatoire. En particulier, plusieurs logiciels et résultats théoriques et expérimentaux dans divers problèmes d'optimisation combinatoire ont été établis dans le domaine des télécommunications. Notons plus spécialement ceux obtenus sur les réseaux sans fils avec les partenaires de l'équipe Mascotte, mais aussi des méthodes de décomposition de problèmes d'optimisation combinatoire afin de permettre leur parallélisation visant les architectures mémoire partagée multi-core. L'équipe investit actuellement sur la relaxation Lagrangienne pour des problèmes issus de la conception de réseaux, en particulier modélisés en termes coloration de graphes et la programmation stochastique qui permet décrire des demandes incertaines. Les chercheurs de l'équipe ParGO sont fortement impliqués dans la formation au niveau master et doctoral. Depuis 1999, 12 étudiants ont été formés et ParGO compte actuellement 5 doctorants et 12 étudiants en master. Le responsable de cette Equipe Associée pour l'équipe ParGo est Cláudia Linhares Sales. Cliquez ici pour obtenir son CV. Six autres chercheurs permanents de ParGO sont également impliqués, Carlos Fish de Brito, Francisco Heron de Carvalho Junior, Gabriel Antoine Louis Paillard, Manoel Bezerra Campêlo Neto, Rafael Castro de Andrade, Ricardo Cordeiro Corrêa, ainsi que 5 doctorants. Carlos Diego Rodrigues, Gisele Azevedo Araújo, Manoel Pereira Gomes Neto, Napoleao Vieira Nepomuceno, et Victor Almeida Campos. En particulier, Napoleao Vieira Nepomuceno fait sa thèse en co-tutelle entre les deux partenaires. Il est de plus prévu que Ronan Soares, un brillant étudiant de Master de Fortaleza (19/20 de moyenne), effectue une partie de son stage (trois mois) au sein de Mascotte.

Historique de la collaboration
La collaboration entres les deux équipes a commencé dans les années 90 lorsque Ricardo Correa a effectué sa thèse à Grenoble sous la direction d'A. Ferreira, un ancien membre de Mascotte, et Claudia Linhares-Sales dans le mème laboratoire. Depuis le contact a été maintenu. Depuis cinq ans, la collaboration s'est intensifiée. Des membres de Mascotte effectuent des visites régulières à l'Université du Ceara (en moyenne 3 visites de 2 semaines chaque année). En 2008, cinq membres de Mascotte se sont rendus à Fortaleza (O. Amini, D. Coudert, F. Huc, N.Nisse et I. Sau-Valls). Les visites des chercheurs brésiliens ont elles été de plus longue durée. Ricardo Correa a passé au sein de Mascotte 2 mois en 2003 et 3 mois en 2006, Claudia Linhares une année entière (2007/2008). Une partie de ces différentes visites ont été possibles grâce à l'action REGAL (financement tripartite CNRS INRIA et région PACA). De plus, Bruce Reed qui a rejoint Mascotte récemment collabore depuis une douzaine d'années avec l'Université de Fortaleza où il se rend très régulièrement. Il a une demi-douzaine de publications communes et organisé plusieurs conférences, workshops et écoles avec eux. Depuis un an, nous avons décidé de favoriser les échanges d'étudiants entre les deux partenaires. Ainsi Leonardo Sampaio a effectué une partie de son stage de Master (trois mois de Janvier à Mars 2008) dans le projet Mascotte sous la direction de Frédéric Havet. Il a travaillé sur le nombre b-chromatique d'un graphe [LS08]. A la meme période, Ignasi Sau-Valls un doctorant de Mascotte, s'est rendu deux mois à Fortaleza et Florian Huc 1 mois. Avec Cláudia Linhares Sales et Júlio Araújo, ils ont développé sur des algorithmes pour la coloration pondérée et la coloration gloutonne d'un graphe [Ara08]. Enfin Napoleao Nepomuceno effectue sa thèse dans le projet Mascotte en co-tutelle l'Université Fédérale du Ceara depuis Décembre 2007 (bourse Région-Entreprise).

Publications communes récentes
[APC+08] A.Aguiar, P.R. Pinheiro, A.L.V Coelho, N. Nepomuceno, A. Neto and R. Cunha, Scalability analysis of a novel integer programming model to deal with energy consumption in heterogeneous wireless sensor networks In Modelling, Computation and Optimization in Information Systems and Management Sciences (MCO'08)}, Communications in Computer and Information Science, volume 14, pages 11-20, 2008. [PDF ]
[Ara08] J. Araújo, Coloração Ponderada e Gulosa, Master thesis, 2008, (en portuguais).
[AHL08] M. Asté, F. Havet, and C. Linhares-Sales. Grundy number and lexicographic product of graphs. In Proceedings of International Conference on Relations, Orders and Graphs and their Interaction with Computer Science (ROGICS 2008), May 2008. [PDF ]
[AHL08b] M. Asté, F. Havet, and C. Linhares-Sales. Grundy number and products of graphs. Technical report inria-00168162, HAL, October 2008. [PDF ]
[BCY06] J-C. Bermond, R, Correa, and M-L. Yu. Gathering algorithms on paths under interference constraints. In 6th Conference on Algorithms and Complexity, volume 3998 of Lecture Notes in Computer Science, Roma, Italy, pages 115--126, May 2006. [PDF ]
[BCY08] J.-C. Bermond, R. Correa, and M.-L. Yu. Optimal Gathering Protocols on Paths under Interference Constraints. Discrete Mathematics, to appear. [PDF ]
[BHHL07] J-C. Bermond, F. Havet, F. Huc, and C. Linhares-Sales. Allocation de fréquences et coloration impropre des graphes hexagonaux pondérés. In Neuvièmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'07), Ile d'Oléron, France, May 2007. [PDF ]
[CHS09] R. Correa, F. Havet, and J.-S. Sereni, About a Brooks-type theorem for improper colouring Australasian Journal of Combinatorics, to appear. [PDF]
[HLR07] F. Huc, C. Linhares-Sales, and H. Rivano. The Proportional Colouring Problem: Optimizing Buffers in Radio Mesh Networks. In LAGOS 07, Puerto Varas, Chile, November 2007. [PDF]
[LMR09] C. Linhares-Sales, F. Maffray, and B. Reed. On planar strict quasi parity graphs. SIAM Journal on Discrete Mathematics 22, 329-347, 2008.
[LS08]L. Sampaio, b-Coloração de grafos, Master thesis, 2008, (en portuguais).

3. Impact La collaboration entre les deux équipes permettra une résolution plus efficace de certains problèmes considérés par les deux équipes. En effet, celles-ci ont une connaissance approfondie des problèmes de réseaux ainsi qu'une grande aptitude leur modélisation et résolution par les mathématiques discrètes et l'optimisation combinatoire. Cependant, chaque équipe a des compétences et des approches des problèmes qui lui sont propres: algorithme exponentiels exacts ou à paramètres fixes, algorithme d'approximation, programmation linéaire, méthode probabiliste, méthode de déchargement, ... La diversité des outils et méthodes maîtrisés par les participants est un ingrédient clé de la réussite des recherches proposées.
De plus, pour le développement conjoint des librairies Mascopt et Parego, la collaboration entre les deux groupes est primordiale. En effet, les deux équipes ne disposant pas d'ingénieur permanent, les capacités de production logicielle sont limitées. Travailler ensemble à l'élaboration de certaines fonctionnalités communes aux deux librairies permet ainsi de compenser en partie ce handicap.
La collaboration facilite ainsi la réalisation des objectifs scientifiques du projet Mascotte et de l'équipe ParGO.

La collaboration entre les deux équipes favorise également la formation de nos étudiants. En effet, ceux d'entre eux qui participent à cette collaboration découvrent des manières différentes de travailler et profitent de l'expertise diverse des membres des deux équipes. Cette collaboration pourrait d'ailleurs servir de point de départ pour un programme d'échanges d'étudiants plus général entre l'Université Fédérale du Ceara et l'INRIA. Le correspondant brésilien pour un tel programme pourrait être soit Claudia Linhares-Sales qui a été responsable des Masters et doctorats ou le responsable actuel Vania Maria Pontes Vidal. Cet échange devrait bien fonctionner car d'une part l'université du Ceara a un vivier d'excellents étudiants qui nous sont recommandés par des chercheurs connaissant bien Mascotte et d'autre part Mascotte a la possibilité de trouver des bourses pour eux . Plus généralement il faut noter que Mascotte a aussi des relations avec d'autres partenaires brésiliens (projet Mobidyn INRIA/FAPESP)) et accueille actuellement en plus de Napoleao Nepomuceno deux autres doctorants brésiliens (de Sao Paolo allocation Cordi et du Minais Gerais bourse brésilienne). Ils se nouent ainsi des relations entre ces étudiants brésiliens et aussi avec les autres étudiants du projet des relations très prometteuses pour l'avenir. Le programme d'échanges d'étudiants avec Fortaleza pourrait s'inscrire dans un cadre plus général de relations France/Brésil. .

Les deux équipes travailleront conjointement sur les différents problèmes décrits ci-dessus. Afin de favoriser les échanges d'idées, la confrontation des points de vue et de garantir la synergie entre les deux groupes, des visites bilatérales de deux semaines à un mois sont prévues. Celles-ci seront réparties tout au long de l'année. A côté de ces courtes visites, Napoleao Nepomuceno doctorant dans Mascotte fera un séjour de 3 mois à Fortaleza dans le cadre de sa co-tutelle et Ronan Soares, étudiant à l'Université Fédérale du Ceara effectuera une partie de son stage de Master dans le projet Mascotte. La plus longue durée de ces séjours est motivée par un souci de formation. Elle permettra aux deux étudiants concernés de mieux profiter des différentes méthodes de travail et expertises des deux partenaires.