Temporal Constraint Scheduling Algorithm for Periodic Data of Ethernet-Based Train Communication Network
-
摘要: 针对工业以太网调度方法以报文截止期为唯一约束的局限,提出了一种基于时态约束的列车通信网络周期数据调度表生成方法.首先基于时间触发机制改造列车以太网的通信与消息模型;其次利用网络设备通信参数与数据报文参数,提出周期数据通信的时态约束有向图量化模型;最后设计了基于可满足性模理论的调度表生成算法,求解单播及广播业务的周期数据调度表以验证算法有效性,并在实际列车通信网络的拓扑条件下进行调度性能测试及分析.实验结果表明:该调度算法能够解决部分传统算法不能调度的通信任务,满足更细化的周期数据调度需求并提升调度灵活性;调度性能测试中最大链路负载超过80%,可调度周期数据业务量达到1 000项.Abstract: Instead of time intervals as the only constraint in message scheduling for industrial Ethernet, a temporal constraint scheduling table generation method for periodic packet data of Ethernet-based train communication network (TCN) is proposed. Firstly, network and message model are modified by time-triggered mechanism. Secondly, a directed graph quantization model for periodic data was proposed according to temporal parameters both from communication equipments and transmitting packets. Finally, a scheduling table generation algorithm based on satisfiability modulo theory was designed. A scenario of unicast and multicast services was scheduled to verify effectiveness of the algorithm. The scheduling performance test and analysis were performed under the actual Ethernet TCN topology. Experimental results show that the proposed scheduling algorithm performs some scheduling tasks that traditional algorithms cannot do, provides a more detailed solution to scheduling requirements for periodic data, and improve scheduling flexibility. In the performance test, the maximum link load exceeds 80%, and its configurable process data traffic reaches 1 000 items.
-
Key words:
- communication networks /
- scheduling algorithms /
- real-time systems /
- Ethernet
-
表 1 网络设备通信参数
Table 1. Communication parameters of network equipments
设备 型号 TTxD/μs TRxD/μs TBD/μs CNN1~3 CP-1616 1.192 0.363 1.720 ED1~3 S120 1.212 0.418 ED4~5 IM151-3 0.158 0.350 表 2 链路传输时延
Table 2. Delay times of transmission link
物理链路 TLD/μs 物理链路 TLD/μs l1 4.795 l9 3.040 l2 4.795 l10 3.040 l3 4.795 l11 4.775 l4 4.775 l12 4.775 l5 4.775 l13 4.775 l6 4.775 l14 3.110 l7 3.714 l15 3.110 l8 3.714 l16 3.110 表 3 过程数据任务与约束条件
Table 3. Tasks and temporal constraints of PD messages
过程
数据源设备/
目的设备任务
组成释放
时间/μs绝对截
止期/μs端到端
截止期/μs链路占
用时间/μs周期/
μsM1 ED1−ED5 ${l_1} \to \;{l_5} \to {l_9}$ 1.000 40.000 17.000 6.880 32.000 M2 ED3−ED5 ${l_3} \to \;{l_6} \to {l_9}$ 13.000 30.000 19.000 6.880 64.000 M3 ED1−ED2 ${l_1} \to \;{l_{15}}$ 8.000 * * 6.880 32.000 M4 ED1−ED3 ${l_1} \to {l_4} \to \;{l_{14}}$ 20.000 35.000 * 6.880 64.000 M5
(广播)ED2−{ED1,ED3,ED5,ED4} $ {l_2} \to {l_{16}}, {l_2} \to {l_4} \to {l_{14}}, $${l_2} \to {l_5} \to {l_9}, {l_2} \to {l_5} \to {l_{10}}$ 5.000 {*,*,*,45.000} {*,24.000,24.000,22.000} 11.840 128.000 -
赵晋南,谭献海,张华等. 列车控制与服务网络流量监管研究[J]. 铁路计算机应用,2017,26(11): 49-53. doi: 10.3969/j.issn.1005-8451.2017.11.013ZHAO Jinnan, TAN Xianhai, ZHANG Hua, et al. Traffic monitoring of train control and service network[J]. Railway Computer Application, 2017, 26(11): 49-53. doi: 10.3969/j.issn.1005-8451.2017.11.013 周洁琼. 基于交换式以太网的列车通信网络实时通信技术研究[D]. 北京: 北京交通大学, 2014. International Electrotechnical Commission. Industrial communication networks − profiles part 2: additional fieldbus profiles for real-time networks based on ISO/IEC 8802-3: IEC 61784-2[S]. Gevena: IEC, 2014. SAE International. Time-triggered Ethernet: AS6802[S]. Warrendale: SAE, 2016. 聂晓波,王立德,申萍. 轨道车辆MVB网络实时性能分析与优化研究[J]. 铁道学报,2011,33(9): 40-44. doi: 10.3969/j.issn.1001-8360.2011.09.007NIE Xiaobo, WANG Lide, SHEN Ping. Real-time performance and optimization of MVB network of rail vehicle[J]. Journal of the China Society, 2011, 33(9): 40-44. doi: 10.3969/j.issn.1001-8360.2011.09.007 FERREIRA J, ALMEIDA L, FONSECA A, et al. Combining operational flexibility and dependability in FTT-CAN[J]. IEEE Transactions on Industrial Informatics, 2006, 2(2): 95-102. doi: 10.1109/TII.2005.875508 POP T, POP P, ELES P, et al. Timing analysis of the FlexRay communication protocol[J]. Real-Time Systems, 2008, 39(1/2/3): 205-235. doi: 10.1007/s11241-007-9040-3 周洁琼,王立德,王涛等. 基于交换式以太网的列车通信网络的交换机排队时延分析[J]. 北京交通大学学报,2014,38(2): 95-100.ZHOU Jieqiong, WANG Lide, WANG Tao, et al. Switch queuing delay of train communication network based on switched Ethernet[J]. Journal of Beijing Jiaotong University, 2014, 38(2): 95-100. WISNIEWSKI L, SCHUMACHER M, JASPERNEITE J, et al. Fast and simple scheduling algorithm for PROFINET IRT networks[C]//IEEE International Workshop on Factory Communication Systems. [S.l.]: IEEE, 2012: 141-144. 刘宁. EPA工业以太网实时性分析及调度方法的研究[D]. 大连: 大连理工大学, 2010. 耿晓晗. 基于实时以太网PowerLink的列车网络的实现研究[D]. 北京: 北京交通大学, 2017. 高鹏飞. 时间触发以太网交换机设计[D]. 西安: 西安电子科技大学, 2014. STEINER W, STEINER W. Design optimization of TTEthernet-based distributed real-time systems[J]. Real-Time Systems, 2015, 51(1): 1-35. doi: 10.1007/s11241-014-9214-8 徐晓飞,曹晨,郭骏,等. TT-RMS:时间触发网络通信表生成算法[J]. 北京航空航天大学学报,2015,41(8): 1403-1408.XU Xiaofeng, CAO Chen, GUO Jun, et al. TT-RMS:communication table generation algorithm of time-triggered network[J]. Journal of Beijing University of Aeronautics and Astronautics, 2015, 41(8): 1403-1408. International Electrotechnical Commission. Electronic railway equipment-train communication network (TCN),part 3-4: Ethernet consist network (ECN): IEC 61375-3-4[S], Geneva: IEC, 2014. 王景波,王吉松,张鹏. 350 km/h中国标准动车组网络控制系统[J]. 机车电传动,2018(2): 12-15.WANG Jingbo, WANG Jisong, ZHANG Peng, et al. Network control system of 350 km/h CEMU[J]. Electric Drive for Locomotives, 2018(2): 12-15.