Groupe de Recherche sur la Théorie des Réseaux Et Communications
(Projet joint ENS-INRIA)

Propositions de stage pour l'année 2006/2007

Titre: Un protocole MAC de type Aloha à réutilisation spatiale pour les réseaux de mobiles sans fil avec des antennes directionnelles.
Encadrants: François Baccelli et Bartek Blaszczyszyn
Description: L'article [1] défini un mécanisme de contrôle d'accès pour les grands réseaux de mobiles utilisant des communications sans fil et avec plusieurs relais. Ce mécanisme est fondé sur une nouvelle représentation des interférences (et donc des collisions) adaptée au contexte de grands réseaux avec mobilité aléatoire. Il est conçu pour le contexte du relai des communications par l'ensemble des mobiles, où il est important de trouver un compromis entre la densité spatiale des communications et la portée des transmissions. Plus précisément, nous montrons comment optimiser le produit du nombre moyen des transmissions qui réussissent simultanément dans une unité d'espace (nombre lié à la notion de réutilisation spatiale) et de la portée moyenne de chaque transmission. L'optimisation qui est proposée est fondée sur des moyennes réalisées sur toutes les configurations poissonniennes des mobiles. Les principaux outils mathématiques sont ceux de la géométrie aléatoire, et tout particulièrement des versions spatiales des processus poissonniens additif et maximal. Le protocole MAC associé peut être implémenté de manière décentralisée si les mobiles disposent d'informations géographiques locales. Sa capacité de transport est proportionnelle à la racine carrée de la densité des mobiles. Sous certaines conditions de mobilité et de stabilité décrites dans l'article, le délai moyen de transport d'un paquet d'un mobile vers un autre est proportionnel à la distance qui les sépare et à la racine carrée de la densité des mobiles.
Dans se stage nous proposons d'intégrer l'utilisation des antennes directionnelles dans le protocole MAC de type Aloha à réutilisation spatiale.
A lire, à regarder:
[1] Baccelli, F., Blaszczyszyn, B. and Mühlethaler, P. (2006). An Aloha protocol for multihop mobile wireless networks. In Proc. of ITC Specialist Seminar on Performance Evaluation of Wireless and Mobile Systems. Antwerp, Belgium. early version in IEEE Information Theory. [Abstract ]
[2] Baccelli, F., Blaszczyszyn, S. Dalibard, B. and Mühlethaler, P. (2006). On opportunistic routing in multi-hop mobile ad hoc networks taking advantage of time and space diversity
[3] Page web sur ce MAC de type Aloha à réutilisation spatiale.

Titre: Arbres géométriques aléatoires pour les réseaux auto-organisés
Encadrant: François Baccelli
Description: Un grand intérêt est actuellement porté pour les graphes dont les sommets sont des points de l'espace euclidien et dont la structure est déterminée localement. La triangulation de Delaunay, les graphes de plus proches voisins ou encore les graphes de type "Small World" sont des exemples populaires de ce type de graphes. Lorsque l'ensemble de points est un processus ponctuel de Poisson sur R^d, il est possible de mener à bien un étude approfondie des propriétés de ces graphes aléatoires. Nous proposons à l' étudiant de travailler sur des arbres de ce type. D'une part, les techniques de calcul de la géométrie stochastique permettent de déterminer explicitement la loi de fonctionnelles locales de ces graphes, comme le degré d'un sommet ou les longueurs des arêtes qui en sont issues. D'autre part, il est aussi possible de s'intéresser à des caractéristiques plus globales de ces arbres. Par exemple, on peut considérer le chemin dans l'arbre entre deux sommets et s'intéresser à la convergence du nombre d'arêtes dans ce chemin lorsque la distance entre les deux sommets tend vers l'infini. Dans ces deux axes d'investigation, il existe des problèmes non résolus mais néanmoins abordables par un etudiant.

A lire, à regarder:
F. Baccelli, Ch. Bordenave (2006) The radial spanning tree of a Poisson point process to appear in Annals of Applied Probability.

Titre: Dimensionnement de buffers pour les réseaux haut débits.
Encadrant: Marc Lelarge
Description: Un critère clé pour le design des réseaux est la probabilité qu'une file d'attente dépasse la capacité du buffer. Dans un article récent Cao et Ramanan considèrent une file d'attente recevant $N$ sources de trafic indépendantes et telle que la vitesse du serveur soit proportionnelle à $N$. Ils calculent la probabilité que le buffer dépasse un seuil quand $N$ tend vers l'infini. Le résultat obtenu est relativement simple puisque cette probabilité correspond à celle d'atteindre le seuil pour une file $M/D/1$. En effet, le seuil étant constant lorsque N tend vers l'infini, l'échelle de temps caractéristique est inversement proportionnelle au nombre de sources $N$, c'est à dire de l'ordre de grandeur de l'inter-arrivée moyenne des paquets. Quand $N$ augmente, cette inter-arrivée diminue tandis que les inter-arrivées des paquets d'une même source restent constantes. Donc sur cette échelle de temps, les caractéristiques individuelles d'une source deviennent moins importantes et les inter-arrivées de la superposition des sources tend vers un processus de Poisson. Le but du stage est de regarder comment ce résultat peut s'étendre à des réseaux (max,plus)-linéaires.

A lire, à regarder:
J. Cao, K. Ramanan, A Poisson Limit for Buffer Overflow Probabilities, INFOCOM 2002

Last modified: 23/11/2006 by Marc Lelarge