一类节点与弧的容量均有限制的随机流量网络可靠度的计算

现实生活中的许多系统常可以用节点与弧的容量均有限制的随机流量模型来描述。给定要求d,这种网络的可靠度定义为最大流不小于d的概率。通过系统扩展,提出了两个简单的算法以找出系统的最大下界向量和最小上界向量,从而进一步计算出系统系统的可靠度。可以看到,通过这种系统扩展,许多已有的算法都可应用到这类比较复杂的系统中去。     

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

摘 要：对带流量的大型网络,利用状态空间截尾的思想,在ORDER-M算法的基础上构造了一种新的算法:ORDER-M-π 算法,利用该算法产生多状态网络前K个最可能出现的状态, 且所产生的前K个状态发生的概率能覆盖整个网络状态空间的95％以上。对所产生的K个网络状态分别应用流量网络中的最大流算法计算其所能产生的最大流量,累计能成功传输给定流量的网络状态发生的概率,由给出的多状态网络两端可靠度的定义,可得其可靠度。实验结果表明,ORDER-M-π算法不但能大大地节约计算成本,且所产生的可靠度具有良好的精确度。     

流通网络中随机流动的仿真研究

堵塞流是指网络在堵塞情况下通过网络的最大流量，而网络最小流量是网络在最严重堵塞情况下通过网络的最大流量。研究表明，很难从理论上确定一个网络的最小流的准确数值，因此必须借助网络的随机流动仿真试验。本文通过建立流通网络中的随机流动仿真模型来研究一般网络中的堵塞现象及堵塞流运动规律。探索了堵塞流值的概率分布规律，提出了流通网络在随机流动情况下的流通能力的新概念，并证明了作者提出的网络最小流算法的正确性。     

多状态网络可靠度下界的矩阵分解算法

为减少计算多状态网络可靠度精确值的复杂性,提出基于分解计算多状态网络不可靠度精确值的思想,在此基础上提出一个求解多状态网络不可靠度动态上界(对应于可靠度动态下界)的算法.算法先通过分解运算去除某些边引起的d-最小割集之间的相关性,将网络不可靠度转化为多个互斥事件的概率之和,再应用MESP界求取这些事件的概率,计算网络不可靠度上界,对应得到可靠度下界,并计算了得到的可靠度下界与精确值间的绝对误差界.通过定义d-最小割集矩阵,利用矩阵分解实现算法,结构清晰、便于编程计算.相关引理的证明及算例分析表明随着分解的深入,算法能够得到满足精度要求的可靠度下界.     

基于无效状态空间的多状态网络可靠性评估

在应用d-最小割(路)集计算多状态网络可靠度精确值算法中,运用容斥原理求解d-最小割(路)集较为复杂。为此,提出一种不需d-最小割(路)集直接计算多状态网络可靠度精确值的算法。该算法按一定规则分割状态空间,在此基础上生成无效状态空间,通过迭代计算直接获得可靠度精确值,同时通过定义边的容量下界及剩余网络。实例分析结果表明,运用该算法可减少计算量,并能精确求解d-最小割(路)集。     

基于边状态枚举计算多状态网络可靠度动态界

为降低计算多状态网络可靠度的复杂性,综合考虑网络中具有多态性的边处于各中间状态的概率及从某中间状态转换到相邻状态对网络性能的影响,提出了一种基于边状态枚举计算多状态网络可靠度上下界的算法.该算法首先令网络中各边仅取完全工作和完全失效两种状态,将处于中间状态的概率分别叠加到完全工作和完全失效状态的概率上,得到可靠度上下界的初始值;而后按照对可靠度影响递减的顺序迭代枚举边的中间状态,通过集合间的比较,计算可靠度上下界的改变值,同时获得不断减小的可靠度上界和不断增加的可靠度下界,使其最终收敛于可靠度精确值.该算法不需提前求取网络d-最小割(路)集,且枚举较少的网络状态即可得到紧凑的可靠度上下界.相关引理的证明及算例分析验证了该算法的正确性和有效性.     

基于栈的网络最大流算法

针对网络最大流问题,在割集定义和最大流-最小割定理基础上,以邻接矩阵为网络数据存储结构,利用栈作为数据组织形式,遍历网络中所有割集,最小容量的割集即为网络最大流。流量网络其余分支流量由网络结点流量平衡条件来求解。该算法具有：开辟了一种求解流量网络最大流的新的方法,克服了割集和最大流-最小割定理仅仅具有理论价值、没有实用价值的局限性;根据最小容量的割集可以方便确定决定网络最大流的关键分支,为扩展网络流量提供直接技术支持。算法测试表明：基于栈的网络最大流算法是完全可行和有效的。     

