ExOR: Opportunistic Multi-Hop Routing for Wireless Networks

ExOR is the first wireless algorithm we look at that exploits the broadcast nature of wireless networks to build a new routing algorithm. In ExOR, the next hop is chosen after the transmission for that hop; that is, the route depends on who receives the message and not JUST on the current routing state of the network (as in DSDV) or the route information at the sender (like DSR). The major part of the algorithm is limiting duplicate transmissions from multiple nodes that think they should be sending the next hop; for this, each node listens to make sure any higher-priority intermediate node has not already forwarded the packet. Thus there is a tradeoff between waiting for a higher-priority routes and reducing overall routing latency.

ExOR's performance gain comes from essentially having many potential routes to choose from, unlike traditional routing which only has an all-or-nothing path for each hop. This works best when there is independent interference at each.

Looking at the algorithm as described, there's several design points that seem somewhat arbitrary. For example, the backoff when no information is available about higher-priority nodes is five packet times; I fail to see why this is a reasonable assumption, although it may work in practice. That is, there is no evidence this parameter is well-chosen. Another arbitrary number is the ultimate destination sending 10 batch map packets; again, there's no reason to expect this is optimal, nor is there reason to believe that the algorithm is insensitive to this parameter.

In their tests with UDP, ExOR improves throughput. Some of this is undoubtedly due to ExOR being able to choose paths as they are routed, but I would like to see how ExOR compares to a modified 802.11 algorithm that integrates two changes to ACKing: one, having ten ACKs sent instead of one, and second, having ACKs flow backwards to the source. I'm curious to see if the impact of these two decisions can be quantified, perhaps leading to a slight change in 802.11 routing to make it perform almost as well as ExOR.