BLANC - Blanc

– GraTel

Résumé de soumission

André Raspaud a initié en 2005 une collaboration fructueuse avec le Department of Applied Mathematics de l'université de Kaohsiung, Taiwan. Cette proposition s'appuie sur cette coopération de 3 ans (qui comprend notamment un doctorant en co-tutelle). Le thème scientifique prioritaire "Télécommunications" est un domaine applicatif naturel de la théorie des graphes. L'objectif scientifique de cette proposition est d'aborder les problèmatiques en télécommunications, surtout sans-fil, avec les outils des colorations de graphes et de la théorie polyédrale des graphes. Les colorations de graphes sont au coeur de la modélisation de nombreux types de réseaux: dans les réseaux à multiplexage en longueur d'onde, les couleurs représentent les longueurs d'onde; dans les réseaux à tolérance de panne, les couleurs représentent les dispositifs qui partagent une mêmre ressource à risque ... Dans ce projet, nous souhaitons étudier les possibilités induites par des types de colorations graphes très récents, comme les L(p,q)-colorations par listes, et leurs applications en télécommunications, avec une attention particulière aux problèmes d'allocations de fréquences (Tâche 2). Pour des réseaux dynamiques comme les réseaux sans-fil, on peut accroitre l'utilisation des ressources et améliorer le routage des informations en partitionnant les noeuds mobiles en sous-grappes, en temps réel. Les ensembles dominants sont des structures de graphes élémentaires pour réaliser un partitionnement en grappes. Il seront étudiés dans la tâche 1. Les ensembles stables sont très utilisés pour modéliser dans un graphe de conflit les ensembles de noeuds qui ne sont pas en conflit. Ils modélisent aussi des objets naturels en télécommunications: par exemple, dans le cas du planning de diffusion pour le mode de multiplexage TDMA, les différents slots temporels correspondent aux différentes couleurs (et donc des stables) du graphe associé. Tout ceci entre dans le périmètre de la tâche 1. Une technique classique pour garantir une tolérance aux pannes dans un réseau est d'imposer l'existence d'un certain nombres de chemins disjoints entre les sommets entrants et sortants des demandes. Cependant, il peut arriver que le chemin de "secours" soit beaucoup plus court que le chemin principal. Aussi, une contrainte supplémentaire est de rajouter une taille limite à ces chemins. L'approche polyédrale associée aux graphes modélisant ces réseaux a permis de mettre au point des algorithmes efficaces issus de la programmation linéaire, pour le cas d'une unique demande. Dans la tâche 2, nous étendrons cette approche pour traiter le cas de demandes multiples. Tous les participants à ce projet ont une forte compétence en théorie des graphes et bénéficieront de l'expertise de l'équipe INRIA Mascotte dans les problématiques télécoms et de l'expertise de l'équipe INRIA RealOpt en programmation mathématique. Ce projet sera en particulier une belle occasion d'initier une coopération scientifique entre ces deux équipes. Il permettra la mise en place d'un réseau de recherche solide en mathématiques discrètes entre la France (centres: université de Bordeaux, insititut Fourier (Grenoble) et l'INRIA Sophia-Antipolis) et Taiwan (centres: Sun Yat-sen University (Kaohsiung), National Taiwan University (Taipei) et Academia Sinica (Taipei)).

Coordination du projet

L'auteur de ce résumé est le coordinateur du projet, qui est responsable du contenu de ce résumé. L'ANR décline par conséquent toute responsabilité quant à son contenu.

Partenaire

Aide de l'ANR 0 euros
Début et durée du projet scientifique : - 0 Mois

Liens utiles

Explorez notre base de projets financés

 

 

L’ANR met à disposition ses jeux de données sur les projets, cliquez ici pour en savoir plus.

Inscrivez-vous à notre newsletter
pour recevoir nos actualités
S'inscrire à notre newsletter