一种新型时间触发CAN消息动态调度算法的设计及实现*

魏 磊，戴宗贤

（1.阜阳师范大学物理与电子工程学院，安徽阜阳 236037；2.重庆市计量质量检测研究院，重庆 401123）

0 引言

CAN现场总线在汽车、工业现场、楼宇自动化等领域得到广泛应用[1-4]。CAN总线采用非破坏性仲裁进行消息调度，同一总线网络中所有消息都可竞争总线控制权，最高优先级的消息获胜并被发送至总线。该仲裁机制确保了高优先级的消息实时性。但是，因总线竞争、消息碰撞导致低优先级消息传输延迟，甚至被阻塞，消息传输至目标设备的时刻具有不确定性，制约了CAN总线技术在高实时性场合的应用。

针对该问题，Bosch公司推出了基于时间触发的TTCAN协议，该协议将消息划分为周期性消息和事件性消息。周期性消息由预先制定的调度表调度，其发送活动是在各自的独占窗内进行，在此期间总线不会被其他消息抢占，确保了周期性消息的延迟确定性和实时性，提高了总线利用率[5]。但是，TTCAN协议依然存在如下弊端[6-8]：一是在一个基本周期的所有独占窗时段内，事件性消息无法获得总线控制权，该类消息传输延迟大大增加，且具有不确定性。特别是在高负载率时，事件性消息的传输延迟问题将尤为突出。然而，事件性消息往往是系统中具有紧迫性的硬实时消息，该类消息传输延迟的不确定性将增加网络通讯的风险。二是一帧周期性消息的传输时间不能充满独占窗，但剩余的时间片内又不允许事件性消息控制总线，存在对总线资源的浪费。

针对上述问题，本文提出一种新的基于时间触发的CAN总线动态调度算法，旨在确保周期性消息传输实时性的基础上，大大减少事件性消息的延迟。此外，针对算法在嵌入式系统上实现的关键技术问题进行了探讨，讨论基于STM32单片机的算法实现方法。

1 新型时间触发CAN消息调度算法

1.1 算法基本思想

算法基本思想包括以下两点。

（1）改变TTCAN协议中用于周期性消息发送窗口的独占模式，并将其重构。整合TTCAN中一个基本周内的所有独占窗为一个整体（而非像TTCAN中，各独占窗彼此独立），该时间段称之为周期性时段。在周期性时段内，周期性消息采用基于时间触发的机制进行调度。但是，在该时间段内，事件性消息可参与总线仲裁。

（2）为防止低优先级事件性消息被长时间阻塞，对事件性消息采用最低松弛度优先调度算法（Least Laxity First Scheduling Algorithm，LLF算法）进行调度。

1.2 调度矩阵

算法分为静态调度和动态调度两部分，静态调度基于TTCAN协议中的调度矩阵，其矩阵结构如图1所示。

图1 系统调度矩阵结构

一个矩阵周期由若干基本周期（Basic Cycle，BC）组成，基本周期由若干消息窗口组成。每个基本周期开始于由主节点发出的同步消息，同步消息用于同步各从节点的调度时钟。在各个周期标志到来的时刻，预设的周期性消息被发送至总线，而且每个消息窗口只有一个周期性消息被发送至总线。特别强调，周期性窗口内事件性消息的发送不受限制。因而，可以在两个相邻周期性消息发送的间隙发送事件性消息，从而大大降低事件性消息的排队等待时间，具体如图2所示。

图2 事件性消息发送过程

从图中可知，假设有一事件性消息在t1时刻产生，根据TTCAN协议，消息至少要延迟到t4时刻发送，则其延迟时间至少为t4-t1。根据本文算法，则t1时刻即可发送。在周期性消息的空闲事件片内发送事件性消息，不仅增加了总线利用率，而且大大降低了事件性消息的延迟。

随之而来的问题是，取消TTCAN的独占窗模式可能会使周期性消息的传输被延迟。如图2所示，假设在t2时刻产生了事件性消息，该消息将占用总线控制权，且在t3时刻才能完成消息发送，周期性消息B将会被延迟。为保证周期性消息的实时性，设定周期性消息的优先级高于事件性消息，那么事件性消息最多阻塞周期性消息一帧的时间，这种延迟是可以接受的。

1.2.1 调度矩阵参数计算

调度矩阵是本文算法的核心，调度矩阵设计由矩阵规模的设计和周期性消息在矩阵内排列的设计两部分组成。矩阵规模的设计需要计算的参数分别是：矩阵周期、基本周期、矩阵行数、矩阵列数，各参数由如下方法确定。

设CAN总线中的所有周期性消息的周期按照从小到大的顺序排列，得到一个周期集合{ }T1，T2，T3，…，Tm。

（1）矩阵周期

矩阵取上述周期集合的最小公倍数，矩阵周期用TMC表示。

式中：[]为取最小公倍数。

这样，每个周期性消息在一个矩阵周期内被调度次数为整数。

