Throughput regions and optimal policies in wireless networks with opportunistic routing

Opportunistic routing in wireless networks has been proposed as a method to combat the volatility of wireless links, by leveraging their broadcast nature and choosing the next hop for each transmitted packet post-facto, using the actual reception outcomes at the respective neighbors, rather than based on a priori information. Much of the research on the topic has focused on protocol design issues, e.g. coordination mechanisms among the next-hop candidates; however, the fundamental performance bounds of the scheme are not yet known. In this paper we study the theoretical throughput region of opportunistic routing, for a generic network model with an arbitrary matrix of packet erasure probabilities between any two nodes, which cannot be mapped onto any classical model due to the existence of undirected broadcast from each node. We introduce a generic technique involving a transformation into a virtual network consisting of nodes corresponding to packet states in the original network, and define two different throughput-optimal scheduling policies in the virtual network, one based on a backpressure-like approach, and another that uses a dynamic programming algorithm which finds the minimum time to clear the system from any initial queued backlog. These policies can support both a unidirectional (half-duplex) flow between a given source and destination, and a bidirectional (full-duplex) connection with inter-session network coding in intermediate nodes.