Tag Archives: Clock Synchronization

Clock synchronization in the CAN bus

M. Akp\u0131nar and K. W. Schmidt, Predictable Timestamping for the Controller Area Network: Evaluation and Effect on Clock Synchronization Accuracy, IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 54, no. 3, pp. 1926-1935, March 2024 DOI: 10.1109/TSMC.2023.3332559.

Accurate timestamps are important for clock synchronization (CS) and cyber-security on the controller area network (CAN). This article proposes a new predictable timestamping (TS) method on CAN. Different from existing TS methods, our method reduces the effect of uncertainties that are caused by the CAN bit timing, oscillator drifts, and different cable lengths. Accordingly, our TS method provides an improved TS quality, which is confirmed in comprehensive hardware experiments. We further show the positive impact of our TS method on CS for CAN with clock accuracies below 100 ns.

A new pose-graph optimization algorithm for SLAM and other problems whose, through a formulation as global optimization in SE(3), results are certifiable and more robust than standard approaches, and a curious relation between this problem and the clock synchronization problem

Rosen, D. M., Carlone, L., Bandeira, A. S., & Leonard, J. J., SE-Sync: A certifiably correct algorithm for synchronization over the special Euclidean group, The International Journal of Robotics Research, 38(2–3), 95–125, 2019 DOI: 10.1177/0278364918784361.

Many important geometric estimation problems naturally take the form of synchronization over the special Euclidean group: estimate the values of a set of unknown group elements x1,…,xn∈SE(d) given noisy measurements of a subset of their pairwise relative transforms x−1ixj. Examples of this class include the foundational problems of pose-graph simultaneous localization and mapping (SLAM) (in robotics), camera motion estimation (in computer vision), and sensor network localization (in distributed sensing), among others. This inference problem is typically formulated as a non-convex maximum-likelihood estimation that is computationally hard to solve in general. Nevertheless, in this paper we present an algorithm that is able to efficiently recover certifiably globally optimal solutions of the special Euclidean synchronization problem in a non-adversarial noise regime. The crux of our approach is the development of a semidefinite relaxation of the maximum-likelihood estimation (MLE) whose minimizer provides an exact maximum-likelihood estimate so long as the magnitude of the noise corrupting the available measurements falls below a certain critical threshold; furthermore, whenever exactness obtains, it is possible to verify this fact a posteriori, thereby certifying the optimality of the recovered estimate. We develop a specialized optimization scheme for solving large-scale instances of this semidefinite relaxation by exploiting its low-rank, geometric, and graph-theoretic structure to reduce it to an equivalent optimization problem defined on a low-dimensional Riemannian manifold, and then design a Riemannian truncated-Newton trust-region method to solve this reduction efficiently. Finally, we combine this fast optimization approach with a simple rounding procedure to produce our algorithm, SE-Sync. Experimental evaluation on a variety of simulated and real-world pose-graph SLAM datasets shows that SE-Sync is capable of recovering certifiably globally optimal solutions when the available measurements are corrupted by noise up to an order of magnitude greater than that typically encountered in robotics and computer vision applications, and does so significantly faster than the Gauss–Newton-based approach that forms the basis of current state-of-the-art techniques.

Interesting review of time delay measurement in one-way messages in networks at the application level

P. Ferrari, A. Flammini, E. Sisinni, S. Rinaldi, D. Brandão and M. S. Rocha, Delay Estimation of Industrial IoT Applications Based on Messaging Protocols, IEEE Transactions on Instrumentation and Measurement, vol. 67, no. 9, pp. 2188-2199, DOI: 10.1109/TIM.2018.2813798.

Information and operational technologies merge into the so-called industrial Internet of Things, which is one of the basic pillars of the Industry 4.0 paradigm. Roughly speaking, yet-to-come services will be offered in the automation scenario by industrial devices having an internet connection for sharing data in the cloud. Currently, most efforts are in the development of protocols able to ensure horizontal interoperability among heterogeneous applications. Consequently, poor attention is devoted to time-related performance. In this paper, a new, full software, platform-independent approach is proposed for experimentally evaluating the delay in transferring information across local and intercontinental routes by applications leveraging on messaging middleware. The application is realized using the node-RED web-based framework, due to its availability on different platforms; the widely accepted message queue telemetry transport protocol has been chosen thanks to its low overhead and complexity. For sake of completeness, five different, private and public, brokers are used. The adopted industrial-grade hardware, complemented by global positioning system time reference, permits an overall synchronization and timestamping accuracy of a few milliseconds. The vast measurement campaign highlighted that, generally, quality of service (QoS) type 1 offers low end-to-end delay (average value less than 0.5 s) with reduced variability (0.1 s). However, the maximum end-to-end one-way delay ranges from 1 s for QoS 0 to less than 1.5 s for fully acknowledged QoS 2.

