面向多周期循环TTP总线消息操作设计方法

连天野，熊华钢，程子敬，李 峭+

(1.北京航空航天大学 电子信息工程学院，北京 100191；2.北京卫星信息工程研究所天地一体化信息技术国家重点实验室，北京 100086)

0 引 言

时间触发通信协议，如TTP、TTCAN[1]、FlexRay等，适用于电子系统的综合化实时控制应用。其中，TTP网络具有精确的分布式时钟同步能力，已被应用于波音787的环境控制、M-346教练机的全权限数字发动机控制等，其各节点实时通信任务的调度是设计中必须考虑的问题[2]。

通过设定集群循环(cluster cycle)、TDMA周期(TDMA round)、时隙(slot)等参数，TTP总线控制器根据MEDL(message descriptor list)表进行时间触发通信。在不同的调度策略[3]下有相应的时隙占用方式，其中静态多消息分配(MM)是最为常用，且被TTTech公司的TTP-Plan工具支持。

主机端应用进程根据的周期产生多种待发送的消息，需要依据消息操作时间表(message handling time table，MHTT)表将消息通过消息底层接口(message base interface，MBI)转运到TTP控制器。然而，SAE AS6003标准并未规定具有针对性的MHTT消息操作方法，也没有明确的MHTT表设计生成方法；文献[4]中虽然涉及了多种消息在时隙中的排布模型，但采用一条FIFO队列与MBI相连，意味着输出排队可以破坏应用层通信任务固有的周期性。

借鉴FlexRay[5]的信号(signal)与帧(frame)的组织方式，针对TTP网络的时隙特性进行修正，给出一种多周期消息轮询操作(handling)架构，并提出相应的MHTT表设计方法。

在该方法中，不同于文献[6]从不相容关系方面进行划分，而是依据两两相容关系，引进最大团算法[7]求解的多周期任务的相容优化分组问题；同时在考虑严格周期性保证和可调度性必要条件的前提下，利用两组相容性检查和偏移量查找，解决了候选相容组内周期任务消息排布方法问题。

1 TTP网络的MHTT操作建模

1.1 TTP网络节点模型

SAE AS6003标准[8]中的TTP网络由节点(node)和双冗余总线构成，如图1所示，每个节点分为应用层主机、MBI接口和TTP控制器，网络中的各个节点构成分布式集群(cluster)[9]。

TTP集群进行时间触发通信，即：采用采时分多址复用(time division multiple access，TDMA)方式依次访问总线。离线设定TDMA周期(round)及其时隙(slot)划分，根据MEDL表，每个节点只有在给定的时隙内才能执行总线发送操作。

如图1所示，在应用层，MHTT作用于等待队列和MBI接口之间，其中，通信任务具有周期性，消息作为通信任务的实例被等待队列缓存，而等待队列的组织方式直接决定了任务实例向下层的转运方式。

图1 TTP网络节点模型

1.2 周期性通信任务模型

如果保证消息转运操作的严格周期性，则易于与下层时间触发通信访问相协调。对于严格周期调度任务[10]，Ti的执行时间区间Ii为

[φi+kpi,φi+kpi+ei](k∈Z)

(1)

式中：φi,pi,ei分别表示相位(第一个作业的释放时间)、周期(作业的固定释放时间间隔)和每个作业的执行时间。

任务集Λ在单处理器上严格周期可调度的充要条件是

Ii∩Ij=∅(i≠j且i,j∈1,2…N)

(2)

文献[8]可以证明，任意两个周期任务Ti，Tj在处理器上严格周期可调度的充要条件为

e(oi)≤(s(oi)-s(oj))modg≤g-e(oj)

(3)

其中：g=gcd(p(oi),p(oj))，s(oi)，s(oj) 是两个周期任务开始时间，e(oi),e(oj) 为处理两个周期任务消息所用时间。

如果两个通信任务的周期可调度，则称之为“相容”；如果通信任务组中任意两个任务都相容，则称之为候选相容组。

相容性有利于组织多周期轮询操作，但对于比较复杂的两两相容关系，需要结合MHTT表的操作模型进行合理的分组和排布。

1.3 多周期循环的MHTT表操作

在每个TDMA周期，节点只有在所属的时隙获得发送权，因此MHTT表操作的功能是：在时隙到达的时候，将本轮次中就绪的消息派发到主机接口；在运行时间组织等待队列，对通信任务产生的消息排序。本文提出一种面向多周期循环的MHTT表操作方法，如图2所示，即：MHTT表中含有多个消息组MGi，i=1,2…，分别对应于时隙中待加载的消息位置，采用轮询(round-robin)操作加载；对于具有周期相容性的通信任务，采用循环式的等待队列，保证各个通信任务的严格周期性。另外，设置一个局部先入先出(local FIFO)型的消息队列MQ，用以兼顾难以纳入相容组的通信任务。

图2 MHTT表操作模型

根据面向多周期循环的MHTT表操作方法，MBI缓存中的各个位置与MG或MQ一一对应。处于相容组的多周期通信任务采用消息组轮询派发到MBI；少量无法分配到相容组的通信任务通过消息队列MQ排队派发到MBI。

根据SAE AS6003标准，TTP节点发送时，除了时隙开始时的4-bits头部，消息没有任何协议封装，仅通过MEDL表中定时进行区分。

2 多周期循环任务与分组方式

2.1 周期任务图模型

