An Overview of a Class of Clock Synchronization Algorithms for Wireless Sensor Networks: A Statistical Signal Processing Perspective
---
paper_title: Component-Based Software Systems for Smart Environments

paper_content:

The article focuses on the role component-based software may play in realizing smart environments. A scenario describes a future smart environment in a university campus setting. The scenario illustrates how software components might contribute to the various phases of development, deployment and use of smart environments. Key research areas identified include: development of component frameworks, component interface standards, addressing schemes, and protocols.
---
paper_title: Wireless sensor networks for habitat monitoring

paper_content:

We provide an in-depth study of applying wireless sensor networks to real-world habitat monitoring. A set of system design requirements are developed that cover the hardware design of the nodes, the design of the sensor network, and the capabilities for remote data access and management. A system architecture is proposed to address these requirements for habitat monitoring in general, and an instance of the architecture for monitoring seabird nesting environment and behavior is presented. The currently deployed network consists of 32 nodes on a small island off the coast of Maine streaming useful live data onto the web. The application-driven design exercise serves to identify important areas of further work in data sampling, communications, network retasking, and health monitoring.
---
paper_title: The flooding time synchronization protocol

paper_content:

Wireless sensor network applications, similarly to other distributed systems, often require a scalable time synchronization service enabling data consistency and coordination. This paper describes the Flooding Time Synchronization Protocol (FTSP), especially tailored for applications requiring stringent precision on resource limited wireless platforms. The proposed time synchronization protocol uses low communication bandwidth and it is robust against node and link failures. The FTSP achieves its robustness by utilizing periodic flooding of synchronization messages, and implicit dynamic topology update. The unique high precision performance is reached by utilizing MAC-layer time-stamping and comprehensive error compensation including clock skew estimation. The sources of delays and uncertainties in message transmission are analyzed in detail and techniques are presented to mitigate their effects. The FTSP was implemented on the Berkeley Mica2 platform and evaluated in a 60-node, multi-hop setup. The average per-hop synchronization error was in the one microsecond range, which is markedly better than that of the existing RBS and TPSN algorithms.
---
paper_title: Wireless sensor networks for healthcare: A survey

paper_content:

Becoming mature enough to be used for improving the quality of life, wireless sensor network technologies are considered as one of the key research areas in computer science and healthcare application industries. The pervasive healthcare systems provide rich contextual information and alerting mechanisms against odd conditions with continuous monitoring. This minimizes the need for caregivers and helps the chronically ill and elderly to survive an independent life, besides provides quality care for the babies and little children whose both parents have to work. Although having significant benefits, the area has still major challenges which are investigated in this paper. We provide several state of the art examples together with the design considerations like unobtrusiveness, scalability, energy efficiency, security and also provide a comprehensive analysis of the benefits and challenges of these systems.
---
paper_title: Internet time synchronization: The Network Time Protocol

paper_content:

The network time protocol (NTP), which is designed to distribute time information in a large, diverse system, is described. It uses a symmetric architecture in which a distributed subnet of time servers operating in a self-organizing, hierarchical configuration synchronizes local clocks within the subnet and to national time standards via wire, radio, or calibrated atomic clock. The servers can also redistribute time information within a network via local routing algorithms and time daemons. The NTP synchronization system, which has been in regular operation in the Internet for the last several years, is described, along with performance data which show that timekeeping accuracy throughout most portions of the Internet can be ordinarily maintained to within a few milliseconds, even in cases of failure or disruption of clocks, time servers, or networks. >
---
paper_title: Lightweight time synchronization for sensor networks

paper_content:

This paper presents lightweight tree-based synchronization (LTS) methods for sensor networks. First, a single-hop, pair-wise synchronization scheme is analyzed. This scheme requires the exchange of only three messages and has Gaussian error properties. The single-hop approach is extended to a centralized multi-hop synchronization method. Multi-hop synchronization consists of pair-wise synchronizations performed along the edges of a spanning tree. Multi-hop synchronization requires only n-1 pair-wise synchronizations for a network of n nodes. In addition, we show that the communication complexity and accuracy of multi-hop synchronization is a function of the construction and depth of the spanning tree; several spanning-tree construction algorithms are described. Further, the required refresh rate of multi-hop synchronization is shown as a function of clock drift and the accuracy of single-hop synchronization. Finally, a distributed multi-hop synchronization is presented where nodes keep track of their own clock drift and their synchronization accuracy. In this scheme, nodes initialize their own resynchronization as needed.
---
paper_title: A Comparison of Clock Synchronization in Wireless Sensor Networks

paper_content:

The recent advances in microelectro devices have led the researchers to an area of developing a large distributed system that consist of small, wireless sensor nodes. These sensor nodes are usually equipped with sensors to perceive the environment. Synchronization is an important component of almost all distributed systems and has been studied by many researchers. There are many solutions for the classical networks, but the traditional synchronization techniques are not suitable for sensor networks because they do not consider the partitioning of the network and message delay. Additionally, limited power, computational capacity, and memory of the sensor nodes make the problem more challenging for wireless sensor networks. This paper examines the clock synchronization issues in wireless sensor networks. Energy efficiency, cost, scalability, lifetime, robustness, and precision are the main problems to be considered in design of a synchronization algorithm. There is no one single system that satisfies all these together. A comparison of different clock synchronization algorithms in wireless sensor networks with a main focus on energy efficiency, scalability, and precision properties of them will be provided here.
---
paper_title: Wired and wireless sensor networks for industrial applications

paper_content:

Distributed architectures for industrial applications are a new opportunity to realize cost-effective, flexible, scalable and reliable systems. Direct interfacing of sensors and actuators to the industrial communication network improves the system performance, because process data and diagnostics can be simultaneously available to many systems and also shared on the Web. However, sensors, especially low-cost ones, cannot use standard communication protocols suitable for computers and PLCs. In fact, sensors typically require a cyclic, isochronous and hard real-time exchange of few data, whereas PCs and PLCs exchange a large amount of data with soft real-time constrains. Looking at the industrial communication systems, this separation is clearly visible: several fieldbuses have been designed for specific sensor application areas, whereas high-level industrial equipments use wired/wireless Ethernet and Internet technologies. Recently, traditional fieldbuses were replaced by Real-Time Ethernet protocols, which are ''extended'' versions of Ethernet that meet real-time operation requirements. Besides, real-time wireless sensor networking seems promising, as demonstrated by the growing research activities. In this paper, an overview of the state-of-art of real-time sensor networks for industrial applications is presented. Particular attention has been paid to the description of methods and instrumentation for performance measurement in this kind of architectures.
---
paper_title: Clock Synchronization in Wireless Sensor Networks: An Overview

paper_content:

The development of tiny, low-cost, low-power and multifunctional sensor nodes equipped with sensing, data processing, and communicating components, have been made possible by the recent advances in micro-electro-mechanical systems (MEMS) technology. Wireless sensor networks (WSNs) assume a collection of such tiny sensing devices connected wirelessly and which are used to observe and monitor a variety of phenomena in the real physical world. Many applications based on these WSNs assume local clocks at each sensor node that need to be synchronized to a common notion of time. This paper reviews the existing clock synchronization protocols for WSNs and the methods of estimating clock offset and clock skew in the most representative clock synchronization protocols for WSNs.
---
paper_title: Application of Wireless Sensor Networks in Environmental Monitoring

paper_content:

The composition and structure were described to show an environment monitoring system based on wireless sensor network.The design of network node and gateway was discussed to demonstrate the TinyOS-based node's workflow and application program′s component in the system.
---
paper_title: Timing-sync protocol for sensor networks

paper_content:

