基于MDD的随机流网络可靠度分析算法研究

发布时间：2018-01-31 04:13

本文关键词： 网络可靠度随机流网络多值决策图　出处：《桂林电子科技大学》2015年硕士论文　论文类型：学位论文

【摘要】：随机流网络模型是一种多状态离散概率模型,常用来建模计算机网络、交通运输网、通信网等。网络可靠度是评估随机流网络性能的一项重要指标。由于随机流网络的多状态特性,随着网络规模的增长,评估随机流网络可靠度的容斥原理方法的生成项呈指数级增长,无法有效控制状态空间组合爆炸问题。多值决策图(Multi-valued Decision Diagram,MDD)适用于描述多状态变量,能够实现状态空间或者变量组合的隐式表示与搜索,从而缓解状态空间组合爆炸问题。本文基于多值决策图理论,分节点可靠边不可靠的网络和节点边都不可靠的网络两种情况,对约束条件下的随机流网络可靠度进行了研究。主要成果如下:(1)针对节点可靠而边不可靠的随机流网络,基于MDD给出评估成本和时间约束下随机流网络可靠度的BTSFN_MDD算法。给出成本和时间约束的随机流网络的形式化模型和可靠度定义。对评估随机流网络可靠度的Lin算法进行了分析,指出容斥原理是影响Lin算法计算效率的主要因素。针对这一问题,引入MDD评估成本和时间约束的随机流网络可靠度,给出BTSFN_MDD算法。实例分析及实验结果表明,BTSFN_MDD算法能够精确计算成本和时间约束的随机流网络可靠度,与Lin算法相比,BTSFN_MDD算法具有更好的时间效率。(2)针对节点和边都不可靠的计算机网络,基于MDD给出评估错误率和时间约束计算机网络可靠度的RTSCN_MDD算法。给出错误率和时间约束计算机网络的形式化模型和可靠度定义。对评估计算机网络可靠度的Lin算法进行了分析,指出容斥原理是影响Lin算法计算效率的主要因素。针对这一问题,引入MDD评估错误率和时间约束计算机网络可靠度,给出RTSCN_MDD算法。实例分析及实验结果表明,RTSCN_MDD算法能够精确计算错误率和时间约束计算机网络可靠度,具有较好的时间效率。(3)针对节点和边都不可靠的二状态网络,给出评估二状态网络可靠度的NEF_MDD算法。NEF_MDD算法划分单个节点与其未访问邻接边为一个集合,通过枚举节点和边的不同组合,合并导致子网同构的冗余状态,获得简化后的状态向量和可靠度向量,并将此用一个多值决策图变量来表述。通过使用自定义的MDD操作算子,构建整个网络的MDD,遍历MDD节点,计算网络的可靠度。与二元决策图方法相比,NEF_MDD算法能够降低决策图层数和节点规模,有助于节点和边不可靠网络的可靠度分析。
[Abstract]:Stochastic flow network model is a multi-state discrete probability model, which is often used to model the computer network and transportation network. Network reliability is an important index to evaluate the performance of stochastic flow networks. Due to the multi-state characteristics of stochastic flow networks, with the increase of network size. The terms generated by the exclusion principle method for evaluating the reliability of stochastic flow networks increase exponentially. Multi-valued Decision Diagram (MDD) is suitable for describing multi-state variables. It can realize the implicit representation and search of state space or combination of variables, so as to alleviate the problem of state space combination explosion. This paper is based on the theory of multi-valued decision graph. There are two kinds of cases: the network with unreliable edge of node and the network with unreliable edge of node. In this paper, the reliability of stochastic flow networks under constrained conditions is studied. The main results are as follows: 1) for random flow networks with node reliability and edge unreliable. Based on MDD, a BTSFN_MDD algorithm for evaluating the reliability of stochastic flow networks under cost and time constraints is presented. The formal model and definition of reliability of stochastic flow networks with cost and time constraints are given. The Lin algorithm of the reliability of the machine flow network is analyzed. It is pointed out that the principle of inclusion and exclusion is the main factor that affects the computational efficiency of Lin algorithm. In order to solve this problem, MDD is introduced to evaluate the reliability of stochastic flow networks with cost and time constraints. The example analysis and experimental results show that the algorithm can accurately calculate the reliability of stochastic flow networks with cost and time constraints, compared with the Lin algorithm. BTSFN_MDD algorithm has better time efficiency. Based on MDD, a RTSCN_MDD algorithm for evaluating the reliability of computer networks with time constraints and error rates is presented. The formal model and definition of reliability of computer networks with error rates and time constraints are given. The Lin algorithm of computer network reliability is analyzed. It is pointed out that the principle of inclusion and exclusion is the main factor that affects the computational efficiency of Lin algorithm. In view of this problem, MDD is introduced to evaluate the error rate and time-constrained computer network reliability. The example analysis and experimental results show that the RTSCN algorithm can accurately calculate the error rate and time-constrained computer network reliability. It has good time efficiency. It is aimed at the two-state network with unreliable nodes and edges. In this paper, the NEF_MDD algorithm for evaluating the reliability of two-state network. NEF _ D algorithm is proposed to divide a single node and its unvisited adjacent edges into a set, and enumerate the different combinations of nodes and edges. Combining the redundant states of subnet isomorphism, the simplified state vector and reliability vector are obtained, and this is expressed by a multi-valued decision graph variable, by using a custom MDD operator. Compared with the binary decision graph method, the Nefs MDD algorithm can reduce the number of decision layers and the scale of nodes. It is helpful to the reliability analysis of node and edge unreliable networks.
【学位授予单位】：桂林电子科技大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O212;O157.5

【相似文献】