最早截止期优先算法在CAN FD网络中的改进

doi:10.16180/j.cnki.issn1007-7820.2023.02.005

摘要/Abstract

摘要：

针对应用于CAN FD网络中的调度算法,平均分区编码方式的最早截止期算法对报文进行非抢占调度时,其对大范围的截止期编码能力有限,报文易出现较大概率优先级反转以及总线负载较高等问题。通过分析造成报文传递延迟的各种原因并结合之前相关分区调度算法的不足,文中提出了基于指数-幂函数分区的最早截止期优先算法对报文进行调度的改进方式,即在对报文的截止期进行指数分区的基础上,进一步采用幂函数分区细分。文中对该算法的可调度性进行了分析,并使用CANoe进行了仿真验证。实验表明,与现有的平均分区调度算法相比,改进后的算法扩大了截止期的表示范围,降低了总线负载,优化了优先级反转问题,达到了更好的调度效果。

关键词: CAN FD, 车载网络, 最早截止期优先算法, 可调度性, 总线负载, 幂函数分区, 指数-幂函数分区, 优先级反转

Abstract:

For the scheduling algorithm applied in CAN FD network, when the earliest deadline algorithm of average partition coding method performs non-preemptively scheduling on messages, it will have the problems of limited encoding ability for a large range of deadlines, high probability of priority reversal of messages and high bus load. By analyzing various causes that cause of message transmission delay and combining with the shortcomings of previous partition scheduling algorithms, this study proposes an improved method of message scheduling based on the earliest deadline first algorithm based on exponential-power function partition, that is, on the basis of exponential partition of message deadline, power function partition subdivision is further adopted. In this study, the schedulability of the algorithm is analyzed and verified by simulation using CANoe. Experiments show that compared with the existing average partition scheduling algorithm, the improved algorithm expands the representation range of deadline, reduces bus load, optimizes priority inversion problem, and achieves better scheduling effect.

Key words: CAN FD, internet of vehicles, the early deadline first algorithm, schedulability, bus load, power function partitioning, exponential-power function partitioning, priority reversal

中图分类号:

TP273

管银凤,张凤登,张海涛,张宇辉. 最早截止期优先算法在CAN FD网络中的改进[J]. 电子科技, 2023, 36(2): 29-36.

GUAN Yinfeng,ZHANG Fengdeng,ZHANG Haitao,ZHANG Yuhui. Improvement of Earliest Deadline First Algorithm in CAN FD Bus[J]. Electronic Science and Technology, 2023, 36(2): 29-36.

图/表 9

图1

图2

图3

表1

图4

表2

表3

图5

图6

参考文献 23

[1]	刘士宝, 何烈炎, 孙小雨, 等. CAN FD通信信号质量分析和测试方法的研究[J]. 汽车实用技术, 2021, 46(10):99-102.
	Liu Shibao, He Liyan, Sun Xiaoyu, et al. The research of CAN FD communication signal quality analysis and testing method[J]. Automobile Applied Technology, 2021, 46(10): 99-102.
[2]	单祥茹. 汽车智能化将CAN FD推到前台, TI SBC 产品将其效能最大化[J]. 中国电子商情(基础电子), 2019(7): 12-13.
	Shan Xiangru. Automotive intelligence pushes CAN FD to the foreground, and TI SBC product maximizes its efficiency[J]. China Electronic Market, 2019(7):12-13.
[3]	周琦. 汽车CAN FD总线应用研究[D]. 上海: 上海工程技术大学, 2020.
	Zhou Qi. Application and research of CAN FD bus in vehicles[D]. Shanghai: Shanghai University of Engineering Technology, 2020.
[4]	郑志超, 南金瑞, 南江峰. 车载网络CAN FD总线的应用前景和技术研究[J]. 现代电子技术, 2021, 44(1):5-9.
	Zheng Zhichao, Nan Jinrui, Nan Jiangfeng. Research on application prospect and technology of CAN FD bus of vehicle network[J]. Modern Electronics Technology, 2021, 44(1):5-9.
