实时和安全关键流量使用静态路由，其传输路径在网络设计时确定。在路由规划方面已有很多研究工作。基于轨迹法的AFDX网络路由算法[5]使所有虚拟链路(VL)的最大延迟符合限制。整数线性规划(ILP)公式[6]被用于规划数千个VL的路由，以减少带宽消耗，在添加新VL或修改现有VL时具有更大的灵活性。POGA算法[7]以网络的实时传输性能为优化目标来规划网络中RC流量的路由。与传统网络不同，TTE网络具有高优先级的TT流量，网络中的路由需要同时考虑TT和RC流量。
TT帧的调度是静态合成的，可满足模理论(SMT)求解器YICES[8]，通过建立一组约束条件来合成静态TT调度表。文献[9]在TT调度表中引入了时间孔隙度的概念，TT数据帧的调度表被空白时隙分隔，RC数据帧可以在可预测的延迟和抖动下传输。文献[10-11]使用混合整数规划(MIP)和SMT求解器来求解增量调度。文献[12]提出了2种偏移形式：连续偏移形式和分布式偏移形式，TT流量的偏移量可以通过使用更新后的周期来计算获得。ILP公式也被扩展到联合路由和调度策略来计算可行的调度表[13]。文献[14]提出了一种基于强化学习的调度表生成方法，将流量调度问题转化为具有马尔可夫特性的树搜索问题。上述方法在TT流量调度表生成过程中都忽略了TT流量对RC流量的影响。文献[15]提出了一种基于禁忌搜索的启发式方法，优化TT调度表的过程中考虑了RC流量的延迟。该方法通过最短路径路由和尽快(ASAP)调度来生成启发式算法的初始解。然而初始解决方案可能会在某些链路上造成拥塞，这意味着TT和RC帧可能都不可调度。最终解与初始解的相关性较差，不适合网络的增量配置。
本文针对TTE网络，提出了一种基于贪婪随机自适应搜索算法(GRASP)的通信任务调度算法。TT流量调度表生成过程中，考虑了对RC流量的影响，有效的减少RC流量的最坏情况端到端延迟(WCD)。给定TTE网络拓扑G以及一组TT和RC流量F=FTT∪FRC，可以生成一个解决方案M，其中包括TT流量的路由集合R以及TT流量的静态时刻调度表S。在算法初始解的构造过程中采用SMT增量化调度算法，适用于网络的增量化配置以及动态的流量增删。
1 问题描述 本文处理的问题可以公式化成以下的形式：给定TTE的网络拓扑结构G，流量的集合F=FTT∪FRC，其中流量的参数包括帧长、周期或BAG、截止时间、源端系统、目的端系统。通过路径策略和调度策略，可以得到一个解决方案M，在TT流量可调度的前提下，RC流量的WCD最小。因为TT流量采用静态调度表，可以通过源端系统发送时刻偏移量以及目的端系统接收时刻偏移量来计算TT流量的延时。RC流量是事件触发模式，需要通过网络演算的方法[16-17]来计算RC流量的最坏延时。
1.1 TT流量路由 举例说明TT流量路由的重要性。考虑如图 1所示的网络拓扑结构，包含8个交换机(SW)和16个端系统(ES)。网络中有3条TT流量需要进行路由规划，其源端系统(scr)和目的端系统(dest)分别为
 |
 |
| 图 1 A380网络拓扑结构 Fig. 1 Network topology of A380 |
| 图选项 |
采用最短路径原则来规划TT流量的路由，可以直观地减少TT流量的端到端延迟，即可以获得其路由：
 |
在这种情况下，因为数据流链路[SW1, SW4]上TT流量占用时隙过多，导致没有足够的时隙用于发送RC流量，该链路上RC数据帧的延迟可能会很大。同时由于数据流链路[SW1, SW4]上TT流量过多，此链路上的TT流量可调度性变差。
在TTE网络中，节点和数据链路的负载均衡能够使得链路上保留更多的空闲时隙，因此可以显著的提高生成离线时刻调度表的可行性，使得TT流量可调度。同时更多的空闲时隙可以有效的减少该链路上RC流量的延迟。
1.2 TT流量调度 图形化展示在TT流量时刻调度表设计过程中考虑RC流量的重要性。假设采用图 2所示网络拓扑结构，包含1个交换机和3个端系统。流量配置如表 1所示，所有链路速率设置为10 Mbit/s，因此流量f1和f6在链路上的传输时间为600 μs，流量f2和f7为1 000 μs，流量f3、f4和f5为800 μs。RC流量WCD取决于其最坏情况下的延迟，RC流量可能会被高优先级的TT数据帧和比当前数据帧早到达的同优先级的RC数据帧所影响。
 |
