FREE ELECTRONIC LIBRARY - Abstracts, online materials

Pages:     | 1 |   ...   | 3 | 4 || 6 |

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

-- [ Page 5 ] --

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 significantly 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 [9] 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 effective at reducing the expected number of transmissions (EAX). Although this does not guarantee choosing the optimal CSs, we can see from the figure 3.11 that the results are very close to the optimal algorithm.

Regarding the scenario with ncand = ∞, figure 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 figure 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 difficult, and possibly will introduce large signaling overhead and duplicate transmissions. Therefore, the differences obtained with ncand = 3 and ncand = ∞ in a real scenario, are likely to be much smaller than those shown in figure 3.11.

For other scenarios we have obtained similar results. For instance, figures 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 different 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 difference compared with the other algorithms (not noticeable in the graphs).

By comparing figures 3.13 and 3.14 we can see that the difference 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 difference 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 significantly 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 significant part of the potential reduction. This effect 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 benefits. Firstly, the variability of the transmission delays may be significantly 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-off 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 figures 3.17 and 3.18, respectively.

The probability curves for the ncand = 1 case (uni-path routing) in both figures 3.17 and 3.18 are almost the same. These figures 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 figures 3.17 and 3.18 we can see that, by using OR algorithms, the number of transmissions needed to reach the destination is significantly 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 figure 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 figures 3.17 and 3.18 we can see that the probabilities change significantly for the ncand = ∞ case. For instance, in figure 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 figure 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 figure 3.19 have been obtained by averaging over the 100 runs of the corresponding points in figure 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 finish. 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 finish while LCOR needs about 3.3 hours. Recall that MTS(3) first 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 classified different 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 different 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 differences between each algorithm under study we have used a simple example running for each algorithm.

Regarding the different 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 briefly describe different protocols that apply OR to multicast routing. Most of them first 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 different 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.

Pages:     | 1 |   ...   | 3 | 4 || 6 |

Similar works:

«CUSTOMER RELATED FACILITIES MANAGEMENT PROCESS AND ITS MEASUREMENT: UNDERSTANDING THE NEEDS OF THE CUSTOMER Dilanthi Amaratunga David Baldry Richard Haigh Research Institute for the Built and Human Environment The University of Salford ABSTRACT In the past, organisations could concentrate on their internal capabilities, emphasising product performance and technology innovation. Organisations that did not understand their customers’ needs eventually found that competitors could make inroads by...»

«OnStar Europe User Terms UK Version date: March 2016 Welcome to OnStar! OnStar Europe Ltd. (OnStar) offers you support, vehicle information and connectivity in your car including:  Automatic Crash Response  Emergency Service (SOS) Button  Wi-Fi HotSpot with 4G LTE (access provided by a third party carrier and subject to local availability and subscription to a data plan)  Vehicle Diagnostics  Dealer Maintenance Notifications  Smartphone App  Theft Alert Notification ...»

«EN Council of the European Union 16854/14 (OR. en) PROVISIONAL VERSION PRESSE 648 PR CO 71 PRESS RELEASE 3359th Council meeting Foreign Affairs Development issues Brussels, 12 December 2014 President Federica Mogherini High Representative of the Union for Foreign Affairs and Security Policy PRESS Rue de la Loi 175 B – 1048 BRUSSELS Tel.: +32 (0)2 281 6319 / 6319 Fax: +32 (0)2 281 8026 press.office@consilium.europa.eu http://www.consilium.europa.eu/press 16854/14 1 E 12 December 2014 PROVISIO...»

«SCIENTIFIC DISCUSSION 1. Introduction Drug addiction is a worldwide problem of which opioid dependence, notably heroin addiction, is a major component. Most addicts inject drugs, quite often with dirty or shared syringes and needles and this behaviour is linked directly with the transmission of human immunodeficiency virus (HIV) and the hepatitis viruses. A key aim of treatment programs for opioid drug dependence is to stop the subjects from injecting drugs. Substitution is the treatment...»

