一种星载计算机自稳定容错时间同步算法*

冯 丹，江耿丰，刘 波，衣学慧，刘超伟

(北京控制工程研究所，北京 100190)



一种星载计算机自稳定容错时间同步算法*

冯 丹，江耿丰，刘 波，衣学慧，刘超伟

(北京控制工程研究所，北京 100190)

提出一种新的时间同步方法，将软同步和硬同步结合，通过单机间的信息交互完成时间同步.单机之间通过初始化同步建立初始同步状态，然后进入同步保持状态.当单机由于临时故障失去同步后，可通过同步搜索算法自恢复与其他单机的同步.本算法可应用于多机热备份体系结构的星载计算机的时间同步中，用于提高系统的自恢复能力.

自稳定；容错；时间同步

0 引 言

多机冗余热备份是星载计算机通常采用的一种提高系统可靠度的方式.对于离散的冗余热备份计算机，需要采用时间同步机制使各个离散单机之间保持时间同步.

自从1985年Lamport等[1]提出在拜占庭故障下保持时间同步的理论以来，时间同步一直是离散式分布系统的重要研究部分之一.时间同步可按照同步源和同步模式进行分类.

从同步源来说，分为外部公共同步源和无外部同步源系统内自同步两种方法.公共同步源通过一个统一的外部时钟公共源对各个单机进行时间同步，此方法可以简化分布式系统内部的交互逻辑，但是对公共同步源的可靠度提出了很高的要求.公共时钟源硬件设计复杂且不适用于规模较大的系统.无外部同步源系统内自同步通过系统内单机的互相联系(硬件或软件联系)使系统内的单机时间在一定范围内保持一致，此方法不受限于外部公共源，且算法灵活，可分别适用于全连接或不全连接网络、大型网络等，但其算法比较复杂.

从同步模式分类，时间同步主要包括硬件同步、软件同步和混合同步3种[2].

硬件同步主要采用压控振荡器通过锁相环完成互相同步[2].采用硬件时间同步的优点在于系统具有较高的同步精度，缺点在于对网络的连接性能和硬件锁相环提出了较高的需求，增加了网络硬件成本.

软件同步主要通过系统内单机互相交换时间完成时间校正[2].时间校正算法主要包括：平均收敛算法、非平均收敛算法和连贯性算法等[3].其中，Lamport等[1]于1985年提出平均收敛算法，通过其他单机反馈的时间平均值校正本地时间；Lamport等[4]于1988年提出抛弃最大最小可能错误后取中值的算法.在此基础上，Pfluegl等[5]在1995年采用滑动窗口法判断取中值范围，提高了系统容错能力；Dolev等[6]在2004年讨论了通过跳频实现自建立同步算法.软件同步的优点在于系统灵活，硬件成本低，缺点在于由于时延和处理协议导致的同步精度低[7].目前在网络分布系统中应用最为广泛的是IEEE1588协议[8]，通过网络中的主机广播时间戳的方式同步其他从机，协议简单且在对称网络中可屏蔽延时导致的误差.

混合算法是在硬件算法和软件算法的基础上，在同步精度、网络连接形式、硬件成本和算法复杂性之间互相取舍，以达到的折中效果.

1 同步算法

本文针对的研究对象为星载计算机，星载计算机经常采用热备份多机的方式实现系统冗余，要求时间同步具有精度高、可靠性高和硬件资源开销低的特点.

本文提出一种自稳定容错时间同步算法，基于软硬件混合算法，通过单机之间的信息交互完成时间同步.该算法具有同步精度较高(可优于us量级)、可靠性较高(可以容忍多重故障)和软硬件消耗较低的特点，尤其适用于星载计算机的时间同步.此自稳定容错时间同步算法包括初始同步、同步锁定和同步搜索3个部分.

设系统内单机数量为N，系统内最大可能出错的单机数目为M(N≥4M，N和M为整数).则该方法建立于双向传输时间相等的全连接网络，可适用于系统内单机数量为N的容错系统，具备可容忍最多数目为M的单机任意故障的容错能力，具备在故障单机恢复后使其自主重新加入系统的能力，可靠性较高.该算法中各机保持地位平等互相通信，不依赖于主机广播时间或外部公共脉冲，提高了系统可靠性，避免了主机或公共脉冲故障对系统时间的影响.

