基于CAN FD 总线的动静态调度算法研究

赵雅文，周美娇，吴俊鹏

（上海理工大学光电信息与计算机工程学院，上海 200093）

0 引言

目前国内外主流调度算法大致分为3 种：①静态调度算法，如固定优先级算法（Fixed Priority Schedule Algorithm，FPA）［5］；②动态调度算法，如最早截止期优先算法（Earli⁃est-Deadline-First，EDF）［6］和最小松弛优先算 法（Least-Laxity-First，LLF）［7］；③混合调度算法（Mixed Traffic Sched⁃uler，MTS）［8］。根据报文调度过程中的不同要求，可选择合适的算法进行调度。

以上文献中关于报文响应时间的研究为本文分析CAN FD 报文的最坏响应时间奠定了一定基础，但均未将具体的调度算法应用到CAN FD 总线网络中进行验证，以对比不同调度算法的优劣。本文采用固定优先级算法和最早截止期优先算法对CAN FD 总线报文进行调度研究，通过CANoe 仿真平台搭建仿真模型，对两种算法进行仿真对比实验。实验结果表明，最早截止期优先算法对报文的优先级分配更加灵活，在低速传输情况下，报文可以实现全部传输。

1 CAN FD 总线概述

1.1 CAN FD 总线协议

CAN FD 总线是一种基于CAN2.0 协议，且与CAN 共享物理层的现场总线，遵循ISO/OSI 网络标准模型。其弥补了CAN 总线通信速率低的缺点，同时具有基于事件触发、采用短帧格式、遵循非破坏性逐位仲裁规则等特点。CAN FD 总线采用载波监听多路访问/冲突避免（Carrier Sense Multiple Access with Collision Avoidance，CSMA/CA）的媒体访问方式，还可以设置多种拓扑结构，目前在汽车行业应用最多的是总线型拓扑结构。

CAN FD 总线具有3 种报文帧格式，即数据帧、出错帧和超载帧，按照标识符长度又可分为标准帧和扩展帧。CAN FD 数据帧相较于CAN 数据帧新增了扩展数据长度位（EDL 位）、比特率开关位（BRS 位）和错误状态指示位（ESI位），同时采用了新的DLC 编码方式与CRC 算法（CRC 场可扩展至17、21、26 位）。CAN FD 总线以非常高的安全水平支持分布式实时控制，在新一代汽车应用中发挥着重要作用［9］。本文基于具有29 位标识符的扩展数据帧进行研究，CAN FD 扩展数据帧格式如图1 所示。

Fig.1 CAN FD extends data frames图1 CAN FD 扩展数据帧

1.2 帧编码

不归零（No Return Zero，NRZ）是目前使用较为广泛的一种编码方式，CAN FD 总线便是采用该种编码方式。此外，为避免总线连续接收到相同的比特位而造成收发双方无法同步，在NRZ 编码时会使用位填充方法对帧起始与CRC 分隔符之间进行编码，即当发送的比特流中有连续5位极性相同的比特位出现时，便会在第5 位后插入1 个极性相反的填充进行界定，以预防突发错误，保证接收方有足够时间进行同步。

CAN FD 总线在CRC 序列中采用新的位填充规则［10］，即在固定位置插入填充位。具体填充方法为：首先在CRC序列第1 位之前的固定位置填充1 位，然后在CRC 序列每4位后插入1 个填充位，填充位的极性与前1 位相反。接收器在接收到比特流时，应主动将填充位从比特流中丢弃以进行CRC 校验。如果填充位具有与其前1 位相同的极性，则应检测出填充错误。CAN FD 总线中CRC 序列的固定填充位数等于CAN 总线所产生的最大填充位数。

1.3 标识符编码

在总线通信过程中，需要对报文标识符进行编码设计以保证CAN FD 总线通信的实时性，该步骤是应用层协议与应用系统设计的重要内容之一。报文标识符的作用主要体现在两方面：一是在接收时过滤报文，二是定义报文分配优先级，用于总线竞争。CAN FD 报文标识符的编码设计需遵循以下原则［11］：①每个报文的标识符是唯一的；②预留的节点设备应能满足总线上的最大节点个数，报文空间也要能容纳相应节点内的报文个数；③编码方式应简单实用；④编码后的标识符能够与应用层协议相兼容；⑤优先级越高的报文标识符值越小；⑥遵从CAN2.0A 和CAN2.0B 规范，7 个最高位必须不能全都是1。

本文研究对象是具有29 位标识符的扩展CAN FD 数据帧，分别对扩展帧的高11 位以及低18 位进行编码配置（见图2），具体方案设计如下：

基于对亚洲航线邮轮通关相关的现状分析、政策及制度总结、模型构建以及归纳整理，给出以下七点我国航线邮轮运营便利化建议如下：

Fig.2 CAN FD identifier encoding图2 CAN FD 标识符编码

首先，对可变优先级的高11 位标识符进行配置。预留最高两位标识符用于判断报文类型，同时要满足高7 位不能全为1 的设计规则。本文假设00 表示强实时报文，01 表示弱实时报文，10 表示非实时报文。第26 至18 位用于表示报文的优先级提升段，根据报文的截止时间采用动态编码方式进行配置。

其次，标识符的第17 至13 位用于表示节点号，第12 至9 位用于表示报文号，余下6 位用于表示目的地址，最后3位作为保留位，至此完成标识符编码。

1.4 最坏响应时间

由于多个节点的存在，单路CAN FD 总线在报文传输过程中遇到节点同时访问总线时，会不可避免地发生冲突。此时报文传输需要根据自身优先级竞争总线，获得总线使用权，因此会导致报文延迟传送。CAN FD 总线的报文传输延时主要受4 个方面影响：报文帧、控制器、软件与媒体访问［12］。由于控制器和软件造成的延时微乎其微，可以不用在报文响应时间中体现，因此本文主要分析帧延时与媒体访问延时。

