DOC PREVIEW
Berkeley ELENG 290Q - Estimating Clock Uncertainty for Efficient Duty-Cycling in Sensor Networks

This preview shows page 1-2-3-4 out of 12 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Estimating Clock Uncertainty for Efficient Duty-Cycling in Sensor Networks Saurabh Ganeriwal, Deepak Ganesan†, Hohyun Shim, Vlasios Tsiatsis, Mani B. Srivastava Networked and Embedded Systems lab, 56-125B, EE-IV, University of California Los Angeles, CA 90095 † Department of Computer Science, University of Massachusetts, MA 01003 {saurabh, tsiatsis, shimho, mbs}@ee.ucla.edu, {dganesan}@cs.umass.edu ABSTRACT Radio duty cycling has received significant attention in sensor networking literature, particularly in the form of protocols for medium access control and topology management. While many protocols have claimed to achieve significant duty-cycling benefits in theory and simulation, these benefits have often not translated to practice. The dominant factor that prevents the optimal usage of the radio in real deployment settings is time uncertainty between sensor nodes. This paper proposes an uncertainty-driven approach to duty-cycling where a model of long-term clock drift is used to minimize the duty-cycling overhead. First, we use long-term empirical measurements to evaluate and analyze in-depth the interplay between three key parameters that influence long-term synchronization - synchronization rate, history of past synchronization beacons and the estimation scheme. Second, we use this measurement-based study to design a rate-adaptive, energy-efficient long-term time synchronization algorithm that can adapt to changing clock drift and environmental conditions while achieving application-specific precision with very high probability. Finally, we integrate our uncertainty-driven time synchronization scheme with a MAC layer protocol, BMAC, and empirically demonstrate one to two orders of magnitude reduction in the transmit energy consumption at a node with negligible impact on the packet loss rate. Categories and Subject Descriptors C.2.2 [Computer Systems Organization]: Computer Communication Networks – Network Protocols. General Terms Algorithms, Experimentation, Performance, Verification. Keywords Sensor Networks, Time Synchronization, Sampling Period, Clock Drift, Polynomial Model Estimation, Rate Adaptation. 1. INTRODUCTION Many important applications of sensor networks involve the detection of rare, random and ephemeral events [1]. Examples of such event-response applications are diverse and include intrusion detection, chemical spill monitoring, warning of imminent natural disasters, condition-based monitoring of complex equipment and structural integrity monitoring. In theory, sensor nodes deployed for these applications need to use the radio only when the rare events are observed, hence, radio energy consumption should be minimal. However, this is far from true in practice since much energy is expended in addressing time uncertainty between communicating nodes. This can be illustrated by a simple example. Consider a generic event-response network where, to save energy, the nodes are duty-cycled. By default the radio would be off but would wake up periodically to participate in potential network communication. Consider two nodes A and B that simultaneously decide to wakeup after time t to check if the other node has observed an interesting event. During this period t, clocks on both A and B can vary in several uncorrelated ways due to ambient conditions and clock crystal characteristics. Therefore, the local time at A and B can be quite different at time t, hence, A and B would wakeup at different times. Existing duty-cycling techniques use a variety of approaches to deal with this uncertainty. A popular MAC layer protocol, BMAC [2], uses an asynchronous technique that involves no time synchronization or clock estimation whatsoever. Instead, each packet is transmitted with a long preamble which is chosen such that the receiver would wakeup some time during the preamble (refer to Figure 1). This incurs significant transmission overhead. For example with 11.5% duty-cycle a preamble of 250 bytes is used to transmit a 29 byte payload! Other techniques such as SMAC [3] and TMAC [4] use synchronized techniques where explicit time synchronization beacons are transmitted periodically between neighboring nodes. This enables the transmitter to turn on the radio at the right moment (refer to Figure 1), but the inability to deal effectively with time varying changes in clock drift force these techniques to re-synchronize frequently. For instance, one of the most efficient time synchronization protocols available in literature, FTSP [5], synchronizes once every minute to achieve 90µs synchronization error. To put it into perspective, if the event rate is once every hour, 60 extra synchronization beacons will be transmitted for every event notification packet. Thus, existing radio duty-cycling approaches expend a lot of energy in handling time uncertainty between sensor nodes. The lack of techniques to accurately estimate time uncertainty also impacts the ability to deploy long-lived sensor network applications. Although available time synchronization implementations such as FTSP [5], RBS [6] and TPSN [7] can synchronize a pair of nodes within a few microseconds, their focus has been on achieving accurate instantaneous Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. SenSys’05, November 2-4, 2005, San Diego, California, USA. Copyright 2005 ACM 1-59593-054-X/05/0011…$5.00. 130synchronization. These approaches do not enable us to understand either how error accumulates over long periods into the future or how to choose the synchronization frequency for bounding the time uncertainty. While these schemes are important for several applications that require short-term synchronization such as measuring the time-of-flight, acoustic beamforming and tracking, they are insufficient for efficient duty-cycling as well as for applications that require continuous time synchronization such as coordinated actuation and synchronized sampling. In real application scenarios where these approaches have been employed, the choice of synchronization frequency has been handpicked to correspond to the precision requirements of the


View Full Document

Berkeley ELENG 290Q - Estimating Clock Uncertainty for Efficient Duty-Cycling in Sensor Networks

Documents in this Course
Lab 1

Lab 1

16 pages

Lab 1

Lab 1

16 pages

Load more
Download Estimating Clock Uncertainty for Efficient Duty-Cycling in Sensor Networks
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 Estimating Clock Uncertainty for Efficient Duty-Cycling in Sensor Networks 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 Estimating Clock Uncertainty for Efficient Duty-Cycling in Sensor Networks 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?