时间触发以太网的任务调度算法研究

◆刘国辉 祁志民

时间触发以太网的任务调度算法研究

◆刘国辉 祁志民

（北方自动控制技术研究所 山西 030006）

在基于时间触发以太网（time-triggered Ethernet，TTE）的系统中，为了能够根据通信的任务需求优化组织TTE网络的任务调度，本文给出了适用于TTE交换网络的任务分配方法，并使之与互联构型的设计和规划相结合，得到相应的TTE网络任务调度模型。

TTE；任务分配；任务调度

1 引言

时间触发以太网（Time-Triggered Ethernet，TTE）传递时间触发（Time-Triggered，TT）流量的同时，还可兼容两种事件触发的流量——速率约束（Rate Constrant，RC）流量和“尽力传”（Best Effort，BE）流量[1]。基于调度时刻表（scheduling time-table）的TT流量时分多路访问（Time Division Multiplexing Access，TDMA）通信机制，保证了严格时间确定性和高完整性的网络流量传输，即：合理设计的调度时刻表不仅使TT消息经过交换机时不发生碰撞，还可以避免TT流量过分地阻塞RC流量[2]。为了能够根据通信的任务需求优化组织TTE网络的TDMA，提出了适用于TTE交换网络的任务分配方法，并使之与互联构型的设计和规划相结合。

2 网络与任务模型

2.1 网络的物理拓扑结构

在标准以太网中，端系统（End System，ES）与交换机以及交换机之间均通过双向通信链路连接，交换机作为转发结构实现端系统通信。任意两台交换机之间的链路称为多跳链路，图1给出一种多跳拓扑的例子。

在静态路由条件下，对于给定的端到端通信任务，存在一条从源ES经过交换机到目的ES的固定通信路径。如果从源ES到目的ES有多条通道，则意味着端到端路径的选择不是唯一的，则有可能根据路径规划方法为每条独立的虚拟链路（Virtual Link，VL）各自指定不同的物理路径；如果存在多播，则从源ES到多个目的ES形成一个有向的树状路径[4]。

2.2 TTE网络拓扑的定义

用赋权连通有向图G=（V，E）表示网络拓扑，如图2所示[5]，其中V为所有TTE网络节点集合，即TTE网络中处理器和交换机的集合，V=（v1，v2，…，vN），N为节点数量。E为所有连接节点的有向链路的集合，节点vi到节点vj（vi∈V，vj∈V）的有向链路e（e∈E），可以表示为e=vivj=eij；TTE网络中采用全双工链路，若有eij∈E，则eji∈E。

这里定义：邻接矩阵A=（aij）N×N，aij为：

其中，aij=1表示节点vi、vj（vi∈V，vj∈V）为直接相连节点，aij=0表示以上两节点无直接相连关系。

2.3 处理任务与通信任务参数表示

目前，采取了将通信任务参数转化为处理任务附带的代价，运用将多变量优化问题转换为单目标优化问题的方法解决此问题。运用合理简化假设法，不计任务分解后可能带来的额外开销，此外，不同任务之间存在部分的相关性，将这些具有相关关系的部分转化为统一量化量，从而实现多目标到单目标优化的转变。

通信任务是指两个处理任务对应的应用层“端到端”的有向流量。可将通信任务用一个集合T来表示[6]，对于任意tϵT，可以用含三参量（sk，qk，wk）表示，sk指通信任务的发出任务，qk表示通信任务的接收任务，wk表示通信任务的流量。

通过以上通信关系矩阵，可将相应通信任务参数转换成处理任务附带的代价，从而能够将通信任务与处理任务统一分配，达到变量数量简化的目的。

3 任务分配方法

3.1 任务分配遵循原则

在对TTE网络进行任务调度的时候，应该考虑到以下几点准则：

（1）负载均衡原则

在分配通信任务的时候，应该尽量将任务均匀的分配在各条链路上，以次避免路由中某些链路过于繁忙，造成通信堵塞。

（2）路由“跳数”较少原则。

任务在路由中的转跳数，影响链路资源的利用率，合适的转“跳数”同时还可以避免链路的局部堵塞。

3.2 TTE网络的任务调度算法

由于TTE网络中需要考虑的参数较多，因而需要使用迭代算法来简化整个调度过程，其总体流程如下。

首先，对于分解、映射和调度中的评价指标进行归纳，形成一致的评价体系，基于生成的各种“子任务”间的依赖关系和约束关系，确定初步的约束条件（包括硬约束和软约束）和目标函数，并运用现代启发式方法对整个TTE网络的进行计算，寻找到在当前条件下的最优（次优）解，生成任务与资源分布式综合的映射。

3.3 目标函数的确定

