Algorithmique de la mobilité

↑ Accueil du cours


Construction distribuée d'un arbre couvrant

Principe général

Étant donné un réseau et un noeud de départ, il est très facile de construire un arbre couvrant de manière distribuée. Le noeud de départ envoie un message à tous ses voisins. La première fois qu'un noeud reçoit un tel message, il choisit le voisin de qui il l'a reçu comme parent, puis il envoie à son tour le message à ses voisins. Cette propagation au sein du réseau va ainsi définir un arbre dont la racine est le noeud de départ (illustration ci-dessous).

wireless network  →  spanning tree

Construction distribuée d'un arbre couvrant.

Implémentation avec JBotSim

On définit une classe TreeNode qui hérite de Node. Deux événements sont gérés (surchargés) :

  1. La sélection d'un noeud par l'utilisateur (bouton du milieu de la souris), via la méthode onSelection().
  2. L'arrivée d'un message sur un noeud, via la méthode onMessage().

Le code correspondant est donné ci-dessous et expliqué en détail juste après. Il est important de bien comprendre cet algorithme, car il représente un prototype classique pour beaucoup d'autres algorithmes.

import io.jbotsim.core.Color;
import io.jbotsim.core.Message;
import io.jbotsim.core.Node;

import java.util.ArrayList;
import java.util.List;

public class TreeNode extends Node {
    Node parent = null;
    List<Node> children = new ArrayList<>();

    @Override
    public void onSelection() {
        parent = this;
        setIconSize(20);
        sendAll(new Message("", "CONSTRUCTION"));
    }

    @Override
    public void onMessage(Message message) {
        if (message.getFlag().equals("CONSTRUCTION")) {
            if (parent == null) {
                parent = message.getSender();
                getCommonLinkWith(parent).setWidth(4);
                send(parent, new Message("", "ADOPTION"));
                sendAll(new Message(message));
            }
        }else if (message.getFlag().equals("ADOPTION")) {
            children.add(message.getSender());
        }
    }
}

Explications détaillées : Lorsque l'utilisateur sélectionne un noeud (clic molette ou Ctrl+clic), la méthode onSelection() est appelée sur ce noeud et le code que l'on y a placé est exécuté. Ici, le traitement consiste à établir ce noeud comme racine en faisant pointer la variable parent sur lui-même (parent = this;), en agrandissant ton icône, et enfin en initiant la construction de l'arbre par l'envoi d'un message à tous ses voisins dans le réseau via sendAll(). Afin de pouvoir filtrer différents types de messages lors de la réception, nous utilisons des flags pour les différents types de messages, ici "CONSTRUCTION" pour la construction de l'arbre. Le contenu du message lui-même est laissé vide.

Lorsqu'un noeud reçoit un message de type "CONSTRUCTION" (dans la méthode onMessage()), s'il n'avait pas encore de parent, alors il choisit l'émetteur de ce message comme parent et dessine en gras le lien correspondant. Il informe alors son parent en lui envoyant un message de type "ADOPTION" et propage à tous ses voisins le message de "CONSTRUCTION". Enfin, lorsqu'un noeud reçoit un message de type "ADOPTION", il sait que le voisin qui lui a envoyé ce message l'a choisi comme parent. Il ajoute donc ce voisin dans la liste de ses enfants.

Test : Vérifiez le bon fonctionnement de cette classe via la méthode main() suivante.

public static void main(String[] args) {
    Topology tp = new Topology();
    tp.setDefaultNodeModel(TreeNode.class);
    tp.setTimeUnit(500);
    new JViewer(tp);
    tp.start();
}

Hériter de TreeNode ?

Si votre algorithme repose sur un mécanisme d'arbre couvrant, vous pouvez hériter à votre tour de TreeNode. Il faut être prudent, cependant, lorsque vous surchargerez la méthode onMessage(). En effet, plusieurs types de messages peuvent co-exister entre la classe mère et la classe fille. La solution ici serait, par exemple, que la classe fille délégue à la classe mère la gestion des messages dont le flags est "CONSTRUCTION" ou "ADOPTION", en appelant super.onMessage() dans sa propre méthode onMessage(), avant de traiter elle-même les autres types de messages.