Throughput Capacity of Opportunistic Routing in Wireless Sensor Networks

Abstract

Recently, the idea of opportunistic routing (OR) has been widely explored to cope with the unreliable transmissions by exploiting the broadcast nature and spatial diversity of the wireless medium in order to improve the performance of wireless sensor networks. However, there are few theoretical analyses on the maximum throughput of OR WSNs. This paper is the first attempt to conduct a theoretical analysis on aggregate throughput capacity of OR in multihop many-to-one WSNs with consideration for lossy link and transmission fairness. By capturing the key characteristics of forwarding candidate set in OR networks, we propose the cumulative delivery transmission model. Then we introduce the concept of concurrent schedulable set to represent the constraints imposed by the transmission conflicts of OR, and formulate the optimal aggregate throughput problem as a maximum concurrent flow linear programming problem. Simulation results demonstrate that the OR design derived from our analysis model often yields noticeably better throughput than traditional unicast routing protocols and the OR design derived from existing analysis model under a range of scenarios.

1. Introduction

Wireless sensor networks (WSNs) are quickly gaining popularity due to their potentially easy deployment at low cost without relying on the existing infrastructure to a variety of real world challenges. Traditional routing protocols for WSNs follow the concept of routing in wired networks by abstracting the wireless links as wired links. However, these routing protocols ignore that the infrastructureless property and the unstable nature of the wireless medium incur the problem of unreliable communication [1].

To address this problem, opportunistic routing (OR) has been proposed as a new routing paradigm [2]. OR utilizes the high-node density, space diversity, and broadcast advantage of wireless communication to increase the reliability of a single transmission. Instead of relying on one next-hop node to forward a data packet, OR predetermines a set of candidate relays with a priority order and selects the highest-priority relay that indeed receives the packet as the actual forwarder, based on the instantaneous availability.

Researchers have proposed several candidate selection and prioritization schemes to improve throughput [3–5] or energy efficiency [6, 7]. The existing works on OR mainly focused on developing various types of opportunistic routing algorithms and evaluating their performance gain through a number of simulations and empirical measurements [2, 6, 8–11]. However, there is a lack of theoretical analysis on the maximum throughput of OR WSNs. In this paper, we carry out an analytical approach to study the potential capacity enhancement of opportunistic routing in WSNs. Unlike other analytical studies which use a deterministic channel model [6, 12], our approach explores the key characteristics of opportunistic routing (i.e., its ability to take advantage of numerous unreliable wireless links in the network in a probabilistic manner). Taking into consideration of wireless interference, we propose cumulative delivery transmission model in contrast to individual delivery transmission conflict model [12]. Then we introduce the concept of concurrent schedulable set to represent the constraints imposed by transmission conflicts, and formulate a maximum concurrent flow linear programming problem, subjected to the transmission conflict constraints, to compute the optimal aggregate throughput that many-to-one WSNs can support. We show that finding optimal aggregate throughput is a NP-hard problem, and present methods for computing the optimal aggregate throughput bounds of OR WSNs. The knowledge of throughput capacity can be used to reject any excessive traffic in the admission control for real-time services. Furthermore, the derivation of throughput of OR may suggest novel and efficient candidate selection and prioritization schemes.

We view the cumulative delivery transmission model and the aggregate throughput capacity analysis framework for OR WSNs with consideration for lossy links and transmission fairness as the key contributions of our work. Simulation results show that the OR design derived from our analysis model often achieves noticeably better throughput than traditional unicast routing protocols and the OR design derived from existing analysis model under a range of scenarios with different traffic demands.

The rest of the paper is organized as follows. Section 2 introduces the system model. We present details of cumulative transmission delivery model and the framework of computing the optimal network throughput bounds of OR in Section 3. Simulation results are presented and analyzed in Section 4. In Section 5, we discuss related works. Section 6 concludes the paper.

2. System Model

2.1. Opportunistic Routing Framework

The basic module of opportunistic routing employed by the well-known Roofnet [13] is shown in Figure 1. Assume node $n_i$ is transmitting a packet to the destination node $n_d$ , and the other four nodes are the candidates for forwarding. Each link packet delivery ratio (LPDR), denoted as $P_{k,j}$ for the link between node $n_k$ and node $n_j$ , is shown in Figure 1. We denote the set of nodes which receive the packet from node $n_i$ as the neighboring node set $C_i$ of node $n_i$ . Each node selects a subset of its neighbors as forwarding candidate set (FCS) and assigns a priority to each of the candidates, denoted as $F_i:=〈n_{i1},n_{i2},n_{i3},n_{i4}〉$ for node $n_i$ shown in Figure 1, which includes all the nodes selected to be involved in the local opportunistic forwarding based on a particular selection strategy. Note that, $F_i$ is an ordered set, in which the order of the elements corresponds to their priority in forwarding a received packet.

