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 2 ] --

We now compute the expected number of transmissions from node 1 to the destination using OR (E1 ). We can write: E1 = 1 + 3 pi Ei, where pi is the probability of node i beOR OR i=1 ing the next forwarder (or the destination), and Ei is the expected number of transmissions OR from node i to the destination (note that E3 = 0 and E1 = E1 ). Grouping terms we have E1 = (1 + p2 × E2 )/(p2 + p3 ) = (1 + (1 − q13 ) q12 × 1/q23 )/((1 − q13 ) q12 + q13 ). Substituting we OR get E1 ≈ 2.15. Although ETX is much simple to compute than EAX, it does not accurately compute the expected number of transmissions under OR.

3.3 Candidate Coordination Methods

One of the important issues of OR is the candidate coordination, i.e, the mechanism used by the candidates to discover which is the highest priority candidate that has received, and thus, must forward the packet. Coordination requires signaling between the nodes, and imperfect coordination may cause duplicate transmission of packets. A good coordination approach should select the best candidate without duplicate transmissions while using the smallest time/or control overhead.

Existing coordination approaches are divided into three main categories based on the mechanism used: acknowledgment-based (ACK-based), timer-based, network coding (NC) and RTS-CTS Coordination. In the following subsections we briefly describe these approaches.

3.3.1 Acknowledgment-Based Coordination

It is one of the first methods that was proposed for candidate coordination. Upon receiving a data packet, candidates send back a short acknowledgment (ACK) in decreasing order of candidate priority.

This method was first proposed in [24] as the coordination mechanism for the Selection Diversity Forwarding (SDF) protocol. In SDF coordination is achieved by means of a fourway-handshaking: the candidates receiving the data packet send back an acknowledgment to the sender. Based on the acknowledgments, the sender sends a forwarding order to the best candidate, which is also acknowledged.

A similar approach is used in ExOR [6], which uses a modified version of the 802.11 MAC which reserves multiple slots of time for the receiving nodes to return acknowledgments.

Instead of only indicating that the packet was successfully received, each ACK contains the ID of the highest priority successful recipient known to the ACKs sender. All the candidates listen to all ACK slots before deciding whether to forward, in case a low-priority candidates ACK reports a high-priority candidate ID and whose ACK was not correctly received. Including the ID of the sender of the highest-priority ACK heard so far helps suppress duplicate forwarding.

This strategy requires that candidates be neighbors of each other such that the transmission of an ACK can be overheard by all of them.

As an example of the ACK-based coordination, consider a network with source S and destination D. Assume that the CS of S is {A, B, C} (A has the highest priority and C has the lowest). Suppose that all candidates receive a transmission from source. Figure 3.4 shows ACK-based coordination method for this example. All candidates transmit acknowledgments in decreasing order of candidate priority: the first acknowledgment slot belongs to node A, the second slot belongs to node B and the third slot is dedicated to C. In figure 3.4 we suppose that the acknowledgment from A does not receive by B, but node C does hear the A’s ACK (see figure 3.4). Suppose further that node B hears node Cs ACK. If ACKs did not contain IDs, node B would forward the packet, since to its knowledge it is the highest priority recipient. The fact that node C’s ACK contains node A’s ID indirectly notifies B that node A did receive the packet. Once node A has successfully determined itself as the responsible node, it forwards the packet.

–  –  –

Figure 3.4: Acknowledgment-based coordination using a modified 802.

11 MAC.

3.3.2 Timer-Based Coordination In this method, all candidate which are included in the packet are ordered based on a metric.

After a data packet is broadcasted, candidate will respond in order, i.e, ith candidate will respond at the ith time slot. A candidate forwards data packet at its turn only when it does not hear other candidates that forward the packet. Thus, when a candidate forwards a data packet, it means that all other higher priority candidates failed to receive the data packet. In another word, forwarding a data packet by a candidate will prevent the lower priority ones to forward it. In the example of figure 3.1, assume that {B, A} is the CS of source S to reach destination D (B is the better candidate and given the higher priority). After receiving the packet sent by S, candidate B forwards the packet in the first time slot, while A schedules to transmit in the second time slot. If A is in the range of B, overhearing the data packet sent from B by A means that a higher priority candidate received the packet and has forwarded it, thus A simply discard the packet.

