基于灰色预测容错时钟同步算法

doi:10.16180/j.cnki.issn1007-7820.2023.03.005

摘要/Abstract

摘要：

针对分布式实时系统中无主式时钟同步存在时钟拜占庭故障和节点通信链路丢失故障的问题,文中提出一种基于灰色预测容错时钟同步算法。该算法基于广播式通信网络LL模型,使用GM(1,1)的灰色预测方法对前轮次的校正偏差值进行分析,从而预测出该节点在故障伦次中的校正偏差值,再通过计算得到修正值。实验结果表明,文中提出的灰色预测算法能够容忍拜占庭故障,同时可克服节点通信链路丢失故障带来的问题,提升了FTA算法的普适性。通过数据对比分析结果表明,该算法的时钟同步精密度相比于原始算法提高了24.3%;相较于其他算法,文中算法在复杂度上也有一定的优势。

关键词: 分布式实时系统, 无主式, 时钟同步, 拜占庭故障, 通信链路丢失故障, 灰色预测, 容错, 校正偏差值

Abstract:

In view of the problem of clock Byzantine failure and node communication link loss failure in the non-master clock synchronization in the distributed real-time system, a fault-tolerant clock synchronization algorithm based on gray prediction is proposed in this study. The proposed algorithm is based on the LL model of the broadcast communication network, and uses the gray prediction method of GM (1,1) to analyze the correction deviation value of the previous round, so as to predict the correction deviation value of the node in the failure order, and then obtain the correction value through calculation. The experimental results show that the gray prediction algorithm proposed in this study can tolerate Byzantine faults, and at the same time, it can overcome the problems caused by the failure of node communication link loss, and improve the universality of the FTA algorithm. The data comparison analysis results show that the clock synchronization precision of this algorithm is improved by 24.3% when compared with Original algorithm. At the same time, the algorithm complexity has certain advantages when compared with other algorithms.

Key words: distributed real-time system, non-master, clock synchronization, Byzantine failure, communication link loss failure, gray prediction, fault-tolerant, correction deviation

中图分类号:

TN913

陆禹,张力,张凤登. 基于灰色预测容错时钟同步算法[J]. 电子科技, 2023, 36(3): 29-35.

LU Yu,ZHANG Li,ZHANG Fengdeng. Fault-Tolerant Clock Synchronization Algorithm Based on Grey Prediction[J]. Electronic Science and Technology, 2023, 36(3): 29-35.

图/表 8

表1

图1

表2

图2

表3

表4

表5

图3

参考文献 19

[1]	张凤登. 分布式实时系统[M]. 北京: 科学出版社, 2014.
	Zhang Fengdeng. Distributed real-time system[M]. Beijing: Science Press, 2014.
[2]	王天一, 高博. 分布式实时系统数据分发服务DDS技术研究[J]. 电子科技, 2020, 33(8):40-45.
	Wang Tianyi, Gao Bo. Research on data distribution service of distributed real-time system[J]. Electronic Science and Technology, 2020, 33(8):40-45.
[3]	钟麦英, 刘浩, 朱晓强, 等. 基于事件触发机制的故障诊断技术研究综述[J]. 山东科技大学学报(自然科学版), 2021, 40(2):95-102.
	Zhong Maiying, Liu Hao, Zhu Xiaoqiang, et al. A survey on recent studies of event-triggered fault diagnosis technology[J]. Journal of Shandong University of Science and Technology(Natural Science), 2021, 40(2):95-102.
[4]	刘让, 张凤登. FlexRay时钟同步拜占庭故障容错算法研究[J]. 软件导刊, 2020, 19(1):68-74.
	Liu Rang, Zhang Fengdeng. Research on fault tolerant algorithm of Byzantine fault in FlexRay clock synchronization[J]. Software Guide, 2020, 19(1):68-74.
[5]	张凯. 时间触发以太网高精度时钟同步技术研究[D]. 北京: 北京工业大学, 2020.
	Zhang Kai. Research on high-precision clock synchronization technology of Time-triggered Ethernet[D]. Beijing: Beijing University of Technology.
[6]	欧健, 陈瑞楠, 杨鄂川, 等. 基于故障估计的分布式驱动电动汽车容错控制方法[J]. 汽车技术, 2019(6):14-19.
	Ou Jian, Chen Ruinan, Yang Echuan, et al. Fault estimation based fault-tolerant control of distributed drive electric vehicles[J]. Automotive Technology, 2019(6):14-19.
[7]	Qiu T, Liu X, Han M, et al. SRTS: A self-recoverable time synchronization for sensor networks of healthcare IoT[J]. Computer Networks, 2017, 129(129):481-492. doi: 10.1016/j.comnet.2017.05.011
[8]	康立毅, 陈晓, 王劲林. 择优同步分布式时钟同步系统设计[J]. 网络新媒体技术, 2019, 8(1):53-57.
	Kang Liyi, Chen Xiao, Wang Jinlin. Design of distributed clock synchronization system by selecting execllent network nodes to synchronize[J]. Journal of Network New Media, 2019, 8(1):53-57.
