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

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

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

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

多状态网络可靠度的d-最小割（路）集转换算法*

为寻求计算多状态网络系统可靠度更为简明的方法,提出了一种d-最小割、路集转换算法。该算法在已知d-最小割（路）集的基础上,基于逻辑代数理论,通过展开和之积表达式获得d-最小路（割）集,再基于两者中数量较少的一个运用容斥原理,得到网络可靠度。同时,分别利用容量未取最大和不为0的边及对应取值组成的集合对表示d-最小割(路),基于集合之间的隶属关系及将集合运算中正常的先取逆再合并的运算顺序变为先合并再取逆的思想,提出相关引理,简化算法。通过复杂度分析,证明算法有效。算例证明了算法的有效性和适用性。     

基于网络化简和向量集分解的网络两终端可靠度算法*

可靠度是衡量网络性能最重要的指标之一,不交和算法和因子分解算法是计算网络可靠度最重要的两种方法。不交和算法需要提前枚举网络所有极小路或极小割,因子分解算法虽然不需要枚举极小路或极小割,但每次只能分解一条边的状态。为了克服这两种算法的不足,基于网络化简和向量集分解,提出一个计算网络可靠度的高效、实用算法。该算法具有如下特点：a）算法首先求得网络的不可靠度,进而可得网络的可靠度;b）算法不需要提前枚举网络所有极小路和极小割;c）通过引入网络化简操作和向量集分解方法,算法每次可以分解多条边的状态,从而能更快速、     

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

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

计算网络两终端可靠度的新分解算法

网络可靠度是衡量网络性能的一个核心指标,随着网络模型被广泛应用于现实生活,人们对网络可靠度的研究也越来越重视。针对不交和算法和因子分解算法在计算网络可靠度方面存在的不足,给出一个计算网络两终端可靠度的新分解算法。该算法具有如下的优点：不需要提前枚举网络的所有极小路和所有极小割;通过引入网络化简操作和新的分解技术。该算法每次可以分解多条边的状态,从而它能够更快速、更高效地去分解网络的状态向量集,使得网络可靠度的计算更简单,更高效。通过实例以及和其他算法的比较验证了所提出算法的正确性和有效性。     

基于蚁群算法优化回声状态网络的研究

针对输出权值采用最小二乘法的回声状态网络(ESN),在随机选取输入权值和隐层神经元阈值时,存在收敛速度慢、预测精度不稳定等问题,提出了基于蚁群算法优化回声状态网络(ACO-ESN)的算法。该算法将优化回声状态网络的初始输入权值、隐层神经元阈值问题转化为蚁群算法中蚂蚁寻找最佳路径的问题,输出权值采用最小二乘法计算,通过蚁群算法的更新、变异、遗传等操作训练回声状态网络,选择出使回声状态网络预测误差最小的输入权值和阈值,从而提高其预测性能。将ACO-ESN与ELM、I-ELM、OS-ELM、B-ELM等神经网络的仿真结果进行对比,结果验证经过蚁群算法优化的回声状态网络加快了其收敛速度,改善了其预测性能,并增强了隐层神经元的敏感度。     

因子分解二终端网络可靠度近似计算

因子分解算法可以用来计算网络可靠度精确值,但对于大型网络,可靠度精确值的计算非常困难。基于时间和精确度的双重考虑,在精确算法的基础上通过改进得出一种近似算法。实验结果证明,该算法得到的近似值接近精确值,而且计算时间要低于精确算法。     

基于超平行空间集员滤波的非线性系统状态估计方法

针对噪声有界但未知条件下的非线性系统状态估计问题,提出基于超平行空间集员滤波算法.利用Stirling矩阵将模型进行一阶展开,基于凸差规划完成线性化误差定界,采用超平行空间表示误差边界和状态可行集,求解下一时刻预测状态可行集超平行体.在更新步将观测值分解为多个带,融入观测值的线性化误差并将带依次与超平行体相交,得到该时刻超平行空间描述下的状态可行集更新情况.所提出算法能够避免在求解线性化误差过程中外包误差集合带来的体积扩充,降低非线性集员滤波算法的保守性,仿真示例验证了所提出算法的可行性和有效性.     

一种基于概率的QoS单播路由算法