基于办公流程图结构的隐私保护模型研究

针对办公流程图结构易导致隐私泄露的问题,构建了一种面向办公自动化系统的隐私保护模型,采用社会网络匿名化思想,提出了面向工作流图的1邻域真实节点度统一匿名算法和权值最小随机扰动保护方法.该模型对节点的度以及工作流量信息进行保护,有效地防止攻击者根据背景知识、节点的度结构和工作流量信息来识别办公网络中的重要节点,并通过实验验证了隐私保护模型的可用性.     

在线云存储服务的流量管理研究

云存储是云计算应用的一个重要分支,有效利用数据中心的带宽资源,设计高效、均衡、可扩展性良好的带宽资源管理和流量负载均衡算法十分重要。在云存储服务典型应用Dropbox的架构下,可设计最小带宽优先的贪心算法和二次随机选择算法来实现负载均衡,并将其和流量预测、带宽预留技术结合在一起,实现一套流量负载均衡和带宽预留方案。贪心算法的负载均衡技术能够取得良好的性能,但是复杂度高、系统开销较大、可扩展性较差;二次随机选择算法复杂度低并且显著减少了系统通信开销。通过Dropbox真实流量数据和大规模仿真数据的实验,表明二次随机选择算法能够实现接近于贪心算法性能的均衡流量调度。基于预测的带宽预留技术保证了服务质量,提高了网络资源利用率。     

基于遗传算法的计算机网络可靠度优化计算

在提高计算机网络传输系统可靠度的基础上,如何有效的降低网络结点链路成本,成为计算机网络可靠度优化计算中的重要目标之一。为此,在计算机网络可靠度优化计算时,将计算机网络链路介质成本、网络可靠度优化的数学模型等因素综合在一起进行考虑,文章阐述了遗传算法及其执行过程,并对遗传算法用于网络链路成本和网络可靠度优化的计算中,最后通过仿真结果表明,遗传算法能够有效的解决网络传统算法难以解决的可靠度优化计算问题,加快了计算机网络计算的速度,优化了网络的计算效果。     

一类允许节点失效的多信息流随机流量网络的可靠度研究

This paper studies the performance index that the system probability is not less than the given demand for a stochastic-flow network whtere each arcs and nodes have several capacities and multiple types of commodities transmitted through the same network. One solution procedure is proposed to evaluate the multi-commodity reliability and a simple algorithm is presented in terms of MPs. An illustrative example is given and the difference between multiple types of commodities systems and single commodity systems is discussed.     

Optimal routing policy of a stochastic-flow network

Under the assumption that each arc’s capacity of the network is deterministic, the quickest path problem is to find a path sending a given amount of data from the source to the sink such that the transmission time is minimized. However, in many real-life networks such as computer systems, telecommunication systems, etc., the capacity of each arc is stochastic due to failure, maintenance, etc. Such a network is named a stochastic-flow network. Hence, the minimum transmission time is not fixed. We try to evaluate the probability that d units of data can be sent through the stochastic-flow network within the time constraint according to a routing policy. Such a probability is named the system reliability, which is a performance index to measure the system quality. This paper mainly finds the optimal routing policy with highest system reliability. The solution procedure is presented to calculate the system reliability with respect to a routing policy. An efficient algorithm is subsequently proposed to derive the optimal routing policy.     

Reliability evaluation for a manufacturing network with multiple production lines

This paper focuses on performance evaluation of a manufacturing system with multiple production lines based on the network-analysis perspective. Due to failure, partial failure, or maintenance, the capacity of each machine is stochastic (i.e., multi-state). Hence, the manufacturing system can be constructed as a stochastic-flow network, named manufacturing network herein. This paper intends to measure the probability that the manufacturing network can satisfy customers’ orders. Such a probability is referred to as the system reliability. A graphical representation is first proposed to transform a manufacturing system into a manufacturing network. Thereafter, we decompose the manufacturing network into general processing paths and reworking paths. Three algorithms are subsequently developed for different scenarios and multiple production lines to generate the minimal capacity vectors that machines should provide to satisfy demand. The system reliability can be derived in terms of such capacity vectors afterwards.     

基于改进粒子群算法的随机流路网可靠性研究

