计算无线通信网络2-终点可靠性的快速算法

提出计算无线通信网络从源点到汇点(ST)可靠性的一个新拓扑公式．该公式中各项和网络的一类特殊子网络一一对应，与相应的Satyanarayanna公式比较，该公式包含更少的项和更少的算术运算．提出一个计算从网络源点到汇点(ST)可靠性算法．这个算法本质上是通过系统地枚举网络的一类特殊子网络而计算其ST可靠性或生成可靠性表达式．由于所需枚举的子网络数量小于相应的Satyanarayanna算法需枚举的子网络数量，因此新算法性能优于Satyanarayanna算法．最后通过一个具体例子说明了这个结论．     

计算无线通信网络2-终点可靠性的快速算法

提出计算无线通信网络从源点到汇点(ST)可靠性的一个新拓扑公式。该公式本质上是将容斥原理公式和不交和公式融合在一起，公式中各项和网络的一类特殊子网络一一对应，与相应的Satyanarayanna公式比较，该公式包含更少的项和更少的算术运算。提出一个计算从网络源点到汇点(ST)可靠性算法。这个算法本质上是通过系统地枚举网络的一类特殊子网络而计算其ST可靠性或生成可靠性表达式。由于所需枚举的子网络数量小于相应的Satyanarayanna算法需枚举的子网络数量，因此新算法性能优于Satyanarayanna算法。最后通过一个具体例子说明了这个结论。     

计算一类有向网络可靠性的线性时间算法

该文使用的可靠性保护缩减的方法计算有向网络ST可靠性（存在从源点到汇点正常运行道路的概率）是计算网络可靠性的常用方法之一,而且人们非常关心怎样的网络计算其可靠性存在线性时间算法,作者提出了两类新的可靠性保护缩减－－源桥缩减和惠斯通桥缩减和一类有向无圈网络,称之为WST网络,该类网络是对以前的BSP网络的扩展并且对于该类网络提出了一个计算其可靠性的线性时间算法。     

大型网络的SKT可靠性的分散计算法

提出了一种基于分解法的计算大型网络从源点到特定节点集K(即SKT)可靠性的算法。按照一定的分解规则将大型网络划分为若干较小规模的子网络，从而最终将枚举原网络的K树这一复杂问题转化为计算这些子网络的最小路。对求得的K树进行不交化运算，最终得到网络的SKT可靠性。     

一种求解关键路径的新算法

通过定义节点编码图概念,提出一种不需要拓扑排序的求解关键路径的新算法。该算法扩充图的邻接表的存储结构,使图的存储与算法求解过程共享同一存储空间。从图的源节点开始,用加权取极大运算规则,广度优先递归对图中所有节点进行编码。编码图生成后,利用反向搜索求出从源点到汇点的所有关键路径及长度。该算法比现有算法更简单直观,所需的存储空间更小,算法时间复杂度降低到O(n+e),优于现有算法的O(n2)。     

无线传感器网络的二终端可靠性优化

研究的问题是无线传感器网络中一些节点由于能量耗尽导致节点损坏而影响二终端网络可靠性的优化问题,提出了无线传感器网络中,m个节点被损毁情况下使得边不交道路可靠性最大的优化问题.通过引入s-t子图边不交道路可靠性的概念,本文建立了一个优化模型,在该模型中,当C0满足C0≥C(C是设计的启发式算法得到的最可靠的s-t子网中所包含的节点数),而被损毁的节点数m≤|V|-C时,给出了寻找源点与终端节点之间最大的s-t子图可靠性的启发式算法,即最大边不交道路可靠性算法,并证明了这个算法的计算复杂性是多项式时间的.仿真结果说明在损坏的节点数小于给定条件时该算法有效地处理该优化问题.此外也用类似的方法简单地处理了优化模型中C0≤C'时的最大s-t子图可靠性,其中C'是最短s-t道路中所含的点数.     

一种图的st编号路径长度算法

通过对无向图的顶点标注st-编号,可以使它转换为一个有向图,根据有向图的方向可计算出从源点到汇点的路径长度.用DFS算法可计算出st-编号,但一个图有多种不同的st-编号方法,不能确定图的最长路径或者最短路径.使用移除法,连续移除根据时间戳选择出来的顶点,计算出图的st-编号,能够确定图的最长路径或者最短路径.st-编号路径长度在计算网络动态路由、计算最少着色数、减少框图高度等问题上有广泛的应用.     

中心计算的无线传感器网络2-不相交路径路由算法

在多路径路由(multipath routing, MPR)算法中,不相交多路径路由(disjoint multipath routing, DMPR)算法具有更高的可靠性和容错性.DMPR算法面临的主要挑战有2点：不相交路径的选优问题和数据包在不相交路径上的传输问题.针对某些工业应用(例如矿井环境监测)中网络拓扑比较稳定,sink节点运算和存储能力较强等特点,提出了一种中心计算的2-不相交路径路由算法——CCDMPR算法.算法利用全网信息计算出从源节点到sink节点的近似最优2-节点(链路)不相交路径,然后生成仅包含主父交节点,辅父节点对和路径比特序列的微路由表并下传到每个节点;针对中心计算方式对链路状态变化的反应迟缓问题,采用了一种中心调度的自适应机制提高路径维护的灵活性.实验结果证明,CCDMPR算法能够显著减小平均路径长度,节省网络整体能量,并能提高数据传输的可靠性.     

