基于FTT?CAN的电动汽车动态调度算法研究
刘应吉+王书举
摘 要： 针对在控制器局域网（CAN）总线中存在低优先级信息会因为高优先级信息频繁占用总线而出现的死锁问题，在车辆控制系统中引入柔性时间触发机制组建柔性事件触发控制器局域网（FTT?CAN），针对周期信息和随机信息，分别在FTT?CAN的同步相和异步相中采用最早截止期优先（EDF）调度和动态提升优先级（DPP）调度，介绍了FTT?CAN触发原理，提出基于EDF和DPP的动态调度算法，将该调度算法应用于典型电动汽车控制系统模型的调度，验证了该调度算法的优越性。
关键词： 控制器局域网； 柔性时间触发控制器局域网； 动态调度； 可度性分析
中图分类号： TN915.04?34；TP336 文献标识码： A 文章编号： 1004?373X（2017）23?0158?04
Abstract： The controller area network （CAN） bus has the problem that the information with low priority may be deadlocked due to the frequent bus occupation of the information with high priority. The flexible time?triggered CAN （FTT?CAN） based on flexible time?triggered mechanism is introduced into the vehicle control system. The earliest deadline first （EDF） scheduling and dynamic promotion priority （DPP） scheduling are respectively used in the synchronous phase and asynchronous phase of the FTT?CAN for the periodic information and random information. The trigger principle of FTT?CAN is introduced. The dynamic scheduling algorithms based on EDF and DPP are proposed. The proposed dynamic scheduling algorithm is used to the scheduling of the typical electric vehicle control system model. Its superiority was verified.
Keywords： controller area network； flexible time?triggered CAN； dynamic scheduling； schedulability analysis
0 引 言
CAN 总线由于其成本低、布置灵活等优点，在车辆实时控制系统中已经得到广泛应用。CAN协议基于事件触发（Event?triggered，ET）机制，该机制具有较大的信息传输延时抖动，通信不具有确定性[1?3]控制系统需要通过CAN总线传输的大部分控制信息有着实时性和安全性需求，要求信息在规定时间内完成传输，传统的CAN有时不能很好地满足系统对时间约束的要求[4]，因此，有研究在标准CAN协议基础上扩展了支持时间触发机制（Time?triggered，TT）[5?6]，基于时间触发机制的CAN高级协议能够保证周期信息传输的抖动得到有效控制[7?9]。柔性时间触发CAN（Flexible Time?triggered CAN，FTT?CAN）[10]作为CAN的扩展协议兼顾了事件触发的灵活性和时间触发机制的确定性。
本文针对FTT?CAN的特点，提出一种动态调度算法，可以有效地提高总线的利用率及信息的实时性。
1 柔性时间触发CAN原理
FTT?CAN采用同步相和异步相双相结构来控制时间触发和事件触发信息的传输，它将时间、事件触发通信有效地结合起来。FTT?CAN协议将总线时间细分成等长的连续时间单元，即基本周期EC（Elementary Cycles），每个EC开始时，由主节点发送一个EC触发消息TM（Trigger Message）给所有从节点，该消息同时包含了该EC内获准发送的时间触发信息的标识。基本周期由时间意义上的主节点发送触发信息，TM启动，到下一次触发信息出现截止。FTT?CAN的异步相用于传输事件触发信息，即随机信息，它可以在任意时刻产生发送请求，同步相则用于传输时间触发消息，即周期性信息，其发送过程与各个EC同步。FTT?CAN基本周期结构如图1所示，图中AM和SM分别表示随机性信息和周期性信息。两相之间保留空闲时间段[α，]使得不同触发属性的信息能够严格在各自相内进行传输。
FTT?CAN对时间触发信息的调度集中在主节点内，在主节点内保存了一个信息调度表，用于实现对周期性信息的集中式在线调度。图2给出了触发消息对周期信息的控制方式，由图2可以看到，通过触发消息字段就可以控制周期性信息的发送与否。触发信息数据段中的每一位都对应于一个周期信息，对应的信息可在由该触发信息开始的EC内获准发送，否则该信息不能在该EC内发送。通过对主节点内信息调度表的在线规划，动态地改变每个特定EC内的触发信息，就可以实现周期性信息的调度管理。系统中除主节点外各节点仅保留与自身有关的生产/消费表，各个节点解码接收到触发信息数据并查询本节点的生产/消费表，若查到该基本周期内有本节点所发送的信息，则同步相到来后立即申请信息发送。
2 基于FTT?CAN的动态调度算法
由于FTT?CAN协议同步相调度只需在主节点中更新调度表[11]，可实现对动态通信需求的在线接入，这为在同步相引入最早截止期优先（Earliest Deadline First， EDF）动态调度提供了可能。FTT?CAN协议异步相中沿用传统CAN的事件触发机制，可以采用动态优先级提升（Dynamic Priority Promotion，DPP）调度，随着信息仲裁失败上调该信息优先级，进而减少低优先级消息的平均响应时间，使带宽配置更均匀。
2.1 基于EDF的同步相动态调度
EDF调度可获得较高的带宽利用率[12]，因此广泛应用于实时控制系统中，但由于EDF需要实时同步计算各个节点信息的截止期，对各节点硬件的计算能力要求较高，而FTT?CAN对于周期信息的处理过程都集中在主节点内，EDF对于节点的计算要求局限于主节点，另外，主节点可以通过实时更新本地的调度表即可完成同步在线调度，其余节点只需要具有能解码EC触发信息的能力即可。因此，本文对于周期信号的动态调度采用EDF调度算法，对于任一周期信息[m，]EDF具体算法过程如图3所示。
其中，[TDm]为信息[m]的截止期限；[TBC]为一个基本周期的时长；[NS]为周期信息的个数。
2.2 基于DPP的异步相动态调度
DPP算法能够给予网络中各个信息公平的带宽，能保证网络信息的传输有时间上限，因此，DPP算法可以有效地避免网络中低优先级信息总也不能得到网络使用权的情况发生[13]。DPP算法将信息的标识符分成两个优先级域：动态优先级域和固定优先级域。对于随机信息n，以Pn?dynamic表示动态优先级，以Pn?DM表示固定优先级，以s表示优先级提升步数，DPP算法实施步骤如图4所示。
3 网络性能分析
為了评价不同调度策略对网络性能的影响，本文采用一套SAE（Society of Automotive Engineers）电动汽车网络模型为研究对象，该模型包含电池、车辆控制器、马达控制器、控制面板、驾驶员输入、刹车及传输控制7个子系统节点[8]，各系统节点之间需要处理44个信号，将其中31个随机信号记为[A1～A31，]记11个随机信号为[S1～S11，]周期信号的截止期为其周期， 随机信号的截止期依应用环境而定，参见文献[8]。将事件触发的随机信号归集记为[A，]周期信号归集为[S，]将第[n]个基本周期中传输的信号作为[S]的子集归集为[S（n）]。设置网络传输速度为250 Kb/s，基本周期TBC为 5 ms，忽略网络抖动。
分别采用本文基于FTT?CAN的调度策略和文献[8]中的DM调度策略，对比网络利用率、周期信息响应时间及随机信息可调度性等三方面的网络性能。
3.1 周期信息的响应分析
由表1可见，FTT?CAN网络中，由于随机信息被约束在异步相内传输，采用DM算法的话，随机信息的比例因子较小，表明应对更高时间要求能力较差，但是，通过引入DPP动态调度指环，整体的调度性明显得到了提高。
4 结 语
在车辆控制CAN网络中，信息传输的确定性和灵活性越来越重要，本文基于CAN高级协议，针对不同的信息特点引入对应的动态调度算法，提出一种兼顾确定性和灵活性的调度机制，以SAE电动汽车模型为应用对象，通过与传统CAN网络调度相对比，验证了本文所提机制可以实现更好的网络传输性能。
参考文献
[1] 刘超，黄伟，吴涛，等.基于等幅变频晋升CAN总线动态调度算法的研究[J].信息与控制，2015，44（4）：398?402.
[2] KUMAR M， VERMA A K， SRIVIDYA A. Distributed computing and networking [C]// Proceedings 10th ICDCN. [S.l.]： IEEE， 2009： 163?174.
[3] 李军，徐凤霞.基于CAN总线网络控制系统的混合调度算法研究[J].计算机测量与控制，2014，22（11）：3687?3690.
[4] CENA G， VALENZANO A， VITTURI S. Advances in automotive digital communications [J]. Computer standards & interfaces， 2005， 27（6）： 665?678.
[5] KOPETZ H. A comparison of CAN and TTP [J]. Annual reviews in control， 2000， 24： 177?188.
[6] LEEN G， HEFFERNAN D. TTCAN： a new time?triggered controller area network [J]. Microprocessors and microsystems， 2002， 26（2）： 77?94.
[7] XU J， DAVID L P. Priority scheduling versus pre?run?time scheduling [J]. Journal of real?time systems， 2000， 18（1）： 7?23.
[8] TINDELL K， BURNS A， WELLINGS A J. Calculating controller area network （CAN） message response times [J]. Control engineering practice， 1995， 3（8）： 1163?1169.
[9] 王书举，张天侠，张国胜.车载CAN和FTTCAN网络设计与调度策略[J].农业机械学报，2011，42（2）：14?17.
[10] 曹万科，张天侠，闻邦椿，等.柔性时间触发控制器局域网络（CAN）控制系统动态规划应用与性能分析[J].机械工程学报，2008，44（5）：142?146.
[11] PEDREIRAS P， ALMEIDA L. EDF message scheduling on controller area network [J]. Computing & control engineering journal， 2002， 13（4）： 163?170.
[12] BUTTAZZO G C. Rate monotonic vs. EDF： judgment day [J]. Real?time systems， 2005， 29（1）： 5?26.
[13] CENA G， VALENZANO A. An improved CAN ?eldbus for industrial applications [J]. IEEE transactions on industrial electronics， 1997， 44（4）： 553?564.
[14] NATALE M D. Scheduling the CAN bus with earliest deadline techniques [C]// Proceeding of the 21st IEEE Real?time Systems Symposium. Orlando： IEEE， 2000： 259?268.
摘 要： 针对在控制器局域网（CAN）总线中存在低优先级信息会因为高优先级信息频繁占用总线而出现的死锁问题，在车辆控制系统中引入柔性时间触发机制组建柔性事件触发控制器局域网（FTT?CAN），针对周期信息和随机信息，分别在FTT?CAN的同步相和异步相中采用最早截止期优先（EDF）调度和动态提升优先级（DPP）调度，介绍了FTT?CAN触发原理，提出基于EDF和DPP的动态调度算法，将该调度算法应用于典型电动汽车控制系统模型的调度，验证了该调度算法的优越性。
关键词： 控制器局域网； 柔性时间触发控制器局域网； 动态调度； 可度性分析
中图分类号： TN915.04?34；TP336 文献标识码： A 文章编号： 1004?373X（2017）23?0158?04
Abstract： The controller area network （CAN） bus has the problem that the information with low priority may be deadlocked due to the frequent bus occupation of the information with high priority. The flexible time?triggered CAN （FTT?CAN） based on flexible time?triggered mechanism is introduced into the vehicle control system. The earliest deadline first （EDF） scheduling and dynamic promotion priority （DPP） scheduling are respectively used in the synchronous phase and asynchronous phase of the FTT?CAN for the periodic information and random information. The trigger principle of FTT?CAN is introduced. The dynamic scheduling algorithms based on EDF and DPP are proposed. The proposed dynamic scheduling algorithm is used to the scheduling of the typical electric vehicle control system model. Its superiority was verified.
Keywords： controller area network； flexible time?triggered CAN； dynamic scheduling； schedulability analysis
0 引 言
CAN 总线由于其成本低、布置灵活等优点，在车辆实时控制系统中已经得到广泛应用。CAN协议基于事件触发（Event?triggered，ET）机制，该机制具有较大的信息传输延时抖动，通信不具有确定性[1?3]控制系统需要通过CAN总线传输的大部分控制信息有着实时性和安全性需求，要求信息在规定时间内完成传输，传统的CAN有时不能很好地满足系统对时间约束的要求[4]，因此，有研究在标准CAN协议基础上扩展了支持时间触发机制（Time?triggered，TT）[5?6]，基于时间触发机制的CAN高级协议能够保证周期信息传输的抖动得到有效控制[7?9]。柔性时间触发CAN（Flexible Time?triggered CAN，FTT?CAN）[10]作为CAN的扩展协议兼顾了事件触发的灵活性和时间触发机制的确定性。
本文针对FTT?CAN的特点，提出一种动态调度算法，可以有效地提高总线的利用率及信息的实时性。
1 柔性时间触发CAN原理
FTT?CAN采用同步相和异步相双相结构来控制时间触发和事件触发信息的传输，它将时间、事件触发通信有效地结合起来。FTT?CAN协议将总线时间细分成等长的连续时间单元，即基本周期EC（Elementary Cycles），每个EC开始时，由主节点发送一个EC触发消息TM（Trigger Message）给所有从节点，该消息同时包含了该EC内获准发送的时间触发信息的标识。基本周期由时间意义上的主节点发送触发信息，TM启动，到下一次触发信息出现截止。FTT?CAN的异步相用于传输事件触发信息，即随机信息，它可以在任意时刻产生发送请求，同步相则用于传输时间触发消息，即周期性信息，其发送过程与各个EC同步。FTT?CAN基本周期结构如图1所示，图中AM和SM分别表示随机性信息和周期性信息。两相之间保留空闲时间段[α，]使得不同触发属性的信息能够严格在各自相内进行传输。
FTT?CAN对时间触发信息的调度集中在主节点内，在主节点内保存了一个信息调度表，用于实现对周期性信息的集中式在线调度。图2给出了触发消息对周期信息的控制方式，由图2可以看到，通过触发消息字段就可以控制周期性信息的发送与否。触发信息数据段中的每一位都对应于一个周期信息，对应的信息可在由该触发信息开始的EC内获准发送，否则该信息不能在该EC内发送。通过对主节点内信息调度表的在线规划，动态地改变每个特定EC内的触发信息，就可以实现周期性信息的调度管理。系统中除主节点外各节点仅保留与自身有关的生产/消费表，各个节点解码接收到触发信息数据并查询本节点的生产/消费表，若查到该基本周期内有本节点所发送的信息，则同步相到来后立即申请信息发送。
2 基于FTT?CAN的动态调度算法
由于FTT?CAN协议同步相调度只需在主节点中更新调度表[11]，可实现对动态通信需求的在线接入，这为在同步相引入最早截止期优先（Earliest Deadline First， EDF）动态调度提供了可能。FTT?CAN协议异步相中沿用传统CAN的事件触发机制，可以采用动态优先级提升（Dynamic Priority Promotion，DPP）调度，随着信息仲裁失败上调该信息优先级，进而减少低优先级消息的平均响应时间，使带宽配置更均匀。
2.1 基于EDF的同步相动态调度
EDF调度可获得较高的带宽利用率[12]，因此广泛应用于实时控制系统中，但由于EDF需要实时同步计算各个节点信息的截止期，对各节点硬件的计算能力要求较高，而FTT?CAN对于周期信息的处理过程都集中在主节点内，EDF对于节点的计算要求局限于主节点，另外，主节点可以通过实时更新本地的调度表即可完成同步在线调度，其余节点只需要具有能解码EC触发信息的能力即可。因此，本文对于周期信号的动态调度采用EDF调度算法，对于任一周期信息[m，]EDF具体算法过程如图3所示。
其中，[TDm]为信息[m]的截止期限；[TBC]为一个基本周期的时长；[NS]为周期信息的个数。
2.2 基于DPP的异步相动态调度
DPP算法能够给予网络中各个信息公平的带宽，能保证网络信息的传输有时间上限，因此，DPP算法可以有效地避免网络中低优先级信息总也不能得到网络使用权的情况发生[13]。DPP算法将信息的标识符分成两个优先级域：动态优先级域和固定优先级域。对于随机信息n，以Pn?dynamic表示动态优先级，以Pn?DM表示固定优先级，以s表示优先级提升步数，DPP算法实施步骤如图4所示。
3 网络性能分析
為了评价不同调度策略对网络性能的影响，本文采用一套SAE（Society of Automotive Engineers）电动汽车网络模型为研究对象，该模型包含电池、车辆控制器、马达控制器、控制面板、驾驶员输入、刹车及传输控制7个子系统节点[8]，各系统节点之间需要处理44个信号，将其中31个随机信号记为[A1～A31，]记11个随机信号为[S1～S11，]周期信号的截止期为其周期， 随机信号的截止期依应用环境而定，参见文献[8]。将事件触发的随机信号归集记为[A，]周期信号归集为[S，]将第[n]个基本周期中传输的信号作为[S]的子集归集为[S（n）]。设置网络传输速度为250 Kb/s，基本周期TBC为 5 ms，忽略网络抖动。
分别采用本文基于FTT?CAN的调度策略和文献[8]中的DM调度策略，对比网络利用率、周期信息响应时间及随机信息可调度性等三方面的网络性能。
3.1 周期信息的响应分析
由表1可见，FTT?CAN网络中，由于随机信息被约束在异步相内传输，采用DM算法的话，随机信息的比例因子较小，表明应对更高时间要求能力较差，但是，通过引入DPP动态调度指环，整体的调度性明显得到了提高。
4 结 语
在车辆控制CAN网络中，信息传输的确定性和灵活性越来越重要，本文基于CAN高级协议，针对不同的信息特点引入对应的动态调度算法，提出一种兼顾确定性和灵活性的调度机制，以SAE电动汽车模型为应用对象，通过与传统CAN网络调度相对比，验证了本文所提机制可以实现更好的网络传输性能。
参考文献
[1] 刘超，黄伟，吴涛，等.基于等幅变频晋升CAN总线动态调度算法的研究[J].信息与控制，2015，44（4）：398?402.
[2] KUMAR M， VERMA A K， SRIVIDYA A. Distributed computing and networking [C]// Proceedings 10th ICDCN. [S.l.]： IEEE， 2009： 163?174.
[3] 李军，徐凤霞.基于CAN总线网络控制系统的混合调度算法研究[J].计算机测量与控制，2014，22（11）：3687?3690.
[4] CENA G， VALENZANO A， VITTURI S. Advances in automotive digital communications [J]. Computer standards & interfaces， 2005， 27（6）： 665?678.
[5] KOPETZ H. A comparison of CAN and TTP [J]. Annual reviews in control， 2000， 24： 177?188.
[6] LEEN G， HEFFERNAN D. TTCAN： a new time?triggered controller area network [J]. Microprocessors and microsystems， 2002， 26（2）： 77?94.
[7] XU J， DAVID L P. Priority scheduling versus pre?run?time scheduling [J]. Journal of real?time systems， 2000， 18（1）： 7?23.
[8] TINDELL K， BURNS A， WELLINGS A J. Calculating controller area network （CAN） message response times [J]. Control engineering practice， 1995， 3（8）： 1163?1169.
[9] 王书举，张天侠，张国胜.车载CAN和FTTCAN网络设计与调度策略[J].农业机械学报，2011，42（2）：14?17.
[10] 曹万科，张天侠，闻邦椿，等.柔性时间触发控制器局域网络（CAN）控制系统动态规划应用与性能分析[J].机械工程学报，2008，44（5）：142?146.
[11] PEDREIRAS P， ALMEIDA L. EDF message scheduling on controller area network [J]. Computing & control engineering journal， 2002， 13（4）： 163?170.
[12] BUTTAZZO G C. Rate monotonic vs. EDF： judgment day [J]. Real?time systems， 2005， 29（1）： 5?26.
[13] CENA G， VALENZANO A. An improved CAN ?eldbus for industrial applications [J]. IEEE transactions on industrial electronics， 1997， 44（4）： 553?564.
[14] NATALE M D. Scheduling the CAN bus with earliest deadline techniques [C]// Proceeding of the 21st IEEE Real?time Systems Symposium. Orlando： IEEE， 2000： 259?268.
