A scalable framework for distributed time synchronization in multi-hop sensor networks
Ossama Mohamed Younis, Sonia Fahmy · 2005
Abstract — Time synchronization is essential for several ad-hoc network protocols and applications, such as TDMA scheduling and data aggregation. In this paper, we propose a clusteringbased time synchronization framework for multi-hop sensor networks. We assume that relative node synchronization is sufficient, i.e., consensus on one time value is not required. Our goal is to divide the network into connected synchronization regions (nodes within 2-hops) and perform inter-regional synchronization in O(LLSync) × Niter time, where O(LLSync) denotes the complexity of the underlying low-level synchronization technique (used for single hop synchronization), and Niter denotes the number of iterations where the low-level synchronization protocol is invoked. We propose two novel fully-distributed protocols, SYNC-IN and SYNC-NET, for regional and network synchronization, respectively, and prove that Niter is O(1) for both protocols. We exploit the tradeoff between rapid convergence (and consequently energy-efficiency) and perceived accuracy. Our framework does not require any special node capabilities (e.g., being GPS-enabled), or the presence of reference nodes in the network. Our framework is also independent of the particular clustering, inter-cluster routing, and low-level synchronization protocols. We formulate a density model for analyzing interregional synchronization, and evaluate our protocols via extensive simulations. Index Terms — Sensor networks, time synchronization, node clustering I.