基于二维装箱问题的TTE调度表生成算法  

TTE scheduling table generation algorithm based on two dimensional packing problem

作　　者：郭袁贾 GUO Yuan-jia(Institute 706,Second Academy of China Aerospace Science and Industry Corporation,Beijing 100854,China)

机构地区：[1]中国航天科工集团第二研究院七〇六所,北京100854

出　　处：《计算机工程与设计》2021年第8期2159-2166,共8页Computer Engineering and Design

摘　　要：为简化时间触发以太网调度表生成的复杂度并增强灵活性,对调度表生成算法进行研究。所提算法支持通讯任务的动态添加,特别是将链路时间资源抽象为“空箱子”,并将时间触发通讯任务抽象为“二维物品”,这种抽象利用无重叠二维装箱问题的特性来满足数据帧无冲突传输,利用二维装箱算法得出调度表。仿真结果表明,当网络中同时存在较多通讯任务时,改进算法可以有效降低链路的时间资源占用率。To simplify the complexity and enhance the flexibility of TTEthernet(time-triggered Ethernet)scheduling table gene-ration,the scheduling table generation algorithm was studied.The proposed algorithm supported the dynamic addition of communication tasks,especially the time resource was abstracted as an empty box and the time-triggered communication task was abstracted as a two-dimensional item.This kind of abstraction used the characteristics of non-overlapping two-dimensional bin-packing problem to meet the data frame conflict free transmission.The scheduling table was obtained using two-dimensional bin packing algorithm.The simulation results show that the improved algorithm can effectively reduce the time resource occupancy rate of the link when there are many communication tasks in the network.

关 键 词：时间触发协议 实时系统 时间触发以太网 调度表生成 二维装箱算法 

分 类 号：TP393.11[自动化与计算机技术—计算机应用技术]