RTEthernet中改进的FTA时钟同步算法研究

doi:10.16180/j.cnki.issn1007-7820.2023.01.010

摘要/Abstract

摘要：

针对以太网存在节点时钟漂移、网络链路延迟、同步能力差等问题,文中基于RTEthernet协议的通信原理,构建了时钟同步系统的模型。文中研究了RTEthernet的组成、工作原理,考虑了影响实时以太网时钟同步精密度的三大因素:漂移率、网络传输延迟和时钟拜占庭故障,并基于此分析了原始的FTA时钟同步算法,发现它在拜占庭故障增多的情况下容错性能明显降低,进而引入“容错中值”的思想进行改进并提出了RTE-FTM算法。通过CANoe仿真平台,对系统(7个节点)中存在2个拜占庭故障与不存在拜占庭故障进行对比分析。结果表明系统的精密度损失率降低了3.1%,并由此验证了该算法的收敛性和有效性。

关键词: 以太网, RTEthernet, 漂移率, 网络传输延迟, 时钟拜占庭故障, 容错中值, RTE-FTM, 收敛性

Abstract:

In view of the problems that node clock drift, network link delay and poor synchronization ability in Ethernet, this study constructs a clock synchronization system model based on the communication principle of RTEthernet protocol. By studying the composition and working principle of RTEthernet, three factors affecting the time synchronization precision of real-time Ethernet-drift rate, network transmission delay and clock Byzantine fault are considered. Based on this, the original FTA clock synchronization algorithm is analyzed, and it is found that its fault tolerance performance is obviously reduced when Byzantine faults increase. The idea of " fault-tolerant midpoint " is introduced to improve it and RTE-FTM algorithm is proposed. Through the CANoe simulation platform, two Byzantine faults and no Byzantine faults in the system (seven nodes) are compared and analyzed, and the precision loss rate of the system is reduced by 3.1%, which verifies the convergence and effectiveness of the algorithm.

Key words: Ethernet, RTEthernet, drift rate, network transmission delay, clock for Byzantine failure, fault-tolerant midpoint, RTE-FTM, convergence

中图分类号:

TP393

张宇辉,张凤登,张海涛. RTEthernet中改进的FTA时钟同步算法研究[J]. 电子科技, 2023, 36(1): 67-74.

ZHANG Yuhui,ZHANG Fengdeng,ZHANG Haitao. Research on Improved FTA Clock Synchronization Algorithm in RTEthernet[J]. Electronic Science and Technology, 2023, 36(1): 67-74.

图/表 9

图1

图2

图3

图4

表1

伪代码参数"

符号	说明
f	容忍的故障节点数
$P q i$	节点q在第i轮时钟同步时读取的所有时钟差值数列
$T q N O W$	表示节点q当前的逻辑时钟值
AD $J q i$	节点q在第i轮时钟同步的校正项
$T q i$	第i轮中q节点应该发送同步消息的逻辑时刻
Tⁱ	表示进入第i轮的逻辑时钟值
descend ( $P q i$ )	将数列 $P q i$ 降序排列后的数列
throw ( $P q i$ )	表示去掉 $P q i$ 中f个最大值与最小值后的数列
median ( $P q i$ )	求数列 $P q i$ 中值的函数
MED	MED( $P q i$ )
GET[q]	存放获取到的时钟值数列
send ()	发送时钟值函数

表1

图5

表2

图6

图7

参考文献 19

[1]	Lamport L, Melliar-Smith P M. Synchronizing clocks in the presence of faults[J]. Journal of the ACM, 1985, 32(1):52-78. doi: 10.1145/2455.2457
[2]	何万里, 隋江华, 任光. 时钟同步算法的分析和比较[J]. 计算机工程与应用, 2004(34):51-53.
	He Wanli, Sui Jianghua, Ren Guang, Analysis and comparison of synchronization algorithms[J]. Computer Engineering and Applications, 2004(34):51-53.
[3]	赵永发, 周磊. 一种分布式时钟同步系统设计[J]. 无线电工程, 2016, 46(10):8-11.
	Zhao Yongfa, Zhou Lei. Design of a distributed clock synchronization system[J]. Radio Engineering, 2016, 46(10):8-11.
[4]	陈旿, 孙建华, 高小杰, 等. 一种基于平均场的无线自组织网络时钟同步方法[J]. 计算机学报, 2016, 39(5):893-904.
	Chen Wu, Sun Jianhua, Gao Xiaojie, et al. A clock synchronization method for Ad Hoc networks based on mean field[J]. Chinese Journal of Computers, 2016, 39(5):893-904.
