FREE ELECTRONIC LIBRARY - Abstracts, online materials

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

3.4.2 Opportunistic Any-Path Forwarding (OAPF)

–  –  –

Cs,d ← Cs,d ordered by cost the best candidate is the one that reduces the most the expected number of transmissions from s to the destination (line 14). Node s adds the best candidate to its actual CS (Cs,d ) and removes it from its initial set. Note that to find the best candidate in each iteration, candidates should be ordered according to their EAX. It tries again to find the best node from its new initial CS. This process is repeated until there is not any other suitable node to be included in the candidates set of s, or the number of candidates in the Cs,d reaches the maximum number of candidates (ncand). Finally, the CS is ordered by EAX of each candidate.

Now assume that node S in figure 3.7 wants to find its CS using OAPF. First, it creates ˆ its initial CS CS,D. Since the ETX of all its neighbors (A, B and D) to the destination D is ˆ less than ETX(S,D) (see table 3.2) then, the initial CS of S is CS,D = {A, B, D}. Note that, all nodes in the initial CS must select their CSs before S. In table 3.3 we summarize the CS and related expected number of transmissions for node A and B.

Table 3.4 shows the process of selecting candidates for the source S using OAPF.

In the first iteration source selects B as its candidate. Because B is the one that reduces the expected number of transmissions from S to D the most. Then, node B is removed from initial CS. The CS of S in the first iteration would be CS,D = {B}. In the section iteration of while-loop in algorithm 2 (line 12-24), source looks for the second candidate from the remaining potential Table 3.3: Candidates set of A and B in figure 3.7 using OAPF

–  –  –

ˆ candidates in CS,D = {A, D}. As we can see in table 3.4, the second candidates that reduces the expected number of transmissions from S to D the most is D. Therefore the final CS for source using OAPF is CS,D = {D, B} with EAX equal to 3.46.

3.4.3 Least-Cost Opportunistic Routing (LCOR) The goal of this algorithm is to find the optimal CSs. Recall that the optimal CSs are the sets that minimize the expected number of transmissions from the source to the destination.

LCOR [15] uses EAX as the metric to select candidates as shown in Algorithm 3. It works similar to the classical distributed Bellman-Ford algorithm.

The algorithm proceeds iteratively and at each iteration an exhaustive search over all possible CSs is carried out. It starts by initializing the cost (EAX) of each node v to reach the destination d (lines 1–4). Since in the initializing phase the CSs for all nodes are empty, the cost to reach the destination for all nodes is equal to ∞ (costcurr (v) ← ∞). Note that the cost for the destination d is always equal to 0 (costcurr (d) ← 0).

To find the optimal CSs in each iteration, and for every node v except the destination, the algorithm runs an exhaustive search over all possible subsets of N (v) with cardinality not exceeding ncand (line 9). The algorithm terminates when the cost to reach the destination does not change for all nodes in two consecutive iterations (lines 12–17).

In each iteration the algorithm checks for all the nodes but the destination, all subsets of their neighbors with cardinality ≤ ncand. Therefore, for dense networks the computational cost of the algorithm increases extremely fast due to the combinatorial explosion of the exhaustive search of line 9. In section 3.9.8, we will carry out an experimental evaluation of the computational time.

Applying LCOR on the topology in figure 3.7 yields as a result CS,D = {D, A} with the expected number of transmissions equal to 3.36.

–  –  –

Algorithm 3: Candidate.selection.LCOR(s, d, ncand).

forall the v in the network \{d} do costcurr (v) ← ∞; costprev (v) ← ∞

–  –  –

until flag == TRUE Cs,d ← Cs,d ordered by costcurr 3.4.4 Minimum Transmission Selection (MTS) MTS [29, 45] is another algorithm which selects the optimal CSs for any node to a given destination d that minimizes the total expected number of transmissions. Like LCOR, this algorithm proceeds iteratively and uses EAX as the metric for selecting the candidates sets.

The general idea of MTS consists of moving from the nodes closest to the destination d (in terms of the EAX) backwards to the source. Note that, the closest node to the destination has the least EAX. MTS uses the following principle: if u and v are neighbors and EAX(Cu,d, u, d) EAX(Cv,d, v, d), then adding u and its candidates to the CS of node v will reduce the expected number of transmissions from v to d, i.e. EAX(Cv,d ∪ {u} ∪ Cu,d, v, d) EAX(Cv,d, v, d).

Given a general wireless topology, for a given destination d initially let S be the set of all nodes except d. The MTS algorithm for computing the optimal CS from any source node v ∈ S to d is described in pseudo-code in algorithm 4. The algorithm starts by initializing the cost (EAX) of each node v to reach the destination d (lines 2–10 in Algorithm 4). If d is one of the neighbors of v, then v adds the destination to its CS and the cost to reach the destination (cost(v)) is set to qvd, where qvd is the delivery probability of link between the two nodes v and d (note that EAX(Cv,d, v, d) = qvd when Cv,d = {d}).

