费用约束下的多状态网络可靠性评估方法

Evaluation Method for Multi-state Network Reliability Under Cost Constraint

多状态网络是指网络及其组成单元具有多种不同的性能水平,该网络模型已被广泛应用于描述现实中众多技术网络的行为特征。费用约束下的多状态网络可靠性Rel(d,b)是指网络能够把d单位的需求流量从源点成功输送到汇点且总的流传输费用不超过给定预算b的概率,该可靠性指标可以通过费用约束下的极小容量向量(简称(d,b)-MCV)来计算。由于(d,b)-MCV问题是典型的NP-hard问题,求解时间会随着网络规模增加呈指数增长,为提高求解效率,利用边的容量下限建立了关于(d,b)-MCV的改进数学模型,并从求解复杂度方面证明了该模型的优势;并且,利用超越数的概念,建立了(d,b)-MCV与实数之间的一一映射关系;基于此关系,提出了一种新的(d,b)-MCV去重方法。复杂度分析表明,该去重方法比现有方法更实用、更高效。最后,利用数值实验对提出的(d,b)-MCV算法的性能进行了检验;结果表明,该算法在求解(d,b)-MCV方面具有明显的效率优势,从而为费用约束下的多状态网络可靠性评估提供了一种新方法。

Multi-state networks are composed of multi-state components that have different performance levels,and multi-state network model has been extensively used to describe the complex behaviors of many technological networks.Multi-state network reliability under cost constraint,denoted by Rel(),is defined as the probability that the network is able to transmit d units of flow from the source to the destination while satisfying the condition that the total transportation cost is within a given budget b,and can be computed in terms of minimal capacity vector with budget constraint(called(d,b)-MCV for short).Solving(d,b)-MCVs is an NP-hard problem,which means the computational time will exponentially increases with the network scale.In order to enhance the efficiency of solving(d,b)-MCVs,this paper constructs an improved model by introducing lower capacity bounds of arcs,and theoretically demonstrates the merit of the model.Furthermore,this paper employs the concept of transcendental number to establish a one-to-one mapping relationship between(d,b)-MCV and real number,based on which a novel method is proposed to remove duplicate(d,b)-MCVs.It is demonstrated from the viewpoint of time complexity that the proposed method is more practical and efficient in comparison with the existing ones.The performance of the proposed(d,b)-MCV algorithm is tested by numerical experiments,and the results indicate that the algorithm is more efficient in solving(d,b)-MCVs and thus provides a new method for computing Rel().