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.
Document type :
Conference papers
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00092254
Contributor : Martine Peridier <>
Submitted on : Friday, September 8, 2006 - 3:47:38 PM
Last modification on : Thursday, May 24, 2018 - 3:59:21 PM
Long-term archiving on : Tuesday, April 6, 2010 - 12:51:08 AM

Identifiers

  • 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. ⟨lirmm-00092254⟩

Share

Metrics

Record views

192

Files downloads

77