在具有时间、任务和安全等多关键性需求下的航空电子系统中，网络一直是体系架构的核心技术之一。时间触发以太网(Time-Triggered Ethernet, TTE)是一种基于802.3以太网的确定性组网方案，增加了时间触发(Time-Trigger, TT)机制，提高了高关键级别任务的消息传输确定性^[1-2]。而TT消息需要一个全局TT消息调度表来避免不同时间触发窗口之间的冲突^[3]。
先进综合航空电子系统采用时间触发以太网，无论航空电子系统的状态如何，全网TT消息时间表都是静态的。针对静态调度表的设计，各种启发式TT消息调度算法得到了广泛的研究，但具有不同的计算复杂度^[4-6]。
随着满足性模理论(Satisfiability Modulo Theories, SMT)的提出^[7-8]，TT消息调度可利用SMT求解逻辑公式的可满足性。因为TT消息是周期性的，可以用公共周期内无限重复有限集来表示^[9]。将SMT引入到TT消息调度规划中，可以方便地获得一个可行的TT消息调度表^[10-12]。
然而，传统消息延迟统计的是从终端系统的缓冲器向交换机发送消息时开始到终端系统接收到消息结束的一段时间，并没有考虑到终端系统上消息生成后在缓存器的等待延迟^[13-15]。事实上，一个TT消息帧在调度之前可能要在终端系统中等待一个完整的传输周期才能等到发送窗^[16]。在硬实时系统中，TT消息的生成时间是已知的，可以通过减小TT消息的生成时间与调度时刻的差异，使得TT消息延迟的大幅度减小。许多研究人员试图综合任务和网络，得到一个完整的TT消息调度表^[17-19]。
Fraboul的团队认为松散时间触发架构(L-TTA)在航空电子系统中更好^[20]。除了时间触发之外，L-TTA还可以实现一些不确定的调度机制，如速率约束(Rate-Constrained, RC)消息中的多优先级。在L-TTA中，系统和网络有各自的同步机制，任务级时间和网络级时间是不一致的。而基于网络级时间的准确生成时间很难预测，其随任务执行的不同而不同，在终端系统(End System, ES)的每次启动时也可能不同。并且任务级时间和网络级时间也在动态变化。因此，产生时间和触发时间之间的时间漂移也是动态的。会导致TT流量的抖动。必须有在线检测机制来防止TT流量出现剧烈的调度抖动。
为了解决这个问题，需要一个集中式控制器来支持TT消息的在线抖动判断和调度优化。McKeown等^[21]提出了软件定义网络(Software Defined Networking, SDN)来动态调整校园网上的网络配置。其中，网络的动态调整依赖于网络控制器的调度^[22]。Sampigethaya^[23]定性分析了SDN在航空领域的机遇和挑战，SDN在实时网络中具有巨大的优势。在此基础上，Heise等^[24]通过实验对航空电子全双工交换以太网(AFDX)的SDN硬件性能进行了评估。然而，交换机中的流表仅在初始阶段进行了静态配置，没有利用SDN网络动态调整的优势。随后，Kumar等^[25]引入了SDN来保证消息延迟，但只考虑了RC消息的优化问题。
最近，Lu等^[26]将SDN引入TTE网络，通过改变TT消息的传输方式，获取TT消息的生成时间。在TT消息的生成时间已知的情况下，基于SMT的常规算法仅可以得到一个可行的解，不能解决最优问题。Craciunas将任务和网络级调度联合合成问题转化为具有不同目标的混合整数规划(Mixed Integer Programming, MIP)问题^[12]。但是其发现，MIP花费了太多的时间来执行在线计算。随后，提出了一种适合在线调度场景的基于SMT的优化方法^[27]。虽然处理时间明显缩短，但这种基于SMT方法的处理时间仍然较长。在此基础上，Lu等^[26]对SMT的算法进行了优化，进一步减少处理时间。但这些调度算法都没有考虑到TT消息调度对RC延迟的影响^[28]。即，在任一终端系统中，一些TT消息的触发时间间隔较小时，RC消息不能在TT消息的间隔时间传输，只能等待大时隙出现，这就严重影响RC的消息延迟，并且浪费了网络带宽资源。同时，小时隙TT消息也会增加RC消息的抖动。
主要针对在小时隙TT消息情况下，RC消息传输确定性减小的问题，提出了一种大孔隙调度算法。首先，建立软件定义时间触发以太网(Software Defined Time-Trigger Ethernet, SDTTE)模型，阐明SDTTE网络中消息生成时间的获取方法以及TT消息的动态调度机制，描述网络和消息的数学模型；然后，论述TT消息的调度算法，在基本约束条件的基础上，描述小延迟调度算法^[26]和背靠背调度算法的实现方法。考虑到这2种算法在小时隙TT消息情况下，RC消息延迟过大的劣势，提出基于SMT^[7]的大孔隙调度算法；最后，利用OMNeT++软件进行仿真，比较3种算法的性能。
1 系统模型 1.1 网络架构 由于终端系统中的任务和网络之间的异步性，最坏情况下TT消息可能必须在终端系统中等待整个传输周期才能被调度出去^[16]。为了提高TTE的消息传输确定性，将SDN引入TTE，称为SDTTE^[26]，如图 1所示。其中，SDN将交换机的控制层集中起来，由集中控制器控制。流表由集中控制器规划，并下发到各个交换机，交换机只根据流表的指令进行数据的操作，即TTE交换机必须具备软件定义路径的能力^[29-30]。同时，终端系统不再需要TT消息调度表，TT消息产生后实时发送，交换机需要根据TT消息调度表对数据进行操作，TT消息调度表需要借助消息调度算法生成。

