Cette thèse concerne l'étude de l'algorithmique et de la complexité des communications dans les réseaux radio. En particulier, nous nous sommes intéressés au problème de rassembler les informations des sommets d'un réseau radio en un noeud central.<br />Ce problème est motivé par une question de France Telecom (Orange Labs) "comment amener Internet dans les villages".<br />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 où il s'agit de collecter les informations des senseurs dans une station de base.<br />Une particularité des réseaux radio est que la distance de transmission est limité et que les transmissions interfèrent entre elles (phénomènes d'interférences). Nous modélisons ces contraintes en disant que deux sommets (équipements radio) peuvent communiquer s'ils sont à distance au plus dT et qu'un noeud interfère avec un autre si leur distance est au plus dI. Les distances sont considérées dans un graphe représentant le réseau. Une étape de communication consistera donc en un ensemble de transmissions compatibles (n'interférant pas).<br />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. Pour des topologies particulières comme le chemin et la grille, nous avons établi des résultats optimaux ou quasi optimaux.<br />Nous avons aussi considéré le cas systolique (ou continu) où on veut maximiser le debit offert à chaque noeud.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00418297 |
| Date | 05 August 2009 |
| Creators | Reyes, Patricio |
| Publisher | Université de Nice Sophia-Antipolis |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | English |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.002 seconds