| 图 2 TT流量路由实例 Fig. 2 TT traffic routing instance |
| 图选项 |
表 1 网络流量参数 Table 1 Network traffic parameters
| 流量编号 | 周期/ms | 帧长/bit | 路由 |
| f1∈FTT | 40 | 750 | {[ES1, SW1], [SW1, ES3]} |
| f2∈FTT | 20 | 1 250 | {[ES1, SW1], [SW1, ES3]} |
| f3∈FRC | 10 | 1 000 | {[ES1, SW1], [SW1, ES3]} |
| f4∈FRC | 20 | 1 000 | {[ES1, SW1], [SW1, ES3]} |
| f5∈FTT | 40 | 1 000 | {[ES2, SW1], [SW1, ES3]} |
| f6∈FTT | 80 | 750 | {[ES2, SW1], [SW1, ES3]} |
| f7∈FRC | 20 | 1 250 | {[ES2, SW1], [SW1, ES3]} |
表选项
图 3构造了一种RC流量最坏情况下端到端延迟可视化用例，展示TT流量调度对RC数据帧WCD的影响。图中矩形框中的数字表示数据帧的编号；蓝色矩形框表示TT帧；橙色矩形框表示RC帧；矩形框的左边缘是数据帧的发送时刻；矩形框的长度表示数据帧传输持续时间；向下黑色箭头表示RC帧的到达时刻。采用及时阻断集成模式，阴影矩形框表示及时阻断模式下预留的RC帧最大帧长。
 |
| 图 3 TT调度表对RC流量的影响可视化用例 Fig. 3 Visualized instance for effect of TT scheduling timetable on RC traffic |
| 图选项 |
图 3(a)展示了一种未考虑RC流量延迟的情况下生成的TT流量调度表。最坏情况下RC流量f4和f7的延迟为WCD(f4)=7 900 μs，WCD(f7)=6 800 μs。通过调整同一链路上TT数据帧的发送偏移量，重新调度TT流量，可以获得一个优化后的时刻调度表。图 3(b)展示了考虑RC流量延迟的优化后的时刻调度表，在没有改变TT流量端到端延迟的情况下，链路上分散的空闲时隙被整合。整合后的空闲时隙持续时间长度可以用于RC数据帧的传输，此时最坏情况下RC流量f4的延迟减少至4 700 μs，流量f7的延迟减少至6 500 μs。充分说明了TT流量调度表生成过程中考虑RC流量WCD可以有效提升网络实时性能。
2 通信任务调度算法 枚举2个节点间的每一条路径已被证实为一个NP难问题；TT流量调度问题，即流水线调度问题，也是一个NP完全问题[18]。因此第1节提出的路由和调度问题是一个NP难问题。本文提出了基于GRASP的通信任务调度算法，如算法1所示。算法的输入为拓扑结构G和流量集合F=FTT∪FRC，输出为TT流量路由集合R和离线时刻调度表S组成的解决方案M。启发式算法被广泛的应用于组合优化问题，启发式算法不能保证找到最优的解决方案，但是可以在合理的时间内为大型问题找到一个高质量的解决方案。
算法1 ??通信任务调度算法。
输入: TT流量集合FTT、拓扑结构G。
输出: 解决方案M。
1 ??M←?
2 ??repeat
3 ????R←Routing(G, FTT)
4 ????S←Scheduling(G, FTT, R)
5 ????if Obj(S′, F) < Obj(S, F)
6 ??????S←S′
7 ????end if
8 ??until terminate
9 ??return M
通信任务调度算法分为2个部分，路由规划基于K条最短路径算法(K-KSP)[19]为TT流量规划一条最小带宽利用率路径(第3行)；调度时刻表规划基于GRASP算法为TT流量生成一组时刻调度表(第4行)。当新生成的调度表S′计算的目标函数值小于当前最优值时，将调度表S′记录为最优调度表(第6行)。通过上述2个阶段，算法达到给定的时间限制或者迭代次数后终止并输出最优解决方案M，包含TT流量路由集合以及TT流量调度表。
本文考虑的是在TT流量可调度前提下，生成一组调度表使得RC流量的WCD最小，因此设定算法的目标函数Obj(S, F)：
 | (1) |