图 1 软件定义时间触发以太网的网络架构 Fig. 1 Network framework of SDTTE

图选项

当交换机发现TT消息没有流表或者其产生时间和触发时间之间存在巨大偏差时，系统需要重新配置。交换机将上报TT消息到集中控制器，以便其间接获得终端系统的发送时间^[26]。
当TT消息产生时间和触发时间之间不存在较大偏差时，系统不需要重新配置。定义了一个阈值和时间漂移，其中时间漂移表示上一次更新后探测到TT消息的第一次产生时间。如果时间漂移超过阈值，将在线重新配置流表。该阈值避免了在线更新TT消息调度表期间TT消息的大抖动。
无论系统处于何种状态，TTE交换机所需要的TT消息调度表都可以通过调度相应的控制器^[31]执行消息调度算法更新。
1.2 网络模型 一个TTE网络可以形式化表示为一个有向图G(V, E)，端点集合V表示通信节点，包括交换机和端系统；边集合E代表节点间有向通信链路，类似于文献[26]中的定义。
对于一个航空电子平台v_i?V，该平台的一个节点v_{i, j}，可表示为

(1)

式中：i为平台编号；j为平台内的子系统编号；rc_{i, j}为节点v_{i, j}的剩余计算资源；rs_{i, j}为节点v_{i, j}的剩余存储资源；rl_{i, j}为节点v_{i, j}的剩余链路资源。
对于一条带宽为c_{i, j, s, t}(如100 Mb/s)的物理链路e_{i, j, s, t}，可表示为

(2)

在时间触发网络中，利用虚拟链路的概念，对时间触发通信进行建模。一条虚拟链路是网络中从发送节点到一个或多个接收节点的逻辑数据流路径。一条从端系统v_{i, e1}到端系统v_{j, e2}的典型虚拟链接vl_p描述如下：

(3)

式中: 物理链路e_{j, n, j, n}表示消息帧在某个交换机内的传递链路。
1.3 消息类型 对于TTE网络，消息分为3种类型，时间触发消息、速率约束消息和尽力传消息。
1) 时间触发消息。即TT消息，需要一个全局调度表。其定义了消息发送的触发时间，同时也需要一个全局同步时钟来保证整个网络时间一致，从而支持全局调度表的触发调度。
2) 速率约束消息。即RC消息，具有2个重要的参数：带宽分配间隔(Bandwidth Allocation Gap, BAG)和最大帧长。前者也叫做最小帧间间隔，是在一个RC消息中2个连续消息帧的最小间隔时间，仅在发送终端有此约束；后者是消息帧长的约束。这2个约束与航空电子全双工交换式以太网(Avionics Full Duplex switched Ethernet, AFDX)中一致。
3) 尽力传消息。即BE(Best Effort)消息，是没有时间触发和宽带分配间隔保证的一类低优先级的以太网流量，但是其依然存在帧延迟约束^[32-33]。
1.4 消息模型 M可表示所有消息的集合。一个消息m_p∈M利用式(4)参数进行建模。

(4)

式中：P_p为消息周期；L_p为消息长度；vl_p为消息唯一对应的虚拟链路，决定消息传输的路径。
m_{p, q}表示消息m_p的第q个实例。

(5)

式中：T_{p, q}为消息实例m_{p, q}的产生时间。
消息帧f_{p, q}^{e_{i, j, s, t}}唯一对应了一个消息实例在特定链路e_{i, j, s, t}上的消息帧。F表示所有消息帧的集合。F_p^{e_{i, j, s, t}}∈F表示虚拟链路vl_p中在物理链路e_{i, j, s, t}上的所有消息帧f_{p, q}^{e_{i, j, s, t}}的有序子集。这些帧的顺序由帧的触发时间确定。此外，f_{p, 1}^{e_{i, j, s, t}}和f_{p, end}^{e_{i, j, s, t}}分别定义为有序子集F_p^{e_{i, j, s, t}}的第1个消息帧和最后1个消息帧。类似于文献[11]，一个消息帧f_{i, p, q}^{e_{i, j, k}}∈F_{i, p}^{e_{i, j, k}}可定义为式(6)的形式：