At each subsequent iteration while S is not empty the algorithm looks for the node minnode with minimum cost in terms of the expected number of transmissions to the destination (line 12). The neighbors of minnode, N (minnode), add minnode and its candidates to their CS and minnode is removed from S. This process is done by means of the function merge, which combines both CSs and order them in increasing order of their cost (EAX).

Algorithm 4: Candidate.selection.MTS(S, d,ncand).

Data: S is the set of all nodes except d.

cost(d) ← 0 forall the v ∈ S do if v ∈ N (d) then cost(v) ← qvd

–  –  –

Note that proceeding this way, MTS finishes in N − 1 iterations, where N is the number of nodes in the network.

In the description of MTS given above, the optimal CSs for all the nodes in the network are computed assuming there is not any limitation in the number of candidates, as proposed in the original version of this algorithm.

In order to limit the maximum number of candidates, maintaining the optimality of the algorithm, we have added the lines 19–22. Here the nodes are visited in increasing order of their cost, and an exhaustive search is done over all subsets of the CSs with cardinality ≤ ncand. Since MTS first find the optimal CSs in the case of infinite candidates (i.e. all possible nodes can be selected as candidates), and then we look for the best subset of candidates sets with at most ncand elements, the final CSs will be the optimal CSs.

Like the previous algorithms, we apply MTS in the example of figure 3.7 to find the CSs. According to MTS algorithm S = {S, A, B}. The cost of nodes S, A and B to the destination D is 1/0.15, 1/0.4 and 1/0.31, respectively. The result of each iteration of the MTS algorithm is shown in table 3.5, where the first item in each cell is the current best CS for the corresponding node, and the second item is the current smallest expected number transmissions using that set. In the first iteration since the EAX of A is the minimum (EAX({D}, A, D) = 2.5), it removes from S. Then, MTS adds A and its candidates (CA,D = {D}) to the CSs of all neighbors of A, i.e, nodes S and B (see iteration 1 in table 3.5).

Note that in each iteration the EAX of each node is updated according to the new CS. In Table 3.5: Candidates Set selection for the figure 3.7 using MTS

–  –  –

the second iteration the node with the minimum EAX is B (EAX({D, A}, B, D) = 2.79);

it is removed from S and its candidates CB,D = {D, A}, and B are added to the CSs of all neighbors of B which are still in S, i.e, node S. Now, each node has a set of candidates to reach D. Note that, until this step there is not any limitation on the number of candidates.

Doing an excursive search with constraint ncand = 2 over the sets which are found by the original version of MTS results in the optimum CS with length at most equal to 2.

We summarize the CSs and EAX of each node in figure 3.7 using different algorithms under study in table 3.6. The first item in each cell is the CS for the corresponding node, and the second item is the expected number of transmissions (EAX) of the corresponding node using the said set. As we can see in table 3.6 the algorithms that use EAX to select CSs have better expected number of transmissions than ExOR which uses ETX for selection of candidates.

3.5 Network Coding Opportunistic Routing

MORE [11] is an OR protocol that can be used in both unicast and multicast scenarios. It deploys the advantages of network coding to improve performance of OR in wireless multicast networks. Duplicate transmissions are avoided by randomly mixing packets before forwarding.

The sender creates a linear combinations of packets and broadcasts the resulting packet after adding a MORE header containing the CS. Each receiving node discards the packet if it is not linearly independent from the other packets received before, or if its ID does not appear in the candidates list. Otherwise, it linearly combines the received coded packets and rebroadcasts the new packet.

COPE [20, 21] is a practical network coding mechanism for supporting efficient unicast communication in a wireless mesh network. It employs opportunistic listening to enable each node to learn local state information and encoded packet broadcasting to improve the network throughput. It exploits the shared nature of the wireless medium which broadcasts each packet in a small neighborhood around its path. Each node stores the overheard packets for a short time [20]. It also tells its neighbors which packets it has heard by annotating the packets it sends. When a node transmits a packet, it uses its knowledge of what its neighbors have heard to perform opportunistic coding; the node XORs multiple packets and transmits them as a single packet if each intended next-hop has enough information to decode the encoded packet. Motivated by COPE, several other coding-aware routing mechanisms have been proposed [41, 27], which are aimed at improving the network throughput by combining routing with inter-flow network coding. However, neither COPE nor its variants consider the opportunistic characteristic of a wireless channel in packet delivery and the dynamic availability of network coding opportunities at a network node, which can be caused by traffic and network dynamics. This largely limits their capabilities for improving network throughput.

