Chapter 4

Capacity of Multirate Opportunistic Routing

The existing works on OR mainly focused on a single-rate system. Researchers have proposed several candidate selection and prioritization schemes to improve throughput or energy efficiency. However, there is a lack of theoretical analysis on the performance limit or the throughput bounds achievable by OR. In addition, one of the current trends in wireless communication is to enable devices to operate using multiple transmission rates. For example, many existing wireless networking standards such as IEEE 802.11a/b/g include this multirate capability. The inherent rate–distance tradeoff of multirate transmissions has shown its impact on the throughput performance of traditional routing (Awerbuch et al. 2006; Zhai and Fang 2006a,b). Generally, low-rate communication covers a long transmission range, while high-rate communication must occur at short range. It is intuitive to expect that this rate–distance tradeoff will also affect the throughput of OR because different transmission ranges also imply different neighboring node sets, which results in different spacial diversity opportunities. These rate–distance–diversity tradeoffs will no doubt affect the throughput of OR, which deserves careful study. To the best of our knowledge, there is no existing work addressing the throughput problem of OR in a multirate network.

In this chapter, we bridge these two gaps by studying the throughput bound of OR and the performance of OR in a multirate scenario. First, for OR, we propose the concept of concurrent transmission sets, which captures the transmission conflict constraints of OR. Then, for a given network with a given opportunistic routing strategy (i.e., forwarder selection and prioritization), we formulate the maximum end-to-end throughput problem as a maximum-flow linear programming problem subject to the constraints of transmitter conflict. The solution of the optimization problem provides the performance bound of OR. The proposed method establishes a theoretical foundation for the evaluation of the performance of different variants of OR with various forwarding candidate selection, prioritization policies, and transmission rates. We also propose two 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 Multirate Geographic OR (MGOR). Simulation results show that, for OR, by incorporating our proposed multirate OR schemes, systems operating at multirates achieve higher throughput than systems operating at any single rate. Several observations are made about OR: 1. the end-to-end capacity gained decreases when the number of forwarding candidates is increased; 2. there exists a node-density threshold, higher than which 24 mbps GOR performs better than 12 mbps GOR, and lower than which the opposite is the case.

The rest of this chapter is organized as follows. We propose the framework of computing the throughput bounds of OR in Section 4.1. Section 4.2 studies the impact of multirate capability and forwarding strategy on the throughput bound of OR. We then propose the OR metrics, and rate and candidate selection schemes for multirate systems in Section 4.3. Simulation results are presented and analyzed in Section 4.4. Conclusions are drawn in Section 4.5.