（2）基本周期

基本周期为各个周期的最大公约数，用TBC表示。

式中：()为取最大公约数。

（3）矩阵行数

矩阵行数用L表示。

（4）矩阵周期列数

设周期性消息总数为n，周期性消息中最长消息的传输时间为tmax，则各参数应满足：

否则，需要增大波特率。

设周期性消息平均传输时间为ta，事件性消息总传输时间为tc，同步消息传输时间为ts，则极端情况下，基本周期内事件性消息的可传输率为：

若λ值太小，会使得在负载量较高时事件性消息的传输延迟增大，甚至不可调度，这时需要增大波特率以增大ë值，为事件性消息预留更多总线带宽。

1.2 .2周期性消息装载

矩阵周期规模确定后，就要考虑周期性消息在调度矩阵中的排列，即周期性消息的装载，装载原则为周期性消息在各基本周期的数目基本一致，以避免总线负载率的较大波动。具体装载方法如下。首先将周期性消息按照周期大小进行分类，把相同周期的消息分为一组，分组后的消息集合为：中，消息Mki的周期为Tk，设Tk TBC=ak。消息的装载根据周期大小，从小到大依次开始进行，对于周期为Tk的消息，每隔ak个基本周期装载1次。相同周期的消息均匀分布在不同的基本周期内，使得各基本周期的负载率基本一致。

为了让同步消息能够及时地发送到总线上，在每个基本周期的末尾设置一个空闲窗口，在空闲窗口内从节点禁止消息发送，以等待接收来自主节点的同步消息。

2 事件性消息动态调度及嵌入式实现方法

在CAN总线的负载量较高时，低优先级事件性消息可能会被阻塞而错过截止期，为保证其实时性，本文采用LLF算法对事件性消息进行实时调度。LLF算法根据消息的紧急程度（松弛度）确定消息的优先级，松弛度越低的消息优先级越高[9]。消息的松弛度为ΔtL，定义消息的生成时刻与截止时刻之间的时间段长度为有效生存期，用Δtp表示，消息从抢占总线到发送成功所需的时间为ti，则消息的松弛度ΔtL=Δtp-ti。

同时，竞争总线的消息因松弛度不同，各消息的优先级会被动态调整。CAN消息是基于标识符仲裁进行调度的，事件性消息的动态调度需要动态调整其标识符。但是，CAN消息的标识符是消息的ID，是对消息种类及功能识别的标识，也是各节点的CAN收发器进行消息滤波的依据，对标识符的更改将影响这些功能。如何统筹CAN标识符的动态变化和消息的识别及滤波，是LLF算法在CAN总线应用的关键。本文基于STM32单片机论述LLF算法在嵌入式CAN总线中实现的方法。

嵌入式系统以低成本、高效便捷的优势广泛应用在现场总线的各个领域[10-12]。STM32是基于ARMCortex-M3内核的一款高性能嵌入式微控制器，已在各个领域得到广泛应用。STM32内部自带bxCAN收发控制器。bxCAN具有3个发送邮箱和2个三级深度的接收FIFO，并且具有可屏蔽、位宽可变的消息过滤器组，用于对总线消息的硬件过滤，这种硬件过滤机制大大节约了CPU开销。过滤器组具有对CAN消息标识符的部分位进行选择性过滤能力，即可以只过滤某些指定的位，而不关心其余位的标识符能否与过滤器匹配。借助该功能可实现LLF算法对CAN消息的调度。

因事件性消息可在周期性消息窗口内发送，为了防止事件性消息长时间阻塞周期性消息，周期性消息的优先级要高于事件性消息，设定周期性消息标识符的最高位为0，事件性消息标识符的最高位为1。将余下的标识符位分为两部分，后M位设定为固定部分，用于CAN收发器过滤器组的过滤及消息功能识别，那么系统中可调度的消息数目为2M。其余标识符位可变部分，定义由这些可变位组成的数值大小为IDdynamic，用于LLF算法的动态调整。

设系统中所有消息的最大有效生存期为Δtpmax，则：

IDdynamic的计算由CAN网络中各个子节点自行调度。为保证最低松弛度的消息能够被及时地发送，对消息动态ID部分的调整应保持一定频率，而且应确保即使具有最小有效生存期的消息也能够被多次提升优先级，以保证其实时发送。消息ID的调整周期应设定得比所有消息传输时间的最小值还要小。对事件性消息标识符的动态调整由STM32的定时器控制。

3 结束语

本文提出了一种新型基于时间触发CAN消息实时调度算法，该算法在继承了TTCAN时间触发机制优势的基础上，对其不足之处进行改进，将其用于周期性消息发送的独占窗改进为事件性消息也可调度的周期性消息窗，大大降低了事件性消息的延迟，并详细论述了调度矩阵的设计方法。此外，将动态调度思想引入TTCAN协议，对事件性消息采用LLF动态调度算法，以确保CAN总线能够适用于瞬时负载率较大的场合。