Web服务组合的多故障诊断研究成果

基于服务执行矩阵的贝叶斯诊断方法利用多故障诊断推理技术，提出一种求解最小故障行为集的方法，将求得的多个最小故障行为集作为诊断候选，引入贝叶斯公式以计算每一个诊断候选的故障概率，最终选取概率最大的诊断候选作为故障集。

4.6.3.1　相关定义

1987年，Reiter等[176]提出了基于第一原理的多故障诊断方法，在其诊断理论中给出了一种形式化诊断方法，是一种使用深层知识的形式化诊断推理。该方法利用系统的结构和行为等信息，根据实际观测的系统行为与系统描述中应该具有的正确行为之间的不一致，来判断系统存在的故障行为。如果实际观测与系统描述相冲突，那么就说明系统遭遇了一个诊断问题，也就是说，一个或多个系统组件发生了异常；这些与系统描述相冲突的观测就是一个冲突集合。

定义4.50　对于一个Web服务诊断系统DS=（WS，SB，Obs），一个冲突集CS={b1，b2，…，bk}，其中：

（1）WS是一个服务的描述；

（2）SB是服务的行为集合，并且{b1，b2，…，bk}⊆SB；

（3）Obs服务执行的观察集合；

（4）WS∪Obs∪{¬ab（b1），¬ab（b2），…，¬ab（bk）}是不一致的，也就是说{b1，b2，…，bk}必定包含故障行为才导致观测与系统描述冲突，ab（bi）表示行为bi是一个故障行为。

如果一个Web服务中包含冲突，那么需要知道冲突集中的哪些行为能够解释实际观测与系统描述之间的这个冲突，而从冲突集中找出的最小故障行为集就是一组能够解释这个冲突的行为集合，也称为诊断候选。

定义4.51　一个Web服务诊断系统DS=（WS，SB，Obs）存在一个冲突集CS，CS的一个最小故障行为集是一个行为集合mfbs，并且：

（1）∀ci∈CS，ci∩mfbs≠∅，ci是CS中的一个冲突序列；

（2）当且仅当mfbs⊆mfbs′时，∀ci∈CS，mfbs′∩ci≠∅。

从定义4.51可以看出，如果mfbs是冲突集CS的一个最小故障行为集，那么mfbs与CS中的任何冲突序列都至少存在一个相同的行为，且这些相同的行为能够解释冲突序列发生的冲突。

需要强调的是，对于一个冲突集来说，冲突集中并不一定只包含一组最小故障行为集，可能有多个最小冲突集都能用于解释该冲突的发生。

4.6.3.2　求解最小故障行为集

为了获得能够解释实际观察与服务描述不一致的最小故障行为集，我们提出了一种求解最小故障行为集的方法，该方法改进了Abreu[186]提出的用于求解程序故障诊断中的最小碰集的方法，使其适用于求解故障服务的最小故障行为集。

首先，定义一个相似性系数behSim，该相似性系数用于表示行为与异常观测之间的相似程度。

其中，

这里，nf1（i）表示行为i在失败执行中出现的次数，ns1（i）表示行为i在成功执行中出现的次数，nf0（i）表示行为i没有出现在失败执行中的次数。

然后，根据相似性系数排序所有行为，并从系数最大（也就是与异常观测最相关）的行为开始查找，看该行为是否能覆盖所有失败执行。如果行为能覆盖所有失败执行，则认为其是一个最小故障行为集，并将其从行为集合和失败执行中删掉。当检查完所有行为之后，如果行为集合不为空，并且不满足停止条件，那么就迭代寻找能够覆盖所有失败执行的行为组合并验证该组合是否满足最小故障行为集定义。如果该组合是一个最小故障行为集，那么就将该组合放入解集当中，直到行为集合为空或满足停止条件。求解最小行为故障集的具体方法见算法4.6。(www.xing528.com)

算法4.6　get_mfbs（SEM，l，s）

输入：服务执行矩阵SEM，最小故障行为集个数l，搜索停止标准s。

输出：最小故障行为集集合Mset。

在算法4.6中，m表示SEM中的行为个数；cf表示SEM中失败执行的次数总和；rank（behSim，SEM，m）表示根据式4.2计算SEM中m个行为的相似性系数并从大到小排序行为，返回一个行为序列；delete（SEM，i）表示一个新的服务行为矩阵，该矩阵不包含SEM中的第i列；delete（rb，i）表示将rb中的第i个元素删除，并返回删除第i个元素后的数组；delete（dm，j）表示将dm中的第j列元素删除，并返回删除第j列元素后的矩阵；delete（Mset′，1）表示将Mset′中的第1个子集删除，并返回删除第1个子集后的集合；subset（Mset，diag）用于检查diag是否包含Mset中任何一个子集，如果diag包含Mset中任何一个子集，那么返回true，否则返回false，该函数用来验证获得的集合是否是一个最小故障行为集。

4.6.3.3　贝叶斯诊断

在获得最小故障行为集集合Mset={mfbsi|1≤i≤w}后，还需要计算这些最小故障行为集可能是故障的概率，这里w表示集合中最小故障行为集的个数。首先假设行为发生故障的可能都是独立于其他行为的，然后应用贝叶斯概率计算公式计算Mset中每个最小故障行为集对于SEM中的每个执行序列的后验故障概率，计算公式如下：

其中，

这里，succ（mfbsi）表示在所有最小故障行为集mfbsi中的行为成功执行的概率，即：

并且

对于式4.3中的mfbsi的先验故障概率f P（mfbsi），设定为0.01。如果mfbsi中包含k个行为，那么mfbsi的先验概率为

当每次计算得出一个在给定执行序列下的mfbsi的后验概率，都将其作为下一次计算的先验概率。当所有执行序列都被考虑后，mfbsi的最终后验概率也为

这里，对于SEM中的所有执行序列，它们的概率都是相同的，因此可以使用一个变量α来代替所有的f P（SEM（j）），式4.4可以简化为：

又因为所有最小故障行为集的故障概率之和为1，即：

所以

至此已经求得Mset中的所有最小故障行为集的故障概率。对这些概率排序，就能够得到一个具有多个故障行为的诊断解。整个服务故障诊断过程被描述在算法4.7当中。

算法4.7　sem Diag（HD）

输入：历史数据HD。

输出：诊断解d。

在算法4.7中，convert（HD）表示将历史数据HD转换为诊断服务所需要的服务执行矩阵；p（i）=f P（Mset（i），SEM）表示将使用式4.4计算得到的Mset中的第i个最小故障行为集的故障概率赋予p（i）；mv和mid用于记录最大概率和拥有最大故障概率的最小故障行为集编号。