刘婷婷,张长胜,张 斌,王 鹏

(东北大学 计算机科学与工程学院,沈阳 110819) E-mail:549715624@qq.com

1 引 言

可靠性作为SBS系统的服务质量最重要的维度之一[1-3].目前SBS系统的可靠性的相关研究主要分为两类:基于Markov模型[2,4]的方法与基于Petri网的方法[5,6].SBS系统在运行过程中,系统内部服务之间的共享资源以及系统内部信息传递的相互依赖关系的存在,使得系统的成功运行在绝大多数情况下受限于共因失效[2].共因失效泛指的是由于一个因素的发生导致系统多个组件同时失效这一现象.这种失效的诱因可以归结为两种:外部因素(例如,供电故障、共享服务器故障以及共享数据库故障等等)和内部因素(由系统内部的服务故障或者传播途径的故障导致的传播失效).目前绝大多数SBS系统的可靠性的研究[4-6]都假设服务之间相互独立,并没有考虑共因失效.极少数研究[2]考虑共因失效的研究也仅仅考虑了外部因素.为解决上述问题,本文提出一种考虑共因失效的SBS系统的可靠性分析方法.

2 研究背景

2.1 相关研究

对于由系统组件之间的共享资源故障引起的外部共因失效,Scott[7]提出了一种基于事件树模型的可靠性分析方法;Vieria和Richardson[8]提出了多元偏序集的概念,并在分析可靠性的过程中表示软件组件之间的失效相关性;Dai[9]则在提出的可靠性分析方法中用故障树模型合并关联失效事件的组合.Fiondella和Gokhale[10]基于Markov模型提出一种可靠性分析方法,该方法同时考虑了信息在传输过程中的失效和组件对故障的自我修复;Popic[11]提出了一种贝叶斯网络可靠性分析模型.在SBS系统可靠性的研究中只有少数考虑共因失效.其中,Zhou等[3]提出了一种基于分层树结构的SBS系统可靠性分析模型.树结构中的结点只有一个父节点,这一性质导致Zhou的模型中的服务只能受限于一个直接共因失效的诱因.针对上述问题,Peng[2]提出了一种基于Markov的SBS系统可靠性分析模型.近年来,一系列基于二元决策图(binary decision diagram,BDD)的可靠性分析方法被提出[12-14],并应用于多阶段系统的可靠性分析.该类可靠性分析方法利用布尔变量表示系统组件的状态.相比于传统多阶段系统可靠性分析方法[15-17],基于二元决策图的分析方法有更高效的计算复杂度[18,19].因此,本文基于二元决策图提出了一种考虑内部/外部共因失效的SBS系统可靠性分析方法.

2.2 二元决策图相关概念

BDD[20]作为一种基于图的数据结构,最初的设计目的是给离散布尔表达式提供一种高效、简洁的表示形式和操作手段.近年来,BDD已经为成为系统可靠性分析一种重要的表示方法.

BDD是一种有根的、有向的、非循环的基于图的数据结构,基于香农分解定理[20].结构上,BDD由两种类型的结点构成:底端结点和非底端结点.对每一个BDD有且仅有一对0-结点和1-结点,表示布尔表达式的最终结果为0或者为1,底端结点位于整个图结构的末端因此没有出边只有入边.每一个非底端结点都有两条出边,分别称为0-边(else-边)和1-边(then-边),表示该结点代表变量的取值情况.其中,1-边表示结点所输入的值为1,同理0-边表示结点所输入的值为0.基于香农分解定理,BDD中的任何一个非底端结点都能够将该结点代表的布尔表达式编码成if-then-else(ite)格式,

3 考虑内部/外部共因失效的SBS系统可靠性分析方法

3.1 SBS系统可靠性

本文研究的是考虑内部/外部共因失效SBS系统的可靠性分析方法,以下关于共因失效的假设将应用于本文:

1)假设文中研究的系统既受限于内部共因失效又受限于外部共因失效;

2)当内部共因失效发生的情况下,共因失效组[19](common-cause group,CCG)中的服务可能导致传播失效,也可能不导致传播失效;CCG中服务失效的发生以概率εj引起CCG全部服务的失效,若该服务不能导致传播失效,则设εj=0.

3)当外部共因失效发生的情况下,CCG中的全部服务失效.CCG中的wj引发的CCF的发生概率为εj.并且外部失效因素的失效概率与个体失效概率相互独立.

4)本文涉及的参数在SBS系统运行之前已经给定.在本文提出的可靠性分析模型中,假设SBS系统与系统中的服务只有两种状态:成功运行和运行失效.