(6)

式中：of_{p, q}^{e_{i, j, s, t}}为消息帧f_{p, q}^{e_{i, j, s, t}}的发送触发时间；pf_{p, q}^{e_{i, j, s, t}}为消息帧f_{p, q}^{e_{i, j, s, t}}的周期；lf_{p, q}^{e_{i, j, s, t}}为消息帧f_{p, q}^{e_{i, j, s, t}}的传输时间；cf_{p, q}^{e_{i, j, s, t}}为消息帧f_{p, q}^{e_{i, j, s, t}}在物理链路e_{i, j, s, t}上的带宽。对于一个消息帧，有

(7)

对于一个交换机，触发时间包括发送触发时间和接收触发时间。其中，接收触发时间可以通过消息实例在上一链路的发送触发时间进行计算，如下：

(8)

式中：d_Innerhop为接收消息的技术延迟。
2 调度算法 在SDTTE网络下，间接知晓TT消息的生成时间，基于SMT的消息调度算法可以利用不同约束条件，得到各种不同指标的最优。通过分析在最小延迟(Minimum Delay, MID)调度算法^[26]的RC消息传输确定性不足，对基于SMT的消息调度算法进行优化，分析了背靠背调度算法。虽然增加了部分情况下RC消息传输确定性，但考虑到其TT消息等待延迟大，同时RC消息传输确定性不足的问题仍然存在，提出了大孔隙调度算法。
2.1 基本约束条件 TT消息调度表是在集群周期t_c内对所有TT消息f_{p, q}^{e_{i, j, s, t}}的触发时间of_{p, q}^{e_{i, j, s, t}}进行规划，对于?v_j≠v_k≠v_n∈V，m_p≠m_p1≠m_p2∈M，f_{p, q}≠f_{p, q1}≠f_{p, q2}∈F，常规的调度约束条件如下。

2.1.1 边界约束 所有TT消息的触发时间of_{p, q}^{e_{i, j, s, t}}必须在集群周期t_c内。由于触发时间是以任意的一个时间点作为参考时间，可以通过限制最大补偿和最小补偿的差来实现，即该差异不大于集群周期t_c。

(9)

2.1.2 防撞约束 任意2个消息帧不能同时出现在物理链路e_{i, j, s, t}上，即在物理链路e_{i, j, s, t}上任意2个消息帧不能同时传输。消息帧满足式(10)不等式：

(10)

式中：p₁、p₂为不同的消息编号；q₁、q₂为一个消息中不同的实例编号。

2.1.3 时序约束 根据一个消息的传输时序，一个消息实例m_{p, q}在物理链路e_{i, j, s－1, t－1}上的接收时间应该小于下一物理链路e_{i, j, s, t}上的发送时间，如下：

(11)

式中：d_Innerhop为交换机中的技术延迟。

2.1.4 延迟约束 端到端的延迟不应该超过消息的截止时间。一般地，消息的截止时间设为与消息周期pf_{p, q}^{e_{i, j, s, t}}一致。即端到端延迟不能超过消息的周期pf_{p, q}^{e_{i, j, s, t}}。

(12)

2.1.5 周期约束 根据消息的周期性，对于一个在物理链路e_{i, j, s, t}上的消息m_p，其所有消息帧的触发时间应该存在固定间隔。例如，第q₁个消息帧和第q₂个消息帧的间隔应该是q₂~q₁倍的消息周期。

(13)

当同步精度较差时，需要考虑同步抖动t_s，即在以上约束式(1)~式(5)的不等式左侧可以加入2t_s。
2.2 小延迟调度算法 在TTE网络中，为了使TT消息的性能尽量的好，即消息延迟和抖动尽量的小，可以采用MID调度算法，尽量减少TT消息产生时间和触发调度时间的间隔，规划TT消息的调度表。求解最小消息延迟可以使用MIP，但这需要花费大量的时间来完成解算过程。对于一个小于64条TT消息的网络，MIP求解器Gurobi需要的处理时间至少是SMT(Satisfiability Modulo Theories)求解器Yices的25倍(50 s/2 s)^[9]。虽然SMT求解器的处理时间短，但其不能直接求取最小消息延迟，需要加入延迟上界delaymin的约束。

(14)

