A Greedy Distributed Time Synchronization Algorithm for Wireless Sensor Networks
- 1 January 2008
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2327-2331
- https://doi.org/10.1109/icc.2008.443
Abstract
In this paper, a distributed network-wise synchronization protocol is presented. The protocol employs Pairwise Broadcast Synchronization (PBS) in which sensors can be synchronized by merely overhearing the exchange of synchronization packets. We investigate how to minimize the number of PBS required to synchronize all nodes in a network. We show that the problem of finding the minimum number of PBS required is NP-complete. A distributed greedy algorithm is proposed. The protocol is tested by extensive simulations. Although the algorithm behind is heuristic-based, the performance is closed to the centralized algorithm. The message overhead is compared with that of Timing-Sync Protocol for Sensor Networks (TPSN).Keywords
This publication has 9 references indexed in Scilit:
- Pairwise Broadcast Clock Synchronization for Wireless Sensor NetworksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2007
- The flooding time synchronization protocolPublished by Association for Computing Machinery (ACM) ,2004
- Simple, accurate time synchronization for wireless sensor networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Timing-sync protocol for sensor networksPublished by Association for Computing Machinery (ACM) ,2003
- Wireless sensor networksACM SIGCOMM Computer Communication Review, 2003
- Fine-grained network time synchronization using reference broadcastsACM SIGOPS Operating Systems Review, 2002
- Wireless sensor networks: a surveyComputer Networks, 2002
- Next century challengesPublished by Association for Computing Machinery (ACM) ,1999
- Reducibility among Combinatorial ProblemsPublished by Springer Science and Business Media LLC ,1972