Algorithmics of radio communication networks modelled by graphs

Cette thèse concerne l'étude de l'algorithmique et de la complexité des communications dans les réseaux radio. La particularité des réseaux radio est que la distance de transmission est limitée et que les transmissions interfèrent entre elles (phénomènes de brouillage). Nous modélisons ces contraintes en disant que deux sommets (équipements radio) peuvent communiquer s'ils sont à distance au plus d_T et qu'un noeud interfère avec un autre si leur distance est au plus d_I. Les distances sont considérées soit dans un graphe représentant le réseau, soit dans le plan euclidien. Une étape de communication consistera en un ensemble de transmissions compatibles (n'interférant pas). Nous nous sommes intéressés au problème de rassembler les informations des sommets du réseau en un noeud central appelé puits. Notre objectif est de trouver le nombre minimum d'étapes nécessaires pour réaliser un tel rassemblement et de concevoir des algorithmes réalisant ce minimum. Ce problème est motivé par une question de France Telecom "comment amener Internet dans les villages". Les sommets représentent les maisons des villages qui communiquent entre elles par radio, le but étant d'atteindre une passerelle centrale connectée à Internet par une liaison satellite. Le même problème se rencontre dans les réseaux de senseurs ou il s'agit de collecter les informations des senseurs dans une station de base. Nous avons considéré le cas où chaque sommet a un nombre fixé de paquets à transmettre et où les distances sont mesurées sur le graphe. Nous avons montré que trouver une solution optimale est en général un problème NP-difficile. Nous avons donné un algorithme 4-approché pour un graphe quelconque. Nous avons aussi établi des résultats optimaux ou quasi optimaux pour des topologies particulières comme la grille ou le chemin. Nous avons aussi considéré le cas systolique où on veut transmettre continuellement des paquets, l'objectif étant de minimiser l'écart entre l'envoi de deux paquets d'un même noeud. Nous avons étudié ce problème quand les distances sont mesurées sur le graphe et aussi dans le cas de sommets dans le plan avec distances euclidiennes. Nous avons montré que ce problème était NP-difficile, avons établi un algorithme 4-approché et obtenu des solutions quasi optimales pour les chemins, arbres et grilles.NICE-BU Sciences (060882101) / SudocSudocFranceF