一个估计随机流网络可靠性的新方法

首先提出了一个名为状态树搜索(State-tree Search),用以计算随机流网络可靠性的算法,在此基础上提出了一个改进的算法-SS-MC(State-tree Search & Monte Carlo).状态树搜索方法通过在一个状态树中搜索所有的有效状态来计算网络的可靠性;而SS-MC方法将分层抽样技术引入状态树搜索过程来实现大规模网络的可靠性评估.仿真结果表明SS-MC方法是有效的,并具有较小的方差.     

采用推理方法提高多面体Boolean运算的可靠性

提高实体Boolean运算的可靠性是几何造型中最基本也是最迫切的工作。通过对国内外几何造型系统在实体Boolean运算可靠性方面的测试,我们发现,实体Boolean运算不可靠是一个普遍现象,运算失败的根本原因在于数值计算存在误差。数值计算误差决定了我们不能精确地确定集合成员分类。集合成员分类的结果与选定的计算容差有关,具 有相对性。从而相关分类之间会发生冲突。一旦分类之间发生冲突,Boolean运算就不能得到正确的结果。我们提出了一个相当可靠的Boolean运算算法。该算法采用推理的方法在进行Boolean运算之前解决由数值计算误差所引起的相关分类之间冲突。这些算法已在Apollo和SUN工作站上实现,并取代了GEMS 2.0造型系统,构成了一个新的造型系统GEMS 2.1。经测试和比较,这个系统的可靠性比SDRC公司的Geomod 3.9和Intergraph公司的I/EMS高得多。     

计算一类网络K--终点可靠性的线性时间算法

可靠性保护缩减的方法是计算网络可靠性的常用手段之一，而且关心哪类网络的可靠性存在线性时间算法．给出了一类新的可靠性保护缩减-桥缩减和一类无向网络，称之为WST网络，该类网络是对串并联网络的扩展并且对该类网络提出了一个计算K-终点可靠性的线性时间算法，其算法复杂性为O(|E|^2)．     

Computing the SKT reliability of acyclic directed networks using factoring method

1IntroductionReliabilitymeasuresofnetworksareimportantparametersinbothdesignandoperationofsystemslikepowernetworks,communicationnetworks,andcomputernetworks.Inthesenetworks,acyclicdirectednetworks(AD-networks)areverycommon.Inthispaper,westudythesource-to-K-terminal(SKT)reliabilityproblemofAD-networks.Givenadirectednetworkwithunreliablenodesandedges,KbeingasubsetofnodesandsKthespecifiedsource,SKTreliabilityistheprobabilitythatthereexistoperatingpathsfromthesourcestoeachnodeinsetK-{s}.SKT…     

无线通讯网络可靠度的计算

文章提出了几个保持可靠度不变的将边可靠、结点不可靠的无向网络化简以及转化成有向网络的原则,并将这些原则与已有的不交和或容斥原理方法相结合给出了一个新的计算无线通讯网络（Radio Communication Network,简称RCN）两终端可靠度的有效算法。由于文章所给的化简与转化使RCN中指定两结点之间的路径数大大减少,因此该文算法使其可靠度的计算得到很大简化。     

Reliability Optimization in the Design of Distributed Systems

The reliability of a distributed system depends on the reliabilities of its communication links and computing elements, as well as on the distribution of its resources, such as programs and data files. A useful measure of reliability in distributed systems is the terminal reliability between a pair of nodes which is the probability that at least one communication path exists between these nodes. An interesting optimization problem is that of maximizing the terminal reliability between a pair of computing elements under a given budget constraint. Analytical techniques to solve this problem are applicable only to special forms of reliability expressions. In this paper, three iterative algorithms for terminal reliability maximization are presented. The first two algorithms require the computation of terminal reliability expressions, and are therefore efficient for only small networks. The third algorithm, which is developed for large distributed systems, does not require the computation of terminal reliability expressions; this algorithm maximizes approximate objective functions and gives accurate results. Several examples are presented to illustrate the approximate optimization algorithm and an estimation of the error involved is also given.     

无圈有向设备网络可靠度仿真算法研究

在网络技术问题的研究中,3-状态设备网络系统二-终端可靠度评估的BDD算法存在着可靠度符号表达式项数多,算法效率低问题。为提高可靠性,引入串联简化和并联简化,使得BDD算法在产生分枝树的过程中遇到并联结点和串联结点就不再产生新的分枝,并且在结点存储时不存储已经保存过的结点,从而得到了3-状态设备网络系统二-终端可靠度的一个新算法。通过仿真实例表明,算法消除了冗余项、产生的分枝树节点数量大幅度减少,可一次给出3-状态设备网络系统可靠度符号表达式,算法效率显著提高。算法对复杂网络系统性能评估和系统结构设计具有重要参考意义。     

一个计算网络可靠度的递归算法

给出一个计算网络可靠度的有效算法,该算法的特点是结合概率论的有关知识和布尔代数运算：递归地调用一个简单、有效的概率公式来计算网络可靠度。该算法易于在计算机上操作和实现,从而适用于大型网络可靠度的定量计算。最后通过实例验证所给算法的有效性。     

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.