4.1 Computing Throughput Bound of OR

The first fundamental issue to address is the maximum end-to-end throughput when OR is used. Any traffic load higher than the throughput capacity is not supported and even causes performance to deteriorate as a result of excessive medium contention. The knowledge of throughput capacity can be used to reject any excessive traffic in the admission control for real-time services. It can also be used to evaluate the performance of different OR variants. Furthermore, the derivation of throughput of OR may suggest novel and efficient candidate selection and prioritization schemes.

In this section we present our methodology to compute the throughput bound between two end nodes in a given network with a given OR strategy (i.e., given each node's forwarding candidate set, node relay priority, and transmission/broadcast rate at each node). We first introduce two concepts, transmitter based conflict graph and concurrent transmission set, which are used to represent the constraints imposed by the interference among wireless transmissions in a multihop wireless network. We then present methods for computing bounds on the optimal throughput that a network can support when OR is used.

4.1.1 Transmission Interference and Conflict

Wireless interference is a key issue affecting throughput. Existing wireless interference models generally fall into two categories: protocol model and physical model (Gupta and Kumar 2000). Under the protocol model, a transmission is considered successful when both of the following conditions hold: 1. the receiver is in the effective transmission range of the transmitter; and 2. no other node that is in the carrier sensing range of the receiver is transmitting. This kind of protocol model requires only the receiver to be free of interference. To model a 802.11 like bidirectional communications we can extend the protocol model by adding the requirement of interference free also at the transmitter side. Under the physical model, for a successful transmission, the aggregate power at the receiver from all other ongoing transmissions plus the noise power must be less than a certain threshold so that the SNR requirement at the ongoing receiver is satisfied. In this book, we use the term “usable” to describe a link when it is able to make a successful transmission based on either the protocol model or the physical model. When two (or more) links are not able to be usable at the same time, they are having a “conflict”.

Link conflict graphs have been used to model such interference (Jain et al. 2003; Zhai and Fang 2006a). As shown in Figure 4.2(b), in a link conflict graph, each vertex corresponds to a link in the original connectivity graph. There is an edge between two vertices if the corresponding two links may not be active simultaneously due to interference (e.g., having a “conflict”). However, this link-based conflict graph cannot be directly applied to study capacity problem of OR networks because by the nature of opportunistic routing, for one transmission, throughput may take place on any one of the links from the transmitter to its forwarding candidates. The throughput dependency among multiple outgoing links from the same transmitter makes the subsequent maximum-flow optimization problem very difficult (if it is still possible). Therefore, in this paper, we propose a new construction of conflict graph to facilitate the computation of throughput bounds of OR. Instead of creating link conflict graph, we study the conflict relationship by transmitters (or nodes) associated with their forwarding candidates. As shown in Figure 4.2(c) in the node conflict graph, each vertex corresponds to a node in the original connectivity graph. Each vertex is associated with a set of links, e.g., the links to its selected forwarding candidates. There is an edge (conflict) between two vertices if the two nodes cannot be transmitting simultaneously due to a conflict caused by one or more unusable links, which we will define in Section 4.1.2.

4.1.2 Concurrent Transmission Sets

We define the concepts of concurrent transmission sets (CTSs) for OR as follows. These concepts capture the impact of interference of wireless transmissions and OR's opportunistic nature. They are the foundation of our method of computing the end-to-end throughput.

4.1.3 Effective Forwarding Rate

After we find a CTS, we need to identify the capacity on every link associated with a node in the CTS. We introduce the concept of effective forwarding rate on each link associated with a transmitter according to a specified OR strategy. Assume node ni's forwarding candidate set , with relay priorities . Let ψq denote the indicator function on link when it is in a particular CTS: ψq = 1 indicating link is usable, and ψq = 0 indicating that link is not usable. Then the effective forwarding rate of link in that particular CTS is defined in Equation (4.1):

4.1

where Ri is the broadcast rate of transmitter i, and . is the probability of candidate receiving the packet correctly but all the higher-priority candidates not. Note that the candidate (with ψq = 0), which is interfered by other transmissions, is not involved in the opportunistic forwarding, and has no effect on the effective forwarding rate from the transmitter to lower-priority candidates, as .

In a conservative CTS, all the receptions are interference free. Therefore, in each CCTS, every link associated with a transmitter is usable, i.e. ψ = 1, and the effective forwarding rate on each link is non zero. And the effective forwarding rate for a particular link remains same when the link is in a different CCTS. The effective forwarding rate indicates that according to the relay priority, only when a usable higher forwarding candidate did not receive the packet correctly, a usable lower priority candidate may have a chance to relay the packet if it received the packet correctly. Note that this definition generalizes the effective rate for unicast in traditional routing, that is, when there is only one forwarding candidate, the effective forwarding rate reduces to the unicast effective data rate.

For the greedy mode, some link(s) associated with one transmitter may become unusable, thus having zero effective forwarding rate. Furthermore, the effective forwarding rate of the links may be different when they are in different GCTSs. To indicate this possible difference, we use to denote the effective forwarding rate of link when it is in the αth GCTS.

4.1.4 Lower Bound of End-to-End Throughput of OR

Assume we have found all the maximum CCTSs {T1, T2…TM} in the network. At any time, one CTS at most can be scheduled to transmit. When one CTS is scheduled to transmit, all the nodes in that set can transmit simultaneously. Let λα denote the time fraction scheduled to CCTS Tα (1 ≤ α ≤ M). Then the maximum throughput problem can be converted to an optimal scheduling problem that schedules the transmission of the maximum CTSs to maximize the end-to-end throughput. Therefore, considering communication between a single source, ns, and a single destination, nd, with opportunistic routing, we formulate the maximum achievable throughput problem between the source and the destination as a linear programming problem corresponding to a maximum-flow problem under additional constraints in Figure 4.1.

In Figure 4.1, fij denotes the amount of flow on link lij, E is a set of all links in the connected graph G, and V is the set of all nodes. The maximization states that we wish to maximize the sum of flow out of the source. Constraint (4.2) represents flow conservation, i.e., at each node, except the source and the destination, the amount of incoming flow is equal to the amount of outgoing flow. Constraint (4.3) states that the incoming flow to the source node is 0. Constraint (4.4) indicates that the outgoing flow from the destination node is 0. Constraint (4.5) restricts the amount of flow on each link to be non-negative. Constraint (4.6) says there is no flow from the node to the neighboring nodes that are not selected as the forwarding candidates of it. Constraint (4.7) represents, at any time, at most one CTS will be scheduled to transmit. Constraint (4.8) indicates the scheduled time fraction should be non-negative. The constraint (4.9) states the actual flow delivered on each link is constrained by the total amount of flow that can be delivered in all activity periods of the OR modules which contain this link.

The key difference between our maximum flow formulations and the formulations for traditional routing in Jain et al. (2003); and Fang (2006a) lies in the methodology we use to schedule concurrent transmissions. With the construction of concurrent transmission sets, we are able to schedule the transmissions based on node set (with each node associated with a set of forwarding candidates) rather than link set in traditional routing. When we schedule a transmitter, we effectively schedule the links from the transmitter to its forwarding candidates at the same time according to OR strategy. For traditional routing, any two links sharing the same sender cannot be scheduled simultaneously. When a packet is not correctly received by the intended receiver but is opportunistically received by neighboring nodes of the sender, traditional routing will retransmit that packet instead of making use of the correct receptions on the other links. OR takes advantage of the correct receptions. That is why OR achieves higher throughput than traditional routing. Our proposed model accurately captures OR's capability of delivering throughput opportunistically.

A Simple Example: Next, we give an example to show how our formulation helps us to find the end-to-end throughput bound of OR, and we compare this result with the maximum throughput derived from multipath traditional routing based on results in Jain et al. (2003).

For simplicity, in the four-node network shown in Figure 4.2(a), we assume each node transmits at the same rate R, and each link is associated with a PRR indicated in the pair on each link. Assume every node is in the carrier sensing range of any other nodes. We are going to find the maximum end-to-end throughput from node a to d for traditional routing and OR.

Figure 4.2 Conflict graph. Reproduced by permission of © 2008 IEEE.

For traditional routing, we first construct the link-conflict graph as shown in Figure 4.2(b). In the conflict graph, each vertex corresponds to each link in the original connectivity graph. There is an edge between two vertices when these two links conflict with each other. According to the protocol model, no two links in Figure 4.2(a) can be scheduled simultaneously. So the link-conflict graph for traditional routing is a complete graph (clique). There are four independent sets, each containing one node in the conflict graph. Each independent set corresponds to one concurrent schedulable link set. By running the linear programming formulated in Jain et al. (2003) we can find an optimal schedule on links to maximize the throughput. Assuming the whole communication period is τ, one feasible solution is to assign , , , to lab, lac, lbd, lcd, respectively. So the maximum end-to-end throughput between a and d is for the traditional routing.

For OR, we construct the node conflict graph. Assume a chooses nodes b and c as its forwarding candidates, and b and c's forwarding candidate is just the destination d. According to the protocol model, the node conflict graph is constructed in Figure 4.2(c), which only contains three vertices and is also a clique. So the three conservative transmission sets are T1 = {a}, T2 = {b}, and T3 = {c}. Assume node b has higher relay priority than node c, then we have , , and . By running the linear programming formulated in Figure 4.1, we get an optimal schedule that assigns , and , to nodes a, b and c respectively. So the throughput of OR under this optimal schedule is , which is 25% higher than that of the traditional routing.

4.1.5 Maximum End-to-End Throughput of OR

The throughput bound we find based on the maximum conservative CTSs in Section 5.3.4 is a lower bound of maximum end-to-end throughput. The CCTSs can be constructed based on either the protocol model or the physical model. However, the interference freedom at every intended receiver is a stricter requirement than necessary. It may be applicable under some protocol scenarios but it fails to take full advantage of opportunistic nature of OR because it excludes the situations where concurrent transmission is able to deliver throughput on some of the links even though some other links are having conflicts. In order to compute the exact capacity, we apply the same optimization technique to the greedy CTSs. Since greedy CTSs include all the possible concurrent transmission scenarios that generate non-zero throughput, the bound found by the optimization technique based on all greedy CTSs will be the maximum end-to-end throughput of OR.

Like the construction of CCTSs, GCTSs can be constructed based on either the protocol model or the physical model. Under the protocol model, the conflict between two links is binary, either conflict or no conflict. It is not difficult to construct the GCTSs under the protocol model with the proposed node conflict graph. On the other hand, it is well known that the physical model captures the interference property more accurately. However, it is more complicated to represent the interference when multiple transmitters are active at the same time. In this section, we discuss the construction of GCTSs based on the physical interference model.

Under the physical interference model, a link lij, from node ni to nj, is usable if and only if the signal to noise ratio at receiver nj is no less than a certain threshold, e.g., , where Prij is the average signal power received at nj from ni's transmission, PN is the interference + noise power, and SNRth is the SNR threshold, under which the packet cannot be correctly received and above which the packet can be received at least with probability ptd. Note that, SNRth is different for different data rates.

Under the physical model, the interference gradually increases as the number of concurrent transmitters increases and becomes intolerable when the interference+noise level reaches a threshold. We define a weight function , to capture the impact of a transmitter ni's transmission on a link 's reception. Link represents the data forwarding from node nj its forwarding candidate .

4.10

where and are the received power at node from the transmissions of nodes ni and nj, respectively, Pnoise is the ambient noise power, and is the maximum allowable interference at node for keeping link usable.

Then given a transmission set S and nj ∈ S, a link is usable if and only if . It means that link is usable even when all the transmitters in set S are simultaneously transmitting. For conservative mode, if this condition is true for every link associated with each transmitter in S, this set S is a CCTS. For greedy mode, if this condition is true for at least one link associated with each transmitter in S, the set S is a GCTS.

After finding all the GCTSs, we can apply the same optimization technique to the maximum-flow problem based on all the GCTSs. The result is the exact bound of maximum end-to-end throughput.

When each node has only one forwarding candidate, OR degenerates to the traditional routing. Therefore, finding all the concurrent transmission sets is at least as hard as the NP-hard problem of finding the independent sets in Jain et al. (2003) and Zhai and Fang (2006a) for traditional routing. 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 column generation technique (Zhang et al. 2005) can be applied to find a good subset of all the CTSs. In addition, complexity can be further reduced by taking into consideration the fact that interferences/conflicts always happen for nodes within a certain range. How to efficiently find all the CTSs is beyond the scope of this book. We simply apply a greedy algorithm to find all the CTSs, say each time we add new transmitters into the existing CTSs to create new CTSs, until no any additional transmitter can be added into any of the existing CTSs.

4.1.6 Multi-Flow Generalization

Our formulations in Figure 4.1 can be extended from a single source–destination pair to multiple source–destination pairs using a multi-commodity flow formulation (Chavtal 1983) augmented with OR transmission constraints. By assigning a unique connection identifier to each source–destination pair, we introduce the variable to denote the amount of flow for connection k on link lij. For each flow k, according to some OR routing strategy, the corresponding transmitters and their forwarding candidates can be decided. Then the CCTS or GCTS can be constructed over the union of all the OR modules. Referring to Figure 4.1, the objective is now to maximize the summation of all the flows out of all the sources; the flow conservation constraints at each node apply on a per-connection basis (constraint (4.2)); the total incoming flow into a source node is zero only for the connection(s) originating at that node (constraint (4.3)); similarly, the total outgoing flow from a destination node is zero only for the connection(s) terminating at that node (constraint (4.4)); is non-negative (constraint (4.5)); is equal to zero if the flow k is not routed by any link (constraint (4.6)); and the sum of all the flows traversing on a link is constrained by the total amount of flow that can be delivered in all activity periods of the OR modules that contain this link (constraint (4.9)).