基于分层调度算法的列车通信网络实时性研究

贺德强，王亚松，陈彦君，姚晓阳

(1. 广西大学 机械工程学院，广西 南宁 530004; 2. 中车株洲电力机车研究所有限公司，湖南 株洲 412001)

列车通信网络是现代轨道交通列车控制系统中的关键技术之一，主要用于传输列车运行状态信息、控制信息、监视信息、故障信息和乘客信息等重要数据。随着轨道交通朝着智能化方向发展，列车通信网络技术将更加重要。传统的列车通信网络，如LonWorks、CAN、MVB和WTB，因通信速率低，难以满足日益增长的列车通信量对高传输速率的要求[1]。为保障列车通信数据传输的实时性，基于全双工的交换式以太网技术被引入到列车通信网络中，它既能满足大通信数据量的要求，又能降低传统共享式以太网的非确定性[2]。

目前以太网在列车通信领域的研究已取得了一定的成果。文献[3]研究了基于交换式以太网的列车通信网络拓扑结构，并提出采用混合调度算法来改善实时性，但并未详细说明混合调度算法的具体实现。文献[4]研究了基于交换式以太网列车通信网络与随机Petri网模型，并采用了优先级调度，但对列车通信数据的优先级分配只按照数据类型分为三类，没有考虑发送同优先级数据的冲突，无法满足大通信数据量下列车对传输数据实时性的要求。文献[5]研究了高可用性无缝冗余在列车通信网络中的应用，但没有对列车通信数据实时性进行量化研究。

为保障以太网列车通信网络数据的实时性，需要对通信链路调度算法进行优化[6-7]。文献[8]提出一种基于指数分区的最小截止期优先(Earliest Deadline First，EDF)调度算法，来提高CAN总线的实时性，可以改善网络拥堵时低优先级不可调度的问题，但没有对高优先级的实时性是否变化加以说明，而在实时系统中必须优先保证高优先级数据的实时性[9]。文献[10]研究了如何使用EDF算法和最低松弛度优先算法实现最大延迟的最小化，但并未解决高优先级调度的问题。文献[11]研究了EDF算法可调度性的改进方法，提出在任务截止期不大于其周期的基础上，引入新的可调度性测试条件，减少测试所需的检查点数量，使算法提前结束，但该算法在任务总利用率较高时改进效果有限。

本文综合考虑列车通信数据对大容量数据和高实时性的要求，构建了基于全双工交换式以太网的列车通信网络三层拓扑结构；又根据列车通信数据对实时性的要求不同，结合上述拓扑结构，提出了基于优先级的分层调度算法，使用动态与静态优先级结合的方式对列车通信数据进行调度；最后使用网络演算理论和OPNET建模模拟，对分层调度算法的优越性进行仿真验证。

1 基于交换式以太网的列车通信网络

1.1 列车通信网络三层拓扑结构

本文设计的列车通信网络拓扑结构见图1。它分为三层：第一层为列车级网络，由各节车辆中的列车级交换机互联组成环形拓扑列车级骨干网(Ethernet Train Backbone，ETB)，列车级交换机实现车载接入节点的数据处理和整车网络管理；第二层为车辆级网络，在每节车辆中以车辆级交换机为中心节点，采用星型拓扑部署各车载网络节点；第三层为设备控制层，由每节车辆中各终端设备组成，数据经由端口传入发送端系统，再由发送端系统将数据进行以太网帧封装，送至交换机进行调度。每节车辆中的车辆级交换机和所有网络节点构成一个车辆级局域网(Ethernet Vehicle Network，EVN)，整个局域网通过列车级网关与列车级交换机连接，构成完整的通信链路。网关实现对局域网的管理和列车级与车辆级网络之间的协议转换。每节车辆中配置一个车辆控制单元(Vehicle Control Unit，VCU)，对本节车辆的车辆级局域网节点进行管理。首尾司机室各配置一个列车中央控制单元(Center Control Unit，CCU)，与车辆控制单元进行数据交互。

图1 列车通信网络拓扑结构

1.2 列车通信数据

根据数据类型和实时性要求，在列车通信网络中传输的通信数据分为以下5类：

(1)过程数据，表示车辆的实时运行状态和控制指令，帧长度较小，属于周期性强实时任务。

(2)消息数据，监视诊断信息和乘客信息，是按需传送的偶发性数据，帧长度较大，属于非周期性弱实时任务。

(3)监督数据，列车初运行数据或网络冗余控制数据，只有在网络重构或初始化时才被传输，属于偶发任务，但是在列车初运行时监督数据属于强实时任务。

