基于发布订阅架构的在线时间触发调度方法

2023-10-17高一凡何锋于思凡

航空学报 2023年18期

高一凡，何锋，于思凡

北京航空航天大学电子信息工程学院，北京 100191

随着分布式综合模块化航空电子（Distributed Integrated Modular Avionics，DIMA）架构［1］的发展，航空电子系统需要具有更高的实时性、可靠性和安全性。机载网络［2］作为航空电子系统互联的关键技术，需要支持不同实时性需求的应用进行通信。时间触发以太网［3］（Time-Triggered Ethernet，TTE）采用了全局同步时钟，以保证时间触发消息确定性到达和有界抖动。

时间触发以太网依赖调度表对时间触发消息进行确定性调度，而调度表的求解和优化是典型的NP（Non-deterministic Polynomial）难问题［4-6］。传统的基于求解器的调度求解方法包括可满足性模理论［7-10］（Satisfiability Modulo Theories，SMT）、混合整数线性规划［11］（Mixed Interger Linear Programming，MILP）等约束求解方法。有学者通过拓扑分解［12］、简化约束条件［13］对SMT 法进行优化，减少了调度生成所需的时间。这些方法通过将网络拓扑、流量传输、应用需求等构造为一组约束方程并求解，从而得到可行调度表。但这类方法通常复杂度较高，难以在短时间内求解，因此更适用于小规模网络。另一类基于启发式的算法，如元启发式算法［14-15］、分组调度［16］等优化方法，它们拥有更快的求解速度，更好地平衡了调度表的求解时间和调度最优性，但启发式算法的性能与参数设置紧密相关且模型难以泛化，较难适用于不同的应用场景。

时间触发网络的配置并不总是静态的，例如网络拓扑可能会因为节点或链路故障而改变［17］；或者因为上层应用的变化，数据传输需求发生改变［18］，导致需要根据情况更新已生成的时间触发调度表，而静态调度算法通常需要离线计算时间触发调度表，然后将调度表配置下载到交换机或端系统中。所以，这类方法难以适应网络拓扑的变化，或者调度新增时间触发流量。

为了解决动态时间触发调度问题，增量式调度算法［19-20］被提出，它可以在已有调度表的基础上对新增时间触发流量进行调度，但所需时间仍然较长。另外，有学者提出离线等价策略［21-22］，该类方法提前计算离线调度表，然后进行在线更新，大大减少了对存储空间的需求和调度求解时间，但是该类方法只适合初始信息已知并且只有少量更新的场景。Li等［23］提出了一种基于ILP求解器的动态调度方法，该方法可以较快地生成自适应调度方案，但其中部分约束条件仅适用于特定的场景。本文提出了一种联合流量调度顺序和流量偏置进行调度求解的方法，该方法基于映射评价分数，同时求解流量调度顺序与偏置，但在大规模流量求解时，该方法的求解时间仍然过长。

调度表求解时间是调度算法的关键衡量指标之一，尤其是在网络拓扑和待调度流量频繁变化的动态场景中。适用于动态场景的调度算法通常需要较短的执行时间，并且需要在增量消息调度过程中不影响已调度消息的实时性，从而完成调度表的在线求解。考虑到数据分发服务在目前应用中的高灵活性，其基于发布/订阅的信息交互架构，为系统提供了松耦合的集成。本文将时间触发机制与数据分发服务进行结合，提出了基于发布/订阅的时间触发架构模型，实现主题订阅和消息转发分离，一方面基于数据中间件的集中控制，对时间触发流量进行在线调度，增加了系统的灵活性；另一方面通过时间触发网络保证关键消息传输的实时性。

本文首先提出了基于发布/订阅的时间触发网络架构，将数据分发系统的架构拓展到了时间触发网络中，总结了基于数据中间件生成调度表面临的问题；并针对上述问题，提出基于时间分片的在线时间触发调度算法，以提高调度表的求解速度，实现调度表的在线生成和增量式调度。

1 基于发布/订阅的时间触发网络架构

1.1 数据分发服务

