电子电气工程与控制

基于发布订阅架构的在线时间触发调度方法

  • 高一凡 ,
  • 何锋 ,
  • 于思凡
展开
  • 北京航空航天大学 电子信息工程学院,北京  100191
.E-mail: robinleo@buaa.edu.cn

收稿日期: 2022-10-18

  修回日期: 2022-11-23

  录用日期: 2023-03-07

  网络出版日期: 2023-03-31

基金资助

国家自然科学基金(62071023)

Online time-triggered scheduling method based on publish/subscribe architecture

  • Yifan GAO ,
  • Feng HE ,
  • Sifan YU
Expand
  • School of Electronics and Information Engineering,Beihang University,Beijing  100191,China

Received date: 2022-10-18

  Revised date: 2022-11-23

  Accepted date: 2023-03-07

  Online published: 2023-03-31

Supported by

National Natural Science Foundation of China(62071023)

摘要

混合关键性消息的调度优化是其应用于航空电子系统的关键,而日益增加的动态应用更加依赖于时间触发调度的在线求解。现有时间触发网络调度多基于离线调度设计,面对大规模组网应用其调度表生成耗时较长且生成后难以在线调整。为了更快地求解调度表,并适应在线调整需求,结合数据分发系统中的发布/订阅机制,构建了基于发布/订阅架构的时间触发网络模型;在其基础上提出了基于统一时间分片的时间触发调度在线求解算法,将连续时间离散为时间分片,并基于统一长度约束优化调度求解空间,极大地减少了调度表生成时间;进一步,根据时间分片长度度量链路负载情况,在消息调度过程中实现链路负载均衡的目的,在保障时间触发消息传输延迟需求的条件下降低速率约束消息的端到端延迟。实验结果表明:对于包含300条消息的网络,所提算法的求解速度是可满足性模理论求解的数千倍,同时速率约束消息的最坏端到端延迟比可满足性模理论求解降低了17.4%。对于包含2 000条时间触发消息的网络,所提方法生成调度表的时间为100 ms数量级。

本文引用格式

高一凡 , 何锋 , 于思凡 . 基于发布订阅架构的在线时间触发调度方法[J]. 航空学报, 2023 , 44(18) : 328125 -328125 . DOI: 10.7527/S1000-6893.2023.28125

Abstract

The scheduling solution of hybrid critical messages is the key to its application in avionics systems, and increasingly dynamic applications rely more on the online solution of time-triggered scheduling. At present, time-triggered network scheduling is mostly based on offline scheduling design, which take a long time to be generated and are difficult to be adjusted online after generation in large-scale networking applications. In order to solve the scheduling table faster and make online adjustment, this paper constructs a time-triggered network architecture model based on the publish/subscribe model. Then, an online time-triggered scheduling algorithm is proposed based on unified time slots. Time is discretized into time slots with the unified maximum length, which optimizes the scheduling solution space and reduces the time of scheduling table generation. The link load is measured by the time slot length and is balanced in the process of scheduling to reduce the end-to-end delay of rate-constrained messages. The experimental results show that for the network with 300 messages, the scheduling solution speed of the proposed algorithm is thousands of times that of the SMT algorithm, and the worst-case end-to-end delay of rate-constrained messages is reduced by 17.4% compared with that of the SMT algorithm. For the network with 2 000 time-triggered messages, the time of generating schedule table with the proposed method is on the order of 100 milliseconds.

参考文献

1 ZHOU X, XIONG H G, HE F. Hybrid partition- and network-level scheduling design for distributed integrated modular avionics systems[J]. Chinese Journal of Aeronautics202033(1): 308-323.
2 何锋. 机载网络技术基础[M]. 北京: 国防工业出版社, 2018: 171-172.
  HE F. Fundamentals of airborne network[M]. Beijing: National Defense Industry Press, 2018: 171-172 (in Chinese).
