基于截止期价值度优先的CAN消息实时调度算法*

简 毅，魏 磊，杨亚联，刘其鑫

（重庆大学 机械传动国家重点实验室，重庆 400030）

基于截止期价值度优先的CAN消息实时调度算法*

简 毅，魏 磊，杨亚联，刘其鑫

（重庆大学 机械传动国家重点实验室，重庆 400030）

为了保证CAN总线网络中实时性消息的截止期，同时减小紧迫性消息的传输延迟，综合考虑了CAN网络中实时消息的截止期和价值度两个参数，提出了截止期-价值度优先（Deadline-Value First）实时调度算法，简称DVF算法。给出了算法遵循原则和设计过程，对截止期因素进行分段线性处理的方法，使得算法在保证消息截止期的前提下尽量让关键性消息优先发送。以EDF算法和HVF（higest value first）算法为基准，从关键消息的相对延迟、丢帧率和丢失价值率这三个方面对DVF算法进行性能分析，实验表明DVF算法相比于EDF算法和HVF算法有很大改善。

CAN总线网络；截止期；价值度丢失率；丢帧率；相对传输延迟

0 引言

CAN总线在混合动力汽车、船舶、工业自动化等领域得到广泛的应用。作为实时控制网络，我们总是期望CAN网络中紧迫性程度高的消息能尽可能快的传输到目标设备上，而对于其他实时周期性消息应该能够在截止期之前完成发送。CAN网络为多主网络，消息帧采用基于标识符仲裁的方式竞争总线，标识符越小的消息优先级就会越高，能够优先发送。在网络负载率较高的情况下总线上消息的碰撞频率增加，优先级低的消息将因竞争总线失败而被延迟发送，甚至错过其截止期［1］。因而CAN总线网络消息调度不仅要考虑紧迫性消息的发送延迟，还要保证实时性消息在截止期之前完成发送。采用怎样的调度策略，提高消息的调度效率，是CAN总线网络需要考虑的核心问题。

时间触发CAN协议（TTCAN协议）作为静态调度算法，对周期性消息的调度能起到很好的效果，在网络中节点数目改变时此算法显得不够灵活，而且负载率增加时，该算法调度的非周期性消息的延迟明显增加［2-3］，这对偶发性消息的实时发送是相当不利的。文献［4］证明了动态调度算法比静态调度算法具有较高的可调度性。文献［5］证明了EDF（earliest deadline first）算法可以在负载率为100%的情况下实现可靠的调度。文献［6］表明EDF算法在非过载情况下的最优性。文献［7］对CAN标识符的截止期采用指数方式编码，提高了可调度性，其实这种编码方式使得越靠近截止期的消息，其优先级提升的越快。但是EDF算法对消息帧优先级的衡量标准仅为截止期这一个参数，在一个复杂的CAN网络系统中截止期最小的消息未必是紧迫性最高的消息。CAN网络中存在系统负载率瞬间升高甚至过载的情况，而且对于一个高负载率的CAN网络而言消息的平均延迟增加，这些情况下必须确保关键性程度高的消息能够优先发送；因而，应该把消息帧的关键性程度作为度量消息优先级的参数之一。

本文提出了截止期-价值度优先调度算法（Deadline-Value first），简称DVF算法。实验表明，该算法综合性能优于EDF算法和HVF算法。该算法综合考虑了消息的截止期和价值度两个参数对消息帧的影响，其中价值度代表了消息的关键性程度。根据CAN协议，消息帧在传输过程中不被中断，因而该算法是非抢占式算法。

1 截止期-价值度优先算法

1.1 CAN标识符规划及消息帧的参数

CAN网络中不同节点的消息优先级不能相同，也就是标识符不能相同，而动态调度算法需要动态的调整消息标识符的优先级，为了调整的灵活性和避免标识符的重复，这里对标识符作如下规划：采用29位扩展标识符，其中低11位为固定部分，该部分用于CAN控制器的过滤器对消息的选择性接收，而且还要包含节点ID信息，不同的节点其ID值不相同；高18位为可变部分，用于算法对标识符的动态调整。这样截止期-价值度优先调度算法可以统一调度整个CAN网络中所有节点的消息，同时标识符固定部分由于节点ID不同而不会出现重复的情况，这样也避免了不同节点发送的消息其标识符彼此相等而冲突的情形。