数据分发服务（Data Distribution Service，DDS）是一个以数据为中心的中间件协议和接口标准，采用分布式发布/订阅体系架构，以中间件的形式提供通信服务。DDS中间件是一个软件层，它将应用程序从操作系统、网络传输和底层数据格式的细节中抽象出来，从而允许应用程序在不同的操作系统、编程语言和处理体系架构之间交换信息。

系统的基本架构如图1所示。DDS把所有本地存储的数据称作全局数据空间，统一管理主题订阅情况，并进行主题匹配。DDS提供了服务质量（Quality of Service，QoS）保证的数据共享。QoS为每个主题提供专属的服务策略，用于保证DDS消息的实时性，提高系统带宽利用率。应用程序通过发布和订阅由其主题名称标识的主题进行通信，并以主题中的数据对象作为信息共享的单元。

图1 DDS系统架构Fig.1 System architecture of DDS

1.2 时间触发调度

时间触发以太网提供了3种不同的流量类型：时间触发（Time-Triggered，TT）流量，速率约束（Rate-Constrained， RC）流量和尽力传（Best-Effort，BE）流量。其中TT流量延迟抖动最小，需要同步时钟的支持，用于对网络延迟、延迟抖动及传输确定性要求十分严格的应用。所有的TT流量消息按照预先设定好的时刻发送，优先级最高。RC流量消息的延迟确定且存在上界，用于对确定性和实时性要求稍弱一些的应用，并兼容航空电子全双工交换式以太网（Avionics Full DupleX switched Ethernet，AFDX）网络中的流量。BE流量用于实时性要求弱的应用，与传统以太网中的流量兼容。

在时间触发网络的输出端口中，TTE实行混合关键流量调度策略。为避免非TT流量对TT流量实时性产生影响，非TT流量在TT流量调度间隙，利用剩余带宽根据优先级策略进行调度传输，如图2所示。

图2 TTE流量调度Fig.2 Flow scheduling in TTE

时间触发调度可根据TT消息调度窗口的分布情况分为集中调度模式和多孔调度模式。集中调度模式下，调度表包含一个由若干个基本周期组成的矩阵周期，且每个基本周期又分为2段，TT消息集中于基本周期的前一段发送，后一段则用于传输RC消息和BE消息，并在每个基本周期末尾预留一定时间长度的保护间隔。多孔调度模式同样符合矩阵周期和基本周期的概念，但TT消息在基本周期中没有集中调度窗口的限制，TT消息根据自己的周期和偏置在基本周期中安排调度窗口，从而在TT调度窗口之间形成多个时间孔隙，用于RC消息和BE消息的传输。

1.3 基于发布/订阅的时间触发架构模型

基于发布/订阅的时间触发架构模型如图3所示，相较于传统DDS架构，该架构模型解耦了消息的主题订阅和消息传输。通过将主题订阅和消息转发分离，将发布/订阅模型用于主题管理并将时间触发架构用于消息转发，提高了时间触发网络的灵活性和扩展性。

图3 基于发布/订阅的时间触发架构Fig.3 Publish/subscribe based time-triggered architecture

消息的主题订阅基于发布/订阅架构中数据中间件的集中管理，并通过时间触发网络进行传输，从而保证系统的实时性。在该架构下，发布者发布消息主题到数据中间件，订阅者订阅相关主题，数据中间件完成主题的统一匹配。同时，数据中间件存储网络的拓扑结构和全局消息主题，从而有效地完成消息分类、优先级划分和传输路径规划，并生成时间触发调度表。然后，数据中间件将生成的时间触发调度表下发至网络中的每个交换机，同时根据端系统发布的主题，向端系统返回相匹配的主题并下发对应的调度表。端系统根据下发的调度表进行时间触发消息的发送和接收，而交换机也根据调度表完成消息的路由与转发。时间触发网络则保证了系统中消息传输的实时性。

基于发布/订阅的时间触发架构模型，结合时间触发网络的特点和需求，在传统DDS系统架构的基础上进行改进：主要包括发布/订阅主题和消息关联、QoS等级转化为时间触发网络消息分级以及在线时间触发调度表的生成3个方面。

