基于极大代数的安全系统失效传播分析
佘晓丽1, 赵纪元2, 杨健1     
1. 清华大学电子工程系, 北京 100084;
2. 西安交通大学高端制造装备协同创新中心, 西安 710049
摘要:针对多个子系统协同工作的安全系统, 提出基于极大代数的失效传播分析方法。该方法分别针对失效在子系统间的传播过程和控制过程建立模型, 基于极大代数运算规则提出迭代求解公式, 并在此基础上得到失效传播导致的系统危害暴露时间(TSF)。相比其他失效传播模型, 该方法通过失效传播与控制模型的对比发现失效传播机制的非对称特性, 并给出了求解协同系统TSF的方法。通过中国列车控制系统(CTCS)实例分析表明了本方法的有效性。
关键词失效传播    极大代数    安全分析    列车控制系统    
Max-plus algebra failure propagation analysis of safety systems
SHE Xiaoli1, ZHAO Jiyuan2, YANG Jian1     
1. Department of Electronic Engineering, Tsinghua University, Beijing 100084, China;
2. Collaborative Innovation Center of High-End Manufacturing Equipment, Xi'an Jaotong University, Xi'an 710049, China
Abstract: A failure propagation analysis method was developed for safety systems having multiple interactive sub-systems. Two models are given based on min-plus and max-plus algebra to describe the failure propagation and control processes. Iterative solutions for both models give the final hazardous output disclosure time for specific failures. Unlike other failure propagation models, this method describes the asymmetry in the failure propagation mechanism and presents a calculational method for the hazardous incident time for interactive safety systems. This method is applied to a conceptual CTCS system to demonstrate its effectiveness.
Key words: failure propagation    max-plus algebra    safety analysis    train control system    

失效传播机制研究失效转化为系统危害的主要机理。作为系统安全分析的基础,失效传播模型为后续的系统安全分析提供了失效演化的基本框架。

目前安全系统越来越呈现多系统协同的趋势,这样的特点使得局部失效的影响远比在单一系统中复杂,即使局部失效已经恢复,也可能通过系统间交互进一步影响到其他子系统,因而难以确定失效在整系统中是否得到及时控制[1]。另一方面,现代安全系统的实时性要求越来越高,以现代列车控制系统为例,列车速度的提高使得安全功能的实时性要求越发苛刻,失效传播延时成为限制系统安全性能的一个重要因素[2]

针对以上2种趋势,目前的失效传播模型还存在一定的局限性。基于模块的失效传播转化模型(FPTN)能够表达系统间的失效交互作用,但缺乏定量的数学模型支持[3]。多种形式的Petri网模型也用于失效传播分析[4],但容易引入状态爆炸问题。此外,目前普遍应用的失效分析方法仍着重于部件的随机失效对整系统造成的后果,缺乏针对多系统交互的失效分析方法。

本文针对交互安全系统提出了一种新的失效传播模型,采用极大代数运算法则描述失效的逐级传播及延时累加,该模型可同时表征失效传播的逻辑关系和传播延时,并在失效演化计算过程中得到累计传播延时。本文针对失效的传播和控制过程分别建模,通过对比发现失效传播的非对称特性,并在真实系统分析中验证了其重要意义。

1 失效传播分析

失效在铁路等工业领域的安全标准[5]的定义为“偏离规定的系统行为”,是一种非正常的系统状态。失效传播机制研究是指通过简化次要细节,发现失效在系统中演化为危害的主要机理。在失效传播模型中,系统通常被定义为一系列模块,这些模块的行为以及模块间的失效传播结构,共同决定了失效在系统中的传递和控制过程。

系统内部的失效通过通信、光电信号传输、人机接口和物理接口等,引发其他失效,最终可能传播至系统边界,造成危害输出。如图1所示,系统内部失效F1F2传播至系统边界形成危害,失效传递逻辑关系见图1(a),失效发生及控制的时序见图1(b)。对任何事件引发的系统边界失效,安全系统均应保证其危害输出暴露时间Tsf小于安全功能的过程安全时间PST[5],以避免真实事故的发生。

图1 失效传播过程示意图
2 基于极大代数的失效传播分析 2.1 极大代数简介

