Quelques résultats de complexité pour un problème de conception de réseaux radio multi-sauts robustes.

Benoit Darties 1, *
* Auteur correspondant
1 APR - Algorithmes et Performance des Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Résumé : Nous étudions dans ce rapport la complexité d'un problème de conception de réseaux radio multi-sauts, posé au départ par une entreprise de télécommunications du sud de la France. L'objectif de cette entreprise est d'assurer la distribution d'un flux internet haut-débit dans des zones rurales non couvertes en technologie ADSL. Ce flux internet est récupéré à partir de villes sources et doit être acheminé à destination de villages clients par un jeu de relais. Un village client peut également servir de relais. La technologie radio est utilisée pour établir un lien entre deux nœuds du réseau (villes, villages ou relais). Le déploiement d'un tel réseau est soumis à plusieurs contraintes. La difficulté du problème consiste à définir quels liens établir pour assurer une distribution efficace, et ce en respectant les contraintes posées. Nous n'utilisons pas d'antennes omnidirectionnelles pour établir les communications entre nœuds. Un lien est rendu possible par la mise en place d'une antenne directionnelle sur chacune de ses extrémités. La communication est possible si et seulement si la qualité du signal est suffisamment élevée. L'utilisation de cette technologie offre une meilleure robustesse aux interférences. Nous supposerons ces dernières inexistantes.
Ce rapport se décompose en 2 chapitres : Le premier chapitre précise les conditions dans lesquelles sont abordées le problème de conception. Nous y présentons notamment les différentes contraintes que doit satisfaire le réseau à concevoir, ainsi qu'une modélisation formelle du problème.
Nous proposons dans le deuxième chapitre une étude de complexité du problème de conception. Nous distinguons trois paramètres régissant trois principales contraintes de déploiement. Notre étude établit la difficulté du problème selon si certains de ces trois paramètres sont considérés ou non. Nous montrons notamment dans quelles mesures le problème de conception peut se ramener à des problèmes algorithmiques biens connus, et quels résultats existent alors sur ces derniers.
Type de document :
Rapport
[Rapport de recherche] RR-07022, LIRMM. 2007
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00182422
Contributeur : Benoit Darties <>
Soumis le : jeudi 25 octobre 2007 - 18:59:21
Dernière modification le : vendredi 9 juin 2017 - 10:41:43
Document(s) archivé(s) le : lundi 12 avril 2010 - 00:42:06

Identifiants

  • HAL Id : lirmm-00182422, version 1

Collections

Citation

Benoit Darties. Quelques résultats de complexité pour un problème de conception de réseaux radio multi-sauts robustes.. [Rapport de recherche] RR-07022, LIRMM. 2007. <lirmm-00182422>

Partager

Métriques

Consultations de
la notice

83

Téléchargements du document

59