Figure 1

Opportunistic routing in the subgraph of Roofnet.

When node $n_i$ broadcasts a packet, the nodes which indeed receive the packet in its forwarding candidate set $F_i$ respond. One of the candidate nodes continues the forwarding based on their relay priority –A candidate will forward the packet only when it is of the highest priority among the nodes which have received the packet. For example, if the first node $n_{i1}$ in the set has received the packet successfully, it forwards the packet towards the destination while all other nodes suppress duplicate forwarding. Otherwise, the second node $n_{i2}$ , the third node $n_{i3}$ , the forth node $n_{i4}$ , and so forth. When no forwarding candidate has successfully received the packet, the sender $n_i$ will retransmit the packet if retransmission is enabled. The forwarding reiterates until the packet is delivered to the destination node $n_d$ .

2.2. Packet Level Lossy Wireless Interference Model

Wireless interference is a key issue affecting throughput [14]. As OR exploits the broadcast nature and spatial diversity of the wireless medium by selecting unreliable wireless links in order to achieve better performance, the wireless interference model should be nonbinary and reflect the features of lossy links. Therefore, we propose the packet level lossy wireless interference model to define the conditions for a lossy wireless transmission. This model is similar to the receiver interference model of packet level loss rates introduced in [14].

The packet level lossy wireless interference model takes as input traffic demand and received signal strength (RSS) between pairs of nodes. It then estimates the rate at which each sender will transmit and the rate at which each receiver will successfully receive the packets. To compute the link packet delivery ratio, we model the inherent medium loss as well as collision loss. In this paper, we assume that the packet transmissions among individual nodes can be finely controlled and carefully scheduled by an omniscient and omnipotent central entity, which guarantees that there is no MAC contention. So different from [14], we only take as the asynchronous loss that occurs when at least one sender cannot carrier sense the other because there is no synchronous collision. The link packet delivery ratio between node $n_m$ and node $n_n$ initiated by node $n_{si}$ is

$P_{m,n}^{s_i}=1-\left(1-L_{mn}^{\text{RSS}}\right)\times \left(1-L_{mn|s_i}^{\text{COL}}\right),$

(1)

where $L_{mn}^{\text{RSS}}$ is the inherent packet loss rate on link $l_{mn}$ which is a constant value for node $n_{si}$ ; $L_{mn|s_i}^{\text{COL}}$ is asynchronous collision packet loss on link $l_{mn}$ caused by node $n_{si}$ , which can be modeled as

$L_{mn|S_i}^{\text{COL}}=1-{\left(1-L_{mn|S_i}^b\right)}^{8f},$

(2)

where f is the length of the packet transmitted by node $n_m$ , $L_{mn|S_i}^b$ is the collision bit error rate defined as

$L_{mn|S_i}^b=\frac{1}{2}\times {\exp \hspace{0.17em}}^{{\gamma }_{mn|S_i}/2},$

(3)

where ${\gamma }_{mn|S_i}=R_{mn}/(A_n+R_{s_{i}n})$ is the signal to interference plus noise ratio (SINR) of link $l_{mn}$ interfered by node $n_{si}$ , $R_{mn}$ is the received signal strength at node $n_n$ , $A_n$ is the ambient noise of node $n_n$ , and $R_{sin}$ is the interference at node $n_n$ from node $n_{si}$ .

Inferred from (1), (2), and (3), we can model the link packet delivery ratio of $l_{mn}$ over node $n_{si}$ as a function of $R_{mn}$ and $R_{sin}$ :

$P_{m,n}^{s_i}=1-\left(1-L_{mn}^{\text{RSS}}\right)\times {\left(1-\frac{1}{2}\times {\exp \hspace{0.17em}}^{R_{mn}/2\left(A_n+R_{s_{i}n}\right)}\right)}^{8f}.$

(4)

Similarly, we can get the cumulative link packet delivery ratio (CPR), denoted as $P_{m,n}$ , as the following:

$P_{m,n}=1-\left(1-L_{mn}^{\text{RSS}}\right)\times {\left(1-\frac{1}{2}\times {\exp \hspace{0.17em}}^{R_{mn}/2\left(A_n+{\sum }_{k\ne m}{R}_{kn}\right)}\right)}^{8f}.$

