单向延迟测量中时钟动态性检测算法

延迟是评价网络性能的重要指标,也是进行其他网络性能指标测量的基础.基于全球定位系统(GPS)的端到端(end-to-end)时钟同步是测量网络单向指标的常用方法,但是其代价昂贵且缺乏灵活性.在无端到端时钟同步机制下进行网络单向延迟指标测量的关键是消除时钟偏差效应的影响.基于对时间序列分段技术的分析,提出了一种新的时间序列分段标准与改进的分段算法,实现序列的自动聚类,其时间复杂度为O(N²).将该算法应用于检测端到端时钟的动态性,识别测量过程中时钟跳变和时钟频率调整位置,实现对网络单向延迟的测量,弱化了同类工作中对时钟动态性的严格假设.同时提出了基于滑动窗的在线实时时钟动态性检测算法.实际测试实验表明,该算法是行之有效的.     

Wait-Free Clock Synchronization

Multiprocessor computer systems are becoming increasingly important as vehicles for solving computationally expensive problems. Synchronization among the processors is achieved with a variety of clock configurations. A new notion of fault-tolerance for clock synchronization algorithms is defined, tailored to the requirements and failure patterns of shared memory multiprocessors. Algorithms in this class can tolerate any number of napping processors, where a napping processor can fail by repeatedly ceasing operation for an arbitrary time interval and then resume operation without necessarily recognizing that a fault has occurred. These algorithms guarantee that, for some fixed k, once a processor P has been working correctly for at least k time, then as long as P continues to work correctly, (1) P does not adjust its clock, and (2) P's clock agrees with the clock of every other processor that has also been working correctly for at least k time. Because a working processor must synchronize in a fixed amount of time regardless of the actions of the other processors, these algorithms are called wait-free. Another useful type of fault-tolerance is called self-stabilization: starting with an arbitrary state of the system, a self-stabilizing algorithm eventually reaches a point after which it correctly performs its task. Two wait-free clock synchronization algorithms are presented for a model with global clock pulses. The first one is self-stabilizing; the second one is not but it converges more quickly than the first one. The self-stabilizing algorithm requires each processor's communication register contents to be a part of the processor's state. This last requirement is proven necessary. A wait-free clock synchronization algorithm is also presented for a model with local clock pulses. This algorithm is not self-stabilizing. Received December 20, 1993; revised January 1995.     

无线传感器网络中带延时的一致性时间同步

针对无线传感器网络(WSNs)中节点间通信存在传输延迟,影响同步精度的情况,将加权平均应用于相对时钟斜率的计算,提出了一种带延时的一致性时间同步算法.该算法中每个传感器节点通过与邻居节点通信交换时钟信息,根据一致性理论更新时钟参数,从而到达时间同步的目的.研究了在假定传输延时服从正态分布的情况下对一致性时间同步算法的影响,提出的算法降低了延时对同步精度的影响,Matlab仿真验证了该算法的有效性.     

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.     

IEEE 1588v2基于透明时钟的误差分析与修正

针对时间同步过程中出现积聚性错误,导致同步精度降低的问题,通过对误差来源和透明时钟工作原理的分析,结合IEEE 1588v2时间同步协议的延时请求应答机制和对等延时机制,归纳了一整套基于透明时钟的频率补偿和误差修正方法。测试结果表明,经过频率和相位的双重调节,主从时钟的同步精度可以达到亚微秒级别,完全满足高精度同步系统的要求。     

传输时延和时钟同步对以太网控制系统的影响

在分析报文传输时延和时钟同步精度对EPA网络(工业以太网)控制系统的实时性和稳定性的影响的基础上, 提出了新的基于马尔科夫链的时延模型. 给出了在系统稳定的情况下, 通信宏周期、协议传输时延和时钟同步精度应满足的条件. 建立了无丢包情况下的EPA网络控制系统模型. 提出了EPA控制系统稳定时, 可以设置的最小通信宏周期的计算方法.     

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.     

SAE AS6802协议研究及模块化仿真平台设计