This approach is simple and easy to implement and no control packet is required. The overhead of the timer-based coordination is candidate waiting time. The main drawback of this solution is duplicate transmission because of not all candidates are guaranteed to overhear the forwarding from the selected candidate [18].

3.3.3 Network Coding Coordination

Another approaches to prevent duplicate transmission is combining OR with network coding (NC) [3] which provides an elegant method for candidate coordination [11, 7, 43]. The basic principle behind combining NC with OR is that forwarders can combine the packets to be transmitted so as to deliver multiple data packets through a single transmission. When transmitting packets from source to a destination, a flow is divided into batches which contain several native packets (original packets without coding). The source broadcasts random linear combinations of native packets, and candidates forward the linear combinations of received coded packets. When the destination has enough linearly independent coded packet, then it can decode them to reconstruct the set of initial packets.

In order to better clarify the advantage of combining NC with OR, consider the example in figure 3.5. Assume that source S transmits two native packets a and b using CS {C1, C2 }.

It generates two coded packet which are linear combination of a and b and broadcasts them.

Assume that C2 received both coded packet but C1 received only one of them. Two candidates generate coded packets and transmit to the destination D without any coordination. When D received transmitted packets from C1 and C2, it can decode and restore the original packets.

However, using network coding with OR may lead to a high number of potential forwarders sending coded packets, and thus, resulting in redundant transmissions. There exists a trade-off between transmitting a sufficient number of coded packets to guarantee that the destination has enough coded packets to reconstruct the native packets, and avoiding to inject in the network unnecessary packets [7].

a+b C1 p3 2a+2b

–  –  –

3.3.4 RTS-CTS Coordination Some other mechanisms like [19, 50] use explicit control packet(s) exchanged immediately before sending a data packet. In this approach the sender multicasts the RTS to the its CS (it is actually a broadcast control packet). The RTS contains all the candidates addresses which are ordered according to a metric. When an intended candidate receives the RTS packet, it responds by a CTS. These CTS transmissions are sent in decreasing order of candidate priority: the first candidate in priority transmits the CTS after a SIFS, the second one after 2×SIFS, and so on. When the sender receives a CTS, it transmits the DATA packet to the sender of this CTS (which would be the highest priority candidate that responded) after a SIFS interval. This ensures that other lower priority candidates hear the DATA before they send CTS and suppress any further CTS transmission. All such receivers then set their NAV until the end of ACK period.

Figure 3.6 shows an example of RTS-CTS coordination.

Assume that there are three candidates a, b and c to reach the destination (a the highest priority candidate and c the least one). After receiving RTS by candidates they send the CTS packet in order of their priorities.

Here we assume that the first CTS which belong to a was not received, but the second one was received. When the sender s receives the first CTS from b, it sends the data packet to it, therefore the highest priority candidate whose its CTS is received by the source will forward the data packet.

3.4 Candidate Selection Algorithms Another important component of OR is candidate selection, which is similar to building routing tables in traditional routing. Selection of good candidates can affect the performance of the network. According to the amount of information is needed to select and prioritize the candidates, candidate selection algorithms can be divided into two categories; Locationbased and Topology-based selection. In location-based selection [50], each node maintains a limited state information and independently determines its own CS along the path to the intended destination. Topology-based selections [6, 5] find the CSs according to the global topology information of the network. Therefore, a node requires to maintain global network state information, for example, the network topology, state information on each link, and flow-related information (e.g., path and data rate), what can run into a scalability problem.

In general, topology-based strategy outperforms location-based strategy, since the former can optimize the selection of a CSs with more network state information gathered. However, the location-based strategy might be easier to implement, requires less signaling and scales better than topology-based [31].

In this section, we describe 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. These algorithms are: Extremely Opportunistic Routing (ExOR) [6]; Opportunistic Any-Path Forwarding (OAPF) [49]; Least-Cost Opportunistic Routing (LCOR) [15]; and Minimum Transmission Selection (MTS) [29].

ExOR is one of the firsts and most referenced OR protocols, it is based on ETX and is simple to implement. OAPF has an intermediate complexity: it uses the EAX metric but it does not guarantee to yield the optimal sets of candidates (i.e. the CSs that minimize the expected number of transmissions). Finally, we have chosen LCOR and MTS which select the optimal sets of candidates.

Here we introduce some notations that we use throughout this section:

• ncand is the maximum number of candidates per node.

• ET X(v, d) is the uni-path ETX between the two nodes v and d.