N=4的全连接架构示意如图1所示：

图1 N=4网络连接架构Fig.1 Net connection of N=4

系统设置如下：

(1)设系统内存在单机数目为N，N为不小于4的整数；

(2)设置系统内最多数目为M的单机出现故障，其中N≥4M；

(3)系统时间设为t；

(4)t时刻离散化后对应单机N的本地时间为Tn(k)，k为正整数；

(5)由于采用了初始同步，为化简公式，设置系统起始时间为0；

(6)单机N以周期T对外广播初始同步信息CN和同步信息SN；

(7)各单机采用三线制同步串口完成全连接，包括门控、时钟和数据.

1.1 初始同步

为了避免单机在初始运行时产生较大的时间回卷或跳变，需要单机在加电运行后建立初始同步.传统的软件同步算法大多建立在初始同步已经建立的基础上.传统算法多通过单机同时加电或者外部输入的同步复位信号保持单机初始同步.

由于星载计算机多机常采用遥控指令依次加电的方式，且电源建立时间存在偏差，不能保证单机同时启动.因此，本文设计了不依赖于外部输入且能容忍一定加电启动时间间隔(时间偏差小于Ω)的初始同步算法.

本算法设置了初始同步算法的有效时间窗口[0, 2Ω]，实际使用中Ω通常设置为秒量级.在初始同步时间窗口之内，通过多机之间相互广播初始同步信息进行初始同步，算法如下：

(1)单机上电后在[0,Ω]时间内以周期T对外广播初始同步信息码CN；

(2)单机在[0, 2Ω]时间内对接收的“初始同步信息码”进行有效性判断，确认有效后认为本机仍处于初始信息同步状态，对本地时间计数器进行复位；

(3)多机在[0, 2Ω]内将最后到来的“初始同步信息码”作为启动本地时间计数器的基准；

(4)如果单机在[0, 2Ω]时间内均未发现其他单机的“初始同步信息”，则以2Ω时间为基准启动本地时间计数器；

(5)单机对2Ω时间以后的“初始同步信息码”认为无效，不作响应.

初始同步流程如图2所示.

图2 初始同步流程Fig.2 Initializing synchronization

根据上述算法，多机均以有效时间[0,Ω]内最后启动的单机的最后一次“初始同步信息码”作为本地时间计数器的基准启动计数器，可以满足多机之间的初始时间同步.该初始同步算法可以不受系统中错误单机数目不大于M的约束，使任意数目正常启动的单机保持初始同步，并且不受2Ω时间以后启动单机的初始同步的影响.2Ω时间以后启动的单机初始不能和系统保持同步，将通过后续的同步搜索与系统保持同步.

1.2 同步锁定

同步锁定是指初始同步建立或者同步搜索成功状态下的同步保持行为，由硬件同步和软件同步组成.其中硬件同步建立在硬件边沿精确测定的基础上，具有较高的同步精度.软件同步建立在软件协议同步的基础上，可防止单机由于宇宙环境辐照的单粒子事件或复位所导致的时间跳变.在软件同步和硬件同步结合的基础上对精度和硬件资源进行折中，可满足星载计算机对性能和硬件资源的需求.自稳定容错时间同步算法的软硬件结合的同步锁定算法，流程主要包括同步信息的广播、同步信息的接收处理和本地校时3个方面.

(1)同步信息的广播

本地时间的产生包括硬件生成的时间当量(周期为T)和软件在时间当量的基础上进行的时间计数K(K为正整数).

设置T为同步周期.在同步定时时刻TN=KT(K为正整数)来临时，单机N对外广播同步码.同步码包括帧头、本地时间信息SN、校验和帧尾等信息，用于软件同步.对外广播的三线制同步串口的门控信号起始边沿与本单机TN时刻对齐，用于硬件同步.

(2)软件同步和硬件同步的接收

同步信息的接收包括软件同步的接收和硬件同步的带容差接收.设置时间容差为±Y.

