2. 中国联通江西省分公司, 江西 南昌 330045
2. China Unicom Jiangxi Branch, Nanchang 330045, China
1 引言
20世纪80年代初以基于事件触发多主方式工作的CAN总线由于结构简单、可重构、可靠性高、成本低、抗干扰强、响应快等特点，已成为分布式工业控制网络的首选[1, 2, 3, 4]. CAN的MAC层协议采用CSMA/CD非破坏性逐位仲裁规则实现对媒体的访问[2, 5, 6, 7]，由于比较位数多和仲裁时延长，使得网络利用率不高(有时只有20％)，且带宽低(最大带宽只有1 Mb/s)，容易造成死锁. 而CAN协议采用的静态优先权分配策略[2, 5, 6, 7]，由于传输介质分配不公、实时性较差，因而容易造成阻塞. 因此，减少逐位比较位数，改进CAN协议的调度算法，以更好地满足消息传输的不同需求，一直是CAN总线研究的热点.
目前，针对CAN总线事件触发静态调度算法的实时性问题，提出基于事件触发的动态调度算法如最早截止期优先调度算法等和基于时间触发的静态调度算法如TTCAN(time-triggered controller area network)算法等. 但这些算法存在适应性有限、调度算法较复杂和优先权更新频率较高等问题[2, 8, 9, 10, 11]. 因此，针对非破坏性逐位仲裁规则的网络利用率不高的问题，通常采用帧标识域分段编码的方法. 虽然域段的定义多种多样、各有千秋，但一般采用标识域的高位来表示节点地址，且不同节点同种报文的实时性相当，使得不同节点的同种报文获取网络传输权的公平性欠佳[12, 13, 14]. 因此，从标识域分段编码和降低动态调度算法复杂性出发，以改善网络利用率、传输实时性和使用公平性为目的，依据优先权动态晋升机制，提出基于分段编码等幅变频晋升(segmented edcoding such amplitude and variable frequency promotion，SSVP)的动态调度算法.
2 动态调度算法的设计基础 2.1 动态调度算法的基本要求调度是指对数据包传输的先后次序及间隔等实施控制，在网络带宽有限的情况下，合理分配带宽资源，提高网络利用率，满足不同数据包的传输需要(如实时性、公平性等)[2, 10]. CAN总线动态调度算法的基本要求有：
(1) 算法操作应与CAN协议兼容，否则难以在现有的硬件平台上实现.
(2) 逐位比较的平均二进制位数应尽量少，算法应尽可能简单，否则仲裁与算法实现的时延长且开销大.
(3) 在截止期内，报文优先级应达到最高，以保证报文可调度.
(4) 不同报文优先级应尽可能不同，以避免报文传输时发生碰撞.
2.2 优先级晋升及其晋升函数优先级晋升[13, 15]是节点根据报文特性、报文在网络传输中的时间等参数以及原有优先权，以一定的时间间隔更新报文的优先权. 优先权的大小决定调度的优先次序，即所有等待发送报文发送的先后次序. 在CAN协议中，优先权越小，优先级越高[1]. 优先权表达式可表示为
优先级晋升速度取决于优先权的更新幅度和更新频率[13, 15]. 更新幅度由晋升函数控制，决定优先级的变化特性. 若晋升函数f(X1，…，XQ)j=0，则Pij=P0j为常数(P0j为j报文初始优先权)，优先级不变，即为静态调度. 若晋升函数f(X1，…，XQ)j≠0，则优先级可变，即为动态调度. 且当f(X1，…，XQ)j为常数时，则为等幅动态调度；当f(X1，…，XQ)j为变数时，则为变幅动态调度. 对于动态调度，变幅有利于满足报文的可调度性和降低更新频率，但与等幅动态调度相比，实现困难，算法开销大.
优先权更新频率与网络传输速率成反比，与负载成正比，决定优先级变化的快慢[13, 15]. 若更新周期大于截止期，则优先权不变，即为静态调度；若更新周期小于截止期，则优先权可变，即为动态调度. 且当更新频率为常数时，则为等频动态调度；当更新频率为变数时，则为变频动态调度. 对于动态调度，若更新频率高，则晋升开销大；若更新频率小，则晋升性弱. 可见，动态优先级调度算法的关键在于优先权晋升函数及其更新幅度与更新频率.
3 报文帧标识域与晋升函数定义 3.1 报文帧标识域定义为兼容CAN总线应用，在不改变CAN帧格式的前提下，将报文帧标识域(CAN 2.0A为11位，CAN 2.0B为29位)分为3个或3个以上字段，如图 1所示[1]. 标识域的高A位是固定不变的报文类别Type字段，且A不能太大，取2为宜，否则通过分段编码来减少逐位比较的平均二进制位数将被削弱. 而由CAN协议的仲裁规则可知，类别编码值越小，优先级越高. 标识域低C位是固定不变的其它功能FuncID字段，可包含节点地址、报文特性等多个子字段.
 |
