Algorithmique de la mobilité

↑ Accueil du cours


Espace toroidal

Lorsque les noeuds d'un réseau sont distribués aléatoirement sur une surface classique, ceux qui se trouvent proches du bord ont moins de voisins que ceux qui sont au centre. On parle d'effet de frontière (boundary effect). Ces effets, bien que réalistes, compliquent souvent l'analyse des algorithmes. Pour les éviter, on considère souvent un espace toroidal, c'est à dire qu'on recolle virtuellement le bord gauche et le bord droit, et idem pour les bords haut et bas, afin que les noeuds qui s'y trouvent ne soient pas pénalisés (voir la figure ci-dessous).

Espace toroidal.

JBotSim permet de redéfinir la manière dont les liens sont créés et dessinés, les deux étant gérés séparément.

Résolveur de lien

Par défaut, un lien existe entre deux noeuds sans fil s'ils sont plus proches qu'un certain seuil (portée de communication). Ce comportement par défaut est implémenté dans la classe LinkResolver (package io.jbotsim.core), dont on peut hériter et notamment surcharger la méthode isHeardBy(). La classe ToroidalLinkResolver du package io.jbotsim.contrib.geometry.toroidal illustre ce mécanisme en définissant un résolver de lien toroidal, dont le code est donné ci-dessous pour information.

package io.jbotsim.contrib.geometry.toroidal;

import io.jbotsim.core.LinkResolver;
import io.jbotsim.core.Node;
import io.jbotsim.core.Point;

/**
 * A new type of link resolver based on the toroidal distance between nodes.
 * Here, coordinates are assumed to be 2D (only) and nodes to be wireless.
 */

public class ToroidalLinkResolver extends LinkResolver {
    public double toroidalDistance(Node n1, Node n2){
        int width = n1.getTopology().getWidth();
        int height = n1.getTopology().getHeight();
        Point p1 = n1.getLocation();
        Point p2 = n2.getLocation();
        double distX = Math.abs((p1.getX() - p2.getX()));
        distX = Math.min(distX, width - distX);
        double distY = Math.abs((p1.getY() - p2.getY()));
        distY = Math.min(distY, height - distY);
        return Math.sqrt(distX*distX + distY*distY);
    }
    @Override
    public boolean isHeardBy(Node n1, Node n2) {
        return (toroidalDistance(n1, n2) < n1.getCommunicationRange());
    }
}

Pour utiliser ce résolveur, il suffit de remplacer celui par défaut comme suit :

    topology.setLinkResolver(new ToroidalLinkResolver());

Dessinateur de liens

Redéfinir le résolveur de lien est suffisant pour faire des simulations batch (c.à.d. sans GUI). Par contre, si ces liens sont dessinés, par défaut, ils traverseront la topologie d'un bout à l'autre, ce qui n'est pas très joli. Si l'on veut qu'ils soient dessinés aussi de manière toroidale (comme sur la figure en haut), alors il faut redéfinir le dessinateur de lien par défaut. La classe ToroidalLinkPainter du package io.jbotsim.contrib.geometry.toroidal.ui réalise cela en hérite du dessinateur par défaut en surchargeant la méthode paintLink(). Son code est donné ci-dessous pour information.

package io.jbotsim.contrib.geometry.toroidal.ui;

import io.jbotsim.core.Link;
import io.jbotsim.core.Point;
import io.jbotsim.core.Topology;
import io.jbotsim.ui.painting.JLinkPainter;

import java.awt.Graphics2D;

/**
 * A link painter that draws toroidal link in a toroidal fashion.
 * Each toroidal link is drawn using two lines (one for each node).
 * The tricky part is to decide when it is toroidal and over which coordinate.
 */
public class ToroidalLinkPainter extends JLinkPainter {

    protected void drawLine(Graphics2D g2d, Point p1, Point p2) {
        int srcX=(int)p1.getX(), srcY=(int)p1.getY();
        int destX=(int)p2.getX(), destY=(int)p2.getY();
        g2d.drawLine(srcX, srcY, (srcX+(destX-srcX)), (srcY+(destY-srcY)));
    }

    protected void toroidalPaint(Graphics2D g2d, Topology tp, Point p1, Point p2,
                         boolean wrapX, boolean wrapY){
        Point p1b = (Point) p1.clone();
        Point p2b = (Point) p2.clone();
        if (wrapX){
            if (p1.getX() < p2.getX()) {
                p1b.setLocation(p1b.getX() + tp.getWidth(), p1b.getY());
                p2b.setLocation(p2b.getX() - tp.getWidth(), p2b.getY());
            }else{
                p1b.setLocation(p1b.getX() - tp.getWidth(), p1b.getY());
                p2b.setLocation(p2b.getX() + tp.getWidth(), p2b.getY());
            }
        }
        if (wrapY){
            if (p1.getY() < p2.getY()) {
                p1b.setLocation(p1b.getX(), p1b.getY() + tp.getHeight());
                p2b.setLocation(p2b.getX(), p2b.getY() - tp.getHeight());
            }else{
                p1b.setLocation(p1b.getX(), p1b.getY() - tp.getHeight());
                p2b.setLocation(p2b.getX(), p2b.getY() + tp.getHeight());
            }
        }
        drawLine(g2d, p1, p2b);
        drawLine(g2d, p1b, p2);
    }

    @Override
    public void paintLink(UIComponent c, Link link) {
        Graphics2D g2d = (Graphics2D) c.getComponent();
        Point p1 = link.endpoint(0).getLocation();
        Point p2 = link.endpoint(1).getLocation();
        Topology tp = link.getTopology();
        boolean wrapX = (Math.abs((p1.getX() - p2.getX())) > tp.getWidth()/2);
        boolean wrapY = (Math.abs((p1.getY() - p2.getY())) > tp.getHeight()/2);
        if ( ! wrapX && ! wrapY )
            // The link is normal, use default painting
            super.paintLink(g2d, link);
        else
            // The link is toroidal, use special painting
            toroidalPaint(g2d, tp, p1, p2, wrapX, wrapY);
    }
}

Pour utiliser cette classe, il faut remplacer le dessinateur par défaut. Cela se fait sur l'objet de type JTopology qui se situe entre la Topology et le JViewer, comme suit :

    jviewer.getJTopology().setDefaultLinkPainter(new ToroidalLinkPainter());

ou bien

    jtopology.setDefaultLinkPainter(new ToroidalLinkPainter());

selon que vous utilisiez ou non une JTopology explicite.

Pour conclure, si vous utilisez à la fois le résolveur de lien toroidal et le dessinateur de lien toroidal, vous obtiendrez le même comportement que sur l'image du haut.