面向车车通信的安全计算机时间约束性分析验证

高莺，曹源，孙永奎，马连川，洪春华，张玉琢

（1. 中国铁道科学研究院研究生部，北京 100081；2. 北京交通大学轨道交通运行控制系统国家工程研究中心，北京 100044；3. 北京交通大学电子信息工程学院，北京 100044）

1 引言

现代轨道交通列车运行控制系统采用分布式、叠加结构，通过地面子系统设备和车载子系统设备之间的通信实现列车运行控制[1]。但是随着现代无线技术发展，系统将从车地协同控制模式向更加智能化的车车通信模式发展，以满足日益增长的行车组织要求。车车通信技术旨在尽可能减少地面子系统设备，并将地面子系统功能整合到车载子系统中，使列车运行控制模式由列车和地面子系统协同控制转变为列车之间直接协同控制[2]。由于车车通信技术对车载安全计算机功能的要求愈加苛刻，其软件应用也将愈加庞大，使面向车车通信的安全计算机成为多周期性应用并发的实时控制系统。支持多任务并发的系统虽然具有资源整合共享、降低系统设备复杂度、优化系统结构等诸多优势，但也存在影响系统运行实时性及应用执行时间不确定延时的问题。

时间约束性是安全关键系统重要的特性。安全计算机在规定的时间内完成安全控制逻辑，才能保证行车安全。IEC61508标准和EN50128标准均对安全关键系统的软件功能提出时间约束性要求[3]。由于时间约束性在安全关键系统中的重要性，针对实时系统的时间约束性问题，国内外学者已经提出相关的验证和建模方法。文献[4]中提出了一种实时系统的时间约束建模和一致性验证方法，可针对性地检验系统的时间缺陷。文献[5]中提出了基于时间Petri网的实时系统可调度性分析方法，说明了时间Petri网能有效地分析实时系统的时间特性。也有学者利用Petri网对实时系统进行组合可调度性[6]和独立性[7]分析，说明该方法适用于分析安全关键系统的特性。文献[8]通过分析具有标记的时间 Petri网系统的可诊断性，说明时间Petri网适用于安全关键系统的故障诊断。文献[9]分析了时间约束 Petri网模型及其可调度性，从而验证了时间Petri网能有效描述和分析时间约束性问题。文献[10]研究了基于时间Petri网的实时并行设计过程，定量分析了实时并行过程的时域性，说明时间Petri网可为并行设计提供可靠的理论依据。

在轨道交通领域，时间Petri网主要用于分析列车运输调度问题。文献[11]提出基于时间Petri网的推理算法，验证了时间约束的列车运行调整方案的可行性。文献[12]提出了基于模糊时间Petri网的列车运行时间不确定问题的处理方法。然而，目前国内外针对安全计算机安全性方面的研究，主要集中在硬件安全设计方法，如2乘2取2架构、3取2架构等。同时为了确保轨道控制设备的安全性和可靠性，车载安全计算机只采用经过反复验证的计算机硬件，其性能远低于主流的计算机。由于车载安全计算机硬件安全结构和性能等方面的限制，同时也缺乏针对多周期性应用时间约束性的验证和评估方法，导致其系统软件设计更加保守化，严重制约轨道交通控制技术的发展。因此本文以目前安全计算机硬件结构和性能现状入手，针对面向车车通信的车载安全计算机多周期性应用的时间约束性问题，首次采用时间 Petri网建模验证，以说明多周期性应用能够满足车载安全计算机时间约束性的安全需求。

2 车车通信系统

CBTC系统是目前国内外大部分城市轨道交通使用的信号系统技术。CBTC系统主要采用车载子系统与地面子系统相互协作实现列车行车控制和移动闭塞功能，因此线路中存在许多区域控制器（ZC, zone controller）、计算机联锁（CBI, computer-based interlocking）等地面设备。然而，复杂的地面设备导致子系统之间接口复杂化，系统维护成本高，运营灵活性差等诸多问题。为解决以上问题，国内外开始研究轨道交通信号系统车车通信技术，以简化系统复杂度，精简轨旁设备，提高并优化系统性能，如法国里尔地铁1号线已经采用了以目标控制器和列车为核心的控制系统[2]。