• EAX(Cv,d, v, d) is the EAX between node v and d by using Cv,d as the CS of v to reach node d.

• N (v) is the set of all neighbors of node v.

• |S| is the cardinality of the set S.

–  –  –

Cs,d ← Cs,d ordered by cost 3.4.1 Extremely Opportunistic Routing (ExOR) Biswas and Morris proposed ExOR [6], one of the firsts and most referenced OR protocols.

The selection of candidates is based on the Expected Transmission Count (ETX) metric. The basic idea of ExOR is running the Shortest Path First (SPF) with weight = 1/qij, where qij is the delivery probability of the link between the two nodes i and j (i.e. the weights are the ETXs of the links).

The algorithm for selection of candidates in ExOR is shown in Algorithm 1. Every node s except the destination d runs this algorithm. The first node after s in the shortest path is selected as candidate (cand) if its ETX to the destination (ETX(cand, d)) is less than ETX(s, d). Then the link between s and cand is removed, and this process is repeated until no more paths to d are available, or the maximum number of candidates is reached (|Cs,d | = ncand). Finally, ETX(cand, d) (or 0 if the cand is the destination) is used to sort the CS.

Assume that node S in figure 3.7 want to find its CS using ExOR. According to ExOR’s algorithm (see algorithm 1), node S finds the shortest path first (SPF) to D which is S-A-D with ETX=3.99 (see table 3.2). Therefore, node A is the first candidate for node S. Then, edge S-A is removed from the topology and SPF is run again. The new shortest path from S to D is S-B-D with ETX=4.40 and B is selected as the second candidate. Finally, the ETX of each candidate to the destination d is used to sort the CS. The final candidates set of node S is CS,D = {A, B}. ExOR uses ETX to estimate the closeness to the destination but, this metric does not account for the fact that packets are delivered by the candidates under opportunistic forwarding.

Table 3.2: Expected number of transmissions of each node to D in figure 3.


–  –  –

There is a second version of ExOR [5] proposed in 2005. It is designed for batch forwarding.

The source node includes in each packet a CS prioritized by closeness to the destination. Each packet has a Bitmap, which marks those packets that have been received by the sending node or nodes with higher priorities. A candidate transmits a packet only if no forwarder with higher priority has explicitly acknowledged receipt of it, as indicated in Bitmap position for this packet. Therefore, the coordination is done using timer-based coordination (see section 3.3.2). The performance of this protocal was evaluated on Roofnet [2], an outdoor roof-top 802.11b network.

SOAR [35] has been proposed after ExOR. In order to leverage path diversity while avoiding duplicate transmissions, SOAR relaxes the actual route that data traverses to be along or near the default path but constrains the nodes involved in routing a packet to be near the default path. Moreover, this forwarding node selection also simplifies coordination since all the nodes involved are close to nodes on the default path and can hear each other with a reasonably high probability. It selects the shortest path between source and destination using ETX, and the nodes near to the shortest path can act as the CS. SOAR uses timer-based approach for candidate coordination.

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

Similar works:

«Appendices APPENDIX 1 Address by An Taoiseach, Mr. Bertie Ahern TD, to the Plenary Session of the World Summit on Sustainable Development in Johannesburg, South Africa on 3 September 2002. May I first thank the President and Government of South Africa for their outstanding work in hosting and chairing this major event. What we seek to achieve in Johannesburg is profoundly important to the world community.  What we...»

«MINUTES BOARD OF DIRECTORS MEETING January 9-10, 2015 International Headquarters Office St. Louis, Missouri The following Members of the 2014-15 Board of Directors were in attendance for the entire meeting: Ron Huxley Immediate Past President Thedford, Ontario Kenneth Garner President Fort Worth, Texas Dave Bruns President-Elect Topeka, Kansas Marlene Phillips Director Windsor, Ontario Rick Quinlan Director Bellevue, Nebraska Marc D. Katz Director Berkley, Michigan James A. Oliver Director...»

«Chapter 1 Motion in Vacuum 1.1 Crystal Manipulator with Six Degrees of Motional Freedom This design [1] is shown in two parts to separate the azimuthal motion (Fig. 1.1) device from the tilt motion device (Fig. 1.2). A central rod extends from a typical x, y, z-plus rotary motion manipulator. The azimuthal and tilt motion (pushing and pulling) devices are connected to the same central rod and are free to slide up and down on this rod. The central rod is slotted to keep the crystal mount linking...»

