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_{i 1}, n_{i 2}, n_{i 3}, n_{i 4} 〉$ 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_{i 1}$ 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_{i 2}$ , the third node $n_{i 3}$ , the forth node $n_{i 4}$ , 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_{s i}$ is

P_{m, n}^{s_{i}} = 1 - (1 - L_{m n}^{RSS}) \times (1 - L_{m n | s_{i}}^{COL}),

(1)

where

L_{m n}^{RSS}

is the inherent packet loss rate on link

l_{m n}

which is a constant value for node

n_{s i}

;

L_{m n | s_{i}}^{COL}

is asynchronous collision packet loss on link

l_{m n}

caused by node

n_{s i}

, which can be modeled as

L_{m n | S_{i}}^{COL} = 1 - {(1 - L_{m n | S_{i}}^{b})}^{8 f},

(2)

where f is the length of the packet transmitted by node

n_{m}

L_{m n | S_{i}}^{b}

is the collision bit error rate defined as

L_{m n | S_{i}}^{b} = \frac{1}{2} \times \exp^{γ_{m n | S_{i}} / 2},

(3)

where

γ_{m n | S_{i}} = R_{m n} / (A_{n} + R_{s_{i} n})

is the signal to interference plus noise ratio (SINR) of link

l_{m n}

interfered by node

n_{s i}

R_{m n}

is the received signal strength at node

n_{n}

A_{n}

is the ambient noise of node

n_{n}

, and

R_{s i n}

is the interference at node

n_{n}

from node

n_{s i}

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

P_{m, n}^{s_{i}} = 1 - (1 - L_{m n}^{RSS}) \times {(1 - \frac{1}{2} \times \exp^{R_{m n} / 2 (A_{n} + R_{s_{i} n})})}^{8 f} .

(4)

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

P_{m, n} = 1 - (1 - L_{m n}^{RSS}) \times {(1 - \frac{1}{2} \times \exp^{R_{m n} / 2 (A_{n} + \sum_{k \neq m} R_{k n})})}^{8 f} .

(5)

