Satisfaction de requêtes dans un réseau radio synchrone : NP-complétude dans les arbres - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2007

Satisfaction de requêtes dans un réseau radio synchrone : NP-complétude dans les arbres

Résumé

Nous étudions un problème algorithmique inspiré des contraintes de routage rencontrées dans des réseaux sans-fil multisauts. Nous cherchons à satisfaire un ensemble de requêtes de communication dans un environnement radio où les émissions de deux nœuds trop proches génèrent une zone de brouillage. Pour satisfaire une requête, il est possible de lui assigner une route dans le réseau que devra suivre le message de la requête. Pour éviter les brouillages nous envisageons de temporiser l'émission de certains nœuds. Notre objectif est de minimiser le temps nécessaire pour satisfaire toutes les requêtes. Nous montrons ici que ce problème, dont l'étude a été entamée dans des travaux précédents, est NP-Complet lorsque la topologie du réseau est un arbre.
Fichier principal
Vignette du fichier
Algotel2007.pdf (83.61 Ko) Télécharger le fichier
Loading...

Dates et versions

lirmm-00172311 , version 1 (14-09-2007)

Identifiants

  • HAL Id : lirmm-00172311 , version 1

Citer

Benoit Darties, Sylvain Durand, Jérôme Palaysi. Satisfaction de requêtes dans un réseau radio synchrone : NP-complétude dans les arbres. AlgoTel: Aspects Algorithmiques des Télécommunications, May 2007, Ile d'Oléron, France. pp.113-116. ⟨lirmm-00172311⟩
83 Consultations
43 Téléchargements

Partager

Gmail Facebook X LinkedIn More