Lightweight time synchronization for sensor networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Lightweight time synchronization for sensor networks

Full text

Pdf (1.38 MB)

Source

International Workshop on Wireless Sensor Networks and Applications archive
Proceedings of the 2nd ACM international conference on Wireless sensor networks and applications table of contents

San Diego, CA, USA

SESSION: Time synch and localization table of contents

Pages: 11 - 19

Year of Publication: 2003

ISBN:1-58113-764-8

Authors

Jana van Greunen	University of California, Berkeley, Berkeley, CA
Jan Rabaey	University of California, Berkeley, Berkeley, CA

Sponsor

ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 19, Downloads (12 Months): 145, Citation Count: 22

Additional Information:

abstract references cited by 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:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/941350.941353 What is a DOI?

ABSTRACT

This paper presents lightweight tree-based synchronization (LTS) methods for sensor networks. First, a single-hop, pair-wise synchronization scheme is analyzed. This scheme requires the exchange of only three messages and has Gaussian error properties. The single-hop approach is extended to a centralized multi-hop synchronization method. Multi-hop synchronization consists of pair-wise synchronizations performed along the edges of a spanning tree. Multi-hop synchronization requires only n-1 pair-wise synchronizations for a network of n nodes. In addition, we show that the communication complexity and accuracy of multi-hop synchronization is a function of the construction and depth of the spanning tree; several spanning-tree construction algorithms are described. Further, the required refresh rate of multi-hop synchronization is shown as a function of clock drift and the accuracy of single-hop synchronization. Finally, a distributed multi-hop synchronization is presented where nodes keep track of their own clock drift and their synchronization accuracy. In this scheme, nodes initialize their own resynchronization as needed.

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	Jan Rabaey, Ultra Low-Energy Transceivers for Wireless Sensor Networks, Proceedings of the 15th symposium on Integrated circuits and systems design, p.386, September 09-14, 2002
	2	B. Hofmann-Wellenhof, H. Lichtenegger, and J. Collins GPS Theory and Practice, SpringerWienNewYork, 1997.
	3	D. Mills, Network Time Protocol (Version 3) Specification, Implementation and Analysis, from http://www.faqs.org/ftp/rfc/rfc1305.pdf.
	4	E. Anceaume and I. Puaut , A Taxonomy of Clock Synchronization Algorithms, Research report IRISA, NoPI1103, July 1997.
	5	Jeremy Elson , Lewis Girod , Deborah Estrin, Fine-grained network time synchronization using reference broadcasts, Proceedings of the 5th symposium on Operating systems design and implementation Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060304]
	6	M. L. Sichitiu and C. Veerarittiphan, Simple, Accurate Time Synchronization for Wireless Sensor Networks. IEEE Wireless Communications and Networking Conference, WCNC 2003.
	7	Saurabh Ganeriwal, Ram Kumar, Sachin Adlakha and Mani Srivastava, "Network-wide Time Synchronization in Sensor Networks," Technical Report UCLA, April 2002.
	8	S. Mitra and J. Rabek, Power Efficient Clustering for Clock Synchronizarion in Dynamic Multi-hop Sensor Networks, from http://theory.lcs.mit.edu/~mitras/courses/6829/project/project_main.html.
	9	J. Elson and K. Römer, Wireless Sensor Networks: A New Regime for Time Synchronization, Proceedings of the First Workshop on Hot Topics In Networks (HotNets-I), Princeton, New Jersey. October 28--29 2002.
	10	H. Kopetz, W. Schwabl. Global time in distributed real-time systems. Technical Report 15/89, Technishe Univesität Wien, 1989.
	11	Warneke, B. Atwood, K.S.J. Pister, Smart Dust Mote Forerunners, Proceedings of the Fourteenth Annual International Conference on Microelectromechanical Systems (MEMS 2001), Interlaken, Switzerland, January 21-25, 2001, pp. 357--360.
	12	B. Awerbuch, A new distributed depth first search algorithm, Inf. Proc. Lett. 20 (1985), 147--150.
	13	Azzedine Boukerche , Carl Tropper, A Distributed Graph Algorithm for the Detection of Local Cycles and Knots, IEEE Transactions on Parallel and Distributed Systems, v.9 n.8, p.748-757, August 1998 [doi>10.1109/71.706047]
	14	A. Varga, "The OMNeT++ Discrete Event Simulation System," in European Simulation Multiconference (ESM'2001), Prague, Czech Republic, June 2001.
	15	C. Guo, L. C. Zhong and J. M. Rabaey, "Low Power Distributed MAC for Ad Hoc Sensor Radio Networks", Proceedings of IEEE GlobeCom 2001, San Antonio, November 25-29, 2001.

CITED BY 22

	Daniela Tulone, A resource--efficient time estimation for wireless sensor networks, Proceedings of the 2004 joint workshop on Foundations of mobile computing, October 01-01, 2004, Philadelphia, PA, USA
	Chao Gui , Prasant Mohapatra, Power conservation and quality of surveillance in target tracking sensor networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA
	Caimu Tang , Cauligi S. Raghavendra, Compression techniques for wireless sensor networks, Wireless sensor networks, Kluwer Academic Publishers, Norwell, MA, 2004
	Ning Xu , Sumit Rangwala , Krishna Kant Chintalapudi , Deepak Ganesan , Alan Broad , Ramesh Govindan , Deborah Estrin, A wireless sensor network For structural monitoring, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA
	Jiejun Kong , Zhengrong Ji , Weichao Wang , Mario Gerla , Rajive Bagrodia , Bharat Bhargava, Low-cost attacks against packet delivery, localization and time synchronization services in under-water sensor networks, Proceedings of the 4th ACM workshop on Wireless security, September 02-02, 2005, Cologne, Germany
	Saurabh Ganeriwal , Srdjan Capkun , Chih-Chieh Han , Mani B. Srivastava, Secure time synchronization service for sensor networks, Proceedings of the 4th ACM workshop on Wireless security, September 02-02, 2005, Cologne, Germany
	Kun Sun , Peng Ning , Cliff Wang, Fault-Tolerant Cluster-Wise Clock Synchronization for Wireless Sensor Networks, IEEE Transactions on Dependable and Secure Computing, v.2 n.3, p.177-189, July 2005
	Emerson Farrugia , Robert Simon, An efficient and secure protocol for sensor network time synchronization, Journal of Systems and Software, v.79 n.2, p.147-162, February 2006
	An-Swol Hu , Sergio D. Servetto, On the scalability of cooperative time synchronization in pulse-connected networks, IEEE/ACM Transactions on Networking (TON), v.14 n.SI, p.2725-2748, June 2006
	Wen-Zhan Song , Fenghua Yuan , Richard LaHusen , Behrooz Shirazi, Time-optimum packet scheduling for many-to-one routing in wireless sensor networks, International Journal of Parallel, Emergent and Distributed Systems, v.22 n.5, p.355-370, September 2007
	Suyoung Yoon , Chanchai Veerarittiphan , Mihail L. Sichitiu, Tiny-sync: Tight time synchronization for wireless sensor networks, ACM Transactions on Sensor Networks (TOSN), v.3 n.2, p.8-es, June 2007
	Ya. R. Faizulkhakov, Time synchronization methods for wireless sensor networks: A survey, Programming and Computing Software, v.33 n.4, p.214-226, July 2007
	Kyoung-Lae Noh , Yik-Chung Wu , Khalid Qaraqe , Bruce W. Suter, Extension of pairwise broadcast clock synchronization for multicluster sensor networks, EURASIP Journal on Advances in Signal Processing, v.8 n.2, p.1-10, January 2008
	Saurabh Ganeriwal , Christina Pöpper , Srdjan Čapkun , Mani B. Srivastava, Secure Time Synchronization in Sensor Networks, ACM Transactions on Information and System Security (TISSEC), v.11 n.4, p.1-35, July 2008
	Branislav Kusy , Prabal Dutta , Philip Levis , Miklos Maroti , Akos Ledeczi , David Culler, Elapsed time on arrival: a simple and versatile primitive for canonical time synchronisation services, International Journal of Ad Hoc and Ubiquitous Computing, v.1 n.4, p.239-251, July 2006
	Liusheng Huang , Hongli Xu , Yingyu Wan , Junmin Wu , Hong Li, An efficient synchronisation protocol for wireless sensor network, International Journal of Sensor Networks, v.2 n.1/2, p.17-24, April 2007
	Philipp Sommer , Roger Wattenhofer, Symmetric clock synchronization in sensor networks, Proceedings of the workshop on Real-world wireless sensor networks, April 01-01, 2008, Glasgow, Scotland
	Wei Zhang , Yonghe Liu , Sajal K. Das , Pradip De, Fast track article: Secure data aggregation in wireless sensor networks: A watermark based authentication supportive approach, Pervasive and Mobile Computing, v.4 n.5, p.658-680, October, 2008
	Reuven Cohen , Boris Kapchits, An optimal wake-up scheduling algorithm for minimizing energy consumption while limiting maximum delay in a mesh sensor network, IEEE/ACM Transactions on Networking (TON), v.17 n.2, p.570-581, April 2009
	Murtuza Jadliwala , Qi Duan , Shambhu Upadhyaya , Jinhui Xu, Towards a theory for securing time synchronization in wireless sensor networks, Proceedings of the second ACM conference on Wireless network security, March 16-19, 2009, Zurich, Switzerland
	Kyoung-Lae Noh , Yik-Chung Wu , Khalid Qaraqe , Bruce W. Suter, Extension of pairwise broadcast clock synchronization for multicluster sensor networks, EURASIP Journal on Advances in Signal Processing, 2008, p.1-10, January 2008
	Saurabh Ganeriwal , Ilias Tsigkogiannis , Hohyun Shim , Vlassios Tsiatsis , Mani B. Srivastava , Deepak Ganesan, Estimating clock uncertainty for efficient duty-cycling in sensor networks, IEEE/ACM Transactions on Networking (TON), v.17 n.3, p.843-856, June 2009