(5)

We say that a directed link $l_{ij}$ from node $n_i$ to $n_j$ is usable when $P_{m,n}$ is larger than a positive threshold $P_{td}$ . Notice that our definition of $P_{td}$ in OR networks which is generally less than 20% is much smaller than that in traditional routing networks (e.g., the $P_{td}$ in [15] is more than 80%).

3. Computing Bounds on Optimal Throughput of OR in Multiflow Wireless Sensor Networks

The optimal aggregate throughput is a fundamental issue in OR WSNs. We say that an aggregate throughput D in OR WSNs is feasible if there exists a schedule of transmissions such that no two interfering transmissions are simultaneously active which is impacted by the specific forwarding candidate selection and prioritization scheme, and the total throughput for the given source-destination pairs is D.

In this section, we present our framework to compute the optimal aggregate throughput in a given many-to-one WSN with a given OR strategy. We first introduce four concepts, cumulative delivery ratio, concurrent schedulable set, weighted node interference graph, and entirely cooperative conflict set, which are used to represent the constraints imposed by the interference among transmissions in a WSN. We then present methods for computing bounds on the optimal aggregate throughput that an OR WSN can support.

3.1. Cumulative Delivery Ratio

As we adopt a packet level lossy wireless interference model, we need to identify the delivery rate of a transmission in OR-based WSNs. Because by the nature of opportunistic routing, for one transmission, throughput may take place on multiple links, we introduce cumulative delivery ratio (CDR) on each transmission according to a specified OR strategy. Assume node $n_i^{}$ 's forwarding candidate set is $F_i:=〈n_{i1},n_{i2}\dots n_{ir}〉$ , with relay priorities $n_{i1}>n_{i2}>\cdots >n_{ir}$ , which are fixed in OR network with a specific OR policy. For the interference of the concurrent transmitting nodes, only part of forwarding candidates in FCS are usable which are termed as the effective forwarder candidate set (EFCS). Let ${\phi }_q$ denote the indicator function on link $l_{iiq}$ in a particular time: ${\phi }_q=1$ indicating link $l_{iiq}$ is usable, and ${\phi }_q=0$ indicating that link $l_{iiq}$ is not usable. Then the cumulative transmission delivery rate of node $n_i$ in that particular time is defined as:

${\text{CDR}}_i={\displaystyle \sum }_{k=1}^r{\phi }_k·p_{i,i_k}·{\displaystyle \prod }_{t=0}^{k-1}\left(1-{\phi }_t·p_{i,i_t}\right),$

(6)

where $p_{i,i0}:=0$ . From (6) we can deduce that the CDR of a specified node $n_i$ is related to the forwarding candidate selection policy and those concurrent transmitting nodes which may interfere in or even invalidate some links between $n_i$ and its forwarding candidates.

3.2. Weighted Node Interference Graph and Transmission Conflict

Link conflict graph has been used as a handy tool to model wireless interference for traditional routing networks [15, 16]. However, this link-based conflict graph cannot be directly applied to study capacity problem of OR networks because throughput OR may take place on multiple links. Reference [12] proposed a construction of transmitter conflict graph to facilitate the computation of throughput bounds of OR. In this graph, each vertex corresponds to a node in the original connectivity graph. There is an edge between two vertices if the two nodes cannot be transmitting simultaneously due to a conflict caused by the unusable links more than the threshold. However, this transmitter-based conflict graph only denotes a transmission conflict between two nodes but cannot capture the characteristics of joint effect and asymmetry of the transmission conflict in OR networks.

Therefore, taking wireless interference effects into account, we construct a weighted interference graph G for OR networks as shown in Figure 2. In this graph, each vertex corresponds to a node associated with its forwarder candidates. The transmission interference gradually increases as more neighboring nodes transmit simultaneously, and becomes intolerable when the total interference noise level reaches a threshold. This gradual increase in interference suggests that we should have a weighted node interference graph, where the weight of an edge between vertices $n_i$ to vertices $n_j$ (denoted by $R_{i,j}$ ) indicates what fraction of interference noise at node $n_j$ is contributed by node $n_i$ .

Figure 2

Weighted interference graph for OR Roofnet.

