Abstract
Time synchronization is a fundamental service in many wireless applications. While the synchronization problem is well-studied in traditional wired networks, physical constraints of the wireless medium impose a unique set of challenges. We present a novel time synchronization algorithm which is highly energy efficient and failure/recovery-tolerant. Our algorithm allows nodes to synchronize to sources of real time such as GPS when such signals are available, but continues to synchronize nodes to each other, even in the absence of GPS. In addition, the algorithm satisfies a relaxed gradient property, in which the degree of synchronization between nodes varies as a linear function of their distance. Thus, nearby nodes are highly synchronized, which is desirable in many wireless applications.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Elson, J., Girod, L., Estrin, D.: Fine-grained network time synchronization using reference broadcasts. SIGOPS Operating Systems Review 36(SI), 147–163 (2002)
Fan, R., Lynch, N.: Gradient clock syncrhonization. In: Proceedings of the Twenty-third Annual ACM PODC, ACM Press, New York (2004) (to appear)
Fetzer, C., Cristian, F.: Integrating external and internal clock synchronization. Journal of Real-Time Systems 12(2), 123–172 (1997)
Kaynar, D., Lynch, N., Segala, R., Vaandrager, F.: Timed i/o automata: A mathematical framework for modeling and analyzing real-time systems. In: Proceedings of the 24th IEEE International Real-Time Systems Symposium (2003)
Lloyd, E.L.: Broadcast scheduling for TDMA in wireless multihop networks. John Wiley & Sons, Inc., Chichester (2002)
Mills, D.L.: Internet time synchronization: The network time protocol. IEEE Transactions on Computers 39(10), 1482–1493 (1991)
Srikanth, T.K., Toueg, S.: Optimal clock synchronization. J. ACM 34(3), 626–645 (1987)
Verissimo, P., Rodrigues, L., Casimiro, A.: Cesiumspray: a precise and accurate global time service for large-scale systems. Technical Report NAV-TR-97-0001, Universidade de Lisboa (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fan, R., Chakraborty, I., Lynch, N. (2005). Clock Synchronization for Wireless Networks. In: Higashino, T. (eds) Principles of Distributed Systems. OPODIS 2004. Lecture Notes in Computer Science, vol 3544. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11516798_29
Download citation
DOI: https://doi.org/10.1007/11516798_29
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-27324-0
Online ISBN: 978-3-540-31584-1
eBook Packages: Computer ScienceComputer Science (R0)