此处只考虑周期实时性消息，对于任意实时性消息Mj其参数可描述为Mj=｛Tj，tja，Dj，vj｝；其中：Tj是消息的发送周期，tja是消息的到达时间；Dj是消息帧的绝对截止期；vj是消息的价值度。

一些参数的定义如下：绝对截止期是随着时间的推移而不断增加的量，其数值太大不方便计算，这里用相对截止期dr表示，dr=Dj-tja。定义消息的松弛度为dj，其大小表示为dj=Dj-tS，其中ts为系统当前时间，所以dj的范围为（0，dr）。CAN网络中每个节点单独计时而非采用统一时钟，采用定时器加标志变量的方式来表示到达时间tja、系统当前时间ts和绝对截止期Dj。

1.2 算法设计

DVF算法遵循如下原则：①保证消息满足截止期的情况下，尽量让价值度高的消息优先发送；②在消息距离其发生截止期较远时，消息的价值度对优先级的高低起主要作用，而接近截止期时消息，消息的松弛度对优先级高低起主要作用。这样价值度高的消息可以优先发送，同时保证了消息在截止期之前发送成功。而具体如何量化处理上述问题将在下面进行阐述，CAN消息的优先级与标识符绑定，设18位动态变化部分的标识符大小用pj表示，pj由截止期影响因子与价值度影响因子相乘得到：

其中φ（dj）为截止期影响因子，ρj为价值度影响因子。

1.2.1 价值度影响因子大小的确定

对任意节点S的所有消息，按照价值度从低到高依次排序，相同价值度的消息作为一组，结果为S=｛M1，（M2，M3），…，（Mi，Mi+1，…，Mj），…，Mk｝；小括号内为相同价值度的消息，其价值度依次为1、2、…、K。消息的价值度因子的大小为

其中k为价值度，即它们在集合中的顺序号。α为价值度在算法中所占的权重，根据具体应用而设定。当α≠0时，价值度越大的消息，其价值度因子越小，那么其标识符数值就越小优先级就越高。当α=0时ρj恒等于1，这时算法就演变成了EDF算法。当α取值较大时，算法就更接近于HVF算法。

1.2.2 截止期影响因子大小的确定

对于截止期影响因子φ（dj）的确定原则为分段计算，具体如下：消息的松弛度较大时，松弛度的变化对消息优先级的影响较小，而消息将要到达截止期时，松弛度的变化对消息优先级的影响增大。这里采用分段直线的方式求取截止期因子φ（dj）。设CAN标识符中留给DVF算法可以动态调整的有N位，标识符动态变化部分表示的范围为（0，2N-1）。设tfs为CAN最大帧时间，那么其值为［8］

其中0≤Sm≤8且取整数。

为了确保消息在其截止期之前发送成功，在dj= tfs时，消息优先级应该最高，这样消息将在下一次总线仲裁时发送。

实时CAN总线网络中往往存在一些紧迫性很高的偶发性消息，这样消息需要最短的响应时间，消息一旦产生就要理立即发送出去，为了满足这类消息的实时性要求，预留出m个优先级给这类偶发性消息，即0到m-1为预留优先级。那么为了确保实时性周期消息的截止期要求，在消息的松弛度dj=tfs时截止期因子φ（dj）应该等于m。

设某网络节点中有L个节点，定义转折截止期为dtr=L·tfs，这样即使在最坏的情况下所有L个节点在同一时刻都向总线上发送了消息，依然可以保证这些消息在截止期之前发送成功。设网络中所有消息的相对截止期最大值为dmax，网络中所有节点消息价值度因子的最大值为ρmax，为了不超出标识符可变部分表示的范围，令

由式（1）～式（4）得出消息Mj在松弛度为dj时可变标识符的数值p（ dj）如下：

一般CAN网络中的dmax与dtr相差较大，因而当dmax＜dj＜dtr时，φ（dj）函数曲线的斜率较小，此时DVF算法更接近于HVF算法，当dj≤dtr时φ（dj）函数曲线的斜率明显增大，此时DVF算法更接近于EDF算法，那么通过选取适当的α值得到合适的价值度因子ρj，使算法达到最好的性能。