极大代数于上世纪60年代提出,也叫路径代数,是定义在运算符{max,+}或{min,+}上的代数系。上世纪90年代,Cohen等学者最早将极大代数方法引入控制理论[6],将一类非线性控制系统在极大代数意义下线性化,进而求解系统相关性能[7]。Gunawardena等进一步扩展了极大代数理论在控制系统中的应用,引入max与min混合的操作符,形成极大极小代数方法[8]

定义在{max,+}上的极大代数运算法则在后文称为max-plus运算法则,其定义域为实数域与负无穷大的集合:

$\Re \triangleq \mathbb{R}\cup \left\{ -\infty \right\}$

极大代数意义下的加法和乘法分别定义为

$\left\{ \begin{matrix} a\oplus b\triangleq \max \left\{ a,b \right\}, \\ a\otimes b\triangleq a+b. \\ \end{matrix} \right.$

定义在{min,+}上的极大代数运算法则在后文称为min-plus运算法则,其运算规则定义与max-plus运算法则类似,只是其max运算法则替换为min运算法则,且定义域与零元的定义与max-plus运算法则呈对偶关系。

极大代数方法适用于局部影响通过迭代传播影响系统特性的问题,如局部器件加工对整个生产线的性能影响[7]和机器学习中的置信传播问题[9]等。极大代数方法在铁路控制领域中被用于求解铁路局部运营延时的传递[10]和运营时间表的稳定性问题[11]等。本文采用极大代数来描述失效在系统中的传播与控制过程,通过极大代数的运算来表征局部的失效通过逐步迭代影响系统行为的过程,并进一步讨论模型的性质与求解。

2.2 基于极大代数的失效传播过程

本节提出使用min-plus关系来描述失效在系统中的传播过程。描述失效的局部扩散传播过程应包括以下2方面属性:

1) 失效传播的逻辑链条关系: 对失效A的的描述包括直接导致A发生的其他失效preA1和preA2,以及A导致的后续失效postA1和postA2,如图2所示。

图2 失效传播属性示意图

2) 局部失效在传播过程中的时间延迟,如图2中的t1t4.

定义1 失效传播矩阵ΦSN×N矩阵,N为系统中的局部失效模式种类数量。如第i种失效发生,经过tij延时后导致第j种失效发生,则 ΦS(i,j)=tij; 如第i种失效发生,不影响第j种失效的状态,则ΦS(i,j)=εε $\triangleq $∞为min-plus法则中的加法零元。

可以看出,失效传播过程是一个“或逻辑”,即: 任一前级失效发生,均可能导致后级失效发生,迭代计算应取多个传播路径上的累计时间最小值。因此采用min-plus法则描述失效的传播过程: 由一个初始状态开始,通过min-plus运算法则,迭代得到最终的失效传播状态。用一个N维向量表示系统状态:

X=[X1,X2,…,XN]T.
其中Xi表示第i种失效的发生时间令X(i)=xi,如该失效还未发生,则X(i)=∞,表示该失效发生时刻未知。

X0表示失效初始态,Xk表示失效经k次迭代后的状态,X为最终状态。失效经一次传递的系统状态变化过程可用极大代数中的矩阵乘法规则表示:

Xk+1=ΦSXk.

失效经多次传递的过程可用极大代数中的幂运算表达:

$\Phi _{S}^{k}=\underbrace{{{\Phi }_{S}}\otimes {{\Phi }_{S}}\otimes \cdots \otimes {{\Phi }_{S}}.}_{k个{{\Phi }_{S}}}$

系统的最终状态是多个传递过程效应的叠加,X最终状态为

