论文部分内容阅读
随着经济的发展,计算机网络、通信网络、电力供应网络、自来水供应网络,天然气供应网络,交通网络等等,在国民经济中的地位也越来越重要.网络的可靠性问题已经是关系到国民经济健康发展的重要环节.本文针对两状态网络和多状态网络的两端可靠性问题进行了研究,主要工作如下:针对网络两端可靠性问题是NP难问题,不易精确计算的情况,本文在网络链路只有工作和故障两种状态,且各条链路的失效率足够小的情况下,证明了网络故障边数不超过2的概率大于2.5/e,从而利用网络状态空间截尾的思想,应用Markov模型对截尾后的网络状态进行分析,获得了两状态网络两端稳态可用度的下界.针对流量网络,网络的链路除了正常工作和失效两种状态还有不同的降级状态,此时的网络为多状态网络.本文首先介绍多状态网络两端可靠性的有关概念以及求多状态网络两端可靠性的算法,接着改进Ramirez-Marquez等人的算法,优化信息共享的机制,提出基于排序的最小割集算法.通过算例发现,对小规模的网络,这种改进意义不大,但对稍大规模的网络,这种改进可以大大减少计算最小割集所需的计算成本.分析多状态网络的状态空间发现,有相当一部分状态出现的概率非常小,某些状态发生的概率和几乎占据到整个状态空间.本文改进ORDER-M算法在多状态网络中找出在实际运行中最有可能发生的前K个网络状态的方法,保证所生成的前K个状态发生的概率和占网络状态总的空间的足够大比例.此时认为这K个网络状态就是在实际运行中发生的网络状态.在此基础上,利用最大流算法对这K个状态进行分析,从而获得多状态网络的两端可靠性.