基于RTEthernet改进的时钟同步算法

以太网其庞大的网络系统在复杂的环境中存在网络链路延迟,节点时钟的漂移,同步能力差等问题。通过研究RTEthernet协议的起源和工作原理,考虑到影响实时以太网时间同步精密度的时钟拜占庭故障、网络传输延迟和漂移率等三个因素,建立了符合RTEthernet协议的通信模型。对FTA时钟同步算法在故障下时钟同步精密度损失率提升较少的问题进行了研究,引入了滑动窗口技术,提出了容错滑动窗口（Fault-Tolerant Sliding Window, FTSW）算法。容错滑动窗口算法能进一步提高分布式系统在进行时钟同步是对故障节点的容错能力。最后,使用CANoe仿真工具对FTSW算法进行仿真验证, FTSW算法的容错性优于FTA时钟同步算法算法,且在系统（七个节点）中存在两个拜占庭故障的情况下,同步后的精密度损失率降低了7.1%。     

Interval-based Clock Synchronization

In this paper, we develop and analyze a simple interval-based algorithm suitable for fault-tolerant external clock synchronization. Unlike usual internal synchronization approaches, our convergence function-based algorithm provides approximately synchronized clocks maintaining both precision and accuracy w.r.t. external time. This is accomplished by means of a time representation relying on intervals that capture external time, providing accuracy information encoded in interval lengths. The algorithm, which is generic w.r.t. the convergence function and relies on either instantaneous correction or continuous amortization for clock adjustment, is analyzed by utilizing a novel, interval-based framework for establishing worst-case precision and accuracy bounds subject to a fairly detailed system model. Apart from individual clock rate and transmission delay bounds, our system model incorporates non-standard features like clock granularity and broadcast latencies as well. Relying on a suitable notion of internal global time, our analysis unifies treatment of precision and accuracy, ending up in striking conceptual beauty and expressive power.     

具有容错性的时间同步协议算法

在无线传感器网络的许多时间同步协议中,算法的精确性、高效性以及简洁性总被优先考虑.此外,容错性时间同步协议也逐渐受到越来越多的关注,鉴于经典算法浮动时间同步协议(FTSP)较为全面地考虑了时间同步的能耗、同步精度、可扩展性等要求,提出了一种基于FTSP具有容错性的时间同步协议,算法通过对历史所测的有限个时钟漂移率进行加权平均计算新的漂移率,其中算法的加权系数根据历史测量值的方差动态确定.通过Matalab对新算法的时钟漂移率和在接收到错误信息情况下漂移率的变化进行仿真分析,结果表明:改进后的算法具有较强的容错性.     

Combination of clock-state and clock-rate correction in fault-tolerant distributed systems

This paper proposes the integration of internal and external clock synchronization by a combination of a fault-tolerant distributed algorithm for clock state correction with a central algorithm for clock rate correction. By means of hardware and simulation experiments it is shown that this combination improves the precision of the global time base in a distributed single cluster system while reducing the need for high-quality oscillators. Simulation results have shown that the rate-correction algorithm contributes not only in the internal clock synchronization of a single cluster system, but it can be used for external clock synchronization of a multi-cluster system with a reference clock. Therefore, deployment of the rate-correction algorithm integrates internal and external clock synchronization in one mechanism. Experimental results show that a failure in the clock rate correction will not hinder the distributed fault-tolerant clock state synchronization algorithm, since the state correction operates independently from the rate correction. The paper introduces new algorithms and presents experimental results on the achieved improvements in the precision measured in a time-triggered system. Results of simulation experiments of the new algorithms in single-cluster and multi-cluster configurations are also presented. Hermann Kopetz (Fellow, IEEE) received the Ph.D. degree in physics ísub auspiciis praesidentis from the University of Vienna, Vienna, Austria, in 1968. He was Manager of the Computer Process Control Department at Voest Alpine, Linz, Austria, and Professor of Computer Process Control, Technical University of Berlin, Berlin, Germany. He is currently Professor of Real-Time Systems, Vienna University of Technology, Vienna, Austria, and a Visiting Professor at the University of California, Irvine, and the University of California, Santa Barbara. In 1993, he was offered a position as Director of the Max Planck Institute, Saarbrcken, Germany. Prof. Kopetz is the key architect of the Time-Triggered Architecture. Astrit Ademaj (IEEE member) received the Dipl-Ing. degree (1995) at the University of Prishtina, Kosova, and a doctoral degree (2003) in computer science from the Technical University of Vienna. He is currently working as Assistant Professor at the Technical University of Vienna and as a Visiting Lecturer at the University of Prishtina. His research interests are design and validation of communication systems for safety-critical and real-time applications. He is a member of the IEEE Computer Society. Alexander Hanzlik received a diploma (1995) and a doctoral degree (2004) in computer science from the Technical University of Vienna. From 1995 to 1998, he was concerned with voice communication system design for air traffic control for the Service de Navigation Aérienne (STNA). Since 1998, his focus is on embedded systems in the fields of telecommunication, automation and process control. Since 2001, Dr. Hanzlik is a member of the Real-Time Systems Group and works as a research assistant at the Technical University of Vienna. His main research activities deal with fault-tolerant clock synchronization in distributed systems and simulation. Currently, he is working on SIDERA, a simulation model for time-triggered, dependable real-time architectures.     

