郭袁贾

(中国航天科工集团第二研究院 七〇六所，北京 100854)

0 引 言

自时间触发以太网(time-triggered Ethernet，TTE)[1-4]概念提出以来，关于调度表生成的研究就一直在持续，调度表生成问题被认为是NP困难问题[5]，目前没有算法可以求解出这个问题的精确最优解，因此大多数算法都致力于生成工程上可用的调度表。传统的调度表生成算法是例如文献[6]和文献[7]中提出的利用SMT求解器进行求解的方法。这之后出现了一些利用启发式算法对调度表进行求解的方法，例如文献[8]中使用了粒子群模拟退火算法，文献[9]中使用了模糊粒子群优化算法，文献[10]中使用了遗传算法。这些启发式算法提高了全局寻优效率，但是当通信任务较多时会导致算法运算时间快速增加，为了解决这个问题，文献[11]和文献[12]中提出了二维装箱算法和启发式算法结合的方法。混合二维装箱算法虽然降低了调度表生成的运算时间，但是仍然存在以下问题：①采用了固定的时隙来传输数据帧，虽然这样可以简化问题，但是实际工程应用中通信任务数据帧通常是不一致的；②无法满足通讯任务动态添加，调度表动态更新的需求，这导致当前的算法无法满足实际工程应用中复杂多变的实际需求。为了解决上述问题，基于二维装箱问题提出了一种调度表生成算法。

1 问题抽象建模

1.1 网络模型

本文参考了文献[5]中的模型，主要关注全双工链路下数据帧的传输，参考了文献[11]中设计的较为复杂的树形网络拓扑结构，如图1所示。……