We redefine the concept of transmission conflict to capture OR's opportunistic nature and the characteristics of joint effect and asymmetry of the transmission interference in OR networks. Node m is termed to have a “transmission conflict” caused by some node set $C_m$ when node m and node set $C_m$ are simultaneously transmitting and the cumulative delivery rate of node m is less than a certain threshold $\text{CD}{\text{R}}_{\text{thresh}}$ (i.e., ${\text{CDR}}_m\le {\text{CDR}}_{\text{thresh}}$ ) due to the joint interference of the nodes in $C_m$ on its forwarder candidates. The node set $C_m$ is named as the cooperative conflict set over node m (denoted by CC ${\text{S}}_m$ ), and i-CC ${\text{S}}_m$ denotes that there are i nodes in the cooperative conflict set, which can be obtained via the weighted interference graph.

3.3. Cumulative Delivery-Based Concurrent Schedulable Sets

We introduce the notion of cumulative delivery based concurrent schedulable set (CSS) in the packet level lossy wireless interference model for OR WSNs, which is the foundation of our method of computing optimal aggregate throughput. A CSS is defined as a set of nodes, in which when they are transmitting simultaneously, none of which has a transmission conflict caused by all the other nodes in that set. If adding any one more node into a CSS will result in the usability status of any nodes in that set, the CSS is called maximal CSS. (In the following of this paper, CSS refers to maximal CSS.) The idea is to allow a node to transmit as long as it can deliver some throughput which meets the requirement of cumulative delivery rate threshold to some of its forwarder candidates. The maximal CSSs can be obtained through Algorithm 1.

Algorithm 1: The Maximal CSS solution.

(1) Initialize a empty CSS C in the interference graph G;

(2) Build a random ordering set $V=\{n_1,n_2,\dots n_r\}$ of all vertices in G;

(3) Add the first vertex $n_1$ in V to C and remove $n_1$ from V;

(4) While the set V is not empty do

(5)  remove the first vertex n_i from the set V;

(6)  if   $(({\text{CDR}}_i\ge \text{CD}{\text{R}}_{\text{thresh}})$ &&

      $({\text{CDR}}_k\ge \text{CD}{\text{R}}_{\text{thresh}}))\hspace{0.17em}\hspace{0.17em}\forall n_k\in C$   then

(7)    Add $n_i$ to C;

(8) return the maximal CCS C which is of size at least one;

3.4. LP Formulation on Optimal Aggregate Throughput of OR in Many-to-One WSNs

The optimal aggregate throughput problem can be described as the intersection of two kinds of constraints—the flow conservation and fairness constraints and the wireless interference constraints [12, 15]. We make the following observation. Suppose there are a total of K maximal CSSs $\{\text{CS}{\text{S}}_1,\text{CS}{\text{S}}_2\dots \text{CS}{\text{S}}_m\}$ in interference graph G. At any time, at most one CSS is scheduled to transmit, and all the nodes in that set can transmit simultaneously. Let constant $\gamma \hspace{0.17em}\hspace{0.17em}(0<\gamma \le 1)$ be the upper bound of throughput ratio between any pair of data flows, and ${\lambda }_i\hspace{0.17em}\hspace{0.17em}(0<{\lambda }_i<1)$ denote the fraction of time allocated to the CS ${\text{S}}_i$ (i.e., the time during which the nodes in ${\text{CSS}}_i$ can transmit packets). Then the maximum aggregate throughput problem can be converted to an optimal scheduling problem that schedules the transmission of the maximal CSSs to maximize the aggregate throughput. Therefore, by considering communications between source node set $N_s\{n_{s1},n_{s2}\dots n_{si}\}$ and a single destination $n_d$ , we formulate the optimal aggregate throughput problem of OR WSNs as a linear programming corresponding to a maximum concurrent flow problem under additional constraints, in (7)–(16) which introduce the LP formulations used to optimize the aggregate throughput for Many-to-One OR WSNs,

$\begin{array}{cc}\hfill & \mathrm{Max}\hspace{0.17em}\hspace{1em}{\displaystyle \sum }_{n_{s_i}\in N_s}^{}{f}_{\text{eff}}^{s_i,s_i}\hfill \\ \hfill & \text{s}.\text{t}.\hspace{1em}\hspace{1em}\gamma \times f_{\text{eff}}^{s_j,s_j}\le f_{\text{eff}}^{s_i,s_i}\le S_{s_i}\hfill \\ \hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\forall n_{s_i}\in N_S,\hspace{0.17em}\hspace{0.17em}\forall n_{s_j}\in N_s\setminus \left\{n_{s_i}\right\},\hfill \end{array}$

(7)

