北京航空航天大学学报 ›› 2015, Vol. 41 ›› Issue (8): 1403-1408.doi: 10.13700/j.bh.1001-5965.2014.0618

• 论文 • 上一篇    下一篇

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

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

  1. 中国航空无线电电子研究所, 上海 200233
  • 收稿日期:2014-10-10 出版日期:2015-08-20 发布日期:2015-09-08
  • 通讯作者: 徐晓飞(1975-),男,安徽芜湖人,高级工程师,xu_xiaofei@careri.com,主要研究方向为实时通信系统、航电网络. E-mail:xu_xiaofei@careri.com
  • 基金资助:
    工信部"十二五"预研项目(MJZS201103);总装重点实验室基金(02120C4701)

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

XU Xiaofei, CAO Chen, GUO Jun, LIU Zhongwei   

  1. China Aeronautical Radio Electronics Research Institute, Shanghai 200233, China
  • Received:2014-10-10 Online:2015-08-20 Published:2015-09-08

摘要: 针对时间触发网络依据全局时间进行触发数据通信的特点,提出了一种基于单调速率调度(RMS)调度机制的通信表生成算法时间触发单调速率调度(TT-RMS),来生成时间触发网络的通信表.TT-RMS算法在安排消息时间槽过程中,首先根据消息周期,计算出各个链路的总负载,再根据链路的消息周期和总负载,通过RMS机制进行消息排序,确定出消息调度的先后顺序,最后根据时间槽的分配状态进行消息调度,优化了消息的调度过程.所提算法的计算时间复杂度为O(n2),空间复杂度为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(n2). 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.

Key words: rate monotonic scheduling (RMS) mechanism, time-triggered network, communication table generation, satisfiability modulo theories (SMT), real-time communication

中图分类号: 


版权所有 © 《北京航空航天大学学报》编辑部
通讯地址:北京市海淀区学院路37号 北京航空航天大学学报编辑部 邮编:100191 E-mail:jbuaa@buaa.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发