Distributed time synchronization from relative measurement in mobile wireless sensor networks

A wireless sensor network (WSN) consists of a set of devices (nodes) with sensing, data processing, and communicating components. They can monitor surrounding physical or environmental information, and collaborate to process such information. They have been used in a variety of applications, such as habitat and environment monitoring, health care, military surveillance, industrial machinery surveillance, home automation and so on. In many of those applications, nodes in sensor networks are mobile. Clock synchronization is critical for the effective use of sensor networks; particularly in applications such as range finding for target tracking and localization, intrusion detection, time correlation of telemetry data, sensor fusion, slot assignment in TDMA, duty cycling protocols, and so on. The problem of clock synchronization indeed has been widely investigated. Most algorithms are designed and tested in static networks, while little attention has been paid to that in mobile networks. In mobile networks, the communication links among networks varies frequently due to changes in inter-node distance and obstacles, which may affect the performance of algorithms designed for static networks.;At a given global time t, the local clock time at node u can be approximately written as tauu(t) = alphaut + betau, where alphau is the skew and betau is the offset. The global time to which all nodes need to be synchronized can be the local clock time at an arbitrarily chosen "reference" node. The time synchronization problem is effectively a problem of estimating the skews and offsets of every node, since the nodes can infer the global time from their local clock times once they know their own skew and offset estimates.;It is not possible for a node to measure its skew and offset directly. However, it is possible for a pair of neighbors to measure the noisy relative difference between their offsets and logarithm of skews by exchanging a number of time stamped messages. We show the existing protocols to perform so-called pairwise synchronization [1--5] can be used to obtain such relative measurements in Chapter 2. The focus of this work is how to achieve network-wide synchronization, i.e., estimate skews and offsets of clocks in nodes from these relative measurements. In Chapter 3 and Chapter 4, two different distributed algorithms are proposed, with which each node can estimate its offset/skew from these noisy relative measurements by communicating only with its neighbors. The algorithms are simple and easy to implement. The convergence of the two algorithms is guaranteed under certain conditions. They are also shown to be robust to measurement noise and time-varying network topologies. The first algorithm (JAT) was inspired by the existing Jacobi type of algorithms for skews and/or offsets estimation [6--10]. The algorithm ensures that the mean of estimation error converges to zero (if relative measurements are unbiased) and variance to a limiting value. The second algorithm (STO) was inspired by stochastic approximation type of consensus principles [11, 12]. It performs better than JAT algorithm in terms of the estimation of the global time as it ensures the variance of skew estimation error converges to zero. Furthermore, we also compare the two proposed algorithm with the state-of-the-art ATS algorithm [13] in terms of synchronization error that is the maximum absolute difference of time estimates of all pairs of nodes in networks. STO achieves better accuracy while its convergence rate is relatively slow. We then provide methods to improve the convergence rate and corresponding numerical validation.