This paper proposes a novel distributed time synchronization scheme for wireless sensor networks, which uses max consensus to compensate for clock drift and average consensus to compensate for clock offset. The main idea is to achieve a global synchronization just using local information. The proposed protocol has the advantage of being totally distributed, asynchronous, and robust to packet drop and sensor node failure. Finally, the protocol has been implemented in MATLAB. Through several simulations, we can see that this protocol can reduce clock error to ±10 ticks, adapt to dynamic topology, and be suitable to large-scale applications.
As in all distributed systems, time synchronization is very important in wireless sensor networks (WSNs) since the design of many protocols and implementation of applications require precise time, for example, forming an energy-efficient radio schedule, conducting in-network processing (data fusion, data suppression, data reduction, etc.), distributing an acoustic beamforming array, performing acoustic ranging (i.e., measuring the time of flight of sound), logging causal events during system debugging, and querying a distributed database.
Time synchronization is a research area with a very long history. Various mechanisms and algorithms have been proposed and extensively used over the past few decades. However, several unique characteristics of WSNs often preclude the use of the existing synchronization techniques in this domain. First, since the amount of energy available to battery-powered sensors is quite limited, time synchronization must be implemented in an energy-efficient way. Second, some messages need to be exchanged for achieving synchronization while limited bandwidth of wireless communication discourages frequent message exchanges among sensor nodes. Third, the small size of a sensor node imposes restrictions on computational power and storage space. Therefore, traditional synchronization schemes such as network time protocol (NTP) and global positioning system (GPS) are not suitable for WSNs because of complexity and energy issues, cost efficiency, limited size, and so on.
In the context of WSNs, time synchronization refers to the problem of synchronizing clocks across a set of sensor nodes that are connected to one another over a single-hop or multihop wireless networks. To achieve time synchronization in wireless sensor networks, we have to face the following four challenges.
1.1. Nondeterministic Delays
There are many sources of message delivery delays. Kopetz and Ochsenreiter  describe the components of message latency, which they call the Reading Error, as being comprised of 4 distinct components plus the local granularity of the nodes clocks. Their work was later expanded by  to include transmission and reception time. The most nondeterministic delay is called Access Time, which is incurred in the MAC layer waiting for access to the transmit channel, its orders of magnitude is larger than the synchronization precision required by the network.
1.2. Clock Drift
Manufacturers of crystal oscillators specify a tolerance value in parts per million (PPM) relative the nominal frequency at 25°C, which determines the maximum amount that the skew rate will deviate from 1. For the nodes used in WSNs, the tolerance value is typically in the order of 5 to 20 PPM. If no drift compensation applied, two synchronized nodes will be out of step soon.
Since sensor networks are often left unattended for long periods of time in possibly hostile environments, synchronization schemes should be robust against link and node failures. Mobile nodes can also disrupt routing schemes, and network partitioning may occur.
1.4. Convergence Speed
Nodes in wireless sensor networks always distribute in large scales, one node may get in touch with another by many hops. This increases the difficulty in reducing the convergence speed in time synchronization algorithm design.
Up to now, many protocols have been designed to address this problem. These protocols all have some basic features in common: a simple connectionless messaging protocol, exchange of clock information among nodes, mitigating the effect of nondeterministic factors in message delivery, and processing utilizing different schemes and algorithms, respectively. They can be classified into two types: centralized synchronization and distributed synchronization.
Centralized synchronization protocol, such as RBS , TPSN , and FTSP , usually has fast convergence speed and little synchronization error. This kind of protocol needs a physical node acting as the whole network’s reference clock, so it has to divide the nodes into different roles, for example, client node and beacon node in RBS. If the node with the special role, such as beacon node in RBS, is out of work, the protocol will suffer from big damage. To deal with the WSNs’ dynamic topology, centralized synchronization protocol is often designed with complexity logic. Another disadvantage of centralized synchronization protocol is that synchronization error grows with the increase of network hops.
Distributed synchronization protocol, such as TDP /GCS /RFA /ATS /CCS , can use local information to achieve the whole network synchronization. This kind of protocol can easily adapt to WSNs’ dynamic topology property with lite computation. Currently, the disadvantage of distributed synchronization protocol is that the convergence speed may be a bit slow, relating to the network topology.
This paper describes a new distributed protocol for time synchronization in wireless sensor networks called time synchronization using max and average consensus protocol (TSMA). We adapt a number of techniques to take up the challenges time synchronization has in WSNs. To eliminate the nondeterministic delays, we make use of MAC layer timestamp technique. To compensate for the clock drift, we adapt max consensus protocol, and we use average consensus protocol to compensate for the clock offset. This protocol has the advantages of being computationally light, scalable, asynchronous, robust to node and link failure, and it does not require a master or controlling node.
The rest of the paper is organized as follows. Section 2 summarizes the related work. Section 3 introduces some mathematical tools and definitions that will be instrumental for the proof of convergence of the proposed TSMA algorithm. Section 4 introduces a model for the clock dynamics and formally defines the synchronization objectives, while Section 5 presents the TSMA algorithm in details. This is followed by MATLAB simulations in Section 6. Finally, Section 7 briefly summarizes the results obtained and proposes potential research directions.
function varargout=prowler(command, varargin)
% prowler - PROBABILISTIC WIRELESS NETWORK SIMULATOR - Main simulation program
% Command line options:
% initialize: prowler('Init')
% simulate: prowler('StartSimulation')
% A graphical user interface can be invoked by typing prowler.
% See also: radio_channel, sim_params, demo_application, simstats, demo_opt
% *** Copyright 2002, Vanderbilt University. All rights reserved.
% *** This program is distributed in the hope that it will be useful,
% *** but WITHOUT ANY WARRANTY; without even the implied warranty of
% *** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
% Written by Gyula Simon, firstname.lastname@example.org