# «Chapter 3 Opportunistic Routing in Wireless Mesh Networks Amir Darehshoorzadeh, Lloren¸ Cerd`-Alabern and Vicent Pla c a Contents 3.1 Introduction ...»

In a recent work, Le and Liu [28] propose an overlay multicast to adapt OR in wireless network. They construct a minimum overlay Steiner tree, and map it into unicast OR relay path connecting the source with all destinations. Their protocol does not exploit opportunistic receptions across diﬀerent links in that tree. They employed unicast OR on each link of the tree.

In [13], we propose a new multicast routing protocol based on OR named Multicast Opportunistic Routing Protocol, MORP. It opportunistically employs a set of forwarders to send a packet toward all destinations. MORP uses a three-way-handshaking where the sending node selects the candidates and towards which destinations they have to forward the packet. The basic idea of MORP is to form a CS to reach the destinations and based on the candidates which successfully receive the packet, selects a set of candidates as the forwarders to reach all destinations. Each forwarder is responsible for sending the packet to a subset of destinations.

Indeed, based on the candidates that successfully receive the packet in each transmission, MORP builds a multicast tree on the ﬂy using OR and forwards the packet through the tree.

**3.8 Opportunistic Routing Analytical Models**

There are some papers which propose analytical models to study the performance of OR.

Baccelli et al. [4] used simulations to show that OR protocols signiﬁcantly improve the performance of multihop wireless networks compared to the shortest path routing algorithms, and elaborated a mathematical framework to prove some of the observations obtained by the simulations.

In [33] an analytical approach for studying OR in wireless multi-hop networks have been proposed. They used lognormal shadowing and Rayleigh fading models for packet reception.

In their model they assume that the nodes are uniformly distributed over the plane. The authors did not consider any speciﬁc candidate selection algorithm, but simply compute the expected progress of the packet transmissions based on the probability of any node in the progressing region successfully receives the packet.

Zubow et al. in [23] claimed that shadow fading losses for spatially close candidates are not independent from each other, unlike commonly assumed. They presented measurements obtained from an indoor testbed and concluded that correlations can not be neglected if nodes are separated by less than 2 m. The authors of [40] proposed an utility-based model for OR and claimed that for the optimal solution it is necessary to search all loop-free routes from the source to the destination. They proposed both optimal and heuristic solutions for selecting the candidates according to their utility function. In [32] an algebraic approach is applied to study the interaction of OR routing algorithms and routing metrics. They showed that OR in combination with ETX could degrade the performance of network.

In [10] we proposed a Markov model to assess the improvement that may be achieved using OR. This model is the basis of the analytic approach described in section 3.9.1. At the same time, Li and Zhang published an analytical framework to estimate the transmission costs of packet forwarding in wireless networks [30]. Both approaches are similar in their formulation, although diﬀer in the way the model is solved: our model leads to a discrete phase-type distribution, while in [30] transmission costs are computed using spectral graph theory. In [9] we have derived the equations that yield the distances of the candidates in OR such that the per transmission progress towards the destination is maximized. There, we have proposed a lower bound to the expected number of transmissions needed to send a packet using OR.

In [8], the issue of optimal CS selection in the OR has been addressed. They provide an analytical framework to model the problem of selecting the optimal CS for both the constrained and unconstrained CS selection. They proposed two algorithms for optimal CS selection, one for the constrained and one for the unconstrained case.

**3.9 Performance Evaluation**

In this section we propose a simple Markov chain model to study the performance of the candidate selection algorithms described in section 3.4. Our model can be used to compute the probability distribution and moments of the number of transmissions needed to send a packet from the source to the destination in a variety of scenarios. For each node, the ordered list of candidates and the delivery probability to each of them are inputs to our model.

Hence, our model does not require any speciﬁc assumptions about the network topology nor the mechanism for selection and prioritization of candidates.

**3.9.1 Markov Model**

We will consider one tagged connection. Each node has a set of candidates that can opportunistically route the packets towards the destination. In order to simplify the explanation of our model, we will ﬁrst describe a simple scenario, and then we will generalize it.

Consider a linear network topology of N nodes equally spaced a distance x = D/(N − 1), being D the distance between the source s and the destination d of the tagged connection (see ﬁgure 3.8).

x [m]

Let p(x) be the probability of successfully delivering a packet to node located at a distance x. The nodes retransmit the packets until successful delivery. With the assumption of independent delivery probabilities, and the nodes always routing the packets to their closest

**neighbor, the average number of transmissions Nt in uni-path routing is given by:**

Assume now that OR is used with a list of 2 candidates. That is, we assume that upon transmission, if any of the next 2 neighbors toward the destination receive the packet, the closest node to the destination opportunistically becomes the next-hop towards the destination. We can model this routing by means of the absorbing DTMC depicted in ﬁgure 3.9.

**The transition probabilities are given by:**

p1 = p(2 x) p2 = p(x) (1 − p1 ) p3 = 1 − (p1 + p2 ) (3.3) p1 = p(x) p3 = 1 − p1.

The DTMC models the progress of a packet from source to destination. The initial state is 1 and a transition occurs at each transmission shot. When the DTMC is in state i it represents that the packet has progressed up to node i. Eventually the packet reaches its destination when the DTMC is absorbed at state N.

A similar DTMC can be easily derived for 3 candidates and so on, until all possible nodes are candidates (we shall refer to this case as inﬁnite candidates). Furthermore, the model can be readily extended to an arbitrary network. The only ingredients needed to build the transition probability matrix are the CSs involved in the routing from s to d, and the delivery probabilities to reach them. Notice that these CSs are: the candidates of node s towards d, the candidates of these candidates towards d, and so on until d (whose CS is the empty set).