[5]	汪晓翔, 马琪. CAN总线控制器IP设计[J]. 电子科技, 2018, 31(10):29-32.
	Wang Xiaoxiang, Ma Qi. Design of CAN bus controller IP[J]. Electronic Science and Technology, 2018, 31(10):29-32.
[6]	程小珊. 基于CAN-CANFD网络的网关实时性研究与分析[D]. 重庆: 重庆邮电大学, 2019.
	Cheng Xiaoshan. Real-time study and analysis of gateway based on CAN-CAN FD network[D]. Chongqing: Chongqing University of Posts and Telecommunications, 2019.
[7]	蔡一杰, 杜峰, 胡乐媛, 等. CAN总线调度算法研究[J]. 装备制造技术, 2020(10):15-19.
	Cai Yijie, Du Feng, Hu Leyuan, et al. Research on CAN bus scheduling algorithm[J]. Equipment Manufacturing Technology, 2020(10):15-19.
[8]	胡继浩. 基于CAN总线的纯电动汽车整车控制器节点的设计与研究[D]. 长沙: 湖南大学, 2018.
	Hu Jihao. The design and research of electric vehicle controller node based on CAN bus[D]. Changsha: Hunan University, 2018.
[9]	马天凤. 电动汽车CAN总线协议调度算法的研究[D]. 沈阳: 辽宁大学, 2017.
	Ma Tianfeng. Research of electric vehicle's scheduling algorithmbased on CAN bus protocol[D]. Shenyang: Liaoning University, 2017.
[10]	常智. 基于CAN总线在车辆通讯协议中的研究和应用[D]. 太原: 中北大学, 2019.
	Chang Zhi. Research and application of vehicle communication protocol based on CAN bus[D]. Taiyuan: North University of China, 2019.
[11]	袁暋, 檀明, 周晶晶. EDF调度算法可调度性分析方法的改进研究[J]. 计算机应用研究, 2013, 30(8):2429-2431.
	Yuan Min, Tan Ming, Zhou Jingjing. Research on improved schedulability analyzing method for tasks scheduled under EDF[J]. Application Research of Computers, 2013, 30(8):2429-2431.
[12]	Kim C, Cho H, Sung Y. Optimising earliest deadline first scheduling for parallel real-time tasks on multiprocessors[J]. Electronics Letters, 2019, 55(25):1343-1345. doi: 10.1049/el.2019.3017
[13]	Kalaivani C, Kalaiarasi N. Earliest deadline first scheduling technique for different networks in network control system[J]. Neural Computing and Applications, 2019, 31(1):223-232. doi: 10.1007/s00521-018-3729-1
[14]	Ayele A A, Rao V S, Dileep K G, et al. Combining EDF and LST to enhance the performance of real-time task scheduling[C]. Indore: Proceedings of the International Conference on ICT in Business Industry & Government, 2016.
[15]	郝勃, 刘衍衍, 曲良东, 等. CAN网络的分组合并策略研究及实现[J]. 仪器仪表学报, 2012, 33(9):2137-2143.
	Hao Bo, Liu Yanyan, Qu Liangdong, et al. Research and implementation of grouping-merging strategy for CAN networks[J]. Chinese Journal of Scientific Instrument, 2012, 33(9):2137-2143.
[16]	张婧璇, 段武. 改进型EDF算法在计算机联锁全电子执行单元中的应用研究[J]. 铁道标准设计, 2017, 61(7):165-169.
	Zhang Jingxuan, Duan Wu. Study on improved EDF algorithm in computer interlocking full electronic execution unit[J]. Railway Standard Design, 2017, 61(7):165-169.
[17]	王浩, 张凤登. CAN总线中改进的EDF调度算法可调度性分析[J]. 计算机测量与控制, 2020, 28(8):238-241.
	Wang Hao, Zhang Fengdeng. The schedulability analysis of improved EDF scheduling algorithm in CAN-bus[J]. Computer Measurement & Control, 2020, 28(8):238-241.
