Geographical routing in wireless sensor networks

We speak of geographical routing, or georouting, when the destination of a message is specified in terms of coordinates. These coordinates may be that of a given node or a particular location (e.g. what is the temperature at a given place?). In some cases, it corresponds to a whole area such as a circle or a rectangle, and all the nodes within this area must get the message, but then we speak of geocasting and this is not our focus today.

Simple (greedy) protocol

Assume the target coordinates are those of a node, and the network in rather dense and homogeneous (in a sense that will become clear later). Then, we can use a very simple routing protocol that consists in executing the following algorithm at each node:

Algorithm 1: When I receive a message, check if the target coordinates are mine. If so, then routing is complete. Otherwise, find out which local neighbor is the closest (in terms of euclidean distance) to the target and send the message to it.

This algorithm is illustrated below, for a given source node (leftmost) and a target node on the right side (red flag).

Figure 1. Geographical routing in a wireless sensor network.

Let us implement this algorithm in JBotSim and then study its limitations.

Generic part

In JBotSim, the content of a message can be any kind of object (e.g. send(neighbor, new Message(object))). When a message is received, this object can be retrieved using getContent(). In the case of geographical routing, we must include some information about the target coordinates into the content. Thus, we start by creating a Bundle class which will include those coordinates in addition to the original content of the message (for simplicity, we will assume a simple string).

import io.jbotsim.core.Point;

public class Bundle {
    public Point target;
    public String text;

    public Bundle(Point target, String text) {
        this.target = target;
        this.text = text;
    }
}

Hence, the content of our messages will be of type Bundle. Let us now create the class GeoNode, which we will use as the model of node by default, and whose skeleton is given below.

import io.jbotsim.core.Color;
import io.jbotsim.core.Message;
import io.jbotsim.core.Node;

public class GeoNode extends Node {
    @Override
    public void onMessage(Message message) {
        Bundle bundle = (Bundle)message.getContent();
        if (bundle.target.equals(getLocation())) {
            System.out.println("Message reçu : " + bundle.text);
        }else{
            route(bundle);
        }
    }
    public void route(Bundle bundle){
        setColor(Color.red);
        // Make a routing choice (work to do)
    }
}

For now, this class is rather simple. When a message is received (onMessage() method), the node first extract the bundle and tests if its coordinates are equal to the target location. If so, the message text is printed and the algorithm terminates. Otherwise, the message is passed to the route() method, which is in charge of selecting the local neighbor to which the message should be sent next. The main exercices below consist of working out this method.

The generic code of the simulation is given in the MainGeorouting class below. In particular, this class adds some code to ease interaction with the user, by having the user select the source node and target node using the mouse (middle-click on PCs, command-shift-click on MACs). Those selections are handled in a onSelection() method inherited from the SelectionListener interface of JBotSim and subscribed to through addSelectionListener on the topology. (Note that this method was also available natively in class Node, but here we want to handle selection globally.)

The first time onSelection() is called, we record the corresponding node as the source; the second time we record it as the target, then the bundle is created and we call the route() method on the source node, which starts the routing process (after that, it keeps on going in a distributed way).

import io.jbotsim.core.Color;
import io.jbotsim.core.Node;
import io.jbotsim.core.Topology;
import io.jbotsim.core.event.SelectionListener;
import io.jbotsim.ui.JViewer;
import io.jbotsim.ui.icons.Icons;

public class MainGeorouting implements SelectionListener{
    Topology tp;
    GeoNode sourceNode;
    GeoNode targetNode;

    public MainGeorouting() {
        tp = new Topology();
        tp.setTimeUnit(100); // slow down for visualization
        tp.setDefaultNodeModel(GeoNode.class);
        tp.addSelectionListener(this);
        new JViewer(tp);
        tp.start();
    }

    @Override
    public void onSelection(Node node) {
        GeoNode selectedNode = (GeoNode) node;
        if (sourceNode == null) {
            sourceNode = selectedNode;
            sourceNode.setColor(Color.red);
        } else if (targetNode == null){
            targetNode = selectedNode;
            targetNode.setIcon(Icons.FLAG); 
            targetNode.setIconSize(14);
            sourceNode.route(new Bundle(targetNode.getLocation(), "HELLO"));
        }
    }

    public static void main(String[] args) {
        new MainGeorouting();
    }
}

Q1. Copy all those classes and check that everything works well.

The topology shown in Figure 1 (above) is available in file georouting1.tp. Once downloaded, you can use it through the context menu (right click on the background) > Load Topology.

Q2. Now implement the simple routing algorithm discussed above. To keep it simple, you are allowed to access directly the list of neighbors from within the route() method, using getNeighbors() on the underlying node. You are also allowed to use the distance() method directly on the node object representing each neighbor. A strict distributed algorithm should rather use extra messages to exchange positions with neighbors. However, there is not much to be said algorithmically about these exchanges, thus better focus on the high-level logic.

→ In each sending, draw in bold the link being used for visualization (as in the picture above). Also color in red the node which has the message currently and make it blue afterwards.

Tip. In order to avoid re-deploying the topology in each execution, you may add to your MainGeorouting() class the faculty to "restart" execution on top of the current topology. For that, implement the StartListener interface as follows (in addition to the SelectionListener interface already implemented).

public class MainGeorouting implements SelectionListener, StartListener{

In the constructor, subscribe as a listener to start events as follows.

tp.addStartListener(this);

And finally you can fill in the onStart() method, adding the code for reinitializing all the states.

    @Override
    public void onStart() {
        if (targetNode != null) {
            targetNode.setIcon(Icons.FLAG);
            targetNode.setIconSize(10);
            targetNode = null;
        }
        sourceNode = null;
        for (Node node : tp.getNodes())
            node.setColor(null);
        for (Link link : tp.getLinks())
            link.setWidth(1);
    }

This code will be executed each time the user clicks on the "restart nodes" item of the context menu.

Local optimum

The greedy approach discussed above works well so long as the network is dense and homogeneous enough to guarantee that whatever the current node is, a neighbor exists that offers (euclidean) progress towards the target. Unfortunately, this may not be the case, as shown on this slightly modified example, where the message get stuck in a local optimum.

Figure 2. Geographical routing vs local optimum.

The topology corresponding to this scenario can be downloaded here. It is slightly different to the one before, but sufficiently so to reveal the problem.

Q3. Solve this problem. There are many possible approaches.