式中: D_mp为每条消息的延迟；D为累加所有消息延迟得到的消息累计总延迟。
通过基本约束和式(14)，在SMT求解器中计算可行解；再利用二分法不断减小延迟上界delaymin的值，然后多次迭代，最后得到近似的最优解^[26]。
2.3 背靠背调度算法 如果TT消息的调度时间间隔小于最大消息帧长，称之为小时隙TT消息。在利用最小延迟调度算法计算TT消息调度时间时，其调度时间存在小时隙的可能，如图 2中MID所示。其中，B2B是背靠背(Back to Back, B2B)调度。当有小时隙TT消息时，RC消息必须等待这些小时隙TT消息执行完后，再传输该RC消息。

图 2 背靠背调度算法的RC消息延迟 Fig. 2 RC message delay by B2B scheduling algorithm

图选项

在图 2所示的MID调度算法下，RC消息的等待延迟，其值与小间隔的TT消息数量、TT消息传输时间和TT消息间隔时间有关。RC消息的抖动随之增加，降低了TTE网络的消息传输确定性。同时，由于这些TT消息的间隔小，间隔之间无法传递其他消息，相应的也减少了TTE网络的可用网络资源，浪费了网络带宽。
为了减少这些闲置的网络带宽，最容易想到的方法就是B2B调度，如图 2中B2B所示。其中，TT消息之间首尾相接，不存在间隙，充分利用网络资源。在该例子里，图 2中的RC消息不再需要等待TT消息的执行，可以在TT消息执行前传输。当然，这种B2B的调度算法一般仅存在于终端系统中，即在消息的发送端，所有的TT消息需要B2B调度。如果在所有交换机中TT消息也使用B2B调度，也将会严重影响TT消息的延迟。在TT消息较多的情况下，还将会影响TT消息的可调度性。
对于发送端的B2B调度，在发送节点v_{i, j}，对于任一TT消息f_{p1, q1}^{e_{i, j, s, t}}，总存在另一个TT消息f_{p2, q2}^{e_{i, j, s, t}}，它们是首尾相接的，形式化表示如下：

(15)

在基本约束条件中加入约束(15)，利用最小延迟调度算法中的SMT求解器，求解在此约束下的最小延迟可行解，实现B2B调度算法。
2.4 大孔隙调度算法 虽然B2B调度算法解决了网络资源浪费的问题，但RC消息延迟和抖动可能变大的问题依然存在，如图 3中B2B所示。其中，RC消息需要等待TT消息T0~T4执行完后，才能传输。RC消息的延迟在MID调度算法和B2B调度算法中没有得到改善，如图 3中MID和B2B所示。这种不确定的等待延迟，增加了RC消息的抖动，也降低了TTE整网消息的消息传输确定性。

图 3 大孔隙调度算法的RC消息延迟 Fig. 3 RC message delay by macrovoid scheduling algorithm

图选项

为了解决该问题，提出了大孔隙(Macrovoid, MAV)调度算法，如图 3中MAV所示。其中，任意2个TT消息首尾相接，或者间隔不小于最大消息帧长，RC消息可以在TT消息间隔窗口直接传输，不必等待TT消息传输完毕。该约束表示为

(16)

式中：lf_max为消息传输时间的最大值。
在基本约束条件中加入约束(16)，同样利用最小延迟调度算法中的SMT求解器^[7]，求解在此约束下的最小延迟可行解，实现大孔隙调度，流程如图 4所示。其中，迭代检查用于算法不收敛时的约束降级。同时，航空电子网络中TT消息占比较少，不满足式(16)的情况不会出现。两者共同保证了算法的收敛性。该算法不仅保证了网络资源的利用率，而且减少了RC消息的等待延迟，降低了抖动的大小，提高了TTE网络中RC消息的传输确定性。

图 4 大孔隙调度算法的流程图 Fig. 4 Flowchart of macrovoid scheduling algorithm

图选项

在MAV算法中，对于TT消息f_{p, q}^{e_{i, j, s, t}}，TT消息的最大等待延迟可以表示为

(17)

式中：n为一个首尾相接的TT消息子集；N为所有首尾相接的TT消息子集的集合；l_{p, q}^{e_{i, j, s, t}}为相邻TT消息的间隔时间；l_max为TTE网络消息的最大传输延迟，等于最大消息帧长与网络带宽之比。
对于RC消息，当无小时隙TT消息时，以图 3为例，利用网络演算，分析在任意物理链路中不同调度算法的RC消息最坏延迟，如图 5所示。

图 5 无小时隙TT消息时不同调度算法的RC最坏延迟 Fig. 5 RC message worst case delays by different scheduling algorithms without small time interval TT messages

图选项

当存在小时隙TT消息时，以图 3为例，利用网络演算，分析在任意物理链路中不同调度算法的RC消息最坏延迟，如图 6所示。

