郝 刚

（煤炭科学研究总院沈阳研究院，沈阳 113001）

1 引言

CAN（Controller Area Network）总线因其低成本、抗干扰等优点已广泛应用于工业自动化领域，国内2005年开始将CAN应用于刨煤机组监控网络，当前采用的固定优先级调度机制存在传输不可预知、低优先级信息易死锁等不足，为了保证信息实时性，CAN实时系统中总线利用率只能达到30%左右。随着CAN应用的不断加深及刨煤机组分布式实时系统中相互连接器件的日渐增多，系统要交换的数据逐步增加，现有的带宽资源越显有限。动态优先级实时调度策略如LLF、EDF（Earliest Deadline First），相比静态调度具有较高的资源利用率，保证时间最紧迫的任务赢得资源，可提高低优先级信息网络竞争能力，使得网络实时信息有较好的时间响应特性[1]。目前，基于CAN的动态调度已成为应用研究中的热点[1-6]。

在CAN总线中实施基于信息时间约束的动态优先级调度面临以下困难：①总线消息时间约束差别较大，且随着时间越来越大，需要越来越多的CAN标识符位来编码信息的截止期，难以用有限的标识符实现；②需要网络中节点之间有严格的时间同步机制。为解决以上问题，文献[2,3]采用主节点调度形式来实现动态调度。文献[5,6]提出的EDF调度，在保证时间同步的基础上，将时间分为若干的小段时间域，根据消息截止期所落的域不同来决定优先级，每隔一段时间（如文献[5]中1ms）更新消息优先级。

本文以信息的松弛时间（除去自身传输用时之外距离信息截止期限的时间）为参数，通过将信息的松弛量化为可传输帧数，用有限的CAN帧标识符位实现信息的时间约束编码，信息参与总线仲裁时更新其松弛优先级，充分利用了CAN总线固有的仲裁机制。

2 CAN及LLF调度算法

2.1 LLF调度中CAN信息优先级规划

CAN有两种不同的帧格式，分别为含有11位标识符的标准帧和含有29位标识符的扩展帧，本文采用扩展帧格式。

记信息m的优先级为PmR，各个信号的优先级由控制优先级Pm-C、松弛优先级Pm-S和截止期单调（DM）优先级Pm-DM共同决定，如图1所示。

图1 LLF调度中优先级规划

CAN总线采用“线与”逻辑来仲裁信息竞争，所以信息标识符越小则优先级越高，总线仲裁从帧起始位开始逐位向后对比进行仲裁。控制优先级为0、松弛优先级越小的信息优先级越高，松弛优先级相同时则根据DM固定优先级仲裁。

LLF调度的核心是动态更新松弛优先级，为实现动态优先级调度，将信息优先级规划分4个步骤：

（1）考虑松弛优先级的动态提升，在29位标识符中除Pm-C位之外的28位中，将前WS位规划为松弛优先级域，松弛优先级用来动态记录信息的剩余松弛，到达其截止期前还可以经历多少次仲裁；将WDM位规划为DM优先级域，DM优先级按信息截止期分配，截止期越小优先级越高，各信息具有总线上唯一的DM优先级。DM优先级属于固定优先级，用于接收滤波以及当两信息松弛优先级相同时予以区分。仲裁域结构规划如图2所示。

图2 LLF调度中CAN帧仲裁域结构

（2）确定用于将信息松弛量化为剩余仲裁数的量化帧的大小。考虑位填充及传输过程中附加的3位帧间空间，其大小应满足公式（1）[7]。

q为量化帧的大小，tCm为系统所有信息的总线最长传输用时，fbaud为波特率，dm为扩展信息帧数据域的字节数。

（3）确定松弛优先级域的位数WS和DM优先级域的位数WDM。

其中，Q为所调度信息的个数。

（4）初始化优先级域

当松弛优先级位数能够满足信息松弛编码要求时，置控制优先级Pm-C＝0，否则Pm-C＝1，通过将控制优先级置1将不能编码的消息挂起，随着信息的松弛不断减少，当满足编码要求时，再置Pm-C＝0，即

其中，tDm为信息m的相对截止期，即当前时刻到信息截止期之间的时间，tJm为软件的抖动时间。

2.2 基于事件触发的LLF动态调度算法

LLF算法思想在于为每个信号引入随总线仲裁动态更新其松弛优先级概念，每次信息竞争总线失掉仲裁，松弛优先级会动态提升，本文定义每次提升步长为1，基于事件触发的LLF算法步骤如下：

（1）选择波特率。

（2）信息产生，初始化信息优先级Pm。

（3）Pm＝concat( Pm-C,Pm-S,Pm-DM)。

（4）监听总线，总线空闲则申请发送。

（5）if 赢得总线仲裁。

开始传输数据，完成后返回第二步；

else if Pm-DM＞1

Pm-DM＝Pm-DM-1，返回第三步。