发布/订阅主题和消息关联。DDS系统应用之间根据主题匹配进行消息推送，而在时间触发网络中，则通过不同关键级别的消息传输信息。因此，该架构中每一个主题对应一种消息，数据中间件主要完成不同应用间消息需求的匹配。

QoS等级转变为时间触发消息分级。DDS系统的QoS包含范围较广，例如带宽分配、主题及其内容存活时间、截止时间等。对于时间触发网络，消息会按照关键级别分为TT、RC、BE 3类消息，以不同优先级进行传输。因此需要将QoS转化为传输消息的分级，按照不同消息类型和级别进行不同的处理。

在线时间触发调度表的生成。传统时间触发网络通常提前生成离线调度表，而调度表一旦生成，就难以更改。如果利用数据中间件规划调度表，则会产生新的问题。

首先，时间触发调度表生成时间过长。航空电子系统对实时性要求严苛，如果在线调度生成时间较久，将严重受影响系统的正常运行。目前常用的时间触发调度生成方法有约束求解器、启发式算法等，它们在固定的TT消息分布下虽然展现出了良好的性能，但是生成时间过长，且只能用于离线调度的场景。

其次，调度表的计算资源有限。调度表生成是一个完全NP问题，属于计算密集型问题。传统启发式算法通过多次迭代求得相应的结果，需要消耗巨大的计算资源。而数据中间件作为控制中心，其计算资源十分有限，传统启发式算法难以直接应用，因此需要降低现有调度表生成方法的复杂度。

最后，增量式调度的影响。离线调度表生成算法很少考虑网络和消息的动态变化，不适用于动态场景。动态时间触发调度求解主要针对具有强实时性要求的TT流量的动态变化。在消息传输过程中，可能会出现新增、减少或者改变TT流量的情况，而RC流量和BE流量在TT流量传输的空闲时间内传输，调度表求解的过程中不需要考虑这两类流量的变化。传统求解方法在TT流量发生变化时，需要重新求解网络中全部的时间触发消息。若需要进行在线调度求解，则当网络中有新增待调度消息，需要在已有调度表中找到一个合适的时间窗口，而删除已调度消息会产生闲置时隙，需要处理相应时隙并用于新增TT消息的调度。因此，需要设计一个灵活的增量式在线调度算法。

2 基于统一时间分片的在线时间触发调度算法

传统的离线调度表生成方法通常不支持TT消息增量调度，而已有的增量式调度方法计算时间过长，随着网络规模的增加，求解时间更加难以符合要求。因此，提出了一种基于统一时间分片的在线时间触发调度算法。首先将时间轴离散化为时间分片，调度消息至特定的时间分片；然后进一步提出时间分片的统一长度约束，缩减调度求解的搜索空间，大大缩短了调度表生成时间；并且可以在线性时间复杂度下逐条消息增量式调度生成初始调度表，还可对已生成调度表进行增加或删除。其次，描述了基于统一时间分片的在线时间触发调度算法在发布/订阅架构下的实现过程，包括系统中数据中间件和交换机的初始化和在线调度阶段的运行流程，使系统可以利用数据中间件实现基于统一时间分片的在线时间触发调度算法。

2.1 在线时间触发调度规划方法

2.1.1 网络模型

一个典型的通信网络可以看作是实时应用的调度平台，可以将其建模为图G={V，E}，其中V为网络节点集合，包括端系统节点和交换机节点vk∈V，E为有向边的集合。(va，vb)∈E表示连接顶点va到vb的一条物理链路。

M为网络中的时间触发消息集合，其中消息mi∈M是周期性消息。每条消息mi用五元组＜Ti，li，ri，σi，δi＞表示。其中，Ti为消息的周期，li为消息的长度，ri为消息的传输路径，σi为消息的源端系统节点，δi为消息的目的端系统节点。

消息从源节点到目的节点的传输路径可以表示为

由消息周期Ti，可以求得该消息组中消息周期的最小公倍数Tlcm和最大公约数Tgcd，则该消息组中任意一条消息的周期Ti=niTgcd，其中ni∈ℤ。本文采用最短路径算法生成TT消息路径，消息集合中的消息最大跳数为hopmax。由于TT消息具有周期性，因此只需要规划消息集合在其周期的最小公倍数Tlcm（即消息超周期）时间内的消息调度表即可。