(4)流数据，包括车辆运行中传输的视频或语音流等数据，属于非周期弱实时任务。

(5)最大努力数据，属于非实时数据。

以上5类数据的数据帧长度和对实时性的要求均不相同，所以服务要求也有所区别。在列车通信网络中传输时，应采用合理的调度算法来保证各类数据的服务要求。

2 基于优先级的调度算法研究

2.1 调度算法分析

目前在列车中广泛使用的MVB/WTB总线均采用主从方式控制总线介质访问，通过主设备将访问权分配给从设备来实现调度。特征轮询周期是基本周期的2n倍。每个基本周期可分为4个相：周期相、监视相、事件相和保护相。其中监视相、事件相和保护相构成偶发相。过程数据在周期相内发送，监督数据和消息数据在偶发相内发送。轮询周期结束之后主权可依次轮换。MVB通信访问方式见图2。

图2 MVB通信访问方式

图3 基于优先级的分层调度算法模型

这种调度方式的优点是在一个基本周期内可以发送所有类型的数据。但随着列车控制系统的发展，传输的列车通信数据量不断增大，现有MVB通信方式难以在一个基本周期内发送所有类型的数据。所以在基于以太网的列车通信网络中，应采用更合适的调度算法来保证列车通信数据传输的实时性[12]。

在基于交换式以太网的实时系统中，要保证传输数据的实时性，不仅要考虑链路带宽和吞吐量，还应该在调度算法上将所传输数据进行合理分类，实时性要求高、重要的数据优先发送，实时性低的数据其次，非实时性的数据最后发送，这点可以通过分配静态优先级实现。

IEC 61375-3-4标准[13]对各个数据服务参数值的定义见表1。

表1 各数据的服务参数值

IEEE 802.1D[14]中规定，优先级分为0～7共8个组，最高优先级为7，最低优先级为0。根据通信数据的数据类型和优先级要求，可将数据在交换机中的传输队列分为4个：0～1，2～3，4～5，6～7。数据优先级分配见表2。

表2 传输数据的优先级分配

发送端系统将数据包封装为以太网数据帧时，应根据其数据类型分配静态优先级，终端设备应使用RFC 2474[15]中定义的IP数据报中的差分服务代码点(Differentiated Services Code Point，DSCP)字段。DSCP字段的二进制为LLL000，其中LLL为静态优先级设定。

在基于静态优先级调度下，同类型数据的优先级相同，可能出现如下情况：①两条同种类型的数据流A和B同时到达处理器，产生冲突，数据立即停止发送，等待一个随机时间R×51.2 μs后重新发送；②两条同种类型的数据流A和B依次到达处理器，数据流B的截止期要比A早，等数据流A处理完毕后再处理数据流B，此时有可能已经超过了数据流B的截止期，则该数据失效。以上两种情况在实时系统中均不可靠，所以要保证数据的实时性，还应在分配静态优先级的基础上进行动态优先级调度。

2.2 基于优先级的分层调度算法

根据上述分析，本文提出基于优先级的分层调度算法，其算法模型见图3。

以太网帧封装采用TCP/IP四层模型，见图4。四层模型中分别添加DSCP字段(LLL000)、截止期(Deadline)字段、TCP首部、IP首部、帧头和帧尾，最终封装成以太网数据帧[16]。封装好的以太网帧格式见图5。

图4 以太网帧封装

图5 封装好的以太网帧格式

由于以太网帧封装是在高层数据中添加DSCP字段和Deadline字段，且字段长度小，所以其对整个系统的时延影响较小，取决于发送节点封装和接收节点解封处理速率。

在终端系统将数据进行以太网帧封装后，按分配好的静态优先级分为4个队列，然后经过交换机进行动态优先级调度。本文采用EDF算法[17]作为动态优先级调度算法。EDF算法根据任务的绝对截止期分配动态优先级，截止期越小，优先级越高。

数据传输过程：在交换机中按静态优先级传输4个队列的数据，同一队列中的数据再计算绝对截止期，根据动态优先级从高到低传输。使用分层调度算法既能够保证数据传输的有效性，又能够细分数据优先级，保证强实时任务的实时性。

2.3 可调度性验证

图6 任务的最大响应时间

由上述分析可知，忙碌期的长度L(a)等于[t1,t2]时刻内完成所有任务的执行时间之和，且所有任务至少被执行一次，则

(1)

式中：⎣x-|表示对x向下取整。

Cj，则

(2)

(3)

(4)

