网络告警是一种特殊的由被管系统主动发送给网管中心的通知，告警数据反映了网络运行过程中某些故障等异常情况的发生，是网络故障的信息化表示.工作人员通过监控系统实时呈现的告警数据了解网络的运行状况，进而分析、定位故障.然而，由于网络中设备繁多，关联复杂，一台设备的故障可能产生多条告警，或者导致与该设备相连的其他设备也产生大量告警，引发告警风暴.数量庞大的告警信息不但不能帮助网管人员定位告警源、确定故障原因，反而会将反映故障本质的根告警淹没，加大故障诊断难度.告警关联性分析可以在网管人员处理告警数据之前对告警进行过滤、合并和转化，进而发现根告警，减少呈现给网管人员告警的数量，辅助工作人员及时准确地定位故障^[1-2].

目前，告警关联性分析方法主要有以下几种^[3-9]：基于编码的告警关联性分析，但该方法需要构建精确的网络对象模型，因此在大型、复杂的综合通信网络中难以应用；基于贝叶斯的告警关联性分析，该方法虽然可以有效克服告警事件的不确定性，但从实际环境中获取先验概率比较困难，且计算每个节点的相关概率是一个NP-hard问题；基于事例的告警关联性分析，但该方法对于网络变化反应不敏感，处理过程较复杂且费时；基于神经网络的告警关联性分析，该方法在告警信息包含噪声的情况下，也能较为准确地识别相关联的告警，但神经网络的学习严重依赖于学习样本，对样本数据的准确性、完整性具有较高的要求；基于规则的告警关联性分析，该方法因其表达直观、表示灵活、便于理解和推理等优点，受到广泛的应用.基于规则的告警关联性分析方法将故障诊断领域的知识以规则的形式存放在知识库中，当网络中的告警报上来以后，它能调用相应的规则推理引擎进行启发式推理，发现根源告警.常用的规则推理算法包括Treat、Leaps、Rete等，其中Rete作为目前效率最高的演绎推理算法成为现有规则推理引擎的主流算法. Rete算法通过节点共享的方式降低模式匹配的时间花销，从而高效地处理大规模数据^{[3, 10-12]}.因此，笔者将Rete算法应用于告警数据的关联性分析，研究基于Rete规则推理的告警关联性分析.

然而，在实际复杂多变的网络环境中，由于网络故障引发的链路中断、拥塞等问题可能导致告警数据的缺失，使得现有Rete算法难以满足根源告警推理准确性、实时性的需求.针对以上问题，笔者提出了一种改进的规则推理算法Im_Rete.该算法结合网络告警数据的特点，分别采用面向告警缺失的模糊逻辑推理策略和基于概率关联模型的事实传播策略，在提高推理准确性的同时，平衡推理速度，有效减少呈现给网管人员的告警冗余，辅助工作人员对网络故障进行及时、准确地诊断，对维护网络的稳定运行具有重要意义^[13-14].

1 相关工作

Rete算法由Forgy^[1]提出，是一种高效的模式匹配算法. Rete算法根据规则的条件编译生成一个树形结构的判别网络作为事实的传播路径，每个规则前件是网络中的一个节点，运行时将事实送入判别网络进行模式匹配，匹配完全的规则即被激活. Rete的规则判别网络如图 1所示.

Rete网络分为Alpha和Beta网络. Alpha网络包括root、type、select和Alpha memory节点. root是所有事实对象(Facts)进入Rete网络的入口；type节点根据事实对象的类型对其过滤，将符合条件的事实向后继节点传播；select节点根据模式的属性对事实进行过滤，将符合条件的事实向后继节点传播，直至alpha memory. Beta网络包括beta memory和join节点. join节点是双输入节点，其中左输入通常为beta memory中的事实对象元组，右输入通常是一个事实对象. join节点对事实间的属性关系进行约束，如条件符合，则对2个输入进行join连接操作，且将结果生成元组存储在beta memory，并向后继节点传播.当事实传播至叶子节点时，表示该节点对应的规则被完全匹配，则将该规则加入议程Agenda.

