CAN网络层次化动态调度策略设计与实现

邵椿与，李晓娟，史涤霏，张笑搏，王 瑞，关 永

1(首都师范大学 信息工程学院 高可靠嵌入式系统技术北京市工程研究中心 电子系统可靠性重点实验室，北京 100048)

2(首都师范大学 燕都学院，北京 100048)

1 引 言

控制器局域网CAN(Controller Area Network)最初是Bosch公司在发展汽车技术的过程中提出来的，汽车系统中存在由多个主机组成的局部网络，为了简化网络内部电子设备之间的交流问题，提出了CAN总线通信协议[1].一般CAN总线上会挂载多个节点，且节点之间互相独立，当节点需要发送消息时，访问总线成功进而允许信息传输.而在访问过程中，存在多个节点同时访问的情况，造成消息碰撞，CAN总线对节点按位仲裁算法，高优先级节点访问总线并传输信息，低优先级节点继续侦听总线状态以等待下次发送[2].这种仲裁方式导致在传输过程中，CAN总线上高优先级节点数据传输往往能得到保证.但对于低优先级的节点来说，由于总线竞争失败而导致数据无法传输的概率，会随着节点数目的增多而逐渐增大.除此之外，CAN总线最初为了解决实时系统中的问题而设计，因此总线上的周期或非周期消息都需要在规定时间内完成，低优先级节点长时间未能传输消息而造成消息丢失，从而对整体CAN通信过程造成影响.

因此为了解决饥饿问题，CAN总线优先级调度的问题研究逐渐成为趋势，出于对实时性要求的考虑，首先提出单调速率(RM)算法[3]，按照消息周期大小进行排序，周期越小优先级越高.一旦消息优先级被分配，其顺序固定不变，因此也被称为静态优先级算法.静态优先级算法的优点是优先级固定，产生可预测的调度和可靠的可调度性分析，但是静态优先级算法导致较低的总线利用率.于是为了提高总线利用率，已经提出了诸如最早截止期优先(EDF)[4，5]的动态优先级算法.在EDF调度CAN消息中，根据消息的相对截止期判断优先级的大小，相对截止期越小的消息优先级越高，这种方式需要在每轮仲裁实时更新消息的相对截止期，EDF调度算法提高了总线利用率，相对于静态优先级算法也更有利于遏止饥饿现象.除了经典的EDF算法，后续又提出了其他动态调度算法.袁熹[6]等人提出了基于AF值(总线访问频率)的动态调度算法，此算法将AF值作为节点优先级动态变化的标准，根据AF值大小动态变化优先级.文献[7]针对当前汽车使用中受到攻击的防御系统和在不同场景下的系统漏洞，提出了动态仲裁ID分配算法，在不改变CAN协议的情况下提高了车辆内安全.文献[8]提出了一种通过减少消息的总响应时间和平均响应时间来减少饥饿策略，因为CAN总线采用位仲裁，通过在每一轮仲裁中增加隐性消息优先级的方式，减少总响应时间又提高了消息优先级.

根据对前人工作的研究可知，对于CAN总线动态调度算法的研究已经比较充分，且动态调度算法在实时性方面调度效果较好.但是当CAN总线上节点增多时，动态调度算法导致每个节点的处理开销也增大，随着时间的推移，系统的绝对截止期也越来越大，造成消息传输的实时性反而下降.除此之外，目前算法在单条总线上节点调度策略比较成熟，但在实际工作场景中，多条CAN总线集成在一个系统.且若单条总线挂载节点数目过多，系统极易发生拥塞情况.在研究中发现文献[9]提出了一种描述和评估层次结构实时总线调度策略的工具，基于不同特性指定仲裁级别.文献[10]提出了一种在异构环境下，针对有向无环图(DAG)的基于优先队列划分的调度算法，首先根据节点数量划分优先对列数，然后根据任务开销划分任务队列，最后将节点分配给合适的队列，以达到提高调度效率的目的.文献[11]提出GETF算法，在已有ETF算法基础上增加了分组函数，将相似消息集合，然后根据分组结构分配给不同的机器，在每组机器中再使用ETF算法，增加了全局分组的思想.类似地，文献[12]将管理时间触发流量的消息调度表分层为低级和高级两层，高级调度表处理平台间消息触发，低级调度处理本地消息触发，以此减少通信消耗.文献[13]则是对层次结构的网格资源调度算法进行优化，根据网格资源调度类型的特点对网格层次结构进行分析和划分，以改进网格层次结构.文献[14]提出的分层调度策略则是针对33种类型消息而提出的分层调度结构，每层调度采用不同的调度策略.3种消息在端口过滤，将消息分段到适合其调度策略的层次，以此达到分层目的，减少消息最坏响应时间.