假设任务集中有4个任务，任务参数见表3。

表3 任务参数

可计算初始值L0(a)=7 ms，再计算a取不同值时任务τ1的响应时间Lm(a)-a，见表4。

表4 任务τ1的响应时间

由表4可以看出，任务τ1的最大响应时间tworst-1为6 ms。同理可得其他任务的最大响应时间，见表5。

表5 各任务的最大响应时间

表5中最大响应时间均小于表3中最小截止时间，所以该任务集可调度。

3 列车通信数据时延分析

在本文提出的列车通信网络模型中，数据帧从源节点发出，经过交换机服务后到终端节点被接收，其所经历的端到端时延分为以下几部分：

(1)帧处理时延TFrm-prcs，代表源节点对数据的以太网帧封装时间，与数据帧长度有关。

(2)发送节点时延Tsc-prcs，代表以太网数据帧的发送延迟。

(3)物理链路时延TLink，代表电信号在物理链路上传输的时间。

(4)交换机处理时延Tswitch，代表交换机内部的排队时间和帧转发时间。

(5)接收节点帧处理时延Trcv-prcs，代表以太网数据帧的接收时间和协议栈处理时间。

通信数据的整体端到端时延为

Tdelay=TFrm-prcs+Tsc-prcs+∑TLink+

∑Tswitch+Trcv-prcs

(5)

3.1 基于网络演算理论的时延分析

(6)

以下采用确定性网络演算理论对列车实时数据的端到端时延进行分析。确定性网络演算是网络演算理论中的一类，将最小加代数与到达曲线和服务曲线等演算工具相结合，来求解网络性能边界的确定性绝对值大小，网络端到端时延上界由到达曲线和服务曲线的距离所决定[19]。

考虑数据帧的大小，交换机可以提供的总服务曲线[20]为

β(t)=[St-L(t)]+

(7)

设数据流i的服务曲线为仿射到达曲线[21]，即

αi(t)=rit+bi

(8)

式中：ri为平均生成速率；bi为突发容忍度。则交换机提供给数据流i的服务曲线为

(9)

交换机对数据流i的服务能力Ri和服务时延Ti[22]分别为

(10)

3.2 实例计算

采用如图1的网络拓扑结构；列车级交换机和车辆级交换机带宽均为100 Mbit/s；每节车辆配置15个网络节点，包括中间车辆的车辆控制单元和首尾司机室的中央控制单元；车辆长度取26 m，电缆长度取车辆长度的1.5倍[23]，即39 m；满足以太网100 m的传输距离要求，信号在物理介质中传输速度为2.0×108m/s；以太网的帧长度为84～1 542 octets。

假定监督数据和过程数据均采用最小数据帧84 octets，取每个周期(监督数据为10 ms，过程数据为20 ms)发送一个数据帧，则监督数据的到达曲线为

α7(t)=8 400t+84

(11)

过程数据的到达曲线为

α5(t)=4 200t+84

(12)

消息数据和流数据一般比较大，取最大数据帧1 542 octets，其发送速率为监督数据的0.2倍，发送一个数据帧，其到达曲线为

α3(t)=1 680t+1 542

(13)

最大努力数据为非实时数据，其到达曲线为

α1(t)=1 680t+15 420

(14)

以过程数据队列(静态优先级Pi为5)中的一个微数据流为例(各参数见表3，已验证过其可调度性)，

τ={τi(Ti,Ci,Di,Pi,ti),i=1,2,3，…，n}=

{τ1(20,1,6,5,0),τ2(20,2,4,5,0),

τ3(20,2,5,5,4),τ4(20,2,8,5,6)}

(15)

另外，监督数据的优先级比过程数据高，假设监督数据队列发送一个数据帧，以下分别采用分层调度算法和固定优先级调度算法对其进行端到端时延计算。固定优先级调度算法指不使用分层调度算法，只按照静态优先级的高低进行队列排序，交换机按照最基本的先来先服务(First Come First Serve，FCFS)原则接收处理任务集信息，只处理位于队列首位的数据。

3.2.1 分层调度算法

假设发送节点以太网帧封装速率为10 Mbit/s，接受节点的协议栈处理时间取50 μs，数据从设备输出端口至中央控制单元最远要通过7个交换机和8段链路，再将T5-3及其他数据代入式(5)得到任务τ3的端到端时延为

同理可求任务τ1、τ2、τ4的端到端时延。

3.2.2 固定优先级调度算法

