Thesis Summary

CLOCK SYNCHRONIZATION

IN WIRELESS SENSOR NETWORKS

Kasım Sinan YILDIRIM

PhD. in Computer Engineering

Supervisor: Assoc. Prof. Dr. Aylin KANTARCI

12.04.2012

Sensor nodes in wireless sensor networks (WSNs) are equipped with cheap hardware clocks which frequently drift apart due to their low-end quartz crystals whose frequencies are not stable and vary over time. Environmental factors such as temperature changes result in short-term frequency instability and subtle effects such as oscillator aging result in long-term frequency instability. Hence, the hardware clocks of the nodes may not remain always synchronized although they might have been synchronized when they are started up.

Lack of synchronized time leads to inaccurate and inefficient operation of many applications and protocols in WSNs. For instance, sensor nodes need to access common time for time coordinated actions such as synchronous power on and shutdown of the communication circuit, which reduces energy consumption of the battery-powered sensor nodes. Therefore, a time synchronization protocol is required so that all nodes exchange their time information to synchronize their clocks for minimizing their synchronization error, i.e. clock skew.

A common strategy in order to achieve network-wide time synchronization is to flood current time information of a reference node into the network, which is utilized by the de facto time synchronization protocol Flooding Time Synchronization Protocol (FTSP). If synchronization to stable time sources such as Coordinated Universal Time (UTC) is required, employing the method of flooding in order to provide time synchronization also becomes crucial. In my PhD thesis, we firstly considered flooding based time synchronization and revealed the drawbacks of the existing synchronization schemes which are based on flooding. Within this context, my thesis presents the following two contributions for flooding based time synchronization in WSNs:

• •Drift Estimation Using Pairwise Slope With Minimum Variance In Wireless Sensor Networks 

   

  In flooding based time synchronization protocols, current time information of a reference node is periodically flooded into the network. Sensor nodes collect the time information of the reference node and perform least-squares regression in order to estimate the reference time. However, least-squares regression exhibits a poor performance since sensor nodes far away from the reference node collect the time information with large deviations. Due to this fact, the slopes of their least-squares line exhibit large errors and instabilities. As a consequence, the reference time estimates of these nodes also exhibit large errors. 

   

  In this study, we proposed a new slope estimation strategy for linear regression to be used by flooding based time synchronization protocols. The proposed method, namely Pairwise Slope With Minimum Variance (PSMV), calculates the slope of the estimated regression line by considering the pairwise slope between the earliest and the most recently collected data points. The PSMV slope is less affected by the large errors on the received data, i.e. it is more stable, and it is more computationally efficient when compared to the slope of the least-squares line. We incorporated PSMV into two flooding based time synchronization protocols, namely FTSP and PulseSync. Experimental results collected from a testbed setup including 20 sensor nodes showed that PSMV strategy improves the performance of FTSP by a factor of 4 and preserves the performance of PulseSync in terms of synchronization error with 40% less CPU overhead for linear regression. Our simulations showed that these results also hold for networks with larger diameters and densities.  

• •Time Synchronization Based On Slow Flooding in Wireless Sensor Networks 

   

  In FTSP, the propagation speed of the flood is slow since each node waits for a given period of time in order to propagate its time information about the reference node. It has been shown that slow-flooding decreases the synchronization accuracy and scalability of FTSP drastically. Alternatively, rapid-flooding approach is proposed in the literature, which allows nodes to propagate time information as quickly as possible. However, rapid flooding is difficult and has several drawbacks in wireless sensor networks.  

   

  In this study, our aim was to reduce the undesired effect of slow-flooding on the synchronization accuracy without changing the propagation speed of the flood. Within this context, we realized that the smaller the difference between the speeds of the clocks, the smaller the undesired effect of waiting times on the synchronization accuracy. In the light of this realization, our main contribution was to show that the synchronization accuracy and scalability of slow-flooding can drastically be improved by employing a clock speed agreement algorithm among the sensor nodes. We presented an evaluation of this strategy on a testbed setup including 20 MICAz sensor nodes. Our theoretical findings and experimental results showed that employing a clock speed agreement algorithm among the sensor nodes drastically improves the synchronization accuracy and scalability of slow-flooding.  