2.1.2 时间分片划分和约束

为了优化调度搜索空间，提高调度求解速度，考虑将时间轴离散，将连续的时间偏置选择转变为离散的时隙选择。因为调度求解是针对消息集合的超周期Tlcm考虑，而集合中的消息周期长度不小于Tgcd。因此，首先将一个超周期长度按照消息周期的最大公约数Tgcd均分成时间分段。另外消息需要在截止期限前经过多跳传输到达目的节点，所以根据网络最大跳数进一步将时间分段划分为时间分片，并将消息调度至路径上各跳链路的时间分片中，占据时间分片中对应长度的时隙进行传输。这样可以保证在一个时间分段长度内，集合中周期最小的消息经过最大跳数传输，仍能在截止期限内到达目的节点。调度求解问题本质上是将链路资源与消息传输需求进行匹配，通过时间分片的划分，将链路资源表示为离散的时间分片，将消息传输与时间分片匹配，从而优化调度求解过程，提高求解效率。以下为具体划分和表示过程。

首先将网络中各链路(va，vb)上的一个超周期时间长度Tlcm按照消息周期的最大公约数均分成时间分段si，(va，vb)，并以消息周期的最大公约数Tgcd作为时间分段的长度，表示为

则一个超周期内的时间分段数Ns为

将每一个时间分段按照网络最大跳数hopmax划分为时间分片pi，(va，vb)，表示链路(va，vb)上的第i个时间分片：

式中：startpi，(va，vb)为时间分片pi，(va，vb)的起始偏置时刻；endpi，(va，vb)为时间分片pi，(va，vb)的结束偏置时刻，lengthpi，(va，vb)为时间分片pi，(va，vb)的长度。

时间分片的长度取决于时间分片中传输的具体的TT消息长度和网络的物理链路带宽。假设时间分片包含一组消息M={mj}，链路的带宽为B，则在不考虑消息传输切换间隔下，链路(va，vb)上的时间分片长度满足：

将链路(va，vb)上一个超周期内的时间分片，表示为

在一个时间分段si内，时间分片由左向右延拓，其余时间分片则由中心节点向外延拓，这样可以尽可能减少消息调度过程中由于时间分片长度不断增加而发生重叠的情况。可以得出，对于si，(va，vb)分段中的p1，(va，vb)和phopmax，(va，vb)，其时间分片分布为

对于其他的节点，即当1＜j＜hopmax时，根据消息最大跳数hopmax，可以求出pj，(va，vb)的中心点为

可得

则时间分片不发生重叠（即无冲突）的条件为startpj，(va，vb)≥endpj-1，(va，vb)。

在消息传输过程中，要保证消息前后两跳时间分片不冲突，需要检测该跳链路的上一跳链路的时间分片结束时刻，满足上一跳链路的时间分片结束时刻不大于该跳链路当前时间分片的开始时刻；另外需要检测该链路下一跳链路的时间分片开始时刻，满足其开始时刻大于该跳链路当前时间分片的结束时刻。由于网络中各链路的时间分片长度独立，上述验证过程复杂度过高，求解时间较长，不适合实时在线进行计算，因此进一步提出时间分片统一长度约束，限制时间分片的长度满足：

因为时间分片是将时间分段按照最大跳数hopmax划分得到的，当时间分片满足统一长度约束时，相邻2个时间分片不会发生重叠。网络链路的时间分段和时间分片分别为图4的上、下部分。

图4 时间分片Fig.4 Time slicing

2.1.3 时间分片调度

对于某条消息mi，该消息需要在超周期Tlcm的时间内传输Tlcm/Ti次。设消息在第k跳链路所对应的时间分片下标为idi，k，其中id用于标识消息传输占用的时间分片的下标。因此根据消息的传输路径，第n个消息传输时，只需满足：

在此条件下，下一跳的时间分片始终晚于上一跳时间分片，即满足TT消息可调度且不会冲突。同时满足消息的发送时间大于消息产生的时间，且消息到达时间小于消息的截止期限。

