Problèmes algorithmiques et de complexité dans les réseaux sans fil

Ces dernières années ont connu l'avènement des réseaux sans fil, dopés par leur facilité de déploiement et par leur usage dans de multiples domaines : réseaux domestiques Wi-Fi, téléphonie mobile, réseaux ad-hoc, réseaux de capteurs, ... L'objet de cette thèse porte sur l'étude de problèmes algorithmiques directement inspirés des contraintes de fonctionnement rencontrées dans de tels réseaux, et se découpe en trois parties. La première partie de nos travaux s'intéresse à l'étude du problème de la diffusion d'un message émis depuis un noeud source unique vers l'ensemble des noeuds participant au réseau. Ce problème est abordé dans plusieurs modèles de communication, qui supposent tous des émissions omnidirectionnelles à portée fixée et l'existence de phénomènes d'interférences. Il en résulte l'incapacité pour un noeud donné de garantir la réception correcte de deux transmissions voisines simultanées. Nous étudions la complexité de ce problème et proposons des stratégies de résolution exactes ou avec garantie de performance. Dans une seconde partie, l'un des modèles de communication précédemment introduits sert de support à l'étude d'un autre problème algorithmique, dont l'objet est la satisfaction de requêtes de communications. Les travaux menés sur ce problème visent à établir sa complexité ainsi que les facteurs dont elle dépend. La dernière partie nous amène au problème de conception de réseaux sans fil. L'objectif est d'assurer une distribution de flux depuis des noeuds sources vers des noeuds clients, en minimisant le coût de l'infrastructure déployée. Les communications établies ici à l'aide d'antennes directionnelles ne sont pas sujettes aux phénomènes d'interférences. La difficulté du problème réside dans la satisfaction de contraintes de déploiement (nombre d'antennes limitées par noeud, résistance aux pannes, ...). Nous étudions la complexité de ce problème, et proposons plusieurs méthodes de résolution exactes et approchées pour des instances de taille raisonnableThe last couple of years have seen the advent of wireless networks, doped by their ease of deployment and their use in multiple fields: personal WiFi networks, mobile telephony, ad hoc networks, sensors networks, ... The subject of this thesis relates to the study of algorithmic problems directly inspired by operating constraints which can be found in such networks. This manuscrit is divided into three parts. The first part of our work is devoted to the study of the problem of broadcasting a single source node message to all the other nodes of a network. This problem is tackled in various communication models. All the considered model suppose range-fixed omnidirectional transmissions subject to interference phenomena. It results from that, that any given node is unable to retrieve simultaneously two incoming transmissions. We study the complexity of this problem and propose some strategies in order to solve it. In a second part, We study another algorithmic problem in the same communication model, whose object is to satisfy a given set of communication requests. Our work consists in etablishing the complexity of this problem, and studying the impact of various factors on this complexity. The last part considers the problem of designing survivable radio networks . The objective is to ensure a distribution of bandwidth from source nodes to customers nodes, by minimizing the cost of the deployed infrastructure. Communications are made via directional antennas, and are not subjects to interferences. The difficulty of the problem lies in the satisfaction of deployment constraints (limited number of antennas per node, robustness against failures of nodes, ...). We study the complexity of this problem, and propose exact and approximated resolution methods to solve reasonable size instancesMONTPELLIER-BU Sciences (341722106) / SudocSudocFranceF