With the spur of modern wireless technologies, a promising way to improve the system throughput is to allow more concurrent transmissions by installing multiple radio interfaces on one node with each radio tuned to a different orthogonal channel (Alicherry et al. 2005; Kodialam and Nandagopal 2005; Zhang et al. 2005). Other than the multiradio multichannel technology, opportunistic routing (OR) also shows its potential for significantly improving network throughput (Biswas and Morris 2005; Chachulski et al. 2007; Dubois-Ferriere et al. 2007; Fussler et al. 2003; Shah et al. 2004; Zeng et al. 2008; 2007a,b,c; Zhong et al. 2006). Opportunistic routing is a network-MAC cross-layer design, which involves multiple forwarding candidates at each hop, and the actual forwarder is selected after packet transmission according to the instant link reachability and availability. It is quite different from the traditional routing (TR) in that only one pre-selected next-hop node is involved to forward packets at each hop.
When integrating these two techniques, an interesting question arises: “what is the end-to-end throughput bound of the multi-radio multi-channel network when OR is available?” In this chapter, we will propose a methodology to answer this question. However, it is a nontrivial task.
First, unlike TR, OR has a unique quality in that for each packet transmission, any one of the forwarding candidates of the transmitter can become the actual forwarder. Thus, effective throughput can take place from a transmitter to any one of its forwarding candidates at any instant. However, for TR, throughput can only happen from a transmitter to a predefined next-hop node even if other neighboring nodes overhear the transmission. Therefore, previous work (Alicherry et al. 2005; Kodialam and Nandagopal 2005; Zhang et al. 2005) on the throughput optimization in multiradio multichannel systems based on traditional routing (TR) cannot be directly applied to OR.
Second, multiradio multichannel capability raises challenging issues on radio-channel assignment for OR. In a single-radio single-channel system, OR naturally takes advantage of the redundant receptions on multiple neighboring nodes without consuming or sacrificing any extra channel resources. When a node is sending packets, all of its one-hop neighbors usually cannot send or receive other packets at the same time due to co-channel interference. That is, these one-hop neighbors have no other choices but listen to the transmission. However, in multiradio/channel systems, the one-hop neighbors have two choices: 1. they can operate on the same channel as the transmitter to improve the diversity gain on the receiver side, then more effective traffic can flow out of the transmitter and the system throughput can be increased; or 2. they can operate on other orthogonal channels. Thus they have chances to transmit/receive packets to/from other nodes, which may result in more concurrent effective traffic flowing in the network and can also increase the system throughput. This can be considered as a tradeoff between multiplexing and spacial diversity. Which choice the neighboring nodes should make is nontrivial. The radio-channel assignment for optimizing the end-to-end throughput in multiradio, multichannel systems when OR is available deserves careful study.
Third, due to the broadcast nature of the wireless medium, a transmission may interfere with neighboring links operating on the same channel. Therefore, a node's transmission should be optimally scheduled in order to maximize the throughput. Finally, even when the radio-channel assignment and transmission scheduling are given, we still need to optimally (often dynamically) select forwarding candidates and assign relay priorities among them in order to maximize the end-to-end throughput. How to dynamically assign and schedule the forwarding priority among forwarding candidates has not been well studied in the existing literature.
In summary, in order to maximize the end-to-end throughput of the multiradio, multichannel network when OR is available, we should jointly address multiple issues: radio-channel assignment, transmission scheduling, and forwarding candidate selection and forwarding priority scheduling. In this chapter, we carry out a comprehensive study on these issues. First, we formulate the end-to-end throughput bound between a source–destination pair in multiradio, multichannel, multihop wireless networks with OR capability as a linear programming (LP) problem which jointly solves the radio-channel assignment, transmission scheduling, and forwarding candidate selection. Second, we propose an LP approach and a heuristic algorithm to find a feasible scheduling of opportunistic forwarding priority to achieve the throughput bound. The proposed heuristic algorithm achieves desirable performance under different number of forwarding candidates. Leveraging our analytical model, we gain the following two insights: 1. OR can achieve better performance than TR under different radio/channel configurations, however, in some scenarios (e.g. when bottleneck links exist between the sender and relays), TR is preferable; 2. OR can achieve comparable or even better performance than TR by using fewer radio resources.
The rest of this chapter is organized as follows. We introduce the system model and opportunistic routing in Section 5.2. We propose the framework of computing the throughput bound between a source–destination pair in multiradio, multichannel, multihop wireless networks with OR capability in Section 5.3. The scheduling of opportunistic forwarding priorities is studied in Section 5.4. Examples and simulation results are presented and analyzed in Section 5.5. Conclusions are drawn in Section 5.6.