$\begin{array}{cc}\hfill & \hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{1em}{\displaystyle \sum }_{n_{s_i}\in N_s}^{}{f}_{\text{eff}}^{d,s_i}={\displaystyle \sum }_{n_{s_i}\in N_s}^{}{f}_{\text{eff}}^{s_i,s_i},\hfill \end{array}$

(8)

$\begin{array}{cc}\hfill & \hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{1em}{f}_{\text{eff}}^{k,s_i}\le {\displaystyle \sum }_{n_i\in F_k}^{}{f}_{\text{eff}}^{i,s_i}\hfill \\ \hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\forall n_{s_i}\in N_s,\hspace{0.17em}\hspace{0.17em}\forall n_k\in N_c\setminus \left\{n_d\right\},\hfill \end{array}$

(9)

$\begin{array}{cc}\hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{f}_{\text{eff}}^{k,s_i}\le f_{\text{act}}^{k,s_i}\times {\text{CDR}}_k\hfill \\ \hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\forall n_{s_i}\in N_s,\hspace{0.17em}\hspace{0.17em}\forall n_k\in N_c\setminus \left\{n_d\right\},\hfill \end{array}$

(10)

$\begin{array}{cc}\hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{f}_{\text{act}}^{d,s_i}=0\hspace{1em}\forall n_{s_i}\in N_s,\hfill \end{array}$

(11)

$\begin{array}{cc}\hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{\displaystyle \sum }_{n_{s_k}\in N_s}^{}{f}_{\text{act}}^{i,s_k}\le {\text{cap}}_i\hspace{1em}\forall n_i\in N_c\setminus \left\{n_d\right\},\hfill \end{array}$

(12)

$\begin{array}{cc}\hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\mathrm{\hspace{0.17em}\hspace{0.17em}}{\displaystyle \sum }_{m=0}^T{\lambda }_m\le 1,\hfill \end{array}$

(13)

$\begin{array}{cc}\hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{\lambda }_m\ge 0,\hspace{1em}1\le m\le ,\hfill \end{array}$

(14)

$\begin{array}{cc}\hfill & \hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{1em}{\displaystyle \sum }_{n_{s_i}\in N_s}^{}{f}_{\text{eff}}^{k,s_i}\le {\displaystyle \sum }_{n_j\in {\text{CSS}}_m,1\le m\le T,n_k\in F_j}^{}{\lambda }_m{\text{Cap}}_j\hfill \\ \hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\times {\phi }_{j,k}^m\times P_{j,k}\hfill \\ \hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\times {\displaystyle \prod }_{l=0}^{F_j^{-1}\left(n_k\right)-1}\left(1-{\phi }_{j,F_j\left(l\right)}·P_{j,F_j\left(l\right)}\right)\hfill \\ \hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\forall n_k\in N_c\setminus \left\{n_{s_i}\right\},\hfill \end{array}$

(15)

$\begin{array}{cc}\hfill & \hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}\hspace{1em}\hspace{0.17em}{\displaystyle \sum }_{n_{s_k}\in N_s}^{}{f}_{\text{act}}^{i,s_k}{\displaystyle \sum }_{n_i\in {\text{CSS}}_m,1\le m\le T}^{}{\lambda }_m{\text{Cap}}_i\hfill \\ \hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\forall n_i\in N_c\setminus \left\{n_d\right\}.\hfill \end{array}$

(16)

In (7)–(16), $f_{\text{act}}^{j,s_i}$ denotes the amount of data flow derived from source node $n_{si}$ actually transmitted by node $n_j$ ; $f_{\text{eff}}^{j,s_i}$ denotes the amount of data flow derived from source node $n_{si}$ required to be transmitted by node $n_j$ ; $N_c$ denotes the whole node set in the interference graph G; $S_{si}$ is the data generation rate of the source $n_{si}$ ; $F_k(i)$ denotes the $i\text{th}$ forward candidate in node $n_k$ 's forwarder candidate set $F_k$ ; $F_k^{-1}(n_i)$ denote the index of node $n_j$ in node $n_k$ 's forwarder candidate set $F_k$ ; ${\text{Cap}}_i$ denotes the transmission capacity of node $n_i$ ; $P_{j,k}$ denotes the cumulative link packet delivery ratio between node $n_j$ and node $n_k$ ; ${\phi }_{j,k}^m$ denotes the indicator function on forwarder candidate $n_k$ of node $n_j$ when $n_j$ is in a particular concurrent schedulable set ${\text{CSS}}_m$ ; ${\phi }_{j,k}^m=1$ indicating n_k is usable, and ${\phi }_{j,k}^m=0$ indicating otherwise.