图 6 小时隙TT消息下不同调度算法的RC最坏延迟 Fig. 6 RC message worst case delays by different scheduling algorithms with small time interval TT messages

图选项

综上所述，在任意物理链路中，无论小时隙TT消息是否存在，理论上MAV调度算法的RC消息最坏延迟最小。
3 仿真实验 通过仿真实验分析MAV调度算法的性质。包括不同场景下的消息延迟、场景变化时RC消息的传输确定性。
3.1 实验配置 利用基于OMNeT++的自行设计软件进行实验，对3种调度算法进行性能评价。交换机模块和控制器模块的结构与Klein和Salih^[34-35]的描述一致，除了它们的缓冲器分为TT、RC和BE 3种类型缓冲器。
基于OMNeT++终端系统模块，如图 7所示。SFlow模块生成所有不同流量类型的数据包，RFlow模块接收所有不同流量类型的数据包，flowDispatch模块负责将数据包派发到不同SFlow/RFlow模块，Buffer模块临时存储不同的数据包，scheduler模块根据不同流量的约束实现不同流量的调度。flowCheck模块用于检查接收包是否满足规则，如时间触发调度表和BAG约束。

图 7 基于OMNeT Fig. 7 End system module based on OMNeT++

图选项

考虑到小时隙TT消息的概率较小，一般出现在局部航空电子网络。同时，航空电子网络规模庞大，很难通过有限时间的仿真得到最坏延迟(计算机配置：中央处理器CPU为i3-M380，内存为4 GB)。实验采用2个交换机的原型拓扑，仿真有小时隙TT消息的情况下航空电子网络各类消息的延迟，如图 8所示，图中，ES和SW分别为终端系统和交换机。图中有1个控制器。2个交换机和4个终端系统。控制器负责TT消息调度，2个交换机互连，每个交换机挂载2个终端系统。考虑到航空电子系统中主干网络采用的是有线网络，具有高独立性和高可靠性，没有加入干扰节点。仿真网络带宽为100 Mb/s。

图 8 网络拓扑 Fig. 8 Network topology

图选项

实验中的消息是终端系统随机生成的，对256条消息设置，如表 1所示。其中，间隔时间表示终端系统中TT消息生成的间隔时间，用于构造有/无小时隙TT消息的场景。为了保证实验对照组的真实性，除了TT消息的间隔时间，其他参数在这2种场景中是一致的。
表 1 实验消息配置 Table 1 Message configuration in experiment

终端系统	类型	参数	配置
ES 1~ES 4	TT	数量	32条
		帧长	1 250 B
		周期	32 ms
		间隔时间	150 μs/240 μs
	RC	数量	32条
		帧长	1 250 B
		BAG	32 ms

表选项






在小时隙TT消息的场景下，每个终端系统中的TT消息生成时间之间间隔150 μs，在传输完该TT消息(约100 μs)后，剩余的间隔时间无法传递RC消息，此时的RC消息需要等到大时隙时再传输。在无小时隙TT消息的场景下，每个终端系统中的TT消息生成时间之间间隔240 μs，在传输完该TT消息(约100 μs)后，剩余的间隔时间约为140 μs。能传递RC消息，此时RC消息不需要等待，可以直接传输。通过分析2种场景下RC消息延迟以及抖动，得到RC消息的传输确定性。
3.2 消息延迟分析
3.2.1 无小时隙TT消息 在无小时隙TT消息的场景下，3种调度算法的TT消息延迟，如图 9所示。实验结果表明，在MID调度算法和MAV调度算法中，TT消息端到端延迟近似，B2B调度算法中TT消息的端到端延迟较大，平均增加了170.4%。

图 9 无小时隙TT消息下不同调度算法的TT消息延迟 Fig. 9 TT message delays by different scheduling algorithms without small time interval TT messages

图选项

在无小时隙TT消息的场景下，3种调度算法的RC消息延迟，如图 10所示。实验结果表明，MID调度算法和MAV调度算法的RC消息延迟近似。B2B调度算法中存在长等待延迟，如图 3中B2B所示，其RC消息延迟增加了3.1%。

图 10 无小时隙TT消息下不同调度算法的RC消息延迟 Fig. 10 RC message delays by different scheduling algorithms without small time interval TT messages

图选项

统计所有TT消息延迟和RC消息延迟，如表 2所示。MID算法和MAV调度算法中所有消息延迟的最大值、平均值和标准差均相同。由于TT消息中不存在小时隙，MAV调度算法中新加入的约束就不会产生作用，其消息延迟与MID算法一致。在B2B调度算法中TT消息延迟的统计数据都有所增大。随着终端系统中的TT消息增加，B2B算法的劣势会愈加明显。
表 2 无小时隙TT消息下不同调度算法的消息延迟统计 Table 2 Statistics of message delays by different scheduling algorithms without small time interval TT messages