A new algorithm that provably converges to a global clock consensus in a network

Miloš S. Stanković, Srdjan S. Stanković, Karl Henrik Johansson, Distributed time synchronization for networks with random delays and measurement noise, Automatica, Volume 93, 2018, Pages 126-137 DOI: 10.1016/j.automatica.2018.03.054.

In this paper a new distributed asynchronous algorithm is proposed for time synchronization in networks with random communication delays, measurement noise and communication dropouts. Three different types of the drift correction algorithm are introduced, based on different kinds of local time increments. Under nonrestrictive conditions concerning network properties, it is proved that all the algorithm types provide convergence in the mean square sense and with probability one (w.p.1) of the corrected drifts of all the nodes to the same value (consensus). An estimate of the convergence rate of these algorithms is derived. For offset correction, a new algorithm is proposed containing a compensation parameter coping with the influence of random delays and special terms taking care of the influence of both linearly increasing time and drift correction. It is proved that the corrected offsets of all the nodes converge in the mean square sense and w.p.1. An efficient offset correction algorithm based on consensus on local compensation parameters is also proposed. It is shown that the overall time synchronization algorithm can also be implemented as a flooding algorithm with one reference node. It is proved that it is possible to achieve bounded error between local corrected clocks in the mean square sense and w.p.1. Simulation results provide an additional practical insight into the algorithm properties and show its advantage over the existing methods.

On the effects of delays in the stability of a network controlled plant due to both clocks not being synchronized

K. Okano, M. Wakaiki, G. Yang and J. P. Hespanha, Stabilization of Networked Control Systems Under Clock Offsets and Quantization, IEEE Transactions on Automatic Control, vol. 63, no. 6, pp. 1708-1723 DOI: 10.1109/TAC.2017.2753938.

This paper studies the impact of clock mismatches and quantization on networked control systems. We consider a scenario where the plant’s state is measured by a sensor that communicates with the controller through a network. Variable communication delays and clock jitter do not permit a perfect synchronization between the clocks of the sensor and controller. We investigate limitations on the clock offset tolerable for stabilization of the feedback system. For a process with a scalar-valued state, we show that there exists a tight bound on the offset above which the closed-loop system cannot be stabilized with any causal controllers. For higher dimensional plants, if the plant has two distinct poles, then the effect of clock mismatches can be canceled with a finite number of measurements, and hence there is no fundamental limitation. We also consider the case where the measurements are subject to quantization in addition to clock mismatches. For first-order plants, we present necessary conditions and sufficient conditions for stabilizability, which show that a larger clock offset requires a finer quantization.

A novel fast algorithm for clock synchronization in a wireless network, with a nice introduction but assuming negligible communication times and thus not directly applicable in teleoperation

Kan Xie, Qianqian Cai, Minyue Fu, A fast clock synchronization algorithm for wireless sensor networks, Automatica, Volume 92, 2018, Pages 133-142, DOI: 10.1016/j.automatica.2018.03.004.

This paper proposes a novel clock synchronization algorithm for wireless sensor networks (WSNs). The algorithm is derived using a fast finite-time average consensus idea, and is fully distributed, meaning that each node relies only on its local clock readings and reading announcements from its neighbours. For networks with an acyclic graph, the algorithm converges in only d iterations for clock rate synchronization and another d iterations for clock offset synchronization, where d is the graph diameter. The algorithm enjoys low computational and communicational complexities and robustness against transmission adversaries. Each node can execute the algorithm asynchronously without the need for global coordination. Due to its fast convergence, the algorithm is most suitable for large-scale WSNs. For WSNs with a cyclic graph, a fast distributed depth-first-search (DFS) algorithm can be applied first to form a spanning tree before applying the proposed synchronization algorithm.

Time synchronization (only offset) or power sinusoid signals

A. Mingotti, L. Peretto and R. Tinarelli, Accuracy Evaluation of an Equivalent Synchronization Method for Assessing the Time Reference in Power Networks, IEEE Transactions on Instrumentation and Measurement, vol. 67, no. 3, pp. 600-606, DOI: 10.1109/TIM.2017.2779328.