$\left\{ \begin{matrix} \Phi _{S}^{*}=E\oplus {{\Phi }_{S}}\oplus \Phi _{S}^{2}\oplus \cdots \oplus \Phi _{S}^{N-1}, \\ X=\Phi _{S}^{*}{{X}_{0}}. \\ \end{matrix} \right.$ (1)
其中E为极大代数意义下的单位阵,其对角线元素为乘法零元e $\triangleq $0,其余元素为ε

图2系统,其失效传播矩阵为

${{\Phi }_{S}}=\left[ \begin{array}{*{35}{l}} \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ {{t}_{1}} & {{t}_{2}} & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & {{t}_{3}} & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & {{t}_{4}} & \varepsilon & \varepsilon \\ \end{array} \right].$

假设系统的初始状态为在时刻t0有preA1发生,即:

X0=[t0,∞,∞,∞,∞]T.

根据式(1)计算得到最终的失效状态为

X=X0X1X2= [t0,∞,t0+t1,t0+t1+t3,t0+t1+t4]T.

2.3 基于极大代数的失效控制过程

本节提出引入max-plus关系来描述失效在系统中的控制过程。与失效传播过程类似,失效的控制过程同样包括逻辑链条关系和时间延迟两个方面的属性。定义类似的矩阵ΦE描述这2个属性。用Y0表示失效控制过程的初始状态,Y0基于失效传播过程的最终状态来设置:

1) 如X(i)=∞(表示失效始终未发生),则 Y0(i)=-∞(表示该失效从不存在);

2) 如X(i)=T(表示该失效在时刻T发生),则Y0(i)=∞(表示该失效在初始状态时存在且消失时刻不确定);

3) 如初始值设置失效i在时刻τ0消失,则 Y0(i)=τ0

确定Y0后,通过以下循环迭代式,可得到失效控制的最终状态Y

Y'k+1=ΦEYk (2)
Yk+1=min{|Y'k+1|,|Yk|}. (3)
其中,式(2)为标准的max-plus迭代运算,式(3)中的min操作是为了处理迭代过程中出现的状态特殊值的影响。失效控制过程是 “与逻辑”过程,只有当一种失效的所有前级失效均消失,该失效才会消失,迭代计算应取多个控制路径上的累计时间最大值,因此采用max-plus法则描述失效的传播过程,迭代运算中产生±∞元素时,如前一状态为确定数值,则后续状态应保持该数值。

图2所示的示例系统,设其失效控制矩阵为

${{\Phi }_{E}}=\left[ \begin{array}{*{35}{l}} \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ {{\tau }_{1}} & {{\tau }_{2}} & \varepsilon & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & {{\tau }_{3}} & \varepsilon & \varepsilon \\ \varepsilon & \varepsilon & \varepsilon & \varepsilon & \varepsilon \\ \end{array} \right].$

注意ΦSΦE并不对称:

ΦS(5,3)=t3, ΦE(5,3)=ε. (4)

式(4)表示A可以引发postA2,但A消失却不会导致postA2随之消失。这是一类失效在传播过程中的重要特性,本文提出的方法可以很好地分析这种特性。

假设preA1于时刻τ0消失,则失效控制过程的初始态为

Y0=[τ0,-∞,∞,∞,∞]T.

使用式(2)和(3)迭代,可以得到失效控制过程的最终状态为

Y=[τ0,-∞,τ0+τ1,τ0+τ1+τ2,∞]T.

2.4 基于极大代数的失效分析方法

基于极大代数的失效分析的步骤为:

1) 根据系统安全功能确定需分析的系统危害,即系统边界的危险失效。

2) 根据节2.2和2.3提出的方法,计算失效的危害暴露时间,系统危害受控需满足:

Tsf(h)=Y(h)X(h)<PSTh. (5)
其中: h表示待分析的系统边界危险失效索引号,PSTh表示该失效的过程安全时间,即可容忍的危险输出持续时间。 X(h)通过式(1)获得,Y(h)通过式(2)和(3)获得。

可以分别从以下2种情况,说明式(5)的满足性:

1) 如危害不发生,则Y(k)=-∞,X(k)=∞,Y(k)-X(k)=-∞<PSTh,满足式(5)。

2) 如危害发生,X(k)表示该危害发生的延时,Y(k)表示危害被控制的延时,满足式(5)代表风险在系统可接受的范围,否则系统风险将不可接受。

3 CTCS系统实例分析

本章通过对中国高速铁路CTCS-3级列车控制系统[12](后文简称为CTCS)进行交互失效的实例分析,以验证本文提出的分析方法的有效性。

3.1 CTCS简介与系统结构