受上述分层调度思想的启发，本文结合CAN总线特性，提出基于多条CAN总线的层次化动态调度算法，该算法将多条总线优先级仲裁分为两层，分为单条总线本地优先级仲裁和系统全局优先级仲裁，最终得到全局优先级最高节点，既保持了动态调度算法的性能、保障了实时性，又增加了系统节点数量.并用Stateflow工具实现此调度算法建模.

2 相关工作

2.1 动态调度算法介绍

目前已经有很多动态调度算法被提出，最经典的是最早截止期优先算法(Earliest Deadline First).如图1所示，EDF调度方法将截止期di(t)平均分为n个区域，通过计算消息的相对截止期来决定消息优先级，即：

di(t)-t

(1)

公式(1)为t时刻该任务的截止期，比较各个消息节点的相对截止期，进行降序排序.例如图1中，当系统运行时间为t1时，当前截止期的大小在截止期编号为2的区域内，因此此时消息i的优先级为2;当系统运行时间为t2时，当前截止期的大小在截止期编号为n-1的区域内，因此此时消息i的优先级为n-1.最后，比较各节点消息的优先级大小，执行最高优先级的消息节点.相对截止期算法EDF是比较经典的动态优先级调度策略，但当负载过大时，系统调度花费过大，导致系统性能极度下降.

图1 相对截止期划分示意图

袁熹等人提出了基于AF值(总线访问频率)的动态调度算法，基于节点访问频率(AF，Access Frequency)动态优先级调度算法的思想[6]是：一条CAN总线上所有节点具有初始化优先级，在通讯过程中，每个节点的AF值被实时记录.随着总线仲裁的进行，根据每个节点的AF值来动态调整其优先级，而且每个节点的AF值也是动态变化的.当AF值低的节点被高优先级任务长时间阻塞时，AF值就会下降，下降至阈值Fth(Frequency Threshold)范围时，说明此节点长时间访问失败，就会提高消息优先级以增大获得总线仲裁的机会以免饥饿现象发生.

对第i个节点的AF值定义如公式(2)：

(2)

其中Si为节点i访问总线成功次数，n为节点总数.

基于AF值的动态调度算法具有灵活性高、实时性好的特点，有效提高了低优先级节点的访问频率，均衡了各节点的访问成功频率.但也存在当节点过多时系统发生拥堵的缺点.

2.2 基于Stateflow建模CAN总线

Stateflow集成于Matlab中的Simulink，其动作主要表达方式是状态跃迁图，Stateflow基于有限状态机理论对状态图、流程图的创建，对事件驱动系统进行建模和仿真，所以它的行为转换通过状态跃迁完成[15]，实现对CAN总线通信模型建模及调度算法研究.因其可视性强，在仿真中可以看到模型状态跃迁过程、故障出现位置及利用遍历性测试故障原因，以降低实际应用中开发难度，减少工作量[16].在前人工作中，已有研究利用Stateflow模拟CAN总线通信过程，文献[17]模拟了在起重机环境下CAN总线的Stateflow模型，得到利用状态流模拟CAN总线是可行的，并且由于Stateflow的特性，其状态流变化过程透明可视，便于分析信息传输过程.Cao[18]等利用Stateflow建立了依据CAN总线通信协议的通信模型，设计了不同的CAN总线通信负载率，以研究其对平均信息时延、网络利用率等数据的影响.

但前人对于Stateflow建立CAN总线调度算法都在单条CAN总线上模拟，对于多条CAN总线建模方面研究较少.

3 层次化动态调度算法

本节中，我们首先会介绍层次化动态调度算法，如何在多条CAN总线中实现两级仲裁及仲裁过程，其次展示如何利用状态机迁移方式在Stateflow中根据CAN总线原理实现层次化动态调度算法.

3.1 算法描述

把节点分配在多条CAN总线中集成于一个CAN网络，需要确定存在于一个系统中的多条CAN总线如何进行仲裁传输.两级调度策略如下：

1)首先确定CAN网络中的CAN总线数目，根据CAN总线传输信息的重要性和实时性综合考虑对其进行排序，总线顺序随重要程度而提前，对所有CAN总线均进行编号，设为bus[1]，bus[2]，bus[3]，…，bus[n];

2)每条CAN总线利用单条CAN总线动态调度算法仲裁得到本条总线优先级最高的节点，并记录此节点的数据信息，每条总线上优先级最高的节点分别定义local_priority[1]，local_priority[2]，…，local_priority[n]，此时完成一级仲裁；