Rete算法作为规则推理引擎的核心，受到了国内外学者的广泛关注.例如，Sottara等^[6]对Rete规则的语法逻辑进行了扩展，即根据规则的逻辑操作符构造一个语法树，并在该树的基础上建立Rete判别网络，逻辑符作为网络中的一个判别节点参与匹配操作，从而减少额外的规则拆分开销，增强Rete算法的通用性；Xiao等^[7]将Beta内存进行单元划分，每个单元设置唯一标识，通过Hash函数进行索引，以提高模式匹配的速度；汪成亮等^[8]提出了最小传输代价的Rete分布的算法，以解决智能环境中基于Rete的规则推理引擎需要将数据集中到sink节点，导致传感器网络中数据传输量过大的问题；Sun等^[9]采取有穷自动机理论的思想，提出了一种基于共享度模型的Rete网络构建方法，通过提高判别网络节点共享度，提高匹配速度；Zhao等^[16]提出了一种基于XML格式规则的Rete算法，该算法基于XML的规则描述方法，实现了规则描述文件和实体类调用的特定逻辑的松散耦合体系结构，以提高规则谓词的扩展能力以及规则共享性.

2 改进的规则推理算法Im_Rete

Rete算法的提出极大提高了规则引擎的匹配效率，为了提高根告警分析的效率，笔者将Rete算法应用于告警数据的关联性分析.系统将接收到的实时告警与规则进行模式匹配，分析出相关联的告警，进而发现根告警，以辅助网管人员快速地进行故障定位和诊断.然而，Rete算法是一个基于网络的完全匹配算法，在应用于网络告警数据中时，由于实际网络环境复杂多变，网络故障引发的链路中断、拥塞、高时延、高丢包率等问题可能导致告警数据的缺失，使得告警序列难以精确匹配对应的规则，从而影响推理的准确性，难以满足故障诊断中根告警分析准确性需求.

针对上述问题，笔者提出一种改进的规则推理算法Im_Rete.该算法根据网络告警数据的特点，采用面向告警缺失的模糊推理策略，以适应网络故障带来的告警缺失问题；同时考虑到告警传播可能导致的告警风暴问题，算法参考近似化Rete的思想^[4]，引入基于概率关联模型的事实传播策略，在提高推理准确性的同时平衡推理速度，能够更加有效地对告警进行关联性分析.

2.1 面向告警缺失的模糊逻辑推理策略

传统告警关联性分析中规则的表示如式(1)所示，其中P_in表示第i个规则中的第n个模式，P_i表示第i个规则的结论.

$ {P_{i1}},{P_{i2}}, \cdots ,{P_{in}} \to {P_i} $

(1)

Rete算法是一个完全匹配算法，对于式(1)，如果P_i1, P_i2, …, P_in的取值都为真，该规则才可被激活.即事实在判别网络进行传播时，如果任意某次join操作失败，则该规则匹配失败.这种精确匹配的方式难以适应网络故障带来的告警缺失问题，对此采用一种面向告警缺失的模糊推理策略，^[15]该策略为规则前件赋予不同的权重，如果某次join操作失败，该模式对规则的重要程度不高，则可忽略此次失败，从而增加推理网络的容错性^[5].改进后的规则表示为

$ {w_{i1}}{P_{i1}},{w_{i2}}{P_{i2}}, \cdots ,{w_{in}}{P_{in}} \to {P_i} $

(2)

其中w_ij(j=1, 2, …, n)是模式P_ij的权重，w_ij≥0且$ \sum\limits_{j = 1}^n {{w_{ij}} = 1} $.定义T(P_ij)为模式P_ij的真度，当事实与模式P_ij相匹配时，T(P_ij)=1；否则T(P_ij)=0.对于一个选定的阈值τ，只要事实匹配的权重和不小于τ，如式(3)所示，即可激活该规则.

$ \sum\limits_{j = 1}^n {{W_{ij}}} T({P_{ij}}) \ge \tau $

(3)

Im_Rete算法采用面向告警缺失的模糊推理策略，基于模糊c-均值(FCM，Fuzzy c-means)聚类为规则前件每个模式设置权重W_each，并设置匹配阈值τ.告警事实在判别网络传播的过程中，当某次join连接操作失败时，如果该规则模式的最小W_each小于(1-τ)，则忽略此次失败.当传播至终端节点(叶子节点)时，如果W_total于事先设定的匹配阈值τ，则激活该规则，否则规则激活失败.其中规则权重的确定对推理的准确性具有重要意义，为了更加准确地确定规则权重，引用FCM算法对告警模糊化获得告警对根告警的模糊隶属度的方法确定权值^[17].

1) 告警量化

告警的每个属性从不同角度反映告警的重要程度.因此，对告警进行模糊化其实就是将告警的各属性值整体进行综合模糊化，告警属性量化是进行告警模糊化的前提.选取以下几个属性：