CTCS系统是中国应用于大铁客运专线的铁路信号系统,是中国高速铁路的重要装备。它的主要特点是利用GSM-R实现车地双向无线通信,从而实现列车运行速度和追踪间隔的实时防护功能,监督列车的安全运行。

CTCS系统结构及其各部分的信息交互示意图如图3所示。系统包含的主要设备包括列控车载防护(ATP)设备、无线闭塞中心(RBC)设备、 GSM-R通信网络、地面列控中心(TCC)、 轨道电路、应答器、车站联锁、临时限速服务器和CTC等,地面操作员和列车司机等人员通过与设备的交互共同完成系统的安全控制功能。

图3 CTCS系统结构及信息交互示意图
3.2 失效模式及危害分析

本文选取信息交互中的失效作为分析对象。考虑模型应能区分失效是否可被检测,本文采用SHARD方法[13]进行失效模式定义,如表1所示。

表1 失效模式分类
组别失效模式符号表示
行为 提供 行为缺失 (omission) 预期外的行为 (commission)oc
数值 可检测到的错误 (detectable error) 不可检测到的错误 (undetectable error) du
时间 过早 (earlier) 过晚 (later)el

根据图3,可以得到系统的失效传播结构。结合信息失效模式定义,根据各系统的处理机制与延时、传输特性以及延时,即可得到系统的ΦSΦE

根据CTCS系统危害定义,选取图3中“I37牵制动命令”中的“未给出正确制动命令”失效模式作为系统危害进行结果分析。以下给出2个典型的分析示例。

3.3 临时限速(TSR)功能分析

临时限速信息I44是应答器与车载ATP的交互信息,用于在C2模式下告知车载ATP前方线路的临时限速。采用图3中的信息流标号和表1中的失效模式标号共同表示特定失效模式,例如“I44临时限速信息”丢失的失效模式索引号用I44∶o表示,X(I44∶o)和Y(I44∶o)分别表示临时限速信息丢失导致“I37未给出正确制动命令”的开始时刻和结束时刻,Tsf(I44∶o)表示其持续时间。X(I44∶o)=30 s,Y(I44∶o)=∞,根据式(5)得到:

Tsf(I44∶o)=∞>PSTh. (1)

分析发现Y(I44∶o)=∞是由于失效模式I44∶o传播的不对称特性导致:

ΦS(I44∶o,I37u)=TS12, ΦE(I44∶o,I37u)=ε.
其中TS12表示图3中“S12 车载ATP”的处理延时。上式所代表的具体意义为: TSR信息丢失后(I44∶o发生),车载ATP不能得知前方线路的临时限速信息,在经过车载ATP处理延时TS12后,给出有偏差的牵引制动信号(I37∶u发生),导致列车超速。此后,即使TSR信息传输通道恢复(I44∶o结束),由于应答器信息接收窗口限制,已经经过的列车无法再次更新信息,使得车载控制器纠正该错误信息(I37∶u结束)。

为消除I44传输失效的不对称性造成的影响,CTCS系统采取的措施包括:

1) 冗余设计: 工程设计中,通过合理设计应答器布置间距,配置各应答器的管辖数据范围,使得各应答器给出的TSR范围相互覆盖,任一应答器的丢失不会导致信息缺失的失效模式。

2) 差异化设计: 设计应答器链接信息I43,并在工程设计中,根据每个应答器的位置配置合理的 参数,使用I43告知车载ATP下一个应答器的距离、规定下一个应答器数据丢失后车载ATP应进行的安全反应。

工程设计中的应答器距离布置和各应答器的参数配置是一项繁琐而关键的工作,它的作用之一就是控制应答器信息丢失对系统造成的持续影响。这项工作对系统安全的重要性也从本文计算分析中得到佐证。

3.4 进路信息分析

进路信息是一类重要信息,用于向列车授权可以安全进入进路。在CTCS系统的不同工作模式下,进路信息可以通过地面信号显示(I25)、 轨道电路发码(I28)和移动授权控制(I30)三个不同路径传递至列车。

