Opportunistic Routing

Introduction

Most conventional approaches for routing in MANETs (mobile ad-hoc networks) use a model, which is deviated from the wired model: Each pair of nodes is seen either as linked or not linked, only linked nodes can communicate directly:

As this figure shows, the model sees all nodes within a certain range of each other to be linked, all other nodes to be not linked. This enables protocols known from wired networks to be applied: Static routes are chosen before a packet is sent through the network. Unfortunately, this masks all the wonderful wireless characteristics: In wireless networks, all nodes - in principle - can communicate with each other:

The error rate may be high, but most pairs of nodes have at least a minimal chance of hearing each others packets (in a non-deterministic manner). Even more: Every node receives all packets which are sent by all of its neighbours, which is a difference to wired networks where all communication is somehow directed. The new approach, called "Extremely Opportunistic Routing" (ExOR) tries to use the advantages of these characteristics, to create a more powerful routing protocol for MANETs.

Idea behind ExOR

Instead of chosing a static route ahead of time, ExOR defers the choice of the next forwarding node until the reception of the packet which is to be routed. The forwarding is done by the node closest to the destination, so the route is built dynamically. Using a mechanism of acknowledgements (ACKs), we can ensure, that only one node forwards the packet.

Let's look at an example transmission, taking place in the network represented by the following figure, where the edges are labeled with the delivery ratios (= propability of reception):

Assume, we want to send a packet from node A to node D. One extreme would be to send the packet directly - at the expense of sending it multiple times because of likely losses. The other extreme is a 3-hop route through B and C - at the expense of sending the packet 3 times. Imagine you are sitting in a crowded pub and want to pass a message to a friend on the other side of the room. You could tell it someone directly sitting next to you, but it will take a long time until it reaches your friend (apart from some serious Chinese whispers effects, which - I admit - are unlikely in computer networks ... Hmm, maybe we should do some research related to this ... could be fun!). Another possibility would be to shout your message loudly into the pub, but you surely would have to do this multiple times, until your friend hears it.

Both strategies leave some performance on the table, so ExOR tries to send the packet as far as possible by selecting the node as the forwarding node, which has the least remaining distance to the final destination. (Imagine you shout the message for your friend loudly into the room - and we elect the person as the forwarder, who is nearest located to your friend among all persons who successfully heard what you said.)

Protocol details

There are some prerequisites for ExOR to work: A loss-rate-matrix has to be available, which contains the probability of a successfull reception of a packet between each pair of nodes. Such a matrix can be built using e.g. a link-state flooding scheme, detailled research on this is done elsewhere.

Every packet has to include a set of forwarding candidates, which are prioritized by distance. The forwarding-decision is then based on the set of forwarding candidates found in the header of our received packet, and on the received ACKs, which follow the transmission of the packet. The node which classifies itself as the forwarding node then retransmits the packet, using a new set of forwarding candidates.

The protocol is divided into three stages, as follows:

Stage 1: Select Forwarding Candidates

The decision which algorithm to use for this selection is very important for the strength of ExOR, as it has a major impact on its performance. The following approach seems to be very simple, but results in good performance in most average topologies:

A node which wants to forward a packet to a final destination first identifies the shortest path to this destination. We definitely need the aforementioned loss-rate-matrix here. The first node in this path is surely a good candidate regarding the forwarding job, so we use him as the best candidate. It's then deleted from the loss-rate-matrix and the whole process is repeated, until the set of forwarding candidates is full. (Typical sizes are 8 or 16 nodes.) Let's have a look at our example net, where the set of forwarding candidates would be (D, C, B), while assuming that we want to send a packet from node A to node D:

As mentioned above, there may be other strategies for other topologies. Imagine a relatively dense network, where all nodes in the set of forwarding candidates would be relatively far away from the sending node. The result would be, that the probability that one of them successfully receives the packet is small, resulting in multiple retransmissions of the packet. The selection of forwarding candidates sould assure that there are always some nodes near the transmitting node in the set.

Stage 2: Acknowledgements

still under construction, sorry

References

Origin of this page is the Ad-Hoc Networks Seminar in WS 2004/05 organized by the Systems Architecture Group at Humboldt University Berlin, in which Martin Stigge talked about that topic and created this page (self reference: see 'self reference'). Most of the content is based on the paper Opportinustic Routing in Multi-Hop Wireless Networks by Sanjit Biswas and Robert Mirros (MIT, 2004).