[9]	张梅, 荣昆, 张双双. 基于卡尔曼滤波的TPSN时钟同步算法[J]. 电子测量技术, 2020, 43(18):43-46.
	Zhang Mei, Rong Kun, Zhang Shuangshuang. TPSN clock synchronization algorithm based on Kalman filter[J]. Electronic Measurement Technology, 2020, 43(18):43-46.
[10]	钱亚娜, 孔凡伟, 华姗姗. 基于时分多址的自组网同步算法研究[C]. 北京: 中国航天电子技术研究院科学技术委员会2020年学术年会, 2020.
	Qian Yana, Kong Fanwei, Hua Shanshan. Research on synchronization algorithm of ad hoc network based on time division multiple access[C]. Beijing: China Academy of Aerospace Electronics Technology Science and Technology Committee 2020 Academic Annual Meeting,2020.
[11]	汪浩, 邓中亮, 莫君, 等. 基于超宽带无线通信技术的无线时钟同步[C]. 北京: 第十届中国卫星导航年会, 2019.
	Wang Hao, Deng Zhongliang, Mo Jun, et al. Wireless clock synchronization based on ultra-wideband wireless communication technology[C]. Beijing: The Tenth China Satellite Navigation Annual Conference, 2019.
[12]	蒋伊琳, 张芳园. 基于自然选择粒子群的时钟同步算法[J]. 西南交通大学学报, 2017, 52(3):593-599.
	Jiang Yilin, Zhang Fangyuan. Clock synchronization algorithm based on particle swarm optimization with natural selection[J]. Journal of Southwest Jiaotong University, 2017, 52(3):593-599.
[13]	Welch J L, Lynch N. A new fault-tolerant algorithm for clock synchronization[J]. Information and Computation, 1988, 77(1):1-36. doi: 10.1016/0890-5401(88)90043-0
[14]	Cristian F, Fetzer C. Fault-tolerant external clock synchronization[C]. Vancouver: Proceedings of the Fifteenth International Conference on Distributed Computing Systems,1995.
[15]	范纯龙, 孙强龙, 刘海港. 基于归并策略的一致性时钟同步算法[J]. 数字通信世界, 2020(1):10-12.
	Fan Chunlong, Sun Qianglong, Liu Haigang. Consistent clock synchronization algorithm based on merge strategy[J]. Digital Communication World, 2020(1):10-12.
[16]	张凤登. 实时传输网络FlexRay原理与范例[M]. 北京: 电子工业出版社, 2017.
	Zhang Fengdeng. Principles and examples of real-time transmission network FlexRay[M]. Beijing: Publishing House of Electronics Industry, 2017.
[17]	Gao C, Zhao G R, Lu J H, et al. Decentralised moving-horizon state estimation for a class of networked spatial-navigation systems with random parametric uncertainties and communication link failures[J]. IET Control Theory & Applications, 2015, 9(18):2666-2677. doi: 10.1049/cth2.v9.18
[18]	Yu H Y, Zhuang Y, Wang W. Distributed H∞ filtering in sensor networks with randomly occurred missing measurements and communication link failures[J]. Information Sciences, 2013, 22(2):424-438.
[19]	王爱. 十四号线及知识城线车载无线通信故障报警分析[J]. 科学技术创新, 2021(24):33-34.
	Wang Ai. Analysis of fault alarm of vehicle-mounted wireless communication on Line 14 and Knowledge City Line[J]. Science and Technology Innovation, 2021(24):33-34.

节点	晶振	微时隙长度	NMUM	宏时隙长度	NIT段长度
A	5 MHz	0.2 μs	5个	1 μs	1 μs
B	2 MHz	0.5 μs	2个	1 μs	1 μs
C	2 MHz	0.5 μs	2个	1 μs	1 μs
D	1 MHz	1.0 μs	1个	1 μs	1 μs

模型精度等级	方差比C	小概率误差P
1级(好)	C≤ 0.35	P> 95%
2级(合格)	0.35<C≤ 0.5	P>80%
3级(勉强)	0.5<C≤ 0.65	P>70%
4级(不合格)	0.65<C	P≤ 70%

模拟验证参数	符号	假设常数值
时钟漂移率	ρ	100 μs·(SP)^-1
远程时钟读取最大误差	ζ	2 μs
节点通信最大延迟	β	8 μs
同步初始状态偏差	δ^init	10 μs
时钟重同步周期	TP	2 000 μs

节点	1	2	3	4	5
起始时刻/μs	0	2	4	6	8
微时隙/μs	3	6	9	12	15
宏时隙/μs	4	4	4	4	4
帧发送时刻/μs	50	100	150	200	250
NIT段/μs	15	15	15	15	15
TP/μs	2 000	2 000	2 000	2 000	2 000