[5]	张凤登, 朱长昊, 李明. 等. 一种适用于实时以太网的会话层帧格式设计:CN,201911413504.5[P].[2019-11-04].
	Zhang Fengdeng, Zhu Changhao, Li Ming, et al. A session layer frame format design for real-time Ethernet: CN,201911413504.5[P].[2019-11-04].
[6]	张凤登. 分布式实时系统[M]. 北京: 科学出版社, 2014.
	Zhang Fengdeng. Distributed real time system[M]. Beijing: Science Press, 2014.
[7]	耿石强. GPS/BDS实时动态相对定位算法研究与实现[D]. 阜新: 辽宁工程技术大学, 2016
	Geng Shiqiang. Research and realization on the algorithm of GPS/BDS real-time kinematic relative positioning[D]. Fuxin: Liaoning Technical University, 2016.
[8]	Iyengar S S, Ramani S K, Ao B. Fusion of the Brooks-Iyengar algorithm and blockchain in decentralization of the data-source[J]. Journal of Sensor and Actuator Networks, 2019, 8(1):17-19. doi: 10.3390/jsan8010017
[9]	刘让, 张凤登. FlexRay时钟同步拜占庭故障容错算法研究[J]. 软件导刊, 2020, 19(1):68-74.
	Liu Rang, Zhang Fengdeng. Research on fault tolerance algorithm of byzantine fault in FlexRay clock synchronization[J]. Software Guide, 2020, 19(1):68-74.
[10]	Tan R, Jiang L, Easwaran A, et al. Resilience bounds of sensing-based network clock synchronization[C]. Singapore: Proceeding of IEEE the Twenty-fourth International Conference on Parallel and Distributed Systems, 2018.
[11]	Fetter C, Cristian F. Integrating external and internal clock synchronization[J]. Real-Time Systems, 1997, 12(2):123-171. doi: 10.1023/A:1007905917490
[12]	Swain A R, Hansdah R C. A model for the classification and survey of clock synchronization protocols in WSNs[J]. Ad Hoc Networks, 2015, 27(8):219-241. doi: 10.1016/j.adhoc.2014.11.021
[13]	王军. IEEE1588与同步以太网技术的研究与实现[D]. 西安: 西安电子科技大学, 2016.
	Wang Jun. Research and implementation of IEEE1588 and synchronous Ethernet technology[D]. Xi'an: Xidian University, 2016.
[14]	于翔, 叶德建. 一种基于云的应用层容错机制设计与实现[J]. 微型电脑应用, 2016, 32(2):63-68.
	Yu Xiang, Ye Dejian. Design and implementation of fault tolerance mechanism in application layer based on cloud[J]. Microcomputer Applications, 2016, 32(2):63-68.
[15]	Pfluegl M J, Blough D M. A new and improved algorithm for fault-tolerant clock synchronization[J]. Journal of Parallel and Distributed Computing, 1995, 27(1):1-14. doi: 10.1006/jpdc.1995.1067
[16]	Khanchandani P, Lenzen C. Self-stabilizing byzantine clock synchronization with optimal precision[J]. Theory of Computing Systems, 2019, 63(2):261-305. doi: 10.1007/s00224-017-9840-3
[17]	何建平. 基于一致性的无线传感器网络时钟同步算法研究[D]. 杭州: 浙江大学, 2013.
	He Jianping. Consensus-based research on clock synchronization algorithm in wireless sensor networks[D]. Hangzhou: Zhejiang University, 2013.
[18]	刘江. 移动计算环境中的软件时钟同步算法研究[D]. 武汉: 中南民族大学, 2015.
	Liu Jiang. Research on software clock synchronization algorithm in mobile computing environment[D]. Wuhan: South-Central University for Nationalities, 2015.
[19]	刘婧岩, 王玉梅. 基于EtherCAT的井下电力监控系统冗余网络[J]. 电子科技, 2021, 34(6):73-78.
	Liu Jingyan, Wang Yumei. Redundant network of underground power monitoring system based on EtherCAT[J]. Electronic Science and Technology, 2021, 34(6):73-78.

参数	符号	数值/μs
最大时钟漂移率	ρ	100
初始同步精密度	φ_int	20
消息传输延迟(中值)	δ	7.5
传输延迟不确定度	ε	2.5
通信循环	R_i	5 000
ST段长度	gST	3 000
DYN段长度	gDYN	1 900
NIT段长度	gNIT	100