式中：δTT为一个无穷大值的权重；fi·deadline为流量fi的传输截止时间。
目标函数有2部分组成：第1项为网络中RC流量的延迟；第2项为网络中TT流量的延迟。当TT流量的延迟均小于其截止时间时，第2项的值为0，否则为无穷大。
2.1 路由规划 如1.1节所描述的，最短路径策略不会使RC流量的WCD最小，负载均衡原则可以有效的避免链路上的冲突，从而达到RC流量减少WCD的目的。因此定量分析数据帧在数据链路上的影响有助于找到一组最优的流量路由集合。式(2)表示在数据链路p上传输的所有数据帧总负载。
 | (2) |
式中：Li为流量fi的帧长；Gi为数据帧fi的周期；C为数据链路带宽。
那么定义流量fk传输路径上的最大链路利用率为
 | (3) |
式中：Rk为流量fk传输路径。
路由规划的输入为拓扑结构G和TT流量集合FTT，输出为TT流量路由集合R。
路由规划步骤如下：
步骤1 ??设定路由集合R为空，意味着网络中的流量均需要配置一条传输路径。
步骤2 ??对流量集合FTT中的所有流量进行随机排序。
步骤3 ??按照排列的顺序，依次为每条流量配置路由。采用K条最短路径算法为流量配置K条增长路径。由于枚举网络中流量fi的所有可能传输路径来寻找最优路径的工作量太庞大，且最优路径可能不是最短路径但是也不会太长，因此采用K条最短路径算法能够减少搜索空间。其中参数K的选择可以根据网络的规模进行设定[19]。
步骤4 ??从K条路径为流量fi选择一条路径，使其传输路径最大链路利用率最小。并将这条路径加入到已生成路径集合R中。
步骤5 ??完成所有流量的路由配置后，返回路径集合R。
需要说明的是，在步骤4中，如果K条路径中同时有多条备选路径的最大链路利用率最小，则从中随机选择一条路径。
在保证链路负载均衡的前提下，通过对流量进行随机排序，路由规划算法可以为后续的调度时刻表规划提供多样且质量高的路由集合。
2.2 调度时刻表规划 GRASP适合组合优化问题的求解[20]，其初始解通过贪婪随机的方式构造。GRASP的每次迭代包括2个阶段：①初始解构造阶段，构造一个初始可行解；②邻域搜索阶段，对构造的初始解进行邻域搜索获取更优的解。构造阶段提供了求解的多样性，邻域搜索则确保获得全局更优的解。
调度时刻表规划基于GRASP算法，输入为TT流量集合FTT、路由集合R、拓扑结构G、参数α和β。其中参数α用于构造阶段，参数β用于邻域搜索阶段。算法的输出为TT流量的一个可行离线时刻调度表S。
首先离线时刻调度表S设定为空，表明一组可行的调度表还未生成。每经过一次迭代，在贪婪随机构造阶段会生成一个新的TT流量调度表S′。在构造阶段的随机性确保了在迭代过程中解空间的不同部分均被搜索过。参数α用来定义随机的程度，随机性太强会大大增加搜索的空间，导致初始解的质量不高，随机性太差会影响初始解的多样性。随后对初始解S′进行邻域搜索，调整调度表中部分流量的偏移量以获得更优的调度表。参数β用来定义重新调整偏移量的TT流量条数。当新生成的调度表S′的目标函数值小于当前最优值时，将调度表S′记录为最优调度表。算法最终返回调度表S。
TT流量fi在链路p上可调度性可由ui, p描述：
 | (4) |
式中：Gi, j为流量fi和fj周期的最小公倍数。
等式(4)用于评价TT流量fi在数据链路p的可调度性。ui, p由2部分累加而成: 第1项表示流量fi在链路p上传输所需的带宽；第2项表示链路p上除流量fi以外的其余流量对流量fi的干扰时间所消耗的带宽。当ui, p数值越小时，说明流量fi在链路p上被无冲突调度的可能性越大，即可调度性越好。
因此TT流量fi的可调度性可定义为
 | (5) |
