章筠[1]2012年在《计算机网络可靠性分析与设计》文中提出随着计算机网络的广泛应用,为了向用户提供满意的服务,需要保障网络的服务质量,由于可靠性是一项反映服务质量的重要指标,网络可靠性相关研究获得了学者的广泛关注。网络可靠性评估是网络可靠性相关研究的基础,而基于可靠度的网络设计则能针对网络可靠度、网络构建费用等网络设计目标,提供各种优化方案供网络管理者参考,是目前网络可靠性研究领域的一大热点。在网络设计方面,由于网络可能会发生故障,故障容错技术能保证网络在故障条件下的正常工作,因此,网络容错设计具有重要的研究意义。本文主要围绕计算机网络可靠性分析与设计进行研究,本文的主要研究内容如下：1.简单介绍了网络可靠性的重要性,发展及其研究现状。2.对数据通过相交路径进行传输的可靠性的评估进行了初步探索。通过比较各数据到达共用链路的时刻,来判断各数据是否存在链路使用权竞争。探讨了数据产生的时间间隔和数据量对可靠度的影响。3.考虑了基于网络可靠度的传输线优化设计问题。针对拓扑结构固定的多源多宿多态计算机网络,提出了一种可靠度最大化的网络传输线配置方法,在满足费用约束的情况下,极大化网络数据传输的可靠度。首先,针对一种给定的传输线配置,在网络构建费用限制条件下,提出了一种可靠度评估算法来计算多态网络各源点到各宿点的可靠度；其次,将可靠度评估算法和非支配排序遗传算法相结合,提出了基于可靠度的传输线路寻优算法来寻找原问题的最优Pareto解集。4.考虑了工作路径给定情况下,基于备用路径的容错设计问题。本文采用两条不相交的路径作为工作路径来同时传输数据,并采用与工作路径不相交的一条最小路集作为备用路径,提出了一个基于最小路集的单条备用路径算法来评估单条工作路径失效情况下的网络可靠度。相对于以往学者采用两条不相交的路径作为工作路径,并采用另外两条不相交的最小路集作为备用路径的研究,在单条工作路径失效情况下,本文提出的算法能大幅度地提高网络可靠度,且所需的备用路径数目更少。5.考虑了工作路径非给定情况下,基于备用路径的容错设计问题。本文具体研究了多协议标签交换网络的路由优化设计问题,在满足网络可靠度限制条件下,通过选择最优的工作和备用路径,并对其进行带宽分配,使得网络总构建费用最小。由于网络总构建费用和网络可靠度存在耦合关系,我们将原问题对等地解耦成两个子问题：费用和可靠度相关子问题。费用相关子问题已被学者研究解决。针对可靠度相关子问题,通过理论推导,降低了解的搜索空间。最后,由于费用和可靠度相关子问题的解是基于相同的搜索准则得到的,原问题的最优工作和备用路径解集可以通过比较两个子问题的解来求出。原问题是一个NP难题,本文提出了一种有效解决该NP难题的思路,具有重要的参考价值。最后对全文进行了总结,并提出了进一步的研究方向。
邓秋红[2]2003年在《计算网络可靠度的两个算法》文中指出本论文研究了计算机通讯网络的可靠度问题。主要讨论了网络可靠度的计算，提出了计算网络可靠度的两种新的算法。 1 不交和方法是一种有效的计算网络可靠度的方法。本文将布尔代数和Shannon公式相结合，提出了一种计算网络可靠度的不交和的新方法。这种方法可以产生比以往不交和算法更紧凑的表达式。 2 无线广播网络(简称RBN)可以用一个点不可靠而边可靠的概率图G来表示。目前，对于具有边不可靠而点可靠的网络可靠度的研究已经很多，而RBN的可靠度的研究还很少。本文针对网络无向图G提出的几种保可靠度缩减原则。利用这些原则可以删去无向图G中不相关的边，得到图G_1；图G_1经过一系列的转化，成为有向图G_2；对有向图G_2进一步化简得到有向图G_3；最后图G的可靠度就可以通过求有向图G_3的可靠度而得到。例子表明，可靠度缩减算法在计算大型RBN的可靠性是有效的。
张红[3]2005年在《计算K-终端网络可靠度的两种算法》文中进行了进一步梳理本论文研究了计算机通讯网络可靠度问题。主要讨论了网络可靠度的计算,提出了计算K-终端网络可靠度的两种新算法。 1 有序二分决策图(OBDD)是计算网络可靠度最有效的工具之一。本文讨论了由一个源点s到一个指定的顶点集合K的网络可靠度问题。首先提出了网络门限变量的两个化简原则及计算网络K-树和极小K-割的算法。然后,基于具有门限变量的布尔方程和有序二分决策图方法(OBDD),给出计算K-终端网络可靠度算法。结果表明,这种算法是有效的。该算法的特点是结构清晰,运算速度快,易于实现。这一算法改进并推广了Rauzy提出的算法。 2 边化简图法是求两终端网络割集合的一种有效方法。本文推广并改进了Yung-Ruei Chang等人的算法,提出一个计算K-终端网络可靠度的割算法。该算法首先基于K-终端网络G构造出│K│个两终端网络,然后对于每个两终端网络,采用边化简图法求两终端网络割集,最后,采用计算K-终端网络可靠度的一个定理和有序二分决策图法(OBDD),计算K-终端网络不可靠度,进而得到K-终端网络可靠度。该算法避免了枚举K-终端网络的所有道路(K-树,生成树)或割集的繁琐计算。实验证明,该算法简单有效。
肖宇峰[4]2009年在《基于离散概率模型的二端网络可靠性分析》文中指出在经济生活日益依赖于通信网的今天,网络故障不仅会带来巨大的数据损失,甚至会导致灾难性后果。利用网络可靠性分析,工程人员可以增强网络可靠性,减少故障时损失。尽管网络可靠性分析已经取得了大量成果,但如下方面还需要开展进一步研究:第一,网络结点不可靠时的可靠性分析。传统的网络可靠性分析通常假设结点可靠,这在一些新的网络研究领域是不成立的,譬如自组织网络、灾难环境网络。而且,当网络结点众多时,可靠性分析中的计算量将变得非常庞大。第二,网络部件故障非统计独立时的可靠性分析。传统的网络可靠性分析通常假设部件故障统计独立,这会给某些网络的可靠度评估带来很大的偏差,譬如极端环境下的网络。另外,当非统计独立故障较多且网络规模较大时,可靠性分析将变得非常困难。第叁,网络部件重要性分析。传统的网络可靠性分析主要讨论可靠度计算,不能从部件故障角度全面了解网络可靠性,缺乏高效的计算方法。第四,网络运行时可靠性分析。传统的网络可靠性分析主要研究可靠性设计指标,其成果不能很好地反映运行时的网络可靠性。通信网有着庞大的规模和动态复杂性,经典的故障分布函数很难描述网络的故障特性。为降低复杂性,解决一般性问题,本文采用了主流的网络可靠性模型——时间独立的离散概率模型。另外,本文只讨论了二端网络的可靠性问题,但其成果可以推广到K端网络和全端网络。针对网络可靠性分析中存在的上述问题,本文从四个方面开展了研究工作:(1)研究了结点不可靠网络的可靠性分析,提出了基于标记因子划分的网络可靠度评估算法——MFP(Marked Factor Partition)和基于特征识别的street网络可靠度评估算法——SNR(Street Network Reliability),解决了部分规模较大而结点不可靠的网络可靠度评估问题。最后,针对无线传感网的众多不可靠结点,提出了能有效评估可靠度的算法——EF(EnhancedFactoring)。1)MFP改进了基于有序二叉判定图(OBDD,Ordered Binary DecisionDiagram)的可靠性分析方法。在创建OBDD过程中,利用边替代(ER,EdgeReplacement)运算处理网络中的不可靠结点。同时,从两个方面减少了计算量:分解网络时,根据子网的标记因子划分来识别同构子网,避免分解同构子网带来的重复计算;利用OBDD来存储网络结点和边的状态,减少了冗余状态。2)SNR是专门针对street网络的方法,其基本原理与MFP相同。SNR利用源端位置信息作为子网特征,识别street网络分解过程中出现的同构子网,从而减少重复计算。3)增强因子分解算法在网络分解过程中采用hash表来存储同构子网的可靠度,提高了计算效率。(2)研究了一类常见的非统计独立故障——共因失效,提出了分析共因失效网络可靠性的算法——CNR(Common-cause-failure NetworkReliability)和无线传感网可靠性的算法——WR(Wireless-sensor-networksReliability)。解决了部分共因事件较多且规模较大网络的可靠度评估问题,讨论了有共因失效的无线传感网可靠度评估问题。1)CNR改进了基于OBDD的共因失效可靠性分析方法。为降低分析复杂性,CNR算法未考虑结点不可靠的情况。由于CNR方法只需要递归创建一个OBDD结构,在共因事件较多、网络规模较大时,这种方法可节省大量计算开销。关于如何创建共因失效网络的OBDD,本文又提出了两种方法:基于布尔运算的方法和基于共因变量集的方法。第一种方式比较灵活,第二种方式有较高的存储效率。2)WR算法充分考虑了无线传感网中的大量共因事件和不可靠结点,借用了CNR创建共因失效网络OBDD的思路,利用结点扩张法来处理无线传感网中的不可靠结点。(3)研究了网络部件重要性分析。讨论利用Birnbaum测度、关键重要度和风险增长区间等部件重要性指标来描述网络可靠性,提出了基于Birnbaum测度的链路重要性评估算法——BIL(Birnbaum Importance ofLink)和基于风险增长区间的网络可靠性评估算法——RI(Risk Increment)。BIL充分利用OBDD结构来高效计算Birnbaum测度、关键重要度和风险增长,发现网络薄弱环节,确定引发故障的最可能部件。而RI能够对部件故障时的网络稳定度进行分析,为网路抗毁性提供了又一个参考指标。另外,针对无线传感网中不可靠结点,提出了基于风险增长的结点重要性评估算法——WNI(Wireless Node Importance)。(4)针对网络运行时可靠性分析,提出了两个可靠性测度:基于故障检测的指标——容错MPLS网络的可靠性测度;基于可用带宽测量的指标——自愈IP网络可靠性测度。最后,为分析容错MPLS网络运行时可靠性,设计并实现了一个开销较低速度较快的故障检测方法——自适应的LSP故障检测机制。
牛义锋, 王艳红, 徐秀珍[5]2011年在《计算网络两终端可靠度的新分解算法》文中研究说明网络可靠度是衡量网络性能的一个核心指标,随着网络模型被广泛应用于现实生活,人们对网络可靠度的研究也越来越重视。针对不交和算法和因子分解算法在计算网络可靠度方面存在的不足,给出一个计算网络两终端可靠度的新分解算法。该算法具有如下的优点:不需要提前枚举网络的所有极小路和所有极小割;通过引入网络化简操作和新的分解技术。该算法每次可以分解多条边的状态,从而它能够更快速、更高效地去分解网络的状态向量集,使得网络可靠度的计算更简单,更高效。通过实例以及和其他算法的比较验证了所提出算法的正确性和有效性。
王泓刚, 董荣胜, 钱俊彦[6]2016年在《计算节点不可靠网络可靠度的一种MDD算法》文中指出节点或边不可靠网络的可靠度分析问题是NP-hard问题,网络节点和边都不可靠的假设更接近现实。基于网络节点和边二元状态的假设,构建了节点和边不可靠网络的形式化模型,给出了分析节点和边不可靠网络可靠度的NEF_MDD算法。该算法将单个节点与其未访问邻接边划分为一个集合,通过枚举节点和边的不同组合,合并导致子网同构的冗余状态,获得简化后的状态向量和可靠度向量,并用一个多值决策图变量来表述。通过使用自定义的MDD操作算子,构建整个网络的MDD,遍历MDD节点,计算网络的可靠度。与二元决策图方法相比,该方法能够降低决策图层数和节点规模,有助于节点和边不可靠网络的可靠度分析。
张庆功[7]2004年在《考虑失效相关时不可修复工程系统的可靠性分析》文中提出随着现代都市规模的不断扩大，其赖以生存和发展的生命线工程的可靠性越来越成为人们关注的问题。如何客观地评估系统的可靠性?通常的做法是根据独立假设原理，得出的结果因系统类型的不同而过于乐观或过于保守。事实上，任何一个存在的系统或子系统至少要受到同一随机干扰源的作用，因此“相关”是系统失效的普遍特征。相关失效是指在同一时间或在规定时间内，由于子系统间或单元间在空间上、环境上、设计上以及人为因素造成的失误等原因，而引起的两个或多个单元的失效或不可用状态。本文在广义的环境失效相关的层次上，讨论系统可靠性分析的两种算法及其在各种系统可靠性分析中的具体应用。主要做了以下四方面的工作： 首先，详细地分析了广泛应用于工程系统可靠性分析中的条件关联系数法。就条件关联系数的取值、系统组成单元正常或失效事件的概率不满足交换律以及串联系统和并联系统的可靠度与条件关联系数、系统规模的关系等问题展开了讨论。 其次，就适用于系统失效相关下可靠性分析的新型模型——限制相关参数的哈马邱尔算子的性质展开了详细的讨论，并对相关参数进行了蒙特卡洛模拟。明确地指出了限制相关参数的哈马邱尔算子存在的缺陷并给予了改进，进一步讨论了改进的哈马邱尔算子的性质，并对改进的哈马邱尔算子的相关参数进行了蒙特卡洛模拟。 再次，定义了表决系统单元状态的逐步补元法和可靠性分析的状态组合通项表示法，使表决系统可靠性分析的计算机化成为现实。 最后，将改进的哈马邱尔算子应用于串联系统、并联系统、表决系统、网络系统和更复杂的系统可靠性分析中，并编制了相应的应用软件。
展敬宇[8]2011年在《基于最小路集的通信网络可靠性计算方法的优化设计》文中指出基于最小路集的网络可靠性算法在网络可靠度的计算中发挥了重大作用。目前研究较多的是基于最小路集的不交积和法以及二元决策图法等,这些算法的效率较之前的网络可靠度算法有了明显提高,但是这些算法的实现较复杂,不利于研究网络的其他特性,而且对于具有NP-hard特性的网络可靠度的计算,算法的效率仍需进一步提高。本文研究基于路集矩阵与布尔运算的网络可靠度算法,这种计算方法不仅原理简单,易编程实现而且可以简化网络可靠性以及可靠性重要度的计算,这些特性使其成为研究基于最小路集的网络系统可靠度的一个有利工具,然而算法存在严重的组合爆炸问题,执行时间随着最小路集数目成指数增长。本文在保留原有算法优势的同时,首先对特殊的路集进行预处理,减少参与后续运算的最小路集数量,其次引入位矢量对路集矩阵及运算过程中产生的中间矩阵进行压缩存储以减少内存需求,再者优化算法思路,消除冗余运算,降低算法的时间复杂度。研究结果表明对于不同的网络拓扑结构,改进算法的执行时间相对于原有算法都有不同程度的降低,这在一定程度上缓解了算法的组合爆炸问题,在一定程度上扩大了算法的应用范围。最后,将改进的算法应用在实际的电力通信光纤网络的可靠性和有效性的计算中,首先计算出网络组件的可靠度和有效性参数,然后生成各个端局到中心局的最小路集,最后利用网络可靠度算法得出各个端局到中心局的可靠性和有效性参数,研究成果对网络可靠性的优化设计与评估具有一定的参考价值。
王泓刚[9]2015年在《基于MDD的随机流网络可靠度分析算法研究》文中认为随机流网络模型是一种多状态离散概率模型,常用来建模计算机网络、交通运输网、通信网等。网络可靠度是评估随机流网络性能的一项重要指标。由于随机流网络的多状态特性,随着网络规模的增长,评估随机流网络可靠度的容斥原理方法的生成项呈指数级增长,无法有效控制状态空间组合爆炸问题。多值决策图(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算法能够降低决策图层数和节点规模,有助于节点和边不可靠网络的可靠度分析。
牛义锋, 徐秀珍[10]2008年在《一种计算网络可靠度的不交和算法》文中研究表明给出了一种计算网络可靠度的不交和算法,该算法的最大特点是操作简便,易于在计算机上实现,从而适用于大型网络可靠度的计算。
参考文献：
[1]. 计算机网络可靠性分析与设计[D]. 章筠. 浙江大学. 2012
[2]. 计算网络可靠度的两个算法[D]. 邓秋红. 大连海事大学. 2003
[3]. 计算K-终端网络可靠度的两种算法[D]. 张红. 大连海事大学. 2005
[4]. 基于离散概率模型的二端网络可靠性分析[D]. 肖宇峰. 北京邮电大学. 2009
[5]. 计算网络两终端可靠度的新分解算法[J]. 牛义锋, 王艳红, 徐秀珍. 计算机工程与应用. 2011
[6]. 计算节点不可靠网络可靠度的一种MDD算法[J]. 王泓刚, 董荣胜, 钱俊彦. 计算机科学. 2016
[7]. 考虑失效相关时不可修复工程系统的可靠性分析[D]. 张庆功. 西南石油学院. 2004
[8]. 基于最小路集的通信网络可靠性计算方法的优化设计[D]. 展敬宇. 华北电力大学. 2011
[9]. 基于MDD的随机流网络可靠度分析算法研究[D]. 王泓刚. 桂林电子科技大学. 2015
[10]. 一种计算网络可靠度的不交和算法[J]. 牛义锋, 徐秀珍. 科学技术与工程. 2008
标签：数学论文; 可靠度论文; 计算机算法论文; 可靠性分析论文; 网络节点论文; 相关性分析论文; 随机算法论文; 可靠性设计论文; 时间计算论文; 路径分析论文;