In this section we present our methodology to compute the throughput bound between two end nodes in a multiradio, multichannel, multihop wireless network when OR is available. We first study which opportunistic modules can coexist at the same time under the constraints of wireless interference and radio interface limits. We then formulate the end-to-end throughput bound as an LP problem, which solves the radio-channel assignment, transmission scheduling and forwarding candidate selection problems together. We further propose an LP approach and a heuristic algorithm to find a feasible scheduling of opportunistic forwarding priorities to achieve the capacity.
5.3.1 Concurrent Transmission Sets
In this subsection, we will discuss which opportunistic modules in the network can be activated at the same time. The set of opportunistic modules that can be activated at the same time is called the concurrent transmission set (CTS). The motivation for building a concurrent transmission set is similar that for building an independent set in Jain et al. (2003) and concurrent transmission patterns in Zhang et al. (2005)—that is, taking the benefit of time-sharing scheduling of different concurrent transmission sets, we could achieve a collection of capacity graphs, associated with capacity constraint on each link. Opportunistic routing can be performed on the underlying capacity graph to achieve the maximum throughput. However, the methodology of constructing CTS for OR is quite different from those in Jain et al. (2003) and Zhang et al. (2005) for TR. Because for OR, any of the forwarding candidates can become the actual forwarder for each transmission, and the instantaneous throughput can take place on any link from the transmitter to any forwarding candidate. So the CTS is constructed based on opportunistic modules (involving multiple links sharing the same transmitter) instead of individual links. Furthermore, besides the co-channel interference, radio interface limits in the multiradio system also impose constraints on concurrent transmissions in the network.
We introduce the concept of transceiver configuration, 
, which indicates node ni operating on channel k (1 ≤ k ≤ K). Each transceiver configuration can be in either the transmission or the reception state and we call it transmitter or receiver, respectively. We say there is a wireless link 
(i ≠ j) when 
is a transmitter and 
is a receiver and 
is in the transmission range of 
. Link 
is usable when 
is not in the interference range of any other transmitters; otherwise, it is unusable. When a link is usable, its transmitter and receiver are also usable. Let 
, and 
.
A CTS Tα can be represented by an indicator vector on all wireless links, written as 
.
5.1 
Denote the following indicator variable to represent the transceiver configuration status in CTS Tα:
5.2 
where 
can be a transmitter or receiver.
An opportunistic module in a CTS Tα can be represented as 
. Note that according to the unique property of OR, when a transmitter 
is usable, its multiple receivers can be usable at the same time, while a usable receiver can only correspond to one transmitter. This can be represented formally by:
Although any two active links operating on different channels do not interfere with each other, due to radio interface constraints, the number of channels being used on one node cannot exceed the number of radios installed on this node. To satisfy this constraint, we have
If two wireless links are concurrently usable on the same channel, they should either share the same transmitter or not interfere with each other. This can be represented by
where
5.6 
According to Equations (5.3), (5.4), and (5.5), we can enumerate all the CTSs. One CTS represents one radio-channel assignment. Note that the number of all the CTS's is exponential in the number of nodes, radios and channels. However, it may not be necessary to find all of them to maximize an end-to-end throughput. A heuristic algorithm similar to that in Tang et al. (2007), or a column-generation technique (Zhang et al. 2005) can be applied to find a subset of all the CTSs to approach the throughput bound. Applying these technologies to find CTSs is beyond the scope of this chapter. In this chapter, we simply enumerate all the CTSs. Next, we discuss which link rate (or rate vector) is supportable by OR from a transmitter to its forwarding candidates.
5.3.2 Effective Forwarding Rate
A fundamental difference of OR from TR is that effective throughput can take place from a transmitter to any of its forwarding candidates at any instant. To capture the unique property of OR we apply the definition of effective forwarding rate in Zeng et al. (2008) to represent the throughput on each link from a transmitter to each of its forwarding candidate according to a forwarding strategy. For a given transmitter ni and its forwarding candidate set 
, under a forwarding priority 
, the effective forwarding rate on link 
is defined in Equation (5.7):
where Ri is the data transmission rate at transmitter ni.
The effective forwarding rate indicates that according to the relay priority, only when higher-priority forwarding candidates do not receive the packet correctly, a lower-priority candidate may have a chance to relay the packet if it does. A similar methodology is used to define the remaining path cost for a forwarding candidate set in (Dubois-Ferriere et al. 2007) and compute the expected number of packets a transmitter must forward in (Chachulski et al. 2007).
Then the effective forwarding rate from a transmitter ni to its forwarding candidate set 
is the summation of the effective forwarding rate to each forwarding candidate in the sequence:
Note that, the effective forwarding rate from a transmitter to a set of its forwarding candidates only depends on the transmission rate and the PRRs on the corresponding links but does not depend on priority among the forwarding candidates. In Section 5.3.4 we will show that this property eases the LP formulation by avoiding enumerating all the possible prioritizations among the forwarding candidates. It will also be used to design a heuristic scheduling of opportunistic forwarding priorities to satisfy a rate vector in Section 5.4.2.
5.3.3 Capacity Region of an Opportunistic Module
In this subsection, we study the capacity region of an opportunistic module 
. This capacity region will serve as a bound of a rate vector corresponding to the links in the opportunistic module.
By applying the result proved in Tassiulas and Ephremides (1993), we have the capacity region of 
indicated in the following inequality (5.9).
where 
(1 ≤ q ≤ r) is the rate from ni to 
in 
, and 
.
The physical meaning of inequality (5.9) is that any subset summation of the rates on the outgoing links from a transmitter to its forwarding candidates must be bounded by the effective forwarding rate from the transmitter to the corresponding forwarding candidate subset. Now we are ready to formulate the end-to-end throughput bound of OR in multiradio, multichannel systems by making use of the CTS and the capacity region of the opportunistic module.
5.3.4 Maximum End-to-End Throughput in Multiradio, Multichannel, Multihop Networks with OR Capability
Assume we have found all the CTSs {T1, T2…TM} in the network. At any time, we activate all the transmitters in one CTS. Let λα denote the time fraction scheduled for CTS Tα (α = 1…M). The maximum throughput problem can then be converted to an optimal scheduling problem, which schedules the activation of the CTSs to maximize the end-to-end throughout. Therefore, considering communication between a single source, ns, and a single destination, nd, with opportunistic routing, we formulate the throughput capacity problem between the source and the destination as a linear programming problem corresponding to a maximum-flow problem under additional constraints in Figure 5.2.
Figure 5.2 LP formulations to optimize the end-to-end throughput between two end nodes in multiradio, multichannel, multihop wireless networks with OR capability. Reproduced by permission of © 2010 IEEE.
In Figure 5.2, 
and 
denote the rate on link 
and 
in the CTS Tα, respectively. Recall that E is the set of all the wireless links, and V is the set of all the transceiver configurations. The maximization states that we wish to maximize the sum of the flow rates out of the source, which is the accumulated flow rates on all outgoing links and all channels from the source in all CTSs. The constraint (5.11) represents flow-conservation, i.e., at each node, except the source and the destination, the accumulated incoming flow rate is equal to the accumulated outgoing flow rate. The constraint (5.12) states that the incoming accumulated flow rate to the source node is 0. The constraint (5.13) indicates that the outgoing accumulated flow rate from the destination node is 0. The constraint (5.14) restricts the amount of flow rate on each link to be non-negative. The constraint (5.15) shows that at any time, at most one CTS will be scheduled to be active. The constraint (5.16) indicates that the scheduled time fraction should be non-negative.
In the constraint (5.17), 
is an indicator vector of ϕj with length 
. The constraint (5.17) states that no matter which forwarding candidates are selected, the flow rates from a transmitter 
to its usable one-hop neighbors in 
should be in the capacity region of the opportunistic module 
. That is, in any CTS Tα, any subset-summation of the flow rates from a transmitter to its usable one-hop neighbors is bounded by the effective forwarding rate from the transmitter to the corresponding neighbor set. So constraint (5.17) actually contains 
inequalities.
The solution of the objective function (5.10) is the upper bound of the throughput between two nodes in multiradio, multichannel, multihop wireless networks when OR is available. The byproduct of the LP in Figure 5.2 is the radio-channel assignment (CTS's {Tα|α = 1…M}) and transmission scheduling ({λα|α = 1…M}). We also get the rate 
on each link 
in each CTS Tα. When 
, node j operating on channel k is selected as a forwarding candidate of 
in the CTS Tα; otherwise, it is not. Candidate selection is therefore also solved by the LP. Note that only one forwarding candidate being selected indicates the usage of TR. So our model is general for OR and TR cases. However, the LP does not tell us how to achieve the link rate 
in the opportunistic module, which is a forwarding priority scheduling problem.
In the following section we propose an LP approach and a heuristic algorithm to satisfy the flow rate 
on each link 
by scheduling the forwarding priorities among the forwarding candidates in an opportunistic module in a CTS Tα.