一种装甲车辆CAN总线混合调度算法

宋小庆，陈永星，赵梓旭，张 健，朱昀炤

(装甲兵工程学院控制工程系，北京100072)

CAN总线作为军用总线广泛应用于装甲车辆在数字化战场信息的传输，其采用CSMA/CD非破坏性仲裁机制按照优先级大小进行信息传输。然而在总线负载率较高、高优先级报文占用总线时，这种机制使得系统中优先级较低的报文一直处于监听总线状态而不能获取总线使用权，有时甚至可能因为多次发送不出去产生发送错误而自动退出总线，导致总线实时性较差。当有紧急消息需要传输时，可能由于该消息所在节点优先级较低，而延缓甚至退出紧急消息的发送，对车辆作战性能发挥有很大的影响。因此，对CAN总线网络上节点消息进行合理分类与调度，使各类信息实时、公平、有效地传输，对装甲车辆总线信息的传输非常重要。

目前，国内外学者在CAN总线非破坏仲裁的基础上，提出了很多CAN总线调度算法，总体上分为静态调度算法和动态调度算法2类。静态调度算法大致有3类:基于优先级的比率单调算法［1］、基于截止期的截止期单调调度算法［2］、基于时间调度表的TTCAN调度算法等。前2种算法对非周期性报文的调度效率较低，且当高优先级报文传输增多时，低优先级报文由于获取不了总线使用权而长时间处于等待状态。TTCAN虽然建立了窗口机制，根据调度表决定报文发送顺序，解决了节点不公平竞争问题，但存在调度表构建时间花销大、与CAN格式不兼容、不允许出错重发以及误帧率较大等方面的不足。动态调度算法大致有2类:最小松弛优先(Least Laxity First，LLF)算法［3］和最早截止期优先(Earliest Deadline First，EDF)算法［4］等。LLF 算法在网络负载较大时，调度过程复杂、调度效率较低;而EDF算法报文的平均等待时延较长。

本文结合当前装甲车辆网络消息特点，按照优先级分层设计、截止期实时调度、同级别公平竞争的原则，提出了一种“分级决策动态均衡”的总线调度算法，改进了当前总线调度方案的实时性与网络利用率等方面的不足。

1 CAN总线仲裁机制

CAN总线网络的仲裁机制为CSMA/CD非破坏性仲裁技术［5］。CAN总线的位中，逻辑“0”被称作显性位，逻辑“1”被称作隐性位。在总线上，当显性位和隐性位进行比较时，隐性位在竞争中退出。CAN总线数据帧结构如图1所示。

图1 报文的数据帧结构

SOF由一个显性位构成，标志着帧的开始。所有要发送帧的节点必须同步于首先发送报文节点的帧起始前沿;仲裁场由标志符和RTR位构成，仲裁场的标志符可用于总线仲裁(即优先级高低判断)，RTR位用于判断此帧是远程帧还是数据帧。

实际上采用CSMA/CD非破坏优先权逐位仲裁规则时，冲突的过程是优先权小的帧逐位淘汰，而优先权大的帧非破坏性地逐位胜出，优先权大的帧先占用总线得到发送。

2 分级决策动态均衡调度算法

目前关于CAN总线调度算法的改进，基本上都是局限于周期型消息的处理，而在实际装甲车辆上有很多报警、故障等突发消息，同类消息中不同周期也对应不同的重要程度，现有算法不能很好地处理这些消息。因此，本文采用均衡调度［6］与最早截止期调度［7］相结合的“分级决策动态均衡”的混合调度算法，按照“分层处理”原则对总线传输消息种类进行了划分，从发送需求及消息重要程度方面对信息进行权值分配，具体分级如下。

第1级:消息传输紧急性的权值分配公式为

式中:Wi为信息的紧急性，i为紧急性权值所占的位数，Wi值越小，代表消息的紧急程度越强。

第2级:同一类型但具有不同相对截止期消息的权值分配。

由于节点发送消息紧急程度、重要程度与截止期有关，节点截止期时限长度越小，节点消息越需要发送出去，对于同一类别而截止期不同的消息，可以按照截止期Di由小到大的顺序映射出节点优先级的大小，从而确定节点优先级，节点i的碰撞次数Ni为

