基于发布订阅架构的在线时间触发调度方法
收稿日期: 2022-10-18
修回日期: 2022-11-23
录用日期: 2023-03-07
网络出版日期: 2023-03-31
基金资助
国家自然科学基金(62071023)
Online time-triggered scheduling method based on publish/subscribe architecture
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
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 Aeronautics, 2020, 33(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 Systems, 2016, 52(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 Letters, 2021, 13(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 Magazine, 2018, 2(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 & Applications, 2016, 1(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]. 北京航空航天大学学报, 2021, 47(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 Astronautics, 2021, 47(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 Systems, 2015, 51(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 Journal, 2022, 9(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 Annals, 2016, 65(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 Informatics, 2018, 14(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 Informatics, 2019, 15(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 Informatics, 2023, 19(2): 2140-2150. |
/
〈 |
|
〉 |