基于概率同步算法的计算机外时钟同步系统设计与仿真

在计算机软件时钟同步系统中，网络延迟的测量与建模、同步算法的设计及算法性能的评估是要解决的三个主要问题。该文研究了基于概率同步算法的计算机外时钟同步系统设计。首先研究了基于PC高分辨计数器接口的网络延迟精确测量方法，对几种典型网络环境进行了测量，建立了网络延迟的对数正态分布统计模型。然后推导了网络延迟为对数正态分布模型下的同步包数目的计算公式，研究了基于该公式的概率同步算法参数设计。最后，对单个从节点情况下改进的概率同步算法的性能进行了仿真检验。结果表明，基于网络延迟的对数正态模型的推导和设计是正确、可靠的。改进的概率同步算法具有较高的同步效率和同步精度，可以用于实际的仿真系统。     

On the Feasibility of Time Estimation under Isolation Conditions in Wireless Sensor Networks

We study the problem of providing a sensor with an accurate estimate of the time, from a novel perspective which is complementary to the well-studied clock synchronization problem. More precisely, we analyze the case in which a sensor node is temporarily unable to run a clock synchronization protocol due to failures or intermittent connectivity, or is willing to skip one or more clock adjustments to save energy, but still requires an accurate estimate of the reference time. We propose and analyze two simple and efficient clock reading methods, one deterministic and the other probabilistic, which are designed to work in synergy with a clock synchronization protocol. Our deterministic method achieves a better time accuracy by exploiting information regarding the sign of the deviation of the hardware clock from the reference time. This algorithm leads to noticeable energy savings since it can be applied to reduce the frequency of the periodic clock adjustments by a factor of 2, while maintaining the same error bound. Moreover, our method is of theoretical interest since it shows how a stronger but realistic clock model leads to a refinement of the optimality bound for the maximum deviation of a clock that is periodically synchronized. We also propose two simple versions of this algorithm: a method that guarantees the monotonicity of the clock values, and a generalization that improves the accuracy in case of clock stability. Our probabilistic method is based on time series forecasting, and provides a probabilistically accurate estimate of the reference time with a constant error bound. It is more flexible than our previous methods since it does not depend on the frequency at which clock synchronization occurs, and can be dynamically tuned according to the application requirements and resource availability. All these methods have broad applicability for their generality. In sensor networks they can be applied to improve the clock accuracy of a sensor node in conditions of network isolation, or to reduce the frequency of the clock adjustments, thus saving energy and increasing the system lifetime.     

Synchronized UTC for distributed real-time systems

We present a novel technique for establishing a highly accurate global time in fault-tolerant, large-scale distributed real-time systems. Unlike the usual clock synchronization approaches, our clock validation technique provides a precise system time that also relates to an external time standard like UTC with high accuracy. The underlying idea is to validate time information of external time sources like GPS-receivers against a global time maintained by the local clocks in the system. As an example, a promising interval-based clock validation algorithm ICV that exhibits excellent fault-tolerance properties is outlined and analyzed. It requires only a few high-accurate external time sources and provides each node with the actual accuracy of its clock.     

