Capacity of opportunistic routing in multi-rate and multi-hop wireless networks

Opportunistic routing (OR) copes with the unreliable transmissions by exploiting the broadcast nature of the wireless medium and spatial diversity of the multi-hop wireless networks. In this paper, we carry out a comprehensive study on the impacts of multiple rates, interference, candidate selection and prioritization on the maximum end-to-end throughput or capacity of OR. Taking into account the wireless interference and unique properties of OR, we introduce the concept of concurrent transmitter sets to represent the constraints imposed by the transmission conflicts of OR, and formulate the maximum end-to-end throughput problem as a maximum-flow linear programming subject to the transmission conflict constraints. We also propose two multi-rate OR metrics: expected medium time (EMT) and expected advancement rate (EAR), and the corresponding distributed and local rate and candidate set selection schemes, one of which is least medium time OR (LMTOR) and the other is multi-rate geographic OR (MGOR). We compare the capacity of multi-rate OR with single-rate ones under different settings. We show that our proposed multi-rate OR schemes achieve higher throughput bound than any single-rate GOR. We observe some insights of OR: 1) although involving more forwarding candidates increases the end-to-end capacity, the capacity gained from involving more forwarding candidates decreases; 2) there exists a node density threshold, higher than which 24 Mbps GOR performs better than 12 Mbps GOR, and vice versa.