The maximization states that we wish to maximize the sum of flow out of the all source nodes, in which constraints (7)–(12) denote the flow conservation and fairness constraints and constraints (13)–(16) denote the wireless interference constraints. The constraint (7) represents the flow validity and fairness, that is, the amount of effective flow derived from each source node is constrained by its data generation rate and the amount of effective flow derived from other source node. The constraint (8) states that flow-conservation, that is, the amount of outgoing flows from all source nodes is equal to the amount of incoming flow of the sink node. The constraint (9) indicates that the amount of effective flow of every node, except the sink node, is constrained by the total amount of effective flows of those nodes whose forwarder candidate sets involve that node. The constraint (10) denotes that the amount of effective flow of each node, except sink node, is constrained by the amount of outgoing flow of that node and its cumulative delivery rate. The constraint (11) says that the outgoing flow from sink node is 0. The constraint (12) represents that the amount of outgoing flow on each node cannot exceed its transmission capacity. The constraint (13) states that at any time, at most one CSS will be scheduled to transmit. The constraint (14) restricts that the scheduled time fraction should be non-negative. The constraint (15) indicates that the amount of effective flow delivered by each node, except source nodes, is constrained by the total amount of flow that can be delivered in all activity periods of those nodes whose effective forwarder candidate sets involve that node. The constraint (16) denotes that the amount of outgoing flow on every node, except sink node, is constrained by the sum of the activity periods of the concurrent schedulable sets which it is a member.

The key difference of our maximum of flow formulations from the formulations for opportunistic routing in [12] lies in the methodology we use to schedule concurrent transmissions. In our proposed model, we involve the factor of the cumulative delivery ratio in flow conservation and fairness considerations which can accurately captures OR's capability of delivering throughput opportunistically. With the construction of cumulative delivery-based concurrent schedulable sets, we are able to schedule the transmissions based on node set whose cumulative delivery ratio exceeds a threshold the same as in traditional routing, which guarantees a high throughput by balancing the tradeoff between packet loss rate and transmission rate. While in [12] it schedules the transmissions based on node set without any delivery rate consideration which will induce the conflict between packet loss rate and transmission rate. That is why our model achieves higher throughput than that of [12]. The detail comparison will be given in the next section.

3.5. Hardness Result

Now, we present a hardness result for computing the optimal aggregate throughput with LP formulation shown in (7)–(16). The part of flow conservation and fairness constraints (i.e., constraints (7)–(12)) is a simple structure on which a linear objective function can easily be optimized. While for the part of wireless interference constraints (i.e., constraint (13)–(16)), the concurrent schedulable set, on the other hand, is a difficult structure and no characterization of it is known (because there may be exponentially many CSSs [17]). When each node has only one forwarding candidate, OR degenerates to the traditional routing. Therefore, finding all the concurrent schedulable sets is at least as hard as the NP-hard problem of finding the independent sets in [15] for traditional routing. Correspondingly, it is NP-hard to find the optimal aggregate throughput in OR WSNs.

Even though it is a NP-hard problem, complexity can be reduced by taking into consideration that transmission conflicts always happen for nodes within certain range. We can look at heuristics for obtaining bounds on the throughput to approximate the optimal aggregate of OR WSNs.

3.6. Lower Bound

The problem of deriving a lower bound is equivalent to the problem of finding a network aggregate throughput that has a feasible schedule to achieve it. Suppose we can get $T^{\prime }$ CSSs through Algorithm 1. If we replace the schedule restrictions imposed by all the CSSs in the original linear program (i.e., constraints (13)–(16)) with those imposed by the found $T^{\prime }$ CSSs, the resulting throughput always has a feasible scheme, and therefore constitutes a lower bound on the maximum achievable throughput. To tighten the bound, we should consider using maximal CSSs as much as possible.

3.7. Upper Bound

To derive an upper bound, we consider a maximal set of nodes in the interference graph that mutually have transmission conflicts with each other which is termed as one-node level entirely cooperative conflict set (ECCS ¹ ). The total utilization of the nodes in each ECC ${\text{S}}^1$ is less than 1. Similarly, the i-nodes level entirely cooperative conflict set (ECCS ⁱ ), a maximal set of nodes that any node can transmit packet simultaneously with part of other nodes in the set but has a transmission conflict caused by all the other i nodes. In ECC ${\text{S}}^i$ , the total utilization of the nodes is less than i-1, the proof for which is not included due to space constraints.

