TT-RMS:时间触发网络通信表生成算法

徐晓飞; 曹晨; 郭骏; 刘忠伟

doi:10.13700/j.bh.1001-5965.2014.0618

TT-RMS:时间触发网络通信表生成算法

doi: 10.13700/j.bh.1001-5965.2014.0618

中国航空无线电电子研究所, 上海 200233

基金项目: 工信部"十二五"预研项目(MJZS201103);总装重点实验室基金(02120C4701)

详细信息

通讯作者:
徐晓飞(1975-),男,安徽芜湖人,高级工程师,xu_xiaofei@careri.com,主要研究方向为实时通信系统、航电网络.

中图分类号: V247.5
计量
- 文章访问数: 1103
- HTML全文浏览量: 187
- PDF下载量: 546
- 被引次数: 0
出版历程
- 收稿日期: 2014-10-10
- 网络出版日期: 2015-08-20

TT-RMS: Communication table generation algorithm of time-triggered network

China Aeronautical Radio Electronics Research Institute, Shanghai 200233, China

摘要

摘要: 针对时间触发网络依据全局时间进行触发数据通信的特点,提出了一种基于单调速率调度(RMS)调度机制的通信表生成算法时间触发单调速率调度(TT-RMS),来生成时间触发网络的通信表.TT-RMS算法在安排消息时间槽过程中,首先根据消息周期,计算出各个链路的总负载,再根据链路的消息周期和总负载,通过RMS机制进行消息排序,确定出消息调度的先后顺序,最后根据时间槽的分配状态进行消息调度,优化了消息的调度过程.所提算法的计算时间复杂度为O(n²),空间复杂度为O(n).目前广泛研究和应用的可满足性理论(SMT)通信表生成方法,其计算时间复杂度通常是多项式级,有时计算时间不收敛.实验结果显示,TT-RMS调度的网络单个链路负载最大可接近100%,计算时间在1 ms左右,平均可调度网络负载是SMT方法可调度网络负载的两倍.TT-RMS通信表生成算法具有计算时间短,可调度消息负载多等优点,可以更好地满足航空航天复杂系统中上千条实时消息流的调度需要.
- RMS调度机制 /
- 时间触发网络 /
- 通信表生成 /
- 可满足性理论 /
- 实时通信
Abstract: According to the characteristic of communications in time-triggered network, which is data communication being triggered by a global clock, a rate monotonic scheduling (RMS) based time-triggered communication table generation algorithm was proposed, which was used to generate configurable communication schedule in the time-triggered network. The scheduling of message timeslots in time-trigger RMS (TT-RMS) algorithm included calculating link load by message period, sorting messages by RMS mechanism according to link load and message period, determining sequences of message transmission, and scheduling messages by timeslots, which optimized scheduling process. The time complexity of the TT-RMS was O(n²). And the space complexity was O(n). The time complexity of the widely used satisfiability modulo theories (SMT) method was polynomial, which did not converge sometimes. The experiment results show that to a single link, maximum bandwidth of the TT-RMS algorithm is approximate to 100% and the computing time is close to 1 millisecond. The average schedulable traffic bandwidth is twice of using SMT. The TT-RMS has better performances on computing time and schedulable traffic bandwidth, which could better satisfy the application of complex aeronautic and aerospace system which has thousands of real-time traffic in network.
- rate monotonic scheduling (RMS) mechanism /
- time-triggered network /
- communication table generation /
- satisfiability modulo theories (SMT) /
- real-time communication

HTML全文

参考文献(16)