实际的动态网络环境迫切要求在QoS路由算法设计中充分考虑网络节点所获网络状态的不精确性.建立了基于非精确状态的网络模型,并提出了一种基于概率的QoS路由算法.该算法通过一种精度可控的次优化方法,解决了基于非精确状态延时带宽限制代价最小的QoS路由问题.仿真实验表明,该算法能有效地屏蔽网络状态的非精确性,忍受较大的网络更新触发门限值,并保持较好的路由性能.     

A hybrid ant-tabu algorithm for solving a multistate flow network reliability maximization problem

Network reliability optimization for multistate flow networks (MFN) is an important issue for many system supervisors. Network reliability maximization for an MFN by determining the optimal component assignment, where a set of multistate components are ready to be assigned to the network, is a common problem. Previous research solved this problem by developing and applying genetic algorithm. Ant colony optimization (ACO) finds a good solution quickly by utilizing the experience of the proceeding ant but sometimes falls into local optimum. Tabu search (TS) adopts a tabu list to avoid searching in the same direction, and thus it explores other possible solutions. This strategy enlarges the search space. Therefore, we propose a hybrid ant-tabu (HAT) algorithm integrating the advantages of ACO and TS to solve this problem, where network reliability is evaluated in terms of minimal paths (MPs) and Recursive Sum of Disjoint Products. Experimental (RSDP) results show that the proposed HAT has better computational efficiency than several soft computing algorithms for networks with more than six MPs or 10 arcs.     

Transmission reliability of k minimal paths within time threshold

The quickest path problem involving two attributes, the capacity and the lead time, is to find a single path with minimum transmission time. The capacity of each arc is assumed to be deterministic in this problem. However, in many practical networks such as computer networks, telecommunication networks, and logistics networks, each arc is multistate due to failure, maintenance, etc. Such a network is named a multistate flow network. Hence, both the transmission time to deliver data through a minimal path and the minimum transmission time through a multistate flow network are not fixed. In order to reduce the transmission time, the data can be transmitted through k minimal paths simultaneously. The purpose of this paper is to evaluate the probability that d units of data can be transmitted through k minimal paths within time threshold T. Such a probability is called the transmission reliability. A simple algorithm is proposed to generate all lower boundary points for (d, T), the minimal system states satisfying the demand within time threshold. The transmission reliability can be subsequently computed in terms of such points. Another algorithm is further proposed to find the optimal combination of k minimal paths with highest transmission reliability.     

A method to evaluate the routing policy with two minimal paths within time threshold

Two attributes, the capacity and the lead time, are involved in the quickest path problem which finds a path with the minimum transmission time. The capacity of each edge is assumed to be deterministic in this problem. However, in many real-life networks such as computer, telecommunication, logistics networks, etc., each edge should be multistate due to failure, maintenance, etc. Such a network is named a multistate network. Hence, the minimum transmission time through a multistate network is not fixed. We evaluate the system reliability that a specified amount of data can be sent through a pair of minimal paths simultaneously within the time threshold. A solution procedure is first proposed to calculate it. In order to boost the system reliability, the network administrator decides the routing policy in advance to indicate the first and the second priority pairs of minimal paths. The second one will be responsible for the transmission duty if the first one fails. According to the routing policy, the system reliability can be subsequently computed. The case to transmit data through more than two minimal paths can be extended easily.     

多状态系统的性能可靠性

工程中的许多系统要求系统性能参数在规定范围内,该文研究了这种多状态系统的结构 和性能可靠性,利用定义出的路和割的新概念,求得系统可靠性的若干界,最后讨论了系统可 靠性计算.     

多约束最短链路分离路径精确算法

在通信的源和目的间寻找两条(主用和备用)链路分离的QoS路径是提供可靠QoS路由的重要途径.现有求解多约束链路分离路径对(multi-constrained link-disjoint path pair,简称MCLPP)的算法难以保证求得存在于任意网络中的可行解和最优解.为解决这一问题,分析了MCLPP问题最优解的性质,提出了精确算法的设计原则,在此基础上给出了求解MCLPP问题的精确算法(link-disjoint optimal multi-constrained paths algorithm,简称LIDOMPA算法),可对任意网络求解客观存在的多约束最短链路分离路径对.为了降低算法的复杂性,引入了候选最优解、紧缩的约束向量和结构化的路径支配3种关键方法,在保障算法精确性的同时,有效地降低了LIDOMPA的搜索空间.大量的实验结果表明,LIDOMPA的求解能力优于现有算法,同时可以实现较低的算法执行时间开销.     

