Interval-Based Time Synchronization for Mobile Ad-Hoc Networks

In this thesis, we make a case for the use of guaranteed intervals for time synchronization in mobile ad-hoc networks. In particular, we look at wireless sensor networks (WSNs), a specific class of mobile ad-hoc networks. WSNs are envisioned to comprise a large number of small, inexpensive devices that operate on a very constrained energy budget. Time synchronization is an important service in WSNs. Approaches developed in the distributed-systems field typically cannot be applied directly because of the limiting characteristics of WSNs: (a) There is no guarantee of stable connectivity between nodes. (b) Energy is a very scarce resource. Communication, which is needed to achieve and maintain synchronization, is expensive in terms of energy and hence has to be kept short. (c) Communication bandwidth is limited. (d) There is no a-priori configuration or infrastructure. In particular, there are few or even no reference clocks available. In this thesis, we make a number of contributions to the state of the art in the field of time synchronization for mobile ad-hoc networks. Our main claim is that interval-based time synchronization is particularly suited for these networks. Specifically, our contributions are the following: We present a new system model for the analysis of interval-based time synchronization in mobile ad-hoc networks. We justify why our abstractions are well chosen for this class of networks. Using our system model, we derive worst-case bounds on the quality of interval-based synchronization and show the worst-case-optimality of a very simple algorithm. The simple, worst-case-optimal algorithm is not optimal in the average case. We present three algorithms that are also worst-case-optimal but achieve better synchronization quality in the average case.We show that two of the algorithms achieve optimal synchronization, albeit at the cost of high memory and communication overhead. We describe how limiting the amount of data that is stored and communicated affects the synchronization quality. We show that interval-based synchronization does not need particular communication patterns such as trees or clustered hierarchies. Hence, interval-based synchronization is resilient to mobility; our simulation results show that mobility actually improves it. Finally, we derive a lower bound on the error of gradient clock synchronization in our system model.