论文部分内容阅读
摘要：总结了进行网络可靠性分析的一般步骤，比较了传统的网络分析方法的优缺点，重点论述了一种基于有序二叉决策图的方法，在考虑失效节点的网络可靠性分析中的应用。
关键词：网络可靠性；状态空间；割集；连接集；图转换；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所示：
OBDD是基于布尔函数的一种分解，即所谓的香农扩展（Shannon expansion）。一个函数f可以针对变量x分解为 。 和 分别为针对x的正负余因子。具体应用到网络图上时，变量x和 可以代表一条边有效和无效， 表示x边有效时扩展的子图， 表示x边无效时扩展的子图，递归地将子图进一步扩展可以得到一系列的路径集，递归地将子图进一步扩展可以得到一系列的路径集，然后用路径集函数计算网络的可靠性。OBDD保证在基于OBDD扩展成的路径集函数中这些路径是不交的。对于两终端问题，基于每条连接到源节点的边来扩展图。设 为连接到源S的边，则可以将给定的网络图G扩展成k个子图 ，该子图就是将源点S沿边 收缩到 所连接的边，这样路径集函数就可以表示为：
，其中 和 是边 和源点 的布尔变量。然后反复对每一个函数递归的使用 即可计算出可靠性。基于OBDD的策略提供了一种系统化求解可靠性概率的方法，值得进一步研究。
五、小结
分析网络可靠性的方法基本上都是基于前述的三种基本方法的，不同之处在于很多方针针对其缺点做了改进，但对于考虑失效节点的网络可靠性分析，基于OBDD的策略值得进一步研究。
参考文献：
[1]Shooman M L.Probabilistic Reliability:An Engineering Approach,2nded.Krieger,Melbourne,Fl,1990
[2]曹晋华,程侃.可靠性数学引论[M].北京:科学出版社,1986
[3]Shooman A M,Kershenbaum A.Exact Graph-Reduction Algorithms for Network Reliability Analysis.In:Proc.IEEE/GLOBECOM Conf.IEEE,New York,NY,Dec.1991
[4]Aggarwal K K,Gupta J S,Misra K B.A simple method for evaluation of a communication system.IEEE Trans.Communications,May,1975,23:563-566
[5]Theologou O R,Carlier J G.Factoring&reductions for networks with imperfect vertices.IEEE Trans.Reliability,1991,40(2):210-217
[6]Yeh Fu-Min,Lin Hung-Yau,Kuo Sy-Yen.Analyzing network reliability with imperfect nodes using OBDD.PRDC’02,IEEE,2002
[7]Bryant R E.Graph-based algorithms for Boolean function manipulation.IEEE Trans.Computers,1986,35(8):677-691
关键词：网络可靠性；状态空间；割集；连接集；图转换；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所示：
OBDD是基于布尔函数的一种分解，即所谓的香农扩展（Shannon expansion）。一个函数f可以针对变量x分解为 。 和 分别为针对x的正负余因子。具体应用到网络图上时，变量x和 可以代表一条边有效和无效， 表示x边有效时扩展的子图， 表示x边无效时扩展的子图，递归地将子图进一步扩展可以得到一系列的路径集，递归地将子图进一步扩展可以得到一系列的路径集，然后用路径集函数计算网络的可靠性。OBDD保证在基于OBDD扩展成的路径集函数中这些路径是不交的。对于两终端问题，基于每条连接到源节点的边来扩展图。设 为连接到源S的边，则可以将给定的网络图G扩展成k个子图 ，该子图就是将源点S沿边 收缩到 所连接的边，这样路径集函数就可以表示为：
，其中 和 是边 和源点 的布尔变量。然后反复对每一个函数递归的使用 即可计算出可靠性。基于OBDD的策略提供了一种系统化求解可靠性概率的方法，值得进一步研究。
五、小结
分析网络可靠性的方法基本上都是基于前述的三种基本方法的，不同之处在于很多方针针对其缺点做了改进，但对于考虑失效节点的网络可靠性分析，基于OBDD的策略值得进一步研究。
参考文献：
[1]Shooman M L.Probabilistic Reliability:An Engineering Approach,2nded.Krieger,Melbourne,Fl,1990
[2]曹晋华,程侃.可靠性数学引论[M].北京:科学出版社,1986
[3]Shooman A M,Kershenbaum A.Exact Graph-Reduction Algorithms for Network Reliability Analysis.In:Proc.IEEE/GLOBECOM Conf.IEEE,New York,NY,Dec.1991
[4]Aggarwal K K,Gupta J S,Misra K B.A simple method for evaluation of a communication system.IEEE Trans.Communications,May,1975,23:563-566
[5]Theologou O R,Carlier J G.Factoring&reductions for networks with imperfect vertices.IEEE Trans.Reliability,1991,40(2):210-217
[6]Yeh Fu-Min,Lin Hung-Yau,Kuo Sy-Yen.Analyzing network reliability with imperfect nodes using OBDD.PRDC’02,IEEE,2002
[7]Bryant R E.Graph-based algorithms for Boolean function manipulation.IEEE Trans.Computers,1986,35(8):677-691