A distributed multihop time synchronization protocol for wireless sensor networks using Pairwise Broadcast Synchronization
- 2 May 2009
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Wireless Communications
- Vol. 8 (4), 1764-1772
- https://doi.org/10.1109/twc.2009.080112
Abstract
Recently, a time synchronization algorithm called pairwise broadcast synchronization (PBS) is proposed. With PBS, a sensor can be synchronized by overhearing synchronization packet exchange among its neighbouring sensors without sending out any packet itself. In an one-hop sensor network where every node is a neighbour of each other, a single PBS message exchange between two nodes would facilitate all nodes to synchronize. However, in a multi-hop sensor network, PBS message exchanges in several node pairs are needed in order to achieve network-wide synchronization. To reduce the number of message exchanges, these node pairs should be carefully chosen. In this paper, we investigate how to choose these ldquoappropriaterdquo sensors aiming at reducing the number of PBS message exchanges while allowing every node to synchronize. This selection problem is shown to be NP-complete, for which the greedy heuristic is a good polynomial-time approximation algorithm. Nevertheless, a centralized algorithm is not suitable for wireless sensor networks. Therefore, we develop a distributed heuristic algorithm allowing a sensor to determine how to synchronize itself based on its neighbourhood information only. The protocol is tested through extensive simulations. The simulation results reveal that the proposed protocol gives consistent performance under different conditions with its performance comparable to that of the centralized algorithm.This publication has 20 references indexed in Scilit:
- A New Approach for Time Synchronization in Wireless Sensor Networks: Pairwise Broadcast SynchronizationIEEE Transactions on Wireless Communications, 2008
- A Greedy Distributed Time Synchronization Algorithm for Wireless Sensor NetworksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2008
- Extension of Pairwise Broadcast Clock Synchronization for Multicluster Sensor NetworksEURASIP Journal on Advances in Signal Processing, 2007
- Global clock synchronization in sensor networksIEEE Transactions on Computers, 2006
- Clock synchronization for wireless sensor networks: a surveyAd Hoc Networks, 2005
- 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
- A posteriori agreement for fault-tolerant clock synchronization on broadcast networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Fine-grained network time synchronization using reference broadcastsACM SIGOPS Operating Systems Review, 2002