Wireless ad-hoc sensor networks have emerged as an interesting and important research area in the last few years. The applications envisioned for such networks require collaborative execution of a distributed task amongst a large set of sensor nodes. This is realized by exchanging messages that are time-stamped using the local clocks on the nodes. Therefore, time synchronization becomes an indispensable piece of infrastructure in such systems. For years, protocols such as NTP have kept the clocks of networked systems in perfect synchrony. However, this new class of networks has a large density of nodes and very limited energy resource at every node; this leads to scalability requirements while limiting the resources that can be used to achieve them. A new approach to time synchronization is needed for sensor networks.In this paper, we present Timing-sync Protocol for Sensor Networks (TPSN) that aims at providing network-wide time synchronization in a sensor network. The algorithm works in two steps. In the first step, a hierarchical structure is established in the network and then a pair wise synchronization is performed along the edges of this structure to establish a global timescale throughout the network. Eventually all nodes in the network synchronize their clocks to a reference node. We implement our algorithm on Berkeley motes and show that it can synchronize a pair of neighboring motes to an average accuracy of less than 20ms. We argue that TPSN roughly gives a 2x better performance as compared to Reference Broadcast Synchronization (RBS) and verify this by implementing RBS on motes. We also show the performance of TPSN over small multihop networks of motes and use simulations to verify its accuracy over large-scale networks. We show that the synchronization accuracy does not degrade significantly with the increase in number of nodes being deployed, making TPSN completely scalable.
---
paper_title: Distributed synchronization in wireless networks

paper_content:

This article has explored history, recent advances, and challenges in distributed synchronization for distributed wireless systems. It is focused on synchronization schemes based on exchange of signals at the physical layer and corresponding baseband processing, wherein analysis and design can be performed using known tools from signal processing. Emphasis has also been given on the synergy between distributed synchronization and distributed estimation/detection problems. Finally, we have touched upon synchronization of nonperiodic (chaotic) signals. Overall, we hope to have conveyed the relevance of the subject and to have provided insight on the open issues and available analytical tools that could inspire further research within the signal processing community.
---
paper_title: Simple, accurate time synchronization for wireless sensor networks

paper_content:

Time synchronization is important for any distributed system. In particular, wireless sensor networks make extensive use of synchronized time in many contexts (e.g. for data fusion, TDMA schedules, synchronized sleep periods, etc.). Existing time synchronization methods were not designed with wireless sensors in mind, and need to be extended or redesigned. Our solution centers around the development of a deterministic time synchronization method relevant for wireless sensor networks. The proposed solution features minimal complexity in network bandwidth, storage and processing and can achieve good accuracy. Highly relevant for sensor networks, it also provides tight, deterministic bounds on both the offsets and clock drifts. A method to synchronize the entire network in preparation for data fusion is presented. A real implementation of a wireless ad-hoc network is used to evaluate the performance of the proposed approach.
---
paper_title: The flooding time synchronization protocol

paper_content:

Wireless sensor network applications, similarly to other distributed systems, often require a scalable time synchronization service enabling data consistency and coordination. This paper describes the Flooding Time Synchronization Protocol (FTSP), especially tailored for applications requiring stringent precision on resource limited wireless platforms. The proposed time synchronization protocol uses low communication bandwidth and it is robust against node and link failures. The FTSP achieves its robustness by utilizing periodic flooding of synchronization messages, and implicit dynamic topology update. The unique high precision performance is reached by utilizing MAC-layer time-stamping and comprehensive error compensation including clock skew estimation. The sources of delays and uncertainties in message transmission are analyzed in detail and techniques are presented to mitigate their effects. The FTSP was implemented on the Berkeley Mica2 platform and evaluated in a 60-node, multi-hop setup. The average per-hop synchronization error was in the one microsecond range, which is markedly better than that of the existing RBS and TPSN algorithms.
---
paper_title: Lightweight time synchronization for sensor networks

paper_content:

This paper presents lightweight tree-based synchronization (LTS) methods for sensor networks. First, a single-hop, pair-wise synchronization scheme is analyzed. This scheme requires the exchange of only three messages and has Gaussian error properties. The single-hop approach is extended to a centralized multi-hop synchronization method. Multi-hop synchronization consists of pair-wise synchronizations performed along the edges of a spanning tree. Multi-hop synchronization requires only n-1 pair-wise synchronizations for a network of n nodes. In addition, we show that the communication complexity and accuracy of multi-hop synchronization is a function of the construction and depth of the spanning tree; several spanning-tree construction algorithms are described. Further, the required refresh rate of multi-hop synchronization is shown as a function of clock drift and the accuracy of single-hop synchronization. Finally, a distributed multi-hop synchronization is presented where nodes keep track of their own clock drift and their synchronization accuracy. In this scheme, nodes initialize their own resynchronization as needed.
---
paper_title: Timing-sync protocol for sensor networks

paper_content:

Wireless ad-hoc sensor networks have emerged as an interesting and important research area in the last few years. The applications envisioned for such networks require collaborative execution of a distributed task amongst a large set of sensor nodes. This is realized by exchanging messages that are time-stamped using the local clocks on the nodes. Therefore, time synchronization becomes an indispensable piece of infrastructure in such systems. For years, protocols such as NTP have kept the clocks of networked systems in perfect synchrony. However, this new class of networks has a large density of nodes and very limited energy resource at every node; this leads to scalability requirements while limiting the resources that can be used to achieve them. A new approach to time synchronization is needed for sensor networks.In this paper, we present Timing-sync Protocol for Sensor Networks (TPSN) that aims at providing network-wide time synchronization in a sensor network. The algorithm works in two steps. In the first step, a hierarchical structure is established in the network and then a pair wise synchronization is performed along the edges of this structure to establish a global timescale throughout the network. Eventually all nodes in the network synchronize their clocks to a reference node. We implement our algorithm on Berkeley motes and show that it can synchronize a pair of neighboring motes to an average accuracy of less than 20ms. We argue that TPSN roughly gives a 2x better performance as compared to Reference Broadcast Synchronization (RBS) and verify this by implementing RBS on motes. We also show the performance of TPSN over small multihop networks of motes and use simulations to verify its accuracy over large-scale networks. We show that the synchronization accuracy does not degrade significantly with the increase in number of nodes being deployed, making TPSN completely scalable.
---
paper_title: Simple, accurate time synchronization for wireless sensor networks

paper_content:

Time synchronization is important for any distributed system. In particular, wireless sensor networks make extensive use of synchronized time in many contexts (e.g. for data fusion, TDMA schedules, synchronized sleep periods, etc.). Existing time synchronization methods were not designed with wireless sensors in mind, and need to be extended or redesigned. Our solution centers around the development of a deterministic time synchronization method relevant for wireless sensor networks. The proposed solution features minimal complexity in network bandwidth, storage and processing and can achieve good accuracy. Highly relevant for sensor networks, it also provides tight, deterministic bounds on both the offsets and clock drifts. A method to synchronize the entire network in preparation for data fusion is presented. A real implementation of a wireless ad-hoc network is used to evaluate the performance of the proposed approach.
---
paper_title: Component-Based Software Systems for Smart Environments

paper_content:

The article focuses on the role component-based software may play in realizing smart environments. A scenario describes a future smart environment in a university campus setting. The scenario illustrates how software components might contribute to the various phases of development, deployment and use of smart environments. Key research areas identified include: development of component frameworks, component interface standards, addressing schemes, and protocols.
---
paper_title: Novel Clock Phase Offset and Skew Estimation Using Two-Way Timing Message Exchanges for Wireless Sensor Networks

paper_content:

Recently, a few efficient timing synchronization protocols for wireless sensor networks (WSNs) have been proposed with the goal of maximizing the accuracy and minimizing the power utilization. This paper proposes novel clock skew estimators assuming different delay environments to achieve energy-efficient network-wide synchronization for WSNs. The proposed clock skew correction mechanism significantly increases the re-synchronization period, which is a critical factor in reducing the overall power consumption. The proposed synchronization scheme can be applied to the conventional protocols without additional overheads. Moreover, this paper derives the Cramer-Rao lower bounds and the maximum likelihood estimators under different delay models and assumptions. These analytical metrics serves as good benchmarks for the thus far reported experimental results
---
paper_title: Wireless sensor networks for healthcare: A survey

paper_content:

