1、2023 年第 36 卷第 3 期Electronic Sci.Tech./Mar.15，2023h t t p s:/j o u r n a l.x i d i a n.e d u.c n收稿日期:2021-08-31基金项目:国家自然科学基金(71840003);上海市自然科学基金(15Z1429300)National Natural Science Foundation of China(71840003);NaturalScience Foundation of Shanghai(15Z1429300)作者简介:陆禹(1997 )，男，硕士研究生。研究方向:分布式实时系统、车载总线。
2、张力(1996 )，男，硕士研究生。研究方向:分布式实时系统。张凤登(1963 )，男，博士，教授。研究方向:分布式实时系统、汽车电子与现场总线。基于灰色预测容错时钟同步算法陆禹，张力，张凤登(上海理工大学 光电信息与计算机工程学院，上海 200093)摘要针对分布式实时系统中无主式时钟同步存在时钟拜占庭故障和节点通信链路丢失故障的问题，文中提出一种基于灰色预测容错时钟同步算法。该算法基于广播式通信网络 LL 模型，使用 GM(1，1)的灰色预测方法对前轮次的校正偏差值进行分析，从而预测出该节点在故障伦次中的校正偏差值，再通过计算得到修正值。实验结果表明，文中提出的灰色预测算法能够容忍拜占庭故
3、障，同时可克服节点通信链路丢失故障带来的问题，提升了 FTA 算法的普适性。通过数据对比分析结果表明，该算法的时钟同步精密度相比于原始算法提高了 24 3%;相较于其他算法，文中算法在复杂度上也有一定的优势。关键词分布式实时系统;无主式;时钟同步;拜占庭故障;通信链路丢失故障;灰色预测;容错;校正偏差值中图分类号TN913;TP311文献标识码A文章编号1007 7820(2023)03 029 07doi:10.16180/ki.issn1007 7820.2023.03.005Fault Tolerant Clock Synchronization Algorithm Based on G
4、rey PredictionLU Yu，ZHANG Li，ZHANG Fengdeng(School of Optical Electrical and Computer Engineering，University of Shanghaifor Science and Technology，Shanghai 200093，China)AbstractIn view of the problem of clock Byzantine failure and node communication link loss failure in thenon master clock synchroni
5、zation in the distributed real time system，a fault tolerant clock synchronization algo-rithm based on gray prediction is proposed in this study The proposed algorithm is based on the LL model of the broad-cast communication network，and uses the gray prediction method of GM(1，1)to analyze the correct
6、ion deviation valueof the previous round，so as to predict the correction deviation value of the node in the failure order，and then obtainthe correction value through calculation The experimental results show that the gray prediction algorithm proposed inthis study can tolerate Byzantine faults，and a
7、t the same time，it can overcome the problems caused by the failure ofnode communication link loss，and improve the universality of the FTA algorithm The data comparison analysis resultsshow that the clock synchronization precision of this algorithm is improved by 243%when compared with Original algo-
8、rithm At the same time，the algorithm complexity has certain advantages when compared with other algorithmsKeywordsdistributed real time system;non master;clock synchronization;Byzantine failure;communica-tion link loss failure;gray prediction;fault tolerant;correction deviation随着计算机信息化高速发展，各种网络化系统大都
9、可以对数据进行自我采集和处理。分布式系统作为典型的网络化系统，其研究也受到越来越广泛的关注1。随着分布式系统复杂度和规模的增大2，为系统分配的节点数目也不断增多，系统发生故障的概率也越来越高。面对目前有严格要求的实时系统，确保高精度的时钟同步是避免故障且维持系统有效控制和精确运行的必要条件之一3。在满足时钟同步的前提下，系统还需要具有一定的容错性4 6，使得分布式系统在其中几个节点出现断线时，仍然可以保持正常节点的时钟同步。目前，国内外研究人员已经提出了许多基于节点双向交换各自时钟信息的时钟参数估计算法来解决时钟同步中的精度问题，并取得了一定成果7 11。文献 12 通过将卡尔曼滤波算法和自然
10、选择粒子群算法结合，提高了无线传感器网络的时钟同步精度。本文主要致力于研究经典分布式系统内部时钟同步算法在运行过程中遇到的通信链路丢失故障的解决方案，并基于此提出一种可以容忍该故障的灰色预测容错时钟同步算法。92Electronic Science and Technology陆禹，等:基于灰色预测容错时钟同步算法h t t p s:/j o u r n a l.x i d i a n.e d u.c n1系统模型描述本文采用广播式通信网络 LL(Lundelius Lynch)模型13，并将时钟状态修正和时钟速率修正相结合。该模型在每轮次中重复执行时钟同步算法，其节点仅在特定时刻发送与时间相
11、关的消息，有效降低了获取时间节点消息的通信成本。从有关 Cristian 和 LL 模型的研究中可知，基于远程时钟读取技术时钟的最大估算误差为 2d(1+2)2()，而基于初始同步的时钟检测技术时钟的最大估算误差为2(+)14。其中，d 表示以 A 节点时钟为基础所测量的 A 节点发送与 B 节点回复过程的总路程的一半，为时钟漂移率，为可能存在的通信延迟的中值，为通信延迟的一个细微不确定度，为一个先验的固定值，表示初始时刻节点间的同步程度。由于LL模型不需要请求 回复机制，所以它的通信开销更小。对于远程时钟读取模型而言，由于节点之间不是点对点地发送消息，所以一定程度上增大了读取时钟的误差，但是
12、在广播式网络中可避免此类问题。该模型对重同步周期 TP 及节点的初始状态有一定要求，下面对模型进行条件假设。1.1条件假设采用模型分析算法时，需对模型进行一定条件的假设，这样才可以合理地分析算法的性能。本文将分布式系统中所有节点用集合 P 表示，每一个节点进程pi P 都对应一个用 Hpi表示的本地时钟。具体假设如下文所述:假设 1假设本地时钟漂移率处在一个合理范围内，即一个极小的常数 0。本文定义在任意真实时间 t 时，本地时钟 Hpi(t)与 都存在如下关系1(1+)dHpi(t)dt(1+)(1)式中，Hpi(t)表示 i 节点在真实时间 t 时对应的本地时钟值;表示 i 节点的本地时钟
13、漂移率;假设 2系统内节点间消息通信延迟有界，也就是节点之间通过任何链接发送、传输、接收任何消息所产生的通信延迟 Td在范围 ，+内。即Td ，+(2)当该假设成立时，时钟同步算法保证了系统中各个节点之间的最大逻辑时间偏差值在一定范围内，也就是精密度;假设 3分布式系统中故障节点有限，设定系统中故障节点数不能超出系统总节点数的三分之一n 3f+1(3)式中，n 表示系统中所有节点的总数目;f 表示系统中拜占庭故障节点的数目;假设 4为了更加容易地分析流程，可以忽略消息处理产生的延迟;假设 5节点在系统开始工作的初始时间点为T0，A 节点在初始时间点的真实时间为 CA(T0)，B 节点在初始时间
14、点的真实时间为 CB(T0)。系统的正常工作节点在初始时间点时同步在一个固定先验范围内，表达式为CAT0()CBT0()(4)式中，为一个先验的固定值;A 和 B 为系统中可正常工作的节点。假设6时钟同步时，A节点在发送自身节点时钟消息时，其余正常工作节点和 A 节点处在同一轮次中。因为系统需要进行重复的时钟同步，因此要对重同步周期 TP 做出以下的假设TP 2(1+)(+)+(1+)max，+(5)且TP /4 /(+)2 2(6)若没有特殊指明，本文的其它假设与前提条件都与 LL模型一致。1.2模型具体应用单个节点通过广播的方式将自己的时钟信息发送给其它各个节点15。系统的时钟同步是一个重
15、复的周期性过程，可以将逻辑时钟用轮次的形式表示时钟同步过程。每一轮次中，时间的总长度 L 是恒定不变的，一轮次中有 k 个宏时隙，则表达式如式(7)所示。L=k ng(7)式中，ng 表示系统全局时间的一个宏时隙长度。由于时钟同步是周期性过程，因此其长度同样要满足上述重同步周期的条件。每轮要留出固定长度的时间作为修正段，例如 Flexay 网络中通常称为 NIT(Net-work Idle Time)段16，节点的时钟逻辑时间在 NIT 段内进行时钟状态修正和时钟速率修正。本文用 4 个节点在完全同步的状态下作为示范说明第 i 轮的结构，节点的相关参数如表 1 所示。表 1 节点参数表Tabl
16、e 1 Node parameters节点晶振微时隙长度NMUM宏时隙长度NIT 段长度A5 MHz02 s5 个1 s1 sB2 MHz05 s2 个1 s1 sC2 MHz05 s2 个1 s1 sD1 MHz10 s1 个1 s1 s03陆禹，等:基于灰色预测容错时钟同步算法Electronic Science and Technologyh t t p s:/j o u r n a l.x i d i a n.e d u.c n图 1 理想状态下第 i 轮状态图Figure 1 State diagram of the i round in an ideal state在轮次 i 中，4 个节点都不在同一个同步时刻，分别为 TiA、TiB、TiC、TiD。当本地时间到达各自的同步时刻时，就发送同步消息。例如A节点在TiA时发送同步消息MA，B 节点一旦收到 MA，就在 B 节点的本地时钟上记录下观测的该时刻 TiAB。表 1 中，NMUM(Number ofMini slots in Unit Macro slot)表示单位宏时隙内微时隙的个数，各节点在第 i 轮情况如图1 所
