BU CS 580S - Modeling and Implications on Multi-Hop Routing

Unformatted text preview:

Temporal Properties of Low Power Wireless Links:Modeling and Implications on Multi-Hop RoutingAlberto [email protected] L. [email protected] [email protected] [email protected] for Embedded Networked Sensing (CENS)Department of Computer ScienceUniversity of California, Los Angeles (UCLA)3563 Boelter Hall, Los Angeles, CA 90095ABSTRACTRecently, several studies have analyzed the statistical prop-erties of low power wireless links in real environments, clearlydemonstrating the differences between experimentally ob-served communication properties and widely used simula-tion models. However, most of these studies have not per-formed in depth analysis of the temporal properties of wire-less links. These properties have high impact on the perfor-mance of routing algorithms.Our first goal is to study the statistical temporal prop-erties of links in low power wireless communications. Westudy short term temporal issues, like lagged autocorrela-tion of individual links, lagged correlation of reverse links,and consecutive same path links. We also study long termtemporal aspects, gaining insight on the length of time thechannel needs to be measured and how often we should up-date our models.Our second objective is to explore how statistical temporalproperties impact routing protocols. We studied one-to-onerouting schemes and developed new routing algorithms thatconsider autocorrelation, and reverse link and consecutivesame path link lagged correlations. We have developed twonew routing algorithms for the cost link model: (i) a gen-eralized Dijkstra algorithm with centralized execution, and(ii)a localized distributed probabilistic algorithm.Categories and Subject DescriptorsC.2.1 [Computer-Communication Networks]: NetworkArchitecture and Design—wireless communication, networkcommunications ; C.2.2 [Computer-Communication Net-works]: Network Protocols—routing protocols, protocol ver-Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.MobiHoc’05, May 25–27, 2005, Urbana-Champaign, Illinois, USA.Copyright 2005 ACM 1-59593-004-3/05/0005 ...$5.00.ification;C.4[Computer Systems Organization]: Per-formance of Systems—measurement techniques, modeling tech-niques, reliability, availability, and serviceabilityGeneral TermsAlgorithms, Design, Measurement, Performance, Reliability,ExperimentationKeywordsWireless communication, sensor networks, experimental test-beds, nonparametric statistical modeling, time series analy-sis, routing algorithms, performance evaluation1. INTRODUCTIONRecent studies indicate profound differences between ex-perimentally observed properties of low power communica-tion links and widely used simulation models [9, 23, 20, 2, 24,25]. Nevertheless, most of these studies have not performedin depth analysis of the temporal properties of wireless links.These properties have a strong impact on the performance ofmany protocols and localized algorithms used in low powernetworks, in particular, routing algorithms.Our starting point is a study of statistical temporal prop-erties of links in low power wireless communication sys-tems. We emphasize on time dependent properties, whichhave strong ramifications on routing protocols. The resultsof the study are used to analyze how statistical temporalproperties impact routing protocols. We studied one-to-one routing protocols and provided several suggestions forprotocol designers using the insight gained from our anal-ysis. We have also developed new routing algorithms thatconsider autocorrelation, reverse link and consecutive samepath link lagged correlations. The first algorithm is a gen-eralized Dijkstra algorithm with centralized execution. Thesecond algorithm is a localized probabilistic algorithm withdistributed execution.In our study, we do not consider the effect of packet lossesintroduced by mobility of the nodes, as it could be the casein ad-hoc networks and sensor networks with mobile nodes.4140 1000 3000 50000 20406080100Link 23 −− 43Time (minutes)Reception Rate (0−100%)(a) RR: 48.02% RNP: 1189.60 1000 3000 50000 20406080100Link 23 −− 24Time (minutes)Reception Rate (0−100%)(b) RR: 95.36% RNP: 1.0491Figure 2: Aggregate of reception rate by minute for a bad and good quality links.0 2 4 6 8 10 120123456789Distance (m)Distance (m)34 35 333736424443 38503951405246314947 41 48 45 55 32 54 53 15 30 29 8 25 24 23 27 28 26 7 22 18 19 21 20 17 9 112 1 4 16 8 3 5 10 13 14 12 Figure 1: Layout of the nodes.However, our results are useful when mobile nodes estab-lish a stationary position. In addition, we do not considerpacket losses introduced by multi-user interference (concur-rent traffic, contention-based MAC). Nevertheless, our re-sults are useful for three reasons. First, the amount oftraffic expected in most application in sensor networks issmall, which means either small contention, or in case ofhighly synchronized events, nodes could be programmed toprevent simultaneous transmissions. Second, our findingsapply directly when using contention free MAC protocols,like pure TDMA or pseudo-TDMA schemes [22]. Finally,they provide a tight upper bound as to what is achievablewhen using contention-based MAC schemes. The analysisof losses due to mobility and multi-user interference is partof future work.2. RELATED WORKThere is a large body of literature on temporal modelsof radio propagation that have influenced this work. Theemphasis has been on the variability of signal strength inproximity to a particular location [15]. Small scale fadingmodels based on Rayleigh and Rice distributions are usedfor modeling localized time durations (a few microseconds)and space locations (usually one meter) changes [15]. Oneof the first models to study the effect of flat fading losses incommunication channels was a 2-state (first order) Markovmodel due to Gilbert and Elliot [10]. This model predictedthe effect of flat fading and signal degradation. Wang etal. [19] and Swarts et al. [17] showed that wireless lossychannel could be represented by an discrete time markovchains of different order (number of states).Our work is


View Full Document

BU CS 580S - Modeling and Implications on Multi-Hop Routing

Download Modeling and Implications on Multi-Hop Routing
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Modeling and Implications on Multi-Hop Routing and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Modeling and Implications on Multi-Hop Routing 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?