2 实验及算法性能分析

为了衡量DVF算法的性能，我们将其与EDF算法和HVF算法进行比较，以系统消息的丢失价值率、丢帧率、关键性消息的相对传输延迟这三个参数作为标准，以此来衡量算法性能，这三个参数定义如下：

2.1 定义

定义1（丢失价值率）：网络各个节点中所有错过截止期的消息所对应的价值度与网络中所有节点发送的消息的价值度比值称为丢失价值率。丢失价值率越小的调度算法其性能越好。

定义2（丢帧率）：CAN网络中所有错过截止期的消息个数与所有节点发送的消息个数的比值称为丢帧率，丢帧率越小的调度算法其保证整个网络范围内的所有消息满足消息截止期的能力越好。

定义3（相对传输延迟）：设消息发送周期为Tj，到达时刻为taj，成功发送时刻为tsj，那么发送延迟与消息周期的比值为相对传输延迟，记作RTD；即RTD=（tsj-taj）/Tj，这样传输延迟的值就不依赖于程序运行的硬件条件，而仅仅与算法有关。相对传输延迟小的消息，其发送延迟就小，因此可以用此参数来衡量关键性程度高的消息的发送延迟。

2.2 实验条件

实验只考虑周期性实时消息的影响，其中α=1，V=7，数据帧数据域为8个字节。网络中各节点向总线上发送的消息情况都相同，任意节点发送的消息Mj都可以表示为Mj=｛Tj，dr，vj｝，Tj为周期，单位为ms，消息Mj在任意时刻的发送概率服从其各自周期上的均匀分布；dr是消息的相对截止期；vj是消息的价值度。那么各节点发送的消息情况如下：M1=｛100，100，6｝，M2=｛40，20，5｝，M3=｛40，20，4｝，M4=｛20，20，3｝，M5=｛20，20，2｝，M6=｛500，10，1｝，通过改变网络中节点个数来改变网络负载率。每种负载率下程序时间为30000·tfs，每种调度算法运行10次取其平均值。

2.3 实验结果与算法性能分析

2.3.1 丢帧率分析

图1给出了DVF算法、EDF算法、HVF算法在不同负载率下的截止期错过率的变化趋势。从图中可见，在整个负载率情况下DVF算法与EDF算法的截止期错过率相当；但是HVF即使在负载率为75%时也有6%的消息错过截止期，这是由于即使在价值度高的消息其距离截止期还很远，而低价值度的消息将要错过截止期的情况下，HVF算法依然还会先发送价值度高的消息，价值度低的消息将被延迟甚至错过截止期限。可见DVF在保证实时性消息的截止期方面，明显优于HVF算法。

图1 丢帧率比较

2.3.2 丢失价值率分析

图2给出了DVF算法、EDF算法、HVF算法在不同负载率下的丢失价值率的变化趋势。从图中可以看出在整个负载率情况下DVF算法丢失价值率最低，在非过载的情况下EDF算法的丢失价值率小于HVF算法，这是由于HVF算法在正常网络负载的情况下依然存在消息消息错过截止期，导致HVF算法的总体价值丢失偏大；在系统超载的情况下DVF算法的丢失价值率逐渐接近HVF算法，但是明显小于EDF算法。可见DVF算法在保证网络整体价值度上相对于EDF算法和HVF算法都有很大的改进。

图2 丢失价值率比较

2.3.3 关键性消息的相对传输延迟分析

图3和图4为价值度v=1和v=2关键消息的相对延迟在不同负载率下的变化趋势。从图中可见，在系统非过载的情况下，基于DVF算法的关键性消息的相对传输延迟和HVF算法基本相当，而在系统超载的情况下，其值要明显小于基于EDF算法的关键性消息相对传输延迟，但趋势线基本与其平行。

