## 1 Introduction  
A wireless sensor network (WSN) is a group of spatially-distributed autonomous sensors, which monitor physical or environmental conditions, such as temperature, humidity, speed, pressure, _etc._, and then transmit the recorded data to a central computing unit for analysis. WSNs originate from military-oriented applications, such as battlefield surveillance and movement monitoring. Nowadays, WSNs have witnessed a rapid growth and have been implemented in a variety of promising applications, which can be classified as follows:  
* Military [1]: battlefield surveillance; forces monitoring; battle damage assessment. * Health [2,3]: tracking and monitoring patients; telemonitoring of human physiological data. * Environment [4,5]: air pollution monitoring; water quality monitoring; forest fire detection. * Home [6,7]: home automation; home appliances management and monitoring. * Industry [8]: machine health monitoring; waste monitoring; data logging. Most of these applications require the clocks of network nodes to be synchronized, because performing a joint task requires all of the nodes to operate on a common time scale. For instance, data logging is a basic operation that collects, processes and transmits data and is used for temporal and spatial monitoring of a habitat. The advantage of data logging in WSNs over the conventional data logging lies in the property of real-time data being collected, which requires some or all nodes in the network to share a common time frame. Each sensor in a WSN operates independently and has its own clock. Even if the clocks of sensors are initially tuned perfectly, due to the imperfections of the clock oscillator, they may drift away from the ideal time as time evolves [9]. Hence, developing efficient clock synchronization protocols is critical in WSNs. In the literature, many clock synchronization algorithms rely on the clock information from the Global Positioning System (GPS). However, GPS is not ubiquitously available and requires a high-power receiver [10]. This fact makes it impractical to implement GPS technology in the clock synchronization of WSNs, since WSNs generally consist of small sensors that have limited energy. Furthermore, sensors sometimes are positioned in an environment where the GPS signal is not available, as is the case with underwater or underground sensors for water quality monitoring. For clock synchronization applications in computer networks, the network time protocol (NTP) represents one of the oldest and standard Internet timing protocols in current use [11]. However, NTP is still not suitable for WSNs, due to the lack of energy availability and unstable working environment in WSNs. Therefore, a variety of synchronization protocols have been particularly designed for WSNs. In general, these protocols perform clock synchronization via timing message exchanges among sensors. However, due to the power requirement for each individual sensor, sensors have a limited communication range, and they are not able to communicate with every other sensor. An example of a WSN with nine sensors is shown in Figure 0(a), where each circle denotes a sensor and each edge represents the communication link (if present) between the corresponding pair of sensors. Traditional synchronization protocols for WSNs generally include two steps: first, the synchronization is conducted within a pair of neighboring nodes; second, a multi-hop structure is built, such that the synchronization can be extended into all of the nodes through a layer-by-layer synchronization. One natural approach to deal with the multi-hop structure of WSNs is to construct a tree-based network. Specifically, as illustrated in Figure 0(b), a sensor is selected as the reference node, then a spanning tree rooted at this node is built, and each sensor synchronizes with its parent pairwisely along the unique path from that sensor to the root. On the other hand, the cluster-based structure divides the network into several interconnected single-hop clusters, as graphically shown in Figure 0(c).