CN102255803A - 一种适用于时间触发交换式网络的周期调度时刻表构建方法 - Google Patents

Abstract

本发明公开了一种适用于时间触发交换式网络的周期调度时刻表构建方法，该周期调度时刻表构建方法是基于时间触发交换式网络的，在提出周期调度时刻表概念的基础上，设计了TT任务建立和删除的流程，实现了TT任务的有效实时传输；通过提出离线任务建立法和动态任务建立法，实现了系统内各个节点中的周期调度时刻表的建立；通过提出左端压缩原则，实现了动态任务建立法的优化；通过提出公共空闲区间法，实现了离线任务建立法的表格评估方法及优化。

Description

一种适用于时间触发交换式网络的周期调度时刻表构建方法

技术领域

本发明涉及一种应用于时间触发交换式网络的调度方法，更特别地说，是指一种适用于时间触发交换式网络的周期调度时刻表构建方法。本发明是基于时间同步和时间触发机制，为周期性通信任务在源节点、目的节点和交换节点上建立周期调度时刻表，并依据周期调度时刻表对数据帧传输进行调度。

背景技术

在时间触发网络中，即以时间触发代替事件触发，如果定时发送和转发的触发的调度合理，即可以避免数据帧争用物理链路，保证传输的时间确定性。在数据通信的过程中，网络中各端系统按照各自的时刻调度表进行数据的发送，即调度时刻表中分配给某个任务的时间区间(time slot)的起始时刻点触发该任务的发送。网络中各个发送任务按照调度表有序的进行，即为时间触发网络。

在时间触发机制下，有共享介质网络(如：TTCAN)和交换式网络。对于共享介质网络，因为只共享一个公共的信道，各个节点的调度表是完全相同的；而对于交换式网络，由于包含多个空间分割的物理网段，所以各个交换节点上的时刻调度表既是不同的，又是根据转发路径的情况在时间上相互关联的。因此，生成交换式网络的调度时刻表并进行维护是较为困难的。

对于带有全局时钟同步机制的时间触发交换式网络，这样的时钟同步可以由额外的物理连线或无线电信号(如：GPS信号)建立并保持，也可以在本网络中利用IEEE1588V2中的P2P透明时钟、时间同步控制帧(PCF，Protocol Control Frame)机制通过固化和压缩功能建立并保持。但无论以何种方法，要求：时钟同步过程是在系统的开始运行时进行并建立同步的，并在系统的运行过程中进行必要的同步，以克服各个本地时钟晶振的漂移；网络中各个分布式节点上时钟的同步精度应该保证其误差不对延迟时间、时延抖动等时间参数的计算和测量数值的有效数字产生影响；如果采用本网络中的同步机制，则该机制应该是“透明”的，即用于时间同步的通信开销不应对时间同步精度造成影响，也不应对时间触发和通信任务的传输造成可以观测到的或精度范围以内的干扰。

将交换式网络中的主机称为“端系统”，端系统以全双工方式接入交换机，根据通信任务“端到端”(end-to-end)的角色充当源端系统和目的端系统；交换式网络中的交换设备中含有转发和多路复用功能的模块被称为“交换节点”。将端系统和交换节点统称为“节点”。各个节点时钟的完全同步为建立按照时刻表发送周期性调度提供了必备条件。

在AFDX(Avionics Full Duplex Switched Ethernet，航空电子全双工以太网)网络中事件触发的速率约束流量，记为RC流量，所述RC流量中传输的数据帧为RC帧，RC流量对应的网络通信任务称为RC任务；标准以太网的“尽力传”流量，记为BE流量，所述BE流量中传输的数据帧为BE帧，RC流量对应的网络通信任务称为RC任务。

发明内容

本发明的目的是提供一种针对时间触发交换式网络的周期性任务的调度方法，即交换式网络周期调度时刻表法。交换式网络周期调度时刻表法在源、目的和交换节点上建立周期调度时刻表，可以保证依据所建立的时刻调度表对周期性通信任务进行调度的时候，数据帧之间不会发生争用物理链路的情况，进而保证了端到端通信的时间确定性，实现了时间触发交换式网络的实时通信。

本发明的一种适用于时间触发交换式网络的周期调度时刻表构建方法，其时间触发交换式网络的路由为静态路由且无环，或为动态路由且无环但在该动态任务运行的过程中路由是固定的；网络中所有交换机均应增加具有建立、更新和维护周期调度时刻表的功能并且具有按照周期调度时刻表时间触发机制完成发送任务功能的模块；动态任务所经过的所有转发交换机上存有放置此动态任务的周期调度时刻表；

对于时间触发交换式网络，周期调度时刻表中的动态任务采用动态任务建立法建立，离线任务采用离线任务建立法建立；

任意交换机SW_c与端系统ES_b直接相连端口对应的转-ES_b-周期调度时刻表Tab_{c-b端系统-route}和端系统ES_b的收-周期调度时刻表Tab_b-receive有Tab_c-b-route＝Tab_b-receive；

动态任务的建立是一个端系统向另一个端系统建立发送TT任务，动态任务的建立过程是由该TT任务的发送端发起的，依据动态任务建立法完成；

动态任务的删除是一个端系统向另一个端系统停止已经建立的TT任务并清除所有节点中该任务对相关TT任务周期调度时刻表时间区间的占用；动态任务的删除过程是由该TT任务的发送端发起的，依据动态任务建立法完成。

本发明适用于时间触发交换式网络的周期调度时刻表构建方法的优点在于：

①本发明方法充分考虑到交换式网络包含多个空间分割的物理网段，与共享介质网络大有不同，所以设计的各个交换节点上的调度时刻表既是不同的，又是根据转发路径的情况在时间上相互关联的。

②本发明方法考虑到实时性要求高的周期性任务的特殊性，保证了实时性，提出了合理的时间触发周期性通信任务建立流程，并能够方便地增加和删除时间触发周期性任务。

③本发明方法考虑到在实际应用中有系统启动就运行的时间触发周期性任务以及在系统运行过程中不定期需要启动的时间触发周期性任务，将周期调度时刻表的生成方法分为离线任务建立法和动态任务建立法。

④本发明方法提出了对于周期调度时刻表离线任务建立法的合理评价方法——公共空闲区间法，为离线生成周期调度时刻表的优化提供了依据。

⑤本发明方法提出了对于周期调度时刻表动态任务建立法的左端压缩原则，用来优化动态生成方法。

附图说明

图1为多个端系统与两个交换机形成的时间触发交换式网络示意图。

具体实施方式

下面将结合附图对本发明做进一步的详细说明。

本发明中，将时间触发机制周期性传输的数据帧流量称为时间触发流量(记为TT流量)，TT流量中传输的数据帧称为TT帧，TT流量对应的网络通信任务称为TT任务，即时间触发周期性任务。TT任务的周期称为TT任务周期。本发明还允许在时间段预留和优先级限制的前提条件下，在同一个网络中兼容与TT流量分时享用物理链路的RC流量和具有低优先级的BE流量。

本发明的应用环境为具有时间同步机制的时间触发交换式网络，特别包括TTTech公司TTE(Time-Triggered Ethernet，时间触发以太网)网络，该种网络以相应的技术规范定义。AFDX网络如果加入时钟同步机制，也可以充当TTE网络。

本发明基于时间触发交换式网络，在提出周期调度时刻表概念的基础上，设计了TT任务(时间触发周期性任务)建立和删除的流程，实现了TT任务的有效实时传输；通过提出离线任务建立法和动态任务建立法，实现了系统内各个节点中的周期调度时刻表的建立；通过提出左端压缩原则，实现了动态任务建立法的优化；通过提出公共空闲区间法，实现了离线任务建立法的表格评估方法及优化。

在本发明中，广义周期调度时刻表是一个用矩阵周期MC(Matrix Cycle)表示的表单，广义周期调度时刻表如表1所示。矩阵周期时间长度是广义周期时刻调度表中所有TT任务的最大周期记为TMC。一个矩阵周期的每一行是一个基本周期BC(Basic Cycle)，基本周期的时间长度记为TBC，TBC可以看作所有TT任务中的最小周期，典型值为1ms。BC在MC的数目即为广义周期调度时刻表的总行数k，k＝TMC/TBC，TMC为TBC的2的幂次倍，即k＝2^q，q＝1，2，3，…正整数。每个基本周期又分为两段，前一段为TT段，主要发送TT数据帧；后一段为RC+BE段，专门发送RC帧和BE帧，为了不对下一个基本周期的TT帧发送造成延迟，RC+BE段的最后需要留出一个当前所有RC任务和BE任务中最大帧长的时间作为保护间隔。每个基本周期的TT段的时间长度相等，每个基本周期的RC+BE段的时间长度相等。在TT段中，时间资源又被分为多个时间区间。时间触发交换式网络中的帧的长度并不固定，但为了易于组合优化时刻调度表，可以令时间区间是定长的。不同长度的帧可以占据一个或多个时间区间。TT段主要用于发送TT任务，除TT任务占用的时间区间，其他时间区间可以用来发送BE任务。在RC+BE段中，时间资源为一个完整的时间段，在该段中只发送RC任务和BE任务。RC任务按照AFDX网络的发送机制进行发送，BE任务按照标准以太网的发送机制进行发送。

表1广义周期调度时刻表

注：◆表示广义周期调度时刻表中每个基本周期中的TT段；

◇表示广义周期调度时刻表中每个基本周期中的RC+BE段。

本发明主要针对广义周期调度时刻表的TT部分，并称之为周期调度时刻表。所谓TT部分是指广义周期调度时刻表中去除所有的RC+BE段后形成的表单。

为了使各个节点保证时间确定性、无冲突地有序的完成TT任务，本发明在各个节点上建立了周期调度时刻表，初始的周期调度时刻表称为空白周期调度时刻表tab_in。所述空白周期调度时刻表Tab_in是一个以矩阵 $\mathrm{TTMC}=\left(\begin{array}{ccccc}{t}_{11}& t_{12}& t_{13}& ...& t_{1n}\\ t_{21}& t_{22}& t_{23}& ...& t_{2n}\\ t_{31}& t_{32}& t_{33}& ...& t_{3n}\\ .& .& .& .& .\\ .& .& .& .& .\\ .& .& .& .& .\\ t_{k1}& t_{k2}& t_{k3}& ...& t_{\mathrm{kn}}\end{array}\right)$ 表示的表格，空白周期调度时刻表Tab_in的表格形式如表2所示。

矩阵周期TTMC中n表示列数，n＝1，2，3，…正整数，n最大为16(n≤16)；k表示行数，与广义周期调度时刻表中的表示一致；t₁₁表示第1行第1列的时间区间；t_1n表示第1行第n列的时间区间；t_k1表示第k行第1列的时间区间；t_kn表示第k行第n列的时间区间。每个时间区间只能被一个TT任务占据。

表2空白周期调度时刻表Tab_in的表格形式

在本发明中，设所有TT任务的TT帧帧长小于一个时间区间的长度。任意一个TT任务记为TSTT_{r_T}，其中r表示TT任务的标号，T表示该TT任务的TT任务周期，单位为毫秒，T＝1，2，4，…k，2的幂次。在本发明中，若被描述的TT任务已指明发送端系统和接收端系统时，r用“发送端系统编号_接收端系统编号”代替，如TSTT_{A_D_1}表示一个发送端系统为A端系统，接收端系统为B端系统，TT任务周期为1ms的TT任务；若被描述的TT任务没有指明发送节点和接收节点，r用数字表示，如TSTT_{3_2}表示标号为3，TT任务周期为2ms的TT任务。

在本发明中，TT任务在表中的放置规则如下：周期为T ms的TT任务只能在未被其他TT任务占据的同一列的时间区间里放置，该TT任务在该列中共占据k/T个时间区间，并以T-1个时间区间为间隔分布在该列中。

举例说明TT任务的放置：周期调度时刻表为空，即空白周期调度时刻表，k＝8，TT任务TSTT_r-T的周期T＝4，那么该任务需要占据2个时间区间，这两个时间区间的位置位于同一列并且间隔为4-1＝3。在空白周期调度时刻表中可以放置的位置如表3所示：t₁₁和t₅₁、t₂₁和t₆₁、t₃₁和t₇₁、t₄₁和t₈₁、t₁₂和t₅₂、t₂₂和t₆₂、t₃₂和t₇₂、t₄₂和t₈₂…t_1n和t_5n、t_2n和t_6n、t_3n和t_7n、t_4n和t_8n。

表3矩阵周期为8ms的空白周期调度时刻表

在本发明中，任意一个端系统ES_b(b表示端系统的编号)对外发送TT任务的周期调度时刻表记为发-周期调度时刻表Tab_b-send；任意一个端系统ES_b接收TT任务的周期调度时刻表记为收-周期调度时刻表Tab_b-receive。

在本发明中，任意一个交换机SW_c(c表示交换机的编号)向其直接相连节点Nod_d转发接收到的TT任务的周期调度时刻表记为转-Nod_d-周期调度时刻表

其中Nod_d需表明节点为端系统还是交换机。

在本发明中，任意一个TT任务TSTT_r-T在其发送端系统的Tab_b-send、转发节点中转发端口对应的和接收端系统的Tab_b-receive中的放置位置t_kn(t_kn也称作空白周期调度时刻表tab_in中任意一个时间区间)完全相同。所述的转发节点是指对TT任务TSTT_r-T进行转发的交换机。为了叙述方便和清楚，如图1所示，A端系统向E端系统建立的发送TT任务TSTT_{A_E_T}为例在TSTT_{A_E_T}的发送节点(A端系统)的Tab_A-send、第一转发节点(A交换机)的Tab_{A-B交换机-route}、第二转发节点(B交换机)的Tab_{B-E端系统-route}和接收节点(E端系统)的Tab_E-receive中的放置位置相同。

参见图1所示，一个典型的多个端系统与两个交换机形成的时间触发交换式网络。

图1所示为含有2台交换机的网络设置，是本发明应用的典型例子。对于单台或多于2台交换机的网络设置，本发明的动态任务建立法同样可以适用。本发明中动态任务建立法的应用条件是：时间触发交换式网络的路由为静态路由且无环，或为动态路由且无环但在该动态任务运行的过程中路由是固定的。网络中所有交换机均应增加具有建立、更新和维护周期调度时刻表的功能并且具有按照周期调度时刻表时间触发机制完成发送任务功能的模块；动态任务所经过的所有转发交换机上存有放置此动态任务的周期调度时刻表。

在该网络中包括A端系统、B端系统、C端系统、D端系统、E端系统、F端系统、A交换机和B交换机。

A端系统ES_A对外发送TT任务的周期调度时刻表记为A端系统的发-周期调度时刻表Tab_A-send；A端系统ES_A接收TT任务的周期调度时刻表记为A端系统的收-周期调度时刻表Tab_A-receive。

B端系统ES_B对外发送TT任务的周期调度时刻表记为B端系统的发-周期调度时刻表Tab_B-send；B端系统ES_B接收TT任务的周期调度时刻表记为B端系统的收-周期调度时刻表Tab_B-receive。

C端系统ES_C对外发送TT任务的周期调度时刻表记为C端系统的发-周期调度时刻表Tab_C-sent；C端系统ES_C接收TT任务的周期调度时刻表记为C端系统的收-周期调度时刻表Tab_C-receive。

D端系统ES_D对外发送TT任务的周期调度时刻表记为D端系统的发-周期调度时刻表Tab_D-send；D端系统ES_D接收TT任务的周期调度时刻表记为D端系统的收-周期调度时刻表Tab_D-receive。

E端系统ES_E对外发送TT任务的周期调度时刻表记为E端系统的发-周期调度时刻表Tab_E-send；E端系统ES_E接收TT任务的周期调度时刻表记为E端系统的收-周期调度时刻表Tab_E-receive。

F端系统ES_F对外发送TT任务的周期调度时刻表记为F端系统的发-周期调度时刻表Tab_F-send；F端系统ES_F接收TT任务的周期调度时刻表记为F端系统的收-周期调度时刻表Tab_F-receive。

A交换机SW_A向A端系统转发接收到的TT任务的周期调度时刻表记为A交换机的转-A端系统-周期调度时刻表Tab_{A-A端系统-route}。

A交换机SW_A向B端系统转发接收到的TT任务的周期调度时刻表记为A交换机的转-B端系统-周期调度时刻表Tab_{A-B端系统-route}。

A交换机SW_A向C端系统转发接收到的TT任务的周期调度时刻表记为A交换机的转-C端系统-周期调度时刻表Tab_{A-C端系统-route}。

A交换机SW_A向B交换机转发接收到的TT任务的周期调度时刻表记为A交换机的转-B交换机-周期调度时刻表Tab_{A-B交换机-route}。

B交换机SW_B向D端系统转发接收到的TT任务的周期调度时刻表记为B交换机的转-D端系统-周期调度时刻表Tab_{B-D端系统-route}。

B交换机SW_B向E端系统转发接收到的TT任务的周期调度时刻表记为B交换机的转-E端系统-周期调度时刻表Tab_{B-E端系统-route}。

B交换机SW_B向F端系统转发接收到的TT任务的周期调度时刻表记为B交换机的转-F端系统-周期调度时刻表Tab_{B-F端系统-route}。

B交换机SW_B向A交换机转发接收到的TT任务的周期调度时刻表记为B交换机的转-A交换机-周期调度时刻表Tab_{B-A交换机-route}。

在本发明中，任意交换机SW_c与端系统ES_b直接相连端口对应的转-ES_b-周期调度时刻表Tab_{c-b端系统-route}和端系统ES_b的收-周期调度时刻表Tab_b-receive有Tab_c-b-route＝Tab_b-receive。在图1中Tab_{A-A端系统-route}＝Tab_A-receive，Tab_{A-B端系统-route}＝Tab_B-receive，Tab_{A-C端系统-route}＝Tab_C-reveive，Tab_{B-D端系统-route}＝Tab_D-receive，Tab_{B-E端系统-route}＝Tab_E-receive，Tab_{B-F端系统-route}＝Tab_F-receive。

在本发明中，对于时间触发交换式网络，周期调度时刻表中的动态任务采用动态任务建立法建立，离线任务采用离线任务建立法建立。

所述的动态任务是指在时间触发交换式网络系统的运行过程中需要不定时开启和结束的TT任务，如在航空电子网络中某次语音通话的任务。

所述离线任务是指整个时间触发交换式网络系统中需要上电就执行的并且在时间触发交换式网络系统的整个运行过程中需要保持的TT任务，如在航空电子网络中导航数据信号传输的任务。

在本发明中，动态任务的建立是一个端系统向另一个端系统建立发送TT任务，动态任务的建立过程是由该TT任务的发送端发起的，依据动态任务建立法完成。为了叙述方便和清楚动态任务建立法的动态任务建立过程，以A端系统向E端系统建立发送TT任务TSTT_{A_E_T}为例进行说明，具体实施步骤如下：

步骤1-1：A端系统向E端系统发送建立TT任务的请求信号记为TTSignal_start，该建立TT任务请求信号TTSignal_start需经A交换机、B交换机进行转发；

步骤1-2：A交换机接收到TTSignal_start并向B交换机转发TTSignal_start时，A交换机进入状态锁存，不接受时间触发交换式网络中任何节点建立TT任务的请求；

步骤1-3：B交换机接收到TTSignal_start并向E端系统转发A端系统发送建立TT任务请求时，B交换机进入状态锁存，不接受时间触发交换式网络中任何节点建立TT任务的请求；

步骤1-4：E端系统接收到TTSignal_start后向B交换机发送非TT任务数据包，记为BAG_E-B。E端系统进入状态锁存，E端系统不接受时间触发交换式网络中任何节点建立TT任务的请求；所述BAG_E-B中的内容是E端系统的Tab_{E_receive}表；

步骤1-5：B交换机接收到BAG_E-B，向A交换机转发所述的非TT任务数据包BAG_E-B；

步骤1-6：A交换机接收到BAG_E-B，向A端系统发送非TT任务数据包，记为BAG_A-B；所述BAG_A-B中的内容有Tab_{E_receive}表和Tab_{A_B交换机_route}表；

步骤1-7：第一方面A端系统建立一个空白的周期调度时刻表Tab_in，并通过对BAG_A-B中周期调度时刻表的提取，得到Tab_{A_B交换机_route}和Tab_{E_receive}，通过在表Tab_in中标识Tab_{E_receive}和Tab_{A_B交换机_route}共同未被占用的时间区间t_pub-free，从而得到表Tab_{动态-公共宁闲区间}。针对表Tab_{动态-公共空闲区间}使用左端压缩原则获得A端系统向E端系统发送TT任务时的周期调度时刻表Tab_{A_E}；

第二方面A端系统向A交换机发送非TT任务数据包，记为BAG_A-E，所述BAG_A-E中的内容是周期调度时刻表Tab_{A_E}。其中BAG_A-E将通过A交换机、B交换机最终到达E端系统；

第三方面A端系统将周期调度时刻表Tab_{A_E}加载到Tab_{A_send}上，即按照Tab_{A_E}中TSTT_{A_E_T}所占时间区间的位置在TAb_{A_send}中相同位置放置TSTT_{A_E_T}，得到更新后的Tab_{A_send}，记为Tab_{A_send_new}；

步骤1-8：A交换机接收数据包BAG_A-E，然后向B交换机转发该数据包；并通过对BAG_A-E中周期调度时刻表的提取，得到周期调度时刻表Tab_{A_E}，然后将Tab_{A_E}加载到Tab_{A_B交换机_route}表中，得到更新后的TT任务表Tab_{A_B交换机_route_new}。其中Tab_{A_B交换机_route}是A交换机向B交换机转发TT任务的周期调度时刻表；

步骤1-9：B交换机接收数据包BAG_A-E，然后向E端系统转发该数据包；并通过对BAG_A-E中周期调度时刻表的提取，得到周期调度时刻表Tab_{A_E}，然后将Tab_{A_E}加载到Tab_{B_E端系统_route}表中，得到更新后的TT任务表Tab_{B_E端系统_route_new}。其中Tab_{B_E端系统_route}是B交换机向E端系统转发TT任务的周期调度时刻表；

步骤1-10：E端系统接收数据包BAG_A-E，通过对BAG_A-E中周期调度时刻表的提取，得到周期调度时刻表Tab_{A_E}。E端系统第一方面将Tab_{A_E}加载到Tab_{E_receive}表中，得到更新后的TT任务表Tab_{E_receive_new}。其中Tab_{E_receive}是E端系统接收TT任务的周期调度时刻表；

第二方面E端系统向A端系统发送TT帧允许信号，记为TTSignal_enable，将通过B交换机、A交换机最终到达A端系统；

第三方面E端系统取消状态锁存，并接受时间触发交换式网络中所有节点的请求；

步骤1-11：B交换机接收到TT帧允许信号TTSignal_enable并向A交换机转发该信号，同时B交换机取消状态锁存，并接受时间触发交换式网络中所有节点的TT帧发送请求；

步骤1-12：A交换机向A端系统转发TT帧允许信号TTSignal_enable，A交换机取消状态锁存，并接受时间触发交换式网络中所有节点的TT帧发送请求；

步骤1-13：A端系统接收到TT帧允许信号TTSignal_enable，A端系统开始按照A端系统的TT任务发送表Tab_{A_send}中TSTT_{A_E_T}的时间区间对E端系统开始TT任务发送。若在一定时间(可配置)内没有收到TT帧允许信号TTSignal_enable，则重复步骤1-1至步骤1-13。

动态任务建立法保证了同一TT任务在与之相关的周期调度时刻表中所在的位置完全相同。与TT任务相关的周期调度时刻表指该任务发送节点的任务发-周期调度时刻表，接受节点的收-周期调度时刻表以及该TT任务所经过的所有交换节点的转-Nod_d-周期调度时刻表。

在本发明中，动态任务的删除是一个端系统向另一个端系统停止已经建立的TT任务并清除所有节点中该任务对相关TT任务周期调度时刻表时间区间的占用。动态任务的删除过程是由该TT任务的发送端发起的，依据动态任务建立法完成。为了叙述方便和清楚动态任务建立法的动态任务删除过程，以删除A端系统向E端系统已建立发送TT任务TSTT_{A_E_T}为例进行说明，具体实施步骤如下：

步骤2-1：第一方面A端系统停止对E端系统的发送TT任务TSTT_{A_E_T}，并向E端系统发送结束TT任务请求信号TTSignal_finish，该信号TTSignal_finish需经A交换机、B交换机最终到达E端系统。

所述结束TT任务请求信号TTSignal_finish是指向E端系统请求结束A端系统对E端系统的发送TT任务的信号。

第二方面A端系统在Tab_{A_send_new}中删除时刻表Tab_{A_E}，即按照Tab_{A_E}中TT任务TSTT_{A_E_T}所占用时间区间的位置，在Tab_{A_send_new}表中的相同位置删除TSTT_{A_E_T}任务，记为Tab_{A_send_delete}；

步骤2-2：A交换机向B交换机转发结束TT任务请求信号TTSignal_finish，同时A交换机进入状态锁存，不接受时间触发交换式网络中任何节点建立TT任务的请求；

步骤2-3：B交换机向E端系统转发TTSignal_finish，同时B交换机进入状态锁存，不接受时间触发交换式网络中任何节点建立TT任务的请求；

步骤2-4：第一方面E端系统接收到TTSignal_finish后进入状态锁存，同时E端系统删除Tab_{E_receive}中的时刻表Tab_{A_E}；

第二方面E端系统向A端系统发送已结束TT任务信号TTSignal_finished，该已结束TT任务信号TTSignal_finished需经B交换机、A交换机最终到达A端系统；

第三方面E端系统取消状态锁存，接受时间触发交换式网络中所有节点的请求；

步骤2-5：第一方面B交换机接收到TTSignal_finished，并将TTSignal_finished转发给A交换机；

第二方面B交换机删除Tab_{B_E端系统_route_new}中的时刻表Tab_{A_E}；

第三方面B交换机取消状态锁存，接受时间触发交换式网络中所有节点的请求；

步骤2-6：第一方面A交换机接收到的TTSignal_finished，将接收到TTSignal_finished转发给A端系统；

第二方面A交换机删除Tab_{A_B交换机_route_new}中的时刻表Tab_{A_E}，得到Tab_{A_B交换机_route_delete}；

第三方面A交换机取消状态锁存，接受时间触发交换式网络中所有节点的请求。

步骤2-7：A端系统接收到TTSignal_finished。若在一定时间(可配置)内未收到该信号，则重复步骤2-1至步骤2-7。

以上所述的TT任务的建立和删除过程中所有的信号和数据包的发送和转发都是通过RC流量完成的。

在本发明中，动态任务建立法在时间触发交换式网络中已有调度表的基础上新增一个TT任务TSTT_r-T，要遵循左端压缩原则。左端压缩原则描述如下：

步骤3-1：在Tab_{动态-公共空闲区间}的时间区间t_pub-free中挑选出所有能够放置TSTT_r-T的t_pub-free所在的列；

步骤3-2：在挑选出的列中选择最靠左端的列L_min；

步骤3-3：在列L_min中，按照3个条件选择TSTT_r-T放置的位置，这三个条件按优先级从大到小分别是：第一条件，能放置任务TSTT_r-T(此条件为必要条件)；第二条件能将其他t_pub-free等间隔分开；第三条件，该位置在L_min中行标最小。

举例说明左端压缩原则。当k＝8，n＝16时，即基本周期为1ms，矩阵周期为8ms。初始的周期调度时刻表(如表1所示)为空，需要增加的动态任务依次为(a)周期为8ms的8个任务(记为TSTT_{r_8})、(b)周期为4ms的4个任务(记为TSTT_{r_4})、(c)周期为2ms的2个任务(记为TSTT_{r_2})和(d)周期为1ms的1个任务(记为TSTT_{r_1})。左端压缩原则要求每增加一个新的TT任务时，将该TT任务放置到周期调度时刻表尽量靠左边的位置。根据左端压缩原则，上述任务生成的周期调度时刻表的TT部分左端4列用矩阵表示为[TSTT_{r_8} TSTT_{r_4} TSTT_{r_2} TSTT_{r_1}](如表4所示)，r表示相同周期的TT任务建立的先后次顺编号，在所述周期调度时刻表的第1列中放置TSTT_{r_8}，第2列中放置TSTT_{r_4}，第3列中放置TSTT_{r_2}，第4列中放置TSTT_{r_1}。在此例中根据上述TT任务生成的周期调度时刻表的第一列中全部放置周期为8ms的任务，第二列中全部放置周期为4ms的任务，第三列中全部放置周期为2ms的任务，第四列中全部放置周期为1ms的任务，但在实际应用中并没有这样的限制，根据不同TT任务的先后加载顺序和左端压缩原则，相同周期的TT任务可能出现在不同的列的不同的位置。在实际应用中，对于基本周期为1ms，矩阵周期为8ms的情况，矩阵[TSTT_{r_8} TSTT_{r_4} TSTT_{r_2} TSTT_{r_1}]有实际的应用价值(此时TT任务TSTT_r-8、TSTT_r-4、TSTT_r-2、TSTT_r-1并不实际存在)，比如增加周期为4ms的1个任务，首先确定能够放置该任务的列标最小的列。然后需查找矩阵[TSTT_{r_8} TSTT_{r_4} TSTT_{r_2} TSTT_{r_1}]中的第2列(因为该TT任务周期为4ms)中的位置，若TSTT_{1_4}所在位置没有被占用则该任务就放在TSTT_{1_4}所在位置。若TSTT_{1_4}所在位置已被占用而TSTT_{2_4}、TSTT_{3_4}、TSTT_{4_4}所在位置未被占用则该任务就放在TSTT_{2_4}所在位置，总之就是按TSTT_{r_4}中所在的位置能够放置该任务且编号r最低的TSTT_{r_4}所在位置放置。

表4用左端压缩原则放置任务的周期调度时刻表

在本发明中，因为多个动态任务是逐个在周期调度时刻表中进行建立的，所以动态任务的建立既可以在全部时刻调度表均未分配TT任务，即周期调度时刻表为空的情况下进行，也可以在部分周期调度时刻表上已经分配了TT任务的情况下开始进行。只要周期调度时刻表未被占用的时间区间可以放置TT任务TSTT_a-T，则可以用动态任务建立法将TSTT_a-T加入到与该任务相关的周期调度时刻表中。这意味着，在时间触发交换式网络有TT任务运行并且没有任何其他TT任务在动态建立或删除的任意时刻，将动态任务建立法建立的一套周期调度时刻表存储起来，在这个网络下次上电启动或重启动时自动加载这些已经存储了任务的周期调度时刻表，其它动态任务在现有周期调度时刻表的基础上使用动态任务建立法进行建立。这也意味着如果将时间触发交换式网络中所有的离线任务在离线设计状态下使用计算机程序仿真的方法生成放置了离线任务的周期调度时刻表，称为离线任务的周期调度时刻表，分别存储到对应的各个节点中，在整个网络上电时各个节点自动加载离线任务周期调度时刻表。

在本发明的实际应用中，整个时间触发交换式网络上电时各个节点自动加载相应地放置了离线任务的周期调度时刻表，离线任务在表中按照时间触发机制开始运行，在该时间触发交换式网络的运行过程中，需要启动的动态任务(如TSTT_a-T)按照动态任务建立法在相关节点上在离线任务周期调度时刻表的基础上建立。离线任务和动态任务按照周期调度时刻表，以时间触发机制无冲突、有序运行。

在本发明中，离线任务周期调度时刻表的建立方法为离线任务建立法。离线任务建立法就是在离线设计的环境下，用计算机程序仿真的方法，先将所有时间触发交换式网络中的离线任务按照任务的编号排列，然后使用动态生成方法加载，并生成该时间触发交换式网络中所有节点的离线任务周期调度时刻表。由于根据不同的离线任务加载顺序得到的周期调度时刻表是不同的，离线生成方法将以所有的加载顺序进行仿真计算，并得到所有的不同加载顺序所对应的一组表格，并根据公共空闲区间法对生成的每一组周期调度时刻表进行评估，选取最优的周期调度时刻表组作为该时间触发交换式网络的离线任务的周期调度时刻表组。

离线任务建立法保证了同一TT任务在与之相关的周期调度时刻表中占据的位置完全相同。

在本发明中，公共空闲区间法是将时间触发交换式网络系统中所有端系统ES_b对外发送TT任务的周期调度时刻表Tab_b-send中共有的未被占用的时间区间t_pub-free进行统计，建立一个空白的周期调度时刻表Tab_in，在Tab_in中仅标识t_pub-free，得到离线公共空闲区间表Tab_{离线-公共空闲区间}。公共空闲区间法以Tab_{离线-公共空闲区间}中的标识时间区间可以填充的各种同周期TT任务数目的加权和作为评价结果。

公共空闲区间法的具体步骤如下：

步骤4-1：将时间触发交换式网络中各个节点离线生成的周期调度表的空闲时间区间做出标记；

步骤4-2：将上述各个表中所共有的空闲时间区间t_pub-free做出统计得到离线公共空闲区间表Tab_{离线-公共空闲区间}。离线公共空闲区间表Tab_{离线-公共空闲区间}的结构与周期调度时刻表相同，只是在共有的未被占用的时间区间t_pub-free和其他时间区间的位置进行不同的标识，如表5所示；

步骤4-3：对Tab_{离线-公共空闲区间}中每一列的公共空闲区间进行评估，其方法是计算该列按照左端压缩原则能够放置的周期为1ms的任务数记为a₁，周期为2ms的任务数记为a₂，周期为4ms的任务数记为a₄，…周期为kms的任务数记为a_k；

步骤4-4：对每一列n的不同周期任务数进行加权求和的结果记为S_n，权值为正数分别记为w_n，S_n＝w₁·a₁+w₂·a₂+w₄·a₄+...+w_k·a_k；

步骤4-5：对于所有列的加权求和结果S_n再求和，记为该公共空闲区间表的评价结果Est，即Est＝S₁+S₂+S₃+...+S_n。该离线生成的周期调度时刻表组的评价结果Est越大，表明该组离线任务的周期调度时刻表可以继续容纳的动态任务数越多，即该组离线任务的周期调度时刻表更为优化合理。

表5和表6是不同的离线任务加载顺序生成的公共空闲区间表。

表5公共空闲区间表1

注：“□”代表表格时间区间被占用；

“○”代表表格时间区间未被占用。

表6公共空闲区间表2

注：“□”代表表格时间区间被占用；

“○”代表表格时间区间未被占用。

以表5和表6为例说明公共空闲区间法。对表5进行评估，即统计空闲区域，第3列的空闲区域若放置周期为2ms的TT任务可以放1个，若放置周期为4ms的TT任务可以放2个，若放置周期为8ms的TT任务可以放4个。第4列于第3列情况一致。再对表6进行评估，第4列的空闲区域，若放置周期为1ms的TT任务可以放1个，若放置周期为2ms的TT任务可以放2个，若放置周期为4ms的TT任务可以放4个，若放置周期为8ms的TT任务可以放8个。由于表5和表6的5至16列的情况一致，这里仅比较3，4列即可，设不同周期任务的评价权值相同，则表5的评价结果为2×(1+2+4)＝14，表6的评价结果为1+2+4+8＝15，15＞14故认为表6所代表的离线生成表相对于表5所代表的离线生成表为最优的离线生成表。

表7和表8分别为假设的离线任务和动态任务。需离线生成的TT任务有：A端系统向B端系统发送周期为1ms的TT任务，记为TSTT_{A_B_1}；A端系统向D端系统发送周期为1ms的TT任务，记为TSTT_{A_D_1}；B端系统向D端系统发送周期为4ms的TT任务，记为TSTT_{B_D_4}；D端系统向E端系统发送周期为4ms的TT任务，记为TSTT_{D_E_4}；D端系统向F端系统发送周期为1ms的TT任务，记为TSTT_{D_F_1}；E端系统向A端系统发送周期为2ms的TT任务，记为TSTT_{E_A_2}。需动态生成的任务有：A端系统向C端系统发送周期为1ms的TT任务，记为TSTT_{A_C_1}；C端系统向A端系统发送周期为1ms的TT任务，记为TSTT_{C_A_1}；F端系统向D端系统发送周期为2ms的TT任务，记为TSTT_{F_D_2}；F端系统向A端系统发送周期为4ms的TT任务，记为TSTT_{F_A_4}；E端系统向C端系统发送周期为4ms的TT任务，记为TSTT_{E_C_4}；E端系统向B端系统发送周期为2ms的TT任务，记为TSTT_{E_B_2}。表6和表7只是普通的任务实例，没有特殊性。本发明所针对的任务的周期可以相同也可以不同，任何两个端系统之间都可以建立任务。本发明可以方便的对TT任务建立周期调度时刻表。

表7离线任务

发送

A端系统

A端系统

B端系统

D端系统

D端系统

E端系统

接收

B端系统

D端系统

D端系统

E端系统

F端系统

A端系统

TT任务周期(ms)

1

1

4

4

1

2

表8动态任务

发送

A端系统

C端系统

F端系统

F端系统

E端系统

E端系统

接收

C端系统

A端系统

D端系统

A端系统

C端系统

B端系统

TT任务周期(ms)

1

1

2

4

4

2

表9至表14分别为图1时间触发交换式网络中的Tab_{A_send}，Tab_{A_receive}，Tab_{E_send}，Tab_{E_receive}，Tab_{A_B交换机_route}，Tab_{B_A交换机_route}，是表7中的离线任务和表8中的动态任务分别按照离线任务建立法和动态任务建立法建立生成的。具体生成方法已在动态任务建立法和离线任务建立法中详细说明。根据系统中的以生成的整套周期调度时刻表：Tab_{A_receive}，Tab_{A_send}，Tab_{B_receive}，Tab_{B_send}，Tab_{C_receive}，Tab_{C_send}，Tab_{D_receive}，Tab_{D_send}，Tab_{E_reveive}，Tab_{E_send}，Tab_{F_receive}，Tab_{F_send}，Tab_{A_A端系统_route}，Tab_{A_B端系统_route}，Tab_{A_C端系统_route}，Tab_{B_D端系统_route}，Tab_{B_E端系统_route}，Tab_{B_F端系统_route}，Tab_{A_B交换机_route}，Tab_{B_A交换机_route}，表7和表8中描述的离线及动态任务可以在图1系统中保证时间确定性、无冲突地有序执行。

表9周期调度时刻表Tab_{A_send}

注：“▲”代表离线生成的任务；

“★”代表动态生成的任务；

“○”代表表格时间区间未被占用。

表9说明A端系统任务TSTT_{A_B_1}、TSTT_{A_D_1}、TSTT_{A_C_1}在Tab_{A_send}中放置情况，排布紧凑，任务之间没有空闲区间。离线任务TSTT_{A_B_1}和TSTT_{A_D_1}根据离线任务建立法先存在于表Tab_{A_send}中，在该时间触发交换式网络启动时就自动加载，动态任务TSTT_{A_C_1}在该时间触发交换式网络运行过程中建立的。离线任务TSTT_{A_B_1}和TSTT_{A_D_1}与动态任务TSTT_{A_C_1}都存在于周期调度时刻表Tab_{A_send}中，有序无冲突地进行周期性发送。

A端系统按照Tab_{A_send}，在TSTT_{A_B_1}、TSTT_{A_D_1}和TSTT_{A_C_1}占用的时间区间内无冲突地向A交换机发送相应的TT任务。

表10周期调度时刻表Tab_{A_receive}

注：“▲”代表离线生成的任务；

“★”代表动态生成的任务；

“○”代表表格时间区间未被占用。

表10中，Tab_{A_receive}说明A端系统接收的TT任务有：TSTT_{E_A_2}、TSTT_{C_A_1}、TSTT_{F_A_4}。其中TSTT_{E_A_2}为离线任务，TSTT_{C_A_1}和TSTT_{F_A_4}为动态任务。仅看Tab_{A_receive}，按照动态任务建立法左端压缩原则，TSTT_{F_A_4}应该放置在Tab_{A_receive}中第2行第1列的位置。但是从整个时间触发交换式网络来看，离线任务TSTT_{F_D_2}已经占用了Tab_{F_send}中的第2行第1列以及第4行第1列的时间区间。故TSTT_{F_A_4}不能放置在Tab_{F_send}中的第2行第1列以及第4行第1列的时间区间，根据同一TT任务在其相关节点的周期调度时刻表中的放置位置一致，得到TSTT_{F_A_4}不能放置在Tab_{F_send}中的第2行第1列或第4行第1列的时间区间。这说明了本发明中周期调度任务表法对于交换式网络空间节点分布以及TT任务周期时间排布的规划合理。

A端系统在Tab_{A_receive}中的TSTT_{E_A_2}、TSTT_{C_A_1}和TSTT_{F_A_4}占用的时间区间内无冲突地分别接收到相应TT任务。

表11周期调度时刻表Tab_{E_send}

注：“▲”代表离线生成的任务；

“★”代表动态生成的任务；

“○”代表表格时间区间未被占用。

E端系统按照Tab_{E_send}，在TSTT_{E_A_2}、TSTT_{E_C_4}和TSTT_{E_B_2}占用的时间区间内无冲突地向B交换机发送相应的TT任务。

表12周期调度时刻表Tab_{E_receive}

注：“▲”代表离线生成的任务；

“★”代表动态生成的任务；

“○”代表表格时间区间未被占用。

E端系统在Tab_{E_receive}中的TSTT_{D_E_4}占用的时间区间内无冲突地接收到TSTT_{D_E_4}任务。

表13周期调度时刻表Tab_{A_B交换机_route}

注：“▲”代表离线生成的任务；

“★”代表动态生成的任务；

“○”代表表格时间区间未被占用。

A交换机按照Tab_{A_B交换机_route}，在TSTT_{B_D_4}和TSTT_{A_D_1}占用的时间区间内无冲突地向B交换机转发相应的TT任务。

表14周期调度时刻表Tab_{B_A交换机_route}

注：“▲”代表离线生成的任务；

“★”代表动态生成的任务；

“○”代表表格时间区间未被占用。

B交换机按照Tab_{B_A交换机_route}，在TSTT_{E_A_2}、TSTTE_{E_C_4}、TSTT_{E_B_2}和TSTT_{F_A_4}占用的时间区间内无冲突地向A交换机转发相应的TT任务。

Claims (5)

1.一种适用于时间触发交换式网络的周期调度时刻表构建方法，其特征在于：时间触发交换式网络的路由为静态路由且无环，或为动态路由且无环但在该动态任务运行的过程中路由是固定的；网络中所有交换机均应增加具有建立、更新和维护周期调度时刻表的功能并且具有按照周期调度时刻表时间触发机制完成发送任务功能的模块；动态任务所经过的所有转发交换机上存有放置此动态任务的周期调度时刻表；

对于时间触发交换式网络，周期调度时刻表中的动态任务采用动态任务建立法建立，离线任务采用离线任务建立法建立；

任意交换机SW_c与端系统ES_b直接相连端口对应的转-ES_b-周期调度时刻表Tab_{c-b端系统-route}和端系统ES_b的收-周期调度时刻表Tab_b-receive有Tab_c-b-route＝Tab_b-receive；

动态任务的建立是一个端系统向另一个端系统建立发送TT任务，动态任务的建立过程是由该TT任务的发送端发起的，依据动态任务建立法完成；

动态任务的删除是一个端系统向另一个端系统停止已经建立的TT任务并清除所有节点中该任务对相关TT任务周期调度时刻表时间区间的占用；动态任务的删除过程是由该TT任务的发送端发起的，依据动态任务建立法完成。

2.根据权利要求1所述的适用于时间触发交换式网络的周期调度时刻表构建方法，其特征在于动态任务建立的过程为：

步骤1-1：A端系统向E端系统发送建立TT任务的请求信号记为TTSignal_start，该建立TT任务请求信号TTSignal_start需经A交换机、B交换机进行转发；

步骤1-2：A交换机接收到TTSignal_start并向B交换机转发TTSignal_start时，A交换机进入状态锁存，不接受时间触发交换式网络中任何节点建立TT任务的请求；

步骤1-3：B交换机接收到TTSignal_start并向E端系统转发A端系统发送建立TT任务请求时，B交换机进入状态锁存，不接受时间触发交换式网络中任何节点建立TT任务的请求；

步骤1-4：E端系统接收到TTSignal_start后向B交换机发送非TT任务数据包，记为BAG_E-B；E端系统进入状态锁存，E端系统不接受时间触发交换式网络中任何节点建立TT任务的请求；所述BAG_E-B中的内容是E端系统的Tab_{E_receive}表；

步骤1-5：B交换机接收到BAG_E-B，向A交换机转发所述的非TT任务数据包BAG_E-B；

步骤1-6：A交换机接收到BAG_E-B，向A端系统发送非TT任务数据包，记为BAG_A-B；所述BAG_A-B中的内容有Tab_{E_receive}表和Tab_{A_B交换机_route}表；

步骤1-7：第一方面A端系统建立一个空白的周期调度时刻表Tab_in，并通过对BAG_A-B中周期调度时刻表的提取，得到Tab_{A_B交换机_route}和Tab_{E_receive}，通过在表Tab_in中标识Tab_{E_receive}和Tab_{_B交换机_route}共同未被占用的时间区间t_pub-free，从而得到表Tab_{动态-公共空闲区间}；针对表Tab_{动态-公共空闲区间}使用左端压缩原则获得A端系统向E端系统发送TT任务时的周期调度时刻表Tab_{A_E}；

步骤1-8：A交换机接收数据包BAG_A-E，然后向B交换机转发该数据包；并通过对BAG_A-E中周期调度时刻表的提取，得到周期调度时刻表Tab_{A_E}，然后将Tab_{A_E}加载到TAb_{A_B交换机_route}表中，得到更新后的TT任务表Tab_{A_B交换机_route_new}；其中Tab_{A_B交换机_route}是A交换机向B交换机转发TT任务的周期调度时刻表；

步骤1-9：B交换机接收数据包BAG_A-E，然后向E端系统转发该数据包；并通过对BAG_A-E中周期调度时刻表的提取，得到周期调度时刻表Tab_{A_E}，然后将Tab_{A_E}加载到Tab_{B_E端系统_route}表中，得到更新后的TT任务表Tab_{B_E端系统_route_new}；其中Tab_{B_E端系统_route}是B交换机向E端系统转发TT任务的周期调度时刻表；

步骤1-10：E端系统接收数据包BAG_A-E，通过对BAG_A-E中周期调度时刻表的提取，得到周期调度时刻表Tab_{A_E}；E端系统第一方面将Tab_{A_E}加载到Tab_{E_receive}表中，得到更新后的TT任务表Tab_{E_receive_new}；其中Tab_{E_receive}是E端系统接收TT任务的周期调度时刻表；

步骤1-11：B交换机接收到TT帧允许信号TTSignal_enable并向A交换机转发该信号，同时B交换机取消状态锁存，并接受时间触发交换式网络中所有节点的TT帧发送请求；

步骤1-12：A交换机向A端系统转发TT帧允许信号TTSignal_enable，A交换机取消状态锁存，并接受时间触发交换式网络中所有节点的TT帧发送请求；

步骤1-13：A端系统接收到TT帧允许信号TTSignal_enable，A端系统开始按照A端系统的TT任务发送表Tab_{A_send}中TSTT_{A_E_T}的时间区间对E端系统开始TT任务发送；若在一定时间内没有收到TT帧允许信号TTSignal_enable，则重复步骤1-1至步骤1-13。

3.根据权利要求1所述的适用于时间触发交换式网络的周期调度时刻表构建方法，其特征在于动态任务删除的过程为：

步骤2-1：第一方面A端系统停止对E端系统的发送TT任务TSTT_{A_E_T}，并向E端系统发送结束TT任务请求信号TTSignal_finish，该信号TTSignal_finish需经A交换机、B交换机最终到达E端系统；

所述结束TT任务请求信号TTSignal_finish是指向E端系统请求结束A端系统对E端系统的发送TT任务的信号；

步骤2-2：A交换机向B交换机转发结束TT任务请求信号TTSignal_finish，同时A交换机进入状态锁存，不接受时间触发交换式网络中任何节点建立TT任务的请求；

步骤2-3：B交换机向E端系统转发TTSignal_finish，同时B交换机进入状态锁存，不接受时间触发交换式网络中任何节点建立TT任务的请求；

步骤2-4：第一方面E端系统接收到TTSignal_finish后进入状态锁存，同时E端系统删除Tab_{E_receive}中的时刻表Tab_{A_E}；

步骤2-5：第一方面B交换机接收到TTSignal_finished，并将TTsignal_finished转发给A交换机；

步骤2-6：第一方面A交换机接收到的TTSignal_finished，将接收到TTSignal_finished转发给A端系统；

步骤2-7：A端系统接收到TTSignal_finished；若在一定时间内未收到该信号，则重复步骤2-1至步骤2-7。

4.根据权利要求1所述的适用于时间触发交换式网络的周期调度时刻表构建方法，其特征在于：动态任务建立法在时间触发交换式网络中已有调度表的基础上新增一个TT任务TSTT_r-T，要遵循左端压缩原则；左端压缩原则描述如下：

步骤3-1：在Tab_{动态-公共空闲区间}的时间区间t_pub-free中挑选出所有能够放置TSTT_r-T的t_pub-free所在的列；

步骤3-2：在挑选出的列中选择最靠左端的列L_min；

步骤3-3：在列L_min中，按照3个条件选择TSTT_r-T放置的位置，这三个条件按优先级从大到小分别是：第一条件，能放置任务TSTT_r-T；第二条件能将其他t_pub-free等间隔分开；第三条件，该位置在L_min中行标最小。

5.根据权利要求1所述的适用于时间触发交换式网络的周期调度时刻表构建方法，其特征在于：公共空闲区间法是将时间触发交换式网络系统中所有端系统ES_b对外发送TT任务的周期调度时刻表Tab_b-send中共有的未被占用的时间区间t_pub-free进行统计，建立一个空白的周期调度时刻表Tab_in，在Tab_in中仅标识t_pub-free，得到离线公共空闲区间表Tab_{离线-公共空闲区间}；公共空闲区间法以Tab_{离线-公共空闲区间}中的标识时间区间可以填充的各种同周期TT任务数目的加权和作为评价结果；

公共空闲区间法的具体步骤如下：

步骤4-1：将时间触发交换式网络中各个节点离线生成的周期调度表的空闲时间区间做出标记；

步骤4-2：将上述各个表中所共有的空闲时间区间t_pub-free做出统计得到离线公共空闲区间表Tab_{离线-公共空闲区间}；离线公共空闲区间表Tab_{离线-公共空闲区间}的结构与周期调度时刻表相同，只是在共有的未被占用的时间区间t_pub-free和其他时间区间的位置进行不同的标识；

步骤4-3：对Tab_{离线-公共空闲区间}中每一列的公共空闲区间进行评估，其方法是计算该列按照左端压缩原则能够放置的周期为1ms的任务数记为a₁，周期为2ms的任务数记为a₂，周期为4ms的任务数记为a₄，…周期为kms的任务数记为a_k；

步骤4-4：对每一列n的不同周期任务数进行加权求和的结果记为S_n，权值为正数分别记为w_n，S_n＝w₁·a₁+w₂·a₂+w₄·a₄+...+w_k·a_k；

步骤4-5：对于所有列的加权求和结果S_n再求和，记为该公共空闲区间表的评价结果Est，即Est＝S₁+S₂+S₃+...+S_n；该离线生成的周期调度时刻表组的评价结果Est越大，表明该组离线任务的周期调度时刻表可以继续容纳的动态任务数越多，即该组离线任务的周期调度时刻表更为优化合理。

Images