Key data between satellites once fault-tolerant scheduling algorithm

doi:10.3778/j.issn.1002-8331.1603-0186

Computer Engineering and Applications ›› 2017, Vol. 53 ›› Issue (14): 61-64.DOI: 10.3778/j.issn.1002-8331.1603-0186

Previous Articles Next Articles

Key data between satellites once fault-tolerant scheduling algorithm

FAN Lingling1，2, LIN Baojun2，3, CHEN Yong3

1.Shanghai Institute of Microsystem and Information Technology, Chinese Academy of Sciences, Shanghai 200050, China
2.Shanghai Engineering Center for Microsatellites, Shanghai 201203, China
3.Academy of Opto-Electronics, Chinese Academy of Sciences, Beijing 100094, China

Online:2017-07-15 Published:2017-08-01

星间实时关键数据一次容错调度算法

范玲玲1，2，林宝军2，3，陈勇3

1.中国科学院上海微系统与信息技术研究所，上海 200050
2.上海微小卫星工程中心，上海 201203
3.中国科学院光电研究院，北京 100094

Abstract

Abstract: In this paper, in accordance with the need of key data in real-time satellite system fault tolerance, and the key data with a relatively small number and a long cycle, it puts forward NP-PEDF-FT algorithm to realize high performance schedule. This algorithm based on EDF fault tolerant algorithm, adjusts the deadline of the key data through fault tolerance coefficient[λ]. This algorithm adjusts the deadline of the key data as the original deadline multiplied by the coefficient [(1-λ)] to the queue of the tasks to send again, when the key data once transmission errors. So it can realize once fault tolerance. Of course, the algorithm will not send again and abandon the task, when the common data once transmission errors. NP-PEDF-FT algorithm is better when the coefficient[λ]is equal to 0.6 through the simulation. It also simulates the NP-PEDF-FT algorithm, NP-EDF-FT algorithm and NP-DP-FT algorithm, and compares the packet loss probability. It turns out that the NP-PEDF-FT algorithm used in this paper has a better effect.

Key words: non-preemptive, key data, fault tolerance, scheduled, deadline, compare

摘要： 针对卫星实时系统中关键数据一次容错问题，首先，针对关键数据与非关键数据混合传输场景，建立系统模型，对系统的容错传输能力进行分析，得出混合数据一次容错传输条件；其次提出NP-PEDF-FT调度算法，通过在非抢占式EDF容错算法的基础上，利用截止期容错系数[λ]调整出错任务的截止期，实现全部关键数据的1次容错传输；同时加入数据传输队列监测功能，以保证关键数据在其截止期之前优先传输；最后对算法进行了仿真分析，比较NP-PEDF-FT、NP-EDF-FT、NP-DP-FT三种非抢占式容错调度策略，分析结果表明，NP-PEDF-FT算法关键数据丢包率较NP-EDF-FT算法平均降低31.6%，较NP-DP-FT算法平均降低86.4%。

关键词: 非抢占式, 关键数据, 容错, 调度, 截止期, 比较

FAN Lingling1，2, LIN Baojun2，3, CHEN Yong3. Key data between satellites once fault-tolerant scheduling algorithm[J]. Computer Engineering and Applications, 2017, 53(14): 61-64.

范玲玲1，2，林宝军2，3，陈勇3. 星间实时关键数据一次容错调度算法[J]. 计算机工程与应用, 2017, 53(14): 61-64.

[1]	WANG Rihong, XING Congying, XU Quanqing, YUAN Shanshan. Efficient Byzantine Fault Tolerant Algorithm with Supervision Mechanism [J]. Computer Engineering and Applications, 2021, 57(18): 142-148.
[2]	XU Yangyang，LI Wei，WANG Jie. Optimization of Robot Delay Using Events and Deadline Control [J]. Computer Engineering and Applications, 2021, 57(17): 260-268.
[3]	WANG Fusen, LI Zhihuai, TIAN Na. Multiple Rounds of PBFT Verification Scheme to Improve Scale and Validity of Sharding [J]. Computer Engineering and Applications, 2020, 56(24): 102-108.
[4]	GAO Weijun, ZHANG Chunxia, YANG Jie, SHI Yang. Research on Fault Tolerant Clustering Algorithm of Scientific Workflow Considering Load Balancing [J]. Computer Engineering and Applications, 2020, 56(23): 53-60.
[5]	ZHAI Sheping, CHEN Siji, WANG Yijing. Research on Digital Copyright Storage System Model Based on Blockchain [J]. Computer Engineering and Applications, 2020, 56(19): 13-21.
[6]	TIAN Hua1, YAN Xiai2, YANG Jinmin3. Adaptive Fault Tolerance Schemes for Cloud Storage of Library [J]. Computer Engineering and Applications, 2019, 55(7): 95-99.
[7]	LI Zhixiang, LI Yun, HE Liang. Scheduling methods for special type of non-preemptive periodic tasks [J]. Computer Engineering and Applications, 2018, 54(9): 22-27.
[8]	ZHU Danhong, LIN Qingxiang, ZHANG Dong. Deadline-aware of congestion control algorithm based on SDN data center network [J]. Computer Engineering and Applications, 2018, 54(3): 68-73.
[9]	XIANG Bo, YU Liyang. Research and design on SDN multi-controller fault tolerance [J]. Computer Engineering and Applications, 2018, 54(23): 81-88.
[10]	MENG Chen1，2, CAO Zongyan1, WANG Long1, CHI Xuebin1. Charm++ RTS based fault tolerance mechanism of heterogeneous computing [J]. Computer Engineering and Applications, 2016, 52(13): 1-7.
[11]	CUI Xuetao, ZHANG Xihuang. Mechanisms for energy efficiency based on reliability under cloud computing [J]. Computer Engineering and Applications, 2016, 52(1): 42-47.
[12]	CHEN Kunwei, GUO Xing, WU Jianguo. Text input system based on gesture recognition [J]. Computer Engineering and Applications, 2015, 51(3): 66-68.
[13]	XIN Qiangwei. Research of wireless sensor networks fault tolerance by minimum connected dominating set [J]. Computer Engineering and Applications, 2015, 51(11): 18-21.
[14]	XU Xiaodong, ZHAO Jianting, XU Chunlei. Fault tolerance in real-time and multitask parallel computing system [J]. Computer Engineering and Applications, 2013, 49(9): 33-36.
[15]	GUO Aiyin1, XU Yunjian2. Improved EDF scheduling algorithm combining with three kinds of primary network businesses [J]. Computer Engineering and Applications, 2013, 49(22): 86-89.

Key data between satellites once fault-tolerant scheduling algorithm

星间实时关键数据一次容错调度算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics