Satisfaction de requêtes par affectation de dates d'émission dans les réseaux radio

Benoit Darties 1 Jérôme Palaysi 1
1 APR - Algorithmes et Performance des Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Résumé : Nous étudions deux problèmes algorithmiques inspirés des contraintes de routage rencontrées dans des réseaux sans-fil. Ces problèmes cherchent à satisfaire des requêtes de communication dans un environnement où deux noeuds ne sont pas nécessairement à portée directe d'émission et où les émissions trop proches génèrent des zones 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 pouvons envisager de temporiser l'émission de certains noeuds. Notre objectif est de minimiser le temps nécessaire pour satisfaire toutes les requêtes. Les deux problèmes diffèrent en ce que les routes données dans l'un (DAWNpaths) sont à trouver dans l'autre (DAWN-requests). Nous montrons en particulier que ces problèmes sont NP-difficiles et non approximables en général à un facteur constant près. Nous déterminons la frontière entre polynomialité et NP-complétude des problèmes de décision associés.
Type de document :
Communication dans un congrès
RenPar'17 : Rencontres francophones du Parallélisme (Perpi'2006), Oct 2006, Canet en Roussillon, France. pp.156-163, 2006
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00092254
Contributeur : Martine Peridier <>
Soumis le : vendredi 8 septembre 2006 - 15:47:38
Dernière modification le : vendredi 9 juin 2017 - 10:42:01
Document(s) archivé(s) le : mardi 6 avril 2010 - 00:51:08

Identifiants

  • HAL Id : lirmm-00092254, version 1

Collections

Citation

Benoit Darties, Jérôme Palaysi. Satisfaction de requêtes par affectation de dates d'émission dans les réseaux radio. RenPar'17 : Rencontres francophones du Parallélisme (Perpi'2006), Oct 2006, Canet en Roussillon, France. pp.156-163, 2006. <lirmm-00092254>

Partager

Métriques

Consultations de
la notice

116

Téléchargements du document

71