Becoming mature enough to be used for improving the quality of life, wireless sensor network technologies are considered as one of the key research areas in computer science and healthcare application industries. The pervasive healthcare systems provide rich contextual information and alerting mechanisms against odd conditions with continuous monitoring. This minimizes the need for caregivers and helps the chronically ill and elderly to survive an independent life, besides provides quality care for the babies and little children whose both parents have to work. Although having significant benefits, the area has still major challenges which are investigated in this paper. We provide several state of the art examples together with the design considerations like unobtrusiveness, scalability, energy efficiency, security and also provide a comprehensive analysis of the benefits and challenges of these systems.
---
paper_title: Cooperative Synchronization in Wireless Networks

paper_content:

Synchronization is a key functionality in wireless networks, enabling a wide variety of services. We consider a Bayesian inference framework whereby network nodes can achieve phase and skew synchronization in a fully distributed way. In particular, under the assumption of Gaussian measurement noise, we derive two message passing methods (belief propagation and mean field), analyze their convergence behavior, and perform a qualitative and quantitative comparison with a number of competing algorithms. We also show that both methods can be applied in networks with and without master nodes. Our performance results are complemented by, and compared with, the relevant Bayesian Cramer-Rao bounds.
---
paper_title: On Clock Offset Estimation in Wireless Sensor Networks with Weibull Distributed Network Delays

paper_content:

We consider the problem of Maximum Likelihood (ML) estimation of clock parameters in a two-way timing exchange scenario where the random delays assume a Weibull distribution, which represents a more generalized model. The ML estimate of the clock offset for the case of exponential distribution was obtained earlier. Moreover, it was reported that when the fixed delay is known, MLE is not unique. We determine the uniformly minimum variance unbiased (UMVU) estimators for exponential distribution under such a scenario and produce biased estimators having lower MSE than UMVU for all values of clock offset. We then consider the case when shape parameter is greater than one and reduce the corresponding optimization problems to their equivalent convex forms, thus guaranteeing convergence to a global minimum.
---
paper_title: On Clock Synchronization Algorithms for Wireless Sensor Networks Under Unknown Delay

paper_content:

In this paper, three clock-synchronization algorithms for wireless sensor networks (WSNs) under unknown delay are derived. They include the maximum-likelihood estimator (MLE), a generalization of the estimator of Noh , and a novel low-complexity estimator. Their corresponding performance bounds are derived and compared, and complexities are also analyzed. It is found that the MLE achieves the best performance with the price of high complexity. For the generalized version of the estimator of Noh , although it has low complexity, its performance is degraded with respect to the MLE. On the other hand, the newly proposed estimator achieves the same performance as the MLE, and the complexity is at the same level as that of the generalized version of the estimator of Noh et al.
---
paper_title: On calibrating measurements of packet transit times

paper_content:

We discuss the problem of detecting errors in measurements of the total delay experienced by packets transmitted through a wide-area network. We assume that we have measurements of the transmission times of a group of packets sent from an originating host, A, and a corresponding set of measurements of their arrival times at their destination host, B, recorded by two separate clocks. We also assume that we have a similar series of measurements of packets sent from B to A (as might occur when recording a TCP connection), but we do not assume that the clock at A is synchronized with the clock at B, nor that they run at the same frequency. We develop robust algorithms for detecting abrupt adjustments to either clock, and for estimating the relative skew between the clocks. By analyzing a large set of measurements of Internet TCP connections, we find that both clock adjustments and relative skew are sufficiently common that failing to detect them can lead to potentially large errors when analyzing packet transit times. We further find that synchronizing clocks using a network time protocol such as NTP does not free them from such errors.
---
paper_title: Analysis of synchronization algorithms with time-out control over networks with exponentially symmetric delays

paper_content:

We study the performance of a class of time-offset estimation algorithms for synchronization of master-slave nodes based on asynchronous transfer of timing cells when GPS is not used. We implement a synchronization control mechanism based on cell acknowledgment time-out (TO) with wait or no wait options. We analyze the mechanism reliability and performance parameters over symmetric links using an exponential cell delay variation model. We show that the maximum-likelihood offset estimator does not exist for the exponential likelihood function. We analytically provide RMS error result comparisons for five ad hoc offset estimation algorithms: the median round delay, the minimum round delay, the minimum link delay (MnLD), the median phase, and the average phase. We show that the MnLD algorithm achieves the best accuracy over symmetric links without having to impose a strict TO control, which substantially speeds up the algorithm. We also discuss an open-loop estimation updating mechanism based on standard clock models.
---
paper_title: Estimation and removal of clock skew from network delay measurements

paper_content:

Packet delay and loss traces are frequently used by network engineers, as well as network applications, to analyze network performance. The clocks on the end-systems used to measure the delays, however, are not always synchronized, and this lack of synchronization reduces the accuracy of these measurements. Therefore, estimating and removing relative skews and offsets from delay measurements between sender and receiver clocks are critical to the accurate assessment and analysis of network performance. We introduce a linear programming-based algorithm to estimate the clock skew in network delay measurements and compare it with three other algorithms. We show that our algorithm has a time complexity of O(N), leaves the delay after the skew removal positive, and is robust in the sense that the error margin of the skew estimate is independent of the magnitude of the skew. We use traces of real Internet delay measurements to assess the algorithm, and compare its performance to that of three other algorithms. Furthermore, we show through simulation that our algorithm is unbiased, and that the sample variance of the skew estimate is better (smaller) than existing algorithms.
---
paper_title: A Factor Graph Approach to Clock Offset Estimation in Wireless Sensor Networks

paper_content:

The problem of clock offset estimation in a two-way timing message exchange regime is considered when the likelihood function of the observation time stamps is Gaussian, exponential, or log-normally distributed. A parameterized solution to the maximum likelihood (ML) estimation of clock offset is analytically obtained, which differs from the earlier approaches where the likelihood function is maximized graphically. In order to capture the imperfections in node oscillators, which may render a time-varying nature to the clock offset, a novel Bayesian approach to the clock offset estimation is proposed by using a factor graph representation of the posterior density. Message passing using the max-product algorithm yields an exact expression for the Bayesian inference problem. Several lower bounds on the variance of an estimator are derived for arbitrary exponential family distributed likelihood functions which, while serving as stepping stones to benchmark the performance of the proposed clock offset estimators, can be useful in their own right in classical as well Bayesian parameter estimation theory. To corroborate the theoretical findings, extensive simulation results are discussed for classical as well as Bayesian estimators in various scenarios. It is observed that the performance of the proposed estimators is fairly close to the fundamental limits established by the lower bounds.
---
paper_title: Wired and wireless sensor networks for industrial applications

paper_content:

Distributed architectures for industrial applications are a new opportunity to realize cost-effective, flexible, scalable and reliable systems. Direct interfacing of sensors and actuators to the industrial communication network improves the system performance, because process data and diagnostics can be simultaneously available to many systems and also shared on the Web. However, sensors, especially low-cost ones, cannot use standard communication protocols suitable for computers and PLCs. In fact, sensors typically require a cyclic, isochronous and hard real-time exchange of few data, whereas PCs and PLCs exchange a large amount of data with soft real-time constrains. Looking at the industrial communication systems, this separation is clearly visible: several fieldbuses have been designed for specific sensor application areas, whereas high-level industrial equipments use wired/wireless Ethernet and Internet technologies. Recently, traditional fieldbuses were replaced by Real-Time Ethernet protocols, which are ''extended'' versions of Ethernet that meet real-time operation requirements. Besides, real-time wireless sensor networking seems promising, as demonstrated by the growing research activities. In this paper, an overview of the state-of-art of real-time sensor networks for industrial applications is presented. Particular attention has been paid to the description of methods and instrumentation for performance measurement in this kind of architectures.
---
paper_title: On maximum-likelihood estimation of clock offset

paper_content:

Delay measurements from timing message exchanges between two clocks produce a maximum-likelihood estimator (MLE) of the clock offset when fixed delays in each direction are equal and unknown, and variable delays in each direction have an exponential distribution with an unknown mean. It is shown that the MLE corresponds to a previously proposed estimator of clock offset. The ML interpretation of the estimator provides further insight and motivation for its use.
---
paper_title: Analysis of synchronization algorithms with time-out control over networks with exponentially symmetric delays

paper_content:

