Clock Synchronization for Multi-hop Ad hoc Networks

Abstract

Clock syncronization is one of the basic requirements of a distributed real-time systems. The greater the precision achievable by the clock synchronization algorithm used, the harder the real-time guarantees that can be given by the system. Numerous clock synchronization algoritms for wired networks have been proposed, which provide varying degrees of precision.

Wireless networks provide a number of challenges which clock synchronization algorithms for wired networks do not address satisfactorily. Dynamic network topology and the existence of multi-hop neighbours, as well as high message loss make wired clock synchronization algoritms unsuited to the wireless environment.

This work presents a clock synchronization algorithm for multi-hop ad hoc networks, which improves on the precision achievable by other such algorithms while minimising the prerequisites of the algorithm. Unlike other algorithms which provide clock synchronization in wireless networks, this algorithm does not require a centralised master node, or predefined slots in which nodes can broadcast their synchronization messages. It utilises the tightness property of the wireless medium, whereby message receipt occurs at the same physical instant across all recipients. The problem of multi-hop synchronization is addressed by using local averaging at overlapping subsets of the nodes to achieve global synchronization.

A theoretical bound on the achievable precision for one-hop synchronization has been calculated. This bound applies in the absence of lost messages and network partitions, with the precision returning belwo the bound upon merging the partitions. The upper bound on precision for one-hop synchronization extends to n times the bound for n-hop synchronization in a multi-hop network. The operation of the algoritm has been simulated to verify this bound.