Opportunistic Routing

still under construction

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 the 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 are unlikely in computer networks ... Hmm, this could be fun! Maybe we should do some research related to this...). 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.)