Satisfaction de requêtes par affectation de dates d'émission dans les réseaux radio - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2006

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

Benoit Darties
Jérôme Palaysi
  • Function : Author
  • PersonId : 938554

Abstract

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.

Domains

Other [cs.OH]
Fichier principal
Vignette du fichier
benoit.darties_document_DAWN-Renpar-06.pdf (111.07 Ko) Télécharger le fichier

Dates and versions

lirmm-00092254 , version 1 (08-09-2006)

Identifiers

  • HAL Id : lirmm-00092254 , version 1

Cite

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⟩
91 View
54 Download

Share

Gmail Facebook Twitter LinkedIn More