Least-Cost Opportunistic Routing

In opportunistic routing, each node maintains a group of candidate next-hops to reach a particular destination, and transmits packets to any node in this group. The choice of candidate next-hops at each node is a key question that is central to the performance of opportunistic routing. This paper addresses the least-cost opportunistic routing (LCOR) problem: how to assign the set of candidate next-hops 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 next-hops 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. The LCOR algorithm and framework are general and can be applied to a variety of networks and cost models, including and beyond ETX-based metrics to improve throughput with lossy links. This paper further focuses on the application of LCOR to low-power wireless communication, and introduces a new link-layer technique to decrease energy transmission costs in conjunction with opportunistic forwarding. The design is implemented and evaluated on a 50-node wireless testbed. Simulation and testbed results demonstrate reductions in energy transmission by up to a factor of three compared to standard routing, up to 30% compared to opportunistic routing using single-path metrics. Furthermore LCOR routes are more robust and stable than with approaches based on single-path distances, due to the integrative nature of the LCOR's route cost metric.