Opportunistic Routing
(Please see also Ad-Hoc Networks for other aspects of Ad-Hoc Networks discussed in our seminar.)
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 the figure above 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 (= probability 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 it 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
After sending the packet, it's important that all candidate nodes somehow agree who will be the forwarding node. This done by acknowledgements (ACKs), which are sent in defined time-slots directly after the successful reception of our packet. The ACKs are sent by the forwarding candidates, in the order in which they appear in the packet header. Each ACK not only contains the ID of its sender, but also the ID of the highest priority successful recipient known to the ACK's sender. All candidates listen to all slots, before deciding whether to forward a packet, so this mechanism can supress duplicate forwarding to a certain degree, because the information, which node will be the forwarding node, somehow 'ripples' through the candidate-subnetwork. Let's have another look at our example network, to make this more clear:
Let's assume, node A sends a packet with D as the final destination. Let's further assume, that B, C and D receive the packet. After the reception of our packet, D is the first to send its ACK (containing D as the highest known ID), because it's first in the list of forwarding candidates, which was (D, C, B). In case node C doesn't receive this ACK (because C may be located far away from D or behind a wall or was distracted by the The Woman In The Red Dress or sth. like that), C then sends its ACK containing C itself as the highest known ID. The third ACK-slot is used by node B, which received D's ACK, so B also sends its ACK with D as the highest known ID. If C successfully receives this ACK (sent by B), then C doesn't forward the packet, because it knows - through B's ACK - that D will do that. (Phew..)
Stage 3: Forwarding Decision
This stage of ExOR is rather simple, because after all nodes received not only the packet but also a (hopefully) large subset of acknowledgements, they can easily decide whether they act as the forwarding node: The packet is forwarded iff the highest known ACK-ID is not greater than (means: equal to) the ID of the node itself.
As said above, this mechanism somehow reduces duplicates, but doesn't eleminate them completely, in some cases. (Imagine a node which doesn't receive any ACKs from other nodes but is not the best candidate). An ID cache should be used to reduce duplicates even more.
Example transmission using ExOR
Let's face the example net for the last time:
A packet is sent from node A to node D with a candidate set of (D, C, B). Let's assume, B and C receive the packet, but D doesn't. The ACK-slots are used as follows:
- No ACK is sent by D (since D didn't hear the transmission)
- ACK from C containing C's own node-id
- ACK from B containing C's node-id as well
If all nodes registered the ACKs, C will become the new forwarding node.
Evaluation and Simulation Results
As the authors of the paper on which this page is based pointed out, ExOR can be implemented using standard 802.11 hardware with only minor firmware modifications. Simulations showed, that the total number of transmissions required to route a packet from source to destination in a MANET can be improved by 55-65% in comparison to the best predetermined route (from the wired model) and that the successful transmission distances are better distributed (which may make us all very happy). Please have a look at the paper for more details about the implementation into 802.11 hardware and some more detailled simulation results.
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 (using some pdf slides) and created this page (self reference: see 'self reference'). Most of the content is based on the paper Opportunistic Routing in Multi-Hop Wireless Networks by Sanjit Biswas and Robert Mirros (MIT, 2004).
Please see also Ad-Hoc Networks for other aspects of Ad-Hoc Networks discussed in our seminar.