帧延时即报文的传输延迟，是一种由信息串行化导致的延时，时延长度由帧长度和总线传输速率决定，其中帧延时=帧长度/波特率［13］。这种延时在传输少量报文时对报文的最坏响应时间影响最大。媒体访问延时分为两种情况，一是总线在使用中且仍要被占用的时间，另一种是总线被高优先级报文占用，低优先级报文等待释放的时间，即排队延迟。

对于扩展帧格式的CAN FD 报文，其最坏情况响应时间主要针对传输时遇到位填充的场景。最坏情况下即按照位填充的规则，每4 位后填充1 位，直至CRC 分隔符。长度为p 个字节的报文帧的最坏响应时间为：

其中，τcan为CAN 总线的位传输速率，τfd为CAN FD 总线的位传输速率。

2 FPS 调度与EDF调度

固定优先级调度算法（Fixed Priority Scheduling，FPS）由静态调度算法演变而来［14］，是总线调度时经常用到的一种算法。该算法根据报文周期或截止期，在报文调度前分配好优先级，保证按照优先级进行调度。应用较多的固定优先级算法为单调速率算法（Rate Monotonic Scheduling，RMS）［15］和截止期单调算法（Deadline Monotonic Schedul⁃ing，DMS）［16］两种，具有额外开销小和实现简单的优点，但存在对事件触发的报文处理不灵活、容错能力差的缺点［17］。

最早截止期优先调度算法（Earliest-Deadline-First，EDF）根据报文的绝对截止时间动态分配优先级，绝对截止时间越小则分配优先级越高，该算法目前较为常用［18］。EDF 调度算法在报文调度时能实时计算报文优先级，满足系统对信息传递的实时性要求。

EDF 是一种动态抢占式调度算法［19］，其报文优先级计算方式是对报文截止时间进行编码，采用不同编码方式得出的计算结果会有所不同，通常采用以下平均分区编码方式。

对于一组报文{m1,m2,m3,…,mn}，假设它们的相对截止时间从小到大依次排列为{d1,d2,d3,…,dmax}，以报文的最大相对截止时间dmax为上限将时间轴均分成k段，则每段区间长为dmax/k。平均分区情况如图3 所示。

Fig.3 Schematic diagram of mean zoning图3 平均分区示意图

3 实验仿真

3.1 仿真模型

本文采用实验对比分析CAN FD 网络在FPS 算法和EDF 算法下的调度效果。通过CANoe 软件搭建CAN FD 网络模型［20］，由4 个节点组成，分别为电池管理节点（BCM）、网关节点（Gateway）、仪表节点（IPC）以及开关节点（Switch），均在1 条CAN FD 总线上，具体如图4 所示。

Fig.4 CAN FD system network planning图4 CAN FD 系统网络规划

各个节点根据功能不同共传递15 个报文。电池管理节点包含3 个电池状态报文，均为周期性报文。网关节点包含前后左右车门状态4 个报文以及车灯、车速2 个周期性报文。仪表节点包含引擎转速、温度、油量以及引擎错误状态4 个周期性报文。在仿真周期性报文时只考虑其最坏相应传输时间，开关节点只收发开和关2 个非周期性报文。所有周期性报文数据长度均设置为8 字节，非周期性报文数据长度为1 字节。具体报文参数如表1 所示。

3.2 实验结果

根据报文参数构造仿真数据库中的报文与信号，编写CAPL（CAN Access Programming Language）脚本，在传输速率为250Kbit/s 和500Kbit/s 的情况下分别进行仿真实验。FPS 算法下报文实际传输结果如表2 所示，EDF 算法下报文实际传输结果如表3 所示。

从表2、表3 结果可以看出，当采用FPS 算法进行调度时，Vehicle 类报文由于事先分配的报文优先级较低，在优先级仲裁获取总线访问权时一直失败，无法占用CAN FD总线，最终导致发送失败，错过报文截止期。而当采用EDF调度算法时，所有报文都可以被合理地安排优先级，可占用总线且均能在截止期前正确发出，满足了报文的实时性要求。电池管理节点与仪表节点报文传送结果与实时显示如图5 所示，网关节点与开关节点报文传送结果如图6所示。

Table 1 Message parameters表1 报文参数单位：ms

Table 2 Message transmission results of FPS algorithm表2 FPS 算法下报文传输结果

Table 3 Message transmission results of EDF algorithm表3 EDF 算法下报文传输结果

Fig.5 Message scheduling results of BCM and IPC图5 电池管理节点与仪表节点报文调度结果

Fig.6 Message scheduling results of Gateway and Switch图6 网关节点与开关节点报文结果

由图中可知，在CAN FD 总线系统中，相较于静态调度算法FPS，采用动态调度算法EDF 进行调度时灵活性更高，能够使报文在截止期前发出，保证报文传送实时性。

4 结语

本文以CAN FD 总线传输理论为基础，分析了报文传输时的最坏响应时间。通过CANoe 仿真平台，分别对FPS算法和EDF 算法在波特率为250Kbit/s 和500Kbit/s 的情况下进行多次仿真实验。结果显示，采用FPS 算法时15 个报文最佳情况下只能正常传送8 个（53%），而采用EDF 算法可以确保15 个报文100%传输。相较于FPS 算法，EDF 算法在报文优先级分配时更加灵活有效，能够避免因错过报文截止期而无法进行调度的情况。此外，CAN FD 总线因具有数据传输速率快、总线利用率高等优点，非常适合当今智能汽车产业需传输大量信号的要求。然而，本文仿真实验是建立在比较理想的条件上，缺乏硬件节点的实际验证，今后需加深该方面研究。