在此模式下，需要判断在消息加入后，时间分片的长度是否满足约束中的统一长度。此时，满足式（12）条件的时间分片数目为

即在符合条件的时间分片中，选出消息传输路径跳数hopi个时间分片即可。则式（14）的复杂度为复杂度分布不均且可能会非常高。求解时间难以满足在线调度的实时性要求。

因此，本文约束消息在传输路径中相邻跳数对应的时间分片也必须相邻，即

在此条件下，由于最大跳数和时间分片均为固定值，单条消息可以在不超过复杂度下得到求解，时间分片长度等于分片内消息传输所需的时间。

对于某条消息mi，其传输路径为ri，将消息传输路径中各条链路对应的时间分片定义为一个时间分片分组：

当消息从源节点到目的节点的路径跳数为hopi时，可以求得该消息满足约束的时间分片的分组数目为

为避免下一条TT消息放入过程中超过时间分片的最大约束长度，将TT消息传输路径上各链路对应的时间分片中，最长消息长度作为其路径负载：

为了避免消息都集中于某个时间分片中，在消息调度过程中，选择消息对应的全部时间分片分组中负载最小的分组，以实现链路的负载均衡：

从而不仅可以避免TT消息集中于个别时间分片内，还保证了RC消息传输所需时隙，降低了RC消息的排队延迟，提高了算法的调度性能。

基于统一时间分片的在时间触发调度算法优化了消息调度求解的搜索空间，显著提高了调度表的求解速度，可以在线性时间复杂度O(n)下，迅速地生成大规模消息的时间触发调度表。同时，在消息增加和删除时，可以在常数阶时间复杂度O(1)内得到修改后的调度表。该方法不依赖离线调度表，可进行在线时间触发调度求解，能够应用在高实时性需求的机载网络中。

2.1.4 算法流程示例

采用简单拓扑对前述调度生成算法及其流程进行说明。示例拓扑如图5所示。

图5 示例网络拓扑Fig.5 Example network topology

现有TT消息参数如表1所示。由表1可以计算出该组消息的周期最小公倍数为8 ，最大公约数为2 ，消息传输路径的最大跳数为3。对于第1条消息，周期为2 μs，在超周期内需要传输4次，并且每次只有1组时间分片可行解，则第1条消息调度的结果如图6所示。

表1 TT消息参数Table 1 TT message parameters

图6 调度TT1消息Fig.6 Scheduling TT1

第2条消息周期为4 μs，在超周期内需要传输2次，并且每次传输的时间分片可行解数目为4，根据式（17）选择对应负载最小的时间分片分组。第3条消息采用的方法类似，放入消息后结果如图7所示。

图7 调度TT2、TT3Fig.7 Scheduling TT2 and TT3

TT4消息的周期为4 μs，超周期内需要传输2次。根据式（16）可以得到共有4个可行的时间分片分组，对应的负载loadri(n)分别为TT1、TT2、TT3和TT1所占用的时间窗长度。选取其中最小的，将消息TT4放入，结果如图8所示。

图8 调度TT4Fig.8 Scheduling TT4

由上述调度过程可以看出，在划分时间分段和时间分片后，只需要把消息放入对应的时间分片中，并根据消息长度之和和链路的带宽计算出消息传输所需时间，从而得到时间分片长度。

2.2 在线时间触发调度算法部署

2.2.1 系统初始化

1）数据中间件初始化

数据中间件主要负责TT调度表生成，其根据时间分片信息计算出时间触发调度表，并下发调度表信息至交换机和端系统中。

数据中间件初始化需要3个步骤：加载全局信息、TT消息路径规划、TT调度表求解。

加载全局信息，包含发布/订阅架构模型的拓扑信息、网络带宽、生成网络拓扑的相关数据结构。另外，数据中间件需要加载初始TT消息，这是系统启动的必要消息，初始调度表的生成也是一个逐条消息调度的增量过程。

TT消息路径规划，是根据全局拓扑，生成TT消息的传输路径。为加快求解速度、减少路由跳数，以减少时间片的分片个数，本文采用最短路径算法生成路由。因为最大跳数直接影响时间片分片的数目，进而影响TT消息增量规划时所需的计算时间。在消息路径规划时，需要遍历TT消息，记录TT消息的最小公倍数Tlcm，最大公约数Tgcd和对应的最大跳数hopmax。