式中:Di为节点i的截止期;tstart为节点消息需要传输时的起始时间;tFrame为单帧传输的平均时间。

对 Ni取整，记为 ni=［Ni］，则有

ni由小到大排列，n→f(i)可得到不同截止期消息的优先权映射关系，如表1所示。

表1 不同截止期消息的优先权映射关系

第3级:同一类型且具有相同相对截止期消息的权值动态分配［8］。

该级利用均衡调度算法进行消息权值分配。如当有5个初始优先级分别为50、49、48、47、46的节点都向总线发送消息时，若按照动态均衡调度算法在消息竞争过程中将各节点ID动态改变，便可将各节点消息公平有效地发送出去，各节点ID标志符动态改变过程如表2所示。

表2 各节点ID标志符动态改变过程

3 算法的实现

3．1 协议制定

以CAN 2．0B扩展帧格式为例，对装甲车辆CAN总线ID标志符进行重新定义，解决消息传输实时性、带宽分配不均带来的网络利用率不高等问题。具体定义如图2所示。

图2 改进的CAN协议扩展帧格式

根据某型装甲车辆消息种类及不同消息的不同截止期，对应分级决策动态均衡算法，可对协议进行如下划分。

1)取消息紧急度标志符为p=2来划分消息种类，实际定义为:“00”代表严重故障类等紧急消息;“01”代表控制类等实时消息;“10”代表命令、节点状态类等实时消息;“11”代表图像、声音等非实时消息。其他车型可根据实际消息类型对p取值。

2)实际装甲车辆各类消息的相对截止期有10，50，100，200，1 000 ms，共计 5 种截止期，故取截止期分级标志符为m=3对不同截止期消息的优先权值进行分配，具体优先权映射关系如表3所示。

表3 实际车辆不同截止期消息的优先权值分配

对于非实时消息，可以规定其截止期映射的优先权值为111，即取其权值为最大值7。

3)实车上同一类型、同一截止期最多有50个消息需要传输，取动态均衡算法标志符q=6来对相同截止周期消息的优先级进行动态公平分配，具体权值可按表2进行分配。

4)报文标志符取18位，可根据实际需要定义。

3．2 算法实现流程

本文提出的车辆总线信息调度方案采用均衡调度、最早截止期调度2种算法相结合的“分级决策动态均衡”的混合调度算法，既保证了系统传输信息的实时性，又合理分配了网络带宽，还减小了系统的开销成本，其算法实现流程如图3所示。

4 试验验证

4．1 试验平台

本试验平台由2部分组成:1)节点消息发送终端(共5个)，用于发送各类消息;2)上位机信息接收端，用于接收各节点终端发送的消息，同时进行相关性能参数指标的统计，其组成框架如图4所示。

图3“分级决策动态均衡”算法实现流程

图4 试验平台框架

本试验通信平台采用CAN通信总线进行数据传输，设置通信速率为10 kbit/s，从节点可设置发送消息个数，上位机接收端有5个信息接收仪表显示端，可统计计算节点在总线上的传输时延，通过对比不同节点的传输时延，即可验证“分级决策动态均衡”混合调度算法的有效性。

4．2 通信速率测试

图5为数据传输过程中示波器捕获的CAN总线信号波形。由图5可以观测出总线数据传输1 bit所用时间为100μs，即总线通信速率为10 kbit/s，与设定值一致。

图5 示波器捕获的CAN总线信号波形

4．3 算法验证对比

4．3．1 原有“固定优先级”算法验证

设定每个节点分别发送紧急程度与截止期均相同的消息组，每个消息组消息个数相同且每个消息数据字长为2B，上位机接收到不同节点的消息后，对传输时延进行统计计算。图6为每个节点发送200个消息的上位机接收记录界面，同理，设定每个节点分别发送50、100、400个消息进行测试并记录，绘出不同节点发送不同消息组的传输时延对比曲线，如图7所示。

图6 静态优先级上位机接收200个消息记录界面

图7 静态优先级CAN总线竞争时延