多约束最短链路分离路径精确算法

在通信的源和目的间寻找两条(主用和备用)链路分离的QoS路径是提供可靠QoS路由的重要途径.现有求解多约束链路分离路径对(multi-constrained link-disjoint path pair,简称MCLPP)的算法难以保证求得存在于任意网络中的可行解和最优解.为解决这一问题,分析了MCLPP问题最优解的性质,提出了精确算法的设计原则,在此基础上给出了求解MCLPP问题的精确算法(link-disjoint optimal multi-constrained paths algorithm,简称LIDOMPA算法),可对任意网络求解客观存在的多约束最短链路分离路径对.为了降低算法的复杂性,引入了候选最优解、紧缩的约束向量和结构化的路径支配3种关键方法,在保障算法精确性的同时,有效地降低了LIDOMPA的搜索空间.大量的实验结果表明,LIDOMPA的求解能力优于现有算法,同时可以实现较低的算法执行时间开销.     

Search for MC in modified networks

In this paper, first we develop an intuitive algorithm using the shortest path based upon the reformation of all MCs in the original network. Next, the computational complexity of the proposed algorithm is analyzed and compared with the existing methods. One computer example is illustrated to show how all MCs are generated in a modified network based upon reformation of all of the MCs of the corresponding original network.Scope and purposeA method is proposed to search for all minimal cuts (MCs) in a network (modified networks) obtained by modifying the original network. It can be used for reliability analysis of various modifications in an existing network for network expansion or reinforcement evaluation and planning. Analysis of our algorithm and comparison to existing best-known algorithms shows that our proposed method has the following advantages: (1) it can be used to search for all MCs without knowing all minimal paths (MPs) and MCs in advance. (2) it is simple and more effective in finding and verifying MC candidates in modified networks than the existing methods. and (3) our method is easier to understand and implement.     

A Network Security Risk Assessment Method Based on a B_NAG Model

Computer networks face a variety of cyberattacks. Most network attacks are contagious and destructive, and these types of attacks can be harmful to society and computer network security. Security evaluation is an effective method to solve network security problems. For accurate assessment of the vulnerabilities of computer networks, this paper proposes a network security risk assessment method based on a Bayesian network attack graph (B_NAG) model. First, a new resource attack graph (RAG) and the algorithm E-Loop, which is applied to eliminate loops in the B_NAG, are proposed. Second, to distinguish the confusing relationships between nodes of the attack graph in the conversion process, a related algorithm is proposed to generate the B_NAG model. Finally, to analyze the reachability of paths in B_NAG, the measuring indexs such as node attack complexity and node state transition are defined, and an iterative algorithm for obtaining the probability of reaching the target node is presented. On this basis, the posterior probability of related nodes can be calculated. A simulation environment is set up to evaluate the effectiveness of the B_NAG model. The experimental results indicate that the B_NAG model is realistic and effective in evaluating vulnerabilities of computer networks and can accurately highlight the degree of vulnerability in a chaotic relationship.     

无线传感器网络一种不相交路径路由算法

无线传感器网络经常被用来采集物理数据,监测环境变化.由于低功耗无线通信不确定性、链路质量不稳定性以及节点失效等问题,传感器网络很容易导致路由数据包丢失.为了提高网络路由的可靠性,人们提出多路径路由算法.多路径路由中源节点到目的节点的多条路径可能含有公共节点,或者公共边,如果公共节点或者公共链路失效,则这个数据包也丢失,因此又有人提出不相交多路径路由算法.不相交多路径路由算法又分为链路不相交多路径路由算法和节点不相交多路径路由算法.提出了一种不相交路径路由算法,可以将感知节点采集到的数据通过不相交路径传送到汇聚节点,提高路由的可靠性.而且,这个算法还可以很方便地应用到多Sink节点的网络当中.该路由算法用到的路由表大小为|K|,其中|K|表示路径数.算法的运行时间复杂度是O(|L|),其中|L|表示网络中的边数.