Algorithmique de la mobilité

↑ Accueil du cours


Learning the footprint in a periodic network (RESCOM Lab)

In this lab, we consider a mobility model where the nodes have periodical movements. As the nodes move, the links between them appear and disappear in a periodical way. The idea is to exploit this regularity in order to learn the footprint of the network (union of all the links over time). The entire process is completely distributed.

Setting up

The recommended IDE for this lab is IntelliJ IDEA.

Let us start with setting up a new project with JBotSim dependency. You can follow the dedicated tutorial, then come back here as soon as the HelloWorld works as expected.

Initial code

Q1. Create a new Java class called PeriodicNode with the following code:

import io.jbotsim.core.Node;
import io.jbotsim.ui.icons.Icons;

public class PeriodicNode extends Node {
    private double delta;

    @Override
    public void onStart() {
        setIcon(Icons.DRONE);
        if (Math.random() > 0.5) // with probability 1/2
            delta = -0.05; // will turn clockwise
        else
            delta = 0.05; // will turn counter-clockwise
    }

    @Override
    public void onClock() {
        setDirection((getDirection() - delta) % (2.0 * Math.PI));
        move(1);
    }   
}

So far, this code just specifies the way the nodes move in every round, and adds an icons of drone (you can adapt the size of the icon to your screen with setIconSize(), if needed).

Q2. Create a class PeriodicMain containing the following code:

import io.jbotsim.core.Topology;
import io.jbotsim.ui.JViewer;

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

The call to setDefaultNodeModel() tells JBotSim that the nodes should be of type PeriodicNode when they are created.

Q3. Execute PeriodicMain (right click > run) and add a few nodes using the mouse to test that everything is OK. You should see the nodes moving in circle.

Learning the temporal neighbors (i.e. neighbors in the footprint)

Q4 (Starting in a "paused" state). For simplicity, we would like that all the nodes start at the same time. For that, we can pause() the topology immediately after it is initialized as follows (then add the nodes while the time is not running). In the main method, add this line right after tp.start():

    ...
    tp.pause();

Now you can execute the new version, add a few nodes (they shouldn't move), and then resume the execution explicitly using the context menu (Right-click > "Resume execution").

The following behaviors should be implemented in the PeriodicNode class.

Q5 (Sending messages). In every round, we want that the nodes send empty messages to their neighbors in order to signify their presence.

Hint: The code consists of calling sendAll() in the onClock() method. The sendAll() method takes as argument an object of type Message, which you can initialize directly using new Message(). Note for later: in general the content of the message may be an object of any type (that will then be passed by reference).

Q6 (Receiving messages). Override the onMessage() method from the parent class Node as follows (or using "Ctrl+o" in IntelliJ)

    @Override
    public void onMessage(Message message) {

    }

This method is called automatically on the node when it receives a message. You only need to insert your code in order to process the received message.

Here, we would like to identify the sender of the message and add it to a set of (temporal) neighbors. You will need the following elements (in unsorted order): getSender() (class Message) returns the sender (an object of type Node). For simplicity, you are allowed to use this reference directly (but we could have used its identifier instead, through getID()). The set of neighbors can be stored, for example, using a HashSet (standard java API), that you can define as a field of your class as follows:

    Set<Node> temporalNeighbors = new HashSet<>();

Q7 (Testing). There are several ways to test your code. One of them is to override the onSelection() method and printing the set of neighbors as follows (or using "Ctrl+o" in IntelliJ)

    @Override
    public void onSelection() {
        System.out.println(temporalNeighbors);
    }

This method is called automatically when a node is selected using the middle click (or Ctrl+click). (You may have to pause the execution for clicking on a moving node... unless you are very quick :-))

Detecting when the temporal neighbors are known

Q8 (Offline question). How many rounds (i.e. number of onClock() executions) does it take for a node before it has completed an entire circle period? The exact answer is not an integer, thus we want to round it above.

Hint: the direction is modified by 0.05 radian in each round, and completing a circle is equivalent to the fact that the direction returns to its initial value. So, how many times 0.05 should be added to reach 2 * Pi?

Q9 (Detecting termination). We would like the nodes to detect themselves when they have completed a circle period. Using the answer to the previous question, add some code in the onClock() method to detect when the round number is above the desire value. You can then change the color of the node to make this visible.

Hint: The current round number can be obtained by calling the getTime() method. Initially, the round number is 0. The color of a node can be set using the setColor() method (with a color, for example Color.BLUE as argument). The value that you compute can be rounded above using Math.ceil().

Q10 (Offline question). Is it possible that a node discovers a new neighbor after the end of the first period? (Check your answer with us before going further.)

Learning the footprint based on multi-hop communication

Once the (temporal) neighbors are known, we want the nodes to share them with each other, so that eventually, all the nodes know the entire footprint of the network.

Concretely, the nodes should exchange all the information they have, and so, repeatedly. After one period, they thus know their 1-hop neighbors in the footprint (already done). After two periods, they should know their 2-hop neighborhood, and so on until they know the entire footprint.

Before continuing, you can make a copy of your code, as the following changes may break it temporarily

Q11. Create an appropriate field (i.e. a global variable) to store the footprint information. We suggest to use a map of sets, which indicate for each node (key of the map), the set of its neighbors (value of the map). The declaration is as follows.

    public Map<Node, Set<Node>> footprint = new HashMap<>();

The content of this object can be initialized in the onStart() method by adding an empty set of neighbors for the underlying node.

    footprint.put(this, new HashSet<>());

Q12 (sending the local version of the footprint). Instead of sending empty messages, we will now send our local version of the footprint. Thus, you should replace sendAll(new Message()) by

    sendAll(new Message(footprint));

Q13 (receiving another version of the footprint and merging it). Whenever a node receives a message from another node (containing this node's version of the footprint), it should now merge this information together with it own information. For simplicity, we provide the code below, make sure that you agree with it!

    @Override
    public void onMessage(Message message){
        footprint.get(this).add(message.getSender());
        Map<Node, Set<Node>> otherFootprint = (Map<Node, Set<Node>>) message.getContent();
        for (Node node : otherFootprint.keySet()) {
            if (!footprint.containsKey(node))
                footprint.put(node, new HashSet<>());
            footprint.get(node).addAll(otherFootprint.get(node));
        }
    }

Note that temporalNeighbors will not be used anymore, you can delete it and print instead the footprint in the onSelection() method.

Q14 (offline question about termination). Remember that the setting here is completely distributed. In particular, no one knows the number of nodes in the network. In this case, do you think that a node can detect when it knows the entire footprint? If no, why? If yes, how? (check your answer with us)

Q15 (visualizing the footprint). You can download this java file and add it to your project sources. It contains code for visualizing the footprint, as thick gray lines that remain permanently (whether the corresponding link is present or not). In order to use it, go to the main() method are replace the line

        new JViewer(tp);

by

        JViewer jViewer = new JViewer(tp);
        jViewer.getJTopology().addBackgroundPainter(new FootprintPainter());

The visualized footprint corresponds to the information contained in the footprint variable of one of the node (in fact, the first one that you created). If the network is not temporally connected, then it is normal that the footprint is limited to this node's temporal component.

What's next?

At this point, there are three choices, depending on what you prefer:

  1. Continuing this scenario: for instance, you may now exploit the footprint information. Typically, you may want to route a message along a shortest journey from a node to another (based on computing a min-hop path in the footprint).
  2. Exploring the other tutorials in JBotSim's website (> Examples > Quick tour)
  3. Create your own scenario!

We can help you with any of these options :-)