[1]	邱爱华,张涛, 顾逸东.面向空间应用的时间触发以太网[J].国防科技大学学报,2014,36(5):117-123. Qiu A H,Zhang T,Gu Y D.Time-triggered Ethernet for space utilization[J]. Journal of National University of Defense Technology,2014,36(5):117-123(in Chinese).
[2]	Lauer M, Mullins J,Yeddes M,et al.Cost optimization strategy for iterative integration of multi-critical functions in IMA and TTEthernet architecture[C]//Proceedings of IEEE 37th Annual Computer Software and Applications Conference Workshops (COMPSACW).Piscataway,NJ:IEEE Press,2013:139-144.
[3]	Zhang L C, Goswami D,Schneider R,et al.Task-and network-level schedule co-synthesis of Ethernet-based time-triggered systems[C]//Proceedings of the 19th Asia and South Pacific Design Automation Conference,ASP-DIC.Piscataway,NJ:IEEE Press,2014:119-124
[4]	罗安心. 基于时间触发以太网的同步算法研究与实现[D].成都:电子科技大学,2013. Luo A X.Research and implementation synchronization algorithm based on time-trigger Ethernet[D].Chengdu:University of Electronic Science and Technology of China,2013(in Chinese).
[5]	Steiner W, Bauer G,Hall B,et al.Time-triggered communication[M].Boca Raron:CRC Press Inc,2011:88-89.
[6]	郝燕艳,潘瑞, 万小磊.基于TTEthernet的综合电子系统通信网络研究[J].航天器工程,2013,22(6):98-99. Hao Y Y,Pang R,Wan X L.Research of integrated avionics communication network based on TTEthernet[J].Space Engineering,2013,22(6):98-99(in Chinese).
[7]	章磊,祝明,武哲. 无人直升机系统CAN总线应用层协议设计[J].北京航空航天大学学报,2011,37(10):1264-1270. Zhang L,Zhu M,Wu Z.CAN bus application layer protocol design for unmanned helicopter system[J].Journal of Beijing University of Aeronautics and Astronautics,2011,37(10):1264-1270(in Chinese).
[8]	Kang M, Park K,Jeong M-K.Frame packing for minimizing the bandwidth consumption of flex ray static segment[J].IEEE Transaction on Vehicular Technology,2013,60(9):4001-4008.
[9]	Sagstetter F, Lukasiewycz M,Chakraborty S,et al.Schedule integration for time-triggered systems[C]//Proceedings of the 18th Asia and South Pacific Design Automation Conference,ASP-DIC.Piscataway,NJ:IEEE Press,2013:53-58.
[10]	王振宇,李照瑜. 单层树型网格下独立任务的周期性调度[J].软件学报,2013,24(2):378-390. Wang Z Y,Li Z Y.Scheduling periodic independent tasks on single-level tree grid[J].Journal of Software,2013,24(2):378-390(in Chinese).
[11]	刘虎球,赵鹏. 一种多核间内存公平调度模型[J].计算机学报,2013,36(11):2192-2198. Liu H Q,Zhao P.A Multi-core fair memory scheduling model[J].Chinese Journal of Computers,2013,36(11):2192-2198(in Chinese).
[12]	Noguero A, Calvo I,Almeida L,et al.A model for system resources in flexible time-triggered middleware architectures[C]//Proceedings of 16th International Conference on Information and Communications Technologies,EUNICE.Berlin:Springer,2012,7479 LNCS:215-226.
[13]	Steiner W. An evaluation of SMT-based schedule synthesis for time-triggered multi-hop networks[C]//Proceedings of 31st IEEE Real-Time Systems Symposium.Piscataway,NJ:IEEE Press,2010:375-384.
[14]	Steiner W, Dutertre B.SMT based formal verification of a TTEthernet synchronization function in formal methods for industrial critical systems[C]//Proceedings of 15th International Workshop on Formal Methods for Industrial Critical Systems,FMICS.Berlin:Springer,2010,6371 LNCS:148-163.
[15]	Huang J, Blech J O,Raabe A,et al.Static scheduling of a time-triggered network-on-chip based on SMT solving[C]//Proceedings of Design,Automation & Test in Europe Conference & Exhibition, DATE.Piscataway,NJ:IEEE Press,2012:509-514.
[16]	Craciunas S S, Oliver R S,et al.SMT-based task-and network-level static schedule generation for time-triggered networked systems[C]//Proceedings of the 22nd International Conference on Real-Time Networks and Systems.New York:Association for Computing Machinery,2014:45-54.