算法	TT/ms				RC/ms
	最大	平均	标准差		最大	平均	标准差
MID	0.401	0.355	0.069		32.396	31.298	0.789
B2B	1.610	0.960	0.371		37.595	32.259	1.708
MAV	0.401	0.355	0.069		32.396	31.298	0.789

表选项






MAV调度算法、B2B调度算法和MAV调度算法的计算耗时分别为59.264 s、42.86 s和58.738 s。此时，MAV调度算法的大孔隙约束(16)未能生效，等效于MID调度算法，计算耗时相近。

3.2.2 有小时隙TT消息 由于TT消息生成的时间间隔小于消息帧长，所以任意2个TT消息之间不会有RC消息的传输。使用基于OMNeT++的软件，仿真分析3种调度算法的消息延迟实验。
在小时隙TT消息的场景下，3种调度算法的TT消息延迟，如图 11所示。实验结果表明, MID调度算法的TT消息端到端延迟最小，MAV调度算法的最大TT消息延迟增加了19.5%。而B2B调度算法的最大TT消息延迟变化明显，增加了997.3%。MAV调度算法的平均TT消息延迟增加了11.3%。而B2B调度算法的平均TT消息延迟增加了618.3%。

图 11 有小时隙TT消息下不同调度算法的TT消息延迟 Fig. 11 TT message delays by different scheduling algorithms with small time interval TT messages

图选项

在小时隙TT消息的场景下，3种调度算法的RC消息延迟，如图 12所示。实验结果表明，MAV调度算法的RC消息端到端延迟最小。由于B2B调度算法存在图 3中的RC消息等待延迟，其RC消息的延迟有所增大。而MID调度算法由于同时存在图 2、图 3中的RC消息等待延迟，其RC消息的端到端延迟最大。但是它们的RC消息延迟的平均值较接近。

图 12 有小时隙TT消息下不同调度算法的RC消息延迟 Fig. 12 RC message delays by different scheduling algorithms with small time interval TT messages

图选项

统计所有TT消息延迟和RC消息延迟，如表 3所示。相比于MID算法，MAV调度算法中，RC消息延迟最大减少了10.8%。所有同类消息的标准差反应了消息的抖动情况，消息的抖动越小，消息的传输确定性越强。
表 3 有小时隙TT消息下不同调度算法的消息延迟统计 Table 3 Statistics of message delays by different scheduling algorithms with small time interval TT messages

算法	TT/ms				RC/ms
	最大	平均	标准差		最大	平均	标准差
MID	0.401	0.355	0.069		36.792	31.992	1.511
B2B	4.400	2.355	1.201		35.567	31.653	1.197
MAV	0.479	0.395	0.072		32.830	31.364	0.756

表选项






MID调度算法、B2B调度算法和MAV调度算法的计算耗时分别为58.454 s、20.280 s和178.448 s。分析不同场景下相同算法耗时不同的原因，对于B2B调度算法，TT消息的间隔时间更短、算法的搜索空间更小、计算耗时更少。对于MAV调度算法，大孔隙约束(16)生效，约束条件增加、计算耗时更长。
3.3 RC消息传输确定性分析 由于B2B调度算法的TT消息延迟一直较大，在传输确定性分析中忽略B2B调度算法，主要考虑MID调度算法和MAV调度算法，如图 13所示。其中，无小时隙TT消息的场景下，MID调度算法和MAV调度算法的RC消息延迟是一致的。

图 13 不同场景下不同调度算法的RC消息延迟 Fig. 13 RC message delays by different scheduling algorithms in different scenarios

图选项

实验结果表明，在有/无小时隙TT消息的2种场景下，MAV调度算法的RC消息延迟抖动较小，变化幅度为4.2%。而MID调度算法的RC消息延迟抖动较大，变化幅度为91.5%。相对于MID调度算法，MAV调度算法的RC消息的传输确定性增加了87.3%。
4 结论 在SDTTE中，TT消息调度表是保证TT消息在交换机之间无冲突传输的重要前提，不同的调度算法会根据不同的约束条件得到不同的消息延迟。所提出的MAV调度算法，减少RC消息在小时隙TT消息的场景下可能的等待延迟，保证了RC消息的传输确定性。基于OMNeT++的实验表明：
1) B2B调度算法的消息延迟最大，一般在资源缺乏的场景使用。
2) 在无小时隙TT消息的场景下，MAV调度算法和MID调度算法的消息延迟接近，MAV调度算法能保证消息传输的实时性。
3) 在小时隙TT消息的场景下，MAV调度算法的传输确定性最好，相对于MID调度算法，MAV调度算法的RC消息的传输确定性增加了87.3%。
由于调度算法是基于可满足性模理论的，从理论上分析算法复杂度较为困难，后续可以对可满足性模理论进行深入研究，分析不同约束下的算法复杂度。

