Timing-sync protocol for sensor networks

ABSTRACT

Wireless ad-hoc sensor networks have emerged as an interesting and important research area in the last few years. The applications envisioned for such networks require collaborative execution of a distributed task amongst a large set of sensor nodes. This is realized by exchanging messages that are time-stamped using the local clocks on the nodes. Therefore, time synchronization becomes an indispensable piece of infrastructure in such systems. For years, protocols such as NTP have kept the clocks of networked systems in perfect synchrony. However, this new class of networks has a large density of nodes and very limited energy resource at every node; this leads to scalability requirements while limiting the resources that can be used to achieve them. A new approach to time synchronization is needed for sensor networks.In this paper, we present Timing-sync Protocol for Sensor Networks (TPSN) that aims at providing network-wide time synchronization in a sensor network. The algorithm works in two steps. In the first step, a hierarchical structure is established in the network and then a pair wise synchronization is performed along the edges of this structure to establish a global timescale throughout the network. Eventually all nodes in the network synchronize their clocks to a reference node. We implement our algorithm on Berkeley motes and show that it can synchronize a pair of neighboring motes to an average accuracy of less than 20ms. We argue that TPSN roughly gives a 2x better performance as compared to Reference Broadcast Synchronization (RBS) and verify this by implementing RBS on motes. We also show the performance of TPSN over small multihop networks of motes and use simulations to verify its accuracy over large-scale networks. We show that the synchronization accuracy does not degrade significantly with the increase in number of nodes being deployed, making TPSN completely scalable.

REFERENCES

• 1: K. Sohrabi, J. Gao, V. Ailawadhi, G. Pottie, "Protocols for self-organization of a wireless sensor network," IEEE Personal Communications Magazine, Vol.7, No.5, pp. 16--27, Oct. 2000.
• 2: Deborah Estrin , Ramesh Govindan , John Heidemann , Satish Kumar, Next century challenges: scalable coordination in sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.263-270, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313556]
• 3: S. I. Roumeliotis, G. A. Bekey, "An extended kalman filter for frequent local and infrequent global sensor data fusion," In Proc. of the SPIE (Sensor Fusion and Decentralized Control in Autonomous Robotic Systems, Pittsburgh, PA, USA, Oct. 14-15, 1997, pp.11--22.
• 4: V. Claesso, H. Lönn, N. Suri, "Efficient TDMA Synchronization for Distributed Embedded Systems"" 20th symposium on Reliable Distributed Systems (SRDS), pp 198--201, October, 2001.
• 5: D. L. Mills, "Internet time synchronization: The Network Time Protocol" In Z. Yang and T. A. Marsland, editors, Global States and Time in Distributed Systems. IEEE Computer Society Press, 1994.
• 6: Paulo Veríssimo , Luís Rodrigues , Antonio Casimiro, CesiumSpray>: a Precise and Accurate Global Time Servicefor Large-scale Systems, Real-Time Systems, v.12 n.3, p.243-294, May 1997 [doi>10.1023/A:1007949113722]
• 7: 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]
• 8: Jeremy Elson , Deborah Estrin, Time Synchronization for Wireless Sensor Networks, Proceedings of the 15th International Parallel & Distributed Processing Symposium, p.186, April 23-27, 2001
• 9: K. Arvind, Probabilistic Clock Synchronization in Distributed Systems, IEEE Transactions on Parallel and Distributed Systems, v.5 n.5, p.474-487, May 1994 [doi>10.1109/71.282558]
• 10: J. Elson, K. Romer, "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.
• 11: 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]
• 12: Navneet Malpani , Jennifer L. Welch , Nitin Vaidya, Leader election algorithms for mobile ad hoc networks, Proceedings of the 4th international workshop on Discrete algorithms and methods for mobile computing and communications, p.96-103, August 11-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345848.345871]
• 13: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TAG: a Tiny AGgregation service for Ad-Hoc sensor networks, 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.1060303]
• 14: Chipcon CC1000 Radio Datasheet, http://www.chipcon.com/files/CC1000_Data_Sheet_2_1.pdf
• 15: J. Hill and D. Culler, "A Wireless Embedded Sensor Architecture for System-level Optimization." Technical report, U. C. Berkeley, 2001.
• 16: TinyOS, http://webs.cs.berkeley.edu/tos/
• 17: 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]
• 18: S. Ganeriwal, V. Tsiatsis, C. Schurgers, M. B. Srivastava, "NESLsim: A parsec based simulation platform for sensor networks," NESL, 2002.
• 19: S. Ganeriwal, R. Kumar, S. Adlakha, M. B. Srivastava, "Network-wide time synchronization in sensor networks," NESL Technical Report, 2003.
• 20: Andreas Savvides , Chih-Chieh Han , Mani B. Strivastava, Dynamic fine-grained localization in Ad-Hoc networks of sensors, Proceedings of the 7th annual international conference on Mobile computing and networking, p.166-179, July 2001, Rome, Italy [doi>10.1145/381677.381693]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

General Terms:
Algorithms, Experimentation, Performance, Verification

Keywords:
clock drift, medium access control, packet delay, sensor networks, time synchronization