① 告警节点.告警节点所连接的链路数目大小反映节点位置的重要程度，链路数目越大，重要程度越高.

② 告警级别.告警级别由厂商以及专家预先定义，分别用1~5依次表示告警的级别，数字越大，告警级别越严重.

③ 告警类型.根据TCP/IP协议模型，低层为上层提供服务.若低层发生故障，故障将会传播至使用该低层服务的高层，从而引发较高层产生次生告警，因此低层告警相对重要程度较高.

2) 模糊权值的确定

根据一条告警与根告警的接近程度，定义语言变量评价模糊集F={A₅, A₄, A₃, A₂, A₁}，接近根源告警的程度依次降低.因此对告警J进行模糊化，就是求J对于F的模糊隶属度向量. FCM实现将n个向量u_i(i=1, 2, …, n)划分成c(c取告警等级数5)个模糊簇，然后每个告警以[0, 1]区间某个取值隶属于该聚类.

隶属度矩阵：

$ \mathit{\boldsymbol{U}} = \{ {u_{ij}} \in [0,1]|1 \le i \le c,1 \le j \le n\} $

(4)

隶属度向量归一化处理：

$ \sum\limits_{i = 1}^c {{u_{ij}}} = 1,\forall j = 1,2, \cdots ,n $

(5)

目标函数：

$ J(\mathit{\boldsymbol{U}},{c_1}, \cdots ,{c_c}) = \sum\limits_{i = 1}^c {{J_i}} = \sum\limits_{i = 1}^c {\sum\limits_{j = 1}^n {u_{ij}^m} } d_{ij}^2 $

(6)

其中：c_i(i=1, 2, …, c)为第i个聚类中心，m∈[1, ∞)为加权指数，d_ij为元素j至聚类中心c_i的欧氏距离.构造新的目标函数：

$ \begin{array}{*{20}{c}} {\bar J(\mathit{\boldsymbol{U}},{c_1}, \cdots ,{c_c},{\lambda _1}, \cdots ,{\lambda _n}) = }\\ {J(\mathit{\boldsymbol{U}},{c_1}, \cdots ,{c_c}) + \sum\limits_{j = 1}^n {{\lambda _j}} \left( {\sum\limits_{i = 1}^c {{u_{ij}}} - 1} \right) = }\\ {\sum\limits_{i = 1}^c {\sum\limits_{j = 1}^n {u_{ij}^m} } d_{ij}^2 + \sum\limits_{j = 1}^n {{\lambda _j}} \left( {\sum\limits_{i = 1}^c {{u_{ij}}} - 1} \right)} \end{array} $

(7)

其中λ_j(j=1, 2…, n)是J(U, c₁, c₂，…, c_c)约束式的拉格朗日乘子.对式(7)求导，可得

$ {c_i} = \frac{{\sum\limits_{j = 1}^n {u_{ij}^m} {x_j}}}{{\sum\limits_{j = 1}^n {u_{ij}^m} }} $

(8)

$ {u_{ij}} = \frac{1}{{\sum\limits_{k = 1}^c {{{\left( {\frac{{{d_{ij}}}}{{{d_{kj}}}}} \right)}^{2/(m - 1)}}} }} $

(9)

c_i、u_ij即为目标函数取得最小值的必要条件.

设F={A₅, A₄, A₃, A₂, A₁}模糊语言评价集中对应的权重分别为{w₅, w₄, w₃, w₂, w₁}，则对于模糊隶属度向量为(u_5j, u_4j, u_3j, u_2j, u_1j|j=1, 2, …, n)的告警J，其权值如下：

$ {V_{al}} = \frac{{u{\kern 1pt} {\kern 1pt} 5j{w_5} + {u_{4j}}{w_4} + {u_{3j}}{w_3} + {u_{2j}}{w_2} + {u_{1j}}{w_1}}}{{{w_5} + {w_4} + {w_3} + {w_2} + {w_1}}} $

(10)

2.2 基于概率关联模型的事实传播策略

传统Rete算法在事实匹配阶段将事实传播给节点的每个后继节点，该方法采用完全匹配的方式，效率较低，难以适应告警风暴时根源告警推理实时性的需求.而Im_Rete算法参考近似化Rete的思想，引入基于概率关联模型的事实传播策略^[4]，在提高推理准确性的同时平衡推理速度，能够更加有效地对告警进行关联性分析.基于概率关联模型的事实传播策略是指Im_Rete算法在事实传播给后继节点的过程中基于概率关联模型进行近似化处理以达到提高推理效率的方法. Im_Rete算法通过获取事实传播给后继节点的概率，并对关联概率较低的传播过程进行剪枝，以提高匹配效率.

