| Citation: | ZHENG Zhong, HE Feng, LI Haoruo, et al. Scheduling algorithm of TTE network based on greedy randomized adaptive search procedure[J]. Journal of Beijing University of Aeronautics and Astronautics, 2021, 47(11): 2268-2276. doi: 10.13700/j.bh.1001-5965.2020.0382(in Chinese)
|
Time-Triggered Ethernet (TTE) makes communication tasks have strict determinacy and conflict free by global time-triggered mechanism, which is suitable for mixed critical application fields such as avionics. TTE network provides three different traffic types: Time-Triggered (TT) traffic with low jitter and bounded end-to-end delay, Rate Constrained (RC) traffic with limited end-to-end delay, and no real-time guaranteed "Best Effort" (BE) traffic. Aiming at the problem that Satisfiability Modulo Theories (SMT) and other methods do not consider the influence of TT traffic routing and scheduling on RC traffic delay in the process of generating the TT traffic scheduling timetable, in order to optimize the real-time performance of TTE network, this paper proposes a scheduling algorithm based on greedy randomized adaptive search procedure. The Worst-Case end-to-end Delay (WCD) of RC traffic is considered in the generation process of TT traffic offline scheduling timetable. Under the premise of ensuring the schedulability of TT traffic, the WCD of RC traffic is reduced by routing strategy and scheduling strategy. The comparative experimental results show that the proposed method can effectively improve the real-time performance of the network. Through the comparative analysis of A380 topology networking cases, the average delay of RC traffic is reduced by 14.34%. Also, the larger the network traffic scale, the greater the income of this method.
| [1] |
Aerospace. SAE AS6802: Time-Triggered Ethernet[S]. [S. l. ]: SAE International, 2011: 8-21.
|
| [2] |
ARINC. Aircraft data network, Part 7, Avionics full-duplex switched ethernet network: ARINC 664P7[S]. [S. l. ]: Aeronautical Radio INC, 2009: 9-18.
|
| [3] |
KOPETZ H. Real-time systems: Design principles for distributed embedded applications[M]. Berlin: Springer Science and Business Media, 2011: 79-109.
|
| [4] |
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.
|
| [5] |
刘成, 李航, 何锋, 等. 基于轨迹方法的AFDX网络路由配置算法[J]. 北京航空航天大学学报, 2012, 38(12): 1587-1590. https://bhxb.buaa.edu.cn/CN/Y2012/V38/I12/1587
LIU C, LI H, HE F, et al. Routing algorithm of AFDX network based on trajectory approach[J]. Journal of Beijing University of Aeronautics and Astronautics, 2012, 38(12): 1587-1590(in Chinese). https://bhxb.buaa.edu.cn/CN/Y2012/V38/I12/1587
|
| [6] |
Al S A, BRUN O, CHERAMY M, et al. Optimal design of virtual links in AFDX networks[J]. Real-Time Systems, 2013, 49(3): 308-336. doi: 10.1007/s11241-012-9171-z
|
| [7] |
代真, 何锋, 张宇静, 等. AFDX虚拟链路路径实时寻优算法[J]. 航空学报, 2015, 36(6): 1924-1932. https://www.cnki.com.cn/Article/CJFDTOTAL-HKXB201506021.htm
DAI Z, HE F, ZHANG Y J, et al. Real-time path optimization algorithm of AFDX virtual link[J]. Acta Aeronautica et Astronautica Sinica, 2015, 36(6): 1924-1932(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-HKXB201506021.htm
|
| [8] |
STEINER W. An evaluation of SMT-based schedule synthesis for time-triggered multi-hop networks[C]//201031st IEEE Real-Time Systems Symposium. Piscataway: IEEE Press, 2010: 375-384.
|
| [9] |
STEINER W. Synthesis of static communication schedules for mixed-criticality systems[C]//201114th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing Workshops. Piscataway: IEEE Press, 2011: 11-18.
|
| [10] |
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. doi: 10.1007/s11241-015-9244-x
|
| [11] |
宋梓旭, 李峭, 汪晶晶, 等. 基于可调度性排序的时间触发调度表生成方法[J]. 北京航空航天大学学报, 2018, 44(11): 145-152. doi: 10.13700/j.bh.1001-5965.2018.0043
SONG Z X, LI Q, WANG J J, et al. Time-triggered scheduling table generation method based on schedulability ranking[J]. Journal of Beijing University of Aeronautics and Astronautics, 2018, 44(11): 145-152(in Chinese). doi: 10.13700/j.bh.1001-5965.2018.0043
|
| [12] |
SUETHANUWONG E. Scheduling time-triggered traffic in TTEthernet systems[C]//Proceedings of 2012 IEEE 17th International Conference on Emerging Technologies and Factory Automation (ETFA 2012). Piscataway: IEEE Press, 2012: 1-4.
|
| [13] |
SCHWEISSGUTH E, DANIELIS P, TIMMERMANN D, et al. ILP-based joint routing and scheduling for time-triggered networks[C]//Proceedings of the 25th International Conference on Real-Time Networks and Systems. New York: ACM, 2017: 8-17.
|
| [14] |
李浩若, 何锋, 郑重, 等. 基于强化学习的时间触发通信调度方法[J]. 北京航空航天大学学报, 2019, 45(9): 1894-1901. doi: 10.13700/j.bh.1001-5965.2018.0789
LI H R, HE F, ZHENG Z, et al. Time-triggered communication scheduling method based on reinforcement learning[J]. Journal of Beijing University of Aeronautics and Astronautics, 2019, 45(9): 1894-1901(in Chinese). doi: 10.13700/j.bh.1001-5965.2018.0789
|
| [15] |
TÃMAŞ-SELICEAN D, POP P, STEINER W. Design optimization of TTE thernet-based distributed real-time systems[J]. Real-Time Systems, 2015, 51(1): 1-35. doi: 10.1007/s11241-014-9214-8
|
| [16] |
ZHAO L, XIONG H, ZHENG Z, et al. Improving worst-case latency analysis for rate-constrained traffic in the time-triggered ethernet network[J]. IEEE Communications Letters, 2014, 18(11): 1927-1930. doi: 10.1109/LCOMM.2014.2358233
|
| [17] |
ZHAO L, POP P, LI Q, et al. Timing analysis of rate-constrained traffic in TTEthernet using network calculus[J]. Real-Time Systems, 2017, 53(2): 254-287. doi: 10.1007/s11241-016-9265-0
|
| [18] |
GAREY M R, JOHNSON D S, SETHI R, et al. The complexity of flowshop and jobshop scheduling[J]. Mathematics of Operations Research, 1976, 1(2): 117-129. doi: 10.1287/moor.1.2.117
|
| [19] |
YEN J Y. Finding the k shortest loopless paths in a network[J]. Management Science, 1971, 17(11): 712-716. doi: 10.1287/mnsc.17.11.712
|
| [20] |
RESENDE M G C, RIBEIRO C C. GRASP: Greedy randomized adaptive search procedures[M]//BURKE E K, KENDALL G. Search methodologies. Berlin: Springer, 2014: 287-312.
|
Figures(7) / Tables(3)
Copyright © Journal of Beijing University of Aeronautics and Astronautics
Address: Editorial Department of Journal of Beijing University of Aeronautics and Astronautics, 37 Xueyuan Road, Haidian District, Beijing Post Code: 100191 Email: jbuaa@buaa.edu.cn
Supported by:
Beijing Renhe Information Technology Co., Ltd.
DownLoad:
