FREE ELECTRONIC LIBRARY - Abstracts, online materials

Pages:   || 2 | 3 | 4 | 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 1 ] --

Chapter 3

Opportunistic Routing in Wireless

Mesh Networks

Amir Darehshoorzadeh, Lloren¸ Cerd`-Alabern and Vicent Pla

c a


3.1 Introduction

3.1.1 Issues in Opportunistic Routing..................... 3

3.1.2 Research Directions in Opportunistic Routing............. 4

3.2 Routing Metrics............................. 6

3.3 Candidate Coordination Methods.................. 7 3.3.1 Acknowledgment-Based Coordination................. 8 3.3.2 Timer-Based Coordination

3.3.3 Network Coding Coordination

3.3.4 RTS-CTS Coordination......................... 10

3.4 Candidate Selection Algorithms.................... 11 3.4.1 Extremely Opportunistic Routing (ExOR)............... 12 3.4.2 Opportunistic Any-Path Forwarding (OAPF)............. 13 3.4.3 Least-Cost Opportunistic Routing (LCOR).............. 15 3.4.4 Minimum Transmission Selection (MTS)................ 16

3.5 Network Coding Opportunistic Routing............... 18

3.6 Geographic Opportunistic Routing.................. 19

3.7 Multicast Opportunistic Routing................... 20

3.8 Opportunistic Routing Analytical Models.............. 20

3.9 Performance Evaluation

3.9.1 Markov Model.............................. 21 3.9.2 Expected Number of Transmissions................... 24 3.9.3 Propagation Model............................ 24 3.9.4 Evaluation Methodology......................... 25 3.9.5 Numerical Results............................ 26 3.9.6 Variance of Expected Number of Transmissions............ 28 3.9.7 Probability Distribution of the Number of Transmissions....... 30 3.9.8 Execution Time.............................. 31

3.10 Conclusions................................33

3.1 Introduction In recent years, multi-hop wireless networks (MWN) have already become very popular and are receiving an increasing amount of attention by the research community. Compared to wired networks, routing in MWN is specially challenging because of two fundamental differences. The first one is the heterogeneous characteristics of the wireless links: due to the strong dependency of radio transmission impediments between the nodes with their distance and the environmental elements influencing the radio waves propagation. As a consequence, packet delivery probabilities may be significantly different for every link of a MWN network. The second one is the broadcast nature of wireless transmissions: unlike wired networks, where links are typically point to point, when a node transmits a packet in a wireless network, this can simultaneously be received by several neighboring nodes.

Traditional routing protocols proposed for wireless networks perform best path routing, i.e., preselect one fixed route before transmissions starts. Each node in a route uses a fixed neighbor to forward to. Doing this way, in the routing table of every node participating in the routing between a source and a destination, there is a forwarding entry which points to a neighbor (referred to as next-hop), over which packets addressed to the destination will be sent. Note that once all next-hops have been chosen, all packets between a source and destination follow the same path. This motivates the name of uni-path routing for such type of protocols. These approaches borrowed from the routing protocols for wire-line networks, and do not adapt well to the dynamic wireless environment where transmission failures occur frequently.

Opportunistic Routing (OR), also referred to as diversity forwarding [24], cooperative forwarding [17] or any-path routing [16], is being investigated to increase the performance of MWNs by taking advantage of its broadcast nature. In OR, in contrast to traditional routing, instead of preselecting a single specific node to be the next-hop as a forwarder for a packet, an ordered set of nodes (referred to as candidates) are selected as the potential next-hop forwarders. We shall refer to the ordered set of candidate of a node as its CS.

Thus, the source can use multiple potential paths to deliver the packets to the destination. More specifically, when the current node transmits a packet, all the candidates that successfully receive it will coordinate with each other to determine which one will actually forward it, while the others will simply discard the packet.

For a better understanding of the inherent benefits associated to OR, consider the example shown in figure 3.1 (the example has been taken from [5]). It presents the possibility that one transmission may reach a node which is closer to the destination than the particular next-hop in traditional routing.

10% 30%

–  –  –

Assume that S is the source and D is the destination and the packet transmissions in each link are Bernoulli with the delivery probabilities specified over the links. The best path from the source to the destination using traditional routing is S-A-B-D which has

0.9 × 0.9 × 0.9 ≈ 0.72 end-to-end delivery probability. It minimizes the expected number of transmissions from node S to the destination D, 3 × 1/0.9 ≈ 3.33. If a packet sent by S is correctly received by B but not node A, it has to be retransmitted by S until it reaches the designated next-hop A. Another situation that might happen is that a packet sent by S is correctly received by both node A and B. Although node B is closer to the destination than node A, it is not allowed to forward the packet. In contrast to the traditional routing, OR takes advantage of any these situations to maximize the packet progress to the destination.

An OR protocol can use {D, B, A} as the candidates (D is the highest priority candidate, and A the least one) to forward the packet. If both nodes A and B receive the packet but not D, since node B has more priority than A (it is closer to the destination), then it will forward the packet while node A will simply discard it.

Another benefit of OR is that it increases the reliability of transmissions by combining weak physical links into one strong virtual link. In other words, it acts like OR has additional backup links and the possibility of transmission failure is reduced [18]. As shown in figure 3.2 the sender has a low delivery probability to all its neighbors, while they have a perfect link to the destination. Under a traditional routing protocol, we have to pick one of the five intermediate nodes as the relay node. Thus, altogether we need 5 transmissions on average to send a packet from the source to the relay node and 1 transmissions from the relay node to the destination. In comparison, under OR, we can select the five intermediate nodes as the candidates. The combined link has a success rate of (1 − (1 − 20%)5 ) ≈ 67%. Therefore, on average only 1/0.67 = 1.48 transmissions are required to deliver a packet to at least one of the five candidates, and another transmission is required for a candidate to forward the packet to the destination, so on average it takes only 2.48 transmissions to deliver a packet to the destination.

3.1.1 Issues in Opportunistic Routing

Three main issues arise in the design of OR protocols:

• Candidate selection All nodes in the network must run an algorithm for selecting and sorting the set of neighboring nodes (candidates) that can better help in the forwarding process to a given destination. We shall refer to this algorithm as candidate selection.

The aim of candidate selection algorithms is to minimize the expected number of transC1 % <

–  –  –

missions from the source to the destination. In section 3.4 some noteworthy candidate selection algorithms are described.

• OR metric In order to accurately select and prioritize the CSs, OR algorithms require a metric. First OR algorithms were based on simple metrics inherited from traditional unicast routing, as those used by shortests path first (SPF) algorithms. However, some researchers realized that more accurate metrics were required in OR. Different metrics in OR will be discussed in detail in section 3.2.

• Candidate coordination is the mechanism used by the candidates to discover which one has the highest priority that has received, and thus, must forward the packet.

Coordination requires signaling among the nodes, and imperfect coordination may cause duplicate transmission of packets.

With perfect coordination among candidates, the larger is the number of candidates the lower is the expected number of transmissions from the source to the destination.

However, increasing the number of candidates increases also the coordination overhead.

Therefore, in practice, the maximum number of candidates that can be used is limited.

This fact has often been neglected in candidate selection algorithms proposed in the literature. Perfect coordination and no signaling overhead has been assumed and the algorithms have been designed to select all possible candidates to reduce the expected number of transmissions.

3.1.2 Research Directions in Opportunistic Routing In this section we give an overview of the main research contributions in OR. Table 3.1 shows some of the OR research contributions found in the literature that will be described in the

following sections. The meaning of the columns is the following:

• Protocol: Here there is the name of the protocol coined by the authors, or NA if no name was given. The corresponding reference is also provided here.

• Year: Year of publication.

• Type: Method to obtain the numerical results presented in the paper. We use the keys:

S, for simulation; A, for analytical; and E, for Experimental.

• Topic: Main topic of the paper.

• Metric: Metric used by the candidate selection algorithm (see section 3.2).

• Coord.: Coordination method used in the paper (see section 3.3). The table shows NA in those papers where a perfect coordination is assumed without relying in any specific type of coordination.

• Cand. Sel.: Information used by the candidate selection algorithm (see section 3.4):

Topology when it is related with the topological graph of the network, and Location when it uses the geographical position of the nodes.

Entries in table 3.1 are sorted in chronological order. The table shows the increasing interest that has emerged related with OR in the last decade.

Table 3.1: Classification of research works in opportunistic routing protocol.

–  –  –

Most of the research in OR is related with the issues described in section 3.1.1, but there are other areas of OR that have been investigated as well. We have identified the following

as the main topics on research in OR:

• Metrics, section 3.2.

• Candidate coordination, section 3.3.

• Candidate selection algorithms, section 3.4.

• Network coding, section 3.5.

• Geographic OR, section 3.6.

• Multicast OR, section 3.7.

• Sensor networks.

Each of this topics will be addressed in the next sections as indicated above.

Although many of the OR proposals can be adapted for sensors networks, there are some contributions that specifically study OR in this context. As an example, we have included [36] in table 3.1. In this paper the authors take into consideration how OR can be exploited when there are the characteristic power down periods that occur in sensor networks. Due to the limited number of works in this specific area, we do not analyze this topic further.

After the sections explaining the work in the research areas listed above, we continue the chapter by describing analytical models of OR in section 3.8. In section 3.9 we presented some numerical results that illustrate the performance achieved with some relevant candidate selection algorithms described in section 3.4. Finally, some concluding remarks are given in section 3.10.

3.2 Routing Metrics

–  –  –

In OR, however, it is necessary to consider the fact that there are some candidates which can receive the packet, thus, a packet may travel along any of the potential paths. Authors in [15, 29] have shown that using ETX may give suboptimal selection of candidates and in [32] it was shown that OR in combination with ETX could degrade the performance of the network. Because of that Zhong et al. [49] proposed another metric which has bee widely adopted in OR.

Expected Any-path Transmission (EAX) [49]: is an extension of ETX and can capture the expected number of transmissions taking into account the multiple paths that can be used under OR. Alternative methods to compute EAX have been proposed by other authors [15, 29, 10]. In section 3.9.1 we present a model for OR that can be used to calculate the expected number of transmissions from source to the destination.

The following simple example illustrates the meaning of EAX. Consider the network topology and the CS of each node in figure 3.3. Node 1 is the source and node 3 is the destination.

Assume that packet transmissions in each link are Bernoulli with the delivery probabilities from node i to node j, qij, indicated in the figure. Note that in the CS of node 1, node 3 has higher priority than node 2. Note also that node 2 has only one candidate (the destination).

Therefore, upon being the next forwarder, node 2 would behave as in traditional routing.

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

Similar works:

«REVISIONS – 12/3/2015 Note: All revisions are highlighted in yellow. Part 1: Product Demonstration – page 4 2016 MATE ROV COMPETITION: From the Gulf of Mexico to Jupiter’s Moon Europa: ROV Encounters in Inner and Outer Space NAVIGATOR CLASS COMPETITION MANUAL For general competition information, including a description of the different competition classes, eligibility, and demonstration requirements, visit Team Info. OVERVIEW THINK OF YOURSELVES AS ENTREPRENEURS PART 1: PRODUCT...»

«EBA BOS 08-09 DECEMBER 2015 – FINAL MINUTES EBA BS 2016 001rev1 EBA Staff 08-09 December 2015 Location: London EBA Board of Supervisors – Final Minutes Agenda item 1.: Welcome, Approval of Agenda and Minutes 1. The Chairperson opened the meeting. He informed of changes to the Board of Supervisors (BoS) membership of the Latvian Financial and Capital Market Commission (Ms Liga Kleinberga would become the new high-level alternate member), the Supervisory Board of the European Central Bank (Mr...»

«»Those Who Strive to Rip the Motherland Apart Must Perish«— Reactions to 2008 Tibet Protests Katarína Čavojská The Internet has become an important tool for communication, not only for spreading information that does not appear in conventional media, but also for connecting like-minded people and organizing their actions. Even in the People’s Republic of China (PRC), where the Internet is monitored and censored, it serves as a platform for self-expression and bottom-up activism. The...»

«Philadelphia Freedom Valley YMCA Summer Day Camp Family Handbook PHILADELPHIA FREEDOM VALLEY YMCA SUMMER DAY CAMP Welcome to Summer Day Camp at the Philadelphia Freedom Valley YMCA! Our goal this Summer Day Camp season is to nurture the potential of every child and teen in order to help them grow and develop into the best person they can be. At our Summer Day Camps, children will experience new activities, develop communication skills and make new friends in a safe, secure environment....»

«1 TDC times and checks for waveform corruption The waveform contains up to 11 samples that have been overwritten with TDC times; each of these samples is marked by the 7th bit being set. These TDC hits are stripped out, converted from gray code to normal binary, and corrected for the electronics calibration t0. They are packed into the output container as a list of up to 11 times; the first hit in the list is always that matching the leading edge of the pulse; the remaining hits are listed in...»

«Al Qaeda in the Arabian Peninsula Introduction Al Qaeda in the Arabian Peninsula (AQAP), described by the U.S. government as the most active and dangerous branch of Al Qaeda, is the terrorist organization's wing in Yemen and Saudi Arabia. The growth of AQAP has led American officials to indicate that Yemen could become Al Qaeda's next operational and training hub for the group's militants from around the world. Formed in early 2009, AQAP has attempted to carry out multiple attacks against the...»

«LESSON 14 | Single-mindedness Bible Basis: 2 Chronicles 20:1 – 30; Matthew 14:22 – 33 Key Verse: Matthew 6:33: “Put God’s kingdom first. Do what he wants you to do. Then all those things will also be given to you.” Key Question: How do I keep my focus on Jesus? Key Idea: I focus on God and his priorities for my life. Resource: Believe Storybook Bible, Chapter 14, “SingleMindedness” or story script (below) Master Supplies List ❑ Believe Storybook Bible (optional) ❑ PowerPoint...»

«Social Research Update 37: Citizens Juries 11/26/2005 10:22 AM Issue 37 Summer 2002 Social Research Update is published quarterly by the Department of Sociology, University of Surrey, Guildford GU7 7XH, England. Subscriptions for the hardcopy version are free to researchers with addresses in the UK. Apply to SRU subscriptions at the address above, or email sru@soc.surrey.ac.uk. A PDF version of this article is available here. Citizens Juries: a radical alternative for social research Tom...»

«STREETSCAPE FEATURES RELATED TO PEDESTRIAN ACTIVITY Reid Ewing (corresponding author) College of Architecture + Planning, 220 AAC University of Utah 375 S 1530 E Salt Lake City, Utah 84103 P: 801-585-3745 F: 801-581-8217 ewing@arch.utah.edu Amir Hajrasouliha College of Architecture + Planning, 220 AAC University of Utah 375 S 1530 E Salt Lake City, Utah 84103 P: 801-809-3569 F: 801-581-8217 a.hajrasouliha@utah.edu Kathy Neckerman 420 W 118th Street mail code 3355 New York, NY 10027 USA Phone P:...»

«TIPS TO BI O-BOTA NY TEA CHER S If the students concentrate more on the units1, 2 & 5 they can score • 69 /75 marks. As most of the 5 and 10 marks questions of the above 3 units are already • existed in practical syllabus.It is very easy to prepare the above 3 units for theory exam to score maximum marks. Remaining 6 marks out of 69/75 can be easily achieved by studying the • frequently asked one mark questions of the chapters 3,4 & 6. As8 to 13 marksweightage may be given to...»

«Girls Mission Camp Name Cabin CAMPER INFORMATION (Sponsors Do Not Have to Fill Out This Form) Please complete this information sheet and bring it with you to registration. Camper and parent/guardian signature is necessary. Camper’s Name _ Home Address City State Zip _ Date of Birth _ Age School Grade Completed Mother’s Name_ Father’s Name _ Church Camper Attends Church Address _ City State Zip _ Has camper made a profession of faith? Yes _ No Is camper a church member? Yes _ No...»

«O&SB2010 “Open and Sustainable Building” – Chica, Elguezabal, Meno & Amundarain (Eds.) © 2010, Labein -TECNALIA. ISBN 978-84-88734-06-8 ACHIEVING OPEN BUILDING IN HIGH-RISE, HIGH DENSITY BUILT ENVIRONMENT – FACTS, OBSTACLES AND WAY OUTS Lau, Wai Kin & Ho, Daniel Chi Wing Department of Real Estate and Construction The University of Hong Kong ABSTRACT Aging of building stock is emerging. Open Building as a sustainable approach to deal with the aging building stock is seldom applied in...»

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