3)单条总线仲裁完成后，从local_priority[1～n]中再进行优先级比较，选出其中优先级最高的节点，胜出的则为全局优先级最高的节点，定义为global_priority，利用公式(3)可得，此节点进行数据传输，最终实现两级仲裁.如图2所示，为两级仲裁调度示意图.

global_priority=max(local_priority[1]，…，local_priority[n])

(3)

为了更直观地说明本算法的调度过程，用算法1说明，CAN系统中的节点即为算法输入，输出结果为global_priority.假设CAN网络中有n条CAN总线，每条总线上挂载m个节点.系统中n条CAN总线并行运行.每条总线上的节点均有初始优先级，一级调度采用动态优先级调度算法，节点优先级也随着系统运行不断变化，因此在每轮一级调度中如算法1所示，依次比较单条总线上每个节点的优先级，仲裁出本条总线m个节点中优先级最高的节点作为本条总线的local_priority，分别决策出local_priority[1～n].完成本轮仲裁一级调度.在算法1层次化调度中16行表示比较二级调度过程，即用公式(3)得到global_priority，本轮仲裁成功传输的节点即global_priority.算法1描述了系统中一轮优先级仲裁的过程，而在规定运行时间内仲裁不断发生，除了第1轮仲裁节点优先级遵循设定的初始优先级，后续每轮仲裁中节点的优先级，依据动态调度算法中其优先级评价指标而动态改变.如图2中所示，当本轮仲裁结束，global_priority节点成功传输.传输完成的结果会影响并改变系统内节点优先级数据，即每轮仲裁中的算法输入即bus[n]_node[m]，其优先级数据由上一轮仲裁及节点运行结果而得到，再继续重复算法1中第2～第16行仲裁得出local_priority和global_priority的过程，实现迭代过程，因而一级仲裁得到的local_priority[1～n]和二级仲裁得到的global_priority在每轮仲裁中也动态发生变化.

图2 层次化调度示意图

算法1.CAN总线层次化调度1.bus[n]_node[m] 初始化:2.for i=1 to n do3.local_priority[i]=04.end for5.global_priority=0 计算:6.for i=1 to n7. for j=1 to m-1 do8. if bus[i]_node[j]≥bus[i]_node[j+1] then9. local_priority[i]= bus[i]_node[j]10. else local_priority[i]= bus[i]_node[j+1]11. j=j+112. end if13. end for14. i=i+115.end for16.global_priority=max(local_priority[1 to n])

3.2 模型构建

3.2.1 算法实现步骤

将CAN总线的原理与Stateflow建结合并实现层次化动态调度算法，需要实现以下步骤：

•根据CAN总线的实时性要求和每个节点的截止时间周期，需要一个时钟作为全局变量来控制传输步骤中的时间.

•将CAN总线的收发过程抽象为具体模块，设计了节点模块、总线模块和竞争功能模块，且每条总线都是并行运行，须将节点模块设计为并行状态.

•根据各模块的功能和算法的运行过程，结合层次化动态调度算法，设计状态转移条件、状态执行步骤和函数计算算法.

3.2.2 节点模块

节点状态跃迁过程如图3所示，每个节点模块由send、buffer、period_data_put这3部分组成，其中period_data_put是数据输入部分，此数据由Stateflow环境输入，在此模块被组装成数据帧.buffer模块是节点的缓冲区，此模块包括两个状态：null和nonnull.数据被采集并组装成数据帧后，状态由null跃迁到nonnull，将节点信息存放在等待发送的buffer中，发送完成后，返回null状态，等待下一次触发.

图3 节点状态跃迁图

send模块代表节点发送部分，初始节点处于sleep状态，代表此时没有信息需要传输.为了便于统计每个节点的状态，用变量n代表节点状态结果，例如图3中n1[0]则代表第一条总线上第一个节点的状态结果，初始n1[0]=0，表示节点处于睡眠状态；P规定为节点初始优先级数据大小.当buffer区有数据被采集进来后，由sleep状态跃迁到wait状态，此时n1[0]=1，表明节点处于等待发送信息状态.若此节点在本轮仲裁中竞争成功，则跃迁到transmission状态，n1[0]变为2，否则继续处于wait状态，等待下一轮仲裁.当数据帧发送完成后，回到sleep状态.图3可以看到，在send模块中，若本节点传输信息成功，当回到sleep模块后，P值也随之回归初始值，若仲裁失败，则P=P+1，所以随着每轮竞争仲裁，P值也是不断变化的，因此每轮优先级也是动态变化的.

为了保证传输实时性，本实验在全局模型中设置了一个全局时钟，定义为time，通过记录到达状态的时间，可以计算得知节点传递信息所用时间，例如图3中，t0[0]=time、t1[0]=time和t2[0]=time记录到达此状态的时间，以便设定节点运行周期，计算节点运行时间等.

