Routage géographique dans les réseaux de capteurs
On parle de routage géographique, ou georouting, lorsque la destination d'un message est spécifiée sous forme de coordonnées. Il peut s'agir des coordonnées d'un noeud (destinataire), où d'un point quelconque, par exemple pour demander quelle température il fait à un endroit précis (information localisée). Parfois, la cible du routage est une zone entière (p.ex. rectangle ou cercle) et le message doit alors atteindre tous les noeuds qui s'y trouvent -- on parle de geocasting -- mais nous n'étudierons pas ce cas là aujourd'hui. On supposera toujours que les noeuds connaissent leurs coordonnées exactes.
Protocole simple (glouton)
Supposons que la destination correspond aux coordonnées exactes d'un noeud et que le réseau est suffisamment dense (de manière homogène). Dans ce cas, il existe un protocole de routage très simple, qui consiste à exécuter l'algorithme suivant sur chaque noeud:
Algorithme 1: Quand je reçois un message, je regarde quelle est sa destination. S'il s'agit de mes propres coordonnées, alors le routage est terminé. Sinon, je transmets le message à celui de mes voisins qui s'approche le plus de la destination.
Cet algorithme est illustré ci-dessous, pour un noeud de départ donné (le plus à gauche) et un noeud destinataire donné (drapeau rouge).
Figure 1. Routage géographique dans les réseaux de capteurs.
Nous allons implémenter cet algorithme, dont nous étudierons les limitations ensuite.
Partie générique
Pour rappel, JBotSim permet d'envoyer n'importe quel objet dans vos message (p.ex. send(noeud, new Message(objet))). Lorsqu'un message est reçu, cet objet peut être récupéré via la méthode getContent() du message. Dans le cas du routage géographique, nous souhaitons ajouter des informations sur les coordonnées du destinataire. Nous allons donc commencer par créer une classe Bundle qui encapsulera ces coordonnées ainsi que l'objet du message lui-même (pour simplifier, disons une chaîne de caractère).
import io.jbotsim.core.Point;
public class Bundle {
public Point target;
public String text;
public Bundle(Point target, String text) {
this.target = target;
this.text = text;
}
}Le contenu de nos messages sera donc de type Bundle. Créons maintenant une nouvelle classe de noeud GeoNode, dont le squelette est fourni ci-dessous.
import io.jbotsim.core.Color;
import io.jbotsim.core.Message;
import io.jbotsim.core.Node;
public class GeoNode extends Node {
@Override
public void onMessage(Message message) {
Bundle bundle = (Bundle)message.getContent();
if (bundle.target.equals(getLocation())) {
System.out.println("Message reçu : " + bundle.text);
}else{
route(bundle);
}
}
public void route(Bundle bundle){
setColor(Color.red);
// Travail à faire
}
}Pour l'instant, cette classe est très simple. Lorsqu'on reçoit un message (c.f. onMessage() ci-dessus), on récupère le bundle pour tester si nous en sommes le destinataire. Si oui, on affiche le message et l'algorithme est terminé. Si non, on transmet le bundle à la méthode route(), qui doit décider à quel voisin l'envoyer. C'est dans cette méthode que vous ajouterez vos contributions.
Le code générique de l'application est donné ci-dessous dans la classe MainGeorouting. En particulier, cette classe ajoute du code permettant de détecter (globalement) lorsque la source et la destination sont sélectionnées à l'aide de la souris (Clic molette ou Ctrl+Clic). Cela se fait via la méthode onSelection(). Note : cette méthode existe nativement dans la classe Node, mais ici nous voulons traiter l'événement globalement dans la classe MainGeorouting, d'où l'usage explicite de l'interface SelectionListener et de la méthode addSelectionListener.
La première fois que onSelection() est appelée, on mémorise le noeud correspondant comme source, la deuxième fois on le mémorise comme destinataire. Sitôt ces deux noeuds connus, le bundle est créé et on appelle la méthode route() sur le noeud source pour démarrer le routage, qui s'exécutera à partir de là de manière distribué.
import io.jbotsim.core.Color;
import io.jbotsim.core.Node;
import io.jbotsim.core.Topology;
import io.jbotsim.core.event.SelectionListener;
import io.jbotsim.ui.JViewer;
import io.jbotsim.ui.icons.Icons;
public class MainGeorouting implements SelectionListener{
Topology tp;
GeoNode sourceNode;
GeoNode targetNode;
public MainGeorouting() {
tp = new Topology();
tp.setTimeUnit(100); // slow down for visualization
tp.setDefaultNodeModel(GeoNode.class);
tp.addSelectionListener(this);
new JViewer(tp);
tp.start();
}
@Override
public void onSelection(Node node) {
GeoNode selectedNode = (GeoNode) node;
if (sourceNode == null) {
sourceNode = selectedNode;
sourceNode.setColor(Color.red);
} else if (targetNode == null){
targetNode = selectedNode;
targetNode.setIcon(Icons.FLAG);
targetNode.setIconSize(14);
sourceNode.route(new Bundle(targetNode.getLocation(), "HELLO"));
}
}
public static void main(String[] args) {
new MainGeorouting();
}
}Q1. Recopier ces trois classes et les tester, notamment en sélectionnant deux noeuds l'un après l'autre à l'aide de la souris.
La topologie correspondant à la Figure 1 (plus haut) est disponible dans le fichier georouting1.tp. Vous pouvez le charger une fois le programme lancé, en choisissant Load Topology depuis le menu contextuel (clic droit sur la topologie) et en vous rendant là où vous l'avez sauvegardé.
Q2. Implémenter l'algorithme de routage vu précédemment. Pour simplifier, on s'autorisera à récupérer la liste des voisins directement via getNeighbors() et à tester leur distance à la destination via la méthode distance(). Pour être plus réaliste, les noeuds devraient s'échanger leurs positions par des messages, mais cela compliquerait l'implémentation et nous autorisons cette simplification.
→ À chaque envoi de message, dessiner en gras l'arête utilisée de sorte à visualiser le chemin emprunté (comme sur la figure). De même, colorier en rouge le noeud qui a le message actuellement et le faire passer en bleu une fois qu'il a envoyé le message.
Astuce. Pour éviter de re-déployer votre topologie à chaque fois, vous pouvez ajouter à votre classe MainGeorouting() la possibilité de "redémarrer" l'exécution sur la même topologie. Pour cela, il faut implémenter l'interface StartListener en plus de l'interface SelectionListener déjà implémentée.
public class MainGeorouting implements SelectionListener, StartListener{Dans le constructeur, s'enregistrer comme listener pour cet événement.
tp.addStartListener(this);Et enfin coder la méthode correspondante, pour réinitialiser tous les états de la simulation.
@Override
public void onStart() {
if (targetNode != null) {
targetNode.setIcon(Icons.DEFAULT_NODE_ICON);
targetNode.setIconSize(10);
targetNode = null;
}
sourceNode = null;
for (Node node : tp.getNodes())
node.setColor(null);
for (Link link : tp.getLinks())
link.setWidth(1);
}Ce code sera exécuté à chaque fois que vous cliquerez sur "restart nodes" dans le menu contextuel.
Optimum local
L'algorithme glouton vu précédemment fonctionne bien tant qu'il existe suffisamment de noeuds sur le chemin vers la destination. Malheureusement, ce n'est pas toujours le cas comme illustré par la figure ci-dessous, qui représente un scénario très légèrement différent du précédent, et où le message reste coincé dans un optimum local. Autrement dit, il n'existe pas de voisin qui nous rapproche de la destination.
Figure 2. Message bloqué dans un optimum local.
La topologie correspondant à cette figure peut être téléchargée ici. Elle est très légèrement différente de la précédente, mais suffit pour changer la route. Vous pouvez aussi utilisez une troisième topologie ayant de nombreuses zones vides ici.
Q3. Concevoir et implémenter une variante du protocole précédent permettant de résoudre ce problème. On pourra envisager une solution probabiliste (simple), puis une solution géométrique (un peu moins simple) pour contourner les espaces vides. Faites valider votre stratégie auprès de l'enseignant avant de vous lancer dans l'implémentation.
Bonus : Geocasting
Nous considérons maintenant une nouvelle variante du problème, où la destination n'est plus spécifiée par un point, mais par une zone rectangulaire (caractérisée par deux points : haut-gauche et bas-droite). Vous devez faire en sorte que tous les noeuds dans la zone reçoivent le message. Cette variante est motivée, par exemple, par le fait d'envoyer un message d'information à tous les véhicules qui se trouvent dans une certaine zone géographique. Une difficulté supérieure est que les noeuds à l'intérieur de la zone ne forment peut-être pas graphe connexe. Là aussi, faites valider votre solution auprès de l'enseignant avant de l'implémenter.