skip to main content
10.1145/1644038.1644061acmconferencesArticle/Chapter ViewAbstractPublication PagessensysConference Proceedingsconference-collections
research-article

Optimal clock synchronization in networks

Published: 04 November 2009 Publication History

Abstract

Having access to an accurate time is a vital building block in all networks; in wireless sensor networks even more so, because wireless media access or data fusion may depend on it. Starting out with a novel analysis, we show that orthodox clock synchronization algorithms make fundamental mistakes. The state-of-the-art clock synchronization algorithm FTSP exhibits an error that grows exponentially with the size of the network, for instance. Since the involved parameters are small, the error only becomes visible in midsize networks of about 10--20 nodes. In contrast, we present PulseSync, a new clock synchronization algorithm that is asymptotically optimal. We evaluate PulseSync on a Mica2 testbed, and by simulation on larger networks. On a 20 node network, the prototype implementation of PulseSync outperforms FTSP by a factor of 5. Theory and simulation show that for larger networks, PulseSync offers an accuracy which is several orders of magnitude better than FTSP. To round off the presentation, we investigate several optimization issues, e.g. media access and local skew.

References

[1]
TinyOS. http://www.tinyos.net/.
[2]
M. Allen, L. Girod, R. Newton, S. Madden, D. T. Blumstein, and D. Estrin. VoxNet: An Interactive, Rapidly-Deployable Acoustic Monitoring Platform. In Proc. 7th International Conference on Information Processing in Sensor Networks (IPSN), 2008.
[3]
R. Bar-Yehuda, O. Goldreich, and A. Itai. On the Time-Complexity of Broadcast in Multi-hop Radio Networks: An Exponential Gap Between Determinism and Randomization. J. Comput. Syst. Sci., 45(1):104--126, 1992.
[4]
S. Biaz and J. L. Welch. Closed Form Bounds for Clock Synchronization Under Simple Uncertainty Assumptions. Inf. Process. Lett., 80(3):151--157, 2001.
[5]
I. Chlamtac and S. Kutten. On Broadcasting in Radio Networks - Problem Analysis and Protocol Design. IEEE Transactions on Communications, 33:1240--1246, 1985.
[6]
I. Chlamtac and O. Weinstein. The Wave Expansion Approach to Broadcasting in Multihop Radio Networks. In Proc. 6th annual IEEE Conference on Computer Communications (INFOCOM), 1987.
[7]
A. Czumaj and W. Rytter. Broadcasting Algorithms in Radio Networks with Unknown Topology. In Proc. 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2003.
[8]
J. Elson, L. Girod, and D. Estrin. Fine-Grained Network Time Synchronization using Reference Broadcasts. In Proc. 5th Symposium on Operating Systems Design and Implementation (OSDI), 2002.
[9]
R. Fan and N. Lynch. Gradient Clock Synchronization. In Proc. 23rd annual ACM Symposium on Principles of Distributed Computing (PODC), 2004.
[10]
S. Ganeriwal, R. Kumar, and M. B. Srivastava. Timing-Sync Protocol for Sensor Networks. In Proc. 1st International Conference on Embedded Networked Sensor Systems (SenSys), 2003.
[11]
J. Hill and D. Culler. Mica: a Wireless Platform for Deeply Embedded Networks. Micro, IEEE, 22(6):12--24, 2002.
[12]
W. Hoeffding. Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association, 58(301):13--30, 1963.
[13]
S. Kim, S. Pakzad, D. Culler, J. Demmel, G. Fenves, S. Glaser, and M. Turon. Health Monitoring of Civil Infrastructures using Wireless Sensor Networks. In Proc. 6th International Conference on Information Processing in Sensor Networks (IPSN), 2007.
[14]
H. Kopetz and W. Ochsenreiter. Clock Synchronization in Distributed Real-Time Systems. IEEE Trans. Comput., 36(8), 1987.
[15]
F. Kuhn and R. Oshman. Gradient Clock Synchronization using Reference Broadcasts. CoRR, abs/0905.3454, 2009.
[16]
B. Kusy. Spatiotemporal Coordination in Wireless Sensor Networks. PhD thesis, Vanderbilt University, 2007.
[17]
C. Lenzen, T. Locher, and R. Wattenhofer. Tight Bounds for Clock Synchronization. In Proc. 28rd Annual ACM Symposium on Principles of Distributed Computing (PODC), 2009.
[18]
J. Lundelius and N. A. Lynch. An Upper and Lower Bound for Clock Synchronization. Information and Control, 62(2/3):190--204, 1984.
[19]
M. Maróti, B. Kusy, G. Simon, and Á. Lédeczi. The Flooding Time Synchronization Protocol. In Proc. 2nd International Conference on Embedded Networked Sensor Systems (SenSys), 2004.
[20]
L. Meier and L. Thiele. Brief announcement: Gradient Clock Synchronization in Sensor Networks. In Proc. 24th annual ACM Symposium on Principles of Distributed Computing (PODC), 2005.
[21]
D. Mills. Internet Time Synchronization: the Network Time Protocol. IEEE Transactions on Communications, 39(10):1482--1493, Oct 1991.
[22]
T. Moscibroda, P. von Rickenbach, and R. Wattenhofer. Analyzing the Energy-Latency Trade-Off During the Deployment of Sensor Networks. In Proc. 25th Conference on Computer Communications (INFOCOM), 2006.
[23]
R. Ostrovsky and B. Patt-Shamir. Optimal and Efficient Clock Synchronization Under drifting Clocks. In Proc. 18th annual ACM Symposium on Principles of Distributed Computing (PODC), 1999.
[24]
K. Römer. Time Synchronization in Ad Hoc Networks. In Proc. 2nd ACM International Symposium on Mobile ad hoc Networking&Computing (MobiHoc), 2001.
[25]
J. Sallai, B. Kusy, A. Ledeczi, and P. Dutta. On the Scalability of Routing Integrated Time Synchronization. 3rd European Workshop on Wireless Sensor Networks (EWSN), 2006.
[26]
J. Schneider and R. Wattenhofer. A log-star Distributed Maximal Independent Set Algorithm for Growth-Bounded Graphs. In Proc. 27th ACM Symposium on Principles of Distributed Computing (PODC), 2008.
[27]
G. Simon, M. Maróti, A. Lédeczi, G. Balogh, B. Kusy, A. Nádas, G. Pap, J. Sallai, and K. Frampton. Sensor Network-based Countersniper System. In Proc. 2nd International Conference on Embedded Networked Sensor Systems (SenSys), 2004.
[28]
R. Solis, V. Borkar, and P. R. Kumar. A New Distributed Time Synchronization Protocol for Multihop Wireless Networks. In Proc. 45th IEEE Conference on Decision and Control (CDC), 2006.
[29]
P. Sommer and R. Wattenhofer. Gradient Clock Synchronization in Wireless Sensor Networks. In Proc. 8th ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN), 2009.
[30]
T. K. Srikanth and S. Toueg. Optimal Clock Synchronization. J. ACM, 34(3), 1987.
[31]
A. A. Syed and J. Heidemann. Time synchronization for high latency acoustic networks. In Proc. 25th Conference on Computer Communications (InfoCom), 2006.
[32]
G. Werner-Allen, K. Lorincz, J. Johnson, J. Lees, and M. Welsh. Fidelity and Yield in a Volcano Monitoring Sensor Network. In Proc. 7th Symposium on Operating Systems Design and Implementation (OSDI), 2006.
[33]
G. Werner-Allen, G. Tewari, A. Patel, M. Welsh, and R. Nagpal. Firefly-Inspired Sensor Network Synchronicity with Realistic Radio Effects. In Proc. 3rd International Conference on Embedded Networked Sensor Systems (SenSys), 2005.