总之，EDF算法是依据消息的截止期大小进行调度，总是优先发送相对截止期最小的消息，但是EDF算法会导致关键性消的延迟增大，随着负载率的增加这种情况加剧。HVF算法只依据消息的价值度进行任务调度，而未考虑消息的截止期，可能某些将要达到截止期的消息因其价值度低而不能得到总线控制权，从而错过了截止期。而DVF算法兼顾截止期和价值度两个参数，在正常网络负载下，可以保证消息的优先级在错过截止期之前达到最高。通过合理的选择k和α的值可以使算法达到很好的性能。

图3 消息1的相对传输延迟

图4 消息2的相对传输延迟

3 结束语

研究表明，在实时CAN总线网络中应该综合考虑消息的截止期和价值度两个因素。本文提出了DVF算法，采用了分段处理的方法处理截止期因素，在消息距离截止期较远时，消息的优先级主要由价值度决定，为了保证消息不错过截止期，在接近截止期时消息的优先级高低主要由消息的松弛度决定。图2、图3和图4表明DVF算法在低负载率时接近EDF算法，在高负载率时接近HVF算法，但是综合性能均优于EDF算法和HVF算法。因此，采用DVF算法调度的CAN总线网络，在系统出现错误帧或者瞬时过载时，仍然可以保证最多的实时消息在截止期之前成功发送到总线上，而且保证了关键性消息优先发送，从而使得系统价值度收益最大。

［1］佟为明，高洪伟，陈培友.CAN总线传输延时特性研究［J］.仪器仪表学报，2007，28（4）：295-297.

［2］李佳，朱元，田光宇.CAN与TTCAN通信延迟时间的分析［J］.清华大学学报，2006，46（3）：261-265.

［3］王书举，张天侠，张国胜.汽车TTCAN实时性分析及其可视化研究［J］.汽车工程，2011，33（2）：172-175.

［4］Zuberi K M，Shin KG.Scheduling messages on controller area network for real-time CIM application［J］.IEEE Transaction on Robotics and Automation，1997，13（2）：310-314.

［5］张杰.最早截止期有限实时调度算法研究［D］.武汉：华中科技大学，2009.

［6］G Buttazzo，M Spuri，F Sensini.Va-lue vs.deadline scheduling in overload conditions［A］.Proceeding of 16thIEEE Real-Time Systems Symposium［C］.Los La-mitos，California：IEEE Computer Society 1995.

［7］王跃飞，张伟伟，严刚.CAN消息的动态调度截止期选取研究［J］.合肥工业大学学报，2010，33（5）：644-651.

［8］王俊波，胥布工.CAN报文实时性分析与在线评估［J］.控制与决策，2007，22（4）：448-452.

（编辑 李秀敏）

Real-time Scheduling Algorithm of CAN Bus Message Based on Dead line-value First

JIAN Yi，WEI Lei，YANG Ya-lian，LIU Qi-xin
（State Key Laboratory of Mechanical Transmission，Chong Qing University，Chongqing 400030，China）

In order to guarantee the deadline of real-time message in CAN network and reduce the transmission delay of Emergency messages，a real-time scheduling algorithm named DVF（Deadline-Value First）is proposed，Considered deadline and value of real-time message in CAN network.The Principle and way of the algorithm is given.By disposing the deadline element in subsection-linear method，this algorithm can send the most critical message firstly with no loss of other message's deadline.The performance of the DVF（deadline-value first）algorithms is analyzed by comparing it with EDF（earliest deadline first）algorithm and HVF（highest value first）algorithm based on value lose ratio，miss message ratio and relative transmission delay.The experiment shows that HVF algorithms can improve the performance compared to the classical EDF algorithm and HVF algorithm under all workload conditions.

CAN bus network；deadline；value lose ratio；deadline miss ratio；relative transmission delay

TH166；TG659

A

1001-2265（2015）01-0157-04 DOI：10.13462/j.cnki.mmtamt.2015.01.044

2014-04-10

国家自然科学基金：ISG速度多段耦合混合动力传动系统物理仿真及综合换挡控制策略研究（51075411）

简毅（1968—），男，重庆人，重庆大学副教授，硕士生导师，研究方向为机电系统、智能控制；通讯作者：魏磊（1987—），男，安徽人，重庆大学硕士研究生，研究方向为智能控制与计算机协同监控，（E-mail）happyhm527@163.com。