由图7可知:由于CAN总线CSMA/CD仲裁机制的影响，采用静态优先级算法，不管发送消息多少，优先级最高的节点1的消息优先发送，所用时间最短，而优先级最低的节点5的消息最后发送，所用时间最长，节点之间消息发送不公平。只是随着总线负载增加，各节点发送消息传输时延在同步增加。

4．3．2 “均衡调度”算法验证

采用动态优先级算法时，各节点发送消息前提条件与静态优先级算法相同。图8为每个节点发送200个消息的上位机接收记录界面，不同节点发送50、100、200、400个消息的传输时延对比如图9所示。

图8 动态优先级上位机接收200个消息记录界面

图9 动态优先级CAN总线竞争时延

由图9可知:采用动态优先级算法，各节点在发送紧急程度与截止期均相同的消息组时，由于消息ID标志符处于动态改变的过程中，即优先级由高到低循环发生变化，故各节点在总线的传输时延基本相同。

因此，相对静态优先级而言，采用动态优先级算法，各节点消息公平传输，且优先级较低的节点传输时延明显减少，提高了节点传输消息的公平性。

4．3．3 “分级决策动态均衡”混合调度算法验证

当各节点发送消息的相对截止期不同时，可利用分级决策动态均衡混合调度算法进行消息的传输。设定各节点分别传输100个2B数据字的消息，假设节点2、5传输消息的截止期相同，记为D1，节点1、3、4传输消息的截止期相同，记为D2，且D1＜D2。分别采用3种算法时各节点传输100个消息的时延对比如表4所示。

由表4可知:传输消息截止期不同时，采用固定优先级算法时，节点消息依次传输，节点5所用时延可长至5．89 s，节点4、5优先级较低，当有紧急消息传输时，会导致消息不能及时传输，实时性不高;采用均衡调度算法时，各个节点消息的传输时延约为3．5 s，几乎同时传输完毕，节点4、5消息的优先级得到提高，各节点消息公平传输;而采用混合调度算法时，由于节点2、5截止期相同且较短，优先进行消息的传输，两节点内部采用动态均衡算法传输，所用时间为1．8 s左右，节点1、3、4截止期相同但相对较长，其内部同样采用动态均衡算法，用时4．2 s左右，这样既保证了截止期较小消息的优先传送，又保证了消息传输的公平性。通过分析对比可知:相对固定优先级算法和均衡调度算法而言，分级决策动态均衡调度算法提高了节点通信网络信息的传输效率，使得各类消息公平有序地传输。

表4 3种算法传输消息时延对比

5 结论

当前装甲车辆综合电子系统消息的紧急程度、重要程度各不相同，在实车中的实时性要求也不同。本文针对某型装甲车辆的实时性要求，对CAN协议进行3层划分，提出了“分级决策动态均衡”的混合调度算法，并通过试验验证了算法的可行性，对实际装甲车辆综合电子系统信息调度算法及总线性能研究具有重要意义。

［1］ Liu C L，Layland J W．Scheduling Algorithms for Multiprogramming in a Hard-real-time Environment［J］．Journal of ACM，1973，20(1):174-189．

［2］ Zuberi K M，Shin K G．Design and Implementation of Efficient Message Scheduling for Controller Area Network［J］．IEEE Transactions on Computers，2000，49(2):182-188．

［3］ George R，Kanayama Y．A Rate-monotonic Scheduler for the Real-time Control of Autonomous Robots［C］∥IEEE International Conference on Robotics and Automation．New York，USA:IEEE，1996:2804-2809．

［4］ Pedreiras P，Almeida L．EDF Message Scheduling on Controller Area Network［J］．Computing ＆ Control Engineering Journal，2002，13(4):163-170．

［5］ 宋小庆．军用车辆综合电子系统总线网络［M］．北京:国防工业出版社，2010:120-122．

［6］ 刘向明，方建安．CAN总线网络的实时性研究和改进［J］．现代电子技术，2011，34(22):46-49．

［7］ 谌介人，彭军，吴敏，等．CAN总线中EDF调度算法的研究与改进［J］．计算机测量与控制，2008，18(16):1678-1681．

［8］ 袁远，李红信．CAN网络实时性分析及改进［J］．电子设计工程，2010，18(6):110-112．