在基于车车通信的列车运行控制系统中，区域控制器、联锁设备的功能被智能化的目标控制器和车载设备所取代，从而改变现有CBTC系统以地面控制设备为核心的架构，使车载系统成为行车控制核心。通过现代无线通信（如wlan、LTE-M）和移动控制算法[13-14]等技术实现列车与列车之间，列车与目标控制设备之间直接协同控制，降低系统对轨旁设备的依赖，减少系统控制流中间环节，如图 1所示。基于车车通信的列车运行控制系统能够降低系统复杂度，降低维护成本，提高运营的灵活度，并将全面提高对车载安全计算机的性能需求。多个独立控制功能模块整合到车载安全计算机中，使其设计面临多应用并发和系统实时性之间的矛盾。列车运行控制系统作为安全关键实时控制系统，其应用逻辑设计基本采用周期性时限执行的控制算法，对执行的时间约束性要求高。而目前CBTC系统的车载安全计算机只考虑简单应用需求场景，缺少对多个独立功能模块整合的并发系统的研究，针对该问题，本文对安全计算机多应用并发性进行时间约束性分析，对CBTC系统由车地通信模式向车车通信模式转换有一定的指导意义。

图1 车车通信系统架构

3 时间约束性分析

3.1 时间Petri网

Petri网概念最早于1962年由德国Carl Adam Petri提出，直观的图形表示特点和完善的数学理论基础使其特别适合描述异步并发系统。随着时间因素在实际应用分析中愈加重要，出现 TPN分支理论[9]。TPN也是 IEC61508和 EN50128软件完整性等级SIL4所推荐的建模方法。下面以图2为例分析TPN模型的参数含义。

如图2所示的TPN模型描述的是在T0时刻库所sn开始等待接收托肯，由于传输延时，托肯到达库所存在延时。

图2 基本TPN模型片段

定义1可调度性。若考虑变迁tn和库所托肯到达的时间，且变迁tn满足式(1)，则称其具有强可调度性。若不考虑库所托肯到达的时间，则称为弱可调度性[9]。

变迁满足可调度性是指在一定的可调度范围内，通过调度调整能够实现满足时间约束性变迁，而不是在任何时间点都能实现变迁[9]。

3.2 安全计算机TPN模型

目前，国内外车载安全计算机基本采用分布式2乘2取2容错结构，每系独立划分为通用计算域、安全管理域[3]。实时系统的应用运行在通用计算域，并由安全管理域监督。安全计算机应用运行采用基于时间触发式的调度机制，在限定周期内完成一次应用执行逻辑，即周期性控制算法。为提高控制精确度，将一个应用执行周期T划分 3个子周期：数据输入子周期、应用运算子周期、数据输出子周期。每个子周期在规定时间内完成相应逻辑处理后，向安全管理域报告运行状态，由安全管理域根据时间约束性判断应用执行逻辑是否满足安全要求，如图4所示。

图3 TPN片段时间流描述

图4 安全计算机时间调度算法

若应用出现故障不满足时间约束关系，则容错安全管理域能够及时有效地发现应用故障，从而采取有效安全措施防止事故发生。由安全计算机控制过程可知，车载安全计算机中系统应用在安全控制逻辑中被周期性调用执行，只要周期性应用不满足时间约束要求，就会触发安全计算机安全处理逻辑，使系统导向安全。根据图4安全控制逻辑流程，对时间触发式控制算法建立TPN模型，如图5和表1所示。

图5 安全计算机时间调度算法TPN模型

表1 TPN模型变迁含义

由图5可知TPN模型能直观描述安全计算机平台逻辑的时间约束特性。由于多任务多应用的复杂并发系统存在有限的资源（输入输出资源、CPU资源等）复用问题，需要增加调度机制实现多个应用并发管理。假定单应用的TPN模型变迁都是可调度的，即在单任务的简单控制系统中，满足时间约束性要求的条件下，只要增加的调度变迁是可调度的，则多应用并行就能在满足时间约束关系条件下成功变迁。

3.3 调度变迁可调度条件

3.3.1 应用调度变迁

在多个周期性应用并行模式下，应用通过多线程（或多任务）调度机制实现并发执行。由于系统基于嵌入式实时操作系统，线程上下文切换开销时间与应用逻辑处理时间相比可忽略不计。设应用执行调度变迁为k，系统各应用的变迁运算处理耗时为ti，则n个应用并行情况下，最长可能变迁延时为

在应用执行阶段只负责数据逻辑处理，数据获取和传输都在其他时间段执行，因此Ta(sk)=0，Tl(sk)=0，并且托肯的使能时间约束区间与触发约束区间相同。同时该变迁的某个时间约束段可能属于多个应用的时间约束区间，这种情况下该时间约束区取各个应用中最短的时间约束区间，即

且由定义1可知，若要满足强可调度，则变迁k需满足式(4)。

3.3.2 输入调度变迁

在多应用并发执行模式下，每个应用输入变迁增加了数据排队到达的调度延时，则到达延时为

