Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 3 Février 2004

Introduction aux réseaux mobiles --- Algorithmes quasi optimaux et efficaces en énergie (Election, estimation de la taille du réseau, initialisation)

par Christian Lavault (LIPN, Université de Paris XIII)

Les réseaux mobiles (ou réseaux ad hoc, ou réseaux sans fils) sont des systèmes distribués comportant $n\ge 2$ sites (ou stations de radio). Il existe une foule de modèles de réseaux mobiles, définis en fonction des propriétés considérées en priorité : la mobilité (nombreux modèles et sous-modèles), le mode de communication (synchrone ou asynchrone), les performances des protocoles mis en oeuvre (complexité en moyenne, efficacité en énergie, fiabilité, etc.), etc.

Dans la suite, nous supposons que $n$ est inconnu des stations et nous considérons deux modèles : avec ou sans détection de collisions (CD et sans-CD resp.) et, pour les réseaux sans-CD, deux sous-modèles : le modèle fort et le modèle faible, selon la capacité des stations à émettre ET à recevoir les signaux (téléphone) ou bien à émettre OU à recevoir ("Talky-Walky"), resp.

  1. Deux protocole d'élection (un par modèle ci-dessus) sont présentés et analysés ; leur complexité moyenne en temps est en $O(\log(n))$ et chaque station s'éveille $O(\log\log(n))$ unités de temps au plus (efficacité en énergie).
  2. Avec une probabilité tendant vers 1, on effectue ensuite une bonne estimation de la taille $n$ du réseau. Celle-ci s'effectue aussi en $O(\log\log(n))$ unités de temps au plus et sa complexité moyenne en temps reste en $O(\log(n))$.
  3. Grâce aux deux résultats précédents, il est ensfin possible de réaliser un protocole de nommage (ou initialisation) des $n$ stations du réseau. Sa complexité moyenne en temps est alors linéaire, mais la propriété d'efficacité en énergie est conservée.
GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr