刘国辉，祁志民

(北方自动控制技术研究所， 太原 030006)

基于调度时刻表(scheduling time-table)的通信调度是时间触发以太网严格时间确定性和高完整性保障机制的关键。近年来，对TTE网络的研究主要集中在TT调度表的离线设计。文献[1-2]研究了RC流量对TT流量调度的影响，忽略了TT流量间的依赖性；文献[3]通过改变TT消息在源端的触发时间及中间传输的路径，研究了TT消息调度的时延变化，缺少了TT流量总体时间占比对结果影响的分析；文献[4]设计了一种冗余至节点的双以太网结构，对于不同优先级的消息采用不同的传输通道，研究了此状态下TT流量调度的时延问题，缺乏对同一通道上不同消息影响机制的分析；文献[5]在不限制TT消息的周期属性的基础上，对不同长度的TT消息匹配相应的时间槽，研究了TT流量的调度问题，缺少对TT流量在已知端到端间不同路径传输对TT流量调度影响的分析；文献[6]在TTE的基础上增加了流量隔离功能，研究了大规模实时任务下调度表的生成问题，但增加的通信规则使得TT流量分布趋于固定；文献[7-8]提出将TT消息间的依赖度转化为矩阵表示，研究实时任务的可调度性，但未考虑TT流量在整网分布的均匀度对TT流量调度的影响。上述研究都未综合考虑TT流量时间占比及TT流量在端到端间不同路由的传输，对TT流量调度时延的影响。本文在已有研究的基础上，提出了时间触发以太网中实时任务调度算法，研究实时任务的时间占比及任务分配均衡度对整网延时的影响。

1 时间触发以太网建模

TTE网络拓扑定义[9-10]为赋权连通有向图G=(V，E)，如图1所示，其中V为网络节点集合，在TTE网络中为处理器和交换机的集合，V=(v1，v2，…，vN)，N为节点数量。E为连接节点的有向链路的集合，节点vi到节点vj(vi∈V，vj∈V)的有向链路l(l∈E)可以表示为l=vivj=lij；TTE网络中采用全双工链路，若有lij∈E，则lji∈E。

图1 网络拓扑的定义示意图

定义：邻接矩阵A=(aij)N×N，aij为

定义：两确定节点vi，vj间任一路由g对应的路由路径(Pathij)g=〈lip，…，lpk，lkj〉；路径矩阵R=(uij)N×N，uij取值0或1，代表节点vi与节点vj之间是否存在相邻连接关系；链路带宽矩阵C=(cij)N×N，cij是有向链路lij的带宽；链路利用率矩阵H=(hij)N×N，是对应于矩阵R中所有相连链路lij的链路利用率；路径代价矩阵W=(wij)N×N，wij是节点vi有到节点vj的路径的代价值。

定义：两确定节点vi，vj间任一路由g所经过链路的最大链路利用率为：

max(hPathijg)=max(hip,…,hpk,hkj)

定义：pathNum为路由数目，以max(h(Pathij)g)=max(h(Pathij)1，h(Pathij)2，…，h(Pathij)g)，表示节点vi到节点vj所选路由的链路利用率的最大值。

定义：任一路由的跳数为

定义：S=(sij)N×N，sij=hop(P)，表示节点vi到节点vj所选路由的跳数。

2 调度表结构

TTE时刻表调度适用于具有多个空分网段的交换式网络，每个进行TT通信的发送端，都存放有一个对应的TT帧调度时刻表。

对于周期性TT通信任务，调度表整体定义为一个矩阵周期(Matrix Cycle，MC)，它由若干个基本周期(Basic Cycle，BC)组成[11]。

其中BC的值为所有TT消息传输周期的最大公约数，MC的值为所有TT消息传输周期的最小公倍数，矩阵周期表的行数为r=MC/BC。

如图2所示，将每个基本周期人为划分成两段，即TT帧段、ET帧段。其中为实现TT消息的紧凑传输，定义时间窗Q，默认TT消息只在这个范围调度。

图2 周期结构框图

3 调度表生成

根据调度表整体定义，需要构造一个矩阵周期表M=(mij)r×n，n为所有TT通信消息个数，又

其次，对于第i基本周期，即矩阵周期表第i行，需要构造一个对应的“通信任务—通信路由链路”通信状态表TB=(ωuv)n×k，其中k为整网通信链路的个数，其中：

3.1 TT流量路由规划

端到端路由的确定，需要考虑节点间通信的自由度，两个具备通信关系的节点间可供选择的路径可能有多条。这里采用两个参量限制通信的自由度，即负载均衡度和路由转跳次数，综合考量这两个因素的相互约束，以期路径较好的匹配。

3.1.1 路由评价函数

以Cost(P)=min(Max(hP))表示路由负载代价函数，Max(hP)是指所经过链路的链路利用率的最大值，以此为指标寻找目的路由，可绕开负载较大的链路，避免局部堵塞。Cost(P)=min(hop(P))为路由跳数代价函数，hop(P)是路由的跳数，以此为指标寻找目的路由，可找到最小跳数的路由。

(1)

(2)

(3)

(4)

结合公式推导进行分析，两种路由配置策略的根本区别在于通信任务流量的散布方式。综合考虑两个路由配置策略，提出两者的加权代价函数——路径代价函数，加权值为α和(1-α)，0≤α≤1，定义加权后的代价：

其中为了保证量级数的一致，采用标准差。

3.1.2 加权值α的预选取

加权值α体现了整网的TT流量的负载均衡程度，与网络的拓扑结构、链路带宽及消息经过的路由等参数密切相关。

假设链路i的链路利用率为hi(0≤hi≤1)，对于整网的n条链路，其链路利用率分别为h1，h2，…，hi，hi+1，…，hn，并且h1+h2+…+hi+hi+1+…+hn=C(0≤C)。整网链路的负载均衡可以表述为h1，h2，…，hi，hi+1，…，hn之间的差值和最小化问题。根据切比学夫不等式取a∈CN，b∈CN，a={a1，a2，…，an}，b={b1，b2，…，bn}，且a1≥a2≥…≥an，b1≥b2…≥bn，得到：

令aj=bj=hi，可得加权值α，其计算公式如式(5)：

(5)

当α=0时，min(Cost(P))相当于最小跳路由代价函数；α=1时，min(Cost(P))相当于负载均衡代价函数。

3.1.3 路径规划

步骤1：获取TTE网络参数，即建立A=(aij)N×N，C=(cij)N×N，S=(sij)N×N，初始化B=(bij)N×N，bij=0，H=(hij)N×N，hij=0，W=(wij)N×N，wij=0；

步骤2：预设的值，选择对应的路径代价函数，将其嵌入到DFS路径搜索算法中；

步骤3：设计寻找最小代价算法，流程如图3所示，获取两确定节点间任务、路由匹配信息。

图3 最小代价算法流程框图

3.2 任务时间分配

3.2.1 TT消息影响系数

由于每条TT消息的发送、转发和到达时间的确定都会对其余的TT消息的时间的确定造成影响，就需要确定那条TT消息对整个TTE网络的影响最大，从而通过从影响最大的任务开始分配的方式，最大程度地减小TT消息间相互的影响。

在确定TT消息对整个TTE网络的影响程度的过程中，主要依据以下四条原则[11]： TT消息的长度L越大，对TTE网络的影响程度越大； TT消息的周期T越小，对TTE网络的影响程度越大； TT消息的转跳数N越大，对TTE网络的影响程度越大； TT消息的所经过的链路的负载越大，对TTE网络的影响程度越大。

根据上述原则，定义了TT消息的影响系数U：

其中，dk为TT消息所经过的链路lk的负载，即TT消息的影响系数U与TT消息所经过的所有链路的负载之和成正比。

3.2.2 调度时刻表生成

图4展示了调度时刻表的生成算法。结合该流程图，可见具体的处理步骤如下：

步骤1：输入TTE网络的相关参数。包括邻接矩阵、TT消息的长度、周期及消息路由路径矩阵等；

步骤2：依据TT消息的长度、周期、传输路径以及TTE网络中各链路的负载，计算出TT消息的影响系数U；

步骤3：按照影响系数U的大小进行排序，决定TT消息的分配顺序；

步骤4：根据TT消息的传输路径生成“虚拟链路”，这里的“虚拟链路”与TTE网络实时通信VL的概念完全相同。对应矩阵周期表每一行，建立相应的“通信任务—通信路由链路”通信状态表TB，然后依据通信链路相关约束及TT消息时间窗Q的大小，建立整网链路通信时刻约束矩阵，运用MATLAB求解；

步骤5：若有可行解，则输出时间表，结束算法；若没有可行解，有两种解决方法：一是直接结束算法；二是需要修改链路带宽或个别消息特征值以达到可解目的。

图4 调度时刻生成算法框图

4 实例分析

TTE网络包含4个终端节点，4个交换机，其网络拓扑如图5所示。

图5 实例拓扑示意图

网络带宽为1 000 Mbit/s，TT通信任务30个，得到一个矩阵周期内特定时间段的调度时刻分布如图6所示，在调度表可解的情况下，根据得到的调度时刻表，得出在一个矩阵周期中整网的链路利用率均值、链路利用率方差及整网通信最小时延与路径代价函数中加权因子的关系图如图7～图9所示。

图6 调度时刻分布图

图7 链路利用率方差随加权因子α的变化曲线

由图7，图8可知当α=0时，即选择最小跳数路由配置策略得到的链路利用率均值和方差最小，分别为0.218 7%，0.038；当α=1时，即选择负载均衡路由配置策略得到的链路利用率均值和方差最大，分别为1.538%，1.528。特别的，当0.12≤α≤0.36时，链路利用率均值较大，而其方差较小，此时整网链路负载分配最佳。由图9可知，整网最小时延在整体趋势上随α的阶段增大而增加。由图10可知，当TT任务时间占比小于10%时，整网最小延时随着占比增大呈线性增大。

图8 链路利用率均值随加权因子α的变化曲线

图9 最小延时随加权因子α的变化曲线

图10 最小延时随时间占比Q的变化曲线

5 结论

本文通过分析TT消息的调度特性，在路由分配过程中建立了评价函数，综合权衡了负载均衡和路由跳数对调度表生成的影响。通过实际的案例仿真分析，得到了有效的TT消息静态调度表，同时通过对比分析加权因子、TT消息时间占比与网络最小延时的关系，为获得最小延时的基础上选取TT任务时间占比及任务在整网分布均匀度提供了一定的参考依据。