如图 2所示，定义某一事实fact传播至节点(i-1)的概率为p(i-1)，fact与节点(i-1)匹配成功的概率为p_pass(i-1)，fact在节点(i-1)与i之间的传播概率为p_sp(i-1, i)，则fact传播至节点i的概率p(i)为

$ {p(i) = p(i - 1){p_{{\rm{ pass }}}}(i - 1){p_{{\rm{ sp }}}}(i - 1,i)} $

(11)

$ {{p_{{\rm{ pass }}}}(i - 1) = \frac{{ {\rm{match}} (i - 1)}}{{ {\rm{total}} (i - 1)}}} $

(12)

$ {{p_{{\rm{ sp }}}}(i - 1,i) = \frac{{ {\rm{match}} ((i - 1) \cap i)}}{{ {\rm{match}} (i - 1)}}} $

(13)

其中：match(i-1)表示与节点(i-1)匹配成功的事实数，total(i-1)表示传播至节点(i-1)的总事实数；match((i-1)∩i)表示与节点i和(i-1)均匹配成功的事实数.上述变量可根据历史数据进行统计获取，在进行实时匹配时按照p(i)概率的大小，即当概率大于预先设置的概率阈值时，选择后续分支进行传播，以提高事实传播的速率，减少不必要存储.其中概率阈值的设置对推理效果具有重要影响，设置得过大会导致过剪枝，无法匹配到对应的规则，影响推理的准确性；设置得过小会导致事实传播策略回退至完全传播，从而影响匹配速率.

3 仿真实验结果与分析

实验选取Rete^[1]、Rete_SDM^[9]算法和所提出的Im_Rete算法进行对比，所采用的数据来自于某地区电力通信网网管系统导出的告警数据.仿真实验使用的操作系统为Windows7，运行环境CPU为2.2GHz Intel Core i3，内存为8GB，编程语言为Java1.7，IDE为MyEclipse2017.在不同的规则数和事实数下分别运行Rete、Rete_SDM和Im_Rete算法多次，记录每次算法的运行时间，统计平均值，算法运行结果如图 3、图 4和图 5所示.需要说明的是，结果中的运行时间消耗不包括告警数据预处理的时间以及构建Rete网络的时间.

在推理准确度方面，选取该电力通信网50次故障期间产生的告警数据进行仿真分析，如图 6~8所示.在不同匹配阈值的条件下，Im_Rete算法推理准确度均高于Rete和Rete_SDM算法.由于实际网络环境复杂多变，网络故障引发的链路中断、拥塞、高时延、高丢包率等问题都可能导致告警数据的缺失，Im_Rete算法结合网络告警的特点，采用了面向告警缺失的模糊推理策略，当规则中匹配的模式权重超过匹配阈值时即可激活该规则，从而提高根告警分析的容错性.

其中匹配阈值的选取对于推理的准确性具有重要影响，匹配阈值过小会导致匹配到的规则过多，从而掩盖真实的根告警；匹配阈值过大会导致推理策略回退至完全匹配，从而影响推理的准确性.阈值的选取需要结合具体场景进行反复实验确定.

在推理速度方面，如图 3、图 4和图 5所示，在不同规则数的条件下，Im_Rete算法的推理速度均优于传统Rete算法，与Rete_SDM算法基本一致.这是因为Im_Rete算法采用的面向告警缺失的推理策略会带来额外的开销，在一定程度上会影响算法的推理速度，对此，Im_Rete算法在Rete_SDM算法共享度模型^[9]的基础上采用了基于概率关联模型的事实传播策略，虽然会损失一部分推理精度，但可以提高匹配过程中事实的传播速度，在推理的准确度和速度之间获得良好的平衡，从而更好地适应网络根告警分析实时性、准确性的需求.

4 结束语

针对现有Rete规则推理算法的不足，结合网络告警数据的特点，提出了一种改进的规则推理算法Im_Rete.该算法分别采用面向告警缺失的模糊逻辑推理策略和基于概率关联模型的事实传播策略，以适应网络故障带来的告警缺失以及告警风暴等问题，可以更加快速、准确地对告警进行压缩和过滤，发现根源告警，最后通过仿真实验进行对比分析，结果表明Im_Rete算法在根告警分析方面具有较好的性能.