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.