在具有容差的同步定时时刻[KT-Y，KT+Y]内，单机N接收包括自己在内的所有单机的同步串口S1-SN信息，[KT-Y，KT+Y]范围外的广播信息被认定为无效.

硬件接收方面：单机N通过硬件锁存有效同步串口的门控信号到来的准确本地时间，设置单机1～N 在门控信号到来时本机计数得到的时间为Δ1,Δ2,…,ΔN.

软件接收方面：软件通过帧头帧尾和校验码判断信息有效性，接收同步串口传输的同步码Q1,Q2,…,QN并存储.

(3)本地校时

本地校时分为硬件同步校时和软件同步校时两种.

硬件同步校时通过(2)中计算的时间Δ1,Δ2,…,ΔN精确调整硬件的时间当量计数器.将 Δ1～ΔN进行大小排序，抛弃M个最大值和M个最小值，生成新序列σ1,σ2,…,σN-2M.求其平均值，并将本地时间修正.以p单机为例，则修正为：

(1)

考虑到系统全连接之间的最大路径延迟为θ和单机硬件接收同步串口的硬件偏差为ε，单机得到的结果为：

(2)

当硬件计数器从T-Y跨越到T+Y时，产生计数当量脉冲，可保证硬件时间计数不会由于时间调整多产生或少产生当量脉冲，保证软件计时的正确性.

软件同步主要保证出现临时故障的单机能够进行修正软件时间计数值K.因此，软同步校时算法对同步码Q1,Q2,…,QN进行比较.抛弃最多M错误的同步码，通过类似的平均算法选举出正确的软件计算时间，如果本地时间与选举时间不同，将本地时间修改为选举时间.

各单机使用的晶振存在一定的精度偏差和时间漂移，设置漂移率最大偏差为ρ.

在单机具备初始同步的背景下，在T时间内，正确单机之间时间偏差小于ρT.设置时间容差为ΔT：

ΔT=θ+ε+ρT

(3)

因此，在k时刻，任意不出现故障的单机p和q(p、q均为整数，小于N)可保证时间差在

2ΔT误差内，即

(4)

在下一时刻K+1，修正前的

|Tp(k+1)-Tq(k+1)|

=|Tp(k)-Tq(k)+(ρp-ρq)T|<4ΔT

(6)

按照修正公式，修正后的结果

(7)

(9)

由于系统最大容忍M重故障，因此序列σpi和σqi中最多有M个序列不一致，且：

|σpi-σqj|<4ΔT，i∈N，j∈N

(10)

(11)

即K+1时刻校正后的时间也能保持p和q单机时间差在2ΔT内.该算法可保证时间同步，系统最大时间偏差为：

2ΔT=2(θ+ε+ρT)

(12)

1.3 同步搜索

在自稳定容错时间同步算法的算法中，保持同步状态的单机由于临时故障(单粒子翻转、单机复位等)脱离同步状态后，可通过同步搜索与与其他单机重新建立同步，进入同步系统，使系统具备一定的自恢复能力.同步搜索算法包括同步状态判断和同步搜索跟踪两个状态.

(1)同步状态判断

单机通过[KT-Y，KT+Y]时间内收到其他单机有效时间信息的个数L判断本单机是否与其他单机保持一致.如果在L≥N-M，则表示单机处于保持同步的状态；如果L≤M，则表明单机处于失锁状态.如果单机处于失锁状态，则通过同步跟踪搜索重新建立本单机与其他单机的锁定.

(2)同步搜索跟踪

失锁后的单机不再限定接收其他单机时间信息的时间窗口[KT-Y，KT+Y]，而改为在全时间范围内观测其他单机的时间信息.当发现有H(H>M)个单机的时间同步信息出现的时间差在2ΔT范围内，则以这些单机的时间平均值校正本地时间，参照本地校时中的算法，将M1-MK按照多数选举法则选出的时间码修改本地时间，抛弃M个最大最小值后的平均值修正本地精确时间，完成同步搜索跟踪.

2 系统仿真

对上述算法进行仿真.参数设置如下：

a)N=4M