采用周期任务图(periodical task graph，PTG)反映通信任务之间的相容关系，周期任务图是对主机通信任务之间相关性的建模，其模型G=(V,E) 由任务集合V、无向边集合E构成。周期任务抽象为PTG中的顶点。

顶点之间是否存在边取决于两顶点对应周期任务的相容性。各条消息的长度不同，发送的执行时间e不同；然而，分组仅需考虑以TDMA周期为单位的通信任务实例之间的间隔，如图3所示。图中每行均代表一定循环次序下准备输入MBI的消息，下文中将这样的消息排布的位置称为消息组的“行”。

图3 消息组中的通信任务

所以，令所有通信任务的周期均以TDMA周期为单位，且令式(3)中e(oi)和e(oj)缩展为单位1，即验证是否满足式(4)，如果满足，则顶点间存在无向边，反之边不存在

1≤(s(oi)-s(oj))modg≤g-1

(4)

2.2 周期任务图的分组

采用合理的周期任务分组可以使尽可能多的消息满足严格周期性调度，且使给定节点所需的MBI和时隙长度下限更短。依据文献中的“最大团”(max-group)算法PTG进行合理的分组。

图4 多周期任务分组

对于候选相容组内的任意任务，如果与其它任务均两两相容，则称任务之间完全相容。分组后候选相容组内的通信任务并不一定完全相容，需要在消息排布过程中进行进一步的检验和组合优化。

3 候选相容组内的消息排布

(5)

对于满足式(5)条件的候选相容组，根据表1所示的伪代码构建排布算法。按周期从小到大顺序对通信任务排序，记为T1,…,TN； 且排布时需要两个任务集合，它们分别对应排布算法结束后的消息组，不失一般性，分别记为MG1和MG2。

表1 通信任务的分组相容性

该算法降低了两两相容判断的规模，MG1中的任务可保证完全相容；给定MG1条件下再对MG2中的任务根据式(4)两两检查；排除未通过检查的情况，MG1和MG2组内完全相容即成为一种可选排布方式。

在可选排布方式中，MG2中消息采用数字编码循环方式进行优化分析；消息占位设为1，空占位设为0，以包含所有消息占位的最短数字序列作为数字循环组，对循环编码组进行平移排布。平移后的消息通过静态多消息分配(MM)方式与MG1中消息进行调度，利用偏移量查找确定最终优化解。下文将结合案例进行说明。

4 案例研究

通过仿真实验设定10个周期任务，周期以TDMA周期为单位，包含从2开始的较小质数，以及以质数为因子的12以内的数值，如表2所示，周期任务消息长度参数在10-50中随机选择。

表2 典型算例实验数据

依据2.2节所述的步骤得到周期任务如图5所示。利用最大团回溯法得到候选相容组V=(2,4,6,8,10,12)。

图5 实验算例周期任务

在MG1中周期任务完全相容的条件下，每一条路径代表一种MG2中任务相容关系，如图6所示。经过算法的进一步检查，其中路径1和路径3为可选排布方式。

图6 实验算例通信任务排布路径

对路径1和路径3采用第3节所述编码循环方式进行优化筛选，实验结果见表3。

表3 实验偏移量数据

其中循环方式1编码为：111000；方式2编码为：011100；方式3编码为001110；方式4编码为000111；方式5编码为0000111；方式6编码为00000111。

各个消息组偏移量值之和决定了时隙的长度，较短的偏移量可以适用于较短的TDMA周期长度，而且意味着缓存的容量较少，因此优先选择具有最短偏移量的MHTT表排布方案。

优化的结果可能出现多个排布方案，它们的偏移量都为最短。如图7所示，序号4,8,12的排布方案各有不同，但均为最小偏移量。此时，如果选用其中的任一个，在总体上优化效果都是可以接受的。然而，在MHTT离线设计中，可以利用更精细地评价手段选取最优的结果。

图7 算例实验数据

注意到如果排布方案的波峰、波谷起伏不规则，则对以后的扩展(即：在不改变现有方案的条件下增量化添加通信任务)造成困难。这种情况以信号处理的观点，对应着更丰富的高频分量。用离散傅氏变换的方法可以对高频分量进行观察，但在数字频率π附近存在混叠。理想的方法是采用小波变换对高频分量部分进行比较。

设排布方案的离散数据为x，则一级离散小波变换得到尺度函数的展开系数cA1[k]和小波函数的展开系数cD1[k]，其中后者代表信号的细节(即：高频)部分。如图8所示，Haar小波对图7中偏移量数据进行变换。经过比对，序号12对应较小的小波展开系数绝对值。

图8 Haar小波处理结果

最佳排布方案中相容组最大偏移量与非相同组Local FIFO最大偏移量总和为186 μs。不考虑次序的多周期消息排布方式，偏移量总和为308 μs。本方法偏移量降低40%，从而使给定节点所需的MBI和时隙长度下限更短。

5 结束语

本文提出了适用于轮询调度MHTT架构的消息操作方法，该方法分为周期消息候选相容性分组和组内优化排布两个步骤；①考虑了两两相容性构成的任务图模型并采用了最大团分组方法得到候选相容分组；②分别利用两组相容性检查和偏移量查找对组内周期通信任务进行组内排布。案例研究表明，综合利用该方法，与不考虑次序优化的多周期消息操作相比，不仅完全保证相容周期任务的可调度性，而且使给定节点所需的MBI和时隙长度下限更短。