Time Synchronization for Random Mobile Sensor Networks

Mobile sensor nodes have a wide spectrum of applications, such as social networks and habitat monitoring. Time synchronization is a critical issue for most applications using mobile sensor networks. However, due to the limited communication range, mobile sensor nodes can only exchange their information when they are sufficiently close for contact. Moreover, random movements of the nodes render the performance analysis of any time synchronization protocols challenging. In this paper, we introduce the relation graph for modeling the random contact of mobile sensor nodes and evaluate the probability that the network can be synchronized within an arbitrary time. We adapt the previous maximum time synchronization (MTS) protocol, which can drive the clocks of all sensor nodes to a common value by utilizing their own neighboring information. We provide an analytical lower bound of the probability that the time synchronization can be finished within any given time. The obtained theories and algorithms are applied for several fundamental problems, and it is proven that a better connectivity is beneficial for convergence. For linearizable graph, we provide an efficient way to calculate the exact probabilities. Extensive numerical examples demonstrate the effectiveness of our results.