2. 北京邮电大学 电子工程学院, 北京 100876
针对第5代移动通信系统（5G）环境下海量网管数据溯源难、关联挖掘冗余度大的问题，结合时间约束、滑动时间窗和分类层次技术，提出了一种基于网络拓扑的时序告警关联挖掘算法.该算法可以有效缩减候选集，实现对海量网管数据高效压缩和快速溯源.仿真结果表明，改进后的故障溯源候选集在拓扑上具有实际关联性，对比其他关联算法更有效.
2. School of Electronic Engineering, Beijing University of Posts and Telecommunications, Beijing 100876, China
Aiming at solving the problem of difficult traceability of mass network management data and large redundancy of correlation mining in the fifth generation of mobile communications system (5G) environment, sequential alarm correlation mining algorithm based on network topology was proposed by combining with the time constraint, sliding time window and classification hierarchy technology, which effectively reduced candidate sets, and realized the efficiently compressing and rapidly tracing the mass network management data. Simulation verified that the improved candidate set of fault tracing had actual correlation in topology, which was more effective and reliable than other correlation algorithms.
第5代移动通信系统(5G)下需要提供高速率低时延下的高质量通信服务，给通信网络管理提出了新的挑战.在网络设备和网络数据增多的情况下，监控网络快速定位甚至预测故障成为维护网络通信质量的重要手段.面向海量设备在网络拓扑层面进行高精度关联分析，从海量告警数据中对故障根本原因进行精准高效定位的研究，对于减少故障影响提高网络维护质量至关重要.
海量数据的故障溯源，关键是对其进行关联挖掘，告警压缩与关联具有广泛应用[1-3]. He等[4]通过两个模块解决网络告警关联，一是模糊聚类的方法，二是基于FP-growth的分布式机制，在异构分布式网络中取得了较好的结果. Wei等[5]利用贝叶斯网络实现对电力网络告警关联的挖掘，具有高效性和可靠性. Tjhai等[6]利用神经网络结合无监督聚类算法实现对告警策略的过滤，减少误报率.刘洪波等[7]提出了一种基于神经网络的关联告警挖掘算法，解决了传统告警关联算法逻辑推理实现困难的问题.罗明等[8]提出了一种基于加权频繁模式树算法的告警规则自动挖掘方法，实验表明其具有更好的告警压缩比以及告警关联性. Hu等[9]提出了算法针对告警中的频繁模式进行挖掘，可高效处理告警与事件日志. Yan等[10]认为静态告警分析不足以实现告警定位，利用时序告警信息以及相应的动态时间矩阵可以实现对告警的关联分析，从而完成告警定位. Dorgo等[11]利用多时段告警序列挖掘告警数据，完成对告警数据的压缩. Apriori算法[12]是关联算法最经典的算法之一，其可以有效挖掘到关联频繁项集，然而其在效率上不适用于大数据的环境下.有大量文献针对Apriori算法进行优化[13-14].序列模式挖掘(GSP, generalized sequential pattern mining)算法[15]利用树形结构对算法实现了优化，并考虑到了时序信息，有助于对时序关联进行挖掘.此外，大数据场景下，利用并行算法，可以提高算法效率[16].以上研究较少针对网管数据，尤其是终端节点类型增多、告警消息海量且稀疏离散的情况下，算法挖掘结果冗余度较高，故障溯源定位困难.
针对海量网管数据溯源难、关联挖掘冗余度高的问题，笔者提出结合资源拓扑的关联性及现有的数据挖掘算法，引入网络拓扑过滤规则，并结合GSP算法挖掘告警信息的时序关联性.拓扑过滤规则有助于剔除在统计方面相关而实际物理不相关的频繁项集，提升结果可靠性.
1 5G海量网管数据特征分析 1.1 数据源字段采用的网管数据是某市9个时间段的告警信息，每个时间段为6h，时间粒度为1min，共计2.3万条告警信息.其中，告警指纹为告警条目的唯一标识；告警定位对象为告警发生定位到的网元，是最细粒度的定位信息；归属设备网元为定位对象的上一级也有可能与定位对象相同；告警发生时间精确到分钟，统计之后基本每分钟都有大量告警条目；告警标题确定了告警类型；区县ID为地区；网管告警级别与告警标题相对应，告警级别通过数字1~4表示严重程度；设备类型是对于告警设备的描述.
1.2 数据统计特征提取当告警发生在不同的告警专业中时，其告警级别往往不太相同.各告警级别在告警专业内分布如图 1所示，在无线网中告警级别3的告警信息数量较多，无线节点的增加必然导致高危报警的数量增加，海量数据告警压缩和溯源的需求更大.
|
图 1 各告警级别在告警专业内分布 |
告警信息涉及的地域共7个区县，不同地域告警信息专业分布如图 2所示.统计每个地域下告警信息的专业分布，可以看出告警在区县ID为6的地域下发生最频繁，在区县ID为1的地域下发生最稀疏，其中区县ID为6的地域发生的告警集中在无线网，因此选取区县6作为仿真验证的样本.
|
图 2 不同地域告警信息专业分布 |
笔者主要针对无线网的故障溯源进行研究，所以对无线网的222种告警进行了统计，无线网告警类型频率分布如图 3所示，可以看出，部分告警发生得十分频繁.
|
图 3 无线网告警类型频率分布 |
利用给出的资源表，通过OBJECTS无线核心资源表(资源ID和上联资源ID)可以构建无线网络的层级拓扑；通过port传输端口表(端口ID和所属设备ID)和topo_link传输拓扑表(本端ID和对端ID)可以构建出端口与设备的所属关系以及端口与端口间的联系拓扑.构建的无线网拓扑为簇状结构，网元直接存在上下级关系，共计6231个节点，边数为6230，平均度值为13，分支数为13.该方法同样适用于传输网、接入网、光网络的故障溯源.
2.2 故障建模针对现有数据，提取有效数据，告警日志表示为{a1, a2, a3, …}，告警日志具有时间、告警网元、告警类型3个重要特征，即ai=(ti, ni, si).资源拓扑数据可以表示为{(ni, nj), i, j∈(1, 2, …)}，其中ni表示网元节点，网元之间存在连接关系，资源拓扑分为无线网和传输网2个部分.文中使用的数据源为某个市的一定时间段的告警数据，并获取到了其资源拓扑.故障溯源模型如图 4所示.
|
图 4 故障溯源模型 |
1) 关联挖掘.根据时间约束、滑动时间窗和分类层次技术改进传统数据挖掘算法，结合无线网资源拓扑构建过滤规则对时序告警频繁集进行筛选，有效缩减候选集，对海量网管数据高效压缩和溯源.具体改进见第3节.
2) 告警压缩.告警关联频繁项集可作为合并指标.例如，挖掘发现某些特定设备上的特定告警在整个时间段内几乎每分钟都在发生，因此合并推送给网络管理人员，实现告警压缩.
3) 故障溯源.在网络拓扑中验证展示，过滤不存在物理联系的频繁项集，留下存在物理关联的可靠告警频繁项集.这一系列关联告警可以被合并，定位到一个发生故障网元.
3 基于网络拓扑的GSP算法改进针对解决告警实际关联性以及时序性2个问题.对于实际关联性的解决，引入网络拓扑对关联告警进行过滤，更细粒度地划分关联告警.针对告警时序信息，利用时序关联挖掘算法，保存告警事件间的发生顺序.
3.1 基于时序关系的GSP算法改进GSP算法考虑了序列的发生顺序，适用于告警条目在发生时存在时间先后顺序. GSP算法是Apriori算法的扩展算法，其执行过程和Apriori类似. GSP算法的核心思想是：在每一次扫描(pass)数据库时，利用上一次扫描时产生的大序列生成候选序列，并在扫描的同时计算它们的支持度(support)，满足支持度的候选序列作为下次扫描的大序列.第1次扫描时，长度为1的频繁序列模式作为初始的序列. GSP算法[15]最大的特点就在于，引入了时间约束、滑动时间窗和分类层次技术，增加了扫描的约束条件，有效地减少了需要扫描的候选序列的数量，同时还克服了基本序列模型的局限性，更切合实际，减少多余的无用模式的产生.基于时序关系的GSP算法改进代码如算法1所示.
算法1 GSP(S)
1 C1←init－pass(S); // the first pass over S
2 F1←{〈{f}〉|f∈C1, f.count/n≥min sup}; //n is the number of sequence in S
3 for (k=2;Fk－1≠
4 Ck←candidate－gen－SPM(Fk－1);
5 for each data sequence s∈S do //scan the data once
6 for each candidate c∈Ck do
7 if c is contained in s then
8 c.count++//increment the support count
9 end for
10 end for
11 if Ck satisfy T:
12 Fk←{c∈Ck|c.count/n≥min sup}
13 end for
14 return
在原有的GSP算法输出其最长的频繁项集，由于在业务场景中，并不是最长频繁项集中所有项都具有物理关联性，因而这里加入子集输出模块，将挖掘到的最长频繁项集的子集全部输出.此外，伪代码中第11行，判断挖掘出来的频繁项集是否满足拓扑过滤规则，加入了业务背景，当频繁k项集满足拓扑过滤规则时，基于频繁k项集的频繁k+1项集会大大减少，从而减少了计算量.在网元告警场景下在GSP算法内部考虑了序列内告警网元之间的拓扑连接关系，挖掘出有实际物理连接的频繁序列.拓扑筛选的具体过程在3.2节具体说明.
使用GSP算法对告警日志进行处理，采用时间窗口的方式，首先对告警按时间顺序排列，文中按5min为窗口大小，按分钟取每个时间窗口中发生的告警条目，以此作为一条告警项集，然后利用GSP算法挖掘频繁告警集.
3.2 基于网络拓扑的规则筛选结合GSP算法[15]，设计基于网络拓扑的规则筛选代码如算法2所示.
算法2 合网络拓扑的GSP算法
输入：alarm files{a1, a2, a3, …} resource topology files {(ni, nj), i, j∈(1, 2, …)}
1 for item in {(ni, nj), i, j∈(1, 2, …)}:
T[ni, nj]=1
2 Tmp=GSPCk({a1, a2, a3, …})=set([ak1, ak2], [ak3, ak4, ak5], …)
3 Apply Tmp to T, delete [ai, aj] where T[ni, nj]=0
4 Output R, compress original alarm files {a1, a2, a3, …}
输出：R=set([ak1, ak2], [ak3, ak4, ak5], …)
步骤1 根据网络拓扑关系，分别构建无线网和传输网网络拓扑，以邻接矩阵的形式进行存储.
步骤2 利用GSP算法针对告警日志进行关联挖掘，找出时序关联告警.
步骤3 根据网络拓扑计算关联告警的距离d，对告警关联网络进行筛选(消除统计相关影响)，输出得分较高的告警条目，进行拓扑关联.
步骤4 输出关联告警，将原有告警进行压缩.
所提出的基于网络拓扑GSP算法中，第3步应用了拓扑过滤规则发掘关联告警，告警过滤规则为
| $ R=\text{set}\left(\left[a_{i}, a_{j}\right], \forall T\left[n_{i}, n_{j}\right]=1\right) $ |
即只有资源拓扑存在关联，关联告警才具有意义.然而，海量告警具有太多的不确定性，利用图的方法，将告警间的关联呈现为网络，那么关联告警在网络中就是一个连通分支，只要处在同一个连通分支的就是关联告警.当满足拓扑过滤规则时就在2个告警之间连接一条边，如果图中存在n个连通分支，则这些告警分为n类关联告警.
4 仿真结果 4.1 无线网频繁项集根据上述算法，针对某市的各个时间段的告警信息应用改进后的算法进行关联挖掘，关联挖掘结果与传统算法对比结果如表 1所示.
|
表 1 关联挖掘结果与传统算法对比结果 |
由于告警种类十分多且告警条目巨大，所以告警的支持度不高.同时发现有些告警发生先后顺序影响不大，这是因为其同属于同一上级网元，那么有可能是上级网元的故障导致下级网元相继发生故障.此时，告警发生的先后在日志中因为是同时发生，所以不区分先后顺序.基于网络拓扑改进后38~40、43~50的频繁项集不符合关联要求，占比为22%.将观测数量增加到200，改进后的算法去除冗余的比例升高到了40.5%，在压缩的同时提高了关联挖掘的有效性.在表 1中，Min表示入点的告警状态，Mout表示出点的告警状态，O表示置信度，D表示支持度.表 1中标黑部分是传统算法没有挖掘到的关联告警信息，因而可以对比得到利用拓扑过滤GSP算法比传统的关联挖掘算法有效.频繁项集挖掘结果的节点状态如表 2所示.
|
|
表 2 频繁项集挖掘结果的节点状态 |
为了验证结果的可靠性，无线网资源拓扑关联图如图 5所示.在置信度排名中取Top 50关联项集，每个关联项集是有向的，映射到可视化Gephi图中，即为边列表的关系.每一个关联项集中的告警ID都是一个节点，告警ID后面的是告警标题.关联项集中的有向关系就是有向边.可视化中取Top 50个关联项集，图中把每一对有向关系都扩展为有向边.可以看出，挖掘到的关联告警多属于同一个上级网元，在故障处理的时候可以考虑是否是区域性故障.
|
图 5 无线网资源拓扑关联图 |
无线网告警Top 50告警关联局部拓扑如图 6所示，其中相同样式为关联告警.可以发现仅包含19个节点，大多告警信息集中在一个仅有5个节点的簇中，在故障溯源时可持续关注这5个网元，看是否是区域性故障.
|
图 6 Top50告警关联局部拓扑 |
观测挖掘到的频繁项集合，当不考虑拓扑以及时序信息时，挖掘到的告警频繁集中条目较多，且集合间重复较多，无时序关系，拓扑之间也不存在连接关系，因而大部分关联告警是不可靠的.本节提出的关联结果可用于告警故障压缩，在全部数据集上无线网告警压缩比为1.39，传输网故障压缩比为1.25.
4.3 跨域告警关联由于基于网络拓扑的故障溯源将拓扑作为基本处理单元，所以可以直接扩展处理2个不同类型的网络.为了得到跨域网告警关联，对于同一时间同一机房发生的告警信息进行统计，根据统计结果，选取了设备机房号为“611832241”的告警数据，在跨域中主要针对的是“无线网”和“传输网”的跨域关联，应用改进后的GSP算法得到的结果如表 3所示.根据跨域关联结果，共有85项关联规则.规则置信度最高的前7项关联项集为传输网内部告警关联，剩余72项关联项集为跨域关联.
|
|
表 3 跨域关联告警 |
笔者提出了一种基于网络拓扑的时序关联告警挖掘算法，适用于海量告警关联信息挖掘，有助于5G场景下的网络管理.告警数据的重要要素为告警定位网元、告警发生时间及告警类型.通过告警发生时间，将告警条目排序，通过时间窗口利用GSP算法挖掘时序关联告警，然后构建网络资源拓扑，利用拓扑过滤规则，将GSP算法挖掘到的统计关联告警进行过滤，过滤得到的告警条目为真正具有实际意义的关联告警信息.仿真结果证明，所提算法在支持度和置信度都具有较高表现，通过可视化发现告警条目在结构上也存在上下级或同级关联，因此挖掘到的告警条目为可靠告警，从而通过关联告警完成对网络故障的溯源.
| [1] |
Lameski P, Zdravevski E, Koceski S, et al. Suppression of intensive care unit false alarms based on the arterial blood pressure signal[J]. IEEE Access, 2017, 5: 5829-5836. |
| [2] |
Hu W, Chen T, Shah S L. Detection of frequent alarm patterns in industrial alarm floods using itemset mining methods[J]. IEEE Transactions on Industrial Electronics, 2018, 65(9): 7290-7300. DOI:10.1109/TIE.2018.2795573 |
| [3] |
Karoly R, Abonyi J. Multi-temporal sequential pattern mining based improvement of alarm management systems[C]//IEEE International Conference on Systems, Man, and Cybernetics.[S.l.]: IEEE, 2017: 003870-003875.
|
| [4] |
He Q, Zhou W, Xu H, et al. A distributed network alarm correlation analysis mechanism for heterogeneous networks[J]. Journal of Circuits Systems and Computers, 2017, 27(1): 1850012. |
| [5] |
Wei L, Lu M, Zhu H, et al. Alarm correlation analysis method for smart power distribution and utilization communication network based on bayesian networks[C]//International Conference on Frontiers of Manufacturing Science and Measuring Technology. Taiyuan: ATLANTIS Press, 2017: 1259-1264.
|
| [6] |
Tjhai G C, Furnell S M, Papadaki M, et al. A preliminary two-stage alarm correlation and filtering system using SOM neural network and k-means algorithm[J]. Computers & Security, 2010, 29(6): 712-723. |
| [7] |
刘洪波, 陈刚, 宫钦. 基于神经网络的通信网络告警关联分析及应用[J]. 电信技术, 2018(5): 32-35. Liu Hongbo, Chen Gang, Gong Qin. Analysis and application of alarm correlation in communication network based on neural network[J]. Telecommunications Technology, 2018(5): 32-35. DOI:10.3969/j.issn.1000-1247.2018.05.008 |
| [8] |
罗明, 孟传伟, 黄海量. 基于加权频繁模式树的通信网络告警规则挖掘方法[J]. 计算机工程, 2016, 42(4): 190-196. Luo Ming, Meng Chuanwei, Huang Hailiang. Communication network alarm rule mining method based on weighted frequent pattern tree[J]. Computer Engineering, 2016, 42(4): 190-196. DOI:10.3969/j.issn.1000-3428.2016.04.034 |
| [9] |
Hu W, Chen T, Shah S L. Discovering association rules of mode-dependent alarms from alarm and event logs[J]. IEEE Transactions on Control Systems Technology, 2018, 26(3): 971-983. DOI:10.1109/TCST.2017.2695169 |
| [10] |
Yan Limei, Zhou Zhongyuan, Xu Jianjun, et al. Research on the method of fault location of transmission device based on time series of alarm[J]. Power System Protection and Control, 2018, 46(7): 38-48. |
| [11] |
Dorgo G, Abonyi J. Sequence mining based alarm suppression[J]. IEEE Access, 2018(6): 15365-15379. |
| [12] |
Savasere A, Omiecinski E, Navathe S B. An efficient algorithm for mining association rules in large databases[C]//International Conference on Very Large Data Bases.[S.l.]: Morgan Kaufmann Publishers Inc, 1995: 432-444.
|
| [13] |
徐章艳, 刘美玲, 张师超, 等. Apriori算法的三种优化方法[J]. 计算机工程与应用, 2004, 40(36): 190-192. Xu Zhangyan, Liu Meiling, Zhang Shichao, et al. Three optimization methods for Apriori algorithm[J]. Computer Engineering and Applications, 2004, 40(36): 190-192. DOI:10.3321/j.issn:1002-8331.2004.36.059 |
| [14] |
Bodon F. A fast APRIORI implementation[C]//Proceedings of the IEEE Icdm Workshop on Frequent Itemset Mining Implementations[J]. Florida, USA: IEEE Press, 2003, 56-65. |
| [15] |
Srikant R, Agrawal R. Mining sequential patterns: generalizations and performance improvements[C]//International Conference on Extending Database Technology: Advances in Database Technology.[S.l.]: Springer-Verlag, 1996: 3-17.
|
| [16] |
张忠林, 田苗凤, 刘宗成, 等. 大数据环境下关联规则并行分层挖掘算法研究[J]. 计算机科学, 2016, 43(1): 286-289. Zhang Zhonglin, Tian Miaofeng, Liu Zongcheng, et al. Research on parallel hierarchical mining algorithm of association rules in big data environment[J]. Computer Science, 2016, 43(1): 286-289. |