Skip to content

Implementing a routing or dissemination algorithm

Jump to bottom
Radu Ioan Ciobanu edited this page Sep 13, 2016 · 7 revisions

The most important step in implementing an opportunistic routing or dissemination algorithm in MobEmu is writing the data exchange function. However, prior to presenting how this is done, we start by describing the steps taken by MobEmu when two nodes are in contact.

When two MobEmu nodes meet opportunistically (based on the data contained in the trace), the exchangeData function from the Node class is called by the observer node. This function receives the observed node as a parameter, as well as the duration of the contact and the current trace time. If a contact between the two nodes is already in progress then the function simply returns. However, if the contact just began, the onDataExchange function is called. This is an abstract function that should be implemented by any class that extends Node.

Thus, all that is required for writing a routing or dissemination algorithm is implementing the onDataExchange function, but there are several guidelines that should be followed. Firstly, since the first parameter of the onDataExchange function is of type Node, it should be checked if it is indeed an instance of the implementing class, and cast to it. Then, the next step is generally to perform the delivery of direct messages, which are messages destined for the current node (when dealing with routing) or marked with tags that the node is interested in (if disseminating data). This is done by calling the deliverDirectMessages method. Then, the messages from an encountered node’s data memory and own memory (i.e. the messages it generated itself) are analyzed and, based on an algorithm-specific decision, they are downloaded by the current node or not. A message is downloaded by calling the insertMessage function at the current node. If the network bandwidth is considered restricted, then the user must ensure that more messages than allowed per contact are not downloaded. Altruism can also be taken into account when performing data exchanges upon a contact, but it is the programmer’s job to decide whether a node is selfish or not, and whether it should not be helped by other nodes.

Statistics are collected automatically, so the user does not need to do this explicitly, unless more stats are needed. For this, new fields should be added to the Node implementation, and they should be updated when necessary, by extending the corresponding functions. Furthermore, the statistics are aggregated by using the Stats class, which should be extended, and methods for various statistics should be added as desired.

A user may also wish to change the way messages are generated. Currently, this is done daily, in a time interval around lunch (since this is generally when the most contacts occur for the majority of the traces). If the current algorithm performs point-to-point routing, then messages are generated by default using a Zipf distribution with exponent 1, where the most messages are sent to nodes that are both in a node’s community, as well as in its online social network, and the fewest to nodes that have no connection to the current node. If dissemination is performed, a node chooses a random interest, and generates a message marked with it. The generateMessages function from the Message class can be overridden if a new message generation behavior is desired.

MobEmu currently has implementations for the following opportunistic routing and dissemination solutions:

Example

As an example, let's implement a routing and dissemination solution that, upon a contact between two nodes, randomly decides if a message should be exchanged. For each message in an encountered node's data memory, our algorithm generates a random number between 0 and 1 and, if the number if greater than 0.5, the message is downloaded.

The first step is to create a new class that extends from the Node class. Since we wish to implement our algorithm for both dissemination and routing, we will allow the user of our class to specify how the algorithm should be run. Furthermore, we will also allow the user to specify whether node altruism should be taken into account or not. Thus, the first part of our class looks as follows:

public class MyAlgorithm extends Node {

    private boolean dissemination;
    private boolean altruismAnalysis;
    private Random rand;

    public MyAlgorithm(int id, int nodes, Context context, boolean[] socialNetwork,
                       int dataMemorySize, int exchangeHistorySize, long seed,
                       long traceStart, long traceEnd, boolean dissemination,
                       boolean altruism) {
        super(id, nodes, context, socialNetwork, dataMemorySize,
              exchangeHistorySize, seed, traceStart, traceEnd);

        this.dissemination = dissemination;
        this.altruismAnalysis = altruism;
        this.rand = new Random(seed);
    }

    [...]

}

We have only added two new parameters to the constructor, dissemination and altruismAnalysis, the rest are the same as the default constructor of the Node class.

There are two abstract methods that have to be implemented when extending the Node class. The first one is getName, which specifies the algorithm's name:

@Override
public String getName() {
    return "My Algorithm";
}

The other one is onDataExchange, called when two nodes begin a contact. In order to implement it, we first need to implement our random selection method:

private boolean shouldDownload() {
    return rand.nextDouble() >= 0.5;
}

The onDataExchange method receives three parameters: the encountered node (whose messages are analyzed and the ones of interest to the current node are downloaded), the duration of the contact, and the current trace time. Our custom algorithm first downloads messages it is interested in, then cycles through the encountered node's data memory and through the messages it has generated, applies our random selection function (shouldDownload), and then downloads a message if the function returns true. The implementation is straightforward and can be seen below:

@Override
protected void onDataExchange(Node encounteredNode, long contactDuration, long currentTime) {
    // check if the encountered node is also an instance of MyAlgorithm
    if (!(encounteredNode instanceof MyAlgorithm)) {
        return;
    }

    // cast encountered node to MyAlgorithm
    MyAlgorithm myEncounteredNode = (MyAlgorithm) encounteredNode;

    // deliver the message intended for the current node, and compute how many
    // messages can be downloaded for the duration of the contact
    int remainingMessages = deliverDirectMessages(myEncounteredNode, altruismAnalysis,
                                                  contactDuration, currentTime, dissemination);

    int totalMessages = 0;

    // download each message in the encountered node's data memory that
    // is not in the current node's memory, with a 50% probability
    for (Message message : myEncounteredNode.dataMemory) {
        // if the function returns false, skip to next message
        if (!shouldDownload()) {
            continue;
        }

        // verify if there is still time to download additional messages
        if (totalMessages >= remainingMessages) {
            return;
        }

        // add message to current node's memory
        insertMessage(message, myEncounteredNode, currentTime, altruismAnalysis, dissemination);
        totalMessages++;
    }

    // download each message generated by the encountered node that
    // is not in the current node's memory, with a 50% probability
    for (Message message : myEncounteredNode.ownMessages) {
        // if the function returns false, skip to next message
        if (!shouldDownload()) {
            continue;
        }

        // verify if there is still time to download additional messages
        if (totalMessages >= remainingMessages) {
            return;
        }

        // add message to current node's memory
        insertMessage(message, myEncounteredNode, currentTime, altruismAnalysis, dissemination);
        totalMessages++;
    }
}

We used the two variables added to the constructor (dissemination and altruismAnalysis) when calling the deliverDirectmessages and insertMessage functions, since they both work for routing and dissemination, and they also allow the analysis of selfish behavior in opportunistic nodes.

Clone this wiki locally