Multistep interactive convergence: an efficient approach to thefault-tolerant clock synchronization of large multicomputers

We present a new approach for fault-tolerant internal clock synchronization in multicomputer systems employing not completely connected networks (NCCNs). The approach is referred to as multistep interactive convergence and is locally implemented in each multicomputer node by a time server process (TSP). We describe a specific algorithm that uses multistep interactive convergence and bases its operation on a logical mapping of the system's TSPs into an m-dimensional array. A TSP executes m steps per round of synchronization, with each step including a call to an interactive convergence procedure. For any TSP, clock readings in step i are gathered only from TSPs with which it shares a row along dimension i of the array. Hence, a TSP reads clocks only from a small subset of the TSPs in the system, which reduces the number of messages by orders of magnitude over a conventional interactive convergence algorithm in which reliable all-to-all broadcast of clock values is done. The algorithm can be used in systems of arbitrary topology and provides the added benefit of increased locality of communication in regular NCCNs such as hypercubes and tori. These advantages can be combined with a variety of message staggering mechanisms to maintain network contention at a minimum. We present expressions for the maximum clock skew, maximum clock drift, maximum clock discontinuity, and number of messages produced by the algorithm, and show that it tolerates arbitrary faults. A comparison with other algorithms that elucidates the advantages of multistep interactive convergence is also provided     

Average time synchronization in wireless sensor networks by pairwise messages

Most of previous algorithms for time synchronization choose a specific node’s (denoted as a root or leader) local time to be the reference time, which is easily disturbed by many events (e.g. root node’s power down or damage). The Gaussian distribution for the nodes’ local clocks has been reported by a few authors based on laboratory tests, the average of all nodes’ clocks is the best approximation to the ideal time. In this paper, the possibility to realize average time synchronization in wireless sensor networks by pairwise messages exchange is studied, and a simple algorithm (ATSP) is proposed, which synchronizes all the nodes’ clocks to their average. For networks with clock skew, the algorithm compensates the frequencies of nodes to their average also. Using the Lyapunov’s stability theory, convergence analyses and proofs of the algorithm are given. Synchronization error (accuracy) of the algorithm is estimated by using probability theory also, which indicates that the synchronization error of the algorithm is linearly related to the standard deviation of the message delay. Simulations are performed on a 300 nodes network to examine the performance of the algorithm, which verified the theoretical results.     

一种采用时隙对准方式的TDMA自组网同步协议

通过对TDMA方式下的同步协议STS和TISS进行研究,提出一种基于时隙对准方式的TDMA自组网同步协议MFSS。该协议以工作周期为自组网节点之间同步的标准,在节点初入网时采用双向交互和时隙对准方法,消除了传输时延误差和初始时间偏差,从而实现了快速初始同步;随后通过监测过程保证了节点之间产生的时钟漂移误差可自适应控制,同时减小了重新同步带来的开销。仿真结果证明,相比于STS协议和TISS协议,MFSS协议在同步收敛速度、同步精度以及同步开销上都取得了更好的性能。     

Reliable synchronization in distributed systems

In distributed computer systems, processors often need to be synchronized to maintain correctness and consistency. Unlike shared-memory parallel systems, the lack of shared memory and a clock considerably complicates the task of synchronization in distributed systems. The objective of this article is two-fold: (1) We present a new randomized agreement algorithm to synchronize cooperating processors in a distributed system. This algorithm achieves the desired agreement in expected five rounds of message exchanges, tolerating a maximum of one-fifth of the processors failures. The algorithm belongs to the class of broadcast-based synchronization problems. (2) We present a new self-stabilization algorithm for an acyclic directed-graph structured distributed systems. This new fault-tolerant algorithm survives all imaginable faults in distributed systems. The algorithm belongs to arbiter-based and broadcast-based synchronization problems.     

基于最小二乘法精确时钟同步算法研究与实现

在深入地研究P T P时钟同步机理的前提下,仔细分析了时钟偏差产生的原因,并引入了基于最小二乘法的频率补偿算法来校正相对时钟漂移偏差,在搭建的以太网精确时钟同步平台基础上,通过实验验证了该算法的可行性。结果表明,该算法的引人大大地提高了P T P的同步精度。     

基于最优时钟偏差的无线传感器网络同步算法