为解决城市交通路网中容量的随机性对可靠性研究的影响问题,建立了随机流交通路网可靠性模型,提出了一种基于改进粒子群算法的交通路网可靠性评价方法,该方法能够搜索到满足条件的多个解,在算法中引入了一种转移机制可以有效地避免粒子陷入局部无目标搜索状态,又可保证全局搜索能力,最终能够搜索到路网在d需求量下的所有d-下界点以计算路网的可靠性.通过算例结果表明了该改进粒子群算法的可行性及准确性.     

流网络可靠度的计算算法综述

A flow network is usually used to describe real world systems such as telecommunication system,computer system and so on. Given the demand d ,the system reliability is defined as the maximum flow of the network is not less than d. The researchers in the field have presented many algorithms on the reliability evaluation of flow-networks. In this paper ,classfies of flow-networks and the properties of each algorithm ,mainly those algorithms based on MPs and MCs,are summarized.     

Reliability evaluation for a manufacturing network with multiple production lines

This paper focuses on performance evaluation of a manufacturing system with multiple production lines based on the network-analysis perspective. Due to failure, partial failure, or maintenance, the capacity of each machine is stochastic (i.e., multi-state). Hence, the manufacturing system can be constructed as a stochastic-flow network, named manufacturing network herein. This paper intends to measure the probability that the manufacturing network can satisfy customers’ orders. Such a probability is referred to as the system reliability. A graphical representation is first proposed to transform a manufacturing system into a manufacturing network. Thereafter, we decompose the manufacturing network into general processing paths and reworking paths. Three algorithms are subsequently developed for different scenarios and multiple production lines to generate the minimal capacity vectors that machines should provide to satisfy demand. The system reliability can be derived in terms of such capacity vectors afterwards.     

Reliability Evaluation for an Information Network With Node Failure Under Cost Constraint

The quality of service is an important index to measure the performance of an information system. This paper constructs a stochastic-flow network to model the information system. In this network, each node and arc having a designated capacity will have different lower levels due to various partial and complete failures. The studied problem is to evaluate the possibility that a given amount of multicommodity can be sent through an information network under the cost constraint. Such a possibility, which is named the mission reliability, is an appropriate performance index to measure the quality level. The terminology "flow" represents the quantity of data transmitted via such a network, and "demand" represents the required data from clients. Based on the properties of minimal paths, a simple algorithm is first proposed to generate all lower boundary points for the demand; then, the mission reliability can be calculated in terms of such points. The lower boundary point for the demand is a minimal vector, which represents the capacity of each component (arc or node), such that the demand can be fulfilled. Extending the stochastic-flow network to the node failure case, another algorithm is proposed to calculate the mission reliability     

Routing policy of stochastic-flow networks under time threshold and budget constraint

The quickest path problem is to find a path which sends a given amount of data from the source to the sink such that the transmission time is minimized. More specifically, the capacity of each arc in the network is assumed to be deterministic. However, in many real-life networks such as computer systems, telecommunication systems, etc., the capacity of each arc is stochastic due to failure, maintenance, etc. Such a network is named as stochastic-flow network. Hence, the minimum transmission time is not a fixed number. The purpose of this paper is to provide a decision procedure for a stochastic-flow network under the time and budget constraints. We try to evaluate the probability that d units of data can be sent through the network under both time threshold and budget according to the routing policy. Such a probability is named the system reliability, which is a performance index to measure the system quality. An efficient algorithm is proposed to derive the optimal routing policy with highest system reliability. The sensitive analysis can be conducted to improve the most important component which increases the system reliability most significantly.     

Reliability evaluation of a stochastic-flow distribution network with delivery spoilage

From the supply chain management perspective, this paper focuses on evaluating network reliability of a stochastic-flow distribution network (SFDN) under the delivery spoilage consideration. An SFDN is composed of nodes and routes, where each node denotes a supplier, a transfer center, or a market, and each route connects a pair of nodes. Along each route, there is a carrier whose available capacity is stochastic. Moreover, goods may rot or be spoilt during delivery due to traffic accidents, collisions, natural disasters, weather, time, etc., and thus the intact goods may not satisfy the market demand. Network reliability is defined as the probability that the SFDN can satisfy the market demand under the delivery spoilage consideration and the delivery budget constraint, and can be regarded as a performance index for distribution activity in supply chain management. An algorithm is developed in terms of minimal paths to evaluate network reliability. A numerical example is given to illustrate the solution procedure. Then a practical case of fruit distribution is presented to emphasize the management implication of network reliability.