b)ρ为随机数，其中ρ最大为15×10-5

c)ε为绝对值小于200 ns的系统误差

仿真不同同步周期条件下最大的时间偏差，如图3所示，由仿真结果可知，在N≥4M条件下，均能满足系统时间偏差在2ΔT内.同步周期越小系统时间偏差越小，考虑到软硬件资源和时间精度，T通常取ms量级，ε<<ρT、δ<<ρT.

图3 同步周期-时间偏差仿真图Fig.3 Time difference with different synchronization period

仿真不同N和M进行设置，仿真得到算法系统同步精度如图4所示.由仿真结果可知，M越小系统精度越好，在N≥4M条件下系统同步精度小于2ΔT.

图4 系统单机数目-同步精度仿真图Fig.4 Relationship between the amount of computer and the synchronization precision

3 结 论

本文提出了一种时间同步方法，通过单机之间的信息交互完成时间同步.单机之间通过初始化同步保持初始同步状态，然后进入同步保持状态.当单机由于临时故障失去同步后，可通过同步搜索算法恢复与其他单机的同步，一定程度上提高了系统的自恢复能力，可应用于星载计算机的时间同步中.

[1] Leslie L, MelliarS. Synchronizing clocks in the presence of faults[J]. Journal of the ACM,1985, 32(1): 52-78.

[2] Todd A A. A network element based fault tolerant processor[D]. Massachusetts Institute of Technology, 1988.

[3] Ramanathan P, Shin K G. Fault-tolerant clock synchronization in distributed systems[J]. Computer, 1990, 23(10): 33-44.

[4] Lundelius J, LynchN. A new fault-tolerant algorithm for clock synchronization[J]. Information and Computation,1988,77(1): 1-36.

[5] Pfluegl M J, Blough DM.A newandimprovedalgorithmforfault-tolerantclocksynchronization[J]. Journal of Parallel and Distributed Computing，1995, 27(1): 1-14.

[6] Dolev S, Welch JL.Self-stabilizing clock synchronization in the presence of Byzantine faults[J]. Journal of the ACM, 2004, 51(5): 780-799.

[7] Lenzen C,Locher T,Wattenhofer R. Tight bounds for clock synchronization[J]. Journal of the ACM, 2010, 57(2): 1-42.

[8] Ouellette M, Ji K, Liu S, Li H. Using IEEE 1588 and boundary clocks for clock synchronization in telecom networks[J]. IEEE Communications Magazine: Articles, News, and Events of Interest to Communications Engineers, 2011, 49(2): 164-171.

[9] John C S, Benjamin P K, James W C, Hasan B. Clock synchronization on the RAX spacecraft[J]. Acta Astronautica, 2014, 98(5-6): 111-119.

A Self-Stabilization Fault-Tolerant Time-SynchronizationAlgorithm for an On-Board Computer

FENG Dan, JIANG Gengfeng, LIU Bo, YI Xuehui, LIU Chaowei

(Beijing Institute of Control Engineering， Beijing 100190， China)

A new time-synchronization algorithm is presented, which combines software synchronization and hardware synchronization. Time synchronization is achieved via information interchange between two computers. With this algorithm, initial time synchronization is established among different stand-alone computers after initial synchronizing process. And then the systemmaintainsthe synchronized state. If one of the computers falls out of the synchronism due to temporary fault, it can autonomously synchronize with other computers with the algorithm. This algorithm is applicable for the time synchronization of multiple hot redundant on-board computers, and improvesthe self-recovery ability of the system.

self-stabilization； fault-tolerant； time synchronization

*总装备部预研资助项目(513200704).

2015-03-17

V446

A

1674-1579(2015)06-0058-05

10.3969/j.issn.1674-1579.2015.06.011

冯 丹(1983—)，女，工程师，研究方向为高可信容错空间计算机；江耿丰(1982—)，男，工程师，研究方向为空间综合电子系统等；刘 波(1977—)，男，研究员，研究方向为星载容错计算机；衣学慧(1978—)，男，高级工程师，研究方向为星载容错计算机；刘超伟(1982—)，男，高级工程师，研究方向为星载容错计算机。