We say that a directed link $l_{i j}$ from node $n_{i}$ to $n_{j}$ is usable when $P_{m, n}$ is larger than a positive threshold $P_{t d}$ . Notice that our definition of $P_{t d}$ in OR networks which is generally less than 20% is much smaller than that in traditional routing networks (e.g., the $P_{t d}$ 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_{i 1}, n_{i 2} \dots n_{i r} 〉$ , with relay priorities $n_{i 1} > n_{i 2} > \dots > n_{i r}$ , 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 $φ_{q}$ denote the indicator function on link $l_{i i q}$ in a particular time: $φ_{q} = 1$ indicating link $l_{i i q}$ is usable, and $φ_{q} = 0$ indicating that link $l_{i i q}$ is not usable. Then the cumulative transmission delivery rate of node $n_{i}$ in that particular time is defined as:

{CDR}_{i} = \sum_{k = 1}^{r} φ_{k} \cdot p_{i, i_{k}} \cdot \prod_{t = 0}^{k - 1} (1 - φ_{t} \cdot p_{i, i_{t}}),

(6)

where

p_{i, i 0} : = 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 $CD R_{thresh}$ (i.e., ${CDR}_{m} \leq {CDR}_{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 $S_{m}$ ), and i-CC $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 $(({CDR}_{i} \geq CD R_{thresh})$ &&

$({CDR}_{k} \geq CD R_{thresh})) \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 ${CS S_{1}, CS S_{2} \dots CS 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 $γ (0 < γ \leq 1)$ be the upper bound of throughput ratio between any pair of data flows, and $λ_{i} (0 < λ_{i} < 1)$ denote the fraction of time allocated to the CS $S_{i}$ (i.e., the time during which the nodes in ${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_{s 1}, n_{s 2} \dots n_{s i}}$ 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{matrix} Max \sum_{n_{s_{i}} \in N_{s}}^{} f_{eff}^{s_{i}, s_{i}} \\ s . t . γ \times f_{eff}^{s_{j}, s_{j}} \leq f_{eff}^{s_{i}, s_{i}} \leq S_{s_{i}} \\ \forall n_{s_{i}} \in N_{S}, \forall n_{s_{j}} \in N_{s} ∖ {n_{s_{i}}}, \end{matrix}

(7)

\begin{align} \sum_{n_{s_{i}} \in N_{s}}^{} f_{eff}^{d, s_{i}} = \sum_{n_{s_{i}} \in N_{s}}^{} f_{eff}^{s_{i}, s_{i}}, \end{align}

(8)

\begin{matrix} f_{eff}^{k, s_{i}} \leq \sum_{n_{i} \in F_{k}}^{} f_{eff}^{i, s_{i}} \\ \forall n_{s_{i}} \in N_{s}, \forall n_{k} \in N_{c} ∖ {n_{d}}, \end{matrix}

(9)

\begin{matrix} f_{eff}^{k, s_{i}} \leq f_{act}^{k, s_{i}} \times {CDR}_{k} \\ \forall n_{s_{i}} \in N_{s}, \forall n_{k} \in N_{c} ∖ {n_{d}}, \end{matrix}

(10)

\begin{align} f_{act}^{d, s_{i}} = 0 \forall n_{s_{i}} \in N_{s}, \end{align}

(11)

\begin{align} \sum_{n_{s_{k}} \in N_{s}}^{} f_{act}^{i, s_{k}} \leq {cap}_{i} \forall n_{i} \in N_{c} ∖ {n_{d}}, \end{align}

(12)

\begin{align} \sum_{m = 0}^{T} λ_{m} \leq 1, \end{align}

(13)

\begin{align} λ_{m} \geq 0, 1 \leq m \leq, \end{align}

(14)

\begin{matrix} \sum_{n_{s_{i}} \in N_{s}}^{} f_{eff}^{k, s_{i}} \leq \sum_{n_{j} \in {CSS}_{m}, 1 \leq m \leq T, n_{k} \in F_{j}}^{} λ_{m} {Cap}_{j} \\ \times φ_{j, k}^{m} \times P_{j, k} \\ \times \prod_{l = 0}^{F_{j}^{- 1} (n_{k}) - 1} (1 - φ_{j, F_{j} (l)} \cdot P_{j, F_{j} (l)}) \\ \forall n_{k} \in N_{c} ∖ {n_{s_{i}}}, \end{matrix}

(15)

\begin{matrix} \sum_{n_{s_{k}} \in N_{s}}^{} f_{act}^{i, s_{k}} \sum_{n_{i} \in {CSS}_{m}, 1 \leq m \leq T}^{} λ_{m} {Cap}_{i} \\ \forall n_{i} \in N_{c} ∖ {n_{d}} . \end{matrix}

(16)

In (7)–(16),

f_{act}^{j, s_{i}}

denotes the amount of data flow derived from source node

n_{s i}

actually transmitted by node

n_{j}

;

f_{eff}^{j, s_{i}}

denotes the amount of data flow derived from source node

n_{s i}

required to be transmitted by node

n_{j}

;

N_{c}

denotes the whole node set in the interference graph G;

S_{s i}

is the data generation rate of the source

n_{s i}

;

F_{k} (i)

denotes the

i 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}

;

{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}

;

φ_{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

{CSS}_{m}

;

φ_{j, k}^{m} = 1

indicating n_k is usable, and

φ_{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^{'}$ 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^{'}$ 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 $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 $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 $S^{1}$ , ECC $S^{2}$ , … and ECC $S^{i}$ , which gives us a constraint on the usage vector. For example, we can find all the X ECC $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{gathered} \sum_{n_{i} \in {ECCS}_{m}^{1}} λ_{i} \leq 1 1 \leq m \leq X, \end{gathered}

(17)

λ_{i} \geq 0 \forall n_{i} \in {ECCS}_{m}^{1}, 1 \leq m \leq X,

(18)

\begin{gathered} \sum_{n_{s_{k}} \in N_{S}} f_{act}^{i, s_{k}} \leq λ_{i} {Cap}_{i} \forall n_{i} \in N_{c} ∖ {n_{d}}, 1 \leq m \leq X . \end{gathered}

(19)

These constraints may result in a loose bound since there may not be abundant ECC $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.

Footnotes

Acknowledgments

This paper was partially supported by the National Key Basic Research Program of China “973 Project” (Grants no. 2006CB303000) and NSFC (Grants no. 60533110 and no. 60572060).

References

De Couto

D. S. J.

Aguayo

Bicket

Morris

A high-throughput path metric for multi-hop wireless routing

Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (MobiCom ′03)

September 2003

134 146

2-s2.0-1542359009

Biswas

Morris

ExOR: opportunistic multi-hop routing for wireless networks

Proceedings of the ACM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM ′05)

October 2005

Philadelphia, Pa, USA

133 144

2-s2.0-33745126405

10.1145/1090191.1080108

Kurth

Zubow

Redlich

J.-P.

Cooperative opportunistic routing using transmit diversity in wireless mesh networks

Proceedings of the 27th IEEE Conference on Computer Communications (INFOCOM ′08)

April 2008

Phoenix, Ariz, USA

1984 1992

2-s2.0-51349104983

10.1109/INFOCOM.2007.188

Tham

C.-K.

HOF: hybrid opportunistic forwarding for multi-hop wireless mesh networks

Proceedings of the IEEE International Conference on Communications (ICC ′08)

May 2008

2963 2968

2-s2.0-51249105285

10.1109/ICC.2008.558

Radunović

Gkantsidis

Key

Rodriguez

An optimization framework for opportunistic multipath routing in wireless mesh networks

Proceedings of the 27th IEEE Conference on Computer Communications (INFOCOM ′08)

April 2008

Phoenix, Ariz, USA

241 245

2-s2.0-51349091585

10.1109/INFOCOM.2007.293

Zhong

Nelakuditi

On the efficacy of opportunistic routing

Proceedings of the 4th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON ′07)

June 2007

441 450

2-s2.0-48049106003

10.1109/SAHCN.2007.4292856

Luk

C.-P.

Lau

W.-C.

Yue

O.-C.

An analysis of opportunistic routing in wireless mesh network

Proceedings of the IEEE International Conference on Communications (ICC ′08)

May 2008

2877 2883

2-s2.0-51249091858

10.1109/ICC.2008.542

Utility-based opportunistic routing in multi-hop wireless networks

Proceedings of the 28th International Conference on Distributed Computing Systems (ICDCS ′08)

July 2008

470 477

2-s2.0-51849154969

10.1109/ICDCS.2008.90

Chachulski

Jennings

Katti

Katabi

Trading structure for randomness in wireless opportunistic routing

Proceedings of the ACM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM ′07)

August 2007

Kyoto, Japan

169 180

2-s2.0-36949027308

10.1145/1282380.1282400

10.

Katti

Katabi

Balakrishnan

Medard

Symbol-level network coding for wireless mesh networks

Proceedings of the ACM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM ′08)

August 2008

Seattle, Wash, USA

401 412

2-s2.0-65249117585

10.1145/1402946.1403004

11.

Shah

R. C.

Wiethölter

Wolisz

Modeling and analysis of opportunistic routing in low traffic scenarios

Proceedings of the 3rd International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt ′05)