Cited By

View all
  • (2024)Aion: Secure Transaction Ordering Using TEEsComputer Security – ESORICS 202310.1007/978-3-031-51482-1_17(332-350)Online publication date: 11-Jan-2024
  • (2023)Optimizing Comprehensive Cost of Charger Deployment in Multi-hop Wireless ChargingACM Transactions on Sensor Networks10.1145/358495019:4(1-24)Online publication date: 16-May-2023
  • (2023)SoLiCiT: Synchronous Listen, Code, and Transmit Protocol for Wireless Control ApplicationsIEEE Systems Journal10.1109/JSYST.2023.323677817:3(4212-4223)Online publication date: Sep-2023
  • Show More Cited By

Index Terms

  1. Optimal clock synchronization in networks

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      SenSys '09: Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems
      November 2009
      438 pages
      ISBN:9781605585192
      DOI:10.1145/1644038
      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. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 04 November 2009

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. clock drift
      2. lower bound
      3. sensor networks
      4. time synchronization

      Qualifiers

      • Research-article

      Conference

      Acceptance Rates

      Overall Acceptance Rate 198 of 990 submissions, 20%

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)47
      • Downloads (Last 6 weeks)7
      Reflects downloads up to 18 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2024)Aion: Secure Transaction Ordering Using TEEsComputer Security – ESORICS 202310.1007/978-3-031-51482-1_17(332-350)Online publication date: 11-Jan-2024
      • (2023)Optimizing Comprehensive Cost of Charger Deployment in Multi-hop Wireless ChargingACM Transactions on Sensor Networks10.1145/358495019:4(1-24)Online publication date: 16-May-2023
      • (2023)SoLiCiT: Synchronous Listen, Code, and Transmit Protocol for Wireless Control ApplicationsIEEE Systems Journal10.1109/JSYST.2023.323677817:3(4212-4223)Online publication date: Sep-2023
      • (2023)The Internet of Sounds: Convergent Trends, Insights, and Future DirectionsIEEE Internet of Things Journal10.1109/JIOT.2023.325360210:13(11264-11292)Online publication date: 1-Jul-2023
      • (2023)An Accurate Time Synchronization Algorithm Based on Ultra-Wideband Wireless Sensor Networks2023 3rd International Conference on Electronic Information Engineering and Computer Science (EIECS)10.1109/EIECS59936.2023.10435528(238-242)Online publication date: 22-Sep-2023
      • (2022)LPSRS: Low-Power Multi-Hop Synchronization Based on Reference Node Scheduling for Internet of ThingsEnergies10.3390/en1506228915:6(2289)Online publication date: 21-Mar-2022
      • (2022)Probabilistic Flooding Performance Analysis Exploiting Graph Spectra PropertiesIEEE/ACM Transactions on Networking10.1109/TNET.2022.3192310(1-14)Online publication date: 2022
      • (2022)Timestamp-Free Clock Syntonization for IoT Using Carrier Frequency OffsetIEEE Transactions on Mobile Computing10.1109/TMC.2020.300913221:2(712-727)Online publication date: 1-Feb-2022
      • (2022)A Novel Rapid-Flooding Approach With Real-Time Delay Compensation for Wireless-Sensor Network Time SynchronizationIEEE Transactions on Cybernetics10.1109/TCYB.2020.298775852:3(1415-1428)Online publication date: Mar-2022
      • (2022)Toward a Shared Sense of Time for a Network of Batteryless, Intermittently-powered Nodes2022 IEEE International Performance, Computing, and Communications Conference (IPCCC)10.1109/IPCCC55026.2022.9894317(138-146)Online publication date: 11-Nov-2022
      • Show More Cited By

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media