针对无线传感器网络固有的时钟偏移和时钟漂移问题,研究了不同的时间同步方法对同步精度的影响。以簇形网络结构时钟同步原理为依据提出最优时钟偏差算法,应用卡尔曼滤波方法,以最优化递归方式对成员节点的时钟偏差进行最小调整。与一般簇形同步算法进行比较发现,该算法不仅可以提高同步精度,还可以减少节点能耗。仿真结果也表明,该算法能准确地描述同步精度问题,是一种有效的时钟同步算法。     

火电厂控制系统的几种常见对时方法

随着火电厂自动化水平的迅速发展,其控制系统对时钟的精度要求也愈来愈高。本文结合徐州华润电力有限公司(简称:徐州电厂)近期控制系统时钟同步技术改造,就同步时钟原理、对时方式及改造过程中所采用的方法及特点进行介绍。     

基于连续时间戳通信模型的时钟同步

时钟同步是分布式系统、通信领域中的核心技术之一。本论文提出了在异步通信网络环境中实现时钟同步的一种新的方法,即采用连续的时间戳通信模型来构造时钟精度差模型,并根据获得的时钟精度差时钟调整。这种方法不仅能够有效的减少流量对时钟同步的影响,而其也可以进一步提高时钟同步的精度和自适应能力。     

异步环境中基于时钟精度差的时钟同步

在异步通信模型的基础上，提出了一个基于时钟精度差的时钟同步策略，并给出了一个完整的系统模型，研究的重点有3个方面：（1）在时钟同步过程中使用单向信息传输策略，可以有效地减少网络负载；（2）客户机使用本地节点的时间信息和来自于参考时钟的时间戳信息构造一个线性数学模型，并获得本地时钟与参考时钟的运行精度差；（3）根据本地节点计算出的时钟精度差，构造一个自适应的容错模型，能够保证当本地节点与参考节点的连接出现故障时，本地的时钟同步系统还能够正常工作。该文不仅给出了一个详细的数学模型，而且还在实际的Internet环境中进行了模拟试验，取得了满意的结论。     

Layered interactive convergence for distributed clock synchronization

A clock synchronization service ensures that spatially dispersed and heterogeneous processors in a distributed system share a common notion of time. In order to behave as a single, unified computing resource, distributed systems have need for a fault-tolerant, clock synchronization service. One approach employs the interactive convergence (ICV) method, which is both fully distributed and inherently fault-tolerant. However, this approach suffers from limits in terms of system scalability due to resource overhead. In this paper, a new layered form of ICV is introduced, compared with basic ICV and other simpler alternatives via experimental analysis on a distributed system testbed, and shown to improve synchronization tightness, resource utilization, and scalability.     

GPS时钟同步在水下定位系统中的应用

由于对海上搜救快速性的要求日渐提高,研制水下失事声信标快速定位系统。本文介绍了GPS高精度时钟在定位系统中的应用,包括对无线通信链路的同步和水声信号时间测量的同步。详细介绍了GPS时钟同步在Windows和DSP两种不同平台上的具体实现方法。     

仿真系统中的时钟同步算法

研究当前仿真系统中的时钟同步问题和网络时间协议（NTP）。在NTP的基础上通过引入“主从服务器”模式、客户端时间推进和事件注册机制,实现一种适用于分布式仿真系统的、具有较高精度的软件时钟同步算法,给出同步系统的设计和实验方案。根据对实验数据的分析,验证该算法是一种简单有效的高精度时钟同步算法。     

时钟同步的假设检验研究

时钟同步技术是分布式系统中非常活跃的研究领域之一,由于大多数分布式系统实际上是不同步的,因此需要采用容错时钟同步算法确保消息通信的有界延迟,而基于假设检验的时钟同步技术可以避免因错失对两个高概率不同步时钟进行同步调整而造成系统不正常使用的情况。该文讨论了时钟同步的假设检验问题。除了假设检验、两类错误概率,还给出了概率最小时钟偏差、时钟同步概率等概念。在时钟偏差的统计分布特性近似于服务正态分布的假设条件之下,提出了基于非中心t分布的时钟同步假设检验方案。最后,基于服务器和客户端之间双向消息通信传输模式,给出时钟偏差的估计和检验样本。