Least-Cost Opportunistic Routing

In opportunistic routing, each node maintains a group of candidate relays to reach a particular destination, and transmits packets to any node in this group. If a single candidate relay receives the packet, it becomes the effective relay to forward the packet further. If no candidate receives the packet, then the current sender re-transmits. If multiple candidates receive the packet, then the link layer chooses a single receiver to be the relay. This choice could be made at random, or it could be driven by information coming from the routing layer, for example to use the best receiver as the relay. This paper addresses the least-cost opportunistic routing (LCOR) problem: how to assign and prioritize the set of candidate relays at each node for a given destination such that the expected cost of forwarding a packet to the destination is minimized. We solve this problem with a distributed algorithm that provably computes the optimal assignment of candidate relays that each node should allow to reach a particular destination. Prior proposals based on single-path routing metrics or geographic coordinates do not explicitly consider this tradeoff, and as a result make choices which are not always optimal.