其中，αi为各应用输入数据传输的排队延时，Tc为外部通信延时（如无线通信延时）。

输入变迁k负责将接收的外部数据交给应用执行变迁处理，因此其离开库所延时Tl(sk)=0。由定义1可知若要满足可调度性，则各变迁k需满足

3.3.3 输出调度变迁

输出变迁的 TPN模型可看成输入变迁的逆过程，主要不同的是离开延时Tl(sk)。设每个应用排队离开的延时为βi，同样设外部通信延时为Tc，则排队离开的调度延时为

由定义1可知输出变迁若要满足可调度性，需满足

根据输入、输出、应用调度变迁的可调度性条件，对并发系统的应用并发数量与其时间约束特征进行分析。假设系统的周期性应用数为n，计算机性能度量修正参数为tarr，以安全计算机实验平台单核1GHz主频的处理器性能为基准，应用逻辑运行时间基本在 1～10 ms范围，因此可取其最大值tarr= 10 ms作为性能指标。

假定输入输出调度器均基于先到先服务策略，由文献[15]可知输入输出排队延时与并发应用数n之间存在关系，则输入输出排队延时Ts为

根据实时操作系统调度策略，由于各应用具有相同优先级，采用 Round-Roin调度（也称轮询调度），则td∝ (n)，由式(2)可得

其中，g(n)为n个应用并行情况下，最长可能变迁延时。

设关于变量n的可触发区间函数为T(n)，表示最早可能触发开始到最晚可能触发结束的时间长度，则有

由TPN可调度性和定义1可知，f(n)-g(n)≥ 0表示该变迁具有可调度性，否则不具有可调度性。并可用R(n) =f(n) -g(n)表示n个应用并发执行情况下该变迁的可调度时间范围。R(n)值越大，说明调度范围越大，系统的时间冗余度越高，安全性也越高，但是资源利用率越低。

首先分析计算机性能参数tarr与并发系统的应用数n之间关系。由于 CBTC系统采用无线（如WLAN）和有线（如光纤通信）通信组网方式实现各个子系统的协同控制，由文献[16-17]可知，其通信延时在 40～50 ms，因此可设外部通信延时Tc= 50ms。虽然外部通信延时与列车速度等现实因素有一定的关系，但要保证列车安全运营，无线基站的布置满足列车运营需求即可，所以本文没有重

4 时间约束性验证

4.1 可调度验证方法

点阐述列车速度等因素对通信传输速率的影响。CBTC系统中安全计算机控制周期时间为200 ms，其时间约束区间为0～200 ms。则一个周期内可调度时间范围为

令tarr= {10, 1, 0.1}，表示不同计算性能的安全计算机，绘制不同计算性能下，R(n)与应用数n的关系图，如图6所示。当tarr=10ms时，在满足现有的系统应用时间约束的条件下，可最大支持的并发应用数n=4，而目前 CBTC系统中安全计算机实际只运行一个应用功能，其资源利用率η只有25%。而当计算机性能提高到tarr=0.1ms时，并发应用数最大可达n=49，表明计算机性能的提升会为安全计算机提供更大的设计冗余空间，并可进一步优化系统性能。同时，由图 6可知，随着n的增大，时间冗余度也相应降低，为保证系统安全可靠运行，在系统设计时需要考虑一定的时间可调度冗余性。

图6 不同计算计算性能下R( n)与n的关系

上述分析基于每个应用均与外部子系统应用进行通信的假设，而实际在车车通信系统中，各个控制功能模块之间的交互变成了计算机内部线程的交互，数据通信延时将会极大地降低，从而系统性能能得到进一步优化，安全性也能得到进一步提升。假设计算机性能参数tarr=10 ms ，则可调度时间范围为

则根据式（13）可绘制不同通信延时下，R(n)与应用数n的关系图，如图7所示。通信延时减小，系统的时间冗余度能够得到提高，有利于提高系统的安全性。

图7 不同通信延时下R( n)与n的关系

根据上述分析可知并行应用数与其可调度区间关系。可调度区间代表时间约束的冗余度，时间冗余度越高，说明系统容错能力越强，系统安全性越高，但系统性能利用率越低。通过TPN建模可以对时间约束冗余度R(n)与应用数n建立联系，从而定量地确定系统并发设计要求。通过对安全计算机性能以及通信延时这2个方面进行分析，表明安全计算机性能的提升及通信延时的降低能够增加可调度区间，即满足软件综合化的时间约束关系，且能进一步优化时间约束参数，同时也表明在当前硬件条件下，车载安全计算机可满足多个周期应用调度需求。另外，TPN模型能准确描述系统时间约束关系和影响时间特性的主要因素，为进一步优化时间参数提供理论依据。

