Low-energy time synchronization in sensor networks


Time synchronization is critical in many sensornet tasks such as object tracking, surveillance, duplicate detection, power-saving
duty cycling, or distributed beam-forming. It plays a crucial role also in data integration and in TDMA medium access scheduling for
low-energy radio operation. All of these applications explain the great deal of attention to the clock synchronization problem in
sensor networks, and the large volume of work appeared in the last few years.

We have studied the time synchronization problem from a novel perspective which is complementary to the well--studied clock synchronization problem [1,2]. More precisely, we analyze the case in which a sensor node decides to skip one or more clock adjustments to save energy, or it is temporarily isolated, but still requires an accurate estimate of the time. This approach is particularly convenient in long-lived sensor applications such as environmental monitoring applications. Our goal is to improve the accuracy of the clock between synchronization, based on the behavior of the hardware clock since the initialization time. We propose a suit of deterministic and probabilistic algorithms that are provably correct, to improve the time estimate between synchronization.
Our probabilistic clock reading method is based on AR time series models. It returns a time estimate within a tunable error bound and error probability. This method is highly adaptable and allows the sensor to decide how many clock adjustments it can skip within a maximum error bound while maintaining the same time accuracy, thus saving energy. We also propose a deterministic clock reading method that exploits information regarding the sign of the clock deviation and that can be applied to reduce the frequency of the periodic clock adjustments by a factor of 2, while maintaining the same error bound. This method is of both practical and theoretical interest. In fact, it leads to a noticeable energy saving, and shows that a stronger but realistic clock model
can lead to a refinement of the optimality bound for the maximum deviation of a clock that is periodically synchronized. We also propose extensions of this method that improve the clock
accuracy under stronger but realistic conditions.

 [1]  D. Tulone. On the feasibility of global time estimation under isolation conditions in wireless sensor networks.
To appear in Algorithmica.

[2] D. Tulone. A resource-efficient time estimation for wireless sensor networks. In Proc. of the 4th Workshop of Principles of Mobile Computing, pp. 52-59, Oct 2004.