网络点对连通可靠度的近似计算

　　现实世界中的许多网络,如计算机通信网络和分布式多处理器系统等,都会出现由于网络的节点或链路发生故障而导致网络功能降低,甚至整个网络失效的现象。因此分析已有网络的可靠性和设计高可靠性网络具有重要的理论和实用价值。一个网络的抽象结构可用一个无向简单图G=(V,E)表示,即由顶点集V,边集E和二者到区间[0,1]上的两个函数:Φ:V→[0,1]和Ψ:E→[0,1]构成。这两个函数分别被看作对应点和边出故障的概率。因此,网络的可靠性R(G,Φ,Ψ)定义为:图G的顶点和边分别以Φ和Ψ为故障函数的情况下,图G仍保持连通的概率。通常作如下3点限制:

　　(1)所有点都可靠而边不可靠Φ≡0Ψ≠0

　　(2)所有边都可靠而点不可靠Φ≠0Ψ≡0

　　(3)所有点和边都不可靠Φ≠0Ψ≠0

　　无论对于点失效、边失效还是点边混合失效网络模型,精确计算任意规模网络的可靠性测度都已被证明是NP-hard问题[1];随着计算机网络规模的不断扩大,快速精确地计算可靠度是一个现实性难题。因此,部分研究者关注于网络可靠度的近似计算问题上,采用相对简单的计算方法,通过确定网络可靠度上下界值来评估网络可靠性,从而对网络的可靠性分析和可靠性综合提供有价值的参考依据。

　　1边失效情况下的点对连通可靠度

　　在边失效条件下的全终端、两终端和K终端可靠度的计算,主要关注于网络的边割集和最小路与网络可靠性之间的关系[2]。随着网络规模的扩大,网络的最小路与边割集特性也随之复杂化。Amin等人提出了另外一种可靠性测度[3],关注于当网络结点或链路以一定概率相互独立地失效时,网络中仍然能够保持连通的点对(pair-Connected)数量的数学期望值。有如下定义[3]:

　　定义1令G(m,n)表示一个具有m个点,n条边的无向简单图。对于S E(G),|S|=k,令P(s表示图G处于状态S的概率,令PC(S)表示图G在状态S下保持连通的点对的个数, (即由图G的状态S导出的子图中保持连通的点对的个数),p表示边存活的概率,q=1-p表示边失效的概率,则图G的点对连通可靠度可定义为:

　　上式的数学含义:当点可靠,边以概率q相互独立地失效时,网络G中保持连通的点对数量的数学期望值。基于数学期望值的网络可靠性测度有着其他类型测度不可比拟的优点,能够更加真实地反映网络的可靠程度。例如,对于两个网络G(n,m)和H(n,m),G是连通的,H是非连通的,若用点对连通可靠度衡量两个网络,可以反映出H的可靠度比G高的特殊情况,而这种特殊情况是其他可靠性测度无法反映出来的。目前关于边失效情况下点对连通可靠性的研究不是很多,Siegrist等[4]给出了边失效情况下点对连通可靠度多项式的特征和系数确定方法,并证明了对于网络