4.2 时间约束特性实例设计

为了验证基于 TPN的时间约束性分析评估方法在评估安全计算机性能及周期性应用并发数关系上的有效性，本文在车载2乘2取2安全计算机硬件设备条件下，测试3个周期性应用的时间运行关系，验证该安全计算机是否满足3个周期性应用的时间约束性。限于安全性和可靠性方面考虑，该安全计算机平台的硬件采用已验证的单核主频1 GHz的PowerPC系列的处理器。同时分别设计3个周期性应用A/B/C，其周期分别为35 ms、40 ms、50 ms。通过记录每个应用的周期开始和结束时间，以及应用执行的开始和结束时间来确定多应用并发情况下是否满足周期性时间约束。

首先说明面向车车通信的安全计算机与目前CBTC系统中安全计算机的主要差别。CBTC系统主要由分散的子系统ZC和CBI完成控制功能，而车车通信系统将这些功能集中到车载系统。CBTC系统中的车载安全计算机只执行车载列车超速防护（ATP, automatic train protection）功能，而车车通信系统中，车载安全计算机除了实现车载ATP安全关键功能外，还将整合CBTC系统中ZC和CBI的ATP安全苛求功能，如轨旁设备控制命令下达、车门管理等，如图8所示。功能的整合必然使得车载安全计算机成为复杂的并发系统，而车载计算机是典型的安全关键实时控制系统，不仅需要保证处理逻辑功能的正确性，还必须具有严格的周期性特征，即必须在严格限定的时间内执行相关命令，否则可能造成严重的安全事故。

图8 车车通信车载安全计算机结构

4.3 调度时刻特性分析

根据上述实例设计，获得周期性应用的运行时间特性数据，依据时间变量关系将其整理成离散点图，如图9所示。其中，3个周期性应用分别为应用A、应用B和应用C，横轴表示应用在系统调度中的运行时刻表，每个片段表示应用在计算机中被选中调度的实际运行时长。案例设计中，记录应用在其每个控制周期内的运算开始和结束时间点，表示周期内的有效执行时间。

图9 各应用周期调度实际运行时刻

由图9可知，安全计算机安全苛求应用实际运行时间是离散化的，而非连续的。这与宏观上观察的安全计算机应用存在本质区别。在周期调度策略中，就安全计算机安全关键应用对资源的竞争力而言，其逻辑不可能完全保证自身的有效运行时间，必须依靠安全计算机平台的调度策略来保证。

取局部样本分析，如图 10所示。周期性调度策略会根据每个应用声明的调度周期，在时间约束内灵活调度多个应用安全并行。从图 10的实际测试结果可知，在目前软硬件条件下，安全计算机平台能满足3个应用周期性调度。

图10 各应用局部时间特性

图 10中每个应用都能在其周期约束内完成运行逻辑。每个周期内应用实际执行时间占整个周期时间的比率为 10%～30%，符合前面分析结果。同时各个阶段的有效运算时长比率存在波动，图 10中应用的执行时间在每个周期内不尽相同，但执行时长都约束在 10%～30%比率内。造成该现象的原因是多应用并行存在资源竞争，导致任务阻塞，从而增加处理延时。这种情况符合实时操作系统多任务调度特性，也是多应用并行影响原有系统的时间约束性的主要表现。

5 结束语

针对CBTC系统的发展趋势，研究了面向车车通信的车载安全计算机中多个周期性应用并发能否满足时间约束性要求的问题。列车运行控制系统的功能整合，导致多个安全关键的周期性应用在车载安全计算机上并发运行。然而限于目前车载安全计算机的硬件性能，需要对安全计算机能否满足多周期性应用的时间约束性进行验证和评估。本文以目前的安全计算机硬件结构和性能入手，首次采用TPN分析多个周期性应用的并行时间特性。通过建立TPN模型，分析了可调度性区间，结果表明目前使用的2乘2取2车载安全计算机性能满足3个周期性应用的时间约束性要求。同时，论证了在满足各周期性应用时间约束条件下，计算机性能、通信延时与可支持的周期性应用数之间的关系。

基于车车通信的列车运行控制是未来城市轨道交通列车运行控制的发展方向，而车载安全计算机必然也会变得更加复杂化和多功能化。因此，研究车载安全计算机支持多个周期性应用的关键技术具有实际意义。在将来的研究中，我们将考虑更多现实环境因素，并对TPN加以改进，应用于合适的应用场景。