计算机测量与控制!"#""!$#!$"!
!"#$%&'()'*+%('#',&-!",&(".!
!
#""+
!#
收稿日期 "#"%#+%'$!修回日期 "#"%%#"#%
基金项目 国家自然科学基金!'%&*###$"$上海市自然科学基金项目!%)N.%*"+$##"%
作者简介 陈佳佳!%++'"&男&江苏南通人&硕士&主要从事分布式实时系统*实时以太网*深度学习方向的研究%
张凤登!%+($"&男&上海人&博士生导师&教授&主要从事现场总线技术*汽车电子学等方向的研究%引用格式 陈佳佳&张凤登&张宇辉!基于.<`:R F C6F：改进的时钟同步算法'1(!计算机测量与控制&"#""&$ #!$")""+"$$&"'%!
文章编号 %('%*)+& "#"" #$#""+#)!!2/3 %#!%()"( 4!5678!%%9*'(" :;!"#""!#$!#$&!!中图分类号 <=$+$文献标识码 >基于/5W&3'(,'&改进的时钟同步算法
陈佳佳 张凤登 张宇辉
!上海理工大学光电信息与计算机工程学院&上海!"###+$"
摘要 以太网其庞大的网络系统在复杂的环境中存在网络链路延迟&节点时钟的漂移&同步能力差等问题$通过研究.<`:R F C6F：协议的起源和工作原理&考虑到影响实时以太网时间同步精密度的时钟拜占庭故障*网络传输延迟和漂移率等$个因素&建立了符合.<`:R F C6F：协议的通信模型$对a<>时钟同步算法在故障下时钟同步精密度损失率提升较少的问题进行了研究&引入了滑动窗口技术&提出了容错滑动窗口!a<0S&X G A Y::D Y F C G6:I Y8\86H T86\D T"算法$容错滑动窗口算法能进一步提高分布式系统在进行时钟同步是对故障节点的容错能力$最后&使用L>O D F仿真工具对a<0S算法进行仿真验证&a<0S算法的容错性优于a<>时钟同步算法算法&且在系统!'个节点"中存在两个拜占庭故障的情况下&同步后的精密度损失率降低了'?%i% 关键词 .<`:R F C6F:$a<0S$以太网$拜占庭故障$时钟同步
J#$("D'4!."2Z17,23(",8`*&8",6.F"(8&3#;*+'4",/5W&3'(,'&
L M`O18G48G&N M>O Pa F6H\F6H&N M>O P U A R A8
!05R D D Y D X/;:85G Y36X D C K G:8D6G6\L D K;A:F C`6H86F F C86H&0R G6H R G8V68W F C I8:J D X<F5R6D Y D H J&0R G6H R G8!"###+$&L R86G"
6:+&(*2&)`:R F C6F:T8:R8:IR A H F6F:T D C7I J I:F KR G I;C D E Y F K I D X6F:T D C7Y867\F Y G J&\C8X:D X6D\F5Y D57I G6\;D D C I J65R C D68^G] :8D65G;G E8Y8:J86G5D K;Y F B F6W8C D6K F6:!Z J I:A\J86H:R F D C8H86G6\T D C786H;C8658;Y F D X.<`:R F C6F:;C D:D5D Y&G5D K K A685G:8D6K D\]
F Y5D6X D C K86H:D.<`:R F C6F:;C D:D5D Y8I F I:
G E Y8I R F\5D6I8\F C86H:R C F F X G5:D C I I A5R G I5Y D57Z J^G6:86F X G A Y:I&6F:T D C7:C G6I K8I I8D6\F]
Y G J IG6\\C8X:C G:F I&:R G:G X X F5::R F;C F58I8D6D X C F G Y]:8K F`:R F C6F::8K F I J65R C D68^G:8D6!<R F;C D E Y F K:R G::R F a<>5Y D57I J65R C D68^G] :8D6G Y H D C8:R KR G I Y F I I8K;C D W F K F6:865Y D57I J65R C D68^G:8D6;C F58I8D6Y D I I C G:F A6\F C X G A Y:8I I:A\8F
\&:R F I Y8\86H T86\D T:F5R6D Y D H J 8I86:C D\A5F\&G6\:R Fa G A Y:]<D Y F C G6:0Y8\86H S86\D T!a<0S"G Y H D C8:R K8I;C D;D I F\!<R Fa G A Y:]<D Y F C G6:0Y8\86H S86\D TG Y H D C8:R K 5G6X A C:R F C8K;C D W F:R F X G A Y::D Y F C G65F D X:R F\8I:C8E A:F\I J I:F K:D:R F X G A Y:J6D\F IT R F65Y D57I J65R C D68^G:8D68I;F C X D C K F\!a86G Y Y J& :R Fa<0S G Y H D C8:R K8I I8K A Y G:F\A I86H:R FL>O D F I8K A Y G:8D6:D D Y:DW F C8X J:R G::R Fa<0SG Y H D C8:R K8IK D C F X G A Y:]:D Y F C G6::R G6:R F a<>5Y D57I J65R C D68^G:8D6G Y H D C8:R K&G6\86:R F5G I F D X:T DZ J^G6:86F X G A Y:I86:R F I J I:F K!I F W F66D\F I"&:R F;C F58I8D6Y D I I C G:F G X] :F C:R F I J65R C D68^G:8D6\F5C F G I F I E J'?%i!
<'7="(4+).<`:R F C6F:$a<0S$F:R F C6F:$E J^G6:86F X G8Y A C F$5Y D57I J65R C D68^G:8D6
>!引言
.<`:R F C6F:!.F G Y]<8K F`:R F C6F:"是一种可以兼容传
统以太网协议的实时以太网%.<`:R F C6F：在以往的物理层
和数据链路层之上增添了会话层&并且使用了0通信循环1
的概念来分时传输实时性消息和非实时性消息%
国外在时钟同步理论研究的起步是比较早的%%+'&年&
@F I Y8F@G K;D C：在文献'%(中提出了逻辑时钟的概念&逻
辑时钟这一概念的提出给内部时钟同步技术的发展提供了
前提条件&通过在分布式实时系统内部建立一个虚拟的全
局时间来实现各个节点之间的时间同步%
"##*年&,D;F:^等人在其著作'"(中提出了将状态
同步与速率同步相结合的方法&并对主从式&非主从式同
步进行了实验%实验表明&将状态同步与速率同步相结合
能有效提高同步的精密度%对于不同的系统模型*同步精
密度要求和容错能力等方面&衍生出了各种各样的时钟同
步算法%综合远程时钟读取技术*算法容忍故障类型*系
统通信模型等方面&可将算法大致分成了三类'$*()确定
性*概率型和统计型%
通过对.<`:R F C6F：协议通信原理及其基础时钟同步算
法进行了研究&并且考虑拜占庭故障对系统时钟精密度的
影响&引入了滑动窗口技术来提升时钟同步算法容错性&
提出了具有更高容错性的时钟同步算法555滑动窗口时钟
同步算法%
!系统结构及原理
@?!/5W&3'(,'&体系结构
.<`:R F C6F：是保留了传统`:R F C6F：的物理层和数据链
!
投稿网址 T T T!4I45Y J7^!5D K
!!
计算机测量与控制!第$#""""""""""""""""""""""""""""""""""""""""""""""""""""
卷
#"$#!#路层的实时以太网%在这个基础上引进了0全局时间1的概念&同时还用了30/+/03参考模型的会话层进行报文的再封装%.<`:R F C 6F ：不仅可以兼容传统以太网&而且可以通过用时分多路访问!<2->&:8K F\8W 8I 8D 6K A Y :8;Y FG 5]5F I I "的通信方式进行基础报文的传送&提高了传统以太网的实时性和安全性%30/+/03*`:R F C 6F ：和.<`:R F C 6F ：的体系结构如图%所示
%
图%!30/+/03*`:R F C 6F ：和.<`:R F C 6F ：的体系结构
信道间隔@A !/5W &3'(,'&通信结构.<`:R F C 6F ：协议以确定性定时通信为基础&其通信方法是基于周期性重复的循环通信%因此&需要提前建立循环通信和时间窗口的大小&.<`:R F C 6F ：的整体情况表示如图"所示%图中的矩阵从宏观上展现了.<`:R F C 6F ：的工作原理
%
图"!.<`:R F C 6F ：通信原理
A !同步时钟的概念及I 56算法
A @?!时钟同步
时钟同步算法的主要目标是要保证处理器的时钟差异不超过某个定值%在保证一定时钟同步精度的前提下&降低节点在时钟同步过程中的能量消耗&延长节点的生命周期是设计时钟同步算法的首要考虑%保证分布式系统中各个节点的时钟彼此同步成为保证分布式系统实时性的基础%A @A !误差来源
分布式实时系统中的节点需要交换各自的时钟信息来实现建立全局时间%它们通过通信网络连接&在发送和接
受各自本地时钟时都需要一个真实存在的处理时间%因此在时钟同步中需要考虑通信延迟的存在&不然将会直接影响到最终算法的性能%而且节点中的处理器*时钟*通信的链路等组件都有可能发生故障%故障主要可以分成七类&其中最重要的是时钟拜占庭故障%分布式系统中的任意节点都有可能遭遇某一种故障或几种故障混合&这时我们称该节点为故障节点&否则称之为无故障节点%文中考虑的是一般性故障和最恶劣情况!拜占庭故障&如图$所示"下的情况%若分布式系统可以通过某时钟同步算法容忍最恶劣情况下的故障&则说明这个算法是有效的%时钟同步算法的容错性主要体现在系统对拜占庭故障节点的容忍性这方面
%
图$!时钟拜占庭故障
A @
B !时钟同步的衡量指标
为了衡量系统中各个时钟的行为是否达到同步&引入了准确度:*时钟偏差%和精密度；这几个指标来衡量%偏差%)具有相同分辨率的两个时钟在同一单位微节拍上的偏移&即两个时钟速率的相对差&表示为)
%)
8I &K E !J #)8"6E !J #)I "
K !%"!!在上式中&
)表示微节拍$时钟8&I 在第)个微节拍上的偏差用%)8I 来表示$E !J #)8"和E !J #)
I "分别表示时钟
8&I 在第)个微节拍上对应的时钟微节拍数%精密度;)在给定的真实时间间隔'+%&+"(内&任意两个时钟
间的最大偏差&表示为)
;)&K
G B 2%)
8I 4!""!!把有限时间间隔上的最大;)称为时钟集合的精密度%
如果精密度;)小于某个期望值&就表示系统的内部各个节点之间相互同步&反之&就没有达到同步%
准确度:)在某段真实时间段内时钟8相对于参考时
钟E 的偏差&用:8)表示%
:8
)&K G B K $8!)#)
8"6$E !)
#)
8"K !$
"!!其中)$8!)
#)
8"表示时钟8在第)个微节拍的长度&$E !)
#)8"表示时钟8在第)个微节拍上对应参考时钟的微节拍数%某时间段内外部参考与给定时钟时钟的最大偏差常用时钟的准确度来衡量%
A @C !I
56算法传统的容错算法a <>容错均值算法是通过对修正项进
钢铁冶金设备维护!
投稿网址 T T T!4I 45Y J
7^!5D K
第$期
陈佳佳&等)基于.<`:R F C 6F :""""""""""""""""""""""""""""""""""""""""""""""""""""
改进的时钟同步算法#"$%!#
行筛除提高修正项的准确性%a <>算法是一种单轮算法&能够对不一致的信息进行处理&避免因为信息不一致引入的错误%该算法是从传统的0平均技术1发展而来的&并且在其中融入了去除极值的思想&于是形成了基础的时钟同步算法&a <>算法在一定基础上提高了分布式系统时钟同步的容错性&算法过程如图*所示
%
图*!a <>算法同步过程
B !滑动窗口时钟同步算法
B @?!滑动窗口技术
滑动窗口是一种流量控制技术%在早期的网络通信中&通信双方没有考虑网络的拥堵情况而直接发送数据导致了中间结点阻塞丢包&双方都不能发送数据&所以就有了滑动窗口机制来解决此问题
')(
%后来&由这一技术衍化而来
的滑动窗口算法不仅大量运用到了通信领域&在其他各个领域之中也得到了广泛地应用&例如图像处理&轨迹预测及其他进行数据预测*优化的领域%滑动窗口算法和滑动窗口技术是一样的&只是应用的场景不一样&可以根据需
要调整窗口的大小&也可以固定窗口的大小'((
%
滑动窗口技术是在给定的特定窗口大小的数组或字符串上执行要求的操作%该技术可以将一部分问题中的嵌套循环转变为一个单一循环&因此它可以减少时间复杂度%下面举例简单说明滑动窗口技术的原理%如图)所示&我们假定有一组数)9"&$&%&)&*&#&'&%&9%&求出波动最小相邻的*个元素%因此&我们将窗口大小设定为*&当滑动窗口每次划过数组时&计算当前滑动窗口中所有
元素的方差%图)可以方便看出滑动窗口技术可以用来解决一些满足一定条件的连续区间的问题%由于区间的连续性&当区间发生变化时&可以通过既有的计算结果对搜索空间进行裁剪&从而减少了重复计算&节省了时间%B @A !容错滑动窗口算法的描述
根据文中对容错能力的改进&下面以为伪代码的形式描述第8轮同步中节点7使用容错滑动窗口算法进行时钟同步的过程)
%
"函数及符号的定义&见表%
)图)!滑动窗口示例表%!伪代码参数
符号
说明
'容忍的故障节点数
"1)'1(
节点1在第)轮时钟同步时读取的所有时钟差值
数列
#1Y M7
表示节点1当前的逻辑时钟值
N T T 1)
!
U "表示1节点收到节点U 的时钟值!用时钟1度量"
N %C 1
)
节点1在第)轮时钟同步的校正项#1)
第)轮中1节点应该发送同步消息的逻辑时刻
#)
表示进入第)轮的逻辑时钟值
/A =-A ,/!"1)"将数列"1)
降序排列的函数
/)=-8E /!"1)"
表示去掉"1)
中'
+"个最大值与最小值的函数(A /)8,!"1)"
求数列"1)
中值的函数
G 8E )8,-A !"1)"
求数列"1)方差的函数
7.'1(表示第.个含有'个元素的数列B 1)'1(/)=-8E /!/A =-A ,/!"1)'1(
""Q '.
(存放滑动窗口计算出的方差数列Q (8D
表示方差最大的窗口元素组成的数列
J ^%!"1)"表示求数列"1)
中值的函数
E A =+!"&B "
冗余性
获取集合"中B 集合的补集
=A ,/!"发送时钟值函数Q 7N .!
"确定滑动窗口中元素的函数
"
"算法描述算法)容错滑动窗口算法输入)重同步时间
输出)本地节点即将应用的校正项
%!S R 8Y F <7O
/Sf<8\
D +'当任一节点当前的逻辑时钟进入第8轮的循环时开始准备时钟同步'+
"!>..78!7"f<7O
/S +
+每个节点记录当前的时钟值$!8X <7O /Sf<78
:
R F 6+'如果任一节点的时钟值等于重同步时间&则将自己的时钟值发送给其他所有节点'+
*!I F 6\!K F I I G H
F "$)!=78'7(f >..78
!
e "(!F 6\8X
'!8X <7O
/Sf<O
3<8:R F 6!
投稿网址 T T T!4I 45Y J
7^!5D K
!!
计算机测量与控制!第$#""""""""""""""""""""""""""""""""""""""""""""""""""""
卷
#"$"!#&!d 78'7(f \8I 5G C \!\F I 5F 6\!=78
'
7(""++将获取到的时钟值进行降序排列&然后去掉X +"个最大和最小的值
+!T R 8Y F 4%69"X _%:R F 6++获取所有窗口内的方差%#!S 4'7(f 0S>4!
d 7
8
空中舞星
'7("%%!0'4(f W G C 8G 65F !S 4'7("%"!F 6\
%$!-`2fK F \8G 6!C F I :!d 78
'7(&0K
G B ""++获取方差最大集合的补集&然后求得该补集的中值
%*!>2178f<78
9-`2_8++计算校正项%)!C F :A C 6!>2178
"
%(!F 6\8X %'!F 6\T R 8Y F
上述过程概括的来说&可将算法分为*个阶段)时钟值收集阶段*去极值阶段*滑动窗口阶段和求中值阶段%分布式实时以太网将通信的循环划分为了静态段*动态段和O 3<；段%每个节点在通信循环中O 3<；的开始时刻执行a <0S 算法&如图(所示
%
图(!O 3<；段的a <0S 算法
下面将分别介绍a <0S 算法的各个阶段%
%
"时钟值收集阶段)所有要参与时钟同步的节点在通信循环的静态段时隙的开始处&通过通信帧帧头的第*位&向时钟集合中的所有其他参与者表明它将发送是同步帧&
该同步帧的作用是参与网络的同步'
'(
%然后利用静态段发送的同步帧测量时间偏差来得到每个节点的时钟估计值&并存储在一个数列中&然后将数列中的时钟值按照降序排列&如图'所示
%
图'!时钟值收集阶段
每个节点时钟在第E 轮的重同步&可将得到的时钟值构造成一个时钟值矩阵&我们以节点1为例&节点1保存该矩阵的列和对角线上的元素%
8E
1&
D E
%&
%
D E
%&1
D E
"&"D E
"&1
#
#
D E 1&1
##
D E ,&1
D E ,&78
9
:
,!*
"!!对于无故障时钟有)
D E )&1&D E )&)*!%E )&1*/A
"!%6.)&1"
!)"!!其中)%E )&1表示时钟
)和时钟1之间的差异$/A
表示估计的消息延迟$
.!
)&1"&%!!如果!!)&1#!!如果!!)E 2
1
!!"
"去极值阶段)将5E
1中的第1列时钟值按照降序排列后去除'+"个最大和'+"个最小的时钟值&其中'表示
系统能够容忍的最大故障时钟个数
%
图&!去极值阶段
$
"滑动窗口阶段)滑动窗口的大小为'&并且'为该系统能够容忍的故障节点数%该窗口从去极值后的时钟值序列的最左端开始&也就是第一个窗口是由第'+"_%个元素至第$'+"个元素组成的%然后&将窗口逐元素的向右滑动&直至窗口的最右边元素为第,9'+"个元素&即去极值后序列中的最右边元素%在这个过程中&一共得到了,9"'_%个窗口的数据集%最后&从这,9"'_%个数据集中到方差最大的窗口&如图+所示
%
图+!滑动窗口阶段
*
"求中值阶段)利用滑动窗口阶段得出了方差最大的时钟值集&然后将这些时钟值剔除&最后对剩余的时钟值进行求中值&从而减轻时钟拜占庭故障对最终校正项的影响%
上述算法概括的来说&先将远程读取到的时钟值进行降序排列&然后去除'个极端值!'
+"个最大值和最小值"&当'是奇数时将去除的极大值个数向上取整&去除的极小值个数向下取整%然后&对剩余的时钟值利用滑动窗口的
思想求出方差最大的窗口&然后得到其补集%最后求取该补集的中值&若此时补集为偶数时求取中间两个值的均值&然后对该中值向下取整%最终&利用简单的代数运算就可以求得本地时钟的校正项%
从算法的实现上来讲&容错滑动窗口算法在a <>算法的基础上采用了容错中值的思想并且增加了求最大方差窗口的过程&这一过程有效地提高了系统的容错能力&这是
!
投稿网址 T T T!4I 45Y J
超级解霸30007^!5D K
第$期
陈佳佳&等)基于.<`:R F C 6F :""""""""""""""""""""""""""""""""""""""""""""""""""""
朗琴h3000改进的时钟同步算法#"$$!#
该算法的显著特点%
C !算法仿真验证
C @?!系统模型的构成
实验用'个节点组成一个总线型的拓扑结构&该网络中的各个节点模拟.<`:R F C 6F ：协议进行通信%
将节点$和(设置成拜占庭故障节点&把%&"&*&)&'节点设置成无故障节点&如图%#所示为仿真系统拓扑结构
%
图%#!仿真系统拓扑结构
C @A !系统参数设置
根据文献'&%#(研究成果和.<`:R F C 6F ：通信模型对局部参数进行设置)系统中各节点初始同步的精密度设置为;),+f"
#l%#9(I &各个节点的最大时钟漂移率为$f %#9*I
&系统中传输延迟最小的为)l %#9(I &延迟最多的为%#l %#9(I %即设置分布式系统内的消息传输延迟范围为')&%#("
I &因此该系统传输延迟的不确定度为"?)l %#9(I &消息延迟范围的中间值为.f '?)l %#9(
I
%然后&考虑每个循环中包含了0<；段和2U O 段以及O 3<；段&将重同步周期长度设置为)K I
%节点参数设置如表"所示%表"!系统节点参数
节点时钟初始值+"I 时钟偏移率+"I 宏节拍长度+"I 微节拍长度+"I O-=+个同步帧发
送时刻+"
I %"#$)*%**#")*#*#!)&&#$#+#*""%"#*%"
$#*#!""#%(#)&")*#!*%#"##(%#'#**%"*#'
%(
"#
*
#!&
)
"&#
C @B !仿真结果分析
根据上述系统拓扑结构和参数的设置&本文将实验分为两部分&第一部分是无拜占庭时钟故障情况下对a <>和a <0S 算法进行收敛性验证&第二部分是存在拜占庭故障情况下对a <>和a <0S 算法进行容错性验证&运行结果如下)
%"当'f #与系统初始精密度;),+f
"#"I 时&系统中的各个节点分别执行a <>算法和a <0S 算法&最终将每次同步后系统的精密度绘制为如图%%所示%
图%%!无拜占庭故障情况下两种算法的
时钟同步精密度对比
从图%%可以看出&该系统中的各个时钟通过时钟同步算法进行过周期性的时间校正后&系统的时钟精密度会趋于稳定&并且当无拜占庭故障时钟的时候a <>算法大于a <0S 算法%当考虑到传输延迟的误差后&a <0S 算法的平均精密度约为""?"&"I &a <>算法的平均精密度约为"$?%)
"I %由此可以看出&在此系统中无拜占庭故障的情况下&原始算法的精密度还是比较优异的%
""当'f %&"和系统初始精密度;),+f "#"I 时&系统中的各个节点分别执行a <>算法和a <0S 算法&对a <>算法和a <0S 算法进行比较分析和容错性验证%
由图%"可以看出&当系统中节点$发生拜占庭故障时&经过a <>算法同步后该系统精密度为"*?*'"I &当系统中的节点$和(同时发生拜占庭故障时&该系统的精密度为"(?$""I %由此可以发现&在一个由'个节点组成的系统中&当系统中存在两个拜占庭故障的时候&a <>算法的容错能力大大降低&系统的精密度下降了%$?'i %
图%"!出现拜占庭故障情况下两种算法的
时间同步精密度对比
此实验是在时钟同步过程中通过环境变量控制一个节点!节点$"或者两个节点!节点$和("&使其产生'#&"##(之间的随机数!单位为"I "作为该节点的本地时间信息封装到同步帧并发送到网络&试图干扰其他节点的时间同步&但该节点自身真实的本地时间还是保持原来微节拍计数器的正常计数值%从图%"可以看出&当一个节点发生拜占庭故障时&该系统的精密度为""?%)"I &当系统中两个节点同时发生拜占庭故障的时候&该系统的精密度为"$?')"I
%!下转第"'%页"
!
投稿网址 T T T!4I 45Y J
7^!5D K
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议