ExOR: Opportunistic multi-hop routing for wireless networks

This paper is based on the following idea: in a wireless network, a transmitting node can be heard by more than one neighboring nodes. Instead of just depending on one forwarding node as in traditional routing, why not use any node that received the data to do the forwarding? This can reduce the number of re-transmissions and increase throughput. More concisely, this paper aims at making practical use of path diversity in a wireless network.

Alas, this simple idea needs plenty of book-keeping to make it worthwhile, and the rest of the system description describes one such approach. To reduce packet overhead, only a small number of forwarding nodes are considered for each hop. Second, to avoid duplication of transmission, there needs to be some mechanism for nodes to know what other potential forwarding nodes have done. Here, the authors choose to send a batch of packets at a time to pipeline the transmission and agreement of which packets have been sent by forwarding nodes.

Partly due to the complexity of the book-keeping, I was not able to quite follow how this works beyond one hop. Clearly, from the experimental results, ExOR works for multiple hops. I also could not make up my mind how centralized/distributed this scheme is. A server seemed to be necessary to obtain a complete global picture of the network and send it to all nodes such that the source node can pre-compute which are good forwarding nodes. For dynamic networks, a periodic route finding seems expensive and unsatisfactory. Is there a way to discover multiple paths in a distributed fashion in a dynamic environment?

My overall sense of the paper is this: too many things seem to need to happen for it to work, its a wonder that the results are as good as that shown in the paper. It is nice though that the authors point out that path diversity works well only if there is indeed some diversity in loss patterns observed by forwarding nodes; if the losses are highly correlated (perhaps a localized jammer?), there is a performance gap. Still, all it takes is one forwarding node to receive the packet for it to go through.