CORE [43, 42] is a coding-aware OR mechanism that combines opportunistic forwarding and localized inter-flow network coding for improving the throughput performance of a MWN network. Through opportunistic forwarding, CORE allows the next-hop node with the most coding gain to continue the packet forwarding. Through localized network coding, CORE attempts to maximize the number of packets that can be carried in a single transmission. When a node has a packet to send, it simply broadcasts the packet, possibly encoded with other packet(s), which may be received by some of the candidates in its CS. The candidates receiving the packet collaborate to select the best candidate among them in a localized manner, which is the one with the most coding opportunities. This forwarding process is repeated until the packet reaches its intended destination. In CORE, geo-distance metric and timer-based coordination have been used to select and coordinate the candidates, respectively.

3.6 Geographic Opportunistic Routing

Geographic Random Forwarding (GeRaF) [50] is a forwarding protocol which selects set of candidates and prioritizes them using geographical location information. Only those neighboring nodes closer to the destination than the sender can be candidates. The priority of selected candidates is based on their geo-distances to the destination. The CS and prioritization can easily be implemented via an RTS-CTS dialog at the MAC layer, which also ensures that a single forwarder can be chosen.

GOR [47] is used in geographic routing scenarios and adopts timer-based coordination with local candidates order. Authors showed that giving the nodes closer to the destination higher priority is not always the optimal way to achieve the best throughput. They proposed a local metric named expected one-hop throughput (EOT) to characterize the local behavior of GOR in terms of bit-meter advancement per second. Based on EOT, which considers the coordination overhead, they proposed a candidate selection scheme.

S.Yang et. al. [44] proposed a protocol called Position Based Opportunistic Routing, POR. In POR, when a source wants to send data packet to the destination, it finds its CS according to the distance between its neighbors and the destination. The neighbor which the nearest to the destination will have the highest priority. They fixed the maximum number of candidates in each node to 5. When a candidate receives a packet, it checks its position in the CS and waits for some time slots to forward the packet. If it hears the same packet being sent by the other nodes, it will simply discard the packet.

3.7 Multicast Opportunistic Routing Multicast is an important communications paradigm in wireless networks. The availability of multiple destinations can make the selection of CSs and the coordination between candidates complicated. There are few works that have tried made to adapt OR for multicast scenarios.

In [22] the source first creates the shortest path tree to reach all destinations based on the ETX of each link. Then the nodes not only receive packets from their father in the tree, but also can overhear packets from its sibling nodes. It uses random linear network coding to improve multicast efficiency and simplify node coordination.

The authors in [38] used a Steiner tree based on ETX and data packets were forwarded through the links using OR. Their protocol constrains the nodes involved in routing a packet to be near the default multicast tree. The average EAX of each candidate to reach a sub-group of destinations is used as the cost of reaching to multiple destinations.

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

Similar works:

«Fileteller: Paying and Getting Paid for File Storage John Ioannidis½, Sotiris Ioannidis¾, Angelos D. Keromytis¿, and Vassilis Prevelakis ½ AT&T Labs – Research, ji@research.att.com ¾ CIS Department, University of Pennsylvania, sotiris@dsl.cis.upenn.edu ¿ CS Department, Columbia University, angelos@cs.columbia.edu MCS Department, Drexel University, vp@drexel.edu Abstract. FILETELLER is a credential-based network file storage system with provisions for paying for file storage and...»

«The Global Review of Ethnopolitics Vol. 3, no. 1, September 2003, 92-105 Special Issue: Northern Ireland From Outrage to Apathy? The Disputes over Parades, 1995-2003 Neil Jarman, Institute for Conflict Research, Belfast On 7 July 1996, when the police stopped members of the Orange Order from Portadown from marching down the Garvaghy Road on their return route from Drumcree Church, the decision led to widespread protests within the wider Protestant community. Thousands of people gathered at...»

«MATERNAL STRESS AND MOTHERING BEHAVIORS IN STABLE AND UNSTABLE FAMILIES Center for Research on Child Wellbeing Working Paper # 03-08-FF REVISED May 2004 July 2003 Cynthia Osborne Maternal Stress and Mothering Behaviors in Stable and Unstable Families Cynthia Osborne Center for Research on Child Wellbeing 286 Wallace Hall Office of Population Research Princeton University Princeton, NJ 08544 cosborne@princeton.edu 609-258-2772 April 2004 Abstract Prior research linking family structure with...»

«Journal of Intercollegiate Sports, 2008, 1, 202-226 © 2008 Human Kinetics, Inc. In-Season vs. Out-of-Season Academic Performance of College Student-Athletes Brianna M. Scott National Collegiate Athletic Association Thomas S. Paskus National Collegiate Athletic Association Michael Miranda State University of New York—Plattsburgh Todd A. Petr National Collegiate Athletic Association John J. McArdle University of Southern California There is a commonly held belief within the intercollegiate...»

