两端多状态网络可靠度的研究  

Study of two-terminal multi-state network reliability

作　　者：王冰山[1] 宋月[1] 王玉梅[2] 

机构地区：[1]西安电子科技大学数学系,西安710071 [2]陕西科技大学电气与信息工程学院,西安710021

出　　处：《计算机应用研究》2011年第5期1863-1865,共3页Application Research of Computers

摘　　要：对带流量的大型网络,利用状态空间截尾的思想,在ORDER-M算法的基础上构造了一种新的算法———ORDER-M-π算法,利用该算法产生多状态网络前K个最可能出现的状态,且所产生的前K个状态发生的概率能覆盖整个网络状态空间的95%以上。对产生的K个网络状态分别应用流量网络中的最大流算法计算其所能产生的最大流量,累计能成功传输给定流量的网络状态发生的概率,由给出的多状态网络两端可靠度的定义,可得其可靠度。实验结果表明,ORDER-M-π算法不但能大大地节约计算成本,且所产生的可靠度具有良好的精确度。For large networks with flow,this paper proposed a new algorithm ORDER-M-π based on algorithm ORDER-M utilizing the theory of state space truncation.The first produced K states of multi-state network that were most possible to happen using this algorithm,and the possibilities of these K states could cover over 95% of the space of the total network states.Applied the max-flow algorithm in flow network to compute the maximum flow of the produced K network states respectively,and accumulated the probabilities of the network states which could successfully transfer the given flow.According to the definition of the two-terminal reliability of the given multi-state network,the reliability could be obtained.Experimental results show that algorithm ORDER-M-π not only reduces the computational cost,but also provides more accurate reliability.

关 键 词：可靠度 ORDER-M-π算法 ORDER-M算法 状态空间截尾 多状态网络 

分 类 号：P393[天文地球—地球物理学]