While studying flooding based time synchronization protocols, we revealed that the least-squares mechanism employed by these protocols may set the clocks of the nodes back. Hence, my thesis revealed this important problem as a contribution to the time synchronization research:

• •Time Synchronization Without Setting Clocks Back in Wireless Sensor Networks 

   

  The clocks of the nodes are assumed to be monotonically increasing functions by most of the theoretical distributed clock synchronization studies. In this study, we revealed that some time synchronization protocols in wireless sensor networks do not obey this assumption in practice. The reason is that these protocols employ the method of least-squares, which may set the clocks of the nodes back. We showed that FTSP, which is de facto time synchronization protocol in wireless sensor networks, suffers from this shortcoming. In order to preserve the monotonicity of the clocks, we proposed a simple solution and integrate it to the publicly available implementation of FTSP. Our experimental results on a real sensor platform and simulations show that the proposed strategy prevents clocks from being set back with a reasonable increase on the synchronization error.  

Flooding based synchronization schemes may poorly  synchronize neighboring nodes. Hence, another perspective in time synchronization in WSNs is to provide tight synchronization among the neighboring nodes, namely gradient clock synchronization. However, we revealed that there is a lack in the literature of a gradient time synchronization protocol  which can provide external clock synchronization. Within this context, my thesis presented the first external gradient time synchronization protocol in the WSN literature:

• •External Gradient Time Synchronization In Wireless Sensor Networks 

   

  Synchronization to an external time source such as Coordinated Universal Time (UTC), i.e. external synchronization, while preserving tight synchronization among neighboring sensor nodes may be crucial for applications such as determining the speed of a moving object in wireless sensor networks. However, existing time synchronization protocols in the literature which can be used for external synchronization poorly synchronize neighboring nodes. On the other hand, the only protocol which aims at optimizing the synchronization error between neighboring nodes is lack of a mechanism which synchronizes sensor nodes to a reference node and hence it cannot provide external synchronization. Therefore, there is a lack in the literature of a time synchronization protocol which can be used by applications demanding both external synchronization and tight synchronization among neighboring nodes.  

  In this study, we answered the question of whether it is possible for sensor nodes to synchronize to a reference node while they optimize the clock skew between their neighboring nodes at the same time. Within this context, we presented a novel time synchronization protocol, namely External Gradient Clock Synchronization Protocol (EGSync). In EGSync, each sensor node synchronizes to a reference node by using time information flooded by this node as well as synchronizes to its neighboring nodes by employing the agreement algorithm. We implemented EGSync on the MICAz platform using TinyOS and evaluated it on a testbed setup including 20 sensor nodes. We presented the experimental results on our testbed and the simulation results for networks with larger diameters. 

Apart from the practical side of the gradient clock synchronization, there are several theoretical studies which propose theoretical gradient clock synchronization algorithms. We  studied these algorithms and revealed that the CPU overhead of the optimal gradient clock synchronization algorithms in the literature can be reduced. As a last contribution of my thesis, we presented  a new optimal gradient clock synchronization algorithm which is more efficient in terms of CPU consumption:

• •On Decreasing The Computational Overhead Of Optimal Gradient Clock Synchronization In Distributed Systems 

   

  A particular synchronization scheme in distributed systems is gradient clock synchronization which requires neighboring nodes to be more tightly synchronized than far away nodes. There are gradient clock synchronization algorithms in the literature which are optimal in terms of worst-case clock skew between neighboring nodes. However, these optimal algorithms require a search operation to be performed quite frequently in order to decide the speed of clocks and this requirement increases their computational overhead. We showed that optimal gradient clock synchronization can be achieved with a lower overhead in terms of computation. Within this context, we presented a new optimal gradient clock synchronization algorithm which determines the speed of the clocks by performing simple arithmetic operations.