A simple mobility simulation with GraphStream

an iPhone  a Nexus 5  a Nokia lumia

An ad-hoc network

Random waypoint model


      

Implementation

We will use two Java classes:

We will start from these two classes that already implement a fully functional random waypoint simulation, and use GraphStream to represent the associated graph and make some measures on it.

The mobility simulation

The MobilitySimulation role is to register a set of MobileDevice objects and to run in a loop methods to make them move and to check which other mobile devices they can connect to.

The principal methods are:

The mobility simulation

The code is already in the tutorial, but incomplete, we will add a graph to represent the mobile device objects.

We will add two lines in the constructor MobilitySimulation (in orange), note that we refer to a field graph that is already present:

public MobilitySimulation() {
    graph = new SingleGraph("mobility model");
    graph.display(false);
    addMobileDevices(deviceCount);
    initConnectedComponents();
    for(int step=0; step<steps; step++) {
        moveMobileDevices();
        checkConnections();
        showConnectedComponents();
        sleep();
    }
}

The mobile devices

Now lets look at the MobileDevice. Here are the main methods:

The mobile devices

We will also add one field and complete the constructor.

Each device maps to a node in the global graph of the simulation:

protected Node node;
    
public MobileDevice(Graph graph, String name) {
    this.graph = graph;
    this.x = Math.random();
    this.y = Math.random();
    nextTarget();
    node = graph.addNode(name);
}

Specifying nodes position in the display

When the device moves, we must also tell the corresponding node representation in the display to move:

protected void move() {
    x += (targetx-x)*speed;     // Move a little (slow down at arrival).
    y += (targety-y)*speed;
    node.setAttribute("x", x); 
    node.setAttribute("y", y);
}

We use specific UI attributes to specify the abscissa and ordinate of the node.

Fist test

We have a valid code, we can start to test.


Try it !

Now lets add the connectivity !

We need first to know when a node is close to another.

We could use the x and y of the mobile device, but to show you how it works, we will use the coordinates of the node in the graph we set previously in move().

Remove the code in the closeTo() method and change it with:

protected boolean closeTo(Node other) {
    double otherxy[] = nodePosition(other);        
    return(Math.abs(x-otherxy[0]) < 0.07 && Math.abs(y-otherxy[1]) < 0.07);
}

nodePosition() is a static method in the GraphPosLengthUtils class that allows easy retrieval of the coordinate attributes in nodes. This class also allows to easily compute edges lengths for example.

The connectivity

We will now check the connections to create or remove due to the displacement of devices.

We will implement two sub-methods used by the checkConnectivity() method:

protected void checkConnections() {
    removeConnections();
    createConnections();
}

Removing connections

If a device moves too far away, the connections must disappear.

protected void removeConnections() {
    Iterator<?extends Edge> edges = node.getEdgeIterator();

    while(edges.hasNext()) {
        Edge edge = edges.next();
        if(!closeTo(edge.getOpposite(node))) {
            edges.remove();
        }
    }
}

We use an iterator on the set of edges of the graph, and get the opposite node of the edge. Using closeTo() we know if we must remove the edge with the iterator.

Exercise: we could also have used GraphPosLengthUtils.edgeLength().

Creating connections

Now we will create connections for devices that are now close enough.

protected void createConnections() {
    for(Node other: graph) {
        if(other != node && closeTo(other)) {
            if(!node.hasEdgeToward(other.getId())) {
                graph.addEdge(
                    String.format("%s-%s", node.getId(), other.getId()),
                        node.getId(), other.getId());
            }
        }
    }
}

We iterate on each node of the graph. We then test if the node is not us, and if it is close enough. If so, we check if no edge already exist (node.hasEdgeToward()), and then create the new connection with graph.addEdge().

That's it !

Try it !

Lets add a measure

We will add a dynamically updating measure on the graph: the number of connected components. We will also see how to add information on the graph, here the connected components count.

First we add two fields, one for the display on the graph, called a sprite, the other for the algorithm that will observe the graph and constantly update the number of components:

protected Sprite cc;
protected ConnectedComponents ccalgo; 

The ConnectedComponents class comes from the gs-algo package which contains lots of such algorithms.

Initializing a dynamic algorithm

The connected components only need to know the graph. After this it will update itself each time the graph changes.

We also use a SpriteManager to create a sprite, that is a graphical representation on the graph display, to add a label to print the number of connected components.

protected void initConnectedComponents() {
    ccalgo = new ConnectedComponents();
    ccalgo.init(graph);
    
    SpriteManager sm = new SpriteManager(graph);
    cc = sm.addSprite("cc");
    cc.setPosition(Units.PX, 10, 10, 0);
}

Displaying the connected components count

Now we display the measure, by updating the sprite at each simulation step:

protected void showConnectedComponents() {
    cc.setAttribute("ui.label", "Connected components " +
        ccalgo.getConnectedComponentsCount());
}

Adding some style

To make things more fancy, you can try adding a style sheet to the graph. In the MobilitySimulation() constructor, just after graph.display(), add:

...
graph.display(false);
graph.addAttribute("ui.antialias");
graph.addAttribute("ui.stylesheet",
    "edge { fill-color: grey; } sprite { size: 0px; }");
addMobileDevices(deviceCount);
...

Try it !

Slides and Material



Get the Slides and Materials online:

http://graphstream-project.org/doc/Tutorials/Lab-Sessions/ICCSA-2014/

https://github.com/graphstream/gs-talk/tree/iccsa2014 (branch iccsa2014)