分析安全关键领域的时间触发网络协议SAE AS6802与时间同步算法技术,分别对同步流程、时间同步角色、时序保持算法、集中控制算法、时钟纠正算法、同/异步派系检测算法以及通道择优方法等进行研究,归纳时间同步精度的影响因素。在此基础上,设计一种时间同步算法IP核,并构建基于SystemVerilog的模块化仿真验证平台。利用该平台对时间同步算法进行RTL级仿真,结果验证了该时间同步算法的正确性,其同步精度保持在亚微秒级,满足下一代高安全关键领域的应用要求。     

A clock synchronization algorithm for the performance analysis of multicomputer systems

The paper deals with the implementation of global time in multicomputer systems. After a formalization of the synchronization problem, techniques to estimate the synchronization delay and to compensate the drift error are proposed. Then SYNC_WAVE, a clock synchronization algorithm where the values of a reference clock are diffused in a wave-like manner, is described. SYNC_WAVE has no provision for fault-tolerance and is specially designed to introduce low CPU and communication overhead, in order to support performance analysis applications efficiently. An implementation of the devised algorithm in a transputer-based system is presented, showing the accuracy results obtained. Finally SYNC_WAVE is compared to other synchronization algorithms and several of its possible applications are suggested.     

基于控制角度的无线传感器网络时钟同步优化算法

针对无线传感器网络(WSN)时间同步过程中易受干扰,易发生通信延迟所造成的同步精度不高、收敛速度不快的问题,从控制的角度提出一种时钟同步优化算法。该算法首先建立时钟同步状态模型,然后通过现代控制理论的思想,引入中心控制策略,建立基于控制的时间同步状态模型。该控制策略是通过全局的时钟状态信息进行设计,在卡尔曼滤波最优估计前提下,使控制满足使性能指标函数最小的条件下,得到最优控制。仿真结果表明,所提出的时钟同步优化算法和无线传感器时钟同步协议(TPSN)相比,从第6步时钟同步开始,前者的同步误差逐渐比后者的同步误差小;在实现同一较高精度的同步需求时,前者需要的同步次数是后者所用的同步次数的20%左右;由时钟同步误差收敛均值的方差对比值显示,前者比后者的同步误差均方差小了两个数量级,因此所提出的时钟同步优化算法比时钟同步协议同步精度高、收敛速度快、网络通信负荷低。     

实时分布式仿真测试平台时钟同步算法

针对Cristian算法和Berkeley算法同步时间精度不高的缺陷,提出一种基于反射内存的网络时钟同步算法。该算法通过计算出准确的延迟得到较精确的漂移率,并采用渐入渐出的同步冗余策略来确定较精确的同步周期和同步方式。实验测试结果证明,与Cristian算法相比,该算法的时间精度更高。     

Low-complexity time synchronization for energy-constrained wireless sensor networks: Dual-Clock delayed-message approach

Due to the ability of sensor nodes to collaborate, time synchronization is essential for many sensor network operations. With the aid of hardware capabilities, this work presents a novel time synchronization method, which employs a dual-clock delayed-message approach, for energy-constrained wireless sensor networks (WSNs). To conserve WSN energy, this study adopts the flooding time synchronization scheme based on one-way timing messages. Via the proposed approach, the maximum-likelihood (ML) estimation of time parameters, such as clock skew and clock offset, can be obtained for time synchronization. Additionally, with the proposed scheme, the clock skew and offset estimation problem will be transformed into a problem independent of random delay and propagation delay. The ML estimation of link propagation delay, which can be used for localization systems in the proposed scenario, is also obtained. In addition to good performance, the proposed method has low complexity.     

The Optimization of Control Parameters: Finite-time and Fixed-time Synchronization of Inertial Memristive Neural Networks with Proportional Delays and Switching Jumps Mismatch

This thesis’s object is inertial memristive neural networks (IMNNs) with proportional delays and switching jumps mismatch. Different from the traditional bounded delay, the proportional delay will be infinite as t → ∞. The finite-time synchronization (FN-TS) and fixed-time synchronization (FX-TS) can be realized with the devised controllers for the drive-response systems (D-RSs). Along with the Lyapunov function and some inequalities, the synchronization criteria of D-RSs are given. This paper presents an optimization model with minimum control energy and dynamic error as objective functions, aiming to obtain more accurate and optimized controller parameters. An intelligent algorithm: particle swarm optimization with stochastic inertia weight (SIWPSO) algorithm is introduced to solve the optimization model. Meanwhile, an integrated algorithm for selecting optimal control parameters is presented as well. In this method, the optimal control parameters and the setting time of synchronization can be obtained directly. At last, some simulations are presented to verify the theorems and the optimization model.

     