设SBS系统有n个服务,xj(j=1,…n)为系统中服务的状态指示变量,其中xj=0表示服务j在系统运行前失效,对应的,xj=1表示服务j在系统运行前成功运行,设x是元素的状态向量,x=(x1,…,xn).SBS系统的状态可以表达为n个独立服务的状态指示变量x1,…,xn的二元函数Q(x).Q(x)是x的二元方程,表达的是SBS系统结构方程,其中Q(x)=0对应的表示系统失效,Q(x)=1对应的表示系统成功运行.SBS系统可靠性分析的目标就是得到系统成功运行的概率,也就是Pr(Q(x)=1).

而服务xj的不可靠性为qj=Pr(xj=0),对应的可靠性为pj=1-qj.服务的失效方程为Qj=qj.在外部共因失效的情况下,εj表示CCGwj的CCF出现概率.在内部共因失效情况下,εj表示由服务xj的失效引起的传播失效的概率,服务xj的单独失效概率为vj=qj(1-εj).由服务xj引起的整个CCGwm的传播失效的失效概率就为wj=qjεj.

3.2 SBS系统可靠性的二元决策图表示法

根据故障树构造一个二元决策图,每一个二元决策图的变量代表一个故障树中基本事件,根据启发式算法,决策图中的基本事件被安排了一个索引.然后对故障树使用深度优先算法,在此过程中对应的二元决策图根据下列规则,通过一种自底向上的方法递归的构建起来,如下,

GF=ite(x′,Gx′=1,Gx′=0)ite(y′,Fy′=1,Fy′=0)

(1)

=ite(x′,G1,G2)ite(y′,F1,F2)

其中G和F代表已经遍历过的子故障树相对应的逻辑表达式;Gi和Fi对应代表G和F的子表达式;符号◇表示逻辑操作AND或者OR中的一种.前面提到的索引表示输入列表中布尔变量的顺序.更准确的说,规则(1)用于合并代表G和F逻辑表达式的子二元决策图模型,合并称为一个二元决策图模型.为了应用规则(1),需要将两个根节点的顺序被比较,例如,G为x′同时F为y′.如果x′和y′拥有相同的顺序,例如,他们属于相同的元素,则规则(1)将被应用到他们的子节点;否则,顺序更小的变量成为合并二元决策图的新的根节点,然后规则(1)应用到所有顺序比该节点更小的子结点,其他的子二元决策图模型则作为一个整体.直到子表达式(Gi,Fi)中的一个变成了常量′1′或者′0′之前,整个规则被递归的应用到子表达式之间的逻辑操作.

3.3 基于BDD的可靠性分析方法

在内部共因失效发生的情况下,本文定义ej作为SBS系统中服务j的产生传播失效事件.据上小节的定义,传播失效事件ej的发生概率可以给定为:

Pr{ej}=wj=qjεj

在外部共因失效发生的情况下,本文定义ej用于表示CCG中的wj引发的外部共因失效事件,该事件的概率可以给定为:

Pr{ej}=εj

给定系统结构方程φh,利用已知信息完成系统结构方程可以得到系统失效的逻辑表达式.利用故障树结点表示SBS系统中服务,用AND门和OR门表示逻辑关系中的与关系和或关系就可以得到SBS系统可靠性的故障树模型.在上述故障树模型的基础上,本文提出的SBS分析法可以由以下三步进行分析:

Step1.故障树模型的扩展

根据SBS系统所涉及的内部/外部共因失效,将基本故障树模型扩展为包含共因失效关系的故障树模型.扩展的基本思想是:利用逻辑OR门将引起共因失效事件和由它引起的失效服务集合连接到一起.根据共因失效类型的不同,分为两种情况讨论:

内部共因失效情况:对于CCG内的每一个元素wj,需要在SBS系统的故障树模型内添加一个OR门,并且将wj内所涉及的所有服务的原始失效事件和该传播失效事件都连接到该OR门.对于上述所有事件,原始失效事件与传播失效事件之间相互独立.

外部共因失效情况:对于至少出现在一个CCG内的元素,添加一个OR门连接原始失效事件与所有CCG影响的元素.

Step2.SBS系统的二元决策图模型的生成

利用传统方法生成二元决策图模型,需要注意的是,规则(1)在这一步骤中被应用于从扩展的故障树模型中生成二元决策图模型.

Step3.SBS系统的二元决策图模型的代入求解

4 实例分析

