ACTA AERONAUTICAET ASTRONAUTICA SINICA >
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)
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.
Yifan GAO , Feng HE , Sifan YU . Online time-triggered scheduling method based on publish/subscribe architecture[J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2023 , 44(18) : 328125 -328125 . DOI: 10.7527/S1000-6893.2023.28125
| 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. |
/
| 〈 |
|
〉 |
CJA