3.2.3 仲裁过程模块

在Stateflow中，总线模块和节点模块是并行状态，两者之间通过全局变量实现数据传输，完成层次化动态调度的二级仲裁；图4是总线状态跃迁图，以系统中有3条CAN总线为例，由图4可知，总线最初在idle状态，在此状态中计算得到每条总线的最高优先级节点，即bus_max_num=max(P)，bus_max_num为上文3.1节提到的local_priority，因此P值越大伴随着竞争成功的可能性越高，如上节提到，当低优先级节点连续竞争失败时，P值不断增加大，以此增大竞争成功的可能性直到完成一次成功传输，缓解了低优先级饥饿现象.

图4 总线状态跃迁图

此时完成一级调度；随后在idle状态跃迁过程中计算，由图4可知，第i条总线上的local_priority[i]须大于剩余其他总线上的local_priority则竞争成功，成为global_priority.

此时两级调度已经完成.开始传输竞争成功的节点数据帧.利用compete函数(如图5所示)，通过逐一比较global_priority节点所在总线上各待发节点的优先级而实现“线与”功能，符合CAN总线仲裁机制，将发送权给优先级最高的节点，此时跃迁到busy状态进行数据传出，当数据传输完成后，由busy状态跃迁到space状态，为帧间间隔，随后总线模块返回idle状态，等待下一轮传输.

图5 竞争函数

4 实验与结果分析

4.1 实验条件

基于总线使用环境，CANopen协议更适用于工业应用CAN总线，更具有广泛性，因此基于此协议将总线比特率设为125Kbit/s，设定系统运行时间为50s.

为了比较层次化动态调度算法与已有算法的调度效果，在本实验中，设定单条总线EDF动态算法、单条总线基于AF值的动态调度算法、层次化动态调度算法进行比较，单条总线上均搭载10个节点，为了控制节点数目一致，层次化动态调度算法中CAN网络建立2条CAN总线，每个总线上挂载5个节点.

针对缓解低优先级节点饥饿现象问题，因此利用节点访问成功率作为反映算法性能的指标.

节点访问成功率：

(4)

其中bi为总线第i个节点发送成功的报文数目，pi为第i个节点请求发送的报文数目.

4.2 结果与分析

在相同周期、总线比特率、运行时间条件下，本文将3种算法的节点访问成功率进行比较.

从图6中也可看出基于AF值的动态调度算法针对饥饿现象问题优于EDF算法，因此在本实验中将层次化动态调度算法中一级仲裁算法采用基于AF值的动态调度算法.由图6可以看出层次化动态调度算法在保持了原有节点优先级顺序的基础上，相较于在单条总线上的EDF调度算法，提高了低优先级节点的访问成功率，提高程度至少大于20%；而且层次化动态调度算法在保持了节点初始优先级顺序的基础上使得各优先级节点访问成功率趋于稳定，提高了低优先级节点的访问成功率，缓解了饥饿现象.但从中也可得到，低优先级访问成功率提高的代价是部分高优先级节点访问成功率的降低，这在实际中是无法避免的.

图6 不同算法节点访问成功率

本文继续探究当节点数目增多时的算法调度结果.为了模拟工业现场总线节点数量庞大的工作情况，于是设计了带有3条CAN总线的CAN网络，且每条总线负载10个节点，仍旧在一级仲裁处采用基于AF值的动态调度算法，数据设定同于上个实验.

从图7可以看出，当总线和节点数目增多时，由于调度复杂，整个系统的节点访问成功率都会下降，此时高优先级节点与低优先级节点访问成功率接近，可以看出能有效缓解饥饿现象；除此之外，通过将节点分配在不同总线上，层次化动态调度方法能大幅度增加节点数目，有效缓解了系统运行资源紧张的问题.因此可知，层次化动态调度算法在处理低优先级节点饥饿问题和增加挂载节点数目效果较好.

图7 3条总线节点访问成功率

5 总结与展望

本文通过对前人CAN总线动态调度算法和层次化调度思想的研究，提出CAN总线层次化动态调度算法，将搭载多条CAN总线的CAN网络优先级仲裁分为单条总线本地优先级仲裁和全局仲裁，实现层次化调度.而且在Stateflow中实现了此算法，实验表明，层次化方法能增加CAN网络节点数目，并且有效缓解低优先级节点饥饿问题.

该算法对于高优先级节点来说，能保持其高位性，但会让渡一部分优先性给低优先级节点，因此未来研究拟开展如何在保持高优先级节点的性质上与缓解低优先级节点饥饿问题上做到能基于实际工业环境标准的平衡.