TT调度表求解。根据TT消息周期的Tlcm，Tgcd和hopmax，可以为每一条链路规划一个基本的时间分段列表和时间分片列表，并初始化其长度为0。此时遍历TT消息，根据2.1节的在线调度算法，确定每个TT消息对应的时间分片，将消息调度至其中。利用链路带宽和TT消息的长度计算出所需要的传输时间，并更新时间分片的长度。在消息调度过程中，根据时间分片的分配进行负载均衡，提高消息的可调度性。

2）交换机及端系统初始化

接收到数据中间件下发的TT调度规划信息后，交换机的路由模块和队列模块需要进行初始化，同时端系统应用开始根据调度表发送消息。

首先，交换机路由模块需要根据配置信息生成TT消息的静态路由表，以便将接收到的消息迅速转发至相应的端口队列。同时，解析得到消息中的TT调度表配置，生成并下发各个输出端口的配置信息。

队列模块根据消息周期的Tlcm和Tgcd生成对应的时间分片，解析配置信息中的消息序号和消息长度，并依次放入对应的时间分片中。根据时间分片计算公式，得到时间分片的起始时间和终止时间，并开始进行时间分片的轮转。

2.2.2 在线增量调度阶段

由于系统运行过程中，会有主题的匹配和解耦，导致TT消息调度表会随时改变，数据中间件在消息调度生成和端口队列处理时间分片的变化都需要快速调整，处理流程如图9所示。

图9 在线增量调度流程Fig.9 Online incremental flow scheduling

1）数据中间件在线增量时间触发调度

在完成主题匹配和解耦后，会引发TT调度表变化。当新增TT消息时，模型的端口队列根据时间分片信息，根据2.1节中的算法插入新增消息并更新时间触发调度表。当删除已调度TT消息时，根据TT消息传输路径，遍历输出端口对应的时间分片队列，找到该TT消息对应的时间分片，并删除TT消息。

2）端口队列在线时间触发队列

端口需要根据新的配置信息，更新时间分片。新增消息时，将消息对应的静态路由信息保存在路由模块中，并根据时间分片长度重新计算新增消息对应的时间分片的起始时刻和结束时刻。

根据2.1节算法，当时间分片位置不同时，需进行不同处理。当时间分片序号对hopmax取模运算等于1的时候，表示该时间分片是对应的时间分段中的第1个时间分片，因此时间分片的起始时刻固定，只需改变时间分片的结束时刻。当序号对hopmax取模运算等于hopmax时，表示该时间分片是对应的时间分段中的最后一个时间分片，因此时间分片的结束时刻固定，只需要改变时间片的起始时刻。当序号对hopmax取模运算结果介于1和hopmax之间时，时间分片的中心位置固定，起始时刻和结束时刻都会改变。由于时间分片之间不会重叠，不会影响上一跳和下一跳的时间片，仍可以保证TT调度表的合理性。

3 算法评价与分析

3.1 实验参数设置

实验采用如图10和图11所示的2种拓扑结构，图10为小规模拓扑结构，包含8台端系统和4台交换机，以及1个数据中间件。每个交换机与2个端系统以及另外3个交换机和数据中间件相连，链路带宽为1 Gbit/s；图11采用基于空客A380的拓扑结构，包含8个交换机和16个端系统，以及1个数据中间件，拓扑连接关系如图11所示（其中数据中间件与8台交换机连接），链路带宽为1 Gbit/s。数据流的配置信息随机生成，其中设置TT消息周期的Tlcm=2 ms，Tgcd=32 ms。消息的源节点与目的节点从端系统中随机选取（源节点与目的节点不相同且之间经过交换机），同时根据航空电子系统中的消息特点，TT消息长度在64～1 518 bytes均匀分布选取。计算机CPU为英特尔i7-9750h处理器，标准频率为2.60 GHz，最高主频4.2 GHz，内存为24 GB，64位操作系统，实验基于OMNeT++网络仿真平台。