（6）结束。

2.3 LLF调度算法的可调度性分析

根据上述算法原理进行信息传输的可调度性分析。当所有信息同时竞争总线是总线的最坏传输条件，信息m在最坏传输条件下的传输时间称为最糟糕响应时间tRm。信息m的传输时间特性满足式（6）、（7），则该信息可调度

U为总线利用率，Ti为信息的传输周期（随机信息为最小时间间隔），tWm为信息m从申请发送到获得总线使用权所等待的时间，TDm为信息m的截止期，τbit为总线传输一位数据占用时间。

3 实例分析

3.1 自动刨煤机组监控系统

自动刨煤机组监控系统由刨煤系统、输送系统、破碎系统、支护系统、冷却与除尘系统、中央控制室、控制系统、视频监控系统、和设备列车组成，各子系统之间通过CAN总线连接组建网络。

本文以机组监控系统中33个实时信号a1～a33为调度对象，每个信号携带2个字节控制数据，a1～a5、a6～a30、a31～a33周期分别为100ms、200ms、300ms 100ms，为了满足实时性要求，网络信息的传输截止期限应不大于信息周期，取刨煤机组CAN网络位速率为125kbps。

为了体现采用固定优先级调度时，新产生的高优先级信息（松弛较大）将阻碍排队等待的低优先级信息（临近其截止期、松弛很小）的情况，本文做以下假设：a1～a5、a8～a22、a31～a33由t=0开始周期发送，a6～a7、a23～a30在t=70m s时开始发送。

3.2 调度算法在刨煤机组监控系统中的应用

采用DM固定优先级调度方案和本文提出的LLF动态优先级调度方案对33个信息一个周期循环600ms共111个信息进行调度设计。

（1）基于DM算法的信息调度设计

传统设计通常采用DM截止期单调算法对CAN传输信息进行优先级分配P，任务以信息的截止期大小排序被赋予不同的固定优先级。截止期越小的任务获得的优先级越高。采用DM调度方法的优先级规划结果如表1所示。

表1 自动刨煤机组信息集DM及LLF调度设计

（2）基于LLF算法的信息调度设计

考虑现场因素取软件抖动tJm＝1ms，fbaud＝125kb/s，则q＝0.76ms，WDM＝6位，WS＝22位，信息松弛初始值为

需要松弛优先级位数为8位，则可实现信息松弛编码，即Pm-C＝0，LLF调度中优先级规划结果如表1所示。

3.3 刨煤机组监控系统的网络性能分析

为了对网络的可调度性、资源效率进行分析，本文采用以下总线特性参数：

（1）信息组丢失死限信息个数。

（2）总线利用率。

在总线信息参数不变的情况下，通过调节波特率来模拟总线利用率的变化，编程分别对DM、LLF算法进行仿真，得到两种算法调度下的CAN总线网络性能分析结果如图3所示。

由仿真知，DM调度下丢失死限的信息均为低优先级信息。由图3可见，同样的负载条件下LLF调度丢失死限的信息个数明显少于DM调度，LLF算法总线利用率比DM提高了24%。

图3 刨煤机组信息集DM与LLF调度结果

4 结论

本文提出了基于事件触发的LLF调度策略，不需要各节点附加的的时间同步机制，充分利用了CAN协议的非破坏性仲裁机制。对自动刨煤机组控制信息调度结果表明：LLF算法可达到较高的总线利用率，有效解决了低优先级信息的死锁问题，兼顾了低优先级信息的公平性。

[1] Giorgio C Buttazzo, “Rate monotonic vs EDF:judgment day,” Real-Time Systems, 2005,29(1):5-26.

[2] Margull U, Diederichs C, Margull U, et al, “An application based EDF scheduler for osek/vdx,”Proceedings of the conference on Design, automation and test in Europe, Munich, Germany, 2008:1045-1050.

[3] Pedreiras P, A lmeida L, “EDF message scheduling on controller area network,” Computing & Control Engineering Journal, 2002,13(4):163-170.

[4] Fuster S, Rodríguez F, Bonastre A, “Software based EDF Message Scheduling on CAN Networks,”Proceedings of the Second International Conference on Embedded Software and Systems, Washington DC,USA, 2005:450-455.

[5] K. M. Zuberi, K. G. Shin, “Non-preemptive scheduling of messages on controller area network for real-time control applications,” in proc.Real-Time Technology and Applications Symposium,1995:240-249.

[6] Natale M D. Scheduling the CAN bus with earliest deadline techniques. Proc of the 21st IEEE Real time System s Sym posium, Orlando, 2000: 259-268.

[7] Tindell K, Burns A, Wellings AJ, “Calculating controller area network (can) message response times,”Control Engineering Practice, 1995,3(8):1163-1169.

[8] 16 bit Single-Chip Micro cont rollers-C167CR User’s manual, V3.3. Siemens AG, Munich, 2005.