FREE ELECTRONIC LIBRARY - Abstracts, online materials

Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |

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

-- [ Page 4 ] --

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 different 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 fly 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 significantly 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 specific 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 differ 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 specific 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 first 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 figure 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 figure 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 infinite 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 first 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 finite.

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


–  –  –

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 figures 3.11–3.19).

We have proceed has follows:

• First the network topology is set up randomly placing the nodes in a square field 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 different 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 different random node positions. We have used this methodology for each of the algorithms described in section 3.9.1, and for a different 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 figure 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 first observation in figure 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(∞)).

Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |

Similar works:

«GARY B. CONINE* The Prudent Operator Standard: Applications beyond the Oil and Gas Lease ABSTRACT Recent court decisions have determined that the joint operating agreement used by the petroleum industry contains implied duties arisingfrom the notion that the operator must perform whatever actions are reasonable under the circumstances. This article concludes that the operatingagreement should not be construed under rules associatedwith relationalcontracts,like the oil andgas lease, but under...»

«No 26100 Gaceta Oficial Digital, jueves 07 de agosto de 2008 1 LEY 55 De 6 de agosto de 2008 Del Comercio Marítimo LA ASAMBLEA NACIONAL DECRETA: Título I Las Naves Capítulo I Disposiciones Generales Artículo 1. Las naves mercantes, aunque muebles por su naturaleza, constituyen una clase particular, regida por las disposiciones del Derecho Común en cuanto no resulten modificadas por las disposiciones del presente Título. Artículo 2. Para los efectos de la presente Ley, los siguientes...»

«(Nome della Nave). (Nome della Compagnia) (fare rif.to ai dati che saranno contenuti nel “Continuous Synopsis Record richiesto dalla Solas XI-1/5”) PIANO SECURITY NAVE (Ship Security Plan) Conforme alla SOLAS 74 Capitolo XI-2 e al Codice Internazionale per la Sicurezza delle Navi e degli Impianti Portuali (ISPS Code) Emesso il. Preparato da (Responsabile Security della Compagnia “Company security Officer (CSO)” nome e firma).. Copia Controllata nr. di copie Rilasciata a (vedere Cap....»

«School Caretakers’ and Cleaners’ (including Canteen Workers) Collective Agreement 1 April 2015 to 1 December 2016 School Caretakers and Cleaners (including Canteen Workers) 2015-2016 Page 1 INDEX (Note: Part 1 and Parts 4-7 apply to all workers) PART 1 – APPLICATION/TERM OF AGREEMENT 1.1 Parties to the Agreement 1.2 Coverage 1.3 Term of the Agreement 1.4 Variations to the Agreement 1.5 Transitional Arrangements 1.6 Definitions 1.7 Service PART 2 – CLEANERS 2.1 Application 2.2 Wages 2.3...»

«WQC 2011 Teadus, loodus 1. Millise lindude sugukonna suurim liik on Patagona gigas, kuigi pikkust on linnul vaid 20 cm ja kaalu 20 g?2. Millise mõõtühiku esialgne määratlus oli «vahemaa Maa ekvaatorilt pooluseni, jagatuna kümne miljoniga»?3. Liibüa nafta on maailma parimate seas, sest on valdavalt «kerge ja mahe (sweet)». «Kerge» tähendab, et selle erikaal on väike. «Mahe» viitab, et ühe elemendi sisaldus selles on alla 0,5 protsendi. Millise elemendi? 4. Millisel...»

«A Guide to Critical Reflection Ontario Association of Interval and Transition Houses Prepared by Angie Rupra of New Wave Consulting For OAITH © A Guide to Critical Reflection: OAITH © Introduction 3 Acknowledgements 4 Who is this manual for? 5 Why was this Manual Created? 5 What is the Purpose of the Manual? 7 Suggested Ways to use the Manual 7 A Note on Critical Self-reflection 8 An Introduction to a Feminist Anti-Oppression Framework 13 Part 1: Case Studies Advocacy 19 Parenting 25...»

«Lysterfield Lake Park, Victoria Saturday 8th November 2014 20th JUNE 2009 Kathmandu Adventure Series Page 1 of 9 Lysterfield Lake Sat 8th November 2014 These instructions contain all the information you need for race weekend. Make sure you read them carefully! Welcome to the Kathmandu Adventure Series 2014 – Lysterfield Lake, Victoria! Lysterfield Park is one of the most valuable recreation and conservation areas close to Melbourne. As well as being a beautiful spot to visit it offers...»

«SUSTAINABLE FISHERIES MANAGEMENT PROJECT (SFMP) Partners Meeting Report FEBRUARY 25-26, 2015 This publication is available electronically on the Coastal Resources Center’s website at http://www.crc.uri.edu/projects_page/ghanasfmp/ For more information on the Ghana Sustainable Fisheries Management Project, contact: USAID/Ghana Sustainable Fisheries Management Project Coastal Resources Center Graduate School of Oceanography University of Rhode Island 220 South Ferry Rd. Narragansett, RI 02882...»

«Tanks in Grozny Translated by Arch Tait This article is published in English by The Henry Jackson Society by arrangement with Radio Free Europe / Radio Liberty. TANKS IN GROZNY 1 Twenty years ago, the trigger was pulled to start the First Chechen War. Early one Saturday morning, on 26 November 1994, over 3,000 “militia volunteers” entered Grozny from several directions with the support of 40, perhaps even 50, tanks. Most of the tanks were crewed exclusively by serving soldiers of the...»

«Human Rights Watch January 2004, Vol. 16, No. 1 (A) Some Transparency, No Accountability: The Use of Oil Revenue in Angola and Its Impact on Human Rights I. Summary II. Recommendations To the Government of Angola To the International Monetary Fund To the World Bank To Donor governments, the G-8 and Member Governments of the Extractive Industries Transparency Initiative To Oil Companies Operating in Angola III. Background: The IMF and Angolan Government Staff-Monitored Programs: 1995-2001 The...»

«Blending different latency traffic with alpha-mixing Roger Dingledine1, Andrei Serjantov2, and Paul Syverson3 1 The Free Haven Project (arma@freehaven.net) 2 The Free Haven Project (aas23@freehaven.net) 3 Naval Research Laboratory (syverson@itd.nrl.navy.mil) Abstract. Currently fielded anonymous communication systems either introduce too much delay and thus have few users and little security, or have many users but too little delay to provide protection against large attackers. By combining...»

«This resource guide is provided by:  NAMI Michigan    For more information, please contact us:  921 N. Washington Ave.  Lansing, MI 48906  517.485.4049  800.331.4264  info@namimi.org  www.namimi.org  www.facebook.com/namiofmi    www.twitter/namiofmi  Please help NAMI Michigan continue to serve those affected by mental  illness by joining or donating to our organization.  Fill out and mail the ...»

<<  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.