由于TTE网络中TT通信本身所具有的时间确定性，在遵循两个任务分配原则情况下，可以通过定义以下指标进行任务流量的分配：

其中：

这里目标函数的表达采用了概率学中方差的概念，以TTE网络中节点和链路上分配的任务的方差与路由转“跳数方差”之和为目标函数，其值越小，则说明其分配效果越好。

3.4 通信任务路径选择

对通信任务进行配置时，需要考虑任务路径的相关性，在TTE网络中，任务路径配置的次序与计算的影响因子相关，即先配置的任务路径不考虑后配置任务路径对它的影响，而后配置的计算所有先配置的影响。因此，在任务路径配置的过程中，尽可能按照对网络影响程度的大小，配置相应的任务路径的次序[7]。

配置任务路径时，需要考虑节点间通信的自由度，两个具备通信关系的节点间可供选择的路径可能有多条。这里采用两个参量限制通信的自由度，即负载均衡度和路由转跳次数，综合考量这两个因素的相互约束，以期路径较好的匹配。由于，每次路径更新都得在目标函数中重新计算一次，为了更高效进行整网的通信路径匹配，提出了以下路径配置的方法和步骤[8]：

步骤1：确定链路通路，即两节点间直接相连的链路为一条链路通路，构建任务路径数组；

步骤2：将任务路径中的元素按照对这个网络的影响从大到小排序；

步骤3：依据步骤2中的排序，首先确定起始节点，结合目的节点在步骤1数组中的顺序逐步生成次优最小代价树，作为配置的任务路径；

这种生成通信路径的方法，较好地实现了链路负载均衡度与路由转跳次数对配置结果平衡影响的目的，其次，采用的算法复杂度较低，能够快速完成通信路径的匹配。

3.5 优化问题求解

在TTE网络拓扑结构中，需要解决任务与资源映射的组合优化问题，根据求解的效率，这里选用模拟退火算法，依靠其较强的局部搜索能力求解任务分配优化问题，具体步骤如图2。

步骤1：构建TTE网络的相关信息。即其拓扑结构、各个任务的相关参数、各网络节点以及链路之间的约束条件；

步骤2：数学模型中关键变量转化，鉴于TTE网络中TT通信的时间确定性，将约束参量进行统一量化，将通信任务转化为处理任务的相关量，实现统一分配；

图3 模拟退火算法流程

步骤3：相关参数设定，即设计合适的冷却进度表。主要有控制参数Temperature的初值T0、控制参数Temperature的衰减函数及markovLength；

步骤4：产生一个初始解X（0）；

步骤5：从X的邻域中随机选取一个新解X（b），比较X（b）与当前解X的函数值G（X），并计算∆G（X）=G（X（b））-G（X），若∆G（X）<0，则接受新解X←X（b）；若∆G（X）≥0，则以概率exp（-∆G（X）/T）接受新解X←X（b）。然后判断是否达到内循环终止条件（p=MarkovLength+1），若在该温度达到内循环终止条件，则执行下一步，否则重复执行步骤5；

步骤7：输出当前解X。

在上述的过程中，初始解的状态X（0）是随机产生的，G（X）为评价函数，终止条件为连续若干个新解都没有被接受或者增量都非常小时，或迭代次数K大于总迭代次数T时，则终止算法。

4 结论

从TTE网络的任务分配入手，随后考虑互连构型对TT消息路径选择的影响，在任务分配、路径规划的过程中，分阶段地使用了以启发式算法为主的组合优化算法，使得TTE交换网络的TT通信任务的全面综合化设计可以取得近似最优的结果。

[1]王家兴.时间触发以太网关键技术研究与设计[D].浙江大学，2019.

[2]冯健清. 时间触发以太网的节点设备软件设计[D].电子科技大学，2017.

[3]Time-triggered ethernet：SAE AS6802[S].SAE AerospaceStandard，2011-11.

[4]Y Zhang，F. He，G. Lu and H. Xiong. Clock synchronization compensation of Time-Triggered Ethernet based on least squares algorithm[C].2016 IEEE/CIC International Conference on Communications in China（ICCC Workshops）， Chengdu，2016：1-5.

[5]Z. Zheng，F. He and Y Xiong. The research of scheduling algorithm for time-triggered ethernet based on path-hop[C]. 2016 IEEE/AIAA 35th Digital Avionics Systems Conference（DASC），Sacramento，CA，2016：1-6.

[6]汤宇，李峭，贾琪明. 时间触发以太网的分布式任务负载均衡分配方法[J]. 计算机工程与设计，2014，35（05）：1501-1505.

[7]栾不群.时间触发以太网中时间触发业务调度算法的研究[D].西安电子科技大学，2019.

[8]刘美辰. 多跳时间触发以太网调度优化机制与算法的研究[D].大连理工大学，2019.