一种双参数拓扑推测方法

针对采用单一性能参数推测网络拓扑结构算法的问题, 如有效性与网络负载有关以及测量节点性能参数时大多需要节点间时钟的同步等, 在现有的测量方法基础上, 提出了一种不需要节点间时钟同步可以测量端到端时延抖动和丢包相关性的紧接分组对序列测量方法, 同时设计了一种综合端到端时延抖动和丢包相关性的双参数拓扑推测算法, 该算法能够适应不同的网络负载环境。最后通过NS-2仿真实验验证了该算法的有效性和准确性。     

基于频率校正的触发型传感器网络同步算法

通过对现有时钟同步算法的分析,为消除触发型同步算法中时钟频率偏差对同步误差的影响,提出一种基于频率校正的触发型传感器网络同步算法。该算法中基站监测事件发生时,相关传感器节点通过线性回归计算时钟晶振频率偏差,通过同步信令的交互,估算往返时延和时间差值。仿真结果表明,该算法能达到良好的同步精度。     

Delay Optimization in Quorum Consensus

The management of replicated data in distributed database systems is a classic problem with great practical importance. Quorum consensus is one of the popular methods, combined with eager replication, for managing replicated data. In this paper we investigate the problems of delay-optimal quorum consensus. Firstly, we show that the problem of minimizing the total delay (or mean delay) restricted to a ring can be solved in a constant time in contrast to the existing approximation results. Secondly, we show that the problem of minimizing the total delay (or mean delay) is NP-hard. Thirdly, we present an approximate algorithm with an approximate ratio 2; and the approximate algorithm can guarantee the exact solutions for some specific network topology, such as trees and meshes. Finally, we present an improvement on the existing algorithm to solve the problem of minimizing the maximal delay; this reduces the time complexity from O(n ³ log n) to O(n ³) where n is the number of nodes.     

Delay Optimization in Quorum Consensus

The management of replicated data in distributed database systems is a classic problem with great practical importance. Quorum consensus is one of the popular methods, combined with eager replication, for managing replicated data. In this paper we investigate the problems of delay-optimal quorum consensus. Firstly, we show that the problem of minimizing the total delay (or mean delay) restricted to a ring can be solved in a constant time in contrast to the existing approximation results. Secondly, we show that the problem of minimizing the total delay (or mean delay) is NP-hard. Thirdly, we present an approximate algorithm with an approximate ratio 2; and the approximate algorithm can guarantee the exact solutions for some specific network topology, such as trees and meshes. Finally, we present an improvement on the existing algorithm to solve the problem of minimizing the maximal delay; this reduces the time complexity from O(n ³ log n) to O(n ³) where n is the number of nodes.     

具有O(n)消息复杂度的协调检查点设置算法

协调检查点设置及回卷恢复技术作为一种有效的容错手段,已广泛地运用在集群等并行/分布计算机系统中.为了进一步降低协调检查点设置的时间和空间开销,提出了一种基于消息计数的协调检查点设置算法.该算法无须对底层消息通道的FIFO特性进行假设,并使同步阶段引入的控制消息复杂度由通常的O(n²)降低到O(n),有效地提高了系统的效率和扩展性.     

基于指数时延的无线传感器网络时钟同步估计

无线传感器网络的时间同步是无线传感器网络的一个重要的研究方向.本文利用时钟偏移量误差的规律性,提出基于指数时延的无线传感器网络时钟同步估计算法.本算法是一种基于发送者同步模型,在DMTS算法的基础上引入指数时延得到的.理论与仿真实验都证明本算法对时钟偏移量的估计是相合的,同时实验还证明本算法比DMTS算法具有更高的精度和稳定性.     

EPA网络控制系统丢包分析

针对基于时钟同步技术的时分调度网络控制系统工作方式,分析了基于EPA协议的网络丢包原理.建立在不同实时性要求情况下EPA网络系统的丢包模型,并且分析了时钟偏差抖动为马尔科夫链时,通信周期、时间片长度以及时钟同步精度对系统稳定性的影响.提出了提升EPA系统实时性的方法.最后对EPA系统的稳定性进行了分析.