GRASP的构造阶段为后续的邻域搜索提供一个高质量且多样性的初始解，每一次迭代需生成一个不一样的可行调度表。
为获取高质量的初始解，构造阶段生成初始解的过程中需要通过评估函数来评价候选列表中的元素。通过对候选列表中的元素进行评估，可以获得一个限制候选列表(RCL)。从限制候选列表中随机选择一个元素作为S，当所有流量被调度完之后，调度表S即为一个可行初始解。
定义评价函数Z：
 | (6) |
式中：Zmin=min(Obj(S, F))为当前候选列表中各元素计算的目标函数的最小值；Zmax=max(Obj(S, F))为最大值。
候选列表元素为所有可行解，通过评价函数可以从中选择若干个高质量的可行解组成RCL。当参数α=0时，构造阶段为一个完全贪婪的搜索过程，即每次的选择为网络中目标函数值最小的元素，破坏了构造初始解的多样性。当参数α=1时，构造阶段为一个完全随机的搜索过程，即每次简单随机从候选元素中进行选择，降低了初始解的质量。本文设定α=0.6，兼顾了两者优势。
贪婪随机构造算法步骤如下：
步骤1 ??设定离线调度表S为空，意味着需要配置网络TT流量的离线时刻调度表(算法2第1行)。
步骤2 ??设定待调度的TT流量集合为Fcurr，对Fcurr中的流量进行随机排序(算法2第3行)。
步骤3 ??根据网络流量规模，设定构造步长Δ。从集合Fcurr*中依次选择Δ条TT流量并分别通过5种方式排序。5种排序方式为：随机排序、周期升序、帧长降序、负载降序、可调度性降序(算法2第4行)。
步骤4 ??分别对5种排序下的TT流量在原有调度表基础上逐条采用SMT增量调度方法生成5组新的调度表S′(算法2第6行)。
步骤5 ??将其中可行调度表加入到候选列表中(算法2第9行)。
步骤6 ??通过评价函数从候选列表中选择符合要求的元素加入到RCL中(算法2第10行)。
步骤7 ??从RCL中随机选择一个元素作为当前已完成的调度表S(算法2第12行)。
步骤8 ??将Δfi从集合Fcurr中移除(第14行)。
步骤9 ??当集合Fcurr为空时，表明网络中的TT流量均已调度。则输出当前生成的调度表S作为构造阶段的初始解(算法2第16行)。
需要说明的是，如果构造阶段无法生成一个可行的初始解，即RCL.Length=0，则此次构造阶段失败。重新开始新一次的构造。
算法2 ??贪婪随机构造算法。
输入: TT流量集合FTT、路由R、拓扑结构G、参数S。
输出: TT流量离线时刻调度表S。
1 ??S←?
2 ??repeat
3 ??Fcurr*←sortFlow(Fcurr, R)
4 ????Δfi*←sortFlow(Δfi, R)
5 ????for fi∈Δfi* do
6 ????????scheduleFlow(S, fi)
7 ????????S′←S∪{fi}
8 ????end for
9 ????RCL.addCandidate(S′)
10 ??????RCL←restrictedCandidateList(α)
11 ??????if RCL.Length>0 then
12 ????????S←RCL.RandomCandidate
13 ??????end if
14 ??remove Δfi from fcurr
15 ??until Fcurr=?
16 ??return S
GRASP的第1阶段所获得的可行解可能不是寻找的最优解，因此需要在该可行解的邻域进行局部搜索来获得邻域内的最优解。参数β用于限制邻域搜索的范围。根据网络流量规模，设定β值，即重新调整现有调度表中TT流量偏移量的条数。
由于初始解采用SMT增量式调度方法，因此调度表满足以下2个约束条件：
1) 无冲突约束，任意一条数据链路上的TT流量，其传输持续时间窗口不会与相同链路上的其他TT流量的传输时间窗口重叠：
 | (7) |
2) 端到端传输约束，任意1条TT流量的端到端延迟均小于其截止时间：
 | (8) |
式中：fip·offset为流量fi在数据链路p上的偏移量；fifirst·offset和filast·offset分别为流量fi传输路径中第1条数据链路和最后1条数据链路的偏移量。
通过初始解S的调度表，可以获取各TT流量在各链路的偏移量fip·offset，因此可以计算得到流量fi在其传输路径中前、后相邻数据帧的最小帧间间隔[17]分别定义为fifront和firear：
 | (9) |
 | (10) |
