Estimating clock uncertainty for efficient duty-cycling in sensor networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Estimating clock uncertainty for efficient duty-cycling in sensor networks

Full text

Pdf (1.40 MB)

Source

IEEE/ACM Transactions on Networking (TON) archive
Volume 17 , Issue 3 (June 2009) table of contents

Pages 843-856

Year of Publication: 2009

ISSN:1063-6692

Authors

Saurabh Ganeriwal	Google, Mountain View, CA and Electrical Engineering Department, University of California, Los Angeles, CA
Ilias Tsigkogiannis	Microsoft Corporation, Redmond, WA and Electrical Engineering Department, University of California, Los Angeles, CA
Hohyun Shim	Synopsis, Mountain View, CA and Electrical Engineering Department, University of California, Los Angeles, CA
Vlassios Tsiatsis	Ericsson Research, Stockholm, Sweden and Electrical Engineering Department, University of California, Los Angeles, CA
Mani B. Srivastava	Electrical Engineering Department, University of California, Los Angeles, CA
Deepak Ganesan	University of Massachusetts, Amherst, MA

Publisher

IEEE Press Piscataway, NJ, USA

Bibliometrics

Downloads (6 Weeks): 23, Downloads (12 Months): 61, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	10.1109/TNET.2008.2001953

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 into practice. The dominant factor that prevents the optimal usage of the radio in real deployment settings is time uncertainty between sensor nodes which results in overhead in the form of long packet preambles, guard bands, and excessive control packets for synchronization. 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 the BMAC medium access control protocol, and demonstrate one to two orders of magnitude reduction in transmission energy consumption with negligible impact on packet loss rate.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Hui Dai , Richard Han, TSync: a lightweight bidirectional time synchronization service for wireless sensor networks, ACM SIGMOBILE Mobile Computing and Communications Review, v.8 n.1, January 2004 [doi>10.1145/980159.980173]
	2	P. Dutta, M. Grimmer, A. Arora, S. Bibyk, and D. Culler, "Design of a wireless sensor network platform for detecting rare, random, and ephemeral events," in Special Track on Platform Tools and Design Methods for Network Embedded Sensors (SPOTS), 2005, pp. 24-36.
	3	A. El-Hoiydi , J.-D. Decotignie, WiseMAC: an ultra low power MAC protocol for the downlink of infrastructure wireless sensor networks, Proceedings of the Ninth International Symposium on Computers and Communications 2004 Volume 2 (ISCC"04), p.244-251, June 28-July 01, 2004
	4	Jeremy Elson , Lewis Girod , Deborah Estrin, Fine-grained network time synchronization using reference broadcasts, ACM SIGOPS Operating Systems Review, v.36 n.SI, Winter 2002 [doi>10.1145/844128.844143]
	5	J. Elson and K. Romer, "Wireless sensor networks: A new regime for time synchronization," in Proc. 1st Workshop on Hot Topics in Networks (HotNets-I), Oct. 2002, pp. 36-42.
	6	Saurabh Ganeriwal , Ram Kumar , Mani B. Srivastava, Timing-sync protocol for sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958508]
	7	Miklós Maróti , Branislav Kusy , Gyula Simon , Ákos Lédeczi, The flooding time synchronization protocol, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031501]
	8	D. L. Mills, "Internet time synchronization/; The network time protocol," in Global States and Time in Distributed Systems. New Yrok: IEEE Computer Society Press, 1994, pp. 1482-1493.
	9	David L. Mills, Adaptive hybrid clock discipline algorithm for the network time protocol, IEEE/ACM Transactions on Networking (TON), v.6 n.5, p.505-514, Oct. 1998 [doi>10.1109/90.731182]
	10	Santashil PalChaudhuri , Amit Kumar Saha , David B. Johnson, Adaptive clock synchronization in sensor networks, Proceedings of the 3rd international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984672]
	11	Joseph Polastre , Jason Hill , David Culler, Versatile low power media access for wireless sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031508]
	12	C. R. Rao, Linear Statistical Inference and Its Applications. New York: Wiley, 1973.
	13	Kay Römer, Time synchronization in ad hoc networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501436.501440]
	14	K. Romer, "Temporal message ordering in wireless sensor networks," in IFIP MedHicNet, Jun. 2003, pp. 84-89.
	15	Curt Schurgers , Vlasios Tsiatsis , Saurabh Ganeriwal , Mani Srivastava, Optimizing Sensor Networks in the Energy-Latency-Density Design Space, IEEE Transactions on Mobile Computing, v.1 n.1, p.70-80, January 2002 [doi>10.1109/TMC.2002.1011060]
	16	M. Sichitiu and C. Veerarittiphan, "Simple, Accurate time synchronization for wireless sensor networks," in Proc. IEEE Wireless Communications and Networking Conf. (WCNC), 2003, pp. 16-20.
	17	B. Sundararaman, U. Buy, and A. Kshemkalyani, "Clock synchronization for wireless sensor networks: A survey," Tech. Rep., Mar. 2005.
	18	An-swol Hu , Sergio D. Servetto, Asymptotically optimal time synchronization in dense sensor networks, Proceedings of the 2nd ACM international conference on Wireless sensor networks and applications, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/941350.941352]
	19	V. Tsiatsis and S. Ganeriwal, RATS Design Document. [Online]. Available: http://cvs.nesl.ucla.edu/cvs/viewcvs.cgi/sos-l.x/modules/ timesync/rats/RATS.pdf
	20	I. Tsigkogiannis and S. Ganeriwal, UBMAC Design Document. [Online]. Available: http://cvs.nesl.ucla.edu/cvs/viewcvs.cgi/sos-1.x/ drivers/ubmac/UBMAC.pdf
	21	Tijs van Dam , Koen Langendoen, An adaptive energy-efficient MAC protocol for wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958512]
	22	Jana van Greunen , Jan Rabaey, Lightweight time synchronization for sensor networks, Proceedings of the 2nd ACM international conference on Wireless sensor networks and applications, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/941350.941353]
	23	W. Ye, J. Heidemann, and D. Estrin, "An energy-efficient MAC protocol for wireless sensor networks," in Proc. IEEE INFOCOM, 2002, pp. 1567-1576.