Algorithmique de la mobilité

↑ Accueil du cours


Toroidal space

When the nodes are distributed randomly, those which are close to the borders happen to have less neighbors than those in the middle. This boundary effect often makes it harder to analyze properties of the resulting topology as well as algorithms running on top of it. This effect can be avoided by considering a toroidal space, that is, a space wrapped up on the borders so that rightmost nodes can communicate with leftmost ones (and same for top and bottom). As a result, the various properties of the network, such as connectivity, degree distribution, or centrality of nodes are uniform, which is nicer. Here is what a toroidal space looks like.

Toroidal space.

JBotSim allows you to redefine the way links are created and drawn, both being handled separately.

Link resolver

By default, a link exists between two wireless nodes if they are closer than some threshold (communicaton range). This behavior is implemented in the class LinkResolver (package io.jbotsim.core), which can be extended to override the method isHeardBy(). Class ToroidalLinkResolver of package io.jbotsim.contrib.geometry.toroidal (whose code is given below for information) provides a simple toroidal link resolver based on such mechanism.

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());
    }
}

This resolver can then be used as follows:

    topology.setLinkResolver(new ToroidalLinkResolver());

Link painter

Defining the link resolver is enough for batch simulation (e.g. without GUI), but if toroidal links are to be drawn, by default, they will cross the surface from one side to another, which is ugly. To draw them as in the picture above, one must redefine the way those links are drawn. This is done by class ToroidalLinkPainter in package io.jbotsim.contrib.geometry.toroidal.ui, which

extend the default link painter and overrides the paintLink() method. The code is shown below, for 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);
    }
}

Finally, the default link painter can be replaced by the new one. This is done on the JTopology object that fits in between the Topology and the JViewer, as follows:

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

or

    jtopology.setDefaultLinkPainter(new ToroidalLinkPainter());

depending on whether the JTopology object is already used explicitly.

Finally, using both the toroidal resolver and the toroidal painter should result in the same behavior as shown in the picture above.