（计算机科学与技术专业论文）动态系统近似故障定位算法及实现.pdf

彳 参 y 吩 l 1，jl jll- 矗帑：妒。 01 g j 一： 窿 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处， 本人签名： 查苤耄 本人承担一切相关责任。 日期：塑丛：主：“ 关于论文使用授权的说明 本人完全了解北京邮电大学有关保留和使用学位论文的规定，即：研究生在 校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保留：并向国 家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅；学校 可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段 保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 。 本学位论文不属于保密范围，适用本授权书。 本人签名：壹薹：蠢 日期：丛丛：丝 导师签名： ：亟! 业b 日期： 2 盆3 1 2 ：；。( h i f l i l l l l l l 珊 7 3 9 哆 叫 l 产 一。，j 动态系统故障定位算法及实现 摘要 伴随着互联网的飞速发展，各类企业应用在网络上进行了大量部 署，为保障各项业务应用正常运作，能够快速准确的定位i t j j 艮务中的 故障，是其中的关键。在大型网络中，协议栈上层的各类业务应用故 障，是由多种不同原因导致的并且具有很大的不确定性，即这些应用 故障可能是由其他应用故障引起的，也可能是由物理故障引起的，并 且故障之间的关系并不是一成不变的；加之网络中存在一定的观测噪 声，互联网俨然变成了一个复杂的动态系统，这为传统确定性故障定 位技术提出了新的要求和挑战。贝叶斯网是目前不确定知识表达和推 理领域最有效的理论模型之一，基于静态贝叶斯网络的故障定位技术 在定位的复杂度、准确度和精确度方面取得了相当的进展。但是，基 于静态贝叶斯网络的故障定位技术很难满足动态系统故障定位的需 要。 本文通过研究基于贝叶斯网络的故障推理算法，分析各种静态模 型的适应环境，总结各种推理算法的优缺点，提供了一种在给出一组 端到端的失败的服务情况下，基于动态贝叶斯网络的故障诊断方法。 为了适应动态系统的故障诊断，该方法从各个方面对静态贝叶斯诊断 方法进行了改进。为适应系统动态性，引入了时间片信息、加入了相 邻时间片故障关系分析机制、故障概率传播与更新机制；为处理环境 噪声引起的定位不准确问题，引入了噪声过滤机制；为了适应大型网 络，引入了模型简化机制。此外由于精确推理虽然可以取得较高的准 确度，但是复杂度也相当高，不能满足故障定位的需要，因此本算法 加入了一系列近似方法，保证准确度和复杂度之间达到一个均衡。最 后通过实验仿真证明了在网络节点较大、动态环境和噪声情况下，本 算法能够在较小的时间范围内取得较高的准确度和较低的错误率。基 于j a v a 语言给出算法的具体实现过程，通过对算法进行近似，减小了 算法复杂度，适应了复杂动态系统故障诊断的需要。并从准确度，精 确度和定位时间三个方面，与基于静态贝叶斯网络诊断方法进行了对 比，实验证明我们的算法具有更好的性能。 ， ， 。 i 、 关键词：故障定位动态贝叶斯网概率传播模型近似推理 ， _ ， 产 6 产 a b s t r a c t w 1 t ht h er a p i dd e v e l o p m e n to ft h ei n t e m e ta n dag r e a td e a lo f d e p l o y m e n t so fv a r i o u se n t e r p r i s ea p p l i c a t i o n s ，i ti sv e r yi m p o r t a n tt o q u i c k l ya n da c c u r a t e l yl o c a t ei ts e r v i c ef a i l u r e si no r d e rt og u a r a n t e et h e n o r m a lo p e r a t i o no f b u s i n e s sa p p l i c a t i o n sa n dp r o v i d eb e t t e rs e r v i c ef o r c u s t o m e r s i nl a r g ea n dc o m p l e xn e t w o r k s ，t y p e so fa p p l i c a t i o nf a i l u r e si n t h eu p p e rp r o t o c o ls t a c kc a u s e db yav a r i e t yo fd i f f e r e n tr e a s o n sh a v e g r e a tu n c e r t a i n t y , t h a ti s ，f a i l u r eo ft h e s ea p p l i c a t i o n sm a yb ec a u s e db y o t h e rl o g i c a lf a i l u r e s ，b u ta l s om a yb ec a u s e db yap h y s i c a lf a i l u r e t h e r e l a t i o n s h i pb e t w e e nt h e s ef a i l u r e sb e c o m e sm o r ea n dm o r eu n c e r t a i n c o u p l e dw i t ht h eo b s e r v a t i o nn o i s ei nt h en e t w o r ke n v i r o n m e n t ，t h e i n t e r n e th a sb e c o m eac o m p l e xd y n a m i cs y s t e m ，w h i c hag r e a tc h a l l e n g e f o rt r a d i t i o n a ld e t e r m i n i s t i cf a u l tl o c a l i z a t i o nt e c h n i q u e a so n eo ft h e m o s te f f e c t i v et h e o r e t i c a lm o d e l so fp r o b a b i l i s t i ci n f e r e n c e ，b a y e s i a n n e t w o r kr e p r e s e n t st h eu n c e r t a i nr e l a t i o n s h i pb e t w e e nt h ee n t i t i e si n d y n a m i cs y s t e mu s i n gt h ek n o w l e d g eo fg r a p ht h e o r ya n dp r o b a b i l i t y t h e o r y a tp r e s e n t ，f a u l td i a g n o s i st e c h n i q u e sb a s e do ns t a t i cb a y e s i a n n e t w o r kh a sm a d ec o n s i d e r a b l ep r o g r e s si n a l g o r i t h mc o m p l e x i t y , a c c u r a c y a n dp r e c i s i o n h o w e v e r , i ti sd i f f i c u l tt oe x h i b i t g o o d p e r f o r m a n c ei nd y n a m i cs y s t e m a f t e rt h er e s e a r c ho ff a u l td i a g n o s i st e c h n i q u eb a s e do ns t a t i c b a y e s i a nn e t w o r ki n c l u d i n ga n a l y s i so ft h en e t w o r ke n v i r o n m e n ta n dt h e p e r f o r m a n c eo fe v e r ya l g o r i t h m s ，t h i sp a p e re s t a b l i s h e saf a u l td i a g n o s i s t e c h n i q u eb a s e do nd y n a m i cb a y e s i a nn e t w o r kw h i c h ，g i v e nt h es e to f f a i l e de n d t o e n ds e r v i c e s ，d i s c o v e r st h eu n d e r l y i n gr o o tc a u s e s i no r d e r t od i a g n o s i sf o rd y n a m i cs y s t e m s ，t h i sm e t h o di m p r o v e dt h ea l g o r i t h m s b a s e do ns t a t i cb a y e s i a nn e t w o r ki nm a n ya s p e c t s s u c ha si n t r o d u c i n g t h et i m e s l i c ei n f o r m a t i o n ，t h em e c h a n i s mo fa n a l y z i n gr e l a t i o n s h i p b e t w e e na d ja c e n tt i m e s l i c et od e a lw i t ht h ed y n a m i c s ，n o i s ef i l t e r i n gt o d e a lw i t ht h es p u r i o u sa l a r m s ，m o d e ls i m p l i f i c a t i o nt oa d a p tt ol a r g e s y s t e m 。f a u l tt r a n s m i s s i o na n dp r o b a b i l i t yu p d a t i n g w 色u s e dd y n a m i c b a y e s i a nm o d e lt oh a n d l es y s t e md y n a m i c sa n d as i m p l et o o lt od e a lw i t h n o i s e o u ra p p r o x i m a t ea l g o r i t h mh a st a k e ns e v e r a lm e a s u r e st or e d u c e t h ea l g o r i t h mc o m p l e x i t yi no r d e rt od i a g n o s i sf o rl a r g e s - s c a l en e t w o r k s w ei m p l e m e n ts i m u l a t i o nw i 也j a v aa n dc o m p a r eo u ra l g o r i t h mw i t h a l g o r i t h mb a s e do nb n i na c c u r a c y , e f f i c i e n c ya n dt i m e t h er e s u l t ss h o w t h a tt h ea l g o r i t h mc a nr u nw e l la n dh a v eg o o dp e r f o r m a n c e t h i sm e t h o d m a k e sf u l lu s eo ft h eh i s t o r i c a ld a t aa n dc u r r e n to b s e r v a t i o n st oe s t i m a t e t h ec u r r e n ts y s t e ms t a t ea n dc o m p l e t et h ef a u l td i a g n o s i s k e yw o r d s ：f a u l tl o c a l i z a t i o n ；d y n a m i cb a y e s i a nn e t w o r k s ； p r o b a b i l i t yp r o p a g a t i o nm o d e l ；p r o b a b i l i s t i ci n f e r e n c e ， l ， 一， ，一 2 1 2 贝叶斯网络。6 2 2 常用故障定位技术7 2 2 1基于模型的方法7 2 2 2 基于静态贝叶斯网络的方法8 2 2 3 基于动态贝叶斯网络的方法1 0 2 3 算法比较1 2 2 4 故障定位技术面临的主要问题1 3 2 5 本章小结1 4 第三章动态系统的近似故障定位算法1 5 3 1 i t 服务层的故障定位1 5 3 1 1it 服务层故障的特点1 5 3 1 2 动态贝叶斯网适用于i t 业务层故障定位的原因1 8 3 1 3 已有基于贝叶斯网的推理算法的分析1 9 3 1 4 解决问题思路2 0 3 2 动态贝叶斯模型的建立2 1 3 3 故障定位算法介绍2 3 3 4 本章小结2 9 第四章动态系统近似故障定位算法的实现和仿真。3 0 4 1 算法实现3 0 4 1 1 程序架构设计3 0 4 1 2 程序的详细设计3 l 4 1 3 主要实现类说明3 4 4 2 仿真实验环境搭建和实验设计4 2 4 2 1 仿真环境的搭建4 3 4 2 2 实验设计4 4 4 3 实验结果分析4 4 4 4 本章小结4 6 第五章结束语。4 8 参考文献5 0 致谢5 3 攻读学位期间发表的学术论文目录5 4 系统中发 样的诊断 的系统都 致一定的 外在状态的出现，因此这些方法也被称为确定性故障定位方法。但是伴随着当今 互联网的飞速发展，各类企业应用在网络上进行了大量部署，网络的复杂化给网 络运营和维护提出了新的要求。为了保证网络的可用性和高效性，保证i t 服务 的质量，快速准确的定位网络中存在的故障，变得越来越重要。多种i t 业务部 署在分布式系统上，任何软件或是硬件的故障例如软件异常、丢包、访问量过大、 路由表b u g s 、链路拥塞等，都有可能直接或间接的导致i t 服务质量的下降。这 些故障有可能发生在同一层，在同一层传播，引起一些其他故障的发生，也有可 能从底层传到高层。总之业务越复杂，影响i t 服务质量的因素就越多，不确定 性就越大。故障定位系统不再仅仅局限于诊断协议栈底层的物理故障，而诊断协 议栈上层的各类应用业务的故障逐步成为我们关注的重点。在大型复杂网络中， 协议栈上层的各类业务应用故障的出现，是由多种不同原因导致的并且具有很大 的不确定性，加之网络中存在一定的观测噪声，这为确定性故障定位技术提出了 新的挑战。因此出现了一些基于图论、神经网络的不确定性推理技术嫡1 ，其中基 于贝叶斯网络的推理技术成为其中比较流行的技术之一。 基于贝叶斯网络删的推理技术，利用告警和故障之间的不确定关系进行推 理，这种不确定关系模型是通过图论和概率论口1 的知识呈现的，它适应了业务层 故障和症状之间关系的不确定性，并且能够容忍一定的噪声，因此相对于确定性 告警关联性分析陋3 技术，大大提高了诊断的效率和准确度，但是都有一个共同的 假设作为前提，即在故障诊断的过程中，被管系统是不变的，即诊断过程中各个 节点的状态不会发生变化。然而，实际网络并非静态网络，而是一个动态变化的 系统，突出表现为网络拓扑变化、网络路由变化以及网络中的节点的状态也在随 时间不断的变化，因此基于静态贝叶斯网络的模型1 不足以表现实际网络，于是 研究者把目光转向了动态贝叶斯网络。 动态贝叶斯网络n 们将系统表示成从起始时间到终止时间的一系列快照，每一 个快照都包括一个完整的贝叶斯网络，表示系统在该时间的状态，前后两个快照 之间相关的节点添加因果联系，表示在不同时间片的节点状态传播关系。基于动 态贝叶斯网络的推理3 是处理动态不确定性问题的重要方法，在动态系统故障诊 断中发挥着重要的作用。精确推理算法有f o r w a r d s - b a c k w a r d s 算法n2 1 、f r o n t i e r 算法、t h ei n t e r f a c e 算法等，由于精确推理算法复杂度高，不能满足大规模的 动态贝叶斯网络推理的需要，因此研究者把目光转向近似推理，主要近似推理算 法有t h eb o y e n - k o l l e r ( b k ) 算法、t h ef a c t o r e df r o n t i e r ( f f ) 算法n3 i 、p f 算法等n 引。b k 算法利用团树算法执行一次精确推理的全局更新，对于大型网络 是不适用的，f f 算法是将所有节点分别向下一个时间片传递信息，近似后算法 准确度太低，而p f 算法是一种基于统计学的方法。由于这些算法都存在着各自 的缺点，因此都没有用于进行动态系统的故障诊断。 1 2 本文要解决的问题与创新点 本课题的任务是：通过查找资料，研究现有的基于静态贝叶斯网络的模型和 故障定位技术，并总结各个模型运行环境的特点以及推理算法的优缺点，同时对 基于动态贝叶斯网络的建模方法和推理方法进行学习。针对业务层网络故障传播 关系的不确定性以及业务节点状态的动态性，选择一个合适的贝叶斯网络模型， 利用动态贝叶斯网络时间片扩展的方法对此模型进行时间片扩展。在此基础上， 将现有的推理算法应用于动态贝叶斯网络模型，对推理算法进行近似和改进，并 提出能够过滤虚假症状的方法，以适应复杂的动态系统的需要。 要解决的问题包括： 一 网络规模过大情况诊断时间的问题，即如何在网络规模较大的情况下， 既能够保证故障定位的准确度又能够保证定位时间不会过大； 一 环境噪声的问题，即存在环境噪声情况下，如何减小环境噪声在诊断算 法的影响，保证较高的定位准确度； 一 系统动态变化的问题，即网络中节点都有一个生命周期，使用时间越久， 发生故障次数越多，将来发生故障的可能性会越大；随着路由变化、拥 塞等，网络上层节点之间的关系也在动态变化；如何建立一个自学习、 自适应的系统来进行故障诊断； 一 如何搭建实验环境，对本文提出的故障定位算法进行仿真，以证明此算 法具有更好的性能。 创新点主要是提出新的基于动态贝叶斯网的故障定位模型和算法；在算法中 引入时间片信息，以体现动态系统的特性；引入相邻时间片故障关系分析机制， 2 1 3 研究生期间工作 引入噪声过滤机 上执行推理算法； 研究生期间，作者深入学习了电信管理网的理论知识，了解了网络管理方面 相关的规范和技术，并参加了综合网管系统的开发工作。深入研究网络管理中的 故障定位技术，了解国内外现有技术中存在的问题，并提出解决方案。概括来说， 作者在读硕士期间参与的主要研究工作包括 1 ) 综合资源管理系统。负责提出各类资源的添加、修改、删除的具体实施方 案以及各类资源的数据合法性检测方案；负责系统测试，包括测试用例、测试报 告以及用户手册的撰写。 2 ) 综合故障管理系统。负责告警关联性分析算法的设计和实现、数据库设 计与实现，提出了一个基于模型的告警关联性分析算法，并使用j a v a 实现此算 法；负责告警处理模块的测试，以及测试文档的撰写。通过此项目基于模型的告 警关联性分析系统有了更加深入的认识和理解。 3 ) 故障定位算法的研究。在上述告警关联性分析模块的基础上，进一步分 析各类故障定位技术，结合项目的特点和当前故障定位中出现的新需求，对基于 贝叶斯网络的故障定位技术进行了研究；参与基于静态贝叶斯网络的故障定位技 术的研究和实现；独立完成基于动态贝叶斯网络故障定位模型和算法的设计、实 现与仿真；对现有的故障定位技术进行改进，解决了i t 业务层故障定位复杂度 高，定位不准确的问题。发表论文两篇，一篇发表于i c n c 2 0 0 9 ，另一篇发表于 a p n o m s 0 9 ，均为e i 检索。本文是此项工作的总结。 1 4 论文结构 本文共分五章，内容安排如下： 第一章引言，介绍本课题的背景、意义、主要解决的问题和创新点以及作 者在研究生期间的主要工作； 第二章介绍告警与故障的关联关系，已经得到广泛应用的成熟的故障定位 技术以及研究领域所关注的故障定位技术，对这些故障定位技术进 行比较，提出当今故障定位领域面临的一些主要问题； 第三章以业务层网络为例，通过对一个具体场景的介绍和分析，指出动态 系统中故障定位的一些具体问题，针对此场景挖掘出故障定位的新 3 需求，指出动态贝叶斯模型适合予用于动态系统故障定位的原因， 并对现有静态贝叶斯的模型和近似推理算法进行简单介绍，提出扩 展模型和改进后的近似推理算法； 第四章介绍本算法的具体实现过程、仿真实验和结果分析； 第五章结束语，对本文工作进行全面总结，给出本文所取得的成果，指出 存在的不足和改进方向。 4 性能下降状 障通常是不 会直接被网管系统直接观测到的，往往通过一些外在现象表现出来。 告警：症状是故障的外在表现，故障定位通常是根据症状信息来进行的。症 状在实际的网络管理系统中往往是以告警的形式出现的，由监控系统通过对网 络、业务应用潜在的故障或者已经发生的故障的外在表现检测来获取并提供给故 障定位系统的。 在网络管理领域，故障被定义为产生功能异常的原因，是产生告警事件的 原因。告警是由在特定事件发生时被管对象发出的通报构成的一种事件报告， 用于传递告警信息告警是一个系统发出的短消息，表示其发生了某些事情或 者异常j 但告警只是表示可能有故障发生，并不一定有故障发生。资源的被管 对象可以发出告警事件作为对系统当前发生异常的响应。 告警事件包含被管对象状态异常的信息，一个告警消息通常包含以下信息： 有关发出告警的设备的信息，故障的征兆，以及告警产生的时间。然而告警只能 反映本身被管对象局部的信息，通常并不明显包含网络中故障和问题根源的确切 位置信息，当网络中出现故障时，会引发一系列告警，但并不是所有告警都表明 故障原因，这就需要通过分析网络产生的所有告警来判断故障的根本原因。必须 需要注意的是，告警仅仅是反应网络状况发生改变的征兆，这就是说，通常是故 障产生了告警，一个故障可能是另一个故障的根源，但一个告警绝对不会产出其 它告警。 告警故障关联【”】，就是找出告警集合和故障之前的对应关系，告警和故障 之间的关系大多数情况下是一对多的关系，但是也有可能是一对一和多对多的关 系，特别是在业务层，告警可能是由一个故障引起的，也可能是由多个故障引起 的，同一个故障，在不同的时间可能会产生不同的告警，因此告警和故障之间的 关系更加显示出不确定性。当告警发生时，只有快速准确的定位出引起此告警集 合的故障集合，对各个故障逐一修复，响应的告警集合才消失，业务才会正常运 行，服务质量才能得到保证。 2 1 2 贝叶斯网络 贝叶斯网络是一种帮助人们将概率统计应用于复杂领域、进行不确定性推理 和数据分析的工具，是一种系统的描述随机变量之间关系的语言，其特点决定其 在处理协议栈高层业务应用相关故障有着巨大的优势，同时也可以很好的定位协 议栈低层的网络故障。自1 9 8 8 年p e a r l 给出明确定义后，对其的研究和应用成为 学术界的一个热点之一。贝叶斯网本身【1 6 】是一种有向无环图( d a g ) 。图中节点 代表随机变量，节点间的有向边代表了节点间的依赖关系( 由父节点指向其后代 节点) 。每个节点有一个对应的条件概率矩阵表达节点问依赖关系的强度，没有 父节点的节点( 最高节点) 则使用先验概率进行信息表达。它使用概率方法进行不 确定性推理，把问题用组随机变量a2 弘- ，五z9 , - 9 a n j 来刻画，把关于问题的 知识表示为一个联合概率分布，uj ，按照概率论原则进行推理计算。构造贝叶 斯的目的是进行概率推理，即计算一些事件发生的概率，要在一些随机变量之间 进行概率推理，理论上只需要一个联合概率分布即可，但是联合概率分布的复杂 度相对于变量个数成指数增长，所以当变量众多时不可行。贝叶斯网把复杂的联 合概率分布分解成一系列相对简单的模块，从而大大降低了知识获取的难度和概 率推理的复杂度。 推理是通过计算【l7 】回答查询的过程，贝叶斯网中的推理问题有三类：后验 概率问题( b d i e f u p d a t i n ga l s oc a l l e dp r o b a b i l i s t i ci n f e r e n c e ) ，最大后验假设问题 ( b e l i e fr e v i s i o na l s oe a l l e dm a p e x p l a n a t i o n ) 1 1 8 j 以及最大可能解释问题( m o s t p r o b a b l ee x p l a n a t i o na l s oc a l l e dm p e ) 。后验概率问题指的是已知贝叶斯网中某个 变量的取值，计算另外一些变量的后验概率分布的问题：己知变量通常称为证据 变量( e v i d e n c ev a r i a b l e s ) ，记为e ，它们取值记为e ：需要计算其后验概率分布 的变量称为查询变量( q u e r yv a r i a b l e s ) ，记为q ；需要计算的后验分布为p ( q e = e ) 。 最大后验假设问题：已知证据e = e ，有时会对一些变量的后验概率最大的状态组 合感兴趣，这些变量称为假设变量，记之为h 。h 的一个状态组合称为一个假设， 记之为h 。在所有可能的假设中，想找出后验概率最大的那个假设h ，即h 。= 榷 m a x ( h 圳e = e ) 。最大可能解释问题：在贝叶斯网中，证据e = e 的一个解释指的 是网络中全部变量的一个与e = e 相一致的状态组合。往往有时最关心概率最大 的那个解释，即最大可能解释。求最大可能解释的m p e 问题可视为m a p 问题 的一个特例，即m a p 中的假设变量h 包含了网络中的所有非证据变量。 针对基于贝叶斯网络的推理，已经提出了许多推理算法，可以分为两大类精 6 确推理算法和近似推理算法。基于静态贝叶斯网络的算法较多，但是基于动态贝 叶斯网络的算法相对来说比较少，大都是对基于静态贝叶斯网络的扩展或是改 进。 2 2 常用故障定位技术 在网络层及其以下各层，故障和症状的关系大多数情况下是确定性的，即当 某个故障发生时，此故障必然导致一定的外在状态的出现，也即只要观测到特定 的症状信息，就认为某个特定的故障一定发生，因此确定性的故障定位方法【l 9 】 得到了广泛的应用，其中最流行的是基于模型的方法。但是随着网络规模的不断 扩大、复杂企业业务应用的广泛部署，特别是在业务层，故障和症状之间的关系 表现出来越来越多的不确定性，因此不确定性推理技术进入研究者的视野，其中 最受关注的是基于贝叶斯网络的方法，包括基于静态贝叶斯模型和基于动态贝叶 斯模型的方法。 2 2 1 基于模型的方法 在基于模型的定位系统中，每个被管对象都有一个模型与之相对应。一个模 型实际上就是一个软件模块。处于网络管理系统中的事件相关器建立在面向对象 的模型之上，模型之间的协作形成事件关联。这样，模型之间的关系反映出它们 所代表的被管网元之间的关系。每个模型通过与自身所表示的被管网元以及与其 它模型之间进行通信，分析自身所表示的网元是否发生故障。因此，网元的故障 是由模拟该网元的模型识别出，然后报告给网络管理系统。 基于模型的故障定位方法，对根源故障的定位建立在面向对象的模型基础之 上。首先，该类方法会充分利用现有的系统知识，将被管系统的各类物理实体和 业务应用逻辑实体建模为诊断对象，诊断对象之间的关联关系也会被清晰地描 述，从而建立起一个反映了实际系统的结构和行为的模型。然后，基于模型的故 障定位的主要是通过分析模型和实际系统的差异来进行的。一个系统由多个功能 不同的被管对象组成，这些对象之间有着一定的连接关系，并且对象本身要遵循 一定的逻辑以实现系统的部分功能。而模型是对现实系统物理实体、逻辑实体的 理想描述，因此构成模型的基本成分也是会满足一定的理想规则的。由于故障的 出现，系统的实际行为和理想模型必然会出现一定的偏差，此时定位系统通过比 较分析两者的差别，从而定位实际系统错误的根源。 基于模型的方法，依赖于一定的规则，网络越大，规则库就越大，网络中实 体变动时对整个规则库的更新将是非常耗时的。模型需要反映系统底层的细节， 7 因此这种方法具有解决一些新出现的故障的潜力，但当出现的问题超出模型的知 识范围时，其故障诊断的准确将大大下降。对于不同的目标系统，它们的网络拓 扑、业务拓扑结构都不相同，导致模型的知识难以获得和保持持续更新，因此基 于模型的故障定位技术并不具有自适应和自学习的功能。 2 2 2基于静态贝叶斯网络的方法 2 2 2 1 精确推理算法 精确推理算法有变量消元算法，迭代信度传播算法【2 0 】和团树传播算法。变量 消元算法是最普遍，原理最简单的算法，它适用于任何形态的贝叶斯网，但是它 是复杂度最高的一个算法，算法复杂度是指数级的，并且其复杂度与消元顺序有 很大关系。迭代信度传播算法精确推理算法中唯一的一个算法复杂度是多项式级 别的推理算法。但是它只适用于满足p o l y t r e e 的贝叶斯网，也就是说贝叶斯网中 不能含有无向环这个算法的要求太苛刻，不利于改进。团树传播算法( 如图2 1 所示) 是变量消元算法的另外一种形式，它使用团树的形式来组织消元，消除了 冗余。主要思想是：从贝叶斯网出发，按一定顺序进行消元；在消去某个变量x 之前，先构造一个由x 以及所有与x 相邻的变量组成的团；若与删除节点相邻 的两节点之间不存在边，则需在这两个节点之间添加一条边。在消元过程结束后， 把所产生的团以适当方式进行组织，得到一颗覆盖整个网络节点团树，团树算法 的复杂度也相对较高，成指数级增长，但是由于它以团树的形式组织消元，信息 在各个团之间分发和收集，所以它更适用于动态贝叶斯模型。 基于静态贝叶斯网络的精确算法虽然准确度非常高，但是由于算法复杂度也 同样很高，既消耗空间又浪费时间，只适用于节点数目较少的贝叶斯网络，不能 满足大规模贝叶斯网的推理需求，因此不适应于大型的网络。 2 2 2 2 近似推理算法 图2 - 1 团树传播算法 由于基于贝叶斯的精确算法存在复杂度过高的问题，虽然定位准确度相当 高，但是严重受到被管网络规模的限制，因此以贝叶斯推理的精确算法为基础， 近年来出现了形形色色的推理算法，其中具有代表性的有i b m 研究院系统与技 术组研究的i h u 算法【2 1 1 ，卡利福尼亚大学伯克利分校研究的m a x c o v e r a g e 算法【2 2 】 和麻省理工研究的s h r i n k 算法【2 3 】等，这些算法都是基于二分图的，如图2 2 所示。 i h u 算法是事件驱动故障定位技术，用症状到故障的概率映射关系作为故障 传播模型。通过症状解释假设的增量更新来找到最有可能的故障集合，并且这些 故障被分成不同等级。算法的基本思想是：限定同时发生的故障最多为i f i ，每观 察到一个症状，更新假设集合( 假设集中元素为f 的部分子集，每个子集都能独 立的解释目前所有观察到的症状) ，假设集合中概率最大的为最优解释；如果概 率相同，集合较小的为最优解释。同时限定假设集合中元素的个数i f i ，如果个数 等于| f i ，移除最大的集合( 这里假设多个故障同时发生的概率小于单个故障发生 的概率) ，保证继续更新。因此，m u 算法快速定位出能够解释当前所有症状的 最小故障集合，不考虑先验概率和条件概率的情况下，此推理算法属于确定性推 理。它并没有涉及到特殊领域，建模方法和推理算法具有一般性。 m a x - c o v e r a g e 算法并不是事件驱动的模型，但和i h u 算法一样，是基 于二分图模型的算法。算法基本思想是：诊断系统收集到所有的症状以后，对每 一个症状进行诊断，分析出能够解释该症状的故障，加入到假设集合，轮训完成 后，输出解释症状数目最多的假设集合作为诊断的结果。 s h r i n k 算法同样是基于二分图模型的算法，算法的基本思想是：所有故障为 互，互，e ，症状为s ，足，& 。限定同时发生的故障数k ，即在特定时间内， 同时发生故障数最多为k 个，则对故障e ，e ，e 在k 个故障以内进行排列组合， 计算排列组合得到的每一个集合的条件概率p ( 互，ei 墨，氏) ，具有最大概率值 的集合。此算法的算法复杂度是复杂度为o ( m + n ) 。 以上算法可以对网络中的单故障和多故障的情况进行诊断，能够处理一定的 噪声，并且在准确度和复杂度上取得了一定的均衡，基本上可以满足静态网络故 障定位的需要。但是以上算法都有一个假设作为前提的，即模型准确并且模型中 各个节点的故障发生概率和节点之间的依赖关系不会随时间变化而改变。以上算 法均没有考虑到模型不准确，或是模型中节点的概率发生变化的情况，所以不能 应用于动态系统。 9 0 0 2 0 0 1 图2 - 2 二分图 2 2 3基于动态贝叶斯网络的方法 2 2 3 1 精确推理算法 基于动态贝叶斯模型的精确推理算法主要有f o r w a r d s - b a c k w a r d s 算法、 f r o n t i e r 算法、t h ei n t e r f a c e 算法等。f o r w a r d s b a c k w a r d s 算法是最简单，也是复 杂度最高的算法，它适用于各种模型，也是其它算法的基础算法。f r o n t i e r 算法 是用一个时间片的所有隐藏节点d 分割过去和未来，然后将概率信息收集到这组 隐藏节点，然后利用此时间片的隐藏节点向后续时间片传递概率信息。通常情况 下，某个时间片的隐藏节点集合，比需要的节点集合要大，我们只需要有出弧指 向下一个时间片的节点集合就足够可以d 分割过去和将来了，这组节点集合被称 为i n t e r f a c e 。此算法被称为i n t e r f a c e 算法。 虽然精确算法有较好的定位准确度，但是这些算法即使在单个时间片的复杂 度都难以令人接受，在多个时间片上定位出故障时，已经失去了意义了即故障早 已经恢复。因此，精确推理算法不能满足大规模的动态贝叶斯网络推理的需要， 进而不能满足大规模的动态系统故障定位的需要，因此研究者把目光转向近似推 理 2 2 3 2 近似推理算法 而基于动态贝叶斯模型的算法相对来说比较少，这些算法都是对以上基础算 法的改进，伯克利发表的一篇论文，曾对动态贝叶斯模型的表示，推理和学习作 了详细的论述，现有的基于动态贝叶斯模型的算法主要有t h eb o y e n - k o l l e r ( b k ) a l g o r i t h m 、f a c t o r e df f o n t i e r ( f f ) a l g o r i t h m 、l o o p yb e l i e fp r o p a g a t i o na l g o r i t h m ( l b p ) 以及p f 算法【矧( p a r t i c l ef i l t e r i n g ) ，b k 算法、f f 算法和l b p 算法是近似推理中 1 0 的确定性算法，都是对团树算法应用于动态贝叶斯模型所产生的，如图2 3 所示。 b k 算法是t h ei n t e r f a c ea l g o r i t h m 的因式分解的表现形式，基本思想：用一组概 率函数的乘积近似i n t e r f a c e 上的联合概率。b k 算法的最好情况是：观测无噪声 或是传播矩阵最大可能的随机( p ( x t l x t 。1 ) 独立于x t - 1 ) 。相反，最坏情况是： 观测有缺失、信息不全或是转移矩阵是确定性的，此时误差随时间增长。f f 算 法是t h e f r o n t i e ra l g o r i t h m 的因式分解的表现形式，此算法中我们并不需要所有 的f r o n t i e r ，只需要i n t e r f a c e 。它与b k 算法的不同在于近似更新的方式。b k 因 式分解先验概率，根据团树算法执行一次更新，然后执行一次边缘化的操作。但 是对于某些模型，即使利用团树算法执行一次都是不可接受的。f f 不再做精确 更新然后边缘化，而是直接进行边缘化计算。当向f r o n t i e r 加入一个节点的时候， 不再把它的c p d s 乘到f r o n t i e r 联合概率上，只是计算它和它的父节点的局部联 合概率，将c p d s 乘到这个局部联合概率上，然后边缘化。p f 算法是基于动态 贝叶斯模型的近似推理中的随机算法，算法思想是用一组带权的样本来近似信度 状态，可分为三个重要的步骤：抽样、权重计算和在抽样。第一个时间片按照似 然加权法进行抽样，从第二个时间片开始抽样函数为传播概率即根据传播概率和 上一个时间片本节点的抽样值决定。对于观测节点，以观测值作为抽样结果。对 于每一个时间片，算法的输入是上一个时问片每个节点的抽样值、对应的权值及 证据，输出是每个节点的抽样值及对应的权值。最终输出是当前时间片未知节点 的后验概率。抽样算法的缺陷是样本无效和样本衰减，即通过迭代之后，除了一 个样本的权值很大外，其他样本的权值可能变得很小，此时样本权值的方差可能 变的很大，算法的收敛速度变慢( 样本权值的方差越小，说明抽样函数越接近于 最优抽样函数) ，此时需要进行再抽样。通过再抽样来纠正样本的权值。而这些 算法并没有在故障诊断中得到实际应用。仅有的是i b m 系统与技术研究组在 2 0 0 5 年研究中，应用动态贝叶斯模型解决了动态网络中故障诊断的一些简单问 题( 即两个时间片之间最多有一个节点的状态发生改变) ，它所使用的动态贝叶 斯模型如图2 4 所示。 图2 - 3b k 算法模型 2 3算法比较 懒i 皤 毪 t i m | h 一 伍 图2 - 4 两个时间片d b i q 基于模型的故障定位方法依赖于准确的模型的定义，当出现的问题超出模型 的范畴时，其定位准确度将会大大的下降。当网络结构发生变化时，往往需要对 模型做进一步的修正以便反映网络的最新变化以提高定位的准确度，但是于不同 的目标系统( 变化后的系统) ，它们的模型基本都不相同，而且模型的知识难以 获得和保持更新，对模型进行操作时的计算是非常复杂的。因此此类方法也适合 于网络变化不是特别频繁和网络模型较易建模的简单通信网络中。 基于静态贝叶斯贝叶斯网络的故障定位方法，通过收集监控系统采集到的症 状信息来计算所需节点的相关概率，而节点相关概率的计算被证明是是一个 n p h a r d 2 5 j 的问题。通过采用恰当的启发式算法，可以在可接受的时间内完成几 千个节点的计算，但贝叶斯网络边界概率计算效率仍是一个有待解决的问题。虽 然也提出了一些近似推理算法，但是还是未在时间复杂度和定位准确度之间取得 一个良好的平衡，i h u 取得了很好的定位准确度，但是定位时间难以满足实际应 用系统的需求，特别是在大型通信网络中，其定位时间过长；s h r i n k 能够迅 速的定位故障的根源，但是其定位准确度却大打折扣。基于静态贝叶斯模型的故 障定位都有一个共同的假设作为前提，即在故障诊断的过程中，被管系统是不变 的，即诊断过程中各个节点的状态不