A detailed description of the process to build to build the transition probability matrix is given next.

We will utilize graph theory notation for the sake of being concise. Let G = (V, E) be the graph of the network. The vertex s is the source and d is the destination of the tagged connection (s, d ∈ V ). Note that we will use node/vertex and link/edge interchangeably.

Let p(i, j) 0 the delivery probability of the edge between the pair of vertices i, j. Let Ci,d = {ci (1), ci (2), · · · ci (ni )}, Ci,d ⊆ V the ordered set of candidates of vertex i (ci (1) is the best candidate to reach d and ci (ni ) is the worst). As before, each vertex of the graph is a state of the DTMC, being d the absorbing state. The transition probabilities pij = 0 are

**given by:**

where T governs the transmissions before reaching the destination, and t = [p1N p2N · · · pN −1N ]T are the probabilities to reach the destination in one transmission from the nodes 1, · · ·, N − 1.

Let X1 be the random variable equal to the number of transitions from the source (node

1) until absorption. Note that in our model this is the number of transmissions since the source ﬁrst transmits the packet, until it is received by the destination. The DTMC obtained in our model represents a discrete phase-type distribution [26]. Thus, the point probabilities

**and factorial moments of X1 are given by:**

**grouping E[Xi ] we get:**

ni 1+ l=1 pil E[Xl ] E[Xi ] =, i = d. (3.11) 1 − pii Taking E[Xd ] = 0, the equation (3.11) can be used to compute the expected number of transmissions needed to send a packet from the source s to the destination d by using Cs,d as the CS of s to reach node d. Note that the loop free property of the chain guarantees that the recursive equation (3.11) is ﬁnite.

Equation (3.11) has been obtained by other methods in [16] and [49], where it is referred to as least cost any-path and expected any-path transmissions (EAX) respectively. We shall adopt the acronym EAX to refer to it. As explained in section 3.4, some candidate selection algorithms for OR use the Expected Transmission Count (ETX) metric. Although ETX is much simple to compute than EAX, it does not accurately compute the expected number of transmissions under OR.

3.9.3 Propagation Model In order to assess the delivery probabilities we will assume that the channel impediments are characterized by a shadowing propagation model: the power received at a distance x is given

**by:**

0.6 0.4 0.2

is a path-loss exponent and XdB is a Gaussian random variable with zero mean and standard deviation σdB.

Packets are correctly delivered if the received power is greater than or equal to RXThresh.

Note that we shall not consider collisions in our model. Thus, the delivery probability at a

**distance x (p(x)) is given by:**

We have set the model parameters to the default values used by the network simulator (ns-2) [1], given in table 3.7. We shall use these values in the numerical results presented in section 3.9. With these parameters the link delivery probability is approximately 40% at the distance of 150 m.

** Table 3.7: Default values in ns-2 for the shadowing propagation model.**

3.9.4 Evaluation Methodology We shall use the notation ExOR(n) to refer to ExOR with ncand = n, and similarly for the other algorithms under study (see the legend of ﬁgures 3.11–3.19).

**We have proceed has follows:**

• First the network topology is set up randomly placing the nodes in a square ﬁeld with diagonal D = 300 m, except the source and the destination which are placed at the end points of one of the diagonals. We consider scenarios with diﬀerent number of nodes (10 ≤ N ≤ 50).

• The shadowing propagation model described in section 3.9.3 is used to assess the delivery probabilities of the links (qij in the model described in section 3.9.1). We have assumed that a link between any two nodes exists only if the delivery probability between them is greater (or equal) than min.dp = 0.1.

• We assume that the topology and delivery probabilities are known by all nodes, and for each of them it is used one of the algorithms described in section 3.4 to compute the CSs for the given destination.

• Finally, we use the DTMC model described in section 3.9.1 to compute the following performance measures: expected number of transmissions, variance of the expected number transmissions, probability of the number of transmissions.

We have done this evaluation using the R numerical tool [34]. Each point in the plots is an average over 100 runs with diﬀerent random node positions. We have used this methodology for each of the algorithms described in section 3.9.1, and for a diﬀerent maximum number of candidates: ncand = 2, 3, 4, 5, ∞. Recall that we refer as ncand = ∞ to the case when there is no limit on the maximum number of candidates and all possible nodes can be selected as candidates.

As an estimation of the computational cost of the algorithms, we have measured the execution time it takes to compute the CSs in each scenario. These times have been obtained running the algorithms on a computer with an Intel Xeon Dual-Core 2 3.3 GHz, FSB 1333 MHz, with 4 MB cache and 12 GB of memory.

3.9.5 Numerical Results Expected Number of Transmissions First, we we examine in detail the case with at most 3 candidates for each node (ncand = 3), as shown in ﬁgure 3.11. For the sake of comparison, we have included the scenarios using uni-path routing and also the optimal candidate selection algorithm in the case ncand = ∞ (we shall refer to it as Opt(∞)). Note that uni-path routing is equivalent to use ncand = 1 in any of the OR algorithms under study. The curves have been obtained varying the number of nodes, but maintaining the distance D = 300 m between the source and the destination, thus, increasing the density of the network.

As a ﬁrst observation in ﬁgure 3.11, we can see that using any OR algorithm outperforms the traditional uni-path routing. Regarding the optimal algorithms, LCOR and MTS, we have validated that they choose exactly the same CSs, and thus, the curves are the same.

D=300m, β=2.7, σdB =6, min.dp=0.1 5.6

Additionally, for ncand = ∞ the expected number of transmissions for LCOR and MTS are the same, so we show only one of the curves obtained with LCOR(∞) and MTS(∞) (indicated as Opt(∞)).