参考文献

[1]	KOPETZ H, ADEMAJ A, GRILLINGER P, et al. The Time-Triggered Ethernet (TTE) design[C]//Proceedings of the 8th IEEE International Symposium on Object-Oriented Real-Time Distributed Computing. Piscataway: IEEE Press, 2005: 22-33.
[2]	STEINER W, BAUER G, HALL B, et al. TTEthernet dataflow concept[C]//Proceedings of the 8th IEEE International Symposium on Network Computing & Applications. Piscataway: IEEE Press, 2009: 319-322.
[3]	KOPETZ H. Event-triggered versus time-triggered real-time systems[M]. Berlin: Springer, 1991: 86-101.
[4]	GOPALAKRISHNAN S, CACCAMO M, SHA L. Switch scheduling and network design for real-time systems[C]//Proceedings of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium. Piscataway: IEEE Press, 2006: 289-300.
[5]	SUETHANUWONG E. Scheduling time-triggered traffic in TTEthernet systems[C]//Proceedings of the 2012 IEEE 17th Conference on Emerging Technologies & Factory Automation. Piscataway: IEEE Press, 2012: 1-4.
[6]	CRACIUNAS S S, OLIVER R S, ECKER V. Optimal static scheduling of real-time tasks on distributed time-triggered networked systems[C]//Proceedings of the 2012 IEEE 17th Conference on Emerging Technology & Factory Automation. Piscataway: IEEE Press, 2014: 1-8.
[7]	BARRETT C, TINELLI C. Satisfiability modulo theories[M]. Berlin: Springer, 2018: 305-343.
[8]	SEBASTIANI R. Lazy satisfiability modulo theories[J]. Journal on Satisfiability, Boolean Modeling and Computation, 2007, 3: 141-224. DOI:10.3233/SAT190034
[9]	CRACIUNAS S S, OLIVER R S. Combined task-and network-level scheduling for distributed time-triggered systems[J]. Real-time Systems, 2016, 52(2): 161-200. DOI:10.1007/s11241-015-9244-x
[10]	SCHOLER C, KRENZ-BAATH R, MURSHED A, et al. Computing optimal communication schedules for time-triggered networks using an SMT solver[C]//Proceedings of the IEEE International Symposium on Industrial Embedded Systems. Piscataway: IEEE Press, 2016: 1-9.
[11]	STEINER W. An evaluation of SMT-based schedule synthesis for time-triggered multi-hop networks[C]//Proceedings of the 31st IEEE Real-Time Systems Symposium. Piscataway: IEEE Press, 2010: 375-384.
[12]	POZO F, STEINER W, RODRIGUEZ-NAVAS G, et al. A decomposition approach for SMT-based schedule synthesis for time-triggered networks[C]//Proceedings of the IEEE 20th Conference on Emerging Technologies & Factory Automation. Piscataway: IEEE Press, 2015: 1-8.
[13]	TAMAS-SELICEAN D, POP P, STEINER W. Timing analysis of rate constrained traffic for the ttethernet communication protocol[C]//Proceedings of the IEEE 18th International Symposium on Real-Time Distributed Computing. Piscataway: IEEE Press, 2015: 119-126.
[14]	YAO J, XU X, LIU X. MixCPS: Mixed time/event-triggered architecture of cyber-physical systems[J]. Proceedings of the IEEE, 2016, 104(5): 923-937. DOI:10.1109/JPROC.2016.2519381
[15]	ZHAO L X, POP P, LI Q, et al. Timing analysis of rate-constrained traffic in TTEthernet using network calculus[J]. Real-time Systems, 2017, 53(2): 254-287. DOI:10.1007/s11241-016-9265-0
[16]	BOYER M, DAIGMORTE H, NAVET N, et al. Performance impact of the interactions between time-triggered and rate-constrained transmissions in TTEthernet[J]. Embedded Real time Systems, 2016, 14(2): 217-225.
[17]	STEINER W. Synthesis of static communication schedules for mixed-criticality systems[C]//IEEE International Symposium on Object/Component/Service-Oriented Real-time Distributed Computing Workshops. Piscataway: IEEE Press, 2011: 11-18.
[18]	TAMAS-SELICEAN D, POP P, STEINER W. Synthesis of communication schedules for TTEthernet-based mixed-criticality systems[C]//Proceedings of the 8th ACM International Conference on Hardware/Software Codesign & System Synthesis. New York: ACM, 2012: 473-482.
[19]	ZHANG L, GOSWAMI D, SCHNEIDER R, et al. Task-and network-level schedule co-synthesis of Ethernet-based time-triggered systems[C]//Proceedings of the 19th Asia and South Pacific Design Automation Conference (ASP-DAC). Piscataway: IEEE Press, 2014: 119-124.
[20]	FORGET J, BONIOL F, GROLLEAU E, et al. Scheduling dependent periodic tasks without synchronization mechanisms[C]//Proceedings of the 16th IEEE Real-Time and Embedded Technology and Applications Symposium. Piscataway: IEEE Press, 2010: 301-310
[21]	MCKEOWN N, ANDERSON T, BALAKRISHNAN H, et al. OpenFlow: Enabling innovation in campus networks[J]. ACM Sigcomm Computer Communication Review, 2008, 38(2): 69-74. DOI:10.1145/1355734.1355746
[22]	TIAN Z, LI S, WANG Y, et al. Priority scheduling of networked control system based on fuzzy controller with self-tuning scale factor[J]. IAENG International Journal of Computer Science, 2017, 44(3): 308-315.
[23]	SAMPIGETHAYA K. Software-defined networking in aviation: Opportunities and challenges[C]//Proceedings of the 8th Integrated Communication, Navigation, and Surveillance Conference (ICNS). Piscataway: IEEE Press, 2015: 1-21.
[24]	HEISE P, GEYER F, OBERMAISSER R. Deterministic OpenFlow: Performance evaluation of SDN hardware for avionic networks[C]//Proceedings of the 8th 11th International Conference on Network and Service Management (CNSM). Piscataway: IEEE Press, 2016: 372-377.
[25]	KUMAR R, HASAN M, PADHY S, et al. End-to-end network delay guarantees for real-time systems using SDN[C]//Proceedings of the 8th IEEE Real-Time Systems Symposium (RTSS). Piscataway: IEEE Press, 2017: 231-242.
[26]	LU J, XIONG H G, HE F, et al. Enhancing real-time and determinacy for network-level schedule in distributed mixed-critical system[J]. IEEE Access, 2020, 8: 23720-23731. DOI:10.1109/ACCESS.2020.2970266
[27]	CRACIUNAS S, OLIVER R. SMT-based task-and network-level static schedule generation for time-triggered networked systems[C]//International Conference on Real-time Networks & Systems. New York: ACM, 2014: 45-54.
[28]	何锋, 周璇, 赵长啸, 等. 航空电子系统机载网络实时性能评价技术[J]. 北京航空航天大学学报, 2020, 46(4): 651-665. HE F, ZHOU X, ZHAO C X, et al. Real-time performance evaluation technology of airborne network for avionics system[J]. Journal of Beijing University of Aeronautics and Astronautics, 2020, 46(4): 651-665. (in Chinese)
[29]	王荣巍, 何锋, 周璇, 等. 面向无人机蜂群的航电云多层任务调度模型[J]. 航空学报, 2019, 40(11): 1-12. WANG R W, HE F, ZHOU X, et al. Avionics cloud multi-layer task scheduling model for UAV swarm[J]. Acta Aeronautica et Astronautica Sinica, 2019, 40(11): 1-12. (in Chinese)
[30]	鲁俊, 何锋, 熊华钢. 航空电子云系统架构与网络[J]. 航空电子技术, 2017, 28(3): 1-9. LU J, HE F, XIONG H G. System and network architecture of avionics cloud[J]. Avionics Technology, 2017, 28(3): 1-9. (in Chinese)
[31]	TIAN Z, LI S, WANG Y, et al. Scheduling method for networked control system with resource constraints based on fuzzy feedback priority and variable sampling period[J]. Transactions of the Institute of Measurement & Control, 2018, 40(4): 1136-1149.
[32]	FRANCES F, FRABOUL C, GRIEU J. Using network calculus to optimize the AFDX network[J]. Medical Imaging IEEE Transactions on Embedded Real Time Systems, 2006, 25(10): 1319-1328.
[33]	BOYER M, MIGGE J, FUMEY M. PEGASE-A robust and efficient tool for worst-case network traversal time evaluation on AFDX[J]. Physiology and Behavior, 2011, 25(4): 589-593.
[34]	KLEIN D, JARSCHEL M. An OpenFlow extension for the OMNeT++ INET framework[C]//Proceedings of the 6th International Institute for Computer Sciences, Social-Informatics and Telecommunications (ICST) Conference on Simulation Tools and Techniques. Reston: ACM, 2013: 322-329.
[35]	SALIH M A, COSMAS J, ZHANG Y. OpenFlow 1.3 extension for OMNeT++[C]//2015 IEEE International Conference on Computer and Information Technology Ubiquitous Computing and Communications Dependable, Autonomic and Secure Computing; Pervasive Intelligence and Computing. Piscataway: IEEE Press, 2015: 1632-1637.