ExOR: Opportunistic Multi-Hop Routing for Wireless Networks

The authors in this paper propose a technique that is very different from traditional routing schemes. In traditional routing protocols the receiver of the packet is chosen before forwarding the packet. ExOR proposes forwarding the packet to a set of nodes and later deciding which node will forward the packet to the destination. The idea is to exploit the broadcast nature of wireless medium.

ExOR technique involves:

• Source operating on batches of packets. This is done to reduce the communication involved for synchronization.
  
• The source node adds a list of candidate forwarders (sorted in descending order of priority) to each packet in the batch and forwards the packet to all the candidates. Priority is based on the distance of the node from the destination.
  
• Highest priority node then forwards the packet further with its list of candidate forwarders.
• Remaining forwarders transmit in order but only send packets that have not been acknowledged in the batch maps of the higher priority nodes.
• The forwarders continue to cycle through the priority list until 90% of the packets have been received by the destination.
• Remaining packets use traditional routing.

Without going into too much details I just want to go through the advantages of the scheme and then talk about things that concerned me.

Pros:

1. Takes advantage of the broadcast medium
2. Opportunistically takes advantage of long lossy links
3. Provides reliability through diversity
4. Low priority nodes will most likely not forward packets
5. ExOR protocol improves throughput by a factor of 2 or 4 over ETX since it uses multiple relay nodes to forward the packet to the destination.

Concern:

1. ExOR scheme suggests that forwarders (other than the highest priority forwarder) transmit packet if there are unacknowledged packets that were sent by the higher priority node. This means that the higher priority forwarders have to communicate to other forwarders that the packet has not been acknowledged. This seems to be too much of a communication overhead.
2. There is too much state to be kept with each node. Each node has to store each packet it receives in its buffer.
3. After 90% packets have been received rest of the packets use tradition routing. Also these 90% packets can take different routes. Thus, the rate at which packets are arriving at the receiver may vary a lot.
4. There seems to be not much study about the interference of communication between forwarders.