«Chapter 3 Opportunistic Routing in Wireless Mesh Networks Amir Darehshoorzadeh, Lloren¸ Cerd`-Alabern and Vicent Pla c a Contents 3.1 Introduction ...»
We can see that the expected number of transmissions obtained with OAPF is only slightly larger than those obtained with the optimal algorithms. Finally, we observe that the expected number of transmissions required by ExOR is signiﬁcantly larger than any other OR algorithms. The reasons that motivate this inferior performance of ExOR are the following: recall that ExOR is a simple algorithm that uses ETX as the metric for selecting candidates. It looks for the candidates running SPF after removing the links to the nodes that have already been selected as candidates. By doing this, the candidates tend to be chosen close to each other. In  we have investigated the optimal position of the candidates and we have shown that they are not clustered, but distributed over distances that approximate to the destination. Therefore, we conclude that ExOR does a coarse selection of the CS. On the other hand, recall that OAPF incrementally adds the nodes to the CS that are most eﬀective at reducing the expected number of transmissions (EAX). Although this does not guarantee choosing the optimal CSs, we can see from the ﬁgure 3.11 that the results are very close to the optimal algorithm.
Regarding the scenario with ncand = ∞, ﬁgure 3.11 shows that it achieves a noticeable reduction of the expected number of transmissions compared to the scenario with ncand = 3.
However, as shown in ﬁgure 3.12, this is at cost of using a large number of candidates. Note that implementing an OR protocol with a high number of candidates is diﬃcult, and possibly will introduce large signaling overhead and duplicate transmissions. Therefore, the diﬀerences obtained with ncand = 3 and ncand = ∞ in a real scenario, are likely to be much smaller than those shown in ﬁgure 3.11.
For other scenarios we have obtained similar results. For instance, ﬁgures 3.13 and 3.14 have been obtained, respectively, maintaining the total number of nodes equal to N = 10 and N = 50 (thus, representing a low and high density network), and varying the maximum number of candidates to: ncand = 1, 2, · · ·, 5 and ∞. Note that ncand = 1 is equivalent to uni-path routing, thus, the expected number of transmissions obtained for ncand = 1 is the same for all algorithms.
In the case of ncand = ∞ all algorithms have almost the same expected number of transmissions. This comes from the fact that in this case there is not any limitation on the maximum number of candidates. Therefore, all nodes which are closer to the destination than the source can be selected as candidates, and all of the algorithms have almost the same CSs.
Note that since ExOR uses ETX as the metric to select candidates, the order of candidates may be diﬀerent compared with the CSs in the other algorithms. Because of that the expected number of transmissions in the case of ExOR with ncand = ∞ has a very small diﬀerence compared with the other algorithms (not noticeable in the graphs).
By comparing ﬁgures 3.13 and 3.14 we can see that the diﬀerence between ExOR and the other algorithms is higher in a dense network (N = 50). This comes from the fact that in a dense network there is a larger number of possible choices of the CSs. Thus, limiting the maximum number of candidates makes the selection of the candidates sets more critical.
However, we can see that the diﬀerence between OAPF and the optimal algorithms is kept small even in a dense network. We can see that increasing maximum number of candidates (ncand) from 1 to 2 results in an important gain in all cases and increasing ncand from 5 to ∞ is more important in the dense topology.
3.9.6 Variance of Expected Number of Transmissions
One of the metrics which can also be calculated with our model is the variance of expected number of transmissions from source to the destination. Figures 3.15 and 3.16 show the variance of expected number of transmissions for a low (N = 10) and high (N = 50) density network, respectively. Since with one candidate all algorithms have the same result as unipath routing the variances of the expected number of transmissions for ncand = 1 are the same.
Figures 3.15 and 3.
16 show that using OR the variance of the expected number of transmissions is signiﬁcantly reduced compared with uni-path routing. It is also observed that D=300m, beta=2.7, sigmadB =6, min.sp=0.1
Figure 3.14: Expected number of transmissions for the random topology with N = 50 nodes varying maximum the number of candidates.
while the variance decreases with the value of ncand, just a small of value (typically 2 or 3 candidates per node) is enough to attain a signiﬁcant part of the potential reduction. This eﬀect is even more noticeable when the candidate selection algorithm employed is ExOR. Furthermore, while ExOR is the algorithm that yields the highest mean number of transmissions, as it was shown above, it achieves the lowest variance.
The reduction of variance of the expected number of transmissions, compared with unipath routing, has two important beneﬁts. Firstly, the variability of the transmission delays may be signiﬁcantly reduced using OR. Secondly, this fact indicates that the number of retransmissions of a packet by the same node may be also reduced using OR. This may also contribute on the reduction of the transmission delay variability, due to the back-oﬀ algorithm used at the MAC layer.
D=300m, beta=2.7, sigmadB =6, min.sp=0.1
3.2 2.4 1.6
3.2 2.4 1.6
Figure 3.16: Variance of the expected number of transmissions for the random topology with N = 50 nodes varying the maximum number of candidates.
3.9.7 Probability Distribution of the Number of Transmissions For having a more detailed comparison, we have included the probability distribution of the number of transmissions for ncand = 1, 3 and ∞ for a small number of nodes N = 10 and a large one N = 50, in ﬁgures 3.17 and 3.18, respectively.
The probability curves for the ncand = 1 case (uni-path routing) in both ﬁgures 3.17 and 3.18 are almost the same. These ﬁgures show that for N = 10 in the uni-path routing, about 14% of packets reach the destination with 3 transmissions, while about 40% of packets need 6 or more transmissions. In ﬁgures 3.17 and 3.18 we can see that, by using OR algorithms, the number of transmissions needed to reach the destination is signiﬁcantly reduced with respect to the uni-path routing approach. The curves for all algorithms except ExOR are almost the same. In a low density network (N = 10), using the optimal candidate selection algorithms (LCOR or MTS) in the ncand = 3 case, 18% and 37% of packets reach the destination with 2 and 3 transmissions, respectively, while using ExOR only about 5% of packets reach the destination with 2 transmissions. In the network with more nodes (N = 50), LCOR, MTS and even OAPF can select the candidates which are close to the destination.
Therefore as we can see in ﬁgure 3.18 by using these algorithms with ncand = 3 about 20% and 50% of packets reach the destination with 2 and 3 transmissions, respectively.
By comparing the ﬁgures 3.17 and 3.18 we can see that the probabilities change signiﬁcantly for the ncand = ∞ case. For instance, in ﬁgure 3.18 about 50% of packets reach the destination only with 2 transmissions, while in the low dense network (N = 10) only 25% of packets reach the destination with 2 transmissions. Looking at ﬁgure 3.12 we can see that, the ncand = ∞ case uses 25 candidates in a dense network (N = 50). With such a large number of candidates it is likely that some candidate close to the destination will receive the packet, thus, allowing the delivery to the destination with only two transmissions.
3.9.8 Execution Time
In this section we estimate the computational cost of the algorithms under study by measuring the execution time it takes to compute the CSs towards the destination necessary to solve the DTMC model described in section 3.9.1. Recall that these CSs are: the candidates of the source s towards the destination d, the candidates of these candidates towards d, and so on until d (whose candidates is the empty set). Notice that for EXOR this requires calling Algorithm 1 for the source s, for its candidates, the candidates of these candidates, and so on until d. For the other algorithms, computing the CSs of the source requires the computation of all the necessary CSs. This comes from the fact that the other algorithms are based on the EAX metric, which requires the CSs. Therefore, for the algorithms OAPF, LCOR and MTS, the execution time is the time it takes calling only once the algorithms 2, 3 and 4, respectively.
Figure 3.19 shows the expected number of transmissions versus the execution time in logarithmic scale.
We have selected ncand = 3 as a sample case for our study. So, the points in ﬁgure 3.19 have been obtained by averaging over the 100 runs of the corresponding points in ﬁgure 3.11. The values next to the points represent the number of nodes of the network N.
We can see that for all the algorithms, the larger is the number of nodes the lower is the expected number of transmissions and the higher is the execution time. As expected, the fastest algorithm is ExOR whereas LCOR is the slowest. For instance, when the number of nodes in the network is 50, LCOR needs about 3.3 hours to ﬁnish. Obviously, with a maximum number of candidates larger than 3 the execution time will be much longer. OAPF lies between the exhaustive search of the optimal algorithms and the simplicity of ExOR, and thus, has an execution time that falls in between these algorithms, e.g. 0.6 to 47 seconds for the low and high density networks, respectively.
MTS and LCOR have the same expected number of transmissions while the execution time of MTS is much lower than LCOR. For instance in the high density network (N = 50) MTS needs about 40 minutes to ﬁnish while LCOR needs about 3.3 hours. Recall that MTS(3) ﬁrst looks for the optimal candidates sets without limiting the maximum number of candidates, D= 300 m, β= 2.7, σdB = 6, min.dp= 0.1 0.6
Figure 3.19: Expected number of transmissions and execution time of all algorithms.
3.10 Conclusions In this chapter we have described the meaning of Opportunistic Routing (OR) which has been introduced as a way of using the broadcast nature of multi-hop wireless networks. We have classiﬁed diﬀerent research areas in OR: routing metrics, candidate section, candidate coordination, geographic OR and multicast OR. Then, we have surveyed the main research contributions in each category.
The two usual metrics that used in the literature of OR, ETX and EAX, have been discussed in detailed. Although ETX is simpler to compute than EAX, it does not accurately compute the expected number of transmissions under OR. The other important issues of OR is the candidate selection. We have described in detail four diﬀerent candidate selection algorithms that have been proposed in the literature. They range from non-optimum, but simple, to optimum, but with a high computational cost. To show the diﬀerences between each algorithm under study we have used a simple example running for each algorithm.
Regarding the diﬀerent candidate coordination approaches we have described the four most used methods of coordination in OR: acknowledgment-based, timer-based, network coding and RTS-CTS; and have explained the advantages and disadvantages of each approach.
Applying the OR paradigm to multicast routing is another new research direction. The availability of multiple destinations can make the selection of CS and coordination among them complicated. There are few works that have tried to adapt OR to multicast settings.
We have brieﬂy describe diﬀerent protocols that apply OR to multicast routing. Most of them ﬁrst create the shortest path tree to the destinations and then send the packet through the tree using OR.
After the general overview and introduction of OR we have focused on its performance analysis. First, we have surveyed the existing performance studies that are based on analytical models. Then, we have introduced our own contribution, a discrete time Markov chain model to analyze the performance gain that may be achieved by using OR. In our model the nodes are represented by the states of the chain, and the state transitions model how the packet progresses through the network. The only ingredients needed to build the transition probability matrix are the candidates of each node, and the delivery probabilities to reach them. As a consequence, the proposed model can be applied independently of the candidate selection algorithm that is employed. The model leads to a discrete phase-type representation for the distribution of the number of transmissions that are needed to reach the destination node. An important advantage of the phase-type representation is that there exist simple and closed-form expressions for its distribution and moments.
We have applied our model to compare four relevant algorithms that have been described in the candidate selection section. We have compared diﬀerent scenarios in terms of the expected number, the variance and the probability of the number transmissions needed to send a packet from source to the destination. The algorithms have also been compared from the perspective of the the execution time which is needed to construct the CSs.