«Fifth ANNUAL Black & Gold Club KickOff Event Program OHIO DOMINICAN UNIVERSITY BLACK & GOLD CLUB August 6, 2014 | 6 p.m. | Alumni Hall | Ohio Dominican University title Sponsor MVP Sponsors EDUCATION Athletic Director Sponsors Jonathan Michael ’77 COACH SPONSORS Dr. Adolph V., L.H.D. ’11 & Karen & Tom Mueller Anne T. Lombardi, LPCC, BCPC ’03 CAPTAIN SPONSORS Embassy Suites Columbus Mandy & Torrance Powell Albers-Dancer Insurance Mike & Margie Corbett Agency, Inc. Airport John F. Kelley...»

«River, Coastal and Estuarine Morphodynamics: RCEM2011 © 2011 Reconstruction of the sediment transport conditions in the Urumqi alluvial fan (northeastern Tian Shan, China) GUERIT Laure Laboratoire de Dynamique des Fluides Géologiques Institut de Physique du Globe de Paris, Sorbonne Paris Cité, Université Paris Diderot, UMR CNRS 7154 1 rue Jussieu, 75005 Paris, France BARRIER Laurie Laboratoire de Tectonique et Mécanique de la Lithosphère Institut de Physique du Globe de Paris, Sorbonne...»

«Department for Formation, Office for Education Telephone: 0161 817 2204 Fax: 0161 372 9991 Email: education@dioceseofsalford.org.uk INSPECTION REPORT St Antony’s Catholic College Urmston Manchester M41 9PD 19th June 2015 Inspection date Reporting Inspector Sister Judith Russi Mr Kevin Hogan Mr Michael Wright Inspection carried out in accordance with Section 48 of the Education Act 2005 Type of School Catholic High School URN 106372 Age range of pupils 11-16 years Number on roll 548...»

«NAVAL POSTGRADUATE SCHOOL MONTEREY, CALIFORNIA THESIS THE STRING OF PEARLS: CHINESE MARITIME PRESENCE IN THE INDIAN OCEAN AND ITS EFFECT ON INDIAN NAVAL DOCTRINE by Richard D. Marshall Jr. December, 2012 Thesis Advisor: S. Paul Kapur Thesis Co-Advisor: Michael Glosny Approved for public release; distribution is unlimited THIS PAGE INTENTIONALLY LEFT BLANK REPORT DOCUMENTATION PAGE Form Approved OMB No. 0704–0188 Public reporting burden for this collection of information is estimated to...»

«RED HERRING PROSPECTUS Dated September 14, 2010 Please read section 60B of the Companies Act, 1956 100% Book Built Issue Ramky Infrastructure Limited Our Company was incorporated on April 13, 1994 under the provisions of the Companies Act, 1956. For details of changes in our name and registered office, see “History and Corporate Structure” on page 108. Registered and Corporate Office: 6-3-1089/G/10 & 11, 1st Floor, Gulmohar Avenue, Raj Bhavan Road, Somajiguda, Hyderabad 500 082, India....»

«DISCUSSION PAPER EXPLORING CRIMINAL JUSTICE AND THE ABORIGINAL HEALING PARADIGM Prepared By: Rupert Ross, Assistant Crown Attorney, Ontario Ministry of the Attorney General, 216 Water Street, Kenora, Ontario, Canada P9N 1S4 Tel: (807) 468-2840 Fax: (807) 468-2840 e-mail: rupert.ross@jus.gov.on.ca All of the opinions expressed herein are personal to the author, and do not in any fashion reflect the perspectives or policies of the Government of Ontario. A. INTRODUCTION I remember a Cree...»

«A characterization of the mixed discriminant D. Florentin, V. D. Milman∗ R. Schneider, 1 Introduction The striking analogy between mixed volumes of convex bodies and mixed discriminants of positive semidefinite matrices has repeatedly been observed. It was A. D. Aleksandrov [1] who, in his second proof of the Aleksandrov–Fenchel inequalities for the mixed volumes, first introduced the mixed discriminants of positive semidefinite quadratic forms and established some of their properties,...»

«Approved Pamphlet ALTRISET 30862 2014-02-05 Page 1 of 16 GROUP 28 INSECTICIDE ALTRISET™ Termiticide INSECTICIDE SUSPENSION COMMERCIAL This product is to be used only by licensed pest control operators authorized with permits by government for control of subterranean termite populations infesting buildings. For use only in areas where there is a risk of infestation from subterranean termites. Not for sale to the general public. FOR USE ONLY BY LICENSED PEST CONTROL OPERATORS GUARANTEE:...»

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