Algorithmique des réseaux de communication radio modélisés par de [sic] graphes
Institution:
NiceDisciplines:
Directors:
Abstract EN:
This thesis studies the algorithmics anc complexity of communications in a radio network. Radio networks are particular, because the transmission distance is limited and because certain transmissions may interfere with each other. We model this constraints by assuming that two nodes (radio equipment) can communicate with each other if they are at a distance smaller or equal than d_T and that a node interferes with any other that is at a distance smaller or equal than "d_I. This distances are considered in both cases: when they nodes belong to the Euclidean space and the distance between the nodes is the usual Euclidean distance, and when the distances are measured over a graph representing the network. A round being a set of transmissions that are compatible (do not interfere) we interest ourselves in the problem of gathering information originated at the nodes in the network into a central node called the sink. Our goal is to find the minimum number of rounds required to gather all the information and to devise algorithms that calculate this minimum. This problem is motivated by a question asked by France Telecom about providing internet to villages in France (internet dans les villages). The nodes represent houses (clients) that communicate with each other by means of radio signals, their objective being to access internet using a central gateway which, in turn, is connected to the internet with by satellite. The same problem is found in sensor networks, where information is collected in sensors (the nodes) and has to be gathered in a base station. We considered the case where each node has a fixed number of packets to transmit and the distances are measured over a base-graph. We have shown that the problem of finding an optimal solution is Np-Hard in the general case, but we provided a four approximation algorithm, valid for any base-graph. We have also studied either optimal or nearly optimal solutions for particular topologies like the path and the 2-D grid. We have also studied the systolic case where packets are transmitted permanently, the objective being to satisfy arbitrary traffic demands, per unit of time, with the smallest possible delay. We have studied this variant of the problem in the case where distances are measured on a graph, but also then they are measured in the Euclidean space. We have shown that the problem is NP-Hard, have established a four approximation and obtained either optimal or nearly optimal solutions for the path, trees and subsets of the 2-D grid.
Abstract FR:
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.