ExOR: Opportunistic Multi-Hop Routing for Wireless Networks

S. Biswas, R. Morris, "ExOR: Opportunistic Multi-Hop Routing for Wireless Networks," ACM SIGCOMM Conference, (August 2005).

This paper talked about ExOR- (Ex-Opportunistic Routing, what does Ex stand for?) , an efficient integrated routing and MAC protocol. The idea was that ExOR chooses each hop of a packet's route after the transmission for that hop, so that the choice can reflect which intermediate nodes actually received the transmission.  Basically, the paper questioned the very premise of routing in wireless networks. Traditional routing protocols choose the best sequence of nodes between source and destination, and forward each packet through that sequence. However, the authors questioned that such a scheme doesn't work quite well in wireless as transmissions is over lossy paths and has a probabilistic nature. To tackle this, they propose a cooperative diversity scheme which operated as follows:

• The source broadcasts its batch of packets and the neighboring nodes try to 'hear' and buffer as many packets as they can.
• Next, the node A that is closest to the destination (identified by the local forwarder list) transmits its batched sets of packets that the receiver had not received.
• Further, the adjacent node B that overhears A knows about the packets that A has not transmitted and broadcast them and this process continues till the sender.
• The forwarders continue to cycle through the priority list until the destination has 90% of the packets. The remaining packets are transferred with traditional routing.

Comments

This is definitely a great idea! The authors brilliantly utilize the inevitable use of broadcast  in a wireless network and come up with a smart scheme of probabilistically sending packets. They do make assumptions that the receptions at different nodes is independent of each other and there are not many collisions (which may or may not be true on a general basis) and further that there is a gradual decrease of delivery probability with distance (which is generally true, though presence of intermittent noise sources may affect this claim). However, I guess the paper was definitely novel in its approach and was definitely successful in trying to put forth its point that ExOR multihop cooperative routing is definitely better than traditional routing.