基于负载均衡的大规模TTE消息调度表生成方法

A load-balanced TTE scheduling method for large-scale messages transmission

摘要:

在复杂拓扑条件下，机载网络存在大规模数据的高效传输需求. 此时传统的调度表生成方法存在高时间复杂度的问题. 为了有效解决这一问题，本文提出了一种基于负载均衡的时间触发以太网（Time-Triggered Ethernet，TTE）消息调度表生成方法. 该方法首先生成消息的备选较短路径集合，综合考虑消息长度和链路负载来选择消息路径，得到具有负载均衡特性的路径规划结果，然后以提高时序规划效率为目的，基于静态优先级生成调度表，根据消息长度和周期进行排序，并使用“背靠背”的规则进行调度分配，以保证消息的实时性和确定性. 仿真结果表明，当可调度消息帧达6000条以上时，在保证消息实时性的前提下，该方法比传统的满足性模理论（Satisfiablility Modulo Theory, SMT）时间规划方法减少90%以上的计算时间，计算效率提升10~100倍. 可见该方法适合于求解复杂大规模数据调度表的生成问题，本文的研究为改善机载网络的消息调度性能提供了一种可行方案.

Abstract:

There are ungent requirements of large-scale messages transmission in the airborne networks with complex topologies. When the triditional Time-triggered Ethernet ( TTE ) scheduling methods are used to meet a requirement, the time complexity is very high. To solve this problem, we in this paper propose a new TTE message scheduling method based on the idea of load balancing. In this method, a set of candidate paths is firstly generated and then selected according to the message length and the data flow link load. Those paths with load balancing characteristics are choosen. Then the messages are scheduled based on static priority, sorted according to message length and cycle, and allocated by using the " back to back " rule. Finally, the method is compared to the triditional Satisfiablity Modulo Theory (SMT) method to illustrate its performance. Simulation results show that, while the method can reduce the computation time by more than 90% when the schedulable message frames are more than 6000, the computational efficiency is improved by 10~100 times on the basis of ensuring the real-time performance of the message. Therefore, the method is suitable for complex large-scale data scheduling table generation and can feasibly improve the message scheduling performance of airborne network.