图10 案例1～3拓扑结构Fig.10 Topology of case study 1～3

图11 案例4～5拓扑结构Fig.11 Topology of cases 4～5

3.2 实验案例设置

设置5个实验案例，基于图10和图11 2种不同规模的拓扑结构，将本文提出的基于统一时间分片的在线时间调度算法与传统SMT算法和新提出的MSS算法［24］的性能表现进行对比。

案例1～案例3基于图10所示的小规模拓扑。案例1根据调度求解时间，比较3种算法的求解速度；案例2进一步对比本文算法与SMT算法求解生成的调度表中RC消息的平均延迟和最坏延迟，比较2种方法的调度求解性能。在保证时间触发消息的实时性前提下，RC消息延迟越小表示调度算法的性能越好。案例3用于验证本文算法最大调度规模。在典型拓扑结构下，分别对含有1 000、1 500、2 000条TT消息的网络进行调度求解，计算RC消息最坏延迟并验证其是否满足最晚截止期限要求。为进一步验证本文算法的调度性能，案例4和案例5采用图11所示的基于空客A380的拓扑结构，对比本文算法与MSS算法在不同流量规模下的表现。案例4对比本文算法与MSS算法的调度成功率，调度成功率越高则表示算法求解的可调度性越好，能够求解更大规模消息的调度表。案例5对比2种算法的链路时隙资源利用率和链路时隙占用方差。链路时隙利用率高说明消息传输利用了链路资源更加有效。而链路时隙占用方差则可以衡量算法在负载均衡方面的性能。

1）案例1

本案例对比本文所提的在线调度算法与传统SMT算法和MSS算法的调度求解时间。

表2为在不同消息规模下，2种方法的求解时间。由于SMT算法不支持增量调度，所以表中的TT消息数目表示网络中传输的TT消息总数。因为本文所提算法是逐条消息进行调度，因此通过表中每行之间求解时间的差值可以算出本文方法进行增量式调度所需要的时间。由表2可以看出本文所提算法求解速度远快于传统SMT算法和MSS算法。本文方法基本可以在毫秒级时间求解生成调度表。同时随着TT消息的数目的增加，本文算法求解的时间近似线性增加，即随着已调度消息规模的增加，增量调度每条消息的时间始终不变，约为0.037 ms。而SMT求解器的求解时间近似为指数增长，SMT求解器通过遍历所有情况得到可行解，当TT消息较少的时候，搜索空间较小且可行解数目较多，因此可以在秒级的时间内得到结果。但随着TT消息增加，搜索空间骤增，而可行解数目下降，导致求解时间大幅增加。MSS算法的求解时间随着消息规模的增加近似为平方增长，在TT消息数目不超过200条时，MSS算法的求解时间比SMT算法快，但相比本文所提算法，求解时间仍然过长，约是本文算法求解时间的40倍；而当TT消息数较大时，MSS算法的求解时间远远超过本文所提算法的求解时间，当调度2 000条TT消息时，MSS算法的求解时间是本文的500倍左右。对于航电系统而言，实时性至关重要，在消息规模增加时，本文所提算法生成时间仍然较短，更适用于系统的在线调度。

表2 求解时间对比Table 2 Comparison of solution time

2）案例2

在时间触发调度求解过程中，除了需要保证TT消息的可调度性外，还需要考虑RC消息的端到端延迟。在确保TT实时调度的前提下，应尽可能降低RC消息的端到端时延。本案例对比基于统一时间分片的在线时间触发调度算法与离线调度算法（SMT算法）下RC消息的平均端到端延迟和最坏端到端延迟。案例随机生成100条TT消息和200条RC消息，分别采用SMT求解的调度表和在线时间触发调度算法生成的调度表进行求解，得到的结果如图12和表3所示。

表3 调度方法对比Table 3 Comparison of scheduling methods

图12 调度方法延迟对比Fig.12 Comparison of scheduling method delay？

