| Abstract: |
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. |