| 图 1 报文帧标识域字段的划分Fig. 1 Segmentation of message frame identifier field |
标识域中间B位是可变的类内优先权Inter字段，其编码由优先权Pij决定. 因此，存储于节点发送缓冲区的报文，经过分类和类内优先权排队，形成一个有序的虚拟全局队列. 若报文类别的编码为00、01、10，HP00、HP01、HP10分别为报文类别00、01、10的虚拟子队列的队头指针，RP00、RP01、RP10为其相应队尾指针，则节点中等待发送报文的全局虚拟队列如图 2所示.
 |
| 图 2 等待发送报文的全局虚拟队列Fig. 2 Global virtual queue waiting for sending messages |
从优先级晋升机制来看，传输实时性体现在报文发送的松弛度越小，晋升速度越快；使用公平性体现在报文等待发送时间越长，晋升速度越快；网络利用率体现在优先权更新开销小.
根据报文发送松弛度定义有[16]：
对于非破坏性逐位仲裁规则，优先权二进制编码高位为0的数位越多，优先级越高. 为减小晋升开销，可通过优先权编码右移高位补0更新优先权来提高报文优先级. 类内优先权更新定义为
从晋升函数式可知，若右移w位，则晋升幅度为2w. 显然，右移位数越多，晋升幅度越大，出现相同优先权的概率越大. 因此，若右移位数取最小值1，则晋升幅度为最小值2.
若报文以晋升幅度2等幅更新时，由于CAN协议的最高优先级为全0，类内优先权更新次数最大为B次. 若所有报文以碰撞即更新方式等频更新，对于Kjmax>B的报文，在Kj>B时的更新是无效的. 为减小晋升开销，采用变频更新，对于Kjmax>B的报文，更新周期取[Kjmax/B」，即每隔[Kjmax/B」次碰撞更新一次；对于Kjmax≤B的报文，更新周期为1，即每次碰撞均更新. 由此，晋升权的取值为
若类内优先权初始编码为全1，即优先级最低，则采用等幅变频更新策略. 对于Kjmax≥B的报文，在截止期内，类内优先权更新B次，即可使其编码为全0；但对于Kjmax<B的报文，在截止期内，类内优先权更新次数最多仅为Kjmax次，不可能使其编码为全0. 因此，对于Kjmax<B的报文，设定类内优先权初始编码的低Kjmax位为1，其余高位为0，通过Kjmax次更新，亦可使其编码为全0.
4.2 报文优先级动态调度算法(1) 建立报文属性表. 所有节点建立一张报文特性表，表的大小为节点中属性不同的报文数，用于记录固定不变的A位Type字段与C位FuncID字段的编码、更新周期T和最大碰撞避退次数Kjmax. 且当Kjmax≤B时，T=1；当Kjmax>B时，T=└Kjmax/B」.
(2) 新报文帧标识域的填充与插入全局虚拟队列. 当产生一个新报文帧时，将报文属性表中A位Type字段与C位FuncID字段的编码拷贝到新报文帧标识域的对应字段；当T=1时，置B位Inter字段的低Kjmax位为1，其余高位为0；当T>1时，置B位Inter字段为全1. 使碰撞次数变量Kj为0，并按类内优先权越小越靠近队首和类内优先权相同报文先产生在前的原则，将新报文帧插入到全局虚拟队列相应的优先级类子队列中.
(3) 检查是否发送队首报文. 节点侦听总线，若总线空闲，则按非破坏性优先级逐位仲裁规则，取全局虚拟队列中位于队首报文的帧标识域以CSMA方式访问发送；否则继续(2).
(4) 队首报文除标识域的其它域继续发送和队列中报文位置移动. 若没有碰撞，或发生碰撞且优先级仲裁胜出，则继续发送全局虚拟队列除标识域的其它域的队首报文；队首报文成功发送后，全局虚拟队列中的所有报文向队首方向移动一个位置，转(2).
(5) 队首报文除标识域的其它域停止发送和优先权更新. 若发生碰撞且优先级竞争失败，则停止发送全局虚拟队列除标识域的其它域的队首报文，碰撞避退次数变量Kj加1；若队首报文发送失败，当T=1或T>1且[Kj/T」=Kj/T时，队首报文标识域的Inter字段右移一位高位补0，转(2).
5 SSVP动态调度算法性能分析及仿真实验 5.1 报文可调度性分析对于CAN总线动态调度算法，报文可调度的充分条件是在截止期内报文优先级可达最高，必要条件是在截止期内得到响应[14, 17].
SSVP动态调度算法在碰撞次数Kj≤Kjmax时，通过类内优先权初始编码和更新周期的设定，类内优先权编码可达全0，即类内优先级可达最高，满足充分条件. 虽然报文优先级不一定最高，但恰好说明重要度高的类报文可得到及时发送，满足其必要条件. 只有在重要度高的类报文的充分条件与必要条件都满足的前提下，才能满足重要度低的类报文的充分条件.
设CAN总线上有M个节点，在所有节点等待发送报文的全局虚拟队列为空时，M个节点同时产生新报文帧. 一般若满足[13, 14, 17]：
CAN总线优先级动态调度算法的报文通信时延一般满足[14, 18, 19, 20]：
报文帧建立入队的任务包括报文标识域初始化(Ti)、帧组装(Ta)和加入全局虚拟队列(Tl)等，SSVP调度算法的报文帧组装与其它调度算法无异(即Ta相同). SSVP调度算法的标识域初始化需要比较读取报文属性表中信息并加以分析编码，加入全局虚拟队列需要按段查询插入操作，显然比其它调度算法复杂，报文标识域初始化和加入全局虚拟队列增加的时间分别设为ΔTi和ΔTl.
仲裁更新的任务包括标识域编码比较(Tc)、优先权编码更新(Tu)与报文在全局虚拟队列中的位置调整(Tm)等. SSVP调度算法的标识域编码与其它调度算法一样(即Tc相同). 由于SSVP调度算法在报文帧建立入队时已按优先级排序，且优先权更新是正向晋升至最高，位于全局虚拟队列中的队首报文优先级最高，在碰撞退让优先权更新后，优先级仍为最高，仍位于队首，即无需调整位置(即Tm为0). SSVP调度算法的优先权编码更新仅是移位，标识域分段编码可有效地减少逐位比较的二进制位数，若二进制位数减少节约的时间用于更新移位，则可不考虑优先权编码更新(即Tu为0).
报文帧建立入队是一次性的，仲裁更新具有重复性，设重复次数为R，若满足：
采用OPNET网络仿真软件，建立8个节点的网络仿真模型，并参照SJA1000标准波特率表设定节点CAN_TX和CAN_RX及CAN_Link的波特率均为800 kbit/s，选择全局统计变量为网络利用率(端到端最大时延/报文周期)和收发帧数. 帧格式为40 bit CAN 2.0A数据帧的变形，数据域16位，标识域分为2、4、5(其中3位为目的地址)3个字段. 若网络每秒分别发送1 k、2 k、3 k、…、20 k帧报文，则网络负载率分别为0.05、0.10、0.15、…、1.00，且每隔10 s改变网络负载率. 对比CAN静态调度和SSVP动态调度，它们均能可靠地实现报文帧传输，网络利用率与网络负载率的关系如图 3所示.
 |
| 图 3 网络利用率与负载率之间的关系Fig. 3 The relationship between network utilization and load rate |
当网络负载率不大时，由于传输速率足够快，使得全局虚拟队列中等待发送的报文少，大多数报文可快速发送，故网络利用率与调度算法无关. 从仿真实验结果可知，当网络负载率小于0.3时，CAN静态调度与SSVP动态调度的网络利用率是相当的. 随着网络负载率的增大，全局虚拟队列中等待发送的报文增加，发送报文的调度成为影响通信时延的重要因素. 从仿真实验结果可知，当网络负载率为1.0时，SSVP动态调度的网络利用率比CAN静态调度高出0.16. 如果不是最优调度，任何调度算法的网络利用率都存在网络负载率瓶颈，只是大小不同，即不同的调度算法，通过网络调度算法提高网络负载率的范围不同. 从仿真实验结果可知，当网络负载率大于0.80时，SSVP动态调度的网络利用率趋于平稳；而CAN静态调度在网络负载率大于0.60时，网络利用率则趋于平稳. 因此，SSVP动态调度的网络负载率瓶颈比CAN静态调度高出0.2，适应性强.
6 结论保证报文传输的实时性和公平性是网络控制的基本要求，提高网络利用率是增强控制网络性能的基本途径. 针对CAN总线静态优先级调度的局限性，依据优先权动态晋升机制，定义可满足实时性和公平性的晋升函数，建立具有可调度性和报文通信时延短的SSVP调度算法. 仿真实验结果表明SSVP调度算法可靠有效，且网络资源利用率高，可在实际中推广应用.
| [1] | 夏继强, 邢春香. 现场总线工业控制网络技术[M]. 北京: 北京航空航天大学出版社, 2005. Xia J Q, Xing C X. Field bus industrial control network technology[M]. Beijing: Beijing University of Aeronautics and Astronautics Press, 2005. |
| [2] | 陈丹丹, 夏立, 王海峰. CAN总线调度算法研究综述[J]. 湖南工业大学学报, 2007, 21(5): 51-54. Chen D D, Xia L, Wang H F. Overview on scheduling algorithms of CAN[J]. Journal of Hunan University of Technology, 2007, 21(5): 51-54. |
| [3] | 杨捷, 姚晓东, 郑海珍. CAN总线中非周期信息的随机动态优先级调度[J]. 电子技术应用, 2007, 33(2): 18-20. Yang J, Yao X D, Zheng H Z. Dynamic priority scheduling of aperiodic message on CAN[J]. Application of Electronic Technique, 2007, 33(2): 18-20. |
| [4] | 鲍官军, 计时鸣, 张利, 等. CAN总线技术、系统实现及发展趋势[J]. 浙江工业大学学报, 2003, 31(1): 58-61. Bao G J, Ji S M, Zhang L, et al. CAN fieldbus technology, system realization and its developing direction[J]. Journal of Zhejiang University of Technology, 2003, 31(1): 58-61. |
| [5] | 薛雷. CAN总线的动态优先权分配机制与非实时数据的传输[J]. 计算机工程与应用, 1999, 45(12): 33-35. Xue L. The dynamic priority assigning mechanism and non-RT data CAN field-bus[J]. Computer Engineering and Applications, 1999, 45(12): 33-35. |
| [6] | 吴涛. 基于CAN总线工业测控通信系统的研究[D]. 南昌: 江西师范大学, 2011. Wu T. The research of industrial measurement and communication system base on CAN bus[D]. Nanchang: Jiangxi Normal University, 2011. |
| [7] | 贾国光. 工业控制系统中基于CAN总线的实时动态调度研究[D]. 长沙: 湖南大学, 2008. Jia G G. The research on real-time dynamic scheduling based on CAN in industry control systems[D]. Changsha: Hunan University, 2008. |
| [8] | Liu C L, Layland J W. Scheduling algorithms for multiprogramming in a hard-real-time environment[J]. Journal of ACM, 1973, 20(1): 46-61. |
| [9] | Leen G, Heffernan D. TTCAN: A new time-triggered controller area network[J]. Microprocessors and Microsystems, 2002, 26(2): 77-94. |
| [10] | 刘鲁源, 李芳, 吕伟杰. TTCAN协议的分析与展望[J]. 天津理工大学学报, 2005, 21(3): 15-19. Liu L Y, Li F, Lv W J. Analysis and prospect of TTCAN protocol[J]. Journal of Tianjin University of Technology, 2005, 21(3): 15-19. |
| [11] | Pedreiras P, Almeida L. EDF message scheduling on controller area network[J]. Computing & Control Engineering Journal, 2002, 13(4): 163-170. |
| [12] | 辉亚男, 冷文浩, 刘培林. CAN总线应用层通信协议的设计与实现[J]. 计算机工程与设计, 2008, 29(3): 669-671. Hui Y N, Leng W H, Liu P L. Design and implementation of application layer communication protocol for CAN bus network[J]. Computer Engineering and Design, 2008, 29(3): 669-671. |
| [13] | 王黎明, 邵英, 单勇. CAN总线动态调度算法改进研究[J]. 计算技术与自动化, 2008, 27(1): 65-69. Wang L M, Shao Y, Shan Y. The research of improving dynamic scheduling algorithm based on CAN bus[J]. Computing Technology and Automation, 2008, 27(1): 65-69. |
| [14] | 李斌. 基于CAN总线网络控制系统的调度算法的分析与研究[D]. 天津: 天津大学, 2003. Li B. Analysis and research of the scheduling algorithm of networked control system based on CAN fieldbus[D]. Tianjin: Tianjin University, 2003. |
| [15] | 吕伟杰, 刘鲁源, 王毅新. 基于CAN的动态优先级提升算法及实现[J]. 计算机技术, 2005, 32(4): 30-32. Lv W J, Liu L Y, Wang Y X. Algorithm and implementation of dynamics priority promotion based on CAN bus[J]. Computing Technology, 2005, 32(4): 30-32. |
| [16] | Fuster S, Rodriguez F, Bonastre A. Software-based EDF message scheduling on CAN networks[C]//Proceedings of the Second International Conference on Embedded Software and Systems. Piscataway, NJ, USA: IEEE, 2005: 450-455. |
| [17] | 董寅康. 基于CAN总线的调度算法的研究[D]. 北京: 清华大学, 2011. Dong Y K. Investigation of scheduling algorithm base on control area network[D]. Beijing: Tsinghua University, 2011. |
| [18] | 颜碧云, 魏叶华. 基于CAN总线的共享时钟混合调度算法[J]. 计算机工程与应用, 2014, 50(4): 69-72. Yan B Y. Wei Y H. Shared-clock hybrid scheduling algorithm based on CAN[J]. Computer Engineering and Applications, 2014, 50(4): 69-72. |
| [19] | 王毅新. 基于CAN总线的静态调度算法及其实验系统的研究[D]. 天津: 天津大学, 2004. Wang Y X. Static scheduling algorithm and experiment system based on CAN bus[D]. Tianjin: Tianjin University, 2004. |
| [20] | Hasnaoui S, Kallel O, Kbaier R, et al. An implementation of a proposed modification of CAN protocol on CAN fieldbus controller component for supporting a dynamic priority policy[C]//Proceedings of the 38th IAS Annual Meeting of the Industry-Applications-Society. Piscataway, NJ, USA: IEEE, 2003: 23-31. |