We define i-ECCS as denotes a set of ECCSs including ECC ${\text{S}}^1$ , ECC ${\text{S}}^2$ , … and ECC ${\text{S}}^i$ , which gives us a constraint on the usage vector. For example, we can find all the X ECC ${\text{S}}^1$ s in 1-ECCS and write corresponding constraints to define a polytope. We can then maximize the aggregate throughput over the intersection of this polytope with the flow constraints in the original linear program (i.e., constraints (7)–(12)). Thus an upper bound can be obtained.

$\begin{array}{c}{\displaystyle \sum }_{n_i\in {\text{ECCS}}_m^1}{\lambda }_i\le 1\hspace{1em}1\le m\le X,\end{array}$

(17)

${\lambda }_i\ge 0\hspace{1em}\forall n_i\in {\text{ECCS}}_m^1,\hspace{0.17em}\hspace{0.17em}1\le m\le X,$

(18)

$\begin{array}{c}{\displaystyle \sum }_{n_{s_k}\in N_S}{f}_{\text{act}}^{i,s_k}\le {\lambda }_i{\text{Cap}}_i\hspace{1em}\forall n_i\in N_c\setminus \left\{n_d\right\},\hspace{0.17em}\hspace{0.17em}1\le m\le X.\end{array}$

(19)

These constraints may result in a loose bound since there may not be abundant ECC ${\text{S}}^1$ s. To tighten the upper bound, we further augment the LP formulation with the more ECCS constraints by larger i-ECCSs.

Unfortunately, it is computationally expensive to find all levels of the ECCSs, and even if we could find them all, there is still no guarantee that our upper bound will be tight.

4. Performance Evaluation

This section uses Matlab to investigate the performance of OR variant: ExOR [2] in many-to-one WSNs. The section is organized as follows. We first present the illustrative results that demonstrate the flexibility of our cumulative delivery-based OR analytical model (COR) to discuss the issue of convergence of the upper and lower bounds on the optimal aggregate throughput. We also investigate the maximum aggregate throughput in a wide range of scenarios with different traffic demands and compare them with those derived from of the traditional multipath routing analytical model (MPR) [15] and the individual delivery-based OR routing analytical model (IOR) [12].

4.1. Simulation Setup

The simulated network has 49 stationary nodes uniformly distributed in a 900 m × 900 m square region shown in Figure 3. We fix the seven nodes in the first column of the grid as the source candidates, and all of them communicate with the same destination node located in the center of the last column. The PRR threshold ptd in multipath routing and OR routing is set to 0.8 and 0.1, respectively. We assume that the PRR is inversely proportional to the distance with random Gaussian deviation of 0.1 and that all the wireless links have an identical capacity (i.e., speed) of 1 unit. Similar to [18], we use a single interference range 500 m for simplicity. The performance metric is the aggregate throughput.

Figure 3

7×7 grid WSN.

4.2. Aggregate Throughput Bounds of Traditional Multipath Routing and OR Under COR Model

In this section we consider a scenario in the $7\times 7$ simulated network that the two nodes S₃₁, S₅₁ are selected as the sources and the sending rate of each source as 1.

Figure 4 shows the upper and lower bounds of aggregate throughput for OR WSNs derived from our COR model with varying constraints. We can see that the upper bound quickly converges to the stable value. More specifically, the more ECCS constraints being employed, the more accurate upper bound approaching the optimal value is achieved. The lower bound, on the other hand, steadily converges to the optimal value as the number of acquired CSSs increases. However, the upper bound and lower bound cannot converge together due to the fact that the ECCS constraints alone are not sufficient to guarantee optimality of the upper bound, even all ECCS constraints are involved.

Figure 4

Aggregate throughput bounds of COR with varying constraints.

We pick N relaying nodes from 46 available nodes (i.e., they do not include the two sources and the destination), at random, and without replacement. Then, in such a 2-flow network, the resulting normalized maximum aggregate throughput derived from our model and multipath routing model [15] for various values of N is potted in Figure 5. Note that the normalized maximum aggregate throughput continues to rise as the increase of the relaying node. This means that the richer connectivity provided by additional nodes allows for new routes, and allows extra traffic to be sent through the network. Figure 5 shows that the aggregate throughput derived from COR model is higher than that derived from MPR model because OR's ability to take advantage of the numerous, yet unreliable wireless links.

Figure 5

Normalized maximum aggregate throughput in WSNs with varying node densities.

