论文部分内容阅读
[摘 要]总结了进行网络可靠性分析的一般步骤，比较了传统的网络分析方法的优缺点，重点论述了一种基于有序二叉决策图的方法，在考虑失效节点的网络可靠性分析中的应用。
[关键词]网络可靠性，状态空间，割集，连接集，图转换，OBDD
中图分类号：TN915.08 文献标识码：A 文章编号：1009-914X（2013）09-0059-01
1 引言
许多物理问题都可以用網络来建模，例如计算机网络，管道系统和电力网等。网络主要保证两个节点或多个节点之间能交流信息相互操作。理想情况下，只要在图中存在节点与节点之间的路径即可，但是在实际情况中，节点和节点的连接会由于种种原因而失效，如线路老化，断裂等等。
2 网络可靠性的定义
网络可靠性是指在一定的环境条件下，在给定的一段时间内，网络系统正常运行的概率。正常运行有很多种理解方法。假设随着时间的流逝，m个连接失效。如果我们关注一对节点（s，t）之间的通信（其中s为源节点，t为目标节点）那么系统成功运行被定义为s与t之间存在运行路径。这被称为两终端问题（two-terminal）。s与t之间成功通信和概率被称为两终端可靠性。
3 网络可靠性分析的一般研究步骤
具体研究网络可靠性有多种方法，但一般的分析主要着眼于网络的拓扑结构，即考虑抽象的网络图G（V，E），其中V和E分别代表网络的点集和边集。
一般在对网络可靠性进行分析研究时，假设节点和节点之间安概率P进行有效连接。然后分析在概率P下，网络中各点有多大可能连接成功。通常，可以首先考虑网络中两点S和T之间成功连接的概率，即S为源点，T为目标点，从S连接到T成功的概率是多少，即两终端可靠性问题（two-terminal）。
对于连接失效的情况，不考虑中间状态，并且假设连接之间的失效是相互独立的，没有考虑失效连接的修复或者替换。用来描述可修复系统的度量是可用性。在大多数网络可靠性分析中，可用性和可靠性没有什么分别。Shooman对其做了详细的论证[2]。
4 研究的基本方法
评价网络可靠性是件困难的事情，但也有一些方法，对于一些大的实际的问题，可以使用计算可靠性的程序来完成。有些方法主要提供一种算法，可用来估计小网络，从而用来测试计算机程序是否可靠。
传统的方法一般只考虑边失效的情况。主要有以下三种方法：
（1）状态空间枚举法
这是一种最直观的方法，将所有满足条件的事件列举出来然后求其并的概率。具体如下：
首先考虑两终端可靠性问题。
在网络图中，每一条边可能有效，也可能失效，一共有种组合，每种组合可以认为是一个事件，这些事件彼此独立。
对于全终端可靠性问题，同样可列出事件空间，但筛选时应选出将图中所有点都连接起来的事件作为满足条件的事件。对于k终端可靠性问题，它是一个更一般的概念，即k个终端必须连接。K=2就是两终端可靠性，k=n就是全终端可靠性。
因其复杂度随问题的规模呈指数增长，实践中很少应用。
（2）最小连接集和最小割集法
对于两终端可靠性，连接集是形成一条从点s到点t路径的一组边的集合。实际考虑时常用最小连接集。“最小”是指从s到t的路径经过且仅经过每个节点和边不超过一次，即最小连接集就是没有真子集能构成连接集。
对于全终端可靠性问题，则需要分别找出所有节点对连接集和割集。然后，对于连接集计算法，应将不同节点连接集求其交的概率[1]。
这种方法与状态空间法相比较，从数量上大大减少了要考虑的事件，但是增加查找事件的复杂度，并将复杂度部分的转嫁到了具体的概率计算过程中。
（3）图转换法
图转换法是受电路理论中电阻值等价转换的启发，可以在网络中也进行串连、并连和转化[6]。但是应注意：进行网络图转换时不是进行流转换而是进行概率转换。
这种计算网络可靠性的方法基于将图转换成一个简单的网络（或者网络的集合）。这些方法对两终端可靠性计算很简单，但是对全终端可靠性计算就比较复杂。
5 基于OBDD的方法
前面的方法均将节点假设为不失效，然而在实际应用中，节点也会失效。此时，列举所有可能路径的复杂性将显著增加，在文[8]中，Aggarwal强调，通过修改概率方程式就可以将已有的对理想节点网络可靠性的算法转化为考虑失效节点时的算法，并且宣称这种方法可以被嵌入到任何可靠性函数的符号表达式中，基于文[8]中的概念，文[9]中提出了很多考虑失效节点时的代替边的概率的内嵌公式。
前面讨论的方法有如下的缺点：
（1）在处理大的布尔函数时，对基于容斥原理和不交和形式的公式计算效率很低；
（2）基于树的划分算法没有考虑对同构子问题的合并，这不可避免的会产生冗余计算；
（3）当仅有几个变量的概率发生改变时，这些算法不得不重新估算网络；
（4）没有有效的方法替换附属边函数（incidentedgefunction）[2]也没有提出有效的布尔函数简化方法。
现在Fu-MinYeh提出一种基于OBDD[10]（即有序二叉决策图）的方法。OBDD是一种表示和操作布尔函数的有效方法。可以将其看成是图转换中边因素法思想的扩展。它是含有一个根节点和2个终端节点（标记为0和1）的有向无环图，内部节点用布尔变量标记，并且有两个引出边，分别标记为0和1。递归地将子图进一步扩展可以得到一系列的路径集，递归地将子图进一步扩展可以得到一系列的路径集，然后用路径集函数计算网络的可靠性。对于k终端的可以做类似推广，具体参见文[11]。基于OBDD的策略提供了一种系统化求解可靠性概率的方法，值得进一步研究。
小结
分析网络可靠性的方法基本上都是基于前述的三种基本方法的，不同之处在于很多方针针对其缺点做了改进，但对于考虑失效节点的网络可靠性分析，基于OBDD的策略值得进一步研究。
参考文献
[1] Shooman M L.Reliability of Computer System and Networks. Fault Torlerance，Analysis And Design，Wiley，2002.
[2] Shooman M L.Probabilistic Reliability：An Engineering Approach，2nd ed.Krieger.
[关键词]网络可靠性，状态空间，割集，连接集，图转换，OBDD
中图分类号：TN915.08 文献标识码：A 文章编号：1009-914X（2013）09-0059-01
1 引言
许多物理问题都可以用網络来建模，例如计算机网络，管道系统和电力网等。网络主要保证两个节点或多个节点之间能交流信息相互操作。理想情况下，只要在图中存在节点与节点之间的路径即可，但是在实际情况中，节点和节点的连接会由于种种原因而失效，如线路老化，断裂等等。
2 网络可靠性的定义
网络可靠性是指在一定的环境条件下，在给定的一段时间内，网络系统正常运行的概率。正常运行有很多种理解方法。假设随着时间的流逝，m个连接失效。如果我们关注一对节点（s，t）之间的通信（其中s为源节点，t为目标节点）那么系统成功运行被定义为s与t之间存在运行路径。这被称为两终端问题（two-terminal）。s与t之间成功通信和概率被称为两终端可靠性。
3 网络可靠性分析的一般研究步骤
具体研究网络可靠性有多种方法，但一般的分析主要着眼于网络的拓扑结构，即考虑抽象的网络图G（V，E），其中V和E分别代表网络的点集和边集。
一般在对网络可靠性进行分析研究时，假设节点和节点之间安概率P进行有效连接。然后分析在概率P下，网络中各点有多大可能连接成功。通常，可以首先考虑网络中两点S和T之间成功连接的概率，即S为源点，T为目标点，从S连接到T成功的概率是多少，即两终端可靠性问题（two-terminal）。
对于连接失效的情况，不考虑中间状态，并且假设连接之间的失效是相互独立的，没有考虑失效连接的修复或者替换。用来描述可修复系统的度量是可用性。在大多数网络可靠性分析中，可用性和可靠性没有什么分别。Shooman对其做了详细的论证[2]。
4 研究的基本方法
评价网络可靠性是件困难的事情，但也有一些方法，对于一些大的实际的问题，可以使用计算可靠性的程序来完成。有些方法主要提供一种算法，可用来估计小网络，从而用来测试计算机程序是否可靠。
传统的方法一般只考虑边失效的情况。主要有以下三种方法：
（1）状态空间枚举法
这是一种最直观的方法，将所有满足条件的事件列举出来然后求其并的概率。具体如下：
首先考虑两终端可靠性问题。
在网络图中，每一条边可能有效，也可能失效，一共有种组合，每种组合可以认为是一个事件，这些事件彼此独立。
对于全终端可靠性问题，同样可列出事件空间，但筛选时应选出将图中所有点都连接起来的事件作为满足条件的事件。对于k终端可靠性问题，它是一个更一般的概念，即k个终端必须连接。K=2就是两终端可靠性，k=n就是全终端可靠性。
因其复杂度随问题的规模呈指数增长，实践中很少应用。
（2）最小连接集和最小割集法
对于两终端可靠性，连接集是形成一条从点s到点t路径的一组边的集合。实际考虑时常用最小连接集。“最小”是指从s到t的路径经过且仅经过每个节点和边不超过一次，即最小连接集就是没有真子集能构成连接集。
对于全终端可靠性问题，则需要分别找出所有节点对连接集和割集。然后，对于连接集计算法，应将不同节点连接集求其交的概率[1]。
这种方法与状态空间法相比较，从数量上大大减少了要考虑的事件，但是增加查找事件的复杂度，并将复杂度部分的转嫁到了具体的概率计算过程中。
（3）图转换法
图转换法是受电路理论中电阻值等价转换的启发，可以在网络中也进行串连、并连和转化[6]。但是应注意：进行网络图转换时不是进行流转换而是进行概率转换。
这种计算网络可靠性的方法基于将图转换成一个简单的网络（或者网络的集合）。这些方法对两终端可靠性计算很简单，但是对全终端可靠性计算就比较复杂。
5 基于OBDD的方法
前面的方法均将节点假设为不失效，然而在实际应用中，节点也会失效。此时，列举所有可能路径的复杂性将显著增加，在文[8]中，Aggarwal强调，通过修改概率方程式就可以将已有的对理想节点网络可靠性的算法转化为考虑失效节点时的算法，并且宣称这种方法可以被嵌入到任何可靠性函数的符号表达式中，基于文[8]中的概念，文[9]中提出了很多考虑失效节点时的代替边的概率的内嵌公式。
前面讨论的方法有如下的缺点：
（1）在处理大的布尔函数时，对基于容斥原理和不交和形式的公式计算效率很低；
（2）基于树的划分算法没有考虑对同构子问题的合并，这不可避免的会产生冗余计算；
（3）当仅有几个变量的概率发生改变时，这些算法不得不重新估算网络；
（4）没有有效的方法替换附属边函数（incidentedgefunction）[2]也没有提出有效的布尔函数简化方法。
现在Fu-MinYeh提出一种基于OBDD[10]（即有序二叉决策图）的方法。OBDD是一种表示和操作布尔函数的有效方法。可以将其看成是图转换中边因素法思想的扩展。它是含有一个根节点和2个终端节点（标记为0和1）的有向无环图，内部节点用布尔变量标记，并且有两个引出边，分别标记为0和1。递归地将子图进一步扩展可以得到一系列的路径集，递归地将子图进一步扩展可以得到一系列的路径集，然后用路径集函数计算网络的可靠性。对于k终端的可以做类似推广，具体参见文[11]。基于OBDD的策略提供了一种系统化求解可靠性概率的方法，值得进一步研究。
小结
分析网络可靠性的方法基本上都是基于前述的三种基本方法的，不同之处在于很多方针针对其缺点做了改进，但对于考虑失效节点的网络可靠性分析，基于OBDD的策略值得进一步研究。
参考文献
[1] Shooman M L.Reliability of Computer System and Networks. Fault Torlerance，Analysis And Design，Wiley，2002.
[2] Shooman M L.Probabilistic Reliability：An Engineering Approach，2nd ed.Krieger.