«THE ROLE OF LIMPOPO LEGISLATURE OVERSIGHT COMMITTEES IN DEEPENING DEMOCRACY AND ACCOUNTABILITY FOR THE USE OF PUBLIC RESOURCES Nyathela Hlanganani* and Makhado Rudzani Limpopo Legislature, P/Bag X9309, Polokwane, 0700 *Corresponding Author: Email: nyathelah@limpopoleg.gov.za Abstract The primary aim of this paper is to contribute to the body of knowledge and discourses around oversight and accountability. The paper also broadens the understanding of the concept of oversight and accountability...»

«Municipality of Morin-Heights PROVINCE OF QUEBEC ARGENTEUIL COUNTY MRC DES PAYS D’EN-HAUT MINUTES In case of discrepancy, the French version prevails over the English translation. Minutes of the regular meeting of the Municipal council of Morin-Heights, held at the Council Room, 567, Village, on Wednesday, March 9th, 2016 at which were present: Councillor Leigh MacLeod Councillor Mona Wood Councillor Jean Dutil Councillor Peter MacLaurin forming quorum under the chairmanship of Mayor Timothy...»

«Lega Italiana Protezione Uccelli Associazione per la conservazione della Natura Sezione di Varese Il Lago di Varese: un sistema dinamico e complesso. Il suo stato, le minacce e riflessioni sulle possibili soluzioni.PREMESSA Sempre più spesso sulla stampa locale si sente parlare del Lago di Varese e del suo stato di salute e conservazione. Da anni la nostra associazione si batte per la difesa di quest’area e dell’adiacente riserva Palude Brabbia, collegata strettamente all’ecosistema del...»


«1 This review should be cited as: Burns, C., A. Jordan, V. Gravey, N. Berny, S. Bulmer, N. Carter, R. Cowell, J. Dutton, B. Moore S. Oberthür, S. Owens, T. Rayner, J. Scott and B. Stewart (2016) The EU Referendum and the UK Environment: An Expert Review. How has EU membership affected the UK and what might change in the event of a vote to Remain or Leave?E-copies of this review and a short executive summary can be downloaded from: http://environmentEUref.blogspot.co.uk/ Introduction In 2015...»

«Contact information: (Phone) – 805-984-5907 (Fax) – 805-984-2397 Email: info@filmclipsonline.com 4903 Island View St Channel Islands Harbor, CA 93035 visit us online at: www.FilmClipsOnline.com and www.paulistproductions.org © Copyright 2011 Film Clips Spirit of America     FILM CLIPS for CATHOLIC YOUTH FAITH FORMATION Study Guide INTRODUCTION: Film Clips for Youth Faith Formation is an exciting and creative approach to the faith formation of youth that uses a medium for which they...»

«Resource Efficiency and Fiduciary Duties of Investors Final Report ENV.F.1/ETU/2014/0002 DG Environment mmmll Resource efficiency and fiduciary duties of investors Resource Efficiency and Fiduciary Duties of Investors Final Report European Commission, DG Environment This report has been produced by Ernst & Young Cleantech and Sustainability Services (France) on behalf of the European Commission. Contract details European Commission, DG Environment, ENV.F.1/ETU/2014/0002 Study on resource...»

«“ E V E R Y DAY S” I N SO C I A L I SM AND POST-SOCIALISM GYÖRGY MAJTÉNYI A Stain on the Blue Couch Lifestyles of the Dominant Elite in Hungary during the 1950’s and 1960’s “T he villa was illuminated with Chinese lanterns decorated with coloured tissue papers. Before the entrance on the right hunters were standing in dress uniform, and on the left were the party-youth wearing blue shirts and red neckties. The celebrated was not only a party member but, of course, a hunter as well....»

<<  HOME   |    CONTACTS
2017 www.abstract.dislib.info - Abstracts, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.