Figure 6 indicates the relation between the per-flow sending rate and the maximum aggregate throughput in a WSN with varying traffic load. In Figure 6(a), the maximum aggregate throughput increases quickly (i.e., the networks are unsaturated) in the incipient stage and then the increase slows down. The reason is that the network fails to transmit most of the overloading traffic as more traffic is injected into the networks which are being saturated. Because the total traffic of all flows increase steadily, the normalized maximum aggregate throughput of the network declines quickly the increase of the per-flow sending rate.

Figure 6

Maximum aggregate throughput in a WSN with varying traffic load.

From Figures 5 and 6, we can observe that OR achieves much higher aggregate throughput than traditional multipath routing. The difference of OR from traditional routing is that, by allowing multiple nodes to opportunistically forward a packet, the medium time utility is improved, thus the throughput is enhanced.

4.3. OR Throughput Comparison under Different Models

Now we compare the maximum throughput derived from our COR model and two IOR models (i.e., greedy mode and conservative mode). Since both IOR models support one flow at most we consider an OR network with only one flow and set node $S_{41}$ as the source, sending rate of source as 1. From Figure 7, we can observe that maximum aggregate throughput derived from both OR models increases as the richer connectivity provided by additional nodes allows for new forwarding candidates, and allows extra traffic to be sent through the network. Figure 7 indicates that COR model results in higher aggregate throughput than both IOR models because COR model makes the most use of any qualified chance to deliver a packet to the next hop.

Figure 7

Normalized maximum aggregate throughput in WSNs with varying node densities.

Figure 7 also presents an interesting result that the conservative IOR model performs better than the greedy IOR when the number of relaying nodes is less than 25 while performing worse than the greedy IOR when the number of relaying nodes is beyond 25. The reason is that when the number of relaying nodes is less than 25, the greedy IOR needs to perform more retransmissions due to the universal heavy lossy links in sparse networks, while in a dense network the conservative IOR excludes the situations where concurrent transmission is able to deliver throughput on some of the reliable links even though other links are having conflicts.

5. Related Works

Opportunistic routing (OR) is mainly proposed to address the unreliable communication in multihop wireless networks which exploits the broadcast advantage of the wireless medium by involving a set of forwarding candidates instead of only one in traditional routing [2–5, 7–10]. ExOR [2] and utility-based OR [8], rely on the path cost information or global knowledge of the network to select candidates and prioritize them. MORE [9] presents a low-complexity distributed algorithm for intraflow network coding to deliver opportunistic routing gains which allow it to exploit the spatial reuse available and be easily extensible to multicast traffic. Unlike previous packet level opportunistic routing, MIXIT [10] firstly presents a symbol-level opportunistic routing by exploiting partially correct receptions instead of only fully correct packet, which profitably takes advantage of bit-level wireless spatial diversity to achieve high throughput. However, there are few theoretical works determining the aggregate throughput bounds of OR in many-to-one WSNs.

The theoretical performance capacity study on multihop wireless networks mainly focuses on the throughput bounds for a given network [19]. Jain et al. proposed a framework to calculate the throughput bounds of traditional routing between a pair of nodes by adding wireless interference constraints into the maximum flow formulations [15]. Zhai and Fang studied the path capacity of traditional routing in a multirate scenario [16]. Li et al. presented a model to accurately predict the resulting throughput of individual flows and optimize the network for fairness and throughput [19]. Zeng et al. studied the end-to-end throughput capacity of OR networks, which only adopted the wireless interference model which cannot reflect the characteristics of OR networks and considered the scenarios of single flow and saturated traffic demand [12]. Our work falls into this direction. However, distinguished from the previous works, we adopt a packet level lossy interference model [14] and propose a method to compute the aggregate throughput bounds of opportunistic routing, which is much different from the existing methods in that we exploit cumulative transmission delivery instead of individual link delivery to capture the local broadcast nature of OR.

6. Conclusions

In this paper, we studied the impact of multiple flows, lossy link-based interference, candidate selection, and prioritization on the maximum aggregate throughput of OR WSNs. Taking into consideration of an accurate packet- level lossy wireless interference model, we proposed a new method of constructing concurrent schedulable sets, and formulated the optimal aggregate throughput problem of OR as a maximum concurrent flow problem subject to the transmission conflict constraints. We also presented a methodology for computing the aggregate throughput bounds of OR in many-to-one WSNs.

To the best of our knowledge, this is the first theoretical work on capacity problem of OR with different traffic demands for multihop of many-to-one WSNs with consideration for lossy link and transmission fairness. We validate the analysis results by simulation, which shows that the throughput bound derived from our COR model is much closer to the optimal value than that derived from existing IOR model and that OR has great potential to improve aggregate throughput.