Scalable synchronization of clocks in wireless sensor networks

In many sensor-based applications, identifying the sequence of event occurrence is useful. When local clocks lack synchronizations, it is difficult or time-consuming to determine the order of event occurrence. In this paper, we first describe a centralized method for pseudo-synchronizing non-base clocks to a base clock. The pseudo-shift between a pair of non-base/base clocks is estimated by the difference of the occurrence times of pairs of events included in direct "happened-before" relations that only involve this pair of sensors. Evaluation results suggest that this method can closely make non-base clocks synchronized with a base clock without violating the direct "happened-before" relations. The centralized pseudo-synchronization method demands a O(N-3) computational overhead on the base sensor in a network of N sensors. Then, in order to distribute the computational overhead across all sensors, a localized pseudo-synchronization method is proposed by taking advantage of the topologies of wireless sensor networks. (C) 2007 Elsevier B.V. All rights reserved.