式中：fi·length表示流量fi的数据帧长。
因此流量fi偏移量的可调整范围设定为
 | (11) |
调整流量fi的初始偏移量fi·offset至fi·offset+finew，式(7)仍然成立。但是同时调整相同链路上的流量fi和fj则会破坏无冲突约束。邻域搜索不应该破坏初始解的可行性，因此本文设定邻域搜索的范围为
 | (12) |
在任意邻域搜索情况下，式(8)均成立，即TT流量可调度。因此目标函数Obj(S, F)可简化为
 | (13) |
邻域搜索采用首次适应原则，当搜索到比当前解的目标函数更优的可行解时，替换当前解，并将此可行解作为邻域搜索的新起点再次进行搜索。
算法3 ??邻域搜索算法。
输入: TT流量集合FTT、路由R、拓扑结构G、参数β。
输出: TT流量离线时刻调度表S。
1 ??Δfi←random(FTT, β)
2 ??repeat
3 ????for fi∈Δfi do
4 ??????get finew
5 ??????fi·offset←fi·offset+finew
6 ??????S′←S∪{fi}
7 ????end for
8 ????if Obj(S, F) < Obj(S′, F) then
9 ??????S←S′
10 ????end if
11 ??until terminate
12 ??return S
邻域搜索算法步骤如下：
步骤1 ??根据参数β随机选择需要调整偏移量的TT流量(算法3第1行)。
步骤2 ??对每条TT流量fi获取调整偏移量范围(算法3第4行)。
步骤3 ??调整流量fi偏移量至新值，并生成新的调度表S′(算法3第6行)。
步骤4 ??当邻域搜索新生成的调度表S′计算的目标函数值小于当前解S时，将调度表S′替换当前解(算法3第9行)。
步骤5 ??当达到迭代终止条件时，输出邻域搜索结果S(算法3第12行)。
通过上述路由规划和调度时刻表规划，经过数次迭代后，可获得一个最优的可行TT流量离线时刻调度表，其中TT流量满足可调度性，RC流量的WCD最小。
3 实验分析 本文采用一系列不同规模的用例来评估所提算法。首先是规模较小的测试用例TC1，拓扑结构如图 4所示，包含5个交换机和10个端系统。网络中包含63条TT流量和60条RC流量，流量的帧长范围为64~1 518 bit，流量周期为1~128 ms, 链路带宽配置为100 Mbit/s。
 |
| 图 4 TC1网络拓扑结构 Fig. 4 Network topology of TC1 |
| 图选项 |
将本文算法与采用负载均衡路由的SMT调度算法对比，2种方法生成的TT流量调度表下RC流量延迟如图 5所示。可以看出其中47条RC流量的WCD有不同程度的减少，13条RC流量的WCD相较于SMT调度算法有所增加。RC流量的平均延时减少了9.7%(从2 123.095 μs减少至1 919.235 μs)，单条RC流量延迟最大减少了32.8%。该方法在保证TT流量可调度的前提下，能有效减少RC流量的平均延迟，提升整网的实时性能。
 |
| 图 5 RC流量延迟对比 Fig. 5 Comparison of RC traffic delay |
| 图选项 |
除此之外，为了验证本文算法的可扩展性，通过逐次增量网络配置的方式分析算法的收益性。测试用例TC2采用基于A380的拓扑结构，如图 1所示。
基于相同的网络拓扑，通过5组增量化配置来进行实验分析。5组实验的流量配置如表 2第2列所示。100条RC流量配置不变，逐次增量TT流量条数至90~210条，对比不同流量配置下本文算法与SMT调度算法生成TT流量调度表下RC流量的平均延迟。
表 2 TC2用例实验结果对比 Table 2 Comparison of experimental results in TC2
| TC2 | TT流量/条 | RC流量平均延迟/μs | 平均延迟优化比例/% | |
| 本文算法 | SMT调度算法 | |||
| 1 | 90 | 1 811.184 | 1 939.503 | 6.62 |
| 2 | 120 | 2 120.23 | 2 302.004 | 7.9 |
| 3 | 150 | 2 343.516 | 2 582.929 | 9.27 |
| 4 | 180 | 2 520.142 | 2 875.879 | 11.82 |
| 5 | 210 | 2 690.12 | 3 140.462 | 14.34 |
表选项
从表 2中可以直观看出，随着TT流量负载的增加，本文算法对RC流量的延迟比例优化程度逐次增加，从6.62%增加至14.34%。本文算法随着实验中TT流量负载配置的增加，能够更有效的提升网络的实时性能。
如图 6所示，为TC2用例210条TT流量配置下RC流量优化前后的WCD对比。从图中可以看出，RC流量的延迟有所减少。且网络中各端口节点的平均延迟由384.67 μs减少至360.44 μs，节点端口延迟均方差由189.99 μs下降至168.1 μs，说明优化后网络中各节点端口的负载更均匀。
 |
