Internal Synchronization of Drift-Constraint Clocks in Ad-Hoc Sensor Networks

Clock synchronization is a crucial basic service in typical sensor networks, since the observations of distributed sensors more often than not need to be ordered ("a happened before b") or otherwise related ("a and b happened within a time window of size x") in time. Ad-hoc networks may exhibit characteristics which make the use of traditional clock-synchronization algorithms infeasible. Recently, algorithms suitable for ad-hoc networks have been presented. We first propose an improvement to an existing algorithm. While needing less computation and no more communication or memory than the original algorithm, our new algorithm always yields equal or better results and thus outperforms the original algorithm. We then examine how even better synchronization can be obtained, possibly at the cost of additional computation, communication, and memory. To this end, we introduce a model for internal synchronization. This model allows us to find an algorithm which makes use of all the data a node can obtain from the network for a given communication pattern and thus provides optimal synchronization in our model