This paper deals with the evaluation of the accuracy performance of an approach for assessing the phase displacement between voltages at power network nodes. This task is accomplished by processing asynchronous measurements taken at each node. This turns into an equivalent synchronization, which is, therefore, obtained without exploiting any synchronization signals, such as the ones provided by means of wireless (i.e., global positioning system) or wired technologies. As a matter of fact, distribution system operators will gain the possibility of deploying, at more affordable costs, wide area measurement system (WAMS) over their power networks for enhancing their stability and reliability. Phasor measurement units (PMUs) are the most common examples of such WAMS, but, besides their high cost, there are circumstances where providing a time reference signal to remote PMUs often becomes a difficult task. This paper aims at recalling the basic theoretical principles of the method and at proving its applicability in power network through a deep analysis of its metrological performance.

A framework for the performance analysis of collaborative network clock synchronization

Y. Xiong, N. Wu, Y. Shen and M. Z. Win, Cooperative Network Synchronization: Asymptotic Analysis, IEEE Transactions on Signal Processing, vol. 66, no. 3, pp. 757-772, DOI: 10.1109/TSP.2017.2759098.

Accurate clock synchronization is required for collaborative operations among nodes across wireless networks. Compared with traditional layer-by-layer methods, cooperative network synchronization techniques lead to significant improvement in performance, efficiency, and robustness. This paper develops a framework for the performance analysis of cooperative network synchronization. We introduce the concepts of cooperative dilution intensity (CDI) and relative CDI to characterize the interaction between agents, which can be interpreted as properties of a random walk over the network. Our approach enables us to derive closed-form asymptotic expressions of performance limits, relating them to the quality of observations as well as the network topology.

Simultaneous localization and clock synchronization (apparently only offsets are estimated) in wireless networks

Y. Liu, Y. Shen, D. Guo and M. Z. Win, Network Localization and Synchronization Using Full-Duplex Radios, IEEE Transactions on Signal Processing, vol. 66, no. 3, pp. 714-728, DOI: 10.1109/TSP.2017.2770090.

Both localization and synchronization of mobile nodes are important for wireless networks. In this paper, we propose new methods for network localization and synchronization (NLS) using full-duplex radios through only two frames of transmission. Specifically, all nodes simultaneously transmit their signature signals in the first frame, while receiving others’ signals via full-duplex radios. In the second frame, nodes transmit either scrambled versions of their received signals in the first frame or a digital packet of the channel parameter estimates of the received signals. We develop distributed algorithms to estimate the arrival times of different components in the received signals. These arrival times are then used to determine the local network geometry and clock offsets. The Cramér-Rao lower bounds for internode distances and clock offsets are derived, and the former can be translated into error bounds of the node positions. Compared with conventional frequency division duplex or time-division duplex, we demonstrate the high efficiency of NLS using full-duplex radios, revealing its potential beyond data communications in future wireless networks.

Clock synchronization in a wireless network based on consensus method that takes into account the noise (uncertainty) in the system, with a nice related work about consensus-based network clock synchronization

Jianping He, Xiaoming Duan, Peng Cheng, Ling Shi, Lin Cai, Accurate clock synchronization in wireless sensor networks with bounded noise, Automatica, Volume 81, July 2017, Pages 350-358, ISSN 0005-1098, DOI: 10.1016/j.automatica.2017.03.009.

It is important and challenging to achieve accurate clock synchronization in wireless sensor networks. Various noises, e.g., communication delay, clock fluctuation and measurement errors, are inevitable and difficult to be estimated accurately, which is the main challenge for achieving accurate clock synchronization. In this paper, we focus on how to achieve accurate clock synchronization by considering a practical noise model, bounded noise, which may not satisfy any known distributions. The principle that a bounded monotonic sequence must possess a limit and the concept of maximum consensus are exploited to design a novel clock synchronization algorithm for the network to achieve accurate and fast synchronization. The proposed algorithm is fully distributed, with high synchronization accuracy and fast convergence speed, and is able to compensate both clock skew and offset simultaneously. Meanwhile, we prove that the algorithm converges with probability one, which means that an accurate clock synchronization is achieved. We further prove that the probability of the complete synchronization converges exponentially fast. Experiments and simulations are conducted to verify the noise model and demonstrate the effectiveness of the proposed algorithm.