| 图 6 210条TT流量配置下RC流量延迟对比 Fig. 6 Comparison of RC traffic delay with 210 TT flows |
| 图选项 |
用例TC2采用TT流量和RC流量及时阻断集成模式，为进一步验证算法，TC3采用与TC2相同的网络拓扑和网络流量配置，不同的是TT流量和RC流量采用洗牌集成模式。实验结果如表 3所示。从表 3可以看出，在洗牌模式下，随着TT流量负载的增加，本文算法对RC流量的延迟比例优化程度依然逐次增加，从4.84%增加至10.63%。在相同网络配置情况下，洗牌模式优化比例小于及时阻断模式。由于及时阻断模式下，TT流量的发送窗口前会预留一个及时阻断时隙窗口，相当于间接提升了TT流量的负载。因此得到的实验结果符合与TC2用例给出的结论。
表 3 TC3用例实验结果对比 Table 3 Comparison of experimental results in TC3
| TC3 | TT流量/条 | RC流量平均延迟/μs | 平均延迟优化比例/% | |
| 本文算法 | SMT调度算法 | |||
| 1 | 90 | 1 212.797 | 1 274.539 | 4.84 |
| 2 | 120 | 1 299.493 | 1 385.83 | 6.23 |
| 3 | 150 | 1 328.248 | 1 435.529 | 7.47 |
| 4 | 180 | 1 390.14 | 1 523.595 | 8.76 |
| 5 | 210 | 1 430.422 | 1 600.63 | 10.63 |
表选项
如图 7所示，为TC3用例210条TT流量配置下RC流量优化前后的WCD对比。从图中可以看出，RC流量的延迟有所减少。与图 6对比可以发现，洗牌模式下各条RC流量延迟优化比例小于及时阻断模式。
 |