任务集τ中的4个任务静态优先级Pi均等于5，所以在交换机中按照其到达时间顺序先后τ1>τ2>τ3>τ4发送。但在t=0时刻，任务τ1和任务τ2同时到达，发生第一次冲突，须返回并等待一个随机时间R×51.2 μs后再重新发送。R取0～(22-1)之间的一个随机整数，令任务τ1等待2×51.2 μs，任务τ2等待3×51.2 μs，这样不影响原来的发送顺序。将各项参数代入式(10)可得交换机对任务τ1的服务能力和服务时延分别为9.999 16×107bit/s、0.115 8 ms。

再将结果代入式(5)，其他参数同上，可得任务τ1的端到端时延为0.929 6 ms。

同理可求任务τ2、τ3、τ4的端到端时延。

3.2.3 结果对比

对同一个任务集使用不同的调度算法，得出的各任务时延及平均时延见表6。

表6 使用不同调度算法的端到端时延

由表6可以看出，对任务集τ，使用分层调度算法可以降低其整体平均时延，提高数据传输的实时性。

4 基于OPNET的列车通信网络实时性仿真

为验证分层调度算法的优越性，采用OPNET Modeler仿真平台搭建列车通信网络仿真模型，仿真2个场景：

(1)以图1中的网络拓扑为模型，场景大小400 m×400 m，8个100 Mbit/s带宽的24接口列车级交换机采用环形拓扑方式连接，交换机之间相距50 m，每个列车级交换机通过网关与车辆级交换机连接，再以车辆级交换机为中心，采用星型拓扑连接20个网络节点发送所有类型数据，中间6个车辆级交换机再各连接一个VCU，发送和接收该节车辆数据，两司机室的车辆级交换机再各连接一个CCU，同各VCU进行数据交换，交换机使用分层调度算法，参照3.2节为各个网络节点配置通信数据。

(2)拓扑模型和网络节点数据同场景(1)，交换机使用基于固定优先级的FCFS调度算法。

4.1 链路吞吐量

由于司机室的CCU对各个VCU进行控制，所以对CCU与VCU之间的链路吞吐量进行测量，测量结果见图7。由图7可以看出：仿真时间在0～100 s之间时，链路吞吐量达到了4.1×106bit/s，这是由于仿真开始时通信数据量较大，4种数据同时发送，在交换机中出现排队积压现象；仿真继续进行，通信数据在队列中趋于稳定，没有突发性大容量产生，使得吞吐量趋于平缓，最终稳定在2.3×106bit/s左右。

图7 CCU与VCU之间链路吞吐量

4.2 端到端时延

2个场景下的数据端到端时延仿真结果分别见图8和图9。在采用分层调度算法的情况下，4个队列的数据时延分别为0.226、0.266、0.786、1.086 ms；在采用固定优先级调度算法的情况下，4个队列的数据时延分别是0.590、0.698、0.852、0.990 ms。

图8 采用分层调度算法端到端时延

图9 采用固定优先级调度算法端到端时延

通过比较可以看出，两种调度算法均可以区分不同优先级队列的数据，并且能够保证高优先级数据优先发送；相较于固定优先级调度，使用分层调度算法使监督数据和过程数据的时延分别降低61.7%和61.9%，消息数据和流数据的时延降低7.7%，最大努力数据的时延提高9.7%。使用分层调度算法后，对于高优先级数据，可以明显提高实时性；对于低优先级实时数据，由于其数据帧较大，可以少量提高实时性；对于非实时数据，由于其数据帧大且排在最后队列，会少量降低实时性，但是非实时数据的实时性不是重要因素，可以接受较高时延。再比较两种调度算法下的各数据平均时延，由图10可以得到结论，添加动态优先级调度对系统的时延影响较小，使用分层调度算法可以有效降低数据整体传输时延，且显著提高了高优先级数据的实时性。

图10 两种调度算法的平均时延

5 结论

列车通信网络的发展趋势是大带宽、高通信速率，基于以太网的列车通信网络是其发展方向。在此背景下，本文提出了基于优先级的分层调度算法，根据数据类型和实时性需求分配静态优先级，再使用EDF算法作为动态优先级调度，确定最终优先级。理论分析和仿真结果表明，采用该调度算法可以有效改善列车通信数据的整体实时性，满足IEC 61375-3-4标准中对各数据最大延迟的要求；并且相较于固定优先级调度，该算法使优先级较高的监督数据和过程数据的实时性分别提高了61.7%和61.9%，显著提高了高优先级数据的实时性，为大容量数据传输趋势下的列车通信网络提供了理论参考和可行方案。