Time synchronization is an important aspect of sensor network operation. However, it is well known that synchro- nization error accumulates over multiple hops. This presents a challenge for large-scale, multi-hop sensor networks with a large number of nodes distributed over wide areas. In this work, we present a protocol that uses spatial averaging to reduce error accumulation in large-scale networks. We provide an analysis to quantify the synchronization improvement achieved using spatial averaging and find that in a basic cooperative network, the skew and offset variance decrease approximately as 1 ¯ N where ¯ N is the number of cooperating nodes. For general networks, simulation results and a comparison to basic cooperative network results are used to illustrate the improvement in synchronization performance.
The traditional synchronization techniques describe in @cite_11 @cite_13 @cite_1 @cite_4 @cite_10 all operate fundamentally on the idea of communicating timing information from one set of nodes to the next. One other approach to synchronization that has recently received much attention is to apply mathematical models of natural phenomena to engineered networks. A model for the emergence of synchrony in pulse-coupled oscillators was developed in @cite_14 for a fully-connected group of identical oscillators. @cite_5 , this convergence to synchrony result was extended to networks that were not fully connected.
@cite_13 @cite_14 @cite_4 @cite_1 @cite_5 @cite_10 @cite_11
2058455332 1116550701 2234682834 1520594164
Solutions for time synchronization based on coupled oscillators operate in a self-organizing and adaptive manner and can be applied to various types of dynamic networks. The basic idea was inspired by swarms of fireflies, whose flashing dynamics shows an emergent behavior. This article introduces such a synchronization technique whose main components are “inhibitory coupling” and “self-adjustment.” Based on this new technique, a number of contributions are made. First, we prove that inhibitory coupling can lead to perfect synchrony independent of initial conditions for delay-free environments and homogeneous oscillators. Second, relaxing the assumptions to systems with delays and different phase rates, we prove that such systems synchronize up to a certain precision bound. We derive this bound assuming inhomogeneous delays and show by simulations that it gives a good estimate in strongly-coupled systems. Third, we show that inhibitory coupling with self-adjustment quickly leads to synchrony with a precision comparable to that of excitatory coupling. Fourth, we analyze the robustness against faulty members performing incorrect coupling. While the specific precision-loss encountered by such disturbances depends on system parameters, the system always regains synchrony for the investigated scenarios. People have always tried to understand natural phenomena. In computer science natural phenomena are mostly used as a source of inspiration for solving various problems in distributed systems such as optimization, clustering, and data processing. In this paper we will give an overview of research in field of computer science where fireflies in nature are used as role models for time synchronization. We will compare two models of oscillators that explain firefly synchronization along with other phenomena of synchrony in nature (e.g., synchronization of pacemaker cells of the heart and synchronization of neuron networks of the circadian pacemaker). Afterwards, we will present Mirollo and Strogatz's pulse coupled oscillator model together with its limitations. As discussed by the authors of the model, this model lacks of explanation what happens when oscillators are nonidentical. It also does not support mobile and faulty oscillators. Finally, it does not take into consideration that in communication among oscillators there are communication delays. Since these limitations prevent Mirollo and Strogatz's model to be used in real-world environments (such as Machine-to-Machine systems), we will sum up related work in which scholars investigated how to modify the model in order for it to be applicable in distributed systems. However, one has to bear in mind that there are usually large differences between mathematical models in theory and their implementation in practice. Therefore, we give an overview of both mathematical models and mechanisms in distributed systems that were designed after them. The convergence and precision of synchronization algorithms based on the theory of pulse-coupled oscillators is evaluated on programmable radios. Measurements in different wireless topologies show that such algorithms reach precisions in the low microsecond range. Based on the observation that phase rate deviation among radios is a limiting factor for the achievable precision, we propose a distributed algorithm for automatic phase rate equalization and show by experiments that an improved precision below one microsecond is possible in the given setups. It is also experimentally demonstrated that the stochastic nature of coupling is a key ingredient for convergence to synchrony. The proposed scheme can be applied in wireless systems for distributed synchronization of transmission slots, or sleep cycles. Consider a distributed network of n nodes that is connected to a global source of "beats". All nodes receive the "beats" simultaneously, and operate in lock-step. A scheme that produces a "pulse" every Cycle beats is shown. That is, the nodes agree on "special beats", which are spaced Cycle beats apart. Given such a scheme, a clock synchronization algorithm is built. The "pulsing" scheme is self-stabilized despite any transient faults and the continuous presence of up to f < n 3 Byzantine nodes. Therefore, the clock synchronization built on top of the "pulse" is highly fault tolerant. In addition, a highly fault tolerant general stabilizer algorithm is constructed on top of the "pulse" mechanism. Previous clock synchronization solutions, operating in the exact same model as this one, either support f < n 4 and converge in linear time, or support f < n 3 and have exponential convergence time that also depends on the value of max-clock (the clock wrap around value). The proposed scheme combines the best of both worlds: it converges in linear time that is independent of max-clock and is tolerant to up to f < n 3 Byzantine nodes. Moreover, considering problems in a self-stabilizing, Byzantine tolerant environment that require nodes to know the global state (clock synchronization, token circulation, agreement, etc.), the work presented here is the first protocol to operate in a network that is not fully connected.