«TIDBIT CATCH OBJECTIVE To see which owner/dog team is the best tidbit catcher.RULES: 1. Tidbits can be brought by owners, or biscuits will be supplied.2. At judge’s instruction, owner will toss treat to dog (teams will go one at a time).3. After each successful catch, the owner will back-up one step (even with other tossers) CATCH 4. Dogs must stay behind the line. 5. Failure to catch a tidbit eliminates the team from the event. DISQUALIFICATION: DOGS: Not catching the treat. Crossing the...»

«Predatory Trading∗ Markus K. Brunnermeier and Lasse Heje Pedersen First version: June 15, 2002 This version: October 7, 2004 Abstract This paper studies predatory trading, trading that induces and/or exploits the need of other investors to reduce their positions. We show that if one trader needs to sell, others also sell and subsequently buy back the asset. This leads to price overshooting and a reduced liquidation value for the distressed trader. Hence, the market is illiquid when liquidity...»

«SOCIO-ECONOMIC METHODOLOGIES FOR NATURAL RESOURCES RESEARCH BEST PRACTICE GUIDELINES LOCAL PEOPLE’S KNOWLEDGE IN NATURAL RESOURCES RESEARCH Hilary Warburton and Adrienne Martin Natural Resources Institute The University of Greenwich Published by Natural Resources Institute © The University of Greenwich 1999 The Natural Resources Institute (NRI) is a scientific institute within the University of Greenwich, and is an internationally recognized centre of expertise in research and consultancy in...»

«AU/AWC/RWP152/97-04 AIR WAR COLLEGE AIR UNIVERSITY PEARL HARBOR: FAILURE OF INTELLIGENCE? by Robert F. Piacine, Lt Col, USAF A Research Report Submitted to the Faculty In Partial Fulfillment of the Curriculum Requirements Advisor: Dr. Malcolm D. Muir, Jr. Maxwell Air Force Base, Alabama April 1997 Report Documentation Page Report Date Report Type Dates Covered (from. to) 01APR1997 N/A Title and Subtitle Contract Number Pearl Harbor: Failure of Intelligence? DE-AC22-96EW96405 Grant Number...»


«TRUSTEES JULY Governance WWF-UK TRUSTEES BIOGRAPHIES DAVID BRYER MARK CHAMBERS RITA CLIFTON COLIN DAY IAN DIAMOND DAVID GREGSON DAVID MACDONALD DAVID PHILLIPS ALBERTO PIEDRA ED SMITH (CHAIR) VALENTIN VON MASSOW KATHERINE WILLIS WWF-UK Trustees Biographies DAVID BRYER David Bryer graduated from Oxford University with an MA in Middle Eastern Studies and a DPhil on the Druze. He also has a PGCE from Manchester University. After a period of teaching and research in Oxford and Lebanon, he joined...»

«2nd Quarter 2001 Greetings Our institutional life this Quarter commenced with the completion and distribution of the triennial WPA General Survey. It attained a 90% response rate across all WPA Components, evidencing our growing institutional strength. It revealed that our Association has made significant progress in its ample range of activities as compared to three years ago. The General Survey results will inform the preparation of an updated Executive Committee Action Plan as well as of the...»

«Wo r k i n g Pa P e r S e r i e S n o 16 0 4 / n ov e m b e r 2013 Setting CounterCyCliCal CaPital bufferS baSed on early Warning modelS Would it Work? Markus Behn, Carsten Detken, Tuomas A. Peltonen and Willem Schudel maCroPrudential reSearCh netWork In 2013 all ECB publications feature a motif taken from the €5 banknote. note: This Working Paper should not be reported as representing the views of the European Central Bank (ECB). The views expressed are those of the authors and do not...»

«Balance and Fairness In Broadcasting News (1985-1994) by Judy McGregor Margie Comrie Massey University This research w a s funded b y the Broadcasting Standards Authority a n d N e w Z e a l a n d o n Air (Irirangi Te M o t u ). A p r i l 1995 ACKNOWLEDGEMENTS T h i s r e s e a r c h w o u l d n o t h a v e b e e n p o s s i b l e w i t h o u t t h e s u p p o r t of t h e D e p a r t m e n t of H u m a n R e s o u r c e M a n a g e m e n t, F a c u l t y of B u s i n e s s S t u d i e s at M...»

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