本小节将对一个包含5个具体服务的SBS系统进行可靠性分析.首先,对实例系统进行介绍;然后,对内部/外部共因失效进行分情况讨论;最后,根据得到的数值结果与传统BDD可靠性分析方法比较.

4.1 实例介绍

实例系统是一个旅游景点自动导航应用,各服务之间的逻辑关系如图1所示：

图1 SBS系统实例Fig.1 SBS system instance

其中,系统首先要进行景点定位,这一步骤可以通过服务3提供的GPS定位;也可以通过服务1上传景点照片;根据上传的照片,服务2对景点进行定位;在进行完定位操作之后,服务4将根据定位结果将该景点的介绍信息发送给使用者;最后,服务5将后续游览路线推荐信息发送给使用者.根据图1,该系统可靠性的故障树模型如图2所示.

图2 SBS系统故障树模型实例Fig.2 SBS system fault tree model instance

在实际运行过程中,实例系统存在以下三点可能导致共因失效:服务2和服务4共享景点数据库;服务3和服务5共享地理数据库;服务2又依赖于服务1传递的信息.具体情况如图3所示.

图3 SBS系统资源共享情况实例Fig.3 SBS system resource sharing instance

4.2 内部共因失效情况

系统中包含了一组内部共因失效CCGw1={1,2},其中服务1到服务2的传播失效概率为ε1.剩余服务不能引起传播失效,所以有ε2=ε3=ε4=ε5=0.

Step1.扩展基本故障树模型,使其包含内部共因失效事件.添加一个逻辑OR门连接CCGw1中全部服务的原始失效事件和传播失效事件,如图4所示.

图4 SBS系统内部共因失效故障树模型实例Fig.4 Example of common cause failure tree model in SBS interior

Step2.生成BDD模型.应用BDD操作规则(1),并采用序列5→4→3→2→1→w1,得到BDD如图5所示.

图5 SBS系统内部共因失效BDD模型实例Fig.5 Example of common cause failure BDD model in SBS interior

Step3.SBS系统可靠性计算.根据上一步生成的BDD模型,易见从根结点到底端结点“0”有两条路径:

因此,SBS系统的可靠性可以通过如下公式得到,

4.3 外部共因失效情况

图6 SBS系统外部共因失效故障树模型实例Fig.6 Example of common fault failure tree model in SBS system external

系统中包含了两组内部共因失效CCGw2={2,5}、w3={3,4},这两组外部共因失效的发生概率为ε2,ε3.

Step1.扩展基本故障树模型,使其包含外部共因失效事件.为CCG中的每一个服务添加一个逻辑OR门,连接该服务的原始失效事件和共因失效事件,如图6所示.

Step2.生成BDD模型.应用BDD操作规则,并采用序列e2→e1→5→4→3→2→1,得到BDD如图7所示.

图7 实例SBS系统外部共因失效BDD模型Fig.7 Example of common cause failure BDD model in SBS system external

Step3.SBS系统可靠性计算.根据上一步生成的BDD模型,易见从根结点到底端结点“0”有两条路径:

因此,SBS系统的可靠性可以通过如下公式得到,

4.4 结果分析

表1显示了实例SBS系统所有服务的可靠性;

表1 实例SBS系统服务可靠性Table 1 SBS system service reliability instance

表2显示SBS系统所有服务传播失效事件的发生概率;

表2 SBS系统服务传播失效事件概率实例Table 2 SBS system services propagate failure probability instances

表3显示了2个共享资源的失效发生概率;

表3 SBS系统服务共享资源失效事件概率实例Table 3 SBS system service shared resource failure event probability instance

根据表1、表2及表3中的已知数据以及故障树模型的建立可以求得考虑内部/外部共因失效的SBS可靠性分别为95.67%、77.81%.作为对比,利用传统BDD方法不考虑共因失效的可靠性为96.35%,考虑共因失效的结果分别下降了0.71%和19.2%.综上,在SBS系统可靠性分析中考虑内部/外部共因失效对于求解结果的精度有着重要的意义;同时,本文提出的算法可有效的计算受限于共因失效的SBS系统的可靠性.

5 结 论

针对现有SBS系统可靠性研究没有考虑外部/内部共因失效这一问题,本文提出了一种基于二元决策图的SBS可靠性分析方法.通过对实例的分析可知,在研究SBS系统可靠性的过程中是否考虑内部/外部共因失效对求解精度有着重要的影响,本文提出分析方法可以有效的计算受限于共因失效的SBS系统的可靠性.