分别在这3种路径下计算失效模式I25∶u、 I28∶u和I30∶u的Tsf。设置典型参数为: 区间轨道电路长度1 000 m,进路接近区段2 400 m,联锁、 TCC、 RBC和车载ATP等自动控制设备的运行周期均为0.5 s,机车信号反应时间4 s,司机确认信号时间15 s。计算得到Tsf(I25∶u)、 Tsf(I28∶u)和Tsf(I30∶u)分别为74.5、 29.5和2.5 s。

对比结果可以看出: 地面信号控制模式下,系统受进路信息瞬态错误的影响最大,轨道电路发码控制模式下次之,RBC移动授权控制模式下影响最小。这个差异一部分来源于进路信号接收、列车接收轨道发码和无线车地通信的更新频率的差异,另一部分来源于人、机车信号和无线通信的反应时间差异。

由于Tsf形成对工程设计和区间速度等安全关键参数的约束,不同的Tsf也表明了不同模式对安全相关的系统性能的限制。对地面进路信号控制模式,最大制约因素是接近区段的设置,体现为 ΦE(I45∶u,I36∶u)。工程设计中,接近区段的数量和长度都会受到限制,因此,减小Tsf(I25∶u)的余地不大。对轨道电路发码控制模式,最大制约因素是轨道电路的长度ΦE((I40∶u,I37∶u)。Tsf(I28∶u)比Tsf(I25∶u)有一定改善,但对比前两者,基于无线车地通信方式有明显的优势,能够最大限度地减小失效在系统中的滞后效应,分析结果也体现了C3控制模式的优越性。

4 结 论

本文提出基于极大代数的失效传播分析方法,可针对存在复杂交互的多模块协作系统建立失效传播与控制模型,进行定量的失效传播与控制分析。通过CTCS系统的示例分析,表明本方法能够在整系统的角度分析失效的传播机制,有效识别系统风险,为后续工程设计提供相关的功能及参数约束。

参考文献
[1] Leveson N. Engineering a Safer World:Systems Thinking Applied to Safety[M]. Massachusetts:Mit Press, 2011.
[2] Jahanian F, Mok A K. Safety analysis of timing properties in real-time systems[J]. IEEE Transactions on Software Engineering, 1986, 12(9):890-904.
[3] Fenelon P, McDermid J A. An integrated tool set for software safety analysis[J]. Journal of Systems and Software, 1993, 21(3):279-290.
[4] Leveson N G, Stolzy J L. Safety analysis using Petri nets[J]. IEEE Transactions on Software Engineering, 1987, SE-13(3):386-397.
[5] CENELEC. EN 50129 Railway Applications:Safety-related Electronic Systems for Signalling[S]. London, UK:British Standards Institution (BSI), 2003.
[6] Baccelli F, Cohen G, Olsder G J, et al. Synchronization and Linearity:An Algebra for Discrete Event Systems[M]. New York, NY, USA:John Wiley & Sons Ltd, 1992.
[7] 郑大钟, 赵千川. 离散事件动态系统[M]. 北京:淸华大学出版社, 2001.ZHENG Dazhong, ZHAO Qianchuan. Discrete Event Dynamic Systems[M]. Beijing:Tsinghua University Press, 2001. (in Chinese)
[8] Gunawardena J. Min-max functions[J]. Discrete Event Dynamic Systems, 1994, 4(4):377-407.
[9] Yedidia J S, Freeman W T, Weiss Y. Understanding belief propagation and its generalizations[J]. Exploring artificial intelligence in the new millennium, 2003, 8:236-239.
[10] Goverde R M. A delay propagation algorithm for large-scale railway traffic networks[J]. Transportation Research Part C:Emerging Technologies, 2010, 18(3):269-287.
[11] Goverde R M. Railway timetable stability analysis using max-plus system theory[J]. Transportation Research Part B:Methodological, 2007, 41(2):179-201.
[12] 张曙光. CTCS-3级列控系统总体技术方案[M]. 北京:中国铁道出版社, 2008.ZHANG Shuguang. CTCS-3 Train Control System Technical Specification[M]. Beijing:China Railway Publishing House, 2008. (in Chinese)
[13] Pumfrey D J. The Principled Design of Computer System Safety Analyses[D]. York, UK:University of York, 1999.