In this chapter, we review time synchronization and calibration for wireless sensor networks. We will first consider time synchronization in Sections 1.1-1.6, before turning to calibration in Section 1.7. We will show that time synchronization can be considered as a calibration problem and many observations about time synchronization can be transferred to calibration. In Section 1.1, we discuss applications of synchronized time in sensor networks, present challenges of sensor networks, and discuss why traditional synchronization approaches fail to meet these challenges. Section 1.2 presents models of sensor nodes, of hardware clocks, and of communication. Section 1.3 gives an overview of the various classes of synchronization. In Section 1.4, we present common synchronization techniques. Section 1.5 examines current synchronization algorithms. Section 1.6 presents common techniques for evaluating synchronization algorithms and selected evaluation results. Sensor networks are used to monitor real-world phenomena. For such monitoring applications, physical time often plays a crucial role. We will discuss these applications of time in Section 1.1.1. Providing synchronized physical time is a complex task due to various challenging characteristics of sensor networks. In Section 1.1.2, we present these challenges and discuss why synchronization algorithms for traditional distributed systems often do not meet these challenges.  Physical time plays a crucial role for many sensor-network applications. While many traditional applications of time also apply to sensor networks, we will focus here on areas specific to sensor networks. Figure 1 .1 illustrates a rough classification of applications of physical time: (a) at the interface between the sensor network and an external observer, (b) among the nodes of the sensor network, and (c) at the interface between the sensor network and the observed physical world. The following paragraphs will discuss applications of time in these three domains. Note that some applications are hard to assign to a single domain. In such cases, we picked the most appropriate domain. Sensor network -observer In many applications, a sensor network interfaces to an external observer for tasking, reporting results, and management. This observer may be a human operator or an autonomous computing system. Tasking a sensor network often involves the specification of time windows of interest such as "only during the night". As a sensor network reports observation results to an external observer, temporal properties of observed physical phenomena may be of interest. For example, the times of occurrence of physical events are often crucial for the observer to associate event reports with the originating physical events. Physical time is also crucial for determining properties such as speed or acceleration. Sensor network -real world In sensor networks, many sensor nodes may observe a single physical phenomenon. One of the key functions of a sensor network is hence the assembly of those distributed observations into a coherent estimate of the original phenomenon -this process is known as data fusion. Time is a key ingredient for data fusion. For example, if sensors can only detect the proximity of an object, then higher-level information (such as speed, size, or shape) can be obtained by correlating data from multiple sensor nodes. The velocity of a mobile object, for example, can be estimated by the quotient of the spatial and temporal distances between two consecutive sightings of the object by different sensor nodes. Since many instances of a physical phenomenon can occur within a short time, one of the tasks of a sensor network is the separation of sensor samples, that is INTRODUCTION iii the partitioning of sensor samples into groups that each represent a single physical phenomenon. Temporal relationships (e.g., distance) among sensor samples are a key element for separation. Temporal coordination among sensor nodes may also be necessary to ensure correctness and consistency of distributed measurements [11] . For example, if the sampling rate of sensors is low compared to the frequency of an observed phenomenon, it may be necessary to ensure that sensor readout occurs concurrently at all sensor nodes in order to avoid false observation results (e.g., for calibration, see Section 1.7.5.2). It is anticipated that large-scale, complex actuation functions will be implemented by coordinated use of many simple actuator nodes. This requires temporal coordination. Within sensor network Time is also a valuable tool for intra-network coordination among different sensor nodes. Many applications of time known from traditional distributed systems also apply to wireless sensor networks. [17] points out a number of applications of time in distributed systems such as concurrency control (e.g., atomicity, mutual exclusion), security (e.g., authentication), data consistency (e.g., cache consistency, consistency of replicated data), and communication protocols (e.g., atmost-once message delivery). One particularly important example for concurrency control is the use of timedivision multiplexing in wireless communication, where multiple access to the shared communication medium is typically achieved by assigning time slots to the communicating nodes. This requires the participating sensor nodes to share a common view of physical time. A number of approaches intend to improve energy efficiency by frequently switching sensor nodes or components thereof into power-saving sleep modes (e.g., [35] ). In order to nonetheless ensure seamless operation of the sensor network, temporal coordination of the sleep periods among sensor nodes may be required. Another important service for sensor-network applications is temporal message ordering (e.g., [28] ). Many data-fusion algorithms have to process sensor readings ordered by the time of occurrence (e.g., the approach for velocity estimation sketched above). However, the highly variable message delays in sensor networks imply that messages from distributed sensor nodes may often not arrive at a receiver in the order in which they were sent. Reordering messages according to the time of sensor readout requires temporal coordination among sensor nodes. Methods for localization of sensor nodes based on the measurement of time of flight or difference of arrival time of certain signals do also require synchronized time (e.g., [13] ). Time synchronization is a research area with a very long history. Over time, numerous algorithms have been proposed and have been in large-scale use. The Network Time Protocol (NTP) [21] is perhaps one of the most advanced and time-tested sysiv tems. However, several unique characteristics of sensor networks often preclude the use of existing synchronization techniques in this domain. In the following, we discuss sensor-network challenges that impact the design of time-synchronization approaches. Using NTP as an example, we will outline why traditional approaches often do not meet the requirements of sensor networks (see also [9] ). Note that some of the illustrated shortcomings of NTP are relatively easy to fix, while others are not. To provide the necessary background, we will first give an overview of NTP. NTP was designed for large-scale networks with a rather static topology (such as the Internet). Nodes are externally synchronized to a global reference time that is injected into the network at many places via a set of master nodes (so-called "stratum 1" servers). These master nodes are synchronized out of band, for example via GPS (which provides global time with a precision significantly below 1 µs). Nodes participating in NTP form a hierarchy: leaf nodes are called clients, inner nodes are called stratum L servers, where L is the level of the node in the hierarchy. The parents of each node must be specified in configuration files at each node. Nodes frequently exchange synchronization messages with their parents and use the obtained information to adjust their clocks by regularly incrementing them. Energy and other resources Sensor-network applications often require sensor nodes to be small and cheap. This has a number of important implications. First of all, the amount of energy that can be stored in or scavenged by small devices is typically very limited due to the low energy density of available and foreseeable technology. To ensure longevity despite this limited energy budget, energy-efficient design both in hardware and software becomes a dominating goal. Additionally, computing, storage, and communication capabilities of individual sensor nodes are rather limited due to size and energy constraints. These constraints may preclude the use of GPS or other technologies for out-ofband synchronization of NTP master nodes. NTP is also not optimized for energy efficiency, simply because this is not an issue in infrastructure-based distributed systems. Energy overhead in NTP results from several sources. Firstly, the service provided by NTP typically cannot be dynamically adapted to the varying needs of an application. Hence, with NTP all nodes would be continuously synchronized with maximum precision, even though only subsets of nodes might occasionally need synchronized time with less-than-maximum precision. Secondly, NTP uses the processor and the network in ways that would lead to significant overhead in energy expenditure in sensor networks. For example, NTP maintains a synchronized system clock by regularly adding small increments to the system-clock counter. This behavior precludes the processor from being switched to a power-saving idle mode. In addition, NTP servers must be prepared to receive synchronization requests at any point in time. However, constantly listening is an energywise costly operation in sensor networks; many sensor-network protocols therefore switch off the radio whenever possible.
An in-depth survey on time synchronization in WSNs can be found in REF .
Time Synchronization and Calibration in Wireless Sensor Networks
Handbook of Sensor Networks
Computer Science