Connexité dans les réseaux sans fil

Dans cette leçon, nous allons étudier le déploiement aléatoire de noeuds sans fil (ou graphes géométriques aléatoires) et les propriétés de connexité qui en résultent.

Déploiement aléatoire de noeuds sans fil

Q1. Créer une topologie et un viewer depuis la méthode main() d'une classe quelconque.

Q2. Créer une méthode statique deploy() qui prend en argument une topologie et un nombre de noeuds et (sans surprise) y déploie ce nombre de noeuds. Vous utiliserez l'une des variantes de la méthode addNode() de la classe Topology. Le déploiement doit être aléatoire uniforme (ce que vous entendez générallement par aléatoire tout court), à savoir qu'un noeud a la même probabilité d'être n'importe où dans la surface.

Q3. Testez cette méthode; vous devriez obtenir quelque chose qui ressemble à la figure ci-dessous.

Déploiement aléatoire.

Ce type de graphe, où l'existence d'un lien dépend de la distance et où les noeuds sont placés aléatoirement est appellé graphe géométrique aléatoire. Dans l'exemple ci-dessus, ce graphe est connexe car il forme une seule composante dans laquelle tous les noeuds peuvent se joindre (directement ou via un chemin). Selon la portée de communication et le nombre de noeuds, il est possible que le graphe ne soit pas connexe.

Q4. Tester la variante toroidale de ce déploiement, qui nous servira par la suite.

Seuil de connexité

Nous allons maintenant tenter de retrouver expérimentalement le seuil à partir duquel un tel graphe devient connexe quasi-certainement. Cette valeur intervient souvent dans les réseaux ad hoc et peut avoir des applications concrètes (moyennant quelques adaptations), comme le fait de comprendre combien de capteurs doivent être distribués dans une zone à surveiller.

Q5. Lire la page sur le théorème de Penrose, qui caractérise de manière théorique la valeur de seuil qui nous intéresse ici. C'est ce résultat que nous allons tenter de retrouver expérimentalement.

Q6. Fixer les dimensions de la topologie à 1 x 1 (carré unitaire) et activer la détection toroidale de liens comme vu précédemment. En revanche, puisqu'on ne verra rien dans une si petite surface et que nous avons aussi besoin de disponibilité CPU pour les expérimentations, désactivons complètement le viewer en ne le créant pas (idem, bien sûr, pour le dessin des liens toroidaux). Enfin, nous pouvons mettre l'horloge en mode "vitesse maximale" en appelant .setTimeUnit(0) sur la topologie.

Q7. Créer une méthode runExperiment() avec quatres arguments : une topologie, un nombre de noeuds n, une portée de communication cR (pour communication range) et un nombre d'itération nbIter. Cette méthode retournera une probabilité sous forme d'un double entre 0 et 1. Le comportement de cette méthode sera:

Régler la portée de communication de la topologie sur cR.
Déployer n noeuds aléatoirement et tester si le graphe résultant est connexe (vous pouvez utiliser la classe Connectivity (package io.jbotsim.contrib.algos) pour faire le test).
Répéter l'étape 2 un nombre nbIter de fois, en vidant la topologie entre chaque déploiement.
Retourner la proportion du nombre des déploiements où le graphe a été connexe.

Q8. Prendre n=10 et invoquer la méthode runExperiment() en faisant varier à chaque fois la portée de communication à l'aide d'une boucle. Afin d'être statistiquement fiable, fixez le paramètre nbIter au moins à 100. Affichez pour chaque portée dans le terminal une ligne avec cette portée et le résultat de runExperiment(), séparés par un caractère de tabulation.

Q9. En s'aidant de cet exemple (si besoin), tracer la courbe correspondante sous gnuplot. La courbe ainsi dessinée devrait faire apparaître la transition de phase entre non-connexe et connexe. Le rendu peut être amélioré en spécifiant smooth bezier dans les paramètres de la ligne de commande gnuplot.

Q10. Identifier le milieu de la transition de phase, à savoir la portée pour laquelle la probabilité de connexité est à 0.5. C'est cette valeur qui correspond au seuil de la formule de Penrose. On peut donc comparer cette valeur à $r=\sqrt{\frac{\ln n}{\pi n}}\ $. De combien est cette erreur ? (Notez-là en commentaire dans votre code.)

Q11. Reproduire cette expérience pour n=100, puis pour n=1000, en notant l'erreur obtenue (en commentaire dans votre code). Qu'en déduisez-vous ? Note : selon la puissance de votre machine, il faudra faire preuve d'astuce pour réduire le temps de calcul. Par exemple, ne pas balayer tout l'intervalle [0,1] pour la portée de communication, ou réduire le nombre d'itération le temps d'identifier approximativement le seuil (puis rétablir le nombre d'itération en ne balayant que ces valeurs là).