We study the performance of a class of time-offset estimation algorithms for synchronization of master-slave nodes based on asynchronous transfer of timing cells when GPS is not used. We implement a synchronization control mechanism based on cell acknowledgment time-out (TO) with wait or no wait options. We analyze the mechanism reliability and performance parameters over symmetric links using an exponential cell delay variation model. We show that the maximum-likelihood offset estimator does not exist for the exponential likelihood function. We analytically provide RMS error result comparisons for five ad hoc offset estimation algorithms: the median round delay, the minimum round delay, the minimum link delay (MnLD), the median phase, and the average phase. We show that the MnLD algorithm achieves the best accuracy over symmetric links without having to impose a strict TO control, which substantially speeds up the algorithm. We also discuss an open-loop estimation updating mechanism based on standard clock models.
---
paper_title: Estimation of Clock Offset Using Bootstrap Bias-Correction Techniques

paper_content:

A recently proposed estimator of the offset between two clocks in a data communications network is based on an exchange of timing messages between the clocks. It is well known that different distributions of the transmission delays in the two directions associated with the exchanged messages cause the estimator to be biased. We use the bootstrap methodology to obtain a closed-form estimator of the bias and then form a new bias-corrected estimator of the clock offset. We show that for common distribution assumptions for the transmission delays, the bias-corrected estimator has smaller mean squared error (MSE) than the uncorrected estimator. We also derive the order statistic-based best linear unbiased estimator (o-BLUE) of the clock offset under the assumption that transmission delays are exponentially distributed. Several studies on network delay characteristics show that no single distribution adequately characterizes delays. Not only are delays highly dependent on the nature of traffic, they are also ti...
---
paper_title: On Minimum Variance Unbiased Estimation of Clock Offset in a Two-Way Message Exchange Mechanism

paper_content:

For many applications, distributed networks require the local clocks of the constituent nodes to run close to an agreed upon notion of time. Most of the widely used clock synchronization algorithms in such systems employ the sender-receiver protocol based on a two-way timing message exchange paradigm. Maximum likelihood estimator (MLE) of the clock offset based on the timing message exchanges between two clocks was derived in D. R. Jeske, On maximum likelihood estimation of clock offset[IEEE Trans. Commun., vol. 53, pp. 53-54, Jan. 2005], when the fixed delays are symmetric and the variable delays in each direction assume an exponential distribution with an unknown mean. Herein, the best linear unbiased estimate using order statistics (BLUE-OS) of the clock offset between two nodes is derived assuming both symmetric and asymmetric exponential network delays, respectively. The Rao-Blackwell-Lehmann-Scheffe? theorem is then exploited to obtain the minimum variance unbiased estimate (MVUE) for the clock offset which it is shown to coincide with the BLUE-OS. In addition, it is found that the MVUE of the clock offset in the presence of symmetric network delays also coincides with the MLE. Finally, in the presence of asymmetric network delays, although the MLE is biased, it is shown to achieve lesser mean-square error (MSE) than the MVUE in the region around the point where the bidirectional network link delays are symmetric and hence its merit as the most versatile estimator is fairly justified.
---
paper_title: On Minimum Variance Unbiased Estimation of Clock Offset in a Two-Way Message Exchange Mechanism

paper_content:

For many applications, distributed networks require the local clocks of the constituent nodes to run close to an agreed upon notion of time. Most of the widely used clock synchronization algorithms in such systems employ the sender-receiver protocol based on a two-way timing message exchange paradigm. Maximum likelihood estimator (MLE) of the clock offset based on the timing message exchanges between two clocks was derived in D. R. Jeske, On maximum likelihood estimation of clock offset[IEEE Trans. Commun., vol. 53, pp. 53-54, Jan. 2005], when the fixed delays are symmetric and the variable delays in each direction assume an exponential distribution with an unknown mean. Herein, the best linear unbiased estimate using order statistics (BLUE-OS) of the clock offset between two nodes is derived assuming both symmetric and asymmetric exponential network delays, respectively. The Rao-Blackwell-Lehmann-Scheffe? theorem is then exploited to obtain the minimum variance unbiased estimate (MVUE) for the clock offset which it is shown to coincide with the BLUE-OS. In addition, it is found that the MVUE of the clock offset in the presence of symmetric network delays also coincides with the MLE. Finally, in the presence of asymmetric network delays, although the MLE is biased, it is shown to achieve lesser mean-square error (MSE) than the MVUE in the region around the point where the bidirectional network link delays are symmetric and hence its merit as the most versatile estimator is fairly justified.
---
paper_title: Novel Clock Phase Offset and Skew Estimation Using Two-Way Timing Message Exchanges for Wireless Sensor Networks

paper_content:

Recently, a few efficient timing synchronization protocols for wireless sensor networks (WSNs) have been proposed with the goal of maximizing the accuracy and minimizing the power utilization. This paper proposes novel clock skew estimators assuming different delay environments to achieve energy-efficient network-wide synchronization for WSNs. The proposed clock skew correction mechanism significantly increases the re-synchronization period, which is a critical factor in reducing the overall power consumption. The proposed synchronization scheme can be applied to the conventional protocols without additional overheads. Moreover, this paper derives the Cramer-Rao lower bounds and the maximum likelihood estimators under different delay models and assumptions. These analytical metrics serves as good benchmarks for the thus far reported experimental results
---
paper_title: Wireless sensor networks for healthcare: A survey

paper_content:

Becoming mature enough to be used for improving the quality of life, wireless sensor network technologies are considered as one of the key research areas in computer science and healthcare application industries. The pervasive healthcare systems provide rich contextual information and alerting mechanisms against odd conditions with continuous monitoring. This minimizes the need for caregivers and helps the chronically ill and elderly to survive an independent life, besides provides quality care for the babies and little children whose both parents have to work. Although having significant benefits, the area has still major challenges which are investigated in this paper. We provide several state of the art examples together with the design considerations like unobtrusiveness, scalability, energy efficiency, security and also provide a comprehensive analysis of the benefits and challenges of these systems.
---
paper_title: Cooperative Synchronization in Wireless Networks

paper_content:

Synchronization is a key functionality in wireless networks, enabling a wide variety of services. We consider a Bayesian inference framework whereby network nodes can achieve phase and skew synchronization in a fully distributed way. In particular, under the assumption of Gaussian measurement noise, we derive two message passing methods (belief propagation and mean field), analyze their convergence behavior, and perform a qualitative and quantitative comparison with a number of competing algorithms. We also show that both methods can be applied in networks with and without master nodes. Our performance results are complemented by, and compared with, the relevant Bayesian Cramer-Rao bounds.
---
paper_title: Estimation and removal of clock skew from network delay measurements

paper_content:

Packet delay and loss traces are frequently used by network engineers, as well as network applications, to analyze network performance. The clocks on the end-systems used to measure the delays, however, are not always synchronized, and this lack of synchronization reduces the accuracy of these measurements. Therefore, estimating and removing relative skews and offsets from delay measurements between sender and receiver clocks are critical to the accurate assessment and analysis of network performance. We introduce a linear programming-based algorithm to estimate the clock skew in network delay measurements and compare it with three other algorithms. We show that our algorithm has a time complexity of O(N), leaves the delay after the skew removal positive, and is robust in the sense that the error margin of the skew estimate is independent of the magnitude of the skew. We use traces of real Internet delay measurements to assess the algorithm, and compare its performance to that of three other algorithms. Furthermore, we show through simulation that our algorithm is unbiased, and that the sample variance of the skew estimate is better (smaller) than existing algorithms.
---
paper_title: On joint synchronization of clock offset and skew for Wireless Sensor Networks under exponential delay

paper_content:

In this paper, the problem of clock synchronization for Wireless Sensor Network (WSN) under exponential delay is analyzed based on two-way message exchange mechanism. The Maximum Likelihood Estimator (MLE) for joint estimation of the clock offset and clock skew is derived, and an approximate Cramer-Rao Lower Bound (CRLB) is also developed. Simulation results verify that the proposed estimator gives improved performance compared to an existing algorithm.
---
paper_title: On Maximum Likelihood Estimation of Clock Offset and Skew in Networks With Exponential Delays

