（信号与信息处理专业论文）基于拓扑约束和数据挖掘的网络故障定位.pdf

北京邮电大学硕士研究生毕业论文摘要 基于拓扑约束和数据挖掘的网络故障定位 摘要 本文结合与企业合作的课题：基于数据挖掘的智能化移动通信 网络故障管理关键技术研究，对基于拓扑约束的关联规则挖掘技术 在移动通信网络故障定位系统中的应用及其实现方案进行了研究。 该课题通过研究移动通信网络及其告警信息的特征，得出告警是 沿着网络拓扑进行传播的这一结论。基于此，本文提出了在关联规则 挖掘算法中引入网络拓扑模型作为约束，对告警数据进行挖掘中的处 理，将没有存在拓扑连接关系的关联规则过滤掉，从而提高挖掘的效 率和正确性。 本文主要针对关联规则经典挖掘算法存在的各种不足，提出采用 f p g r o w t h 非时序关联规则挖掘算法，并在该算法的实现过程中加入 了网络拓扑关系。该算法仅扫描数据库两次，不产生候选集，具有明 显的性能优势，尤其适合我们将要面对的大型数据库，可以节省大量 时间，提高执行效率。 作者参与了b u p t p r i s m i n e r 智能化告警分析原型系统的研发， 对f p g r o w t h 非时序关联规则算法进行了研究和实现，并配合小组成 员把算法集成入b u p t p r i s m i n e r 系统，完成了模块测试、代码维护 和文档编写等工作。 关键词：故障定位拓扑模型数据挖掘关联规则f p g r o w t h 算 法 北京邮电大学硕士研究生毕业论文a b s t r a c t n e t w o r kf a u i rl o c a l i z a t i o n b a s e do nn e t w o r kt o p o l o g ya n dd a t am i n i n g a b s t r a c t b a s e do nt h ep r o j e c td e v e l o p e dc o o p e r a t i v e l yw i t he n t e r p r i s e ：( ( k e y t e c h n i q u e si ni n t e l l i g e n tm o b i l en e t w o r kf a u l tm a n a g e m e n tb a s e do n d a t am i n i n g ) ) ，t h ep a p e rf o c u s e do nt h ea p p l i c a t i o no ft e c h n i q u e so f m i n i n ga s s o c i a t i o nr u l e si nt h em o b i l en e t w o r kf a u l tl o c a l i z a t i o ns y s t e m t h ep r o j e c tr e a c h e sac o n c l u s i o nt h a ta l a r m ss p r e a dt h r o u g hn e t w o r k t o p o l o g y , a f t e rs t u d y i n gt h em o b i l en e t w o r ka n di t sa l a r m s b a s e do nt h e c o n c l u s i o n ，t h ep a p e rp r e s e n t si n t r o d u c i n gn e t w o r kt o p o l o g yi nm i n i n g a s s o c i a t i o nr u l e st oi n c r e a s em i n i n ge f f i c i e n c ya n dv a l i d i t y t h en e t w o r k t o p o l o g yc a nb eu s e dt op r o c e s st h ea l a r md a t ad u r i n gm i n i n g ，t h u s f i l t r a t i n ga l a r m sa n da s s o c i a t i o nr u l e st h a th a v en ot o p o l o g yc o r r e l a t i o n i na l l u s i o nt ot h ed e f i c i e n c yo ft r a d i t i o n a la l g o r i t h m sf o rm i n i n g a s s o c i a t i o nr u l e s ，t h e p a p e rp r e s e n t su s i n gf p - g r o w t ha l g o r i t h ma n d b r i n g sn e t w o r kt o p o l o g yi n t ot h ea l g o r i t h m t h i sa l g o r i t h ms c a n st h e d a t a b a s eo n l yt w i c e ，i sb e s tf o rh u g ed a t a b a s e ，c a ns a v et i m ea n di m p r o v e e x e c u t i o ne f f i c i e n c y t h ea u t h o r p a r t i c i p a t e d i nt h e s t u d ya n dd e v e l o p m e n to ft h e b u p 耶r i s m i n e r i n t e l l i g e n t a l a r m a n a l y s i ss y s t e m c o n c r e t e l y , t h e a u t h o rt o o kp a r ti nr e a l i z i n gt h ef p - g r o w t ha l g o r i t h m ，h e l po t h e rt e a m m e m b e r st oi n t e g r a t et h ea l g o r i t h m si n t ot h eb u p t p r i s m i n e rs y s t e m m e a n w h i l et h e a u t h o r a c c o m p l i s h e d t h em o d u l e t e s t i n g ，c o d e m a i n t e n a n c e ，d o c u m e n tw r i t i n ga n ds oo n k e yw o r d s ：f a u l tl o c a l i z a t i o n t o p o l o g ym o d e l d a t am i n i n g a s s o c i a t i o nr u l e sf p - g r o w t h a l g o r i t h m 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：困丛日期：丝墨：查：兰z 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：! 塑趁日期：丝q 壁：查：兰z 导师签名：二盔 o 北京邮电大学硕十研究生毕业论文第一章绪论 第一章绪论 本章主要介绍了论文的课题背景、电信网络故障定位技术在国内外的发展现 状以及作者在论文期间所作的工作。 1 1 课题背景 本课题依托于北京邮电大学和i b m 中国研究院联合研究的开放课题“基于 数据挖掘的智能化移动通信网络故障管理关键技术研究一。该课题的主要研究内 容是以北京邮电大学模式识别实验室为某省级移动公司开发的t a c a s 告警关联 与分析系统为基础，采用创新的方法和技术，进一步提高告警分析的速度、精度， 减少对人工专家知识的依赖，最终提高故障定位的准确性和效率，以研制出一个 适用于大规模电信网络和海量数据应用环境下的智能化实时故障诊断、影响分析 和故障定位系统。 故障定位是网络故障管理的核心。随着现代通信系统的产生与发展，故障定 位问题备受关注，并且提出了许多故障定位方案。但是通信系统逐渐地日趋复杂 并且提供一些新的性能，因此故障定位方案也需要进一步的改进。在故障定位技 术中常用的是告警关联，即对相同故障源的告警进行分组的处理过程。 传统的电信网络告警关联挖掘，没有与特定的网络拓扑结构相结合，这种方 式存在两大缺陷，首先待挖掘的数据量很大，其次挖掘的关联规则多且冗余。为 了克服这两大缺陷，提出了构建网络物理拓扑模型，通过网络拓扑模型对告警数 据进行挖掘中的处理，将没有存在拓扑连接关系的关联规则过滤掉，从而提高挖 掘的效率和正确性。通过对某省级移动通信的网络结构和实际告警数据进行分析 后，提出采用数据库表来建立和存储网元拓扑关系信息，从而实现网络物理拓扑 的建模。 基于拓扑约束的关联规则挖掘算法，依照建立的拓扑结构模型得到的网元之 间的层次关系，将发生各个告警的各个设备进行层次编码。由拓扑结构体现出的 各网元之间的连接关系，结合故障的传播路径，得到关联规则挖掘过程的约束条 件。在挖掘关联规则过程中，两个或多个项目是否可能连接为一个项集要由这种 约束条件加以限制。采用基于拓扑约束的关联规则挖掘算法，实现了在连接前更 大程度地减少待检测的组合个数，明显降低了工作量，同时保证得到的规则满足 拓扑关系，提高了挖掘告警关联规则过程的时效性和结果的准确性。 第l 页 北京邮电大学硕十研究生毕业论文第一章绪论 采用基于网络拓扑约束的关联规则数据挖掘技术来改进移动通信网络故障 定位系统，就是在这样的背景下提出的。 1 2 故障定位系统综述 1 2 1 故障定位的概念 网络管理卜1 是指对网络的运行状态进行检测和控制，使其能够有效、可靠、 安全、经济地提供服务。国际标准化组织( i s o ) 将网络管理功能划分为配置管 理、性能管理、故障管理、安全管理和计费管理五个领域。故障管理的目的是迅 速发现和纠正网络故障，动态维护网络的有效性。故障管理卜1 的主要功能有告警 监测、故障定位、测试、业务恢复、故障修复以及故障日志维护等。故障定位是 网络故障管理的核心。在通信系统中，故障的发生是不可避免的，对于一个健全 可靠的系统而言，快速隔离并检测出故障是必要的。 故障定位卜1 是通过一些观测的告警信息发现准确根源故障的过程，包括故障 隔离、事件关联以及根故障分析。故障p 1 可以定义为那些引起系统以非正常方式 操作的事件，可分为：1 ) 网络配置错误；2 ) 网络硬件问题，包括网卡故障、 m o d e m 故障、通讯媒体故障、路由器转换故障等；3 ) 网络软件异常，如路由软 件故障、路由表刷新异常、网络激活应用软件异常等；4 ) 网络流量异常，例如 分组风暴等。在通信网络中，一个故障可能引起网管中心的多重告警，其产生原 因是：1 ) 故障重复发生；2 ) 一个业务可能多次调用有故障的组建：3 ) 一个设 备的一个故障产生多个告警；4 ) 多个设备同时检测到同一故障并同时发出告警； 5 ) 故障传播到其他网络产生额外告警。 网络或设备检测到故障，发出描述故障现象的消息称为告警，它是从网络设 备角度对故障的一个描述。组成网络的设备( 组成设备的模块) 是相互影响的， 一个设备发生异常，相关设备会表现出故障征兆，导致每一个相关设备都发出告 警信息，这种现象称为故障的传播特性。由于大部分故障都是不可直接观测的， 系统必须通过已知的告警信息推理出根故障所在。告警可能携带的信息有：产生 告警的网元的i d ，故障类型，时间标签，告警标志符，故障严重级别，故障的 文本描述等r j 。 为了提供快速、可靠、有竞争力的服务，移动通信网络管理系统要适应网络 规模扩张、带宽提高、复杂性增强的变化。随着网络结构规模日益复杂，网络故 障管理越来越困难。网络故障不仅会降低客户的满意度，也会导致经济损失。故 障的发生在所难免，快速检测和定位故障是保障网络稳定运行的关键因素，也是 网络管理的首要任务。 第2 页 北京邮电火学硕士研究生毕业论文第一章绪论 1 2 2 现存的故障定位技术 在故障定位技术中常用的是告警关联，即对相同故障源的告警进行分组的处 理过程。传统上的告警关联性分析主要是通过人工分析出关联规则，然后再加入 到系统当中。然而，随着网络规模越来越大，单纯依靠网络管理人员获得告警关 联性知识已经无法满足网络维护的需要。网络告警数据库中存储了大量的历史告 警信息，其中蕴含了许多反映网络运行规律的有用信息，利用这些信息可以完善 网络故障管理。因此可通过用知识发现的方法分析告警序列，挖掘告警关联规则。 在移动通信网络故障管理中，现今的技术研究引入了数据挖掘的概念和方 法。其基本思想是将数据挖掘技术引入到告警关联中，目的是为了揭示出隐含在 海量原始故障征兆信息后面有意义的知识和规则，从而以更全面的视角解释网络 故障及性能的问题，使网络管理员能快速的进行故障定位、进一步做出故障决策 并完成预测。这一方法能够较好的适应网络的动态变化，从而找出告警数据之间 存在的规则。 数据挖掘在移动网络领域的典型应用有客户行为分析、客户流失预测、告警 序列分析、网络关键性能指标预测等。从国内来看，不少企业也都意识到将数据 挖掘应用于告警关联分析的重要性，开展了类似的项目研究。 1 2 3 电信网络故障定位系统存在的不足 目前，数据挖掘的商用产品，如s p s s ，s a s 以及i b m 的i n t e l l i g e n tm i n e r 等都不适合处理移动网络告警这种关于时间序列的问题。而业内也出现了一些告 警关联应用系统，如s i n e r g i a 系统、i b m 的n e t f a c t 系统以及a r t s 公司的 d e c s 系统，但这些系统在使用友好性、处理效率等方面也做得不是很完善。 总体分析，现有的故障定位系统存在如下不足： 1 ) 挖掘耗时长 现有挖掘算法通常以告警标题( 告警类型) 作为候选n 项集进行挖掘，因 为告警标题可能超过千种，从而随着项集空间的增大，计算量显著增大，导致挖 掘算法计算量大，效率低，耗时长 2 ) 挖掘结果准确度低 实际的告警信息存在长尾现象，大量的设备和大量的告警标题产生的告警信 息非常少，因此实际告警规则或者告警序列在全部告警数据中可能是稀疏的，这 导致了现有挖掘算法通常挖掘出大量的没有实际价值的告警规则或者序列模式。 另外，现有挖掘算法都没有考虑网络的拓扑约束，所挖掘出来的告警规则或 者序列模式与网络结构没有任何关联，因此大大降低了挖掘结果的准确程度。 第3 页 北京邮电大学硕十研究生毕业论文第一章绪论 3 ) 采用固定时间窗口进行挖掘，规则和序列模式不完整 目前有关告警关联的数据挖掘算法都会设置一个固定的时间窗口，虽然设置 固定的时间窗口使得算法比较容易实现，但是将会导致其挖掘出来的告警关联规 则正确性低。应该设置动态的时间窗口，根据不同的告警或不同的网元动态地调 整时间窗口。 1 3 基于拓扑约束的关联规则挖掘技术在电信网络故障定位系统中 的应用 数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取 隐含在其中的、人们事先不知道的但又是潜在有用的信息和知识的过程。i j l 数据 挖掘就是知识发现技术在数据库领域中的应用，在一个已知状态的数据集上，通 过设置一定的学习算法，发掘出数据间隐含的一些内在规律，即获取( 发现) 所 谓的知识。 在大的通信网中，一个故障产生很多告警，当若干故障并存时，产生大量的 告警，这些告警隐藏了故障的原因，以至难以进行故障诊断和定位，这是当今网 络故障管理的一个难题。网络维护人员感兴趣的不是告警事件本身，而是引起告 警的设备故障。尽管这些告警直接或间接的反映故障现象，但大量的告警事件形 成告警风暴，使迅速、准确定位故障变得很困难。将数据挖掘技术引入到告警关 联中，利用基于规则的相关性分析技术，一方面将多个告警归结成较少的告警， 过滤大量的冗余告警，另一方面用于实时故障诊断和故障定位，可以辅助网络管 理人员，过滤冗余信息，准确的定位故障，及时排除故障，保障网络可靠的运行。 但是，传统的告警关联规则挖掘系统大多是直接对原始告警数据进行简单的 预处理就用挖掘算法进行挖掘，从而得到告警之间的关联关系。这种方法尽管可 以挖掘出有效的告警关联规则，但是对于海量的告警数据来说，这样的告警关联 规则挖掘系统的时效性和效率性都不高。通过引入网络拓扑模型作为告警关联规 则挖掘的约束条件，可以使挖掘过程更有效率、挖掘结果更加准确。首先，在预 处理阶段通过网络拓扑关系过滤掉不相关的告警数据；其次，在关联规则挖掘中， 通过拓扑模型可以过滤掉不相关的候选集。可以说，采用基于拓扑约束的关联规 则挖掘算法，大大提高了挖掘告警关联规则过程的时效性和结果的准确性。 1 4 论文期间所作的工作 本文作者对移动通信网络的结构和告警数据、故障定位系统、告警关联产品 第4 页 北京邮电大学硕十研究生毕业论文第一章绪论 和关联规则挖掘算法进行了深入的研究，并参加了“基于数据挖掘的智能化移动 通信网络故障管理关键技术研究”课题的开发和研究。具体的工作如下： 1 ) 对选题进行考察，参与“基于数据挖掘的智能化移动通信网络故障管理 关键技术研究课题的学习。通过阅读大量的相关文献，了解移动通信网络故障 定位系统的现存解决方案以及所面临的挑战，明确研究方向，撰写论文开题报告。 2 ) 学习数据挖掘领域的知识与技术，对网络告警关联规则挖掘技术进行了 深入的学习和研究，并且对现有的告警关联产品进行了分析和对比。 3 ) 根据某省级移动公司提供的真实告警数据，对移动通信网络及其告警特 征进行了分析。 4 ) 参与了b u p t p r i s m i n e r 智能化告警分析原型系统的研发。参与了对 f p g r o w t h 非时序关联规则算法的研究和开发，并配合小组成员把算法集成入 b u p t p r i s m i n e r 系统，完成模块测试、代码维护和文档编写等工作。 5 ) 对参与项目所作的工作进行完善和总结，撰写研究生阶段报告。 6 ) 收集整理资料，总结研究成果，完成研究生学位论文。 第5 页 北京邮电人学硕十研究生毕业论文第二章网络拓扑模型存故障定位系统中的心用 第二章网络拓扑模型在故障定位系统中的应用 传统的电信网络告警关联挖掘，没有与特定的网络拓扑结构相结合，这种方 式存在两大缺陷，首先待挖掘的数据量很大，其次挖掘的关联规则多且冗余。通 过构建网络拓扑模型，可以对告警数据进行挖掘前的过滤或挖掘中的处理，将没 有存在拓扑连接关系的网元告警、关联规则过滤掉，从而提高挖掘的效率和正确 性。 2 1 网络拓扑模型概述 随着人们对通信需求的不断增加以及电信产业的高速发展，电信网络规模日 益庞大，网络设备不断增加，网络结构也越来越复杂。网络结构的复杂性和异构 性，使得人们对网络整体架构及拓扑关系的理解难度加大，同时也很难对网络结 构进行直观的展示和进一步的研究。因此为了更好的理解电信网络结构、更好的 对利用网络拓扑信息来帮助我们进行一些研究，我们需要对网络拓扑关系建立一 个模型，利用网络拓扑的约束对数据挖掘技术进行改进。 拓扑模型是对网络结构的一个抽象视图，它隐藏了跟拓扑关系无关的其它各 个方面，通过它，我们可以直观的了解网络中各网元的连接关系，发现网络连接 的特点，对研究网络结构和网络性能分析等方面有很大的帮助。所以对网络的研 究建立在模型的基础上会比直接面向实际的网络要简便得多。 2 2 移动网络及其告警信息特征分析 当前的移动网络环境具有大型、分布、异构、动态、多供应商等特征；网络 的告警信息则具有数据海量但信息不完整、冗余信息多且时序相关等特点。大规 模分布式网络包含大量的网络实体，它们在运行过程中会产生各种各样的网络告 警信息。这些信息潜在地展示了网络实体的运行状态和行为，例如链路断路、网 络拥塞、设备失效等。 然而，当前移动网络的故障管理非常被动，它是在网络发生故障后，网络管 理人员根据故障告警来发现并排除故障。由于网络本身的复杂性及其在物理和逻 辑上的关联性，单一的故障可能引发大量的告警，形成所谓的“告警风暴”。众 多的告警信息既增加了网管系统的开销，也不利于网管人员根据告警排查故障。 因此，网络故障管理的首要问题是进行告警关联性分析，即对告警进行合并和转 第6 页 北京邮电大学硕士研究生毕业论文第二章网络拓扑模型在故障定位系统中的应用 化，将多个告警合并成一条具有更多信息量的告警来代替多条告警，以协助网管 人员分析故障信息、快速故障定位。 根据对某省级移动公司真实数据的统计和分析，移动通信网络的告警信息具 有如下特点： 1 ) 网元数量多。 一个典型的省级移动通信网络包含的网元大约为几千个。 2 ) 告警数据数量大。 一个典型的省级移动通信网络每天产生1 3 万条告警记录，每月产生4 0 8 0 万条告警记录。 3 ) 告警之间存在时间关联。 即a 告警的发生可能导致b 告警的发生。 4 ) 告警类型( 告警标题) 数量大。 一个典型的省级移动通信网络所产生的告警标题多达数百到数千种。 5 ) 告警标题产生的告警分布存在大头现象。 极少量告警标题产生了最大量告警。0 6 8 的告警标题产生了4 3 9 的告警 信息。 6 ) 告警标题产生的告警分布存在长尾现象。 大量告警标题产生了少量告警。4 4 3 7 的告警标题每个只产生1 - 9 个告警； 7 5 3 1 的告警标题每个只产生1 9 9 个告警。 7 ) 实际的关联规则相对大量的告警信息来说是稀疏的。 在一个网络中，即使同一故障每月发生1 0 0 次( 这种情况非常罕见) ，但是 相对于每月4 0 多万条告警数据来说，还是非常小的。 8 ) 不能排除长尾中的告警信息属于故障的关键告警信息。 根据课题对该移动公司两个告警传播实例的已有分析和研究，移动网络的告 警传播具有如下特点：告警是沿着网络拓扑进行传播的l u j 。同一个故障可能会引 起若干个存在拓扑连接的网元发出告警，而不管告警是从低层网元向高层网元传 播，还是从高层网元向低层网元进行传播，告警始终都是在故障网元所在的网元 簇中传播，所以只要我们能根据网络拓扑关系将网元簇找出来，便可以进一步根 据该网元簇对告警数据进行抽取和判断，从而进行故障定位。 2 3 故障定位系统中引入网络拓扑模型的目的 故障定位是网络故障管理的核心，其首要问题是进行告警关联性分析，即对 告警进行合并和转化，将多个告警合并成一条具有更多信息量的告警来代替多条 告警，以协助网管人员分析故障信息、定位根源故障。而进行网络拓扑建模则是 第7 页 北京邮电大学硕七研究生毕业论文第二章网络拓扑模型在故障定位系统中的戍用 为了通过网络拓扑模型进行约束使挖掘过程更有效率、挖掘结果更加准确。所以 应用网络拓扑模型，最终是为数据挖掘服务的。 对网络拓扑模型的应用可以有两种方式。第一种应用方式是在预处理阶段， 通过网络拓扑关系过滤掉不相关的告警数据。即针对原始告警数据中的某条待分 析的告警，通过此告警的网元d 在拓扑模型中找到与该网元具有拓扑关系的所 有网元( 或者大部分网元) ，将这些连接在一起的网元提取出来，存放在某种数 据结构中( 以网元i d 的形式存储) ，形成一个网元簇1 ，然后将预设的时间窗口 内原始告警数据的网元i d 与网元簇进行匹配，将不属于该网元簇的告警过滤掉， 最后只留下属于网元簇内网元的告警，然后再用数据挖掘算法对这些数据进行挖 掘。 第二种应用是在关联规则挖掘中，由l 项频繁项集产生l + 1 项候选项集时， 通过网络拓扑模型来过滤掉不相关的候选项集。例如，从1 项频繁项集产生2 项 候选项集，对每一项与其他项进行联接时，首先还是根据该项的网元m 从拓扑 模型中找到相互连接的网元，形成网元簇，这与上面第一种应用方式的过程一样。 然后判断该项与待联接的项是否同出现在网元簇中，如果没有，则这两项不进行 联接，否则就将这两项联接后放入2 项候选频繁项集中。从l 项频繁集产生l + 1 项候选频繁集过程也与此类似。 综上所述，建立拓扑模型最主要的目的就是要实现针对某个网元，能够从模 型中查找出与其存在拓扑连接的所有网元( 或者大部分网元) ，并存储于某种数 据结构中，为其他模块处理做准备。 2 4 基于拓扑约束和数据挖掘的故障定位总体方案 在移动网络中，网络设备之间存在的互相作用和互相影响是产生告警传播的 根源，因此，从相互影响的设备发出的告警序列中发现模式更加具有针对性和更 加有意义。如果不引入设备间的关系，就无法滤除不相关设备的告警对相关设备 告警的干扰，容易产生大量无意义的模式。因此，引入网络拓扑的约束非常重要， 将网络拓扑约束和数据挖掘技术结合起来，可以借助约束降低噪音和数据缺失带 来的影响，以发现有价值的规律。 下图是课题提出的基于网络拓扑约束和数据挖掘技术的故障管理总体解决 方案架构图。 第8 页 北京邮电大学硕十研究生毕业论文第二章嗍络拓扑模型在故障定位系统中的心用 图2 1 故障管理总体解决方案 6 】 上述解决方案应用了现有的数据挖掘方法，结合移动网络的具体特征，将网 络拓扑约束与数据挖掘结合起来，形成了对移动网络故障定位的有针对性的方 法。 在上述解决方案中，本文作者主要针对基于网络拓扑建模的非时序告警关联 规则挖掘算法进行了研究和实现。 移动通信网络的网元根据连接类型以及网元的功能大致可以分成如下几大 子网：话务网、信令网、智能网、g p r s 数据网和网管网。通过移动通信网络结 构分析，我们对网络进行抽象，将话务网、信令网、智能网、g p r s 数据网和网 管网等各个子网实际的网络结构抽象为一般的拓扑模型图，分别建立各自的网络 拓扑模型，这样可以更加明晰、直观的表示网络各个子网的整体结构以及子网之 间的关系。最后将各子网络模型根据连接关系进行组合，从而形成一个总体的移 动网络拓扑模型。 在告警数据挖掘方面，首先要进行历史告警数据的离线挖掘。在完成告警离 线预处理后，对历史告警数据库进行关联规则挖掘和序列模式挖掘，之后将挖掘 出的规则保存在告警规则和序列库中，供在线分析使用。 在挖掘算法的选择上，应重点考虑下面三个因素： ( 1 ) 不采用多次扫描数据库的算法。 ( 2 ) 将网元之间的连接关系作为一种约束条件在挖掘的过程中将一些关联 规则滤除掉。 第9 页 圆 圈豳 北京邮电大学硕十研究生毕业论文第二章网络拓扑模型存故障定位系统中的应用 ( 3 ) 网络层次应当做为考虑的因素，它可以将关联规则更好地加以限制， 以提高挖掘结果的正确性。 在告警关联规则挖掘方面，本文作者对f p g r o w t h 算法进行了研究和实现。 f p g r o w t h 算法对数据库只进行两次扫描，尤其适合我们将要面对的大型数据库， 可以节省大量的执行时间，提高了执行效率。 2 5 基于网络拓扑模型的故障定位技术的特点 通过引入网络拓扑模型的约束，将网络拓扑模型与数据挖掘技术相接合，克 服了传统电信网络告警关联挖掘中待挖掘的数据量大、挖掘的关联规则多且冗余 的缺点。基于网络拓扑模型的故障定位技术具有如下特点： 首先，提高了数据挖掘的效率。现有的挖掘算法通常以告警标题或者类型作 为候选n 项集进行挖掘，因为告警标题可能超过千种，从而随着项集空间的增 大，计算量显著增大，导致挖掘算法计算量大、耗时长、效率低。而通过建立网 络拓扑模型，以网元关联作为约束来筛选候选n 项集，大大减少了候选集的数 量，从而可以减少计算量，提高挖掘算法的效率。 其次，提高了数据挖掘的精度。传统的挖掘算法都没有考虑网络的拓扑约束， 所挖掘出来的告警关联规则与网络结构没有任何关联，从而大大降低了挖掘结果 的准确程度。而以网元关联作为约束来筛选候选集，建立了告警关联与网络拓扑 之间的关联，过滤了不相关告警对挖掘结果的影响，从而可以在关联规则稀疏的 情形下提高挖掘结果的准确度。 第1 0 页 北京邮电大学硕十研究生毕业论文 第三章面向故障定位的移动通信网络拓扑建模 第三章面向故障定位的移动通信网络拓扑建模 拓扑模型是对网络结构的一个抽象视图，它隐藏了跟网络拓扑关系无关的其 他各个方面。通过它，我们可以直观的了解网络中各网元的连接关系，发现网络 连接的特点。因此将拓扑模型引入网络管理故障定位系统，通过拓扑模型滤除掉 不相关网元设备的告警对相关网元告警的干扰，可以提高故障定位数据挖掘的时 效性和准确性。 本章在对某省级移动公司通信网络特征进行研究和分析的基础上，提出了网 络的抽象拓扑模型。尽观我们的研究是以某省级移动公司通信网络为范本和原型 的，但是由于网络具有共性，从该省级移动公司通信网络抽象出来的主要特征同 样适用于其他移动通信网络。而拓扑建模方案也同样可以根据具体网络进行适当 修正后应用于其他移动通信网络。 3 1 移动通信网络结构概述 为支持对某省级移动网络告警数据进行数据挖掘，课题对该省级移动的通信 网络结构进行了研究和建模。移动通信网络网元的连接类型可根据传递信息的不 同分为三大类：话务中继、信令链路和分组数据线路。其中话务中继传递的是传 统话音业务；信令链路传递的是网元间的信令消息：分组数据链路传递的主要是 g p r s 数据等。 该省级移动公司通信网络的网元根据这几种连接类型以及网元的功能大致 可以分为如下五大子网：话务网、信令网、智能网、g p r s 数据网和网管网。在 每个子网中，我们又可以分析其存在的层次关系。网络的层次关系有助于网络通 信的路由查找，而在网络故障管理方面，网络的层次关系同样可以用来进行故障 告警传播的分析。 通过对移动通信网络结构的分析，我们对网络进行抽象，将话务网、信令网、 智能网、g p r s 数据网和网管网等各个子网实际的网络结构抽象为一般的拓扑模 型图，分别建立各自的网络拓扑模型，这样可以更加明晰、直观的表示网络各个 子网的整体结构以及子网之间的关系。最后将各子网络模型根据连接关系进行组 合，从而形成一个总体的移动网络拓扑模型。 第l l 页 北京邮电大学硕十研究生毕业论文第三章面向故障定位的移动通信网络拓扑建模 3 2 移动通信网络拓扑模型 本节我们将对各个子网的网元及其连接关系进行抽象( 比如抽象为网元类 型) ，然后将各个子网通过结构图表示出来；同时将各个子网之间的关系进行抽 象，从而得到整个移动通信网络的抽象拓扑模型。这样就可以更加明晰、直观的 表示出各个子网的整体结构以及子网之间的关系。 3 2 1 话务网模型 话务网是提供传统话音业务的网络，是电信网络中最主要、网元最多的部分， 其网元之间主要是话务中继的连接，同时也有信令链路的连接。它主要的网元有 基站( b t s ) 、基站控制器( b s c ) 、变码器( x c d r ) 、移动交换中心( m s c 、 g m s c 、t m s c ) 等。 话务网模型图如图3 所示，话务网根据网元的功能又可分为无线网和交换 网两部分。无线网即图中所示的b s s ，主要是为移动台( 如手机) 与交换机之间 提供链路，其结构分层比较明显，从模型图中也可以看出，每一个m s c 交换机 连接若干个r x c d r ，而一个或两个r x c d r 则连接一个b s c ，个b s c 下则 连接若干个b t s 。交换网则主要由交换机与用户数据库构成，进行网络通信的交 换和管理，交换网网元的连接则比较复杂，基本上各个交换机都互相连接，如每 个m s c 都与所有的g m s c 、t m s c 连接，g m s c 、t m s c 之间也有连接。同时 如上节提到的，m s c 、g m s c 、t m s c 也都与信令转接点有信令链路的连接。 第1 2 页 北京邮电大学硕士研究生毕业论文第三章面向故障定位的移动通信网络拓扑建模 3 2 2 信令网模型 图3 - 1 话务网模型图”。 7 1 信令网属于支撑网，它主要进行电信业务的接续、控制，是通信网络的神经 系统，在该省级移动通信网络中它主要的网元有高级信令转节点( h s l l p ) 、低级 信令转接点( l s 耶) 、归属位置寄存器( h l r ，存储本地用户信息的数据库，包 括用户号码、预订业务类型、鉴权信息和当前所在地等信息) 、交换机( m s c 、 g m s c 、t m s c ) 以及其它与信令转接点有信令链路连接的网元。 信令网可抽象为图3 3 。我国7 号信令网为三层结构，即高级信令转接点 h s t p 、低级信令转接点l s t p 、信令点s p 这三层。该省级移动公司的h s t p 及 l s t p 是全互联的，而两台h s t p 则互为备份，并与其它省份的高级信令转接点 连接。第三层的信令点在实际中包含网络中的大部分网元，如图3 5 中，包含了 话务网的交换机、g p r s 网的支持节点、智能网的控制点等等。 3 2 3 网管网模型 图3 2 信令网模型图【7 】 网管网是对电信网络中所有网元进行监控管理的支撑网，主要由操作维护中 心( o m c ) 服务器通过该网连接到各个网元，从上面获取配置信息、性能信息 和告警信息等，同时也能通过指令对网元进行远程操作。 网管网模型图如图3 所示，网管网主要由o m c 服务器及其管理的网元构 成，通过x 2 5 等分组网连接，不参与通信业务。o m c 根据管理的网元所属子网 的不同可分为不同的类型，图中o m c s 管理交换网的交换机，o m c r 管理无 线网网元，o m c _ t 管理g p r s 网元，o m c i n 管理智能网网元，o m c s 什管 理信令转接点等网元。而同一类型的o m c 由于所管理的网元的厂家不同也有不 第1 3 页 北京邮电人学硕1 ：研究生毕业论文第三章面向故障定位的移动通信网络拓扑建模 同的设备和名称。各个o m c 服务器之间都不互连，各管各的网元，但是运营商 可能根据实际情况建立一个综合网管系统，将各个o m c 服务器的管理信息统一 收集起来，进行集中管理、集中监控，如图中虚线所示。但由于该综合网管系统 是面向前台维护人员的系统，且在告警数据中也没有该系统的告警，所以我们不 把它列入网络拓扑模型中。 3 2 4 智能网模型 图3 - 3 网管网模型图 7 1 智能网是在原有通信网的基础上设置一层叠加网络，用它快速方便、经济灵 活的生成和实现各种新业务的体系结构。它包括的网元有业务控制点( s c p ) 、 业务交换点( s s p ) 、业务数据点( s d p ) 、充值中心( v c ) 、业务管理点( s m p ) 和智能外设( i p ) 等。 智能网模型图如图3 所示。智能网通过s c p 、s s p 与信令转接点连接，接 入7 号信令网，进行信令的交互；通过s s p 与交换机连接，接入话务网，进行 话务通信。图中s t p 和g m s c 用蓝色表示，因为这两者不属于智能网，但也是 子网间连接的接口。 第1 4 页 北京邮电大学硕上研究生毕业论文第三章面向故障定位的移动通信网络拓扑建模 3 2 5g p r s 网模型 图3 4 智能网模型图【7 】 g p r s 数据网是实现g p r s 业务的网络，网元包括分组控制单元( p c u ，它 与b s c 集成于同一设备当中) 、g p r s 服务支持节点( s g s n ) 、g p r s 网关支持 节点( g g s n ) 、边界网关( b g ) 、计费网关( c g ) 、域名服务器( d n s ) 和防火 墙( f i r c w a l l ) 等。 g p r s 网模型图如图3 一所示。p c u 、s g s n 、g g s n 具有一定的层次结构， p c u 一般与b s c 位于同一网元实体中；s g s n 通过帧中继与p c u 连接，通过分 组网与g g s n 连接：c g 、b g 、d n s 等设备也是通过分组网接入到g p r s 网中。 而g p r s 也通过7 号信令网同其它子网的网元连接，如图中蓝色部分所示。 图3 5g p r s 网模型图【7 】 第1 5 页 北京邮电大学硕l 研究生毕业论文第三章面向故障定位的移动通信网络拓扑建模 3 2 6 移动通信网络模型 上述各小节对移动通信网络各个子网分别进行了抽象并建立起抽象模型。而 各子网之问又通过信令链路、话务中继和分组数据链路等多种连接类型相互连接 在一起，组成了移动通信网络。其中，信令网通过信令链路与其它除网管网之外 的子网进行连接；话务网与信令网有信令链路连接，与智能网有话务中继连接， 与g p r s 网有分组数据链路连接；而网管网则通过自身的分组数据网将各个网元 连接到相应的o m c 服务器。移动通信网络模型如图3 所示，其中不同颜色代表 了不同的子网，蓝色部分表示信令网，绿色部分表示g p r s 网，红色部分表示话 务网，橙色部分表示智能网，粉色部分表示网管网。 图3 6 移动通信网模型图【7 3 3 移动通信网络网元拓扑查找算法研究 本节依据课题所提出的网元簇划分方案，对网元拓扑查找算法进行了研究和 描述。课题将移动通信网络网元划分为三类网元簇，它们分别是：公共连接网元 簇、话务网网元簇和特殊网元簇，并生成三个网元拓扑文件：公共连接网元文件、 话务网网元簇拓扑文件和特殊网元簇拓扑文件。 3 3 1 算法概述 基于上述已有的划分，网元拓扑查找算法对输入的任意一个网元序列，可以 北京邮电大学硕士研究生毕业论文第三章面向故障定位的移动通信刚络拓扑建模 从网络拓扑数据库中查询输入的网元序列是否被一个网元簇包含。如果是则返回 t r u e ，表明这个网元序列中的网元存在拓扑关系，即它们之间存在告警传播路径； 如果不是则返回f a l s e ，即输入的网元序列不被任何一个网元簇包含，这表明这 个网元序列中的网元之间不存在拓扑关系，即它们之间不存在告警传播路径。 关联规则挖掘算法根据返回的t r e e 或f a l s e 对频繁模式进行筛选，从而过滤 掉不存在告警传播条件的错误频繁模式。由于f p g r o w t h 算法采用树结构进行挖 掘，在完成树的生成后就可以一步生成频繁模式，所以f p g r o w t h 算法在挖出频 繁模式后将它们依次进行判定是否符合网络拓扑约束，然后将不符合的模式从最 终的频繁模式集中删除 由于网元簇的划分可能不能涵盖所有的告警传播路径，或者不能完整的覆盖 一个告警传播路径，因此增加一个可控参数一匹配模糊度，来降低现有的网元簇 与过滤掉公共连接网元后的网元序列的匹配精度。匹配模糊度的缺省值为1 ，表 明需要1 0 0 精确的匹配，可以适当降低这个参数值，如降为9 0 ，此时，若过 滤掉公共联接网元后的输入序列与一个网元簇的匹配度达到9 0 ，网元拓扑查 询就返回t r u e 。 3 3 2 输入参数说明 名称：输入网元序列 类型：整数数组 含义：网元标号序列，在实际算法运行中，该序列数为频繁模式中包含的网 元标号序列。 3 3 3 可控参数说明 名称：匹配模糊度 类型：双精度 含义：表征匹配输入网元序列可接受的模糊度，缺省值为1 。如设为9 0 则 表明，当存在一个网元簇与过滤掉公共连接网元后的输入网元序列的匹配度大于 或者等于9 0 时，认为该序列存在拓扑关系，网络拓扑算法返回t r u e 。 3 3 4 输出参数说明 类型：布尔类型 含义：表征过滤掉公共连接网元后的输入网元序列是否被一个定义的网元簇 第1 7 页 北京邮电人学硕j ：研究生毕业论文第三章面向故障定位的移动通信网络拓扑建模 所包含，如果是返回t r u e ，否则返回f a l s c 。 3 3 5 算法流程图 图3 - 7 网络拓扑查找算法流程图 第1 8 页 北京邮电人学硕士研究生毕业论文第三章面向故障定位的移动通信网络拓扑建模 第1 9 页 北京邮电人学硕上研究生毕业论文第三章面向故障定位的移动通信网络拓扑建模 3 3 6 算法逻辑说明 从算法流程图上可以看出，网元拓扑查找算法主要分为三个过程，过滤公共 连接网元，判断过滤后的序列是否被特殊网元簇包含，如果不被包含，判断过滤 后的序列是否被话务网网元簇包含。 过滤公共连接网元 遍历输入网元序列的每一个元素，遍历公共连接网元中的每一个网元，判断 网元序列的当前元素是否包含于公共连接网元集合中，如果是，删除该元素，判 断下一个元素。由于公共连接网元文件的特征是文件每一行仅有一个整数，文件 每一行内容具有唯一性，文件行数相对比较少，有4 2 行，而唯一性以及个数的 确定性正是s t l 中s e t 数据结构的最大特征，所以使用t 数据结构来保存每一 行的数据。而使用s e t 数据结构可使查询的时间复杂度降低。 判断过滤后的序列是否被特殊网元簇包含 扫描特殊网元簇拓扑数组的每一个整数型集合，根据匹配模糊度以及过滤后 的序列的网元个数，计算出判定输入网元序列具有拓扑关系时该输入序列被一个 网元簇包含的网元数目的最小值。遍历过滤后的序列的每一个网元标号，通过查 找当前网元簇整数型集合判断其是否包括当前的网元标号，如果一个网元簇包含 的过滤后的序列中网元标号的个数大于或者等于由匹配模糊度和网元序列个数 决定的匹配最小值时，网络拓扑查询算法返回t r u e ，否则执行判断过滤后的序列 是否被话务网网元簇包含。 判断过滤后的序列是否被话务网网元