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

针对时间触发网络依据全局时间进行触发数据通信的特点,提出了一种基于单调速率调度(RMS)调度机制的通信表生成算法时间触发单调速率调度(TT-RMS),来生成时间触发网络的通信表.TT-RMS算法在安排消息时间槽过程中,首先根据消息周期,计算出各个链路的总负载,再根据链路的消息周期和总负载,通过RMS机制进行消息排序,确定出消息调度的先后顺序,最后根据时间槽的分配状态进行消息调度,优化了消息的调度过程.所提算法的计算时间复杂度为O(n2),空间复杂度为O(n).目前广泛研究和应用的可满足性理论(SMT)通信表生成方法,其计算时间复杂度通常是多项式级,有时计算时间不收敛.实验结果显示,TT-RMS调度的网络单个链路负载最大可接近100%,计算时间在1 ms左右,平均可调度网络负载是SMT方法可调度网络负载的两倍.TT-RMS通信表生成算法具有计算时间短,可调度消息负载多等优点,可以更好地满足航空航天复杂系统中上千条实时消息流的调度需要.

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

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.