Shortest distance and reliability of probabilistic networks
Shortest distance and reliability of probabilistic networks
复制标题
DOI：
10.1016/0305-0548(76)90017-4
复制
发表时间：
1976-12
期刊：
影响因子：
--
通讯作者：
P. Mirchandani
中科院分区：
文献类型：
--
作者：
P. Mirchandani
当链路的“长度”不是确定的，而是由随机过程控制时，网络中两点之间的“最短”路径不一定总是由相同的链路组成，而是取决于网络的状态。例如，在通信和运输网络中，链路上的旅行时间是不确定的，并且两点之间的最快路径不是固定的。本文提出了一种算法，当每个路段上的行程时间具有给定的独立离散概率分布时，计算网络中两个节点之间的期望最短行程时间。该算法假设两个节点之间的所有路径的知识和方法来确定路径的引用。在可靠性（即两个给定的点通过路径连接的概率）计算中，与每个链接相关联的是“失败”的概率和“成功”的概率。由于“故障”意味着无限的旅行时间，该算法同时计算可靠性。本文还讨论了该算法的能力，同时计算一些其他的性能指标，这是有用的紧急服务网络上运行的分析。
When the “length” of a link is not deterministic and is governed by a stochastic process, the “shortest” path between two points in the network is not necessarily always composed of the same links and depends on the state of the network. For example, in communication and transportation networks, the travel time on a link is not deterministic and the fastest path between two points is not fixed. This paper presents an algorithm to compute the expected shortest travel time between two nodes in the network when the travel time on each link has a given independent discrete probability distribution. The algorithm assumes the knowledge of all the paths between two nodes and methods to determine the paths are referenced.In reliability (i.e. the probability that two given points are connected by a path) computations, associated with each link is a probability of “failure” and a probability of “success”. Since “failure” implies infinite travel time, the algorithm simultaneously computes reliability. The paper also discusses the algorithm's capability to simultaneously compute some other performance measures which are useful in the analysis of emergency services operating on a network.