3 KOPETZ H, ADEMAJ A, GRILLINGER P, et al. The time-triggered Ethernet (TTE) design[C]∥ Eighth IEEE International Symposium on Object-Oriented Real-Time Distributed Computing (ISORC'05). Piscataway: IEEE Press, 2005: 22-33.
4 STEINER W. An evaluation of SMT-based schedule synthesis for time-triggered multi-hop networks[C]∥ 2010 31st IEEE Real-Time Systems Symposium. Piscataway: IEEE Press, 2011: 375-384.
5 PAHLEVAN M, OBERMAISSER R. Genetic algorithm for scheduling time-triggered traffic in time-sensitive networks[C]∥ 2018 IEEE 23rd International Conference on Emerging Technologies and Factory Automation (ETFA). Piscataway: IEEE Press, 2018: 337-344.
6 CRACIUNAS S S, OLIVER R S. Combined task- and network-level scheduling for distributed time-triggered systems[J]. Real-Time Systems201652(2): 161-200.
7 LEE D, LIN B, CHENG C K. SMT-based contention-free task mapping and scheduling on SMART NoC[J]. IEEE Embedded Systems Letters202113(4): 158-161.
8 SERNA OLIVER R, CRACIUNAS S S, STEINER W. IEEE 802.1Qbv gate control list synthesis using array theory encoding[C]∥ 2018 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS). Piscataway: IEEE Press, 2018: 13-24.
9 STEINER W, CRACIUNAS S S, OLIVER R S. Traffic planning for time-sensitive communication[J]. IEEE Communications Standards Magazine20182(2): 42-47.
10 ZHANG L C, GOSWAMI D, SCHNEIDER R, et al. Task- and network-level schedule co-synthesis of Ethernet-based time-triggered systems[C]∥ 2014 19th Asia and South Pacific Design Automation Conference (ASP-DAC). Piscataway: IEEE Press, 2014: 119-124.
11 POP P, RAAGAARD M L, CRACIUNAS S S, et al. Design optimisation of cyber-physical distributed systems using IEEE time-sensitive networks[J]. IET Cyber-Physical Systems: Theory & Applications20161(1): 86-94.
12 SHI Y F, LI Q, YANG J H, et al. A topology-based decomposition approach for time-triggered message scheduling in network-on-chip[C]∥ 2019 IEEE/AIAA 38th Digital Avionics Systems Conference (DASC). Piscataway: IEEE Press, 2020: 1-8.
13 鲁俊, 何锋, 熊华钢, 等. 软件定义时间触发网络的调度算法优化[J]. 北京航空航天大学学报202147(5): 1004-1014.
  LU J, HE F, XIONG H G, et al. Scheduling algorithms optimization in software defined time-triggered network[J]. Journal of Beijing University of Aeronautics and Astronautics202147(5): 1004-1014 (in Chinese).
14 TAMAS-SELICEAN D, POP P, STEINER W. Synthesis of communication schedules for TTEthernet-based mixed-criticality systems[C]∥ Proceedings of the Eighth IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis. New York: ACM, 2012: 473-482.
15 T?MA?-SELICEAN D, POP P, STEINER W. Design optimization of TTEthernet-based distributed real-time systems[J]. Real-Time Systems201551(1): 1-35.
16 XU L, XU Q M, TU J Z, et al. Learning-based scalable scheduling and routing co-design with stream similarity partitioning for time-sensitive networking[J]. IEEE Internet of Things Journal20229(15): 13353-13363.
17 POZO F, RODRIGUEZ-NAVAS G, HANSSON H. Schedule reparability: enhancing time-triggered network recovery upon link failures[C]∥ 2018 IEEE 24th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA). Piscataway: IEEE Press, 2019: 147-156.
18 MONOSTORI L, KáDáR B, BAUERNHANSL T, et al. Cyber-physical systems in manufacturing[J]. CIRP Annals201665(2): 621-641.
19 ALNAJIM A, SALEHI S, SHEN C C. Incremental path-selection and scheduling for time-sensitive networks[C]∥ 2019 IEEE Global Communications Conference (GLOBECOM). Piscataway: IEEE Press, 2020: 1-6.
20 NAYAK N G, DüRR F, ROTHERMEL K. Incremental flow scheduling and routing in time-sensitive software-defined networks[J]. IEEE Transactions on Industrial Informatics201814(5): 2066-2075.
21 ZHANG S Q, LI Z H, WANG N C, et al. An offline equivalence scheduling technique for time-triggered Ethernet[C]∥ Proceedings of the 6th International Conference on Communications and Broadband Networking. New York: ACM, 2018: 65-70.
22 NASRI M, BRANDENBURG B B. Offline equivalence: a non-preemptive scheduling technique for resource-constrained embedded real-time systems (outstanding paper)[C]∥ 2017 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS). Piscataway: IEEE Press, 2017: 75-86.
23 WANG N C, YU Q H, WAN H, et al. Adaptive scheduling for multicluster time-triggered train communication networks[J]. IEEE Transactions on Industrial Informatics201915(2): 1120-1130.
24 GUO M, GU C J, HE S B, et al. MSS: exploiting mapping score for CQF start time planning in time-sensitive networking[J]. IEEE Transactions on Industrial Informatics202319(2): 2140-2150.
文章导航

/