Abstract
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.