[18]	简易, 魏磊, 杨亚联, 等. 基于截止期价值度优先的CAN消息实时调度算法[J]. 组合机床与自动化加工技术, 2015(1):157-160.
	Jian Yi, Wei Lei, Yang Yalian, et al. CAN message real-time scheduling algorithm based on deadline value priority[J]. Modular Machine Tool and Automatic Manufacturing Technology, 2015(1):157-160.
[19]	Chaw H S, Lee J, Lee J, et al. Global EDF schedulability analysis for parallel tasks on multi-core platforms[J]. IEEE Transactions on Parallel and Distributed Systems: A Publication of the IEEE Computer Society, 2017.
[20]	Park T, Shin K G. Optimal priority assignment for scheduling mixed CAN and CAN-FD frames[C]. Montreal: Proceedings of IEEE Real-Time and Embedded Technology and Applications Symposium.IEEE, 2019.
[21]	刘啸然. 汽车 CAN 网络的实时调度方法研究[D]. 合肥: 合肥工业大学, 2012.
	Liu Xiaoran. Research on automotive CAN network real-time scheduling method[D]. Hefei: Hefei University of Technology, 2012.
[22]	胡京津. 汽车 CAN网络系统动态调度机制的研究与实现[D]. 合肥: 合肥工业大学, 2014.
	Hu Jingjin. Research and relization of dynamic scheduling mechanism for automobile CAN network[D]. Hefei: Hefei University of Technology, 2014.
[23]	唐妍, 孟鑫, 谢佶宏, 等. 自动驾驶汽车总线技术应用趋势[J]. 电子世界, 2019(10):168-169.
	Tang Yan, Meng Xin, Xie Jihong, et al. Application trend of bus technology in autonomous vehicles[J]. Electronics World, 2019(10):168-169.

BCM	Gateway	IPC	Switch
Battery_Status1	Vehicle_Left_Door1	Engine_Fault	Key_ON
Battery_Status2	Vehicle_Left_Door2	Engine_Speed	Key_OFF
Battery_Status3	Vehicle_Right_Door1	Engine_Temp
	Vehicle_Right_Door2	Petrol_Level
	Vehicle_Speed
	Vehicle_Light

CAN FD报文	报文属性	周期/ms	传输时间/ms
Key_ON	非周期性	-	0.080
Key_OFF	非周期性	-	0.080
Engine_Fault	非周期性	-	0.080
Battery_Status1	周期性	400	0.115
Battery_Status2	周期性	400	0.115
Battery_Status3	周期性	400	0.115
Vehicle_Left_Door1	周期性	500	0.115
Vehicle_Left_Door2	周期性	500	0.115
Vehicle_Right_Door1	周期性	500	0.115
Vehicle_Right_Door2	周期性	500	0.115
Vehicle_Speed	周期性	500	0.115
Vehicle_Light	周期性	500	0.115
Engine_Speed	周期性	1 000	0.115
Engine_Temp	周期性	1 000	0.115
Petrol_Level	周期性	1 000	0.115

序号	时间/s	报文名称	周期/ms	传输时间/ms
1	2.000 111	Engine_Temp	1 000	0.115
2	2.000 220	Battery_Status1	400	0.109
3	2.000 329	Battery_Status2	400	0.109
4	2.000 438	Battery_Status3	400	0.109
5	2.000 547	Engine_Speed	1 000	0.109
6	2.000 656	Petrol_Level	1 000	0.109
7	2.000 765	Vehicle_Left_Door1	500	0.109
8	2.000 874	Vehicle_Left_Door1	500	0.109
9	2.000 983	Vehicle_Left_Door2	500	0.218
10	2.001 091	Vehicle_Right_Door1	500	0.108
11	2.001 201	Vehicle_Right_Door2	500	0.110
12	2.001 310	Vehicle_Right_Door2	500	0.109
13	2.001 418	Vehicle_Light	500	0.217
14	2.001 526	Vehicle_Light	500	0.108
15	2.001 634	Vehicle_Speed	500	0.216
16	2.001 743	Vehicle_Speed	500	0.109