## A simple mobility simulation with GraphStream

• People with mobile communicating devices are moving in a given place.
• Their devices have a limited range of communication with others.
• Each time they are close enough, a connection is created to exchange data.
• This connection disappears as soon as they are too far.
• We use a graph to represent the devices as nodes and the connections as edges.

• The ad-hoc network created through this process is dynamic: links appear and disappear.
• It can be modeled by a dynamic graph where devices are nodes and communication links are edges.
• We will now model such mobile devices behavior and the resulting dynamic graph with Java classes using GraphStream.

## Random waypoint model

• We will use the “random waypoint” mobility model:
• Each person equipped with a mobile device chooses a random destination,
• Walks with a random speed toward it,
• And stands still at this position for a random time.

## Implementation

We will use two Java classes:

• MobileDevice, represents a moving person with a communication device,
• MobilitySimulation, represents a set of persons and runs the simulation.

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.

• Open eclipse and find the mobility directory in the gs-iccsa14 project,
• An open an editor on MobilitySimulation.

## 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:

• MobilitySimulation() the constructor, inits and runs the simulation.
• addMobileDevices() registers a set of mobile devices in the simulation.
• moveMobileDevices() makes each device move toward its target or wait.
• checkConnections() sees toward which mobile devices connections can be made or removed

## 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);
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:

• MobileDevice() Builds a new mobile device knowing its name and the global graph.
• next() Chooses the next action to do.
• closeTo() True if the devices is close to another one.
• nextTarget() Chooses a next target destination.
• move() Move a little toward the target.
• atTarget() True if arrived at target.
• checkConnections() Check new connections or connections to remove.

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

## 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.

• Only nodes will move.
• No edges will be drawn.

# 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())) {
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().

# Try it !

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

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);
...
https://github.com/graphstream/gs-talk/tree/iccsa2014 (branch iccsa2014)