paper_content:

Clock synchronization represents a crucial element in the operation of wireless sensor networks (WSNs). For any general time synchronization protocol involving a two-way message exchange mechanism, e.g., timing synch protocol for sensor networks (TPSN) [see S. Ganeriwal, R. Kumar, and M. B. Srivastava, "Timing Synch Protocol for Sensor Networks," in Proceedings of the First International Conference on Embedded Network Sensor Systems," 2003, pp. 138-149], the maximum likelihood estimate (MLE) for clock offset under the exponential delay model was derived in [D. R. Jeske, ";On the Maximum Likelihood Estimation of Clock Offset," IEEE Transactions on Communications, vol. 53, no. 1, pp. 53-54, January 2005] assuming no clock skew between the nodes. Since all practical clocks are running at different rates with respect to each other, the skew correction becomes important for achieving long term synchronization since it results in the reduction of the number of message exchanges and hence minimization of power consumption. In this paper, the joint MLE of clock offset and skew under the exponential delay model for a two way timing message exchange mechanism and the corresponding algorithms for finding these estimates are presented. Since any time synchronization protocol involves real time message exchanges between the sensor nodes, ML estimates for other synchronization protocols can be derived by employing a similar procedure. In addition, due to the computational complexity of the MLE, a simple, computationally efficient and easy to implement algorithm is presented as an alternative to the ML estimator which particularly suits the low power demanding regime of wireless sensor networks.
---
paper_title: Maximum likelihood estimators of clock offset and skew under exponential delays

paper_content:

Accurate clock synchronization is essential for many data network applications. Various algorithms for synchronizing clocks rely on estimators of the offset and skew parameters that describe the relation between times measured by two different clocks. Maximum likelihood estimation (MLE) of these parameters has previously been considered under the assumption of exponentially distributed network delays with known means. We derive the MLEs under the more common case of exponentially distributed network delays with unknown means and compare their mean-squared error properties to a recently proposed alternative estimator. We investigate the robustness of the derived MLE to the assumption of non-exponential network delays, and demonstrate the effectiveness of a bootstrap bias-correction technique. Copyright © 2009 John Wiley & Sons, Ltd.
---
paper_title: On calibrating measurements of packet transit times

paper_content:

We discuss the problem of detecting errors in measurements of the total delay experienced by packets transmitted through a wide-area network. We assume that we have measurements of the transmission times of a group of packets sent from an originating host, A, and a corresponding set of measurements of their arrival times at their destination host, B, recorded by two separate clocks. We also assume that we have a similar series of measurements of packets sent from B to A (as might occur when recording a TCP connection), but we do not assume that the clock at A is synchronized with the clock at B, nor that they run at the same frequency. We develop robust algorithms for detecting abrupt adjustments to either clock, and for estimating the relative skew between the clocks. By analyzing a large set of measurements of Internet TCP connections, we find that both clock adjustments and relative skew are sufficiently common that failing to detect them can lead to potentially large errors when analyzing packet transit times. We further find that synchronizing clocks using a network time protocol such as NTP does not free them from such errors.
---
paper_title: Sequential Fixed Width Confidence Intervals for the Offset Between Two Network Clocks

paper_content:

Abstract Estimation of the offset between two network clocks has received a lot of attention in the literature, with the motivating force being data networking applications that require synchronous communication protocols. Statistical modeling techniques have been used to develop improved estimation algorithms, with a recent development being the construction of a confidence interval based on a fixed sample size. Lacking in the fixed sample size confidence interval procedures is a useable relationship between sample size and the width of the resulting confidence interval. Were that available, an optimum sample size could be determined to achieve a specified level of precision in the estimator and thereby improve the efficiency of the estimation procedure by reducing unnecessary overhead in the network that is associated with collecting the data used by the estimation schemes. A fixed sample size confidence interval that has a prescribed width is not available for this problem. However, in this paper we de...
---
paper_title: Estimation and Confidence Intervals for Clock Offset in Networks with Bivariate Exponential Delays

paper_content:

There is a large and increasing literature on statistical modeling-based estimation of the offset between two clocks. Recent work has focused on the construction of confidence intervals for offset. However, in most of this work it has been assumed that the network delays that occur during the synchronization process are independent. The network delays are often modeled as independent exponential random variables. Thus, we introduce the use of a bivariate exponential distribution to capture the anticipated correlation between the network delays and derive a maximum likelihood estimator and a confidence interval procedure for the offset parameter. We then illustrate how use of the independent model for network delays can lead to improper inference about the offset parameter.
---
paper_title: Approximate and generalized pivotal quantities for deriving confidence intervals for the offset between two clocks

paper_content:

Abstract Development of algorithms that estimate the offset between two clocks has received a lot of attention, with the motivating force being data networking applications that require synchronous communication protocols. Recently, statistical modeling techniques have been used to develop improved estimation algorithms with the focus being obtaining robust estimators in terms of mean squared error. In this paper, we extend the use of statistical modeling techniques to address the construction of confidence intervals for the offset parameter. We consider the case where the distributions of network delays are members of a scale family. Our results include an asymptotic confidence interval and a generalized confidence interval in the sense of [S. Weerahandi, Generalized confidence intervals, Journal of the American Statistical Association 88 (1993) 899–905. Correction in vol. 89, p. 726, 1994]. We compare and contrast the two approaches for obtaining a confidence interval, and illustrate specific applications using exponential, Rayleigh and heavy-tailed Weibull network delays as concrete examples.
---
paper_title: Estimation of Clock Offset Using Bootstrap Bias-Correction Techniques

paper_content:

A recently proposed estimator of the offset between two clocks in a data communications network is based on an exchange of timing messages between the clocks. It is well known that different distributions of the transmission delays in the two directions associated with the exchanged messages cause the estimator to be biased. We use the bootstrap methodology to obtain a closed-form estimator of the bias and then form a new bias-corrected estimator of the clock offset. We show that for common distribution assumptions for the transmission delays, the bias-corrected estimator has smaller mean squared error (MSE) than the uncorrected estimator. We also derive the order statistic-based best linear unbiased estimator (o-BLUE) of the clock offset under the assumption that transmission delays are exponentially distributed. Several studies on network delay characteristics show that no single distribution adequately characterizes delays. Not only are delays highly dependent on the nature of traffic, they are also ti...
---
paper_title: Least Squares-Based Estimation of Relative Clock Offset and Frequency in Sensor Networks with High Latency

paper_content:

Accurate clock synchronization is essential in the operation of Sensor Networks. Algorithms for clock synchronization generally rely on estimators of the relative offset and frequency of two different clocks. Sensor Networks have limited power resources so it is important that these estimators not be too computationally intensive. For this reason a number of least squares-based estimators have been proposed, however they are not appropriate for sensor networks with significant propagation latency. For these applications, the Time Synchronization for High Latency (TSHL) protocol was developed. We seek to improve the accuracy of TSHL and thus propose, study, and demonstrate the effectiveness of several alternative least squares-based estimators.
---
paper_title: Estimation of Clock Offset Using Bootstrap Bias-Correction Techniques

paper_content:

A recently proposed estimator of the offset between two clocks in a data communications network is based on an exchange of timing messages between the clocks. It is well known that different distributions of the transmission delays in the two directions associated with the exchanged messages cause the estimator to be biased. We use the bootstrap methodology to obtain a closed-form estimator of the bias and then form a new bias-corrected estimator of the clock offset. We show that for common distribution assumptions for the transmission delays, the bias-corrected estimator has smaller mean squared error (MSE) than the uncorrected estimator. We also derive the order statistic-based best linear unbiased estimator (o-BLUE) of the clock offset under the assumption that transmission delays are exponentially distributed. Several studies on network delay characteristics show that no single distribution adequately characterizes delays. Not only are delays highly dependent on the nature of traffic, they are also ti...
---
paper_title: Jackknife Bias Correction of a Clock Offset Estimator

paper_content:

Internet telephony and wireless geolocation prediction are two examples of many data networking applications that require synchronization among independent network clocks. An approach to estimating the offset between two clocks in the presence of variable network delays involves exchanging timing messages between the clocks. A well known clock offset estimator based on this approach can be interpreted as the maximum likelihood estimator when the underlying network delay distributions are assumed to be exponential. Several studies on network delay characteristics show that no single distribution adequately characterizes delays. Not only are delays highly dependent on the nature of traffic, but they are also time varying. Therefore, robustness with respect to the assumed underlying network delay distribution is an important property for any clock offset estimator.
---
paper_title: An Introduction to the Bootstrap

paper_content:

Introduction The Accuracy of a Sample Mean Random Samples and Probabilities The Empirical Distribution Function and the Plug-In Principle Standard Errors and Estimated Standard Errors The Bootstrap Estimate of Standard Error Bootstrap Standard Errors: Some Examples More Complicated Data Structures Regression Models Estimates of Bias The Jackknife Confidence Intervals Based on Bootstrap "Tables" Confidence Intervals Based on Bootstrap Percentiles Better Bootstrap Confidence Intervals Permutation Tests Hypothesis Testing with the Bootstrap Cross-Validation and Other Estimates of Prediction Error Adaptive Estimation and Calibration Assessing the Error in Bootstrap Estimates A Geometrical Representation for the Bootstrap and Jackknife An Overview of Nonparametric and Parametric Inference Further Topics in Bootstrap Confidence Intervals Efficient Bootstrap Computations Approximate Likelihoods Bootstrap Bioequivalence Discussion and Further Topics Appendix: Software for Bootstrap Computations References
---
paper_title: Speech quality prediction in VoIP using the extended E-model

paper_content:

The paper investigates the effects of packet loss and delay jitter on speech quality in voice over Internet protocol (VoIP) scenarios. A new formula is proposed to quantify these effects and incorporated into ITU-T G.107, the E-model. In the simulation, codecs ITU-T G.723.1 and G.729 are used; random packet loss and Pareto distributed network delay are introduced. The prediction errors range between -0.20 and +0.12 MOS (mean opinion score). The formula extends the coverage of the current E-model, and is very useful in MOS prediction as well as network planning.
---
paper_title: Effectiveness of bootstrap bias correction in the context of clock offset estimators

paper_content:

Estimating and correcting the offset between two or more clocks is an important problem in data communication networks. For example, Internet telephony depends on network routers having a common notion of time, and cellular networks provide a higher quality of service by using transmission protocols that depend on neighboring base stations knowing the offset that exists between their local clocks. In previous work it was shown that bootstrap bias correction of Paxson's well-known estimator of clock offset produces an estimator with improved bias and mean squared error (MSE) properties. In addition, the ordered-BLUE (o-BLUE) under an exponential distribution for network delays was derived, and its bootstrap bias-corrected form was shown to have lower bias and MSE than the bootstrap bias-corrected form of Paxson's estimator when network delays follow lognormal, gamma, and Weibull distributions. The inferred robustness of the bias-corrected o-BLUE to the assumed distribution of network delays is an attractiv...
---
paper_title: Effects of channel delays on underflow events of compressed video over the Internet

paper_content:

This paper presents an extensive statistical study and analysis of the effects of channel delays in the current (best-effort) Internet on underflow events in MPEG-4 video streaming. Two types of network delays are considered: end-to-end round-trip delays and delay jitter. Our data were collected in a seven-month real-time streaming experiment, which was conducted between a number of unicast dialup clients in more than 600 major USA cities and a backbone video server. Among other findings, our analysis shows that startup delays approximately 15-20 times the average roundtrip time (RTT) are required for the client to avoid 90% of late packets caused by delay jitter. Meanwhile, startup delays of only 3-4 times the average RTT are needed to achieve lost-packet recovery rates of 90% or more. Hence, a key finding of our study is that delay jitter represents a more challenging problem for video streaming applications than round-trip delays. We also show that the probability density function (PDF) of RTT samples, which are associated with retransmitted video packets, can be modeled using a Pareto distribution. This observation indicates that the upper tail of the RTT PDF decays slower than reported in earlier studies.
---
paper_title: Playout control for streaming applications by statistical delay analysis

paper_content:

A packet transmission delay is an important quality characteristic for various applications including real-time and data applications. In particular, it is necessary to investigate not only the whole distribution of the packet transmission delay, but also the tail part of the distribution, in order to detect the packet loss. In this paper, we analyze the characteristics of the tail part of packet delay distributions by the statistical analytic approach. Our analytic results show that the Pareto distribution is most appropriate in 95-99.9% region of the cumulative distribution of packet transmission delays. Based on our statistical analysis, we next propose an adaptive playout control algorithm, which is suitable to real-time applications. Numerical examples show that our algorithm provides a stable packet loss ratio independently of traffic fluctuations.
---
paper_title: Approximate and generalized pivotal quantities for deriving confidence intervals for the offset between two clocks

paper_content:

Abstract Development of algorithms that estimate the offset between two clocks has received a lot of attention, with the motivating force being data networking applications that require synchronous communication protocols. Recently, statistical modeling techniques have been used to develop improved estimation algorithms with the focus being obtaining robust estimators in terms of mean squared error. In this paper, we extend the use of statistical modeling techniques to address the construction of confidence intervals for the offset parameter. We consider the case where the distributions of network delays are members of a scale family. Our results include an asymptotic confidence interval and a generalized confidence interval in the sense of [S. Weerahandi, Generalized confidence intervals, Journal of the American Statistical Association 88 (1993) 899–905. Correction in vol. 89, p. 726, 1994]. We compare and contrast the two approaches for obtaining a confidence interval, and illustrate specific applications using exponential, Rayleigh and heavy-tailed Weibull network delays as concrete examples.
---
paper_title: Estimation and Confidence Intervals for Clock Offset in Networks with Bivariate Exponential Delays

paper_content:

There is a large and increasing literature on statistical modeling-based estimation of the offset between two clocks. Recent work has focused on the construction of confidence intervals for offset. However, in most of this work it has been assumed that the network delays that occur during the synchronization process are independent. The network delays are often modeled as independent exponential random variables. Thus, we introduce the use of a bivariate exponential distribution to capture the anticipated correlation between the network delays and derive a maximum likelihood estimator and a confidence interval procedure for the offset parameter. We then illustrate how use of the independent model for network delays can lead to improper inference about the offset parameter.
---
paper_title: Least Squares-Based Estimation of Relative Clock Offset and Frequency in Sensor Networks with High Latency

paper_content:

Accurate clock synchronization is essential in the operation of Sensor Networks. Algorithms for clock synchronization generally rely on estimators of the relative offset and frequency of two different clocks. Sensor Networks have limited power resources so it is important that these estimators not be too computationally intensive. For this reason a number of least squares-based estimators have been proposed, however they are not appropriate for sensor networks with significant propagation latency. For these applications, the Time Synchronization for High Latency (TSHL) protocol was developed. We seek to improve the accuracy of TSHL and thus propose, study, and demonstrate the effectiveness of several alternative least squares-based estimators.
---
paper_title: Cooperative Synchronization in Wireless Networks

paper_content:

Synchronization is a key functionality in wireless networks, enabling a wide variety of services. We consider a Bayesian inference framework whereby network nodes can achieve phase and skew synchronization in a fully distributed way. In particular, under the assumption of Gaussian measurement noise, we derive two message passing methods (belief propagation and mean field), analyze their convergence behavior, and perform a qualitative and quantitative comparison with a number of competing algorithms. We also show that both methods can be applied in networks with and without master nodes. Our performance results are complemented by, and compared with, the relevant Bayesian Cramer-Rao bounds.
---
paper_title: Distributed Clock Synchronization for Wireless Sensor Networks Using Belief Propagation

paper_content:

In this paper, we study the global clock synchronization problem for wireless sensor networks. Based on belief propagation, we propose a fully distributed algorithm which has low overhead and can achieve scalable synchronization. It is also shown analytically that the proposed algorithm always converges for strongly connected networks. Simulation results show that the proposed algorithm achieves better accuracy than consensus algorithms. Furthermore, the belief obtained at each sensor provides an accurate prediction on the algorithm's performance in terms of MSE.
---
paper_title: Distributed Clock Synchronization over Wireless Networks: Algorithms and Analysis

paper_content:

We analyze the spatial smoothing algorithm of Solis, Borkar and Kumar (2005) for clock synchronization over multi-hop wireless networks. In particular, for a model of a random wireless network we show that with high probability the error variance is O(1) as the number of nodes in the network increases. This provides support for the feasibility of time-based computing n large wireless networks. We also provide bounds on the settling time of a distributed algorithm
---
paper_title: Distributed Clock Skew and Offset Estimation in Wireless Sensor Networks: Asynchronous Algorithm and Convergence Analysis

paper_content:

In this paper, we propose a fully distributed algorithm for joint clock skew and offset estimation in wireless sensor networks based on belief propagation. In the proposed algorithm, each node can estimate its clock skew and offset in a completely distributed and asynchronous way: some nodes may update their estimates more frequently than others using outdated message from neighboring nodes. In addition, the proposed algorithm is robust to random packet loss. Such algorithm does not require any centralized information processing or coordination, and is scalable with network size. The proposed algorithm represents a unified framework that encompasses both classes of synchronous and asynchronous algorithms for network-wide clock synchronization. It is shown analytically that the proposed asynchronous algorithm converges to the optimal estimates with estimation mean-square-error at each node approaching the centralized Cramer-Rao bound under any network topology. Simulation results further show that {the convergence speed is faster than that corresponding to a synchronous algorithm.
---
paper_title: Cooperative Synchronization in Wireless Networks

paper_content:

Synchronization is a key functionality in wireless networks, enabling a wide variety of services. We consider a Bayesian inference framework whereby network nodes can achieve phase and skew synchronization in a fully distributed way. In particular, under the assumption of Gaussian measurement noise, we derive two message passing methods (belief propagation and mean field), analyze their convergence behavior, and perform a qualitative and quantitative comparison with a number of competing algorithms. We also show that both methods can be applied in networks with and without master nodes. Our performance results are complemented by, and compared with, the relevant Bayesian Cramer-Rao bounds.
---
paper_title: Consensus Clock Synchronization for Wireless Sensor Networks

paper_content:

Wireless sensor networks (WSN) are emerging as a valuable tool in many fields of science and industry. Time synchronization is an important issue for WSN's due to the collaborative and distributed nature of the tasks they perform. This paper describes a new technique for clock synchronization in WSNs called consensus clock synchronization that provides internal synchronization to a virtual consensus clock. It is sensitive to the limited resources available to sensor nodes and is robust to many of the challenges faced in dynamic ad-hoc networks. Simulations are presented to analyse the effectiveness of the synchronization protocol in a mesh network.
---
paper_title: Fast clock synchronization in wireless sensor networks via ADMM-based consensus

paper_content:

In this paper, a consensus-based clock synchronization algorithm is presented and its resilience to frequency displacement estimation errors as well as communication noise is analyzed. The synchronization-enforcing control that is to be applied to clock periods is derived upon re-casting the consensus problem into a convex optimization problem and solving it in a distributed fashion via alternating direction method of multipliers. Conversely, plain consensus is used for reaching agreement on clock values. The proposed algorithm achieves higher convergence rates and equivalent noise resilience with respect to algorithmic solutions based on the only plain average consensus. The superior clock synchronization performance is corroborated via numerical tests.
---
paper_title: Low-Complex Synchronization Algorithms for Embedded Wireless Sensor Networks

paper_content:

In industrial applications of wireless sensor networks (WSNs), synchronized sampling of data on each sensor node is often required. Thus, the wireless communication protocol needs to support accurate timing synchronization. If due to a high sampling rate also high data throughput is required, WSNs based on the IEEE 802.15.4 physical layer often do not provide sufficient data rate. Wireless communications based on the well-established IEEE 802.11 wireless local area network (WLAN) standard provides high data throughput but not an accurate timing synchronization unless the protocol stack is severely changed. We propose two low-complexity consensus-based synchronization algorithms for the hybrid WSN introduced, which are executable at limited embedded computing capacity, e.g., on an 8-b microcontroller. A time division multiple access-based synchronization packet broadcasting with three-step-controlled or proportional-integral (PI)-controlled clock adjustment enables 1-kHz sensor sampling rate with a sampling jitter $\mu $ s for the three-step-controlled synchronization algorithm and $ for the PI-controlled algorithm.
---
paper_title: Distributed Clock Synchronization for Wireless Sensor Networks Using Belief Propagation

paper_content:

In this paper, we study the global clock synchronization problem for wireless sensor networks. Based on belief propagation, we propose a fully distributed algorithm which has low overhead and can achieve scalable synchronization. It is also shown analytically that the proposed algorithm always converges for strongly connected networks. Simulation results show that the proposed algorithm achieves better accuracy than consensus algorithms. Furthermore, the belief obtained at each sensor provides an accurate prediction on the algorithm's performance in terms of MSE.
---
paper_title: Distributed Clock Synchronization over Wireless Networks: Algorithms and Analysis

paper_content:

We analyze the spatial smoothing algorithm of Solis, Borkar and Kumar (2005) for clock synchronization over multi-hop wireless networks. In particular, for a model of a random wireless network we show that with high probability the error variance is O(1) as the number of nodes in the network increases. This provides support for the feasibility of time-based computing n large wireless networks. We also provide bounds on the settling time of a distributed algorithm
---
paper_title: A distributed consensus protocol for clock synchronization in wireless sensor network

paper_content:

This paper describes a novel consensus-based protocol, referred as Average TimeSync (ATS), for synchronizing a wireless sensor. This algorithm is based on a class of popular distributed algorithms known as consensus, agreement, gossip or rendezvous whose main idea is averaging local information. The proposed algorithm has three main features. Firstly, it is fully distributed and therefore robust to node failure and to new node appearance. Secondly, it compensates for clock skew differences among nodes, thus maintaining the network synchronized for longer periods than using simple clock offset compensation. Finally, it is computationally lite as it involves only simple sum/product operations. The algorithm has been implemented and preliminary experimental results are provided.
---
paper_title: Cooperative Synchronization in Wireless Networks

paper_content:

Synchronization is a key functionality in wireless networks, enabling a wide variety of services. We consider a Bayesian inference framework whereby network nodes can achieve phase and skew synchronization in a fully distributed way. In particular, under the assumption of Gaussian measurement noise, we derive two message passing methods (belief propagation and mean field), analyze their convergence behavior, and perform a qualitative and quantitative comparison with a number of competing algorithms. We also show that both methods can be applied in networks with and without master nodes. Our performance results are complemented by, and compared with, the relevant Bayesian Cramer-Rao bounds.
---
paper_title: Consensus Clock Synchronization for Wireless Sensor Networks

paper_content:

Wireless sensor networks (WSN) are emerging as a valuable tool in many fields of science and industry. Time synchronization is an important issue for WSN's due to the collaborative and distributed nature of the tasks they perform. This paper describes a new technique for clock synchronization in WSNs called consensus clock synchronization that provides internal synchronization to a virtual consensus clock. It is sensitive to the limited resources available to sensor nodes and is robust to many of the challenges faced in dynamic ad-hoc networks. Simulations are presented to analyse the effectiveness of the synchronization protocol in a mesh network.
---
paper_title: Global clock synchronization in sensor networks

paper_content:

Global synchronization is important for many sensor network applications that require precise mapping of collected sensor data with the time of the events, for example, in tracking and surveillance. It also plays an important role in energy conservation in MAC layer protocols. This paper describes four methods to achieve global synchronization in a sensor network: a node-based approach, a hierarchical cluster-based method, a diffusion-based method, and a fault-tolerant diffusion-based method. The diffusion-based protocol is fully localized. We present two implementations of the diffusion-based protocol for synchronous and asynchronous systems and prove its convergence. Finally, we show that, by imposing some constraints on the sensor network, global clock synchronization can be achieved in the presence of malicious nodes that exhibit Byzantine failures.
---
paper_title: Network-Wide Clock Synchronization via Message Passing with Exponentially Distributed Link Delays

paper_content:

Clock synchronization has become an indispensable requirement in wireless sensor networks due to its central importance in vital network operations such as data fusion and duty cycling, and has attracted considerable research interest recently. Assuming exponentially distributed random delays in a two-way message exchange mechanism, this work proposes a network-wide clock synchronization algorithm using a factor graph representation of the network. Message passing using the max-product algorithm is adopted to derive the update rules for the proposed iterative procedure. A closed form solution is obtained for each node's belief about its clock offset at each iteration. Simulation results show that the application of the proposed message passing-based network-wide clock synchronization algorithm provides convergent estimates for both regular cycle-free and random topologies. Moreover, the mean square error (MSE) performance of the proposed algorithm is also compared with the Cramer-Rao bound (CRB) for small example networks, which further highlights the effectiveness of the proposed algorithm.
---
paper_title: Distributed Clock Synchronization for Wireless Sensor Networks Using Belief Propagation

paper_content:

In this paper, we study the global clock synchronization problem for wireless sensor networks. Based on belief propagation, we propose a fully distributed algorithm which has low overhead and can achieve scalable synchronization. It is also shown analytically that the proposed algorithm always converges for strongly connected networks. Simulation results show that the proposed algorithm achieves better accuracy than consensus algorithms. Furthermore, the belief obtained at each sensor provides an accurate prediction on the algorithm's performance in terms of MSE.
---
paper_title: Fully-distributed joint clock synchronization and ranging in wireless sensor networks under exponential delays

paper_content:

In this paper, we study the global clock synchronization and ranging problem for wireless sensor networks in the presence of unknown exponential delays using the two-way message exchange mechanism. Based on the Alternating Direction Method of Multipliers (ADMM), we propose a fully-distributed synchronization and ranging algorithm which has low communication overhead and computation cost. Simulation results show that the proposed algorithm achieves better accuracy than consensus algorithm, and can always converge to the centralized optimal solution.
---
paper_title: Timestamp-free network synchronization with random pairwise message exchanges

paper_content:

This paper describes a network synchronization technique based on bidirectional message exchanges between randomly chosen node pairs without the use of timestamps. Each node in the network has a clock with independent stochastic delay and drift. Relative delay and drift synchronization information is conveyed implicitly in the physical layer through the timing of responses to directed messages. Simultaneous delay and drift correction is performed by the node initiating the message exchange. Steady-state synchronization performance bounds are developed as a function of the synchronization stepsize parameter and the statistics of the delay and drift estimation errors. Numerical results for two different connectivity scenarios show that synchronization among the nodes can be achieved without the overhead of digital timestamps, a dedicated synchronization protocol, or network hierarchy.
---
paper_title: Joint Ranging and Clock Parameter Estimation by Wireless Round Trip Time Measurements

paper_content:

In this paper, we develop a new technique for estimating fine clock errors and range between two nodes simultaneously by two-way time-of-arrival measurements using impulse-radio ultrawideband signals. Estimators for clock parameters and the range are proposed, which are robust with respect to outliers. They are analyzed numerically and by means of experimental measurement campaigns. The technique and derived estimators achieve accuracies below 1 Hz for frequency estimation, below 1 ns for phase estimation, and 20 cm for range estimation, at a 4-m distance using 100-MHz clocks at both nodes. Therefore, we show that the proposed joint approach is practical and can simultaneously provide clock synchronization and positioning in an experimental system.
---
paper_title: A New Distributed Time Synchronization Protocol for Multihop Wireless Networks

paper_content:

A distributed algorithm to achieve accurate time synchronization in large multihop wireless networks is presented. The central idea is to exploit the large number of global constraints that have to be satisfied by a common notion of time in a multihop network. If, at a certain instant, Oij is the clock offset between two neighboring nodes i and j, then for any loop i1, i2, i3 , ..., in, in + 1 - i1 in the multihop network, these offsets must satisfy the global constraint Sigma k = 1 nOik, ik + 1 = 0. Noisy estimates Ocirc ij of Oij are usually arrived at by bilateral exchanges of timestamped messages or local broadcasts. By imposing the large number of global constraints for all the loops in the multihop network, these estimates can be smoothed and made more accurate. A fully distributed and asynchronous algorithm which functions by simple local broadcasts is designed. Changing the time reference node for synchronization is also easy, consisting simply of one node switching on adaptation, and another switching it off. Implementation results on a forty node network, and comparative evaluation against a leading algorithm, are presented
---
paper_title: CUSUM algorithm for detecting translations in gamma distributions

paper_content:

The cumulative sum algorithm is developed for detecting translations of in-control gamma distributions. Efficient computing algorithms for the first two moments of the in-control and out-of-control run length distribution are provided. The special case of exponential distributions is discussed in some detail as it provides an unusual context where analytical formulae are available. The results are illustrated by applying them to a network surveillance context. Copyright © 2015 John Wiley & Sons, Ltd.
---
paper_title: Time in general-purpose control systems: the Control Time Protocol and an experimental evaluation

paper_content:

No two clocks generally agree. Distributed control applications, however, require accurate timing information. This necessitates some form of message passing for interpretation of distributed clocks. We exhibit a fundamental indeterminacy in estimating time when delays are unequal in the two directions, necessitating an assumption of symmetry. We present the Control Time Protocol as an architecturally clean algorithm for providing timing information in the domain of distributed control. The protocol introduces no additional dependencies beyond those already present in the very control loops, thus enhancing the reliability of the systems. It has been implemented on the testbed in the Convergence Laboratory at the University of Illinois. Experimental results demonstrating how time stamping can be used to enhance stability and performance, as well as measurements of network latencies, are provided.
---
paper_title: Fundamental Limits on Synchronizing Clocks Over Networks

paper_content:

We characterize what is feasible concerning clock synchronization in wireline or wireless networks. We consider a net work of n nodes, equipped with affine clocks relative to a designated clock that exchange packets subject to link delays. Determining all unknown parameters, i.e., skews and offsets of all the clocks as well as the delays of all the communication links, is impossible. All nodal skews, as well as all round-trip delays between every pair of nodes, can be determined correctly. Also, every transmitting node can predict precisely the time indicated by the receiver's clock at which it receives the packet. However, the vector of unknown link delays and clock offsets can only be determined up to an (n - 1)-dimensional subspace, with each degree of freedom corresponding to the offset of one of the (n - 1) clocks. Invoking causality, that packets cannot be received before they are transmitted, the uncertainty set can be reduced to a polyhedron. We also investigate structured models for link delays as the sum of a transmitter-dependent delay, a receiver-dependent delay, and a known propagation delay, and identify conditions which permit a unique solution, and conditions under which the number of the residual degrees of freedom is independent of the network size. For receiver-receiver synchronization, where only receipt times are available, but no time-stamping is done by the sender, all nodal skews can still be determined, but delay differences between neighboring communication links with a common sender can only be characterized up to an affine transformation of the (n - 1) un known offsets. Moreover, causality does not help reduce the uncertainty set.
---

Title: An Overview of a Class of Clock Synchronization Algorithms for Wireless Sensor Networks: A Statistical Signal Processing Perspective

Section 1: Introduction
Description 1: Introduce wireless sensor networks (WSNs), their applications, and the importance of clock synchronization in these networks.

Section 2: System Model for Pairwise Clock Synchronization
Description 2: Describe the clock model for each sensor node and the two-way message exchange mechanism for pairwise clock synchronization.

Section 3: Pairwise Clock Synchronization under Gaussian Delays
Description 3: Investigate state-of-the-art pairwise clock synchronization algorithms under Gaussian random delays.

Section 4: Pairwise Clock Synchronization under Exponential Delays
Description 4: Survey the pairwise clock synchronization algorithms in the presence of exponential random delays.

Section 5: Pairwise Clock Synchronization under Unknown Random Delays
Description 5: Discuss the signal processing techniques employed in WSNs when the random delays are unknown.

Section 6: Fully-Distributed Clock Synchronization Algorithms
Description 6: Explore synchronization algorithms that assume a fully-distributed operation.

Section 7: Conclusions and Open Problems
Description 7: Conclude the paper and provide some open research topics.