April 2005

294 304

2-s2.0-33744491783

10.1109/WIOPT.2005.30

12.

Zeng

Lou

Zhai

On end-to-end throughput of opportunistic routing in multirate and multihop wireless networks

Proceedings of the 27th IEEE Conference on Computer Communications (INFOCOM ′08)

April 2008

Phoenix, Ariz, USA

1490 1498

2-s2.0-51349107935

10.1109/INFOCOM.2007.133

13.

MIT Roofnet

http://www.pdos.lcs.mit.edu/roofnet/

14.

Qiu

Zhang

Wang

Han

M. K.

Mahajan

A general model of wireless interference

Proceedings of the 13th Annual ACM International Conference on Mobile Computing and Networking (MobiCom ′07)

September 2007

171 182

2-s2.0-37749020501

10.1145/1287853.1287874

15.

Jain

Padhye

Padmanabhan

V. N.

Qiu

Impact of interference on multi-hop wireless network performance

Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (MobiCom ′03)

September 2003

66 80

2-s2.0-1542299160

16.

Zhai

Fang

Impact of routing metrics on path capacity in multirate and multihop wireless ad hoc networks

Proceedings of the 14th IEEE International Conference on Network Protocols (ICNP ′06)

November 2006

86 95

2-s2.0-46149104400

10.1109/ICNP.2006.320201

17.

Lawler

E. L.

Lenstra

J. K.

Kan

A. R.

Generating all maximal independent sets: NP-hardness and polynomial time algorithms

SIAM Journal on Computing 1990 9 3 558 565

10.1137/0209042

18.

Zhai

Fang

Physical carrier sensing and spatial reuse in multirate and multihop wireless ad hoc networks

Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM ′06)

April 2006

Barcelona, Spain

1 12

2-s2.0-39049145668

10.1109/INFOCOM.2006.119

19.

Qiu

Zhang

Mahajan

Rozner

Predictable performance optimization for wireless networks

Proceedings of the ACM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM ′08)

August 2008

Seattle, Wash, USA

413 425

2-s2.0-65249178835

10.1145/1402946.1403005