可以看出，在线式集中调度求解所得的RC消息的平均延迟相比SMT离线调度算法降低了9.98%，RC消息的最坏延迟降低了17.44%。而在线式集中调度求解触发调度表的时间要远远小于SMT求解时间，本文所提方法可以在毫秒级求解得到TT调度表，规划一条单独的TT消息，所花费的时间在微秒级别，可以满足航电网络在线调度的实时性要求，同时RC消息的最坏延迟仍满足要求。本案例表明本文方法提升了RC消息的调度性能，同时大大降低了时间触发调度表的生成时间，使得本文方法更加有可能用于在线生成时间触发调度表的情况，符合航空电子系统对时间触发调度生成的实时性要求，从而增强了系统的灵活性。

3）案例3

大规模流量调度分析。SMT算法求解TT调度表困难，耗时较长，当TT消息上升到500条时，会出现求解时间过长和难以求解的问题。而本文所提在线调度算法仍可以快速求解得到对应的TT调度表。因此，本案例随机生成不同规模的TT消息，并生成对应规模的RC消息，使得RC消息和TT消息的比例为2∶1，通过仿真得到不同规模下RC消息的最坏端到端测试本文算法在大规模消息下的调度性能表现，其结果如图13所示。

图13 大规模消息在线调度最坏延迟Fig.13 Worst-case end-to-end delay of large-scale messages

由图13（a）可以看出，当TT消息数目为500和1 000时，RC消息的最坏延迟仍较低。当TT消息数目上升到1 500时，即含有1 500条TT消息和3 000条RC消息，此时RC消息的最坏端到端时延明显变大，但此时的最坏延迟依然满足RC消息的实时性需求，不会影响规划的时间触发调度表的可调度性。

当消息规模上升到2 000条TT消息和4 000条RC消息时，其平均延迟和最坏延迟如图13（b）所示。当消息达到此规模时，RC的消息的最坏端到端时延显著增加，此时所规划的调度表已无法满足系统的实时性要求。由此可以看出，本文所提算法针对案例中的实验参数设置，最少可以支持1 500条TT消息和3 000条RC消息规模的实时性调度，同时求解调度表所需时间保持在毫秒级，因此可以应用于在线调度。

4）案例4

调度成功率对比。流量的调度成功率定义为成功调度的流量数占网络中总流量数的比例。图14为2种方法在不同时间触发流量数下的调度成功率。当消息数为200条时，2种方法调度成功率均为100%，当消息数为500条时，本文算法调度成功率比MSS算法提高了3.5%，而随着网络中的TT流数目的进一步增加，MSS方法的调度成功率相比本文算法分别提高3.2%，4.9%和6.1%。由此可得在小规模流量下，本文算法的调度成功率略高于MSS算法，在大规模流量下，本文算法的调度成功率略低于MSS算法。结合案例1的实验结果，本文算法在流量数目较多时的求解速度远远高于MSS方法，因此本文所提算法针对大规模流量时，在保证较高调度成功率的前提下，仅牺牲了一部分调度成功率，但大大提高了算法的求解速度，保证了算法的求解效率和求解成功率。

图14 时间触发消息调度成功率Fig.14 Success rate of time-triggered message scheduling

5）案例5

链路时隙利用率和链路时隙占用方差对比。链路时隙利用率定义为链路中被占用的时隙数与链路总时隙数之比，链路时隙利用率高则代表网络中的TT流占据了更多的时隙，更加有效地利用了链路资源，结果如图15中折线所示。而链路时隙占用方差则定义为网络链路的时隙中传输的TT消息长度的方差，以此来衡量网络的负载均衡程度。链路时隙占用方差越小，意味着负载均衡程度越高，结果如图15中柱状图所示。

图15 链路时隙资源对比Fig.15 Network link time slot resource comparison

从图15可以看出，本文所提算法在不同TT流数目下的性能表现均高于MSS算法，而随着TT流量规模的增加，2种方法的表现逐渐接近。在TT流数目为20条和1 000条时，本文所提方法的链路利用率相比MSS算法分别提高了3.1%和0.6%，在不同TT流数目下本文算法的方差均小于MSS算法。实验案例表明：由于本文所提算法在调度流时考虑了可调度的时间分片的占用情况，因此避免将流量调度至占用率较高的时间分片中，从而实现了不同链路负载的均衡。