| 图 7 210条TT流量配置下洗牌模式RC流量延迟对比 Fig. 7 Comparison of RC traffic delay in shuffle mode with 210 TT flows |
| 图选项 |
4 结论 为了优化TTE网络实时性能，本文提出了一种基于贪婪随机自适应搜索法的TTE通信任务调度优化算法。通过输入网络的拓扑结构和流量集合，可生成TT流量的路由集合及TT流量的离线时刻调度表。该算法在保证TT流量满足可调度性的前提下，降低了RC流量的最坏端到端延迟。经过多组合成用例验证了本文算法的有效性和可扩展性：
1) 本文算法通过路由规划和调度时刻表规划，在小型网络配置中，RC流量的平均延时减少了9.7%，有效提高了网络的实时性能。
2) 通过增量化实验可发现，本文算法适用于网络负载更大的配置，且随着网络中流量负载的增加，本文算法优化程度随之增加，由6.62%提高至14.34%。
3) 相同配置下，及时阻断集成模式下RC流量平均延迟优化比例大于洗牌模式。
由于经典网络演算对RC流量的延迟分析存在悲观性，后续工作将进一步提升RC流量延迟分析的精确性，为TTE网络调度算法提供更准确的理论依据。
参考文献
| [1] | Aerospace. SAE AS6802: Time-Triggered Ethernet[S]. [S. l. ]: SAE International, 2011: 8-21. |
| [2] | ARINC. Aircraft data network, Part 7, Avionics full-duplex switched ethernet network: ARINC 664P7[S]. [S. l. ]: Aeronautical Radio INC, 2009: 9-18. |
| [3] | KOPETZ H. Real-time systems: Design principles for distributed embedded applications[M]. Berlin: Springer Science and Business Media, 2011: 79-109. |
| [4] | KOPETZ H, ADEMAJ A, GRILLINGER P, et al. The time-triggered ethernet (TTE) design[C]//Eighth IEEE International Symposium on Object-Oriented Real-Time Distributed Computing (ISORC'05). Piscataway: IEEE Press, 2005: 22-33. |
| [5] | 刘成, 李航, 何锋, 等. 基于轨迹方法的AFDX网络路由配置算法[J]. 北京航空航天大学学报, 2012, 38(12): 1587-1590. LIU C, LI H, HE F, et al. Routing algorithm of AFDX network based on trajectory approach[J]. Journal of Beijing University of Aeronautics and Astronautics, 2012, 38(12): 1587-1590. (in Chinese) |
| [6] | Al S A, BRUN O, CHERAMY M, et al. Optimal design of virtual links in AFDX networks[J]. Real-Time Systems, 2013, 49(3): 308-336. DOI:10.1007/s11241-012-9171-z |
| [7] | 代真, 何锋, 张宇静, 等. AFDX虚拟链路路径实时寻优算法[J]. 航空学报, 2015, 36(6): 1924-1932. DAI Z, HE F, ZHANG Y J, et al. Real-time path optimization algorithm of AFDX virtual link[J]. Acta Aeronautica et Astronautica Sinica, 2015, 36(6): 1924-1932. (in Chinese) |
| [8] | STEINER W. An evaluation of SMT-based schedule synthesis for time-triggered multi-hop networks[C]//201031st IEEE Real-Time Systems Symposium. Piscataway: IEEE Press, 2010: 375-384. |
| [9] | STEINER W. Synthesis of static communication schedules for mixed-criticality systems[C]//201114th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing Workshops. Piscataway: IEEE Press, 2011: 11-18. |
| [10] | 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 |
| [11] | 宋梓旭, 李峭, 汪晶晶, 等. 基于可调度性排序的时间触发调度表生成方法[J]. 北京航空航天大学学报, 2018, 44(11): 145-152. SONG Z X, LI Q, WANG J J, et al. Time-triggered scheduling table generation method based on schedulability ranking[J]. Journal of Beijing University of Aeronautics and Astronautics, 2018, 44(11): 145-152. (in Chinese) |
| [12] | SUETHANUWONG E. Scheduling time-triggered traffic in TTEthernet systems[C]//Proceedings of 2012 IEEE 17th International Conference on Emerging Technologies and Factory Automation (ETFA 2012). Piscataway: IEEE Press, 2012: 1-4. |
| [13] | SCHWEISSGUTH E, DANIELIS P, TIMMERMANN D, et al. ILP-based joint routing and scheduling for time-triggered networks[C]//Proceedings of the 25th International Conference on Real-Time Networks and Systems. New York: ACM, 2017: 8-17. |
| [14] | 李浩若, 何锋, 郑重, 等. 基于强化学习的时间触发通信调度方法[J]. 北京航空航天大学学报, 2019, 45(9): 1894-1901. LI H R, HE F, ZHENG Z, et al. Time-triggered communication scheduling method based on reinforcement learning[J]. Journal of Beijing University of Aeronautics and Astronautics, 2019, 45(9): 1894-1901. (in Chinese) |
| [15] | T?MA?-SELICEAN D, POP P, STEINER W. Design optimization of TTE thernet-based distributed real-time systems[J]. Real-Time Systems, 2015, 51(1): 1-35. DOI:10.1007/s11241-014-9214-8 |
| [16] | ZHAO L, XIONG H, ZHENG Z, et al. Improving worst-case latency analysis for rate-constrained traffic in the time-triggered ethernet network[J]. IEEE Communications Letters, 2014, 18(11): 1927-1930. DOI:10.1109/LCOMM.2014.2358233 |
| [17] | ZHAO L, 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 |
| [18] | GAREY M R, JOHNSON D S, SETHI R, et al. The complexity of flowshop and jobshop scheduling[J]. Mathematics of Operations Research, 1976, 1(2): 117-129. DOI:10.1287/moor.1.2.117 |
| [19] | YEN J Y. Finding the k shortest loopless paths in a network[J]. Management Science, 1971, 17(11): 712-716. DOI:10.1287/mnsc.17.11.712 |
| [20] | RESENDE M G C, RIBEIRO C C. GRASP: Greedy randomized adaptive search procedures[M]//BURKE E K, KENDALL G. Search methodologies. Berlin: Springer, 2014: 287-312. |
