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.
- 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.Google ScholarCross Ref
- D. Estrin, R. Govindan, J. Heidemann, S. Kumar, "Next Century Challenges: Scalable Coordination in Sensor Networks", ACM Mobicom Conference, Seattle, WA, August 1999. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google ScholarCross Ref
- 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.Google Scholar
- P. Verissimo, L. Rodrigues, A. Casimiro, "CesiumSpray: A Precise and Accurate Global Time Service for Large-Scale Systems," Journal of Real-Time Systems, 12(3): 243--294, May 1997. Google ScholarDigital Library
- Jeremy Elson, Lewis Girod and Deborah Estrin, "Fine-Grained Network Time Synchronization using Reference Broadcasts," In the proceedings of the fifth symposium on Operating System Design and Implementation (OSDI 2002), December 2002. Google ScholarDigital Library
- J. Elson, D. Estrin, "Time Synchronization for Wireless Sensor Networks," Proceedings of the 2001 International Parallel and Distributed Processing Symposium (IPDPS), Workshop on Parallel and Distributed Computing Issues in Wireless and Mobile Computing, San Francisco, California, USA, April 2001. Google ScholarDigital Library
- K. Arvind, "Probabilistic Clock Synchronization in Distributed Systems," IEEE Transactions on Parallel and Distributed Systems, 5(5): 474--487, May 1994. Google ScholarDigital Library
- 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.Google Scholar
- Kay Romer (ETH-Zurich), "Time synchronization in ad hoc networks," Mobihoc, 2001. Google ScholarDigital Library
- N. Malpani, J. L. Welch, N. Vaidya, "Leader election algorithm for mobile ad-hoc networks," In Proceedings of 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communication, pp. 96--103, August 2000. Google ScholarDigital Library
- S. R. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong, "TAG: A Tiny AGgregation Service for Ad-hoc Sensor Networks", OSDI Conference, 2002. Google ScholarDigital Library
- Chipcon CC1000 Radio Datasheet, http://www.chipcon.com/files/CC1000_Data_Sheet_2_1.pdfGoogle Scholar
- J. Hill and D. Culler, "A Wireless Embedded Sensor Architecture for System-level Optimization." Technical report, U. C. Berkeley, 2001.Google Scholar
- TinyOS, http://webs.cs.berkeley.edu/tos/Google Scholar
- S. Ganeriwal, Mani B. Srivastava, "Timing-sync Protocol for Sensor Networks (TPSN) on Berkeley Motes", NESL 2003. Google ScholarDigital Library
- S. Ganeriwal, V. Tsiatsis, C. Schurgers, M. B. Srivastava, "NESLsim: A parsec based simulation platform for sensor networks," NESL, 2002.Google Scholar
- S. Ganeriwal, R. Kumar, S. Adlakha, M. B. Srivastava, "Network-wide time synchronization in sensor networks," NESL Technical Report, 2003.Google Scholar
- A. Savvides, C. C. Han, M. B. Srivastava, "Dynamic fine-grained localization in ad-hoc networks of sensors", MobiCom 2001, Rome, Italy, pp.166--179, July 2001. Google ScholarDigital Library
Index Terms
- Timing-sync protocol for sensor networks
Recommendations
Optimal clock synchronization in networks
SenSys '09: Proceedings of the 7th ACM Conference on Embedded Networked Sensor SystemsHaving 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 ...
The flooding time synchronization protocol
SenSys '04: Proceedings of the 2nd international conference on Embedded networked sensor systemsWireless sensor network applications, similarly to other distributed systems, often require a scalable time synchronization service enabling data consistency and coordination. This paper describes the Flooding Time Synchronization Protocol (FTSP), ...
Ratio-based time synchronization protocol in wireless sensor networks
Time synchronization plays a key role in the wireless sensor networks (WSNs). Time synchronization is realized by those messages that are time-stamped. But there are several delay times during transmission after time stamping. Most of them are uncertain ...
Comments