网络可靠性分析方法研究.doc

网络可靠性分析方法研究 　　摘要：总结了进行网络可靠性分析的一般步骤，比较了传统的网络分析方法的优缺点，重点论述了一种基于有序二叉决策图的方法，在考虑失效节点的网络可靠性分析中的应用。 　　关键词：网络可靠性；状态空间；割集；连接集；图转换；OBDD 　　中图分类号：TP393.08 文献标识码：A文章编号：1007-9599 (2011) 13-0000-02 　　Network Reliability Analysis Research 　　He Cong 　　(Chengdu Institute Sichuan International Studies University,Chengdu611731,China) 　　Abstract:The steps of analyzing network reliability are summarized,the traditional methods are compared.Strategies based on edge expansion diagram using OBDD are taken as efficiently method for evaluating network reliability with imperfect nodes. 　　Keywords:Network reliability;State-space;Cut-set;Tie-set;Graph transformation;OBDD 　　一、引言 　　许多物理问题都可以用网络来建模，例如计算机网络，管道系统和电力网等。网络主要保证两个节点或多个节点之间能交流信息相互操作。理想情况下，只要在图中存在节点与节点之间的路径即可，但是在实际情况中，节点和节点的连接会由于种种原因而失效，如线路老化，断裂等等。在这种情况下，网络上的两点或多点能将数据可靠地传达到对方或者操作成功的概率是多少，这正是网络可靠性分析要研究的问题。本文主要关注计算机网络的可靠性分析问题。 　　二、网络可靠性的定义 　　网络可靠性是指在一定的环境条件下，在给定的一段时间内，网络系统正常运行的概率。正常运行有很多种理解方法。假设随着时间的流逝，m个连接失效。如果我们关注一对节点（s，t）之间的通信（其中s为源节点，t为目标节点）那么系统成功运行被定义为s与t之间存在运行路径。这被称为两终端问题（two-terminal）。s与t之间成功通信和概率被称为两终端可靠性。类似地，k终端问题（k-terminal）是有k个节点（ ）的子集都存在连接的概率。 　　三、网络可靠性分析的基本方法 　　评价网络可靠性是件困难的事情，但也有一些方法。传统的方法一般只考虑边失效的情况。传统方法主要是状态空间枚举法。 　　这是一种最直观的方法，将所有满足条件的事件列举出来然后求其并的概率。具体如下： 　　首先考虑两终端可靠性问题。 　　在网络图中，每一条边可能有效，也可能失效，一共有 种组合，每种组合可以认为是一个事件 ，这些事件彼此独立。那么，两终端可靠性就可以表示为这些事件中含有S到T的路径的事件的并的概率。即： 　　（1） 　　或 （2） 　　注意公式（1）中的“＋”代表“ ”，而公式（2）中的“＋”代表求和。 　　对于k终端可靠性问题，它是一个更一般的概念，即k个终端必须连接。K=2就是两终端可靠性，k=n就是全终端可靠性。 　　因其复杂度随问题的规模呈指数增长，实践中很少应用。 　　四、基于OBDD的方法 　　前面的方法均将节点假设为不失效，然而在实际应用中，节点也会失效。此时，列举所有可能路径的复杂性将显著增加，在文[4]中，Aggarwal强调，通过修改概率方程式就可以将已有的对理想节点网络可靠性的算法转化为考虑失效节点时的算法，并且宣称这种方法可以被嵌入到任何可靠性函数的符号表达式中，基于文[8]中的概念，文[5]中提出了很多考虑失效节点时的代替边的概率的内嵌公式。在文[5]中Theologou直接应用失效节点因式分解定理来划分网络，每次基于一条边划分，并且得到两个因子。同时他们也使用了一些缩减规则来减少子问题的数量。 　　在文[6]中，Fu-Min Yeh提出一种基于OBDD[7]（即有序二叉决策图）的方法。OBDD是一种表示和操作布尔函数的有效方法。可以将其看成是图转换中边因素法思想的扩展。它是含有一个根节点和2个终端节点（标记为0和1）的有向无环图，内部节点用布尔变量标记，并且有两个引出边，分别标记为0和1。OBDD对变量序进行了限制：如果 节点引出一条边到 节点，在变量序中 必须位于 前面。 　　例如：对于函数 变量排序为 转化为OBDD表示如图1所示：