智能粒度计算的计算机网络可靠性分析研究
摘要：
本文的研究对象是计算机网络可靠性分析的智能数值求解，将几种常见的网络系统可靠性分析方法应用于计算机网络。并在一般节点遍历法的理论分析的基础上对改进后的节点遍历法进行了深入的探讨。文章首先介绍了计算机网络系统以及可用于计算机网络系统的集中可靠性分析的相关概念及方法，然后着重对节点遍历法等一些算法做了算法分析和具体实现，使繁杂的算法易于理解。网络系统可靠性数值计算量大而烦琐，改进后的节点遍历法可以大大减少其运算量，对现有算法的改进是十分有意义的。本文提出的智能粒度分层分析方法可以较好的满足一定范围内计算机网络可靠性数值计算的需求。
关键字：计算机网络可靠性智能粒度计算 节点遍历法
引言
1. 研究背景
在信息化社会中，计算机已从单一使用发展到群集使用。越来越多的应用领域需要计算机在一定的地理范围内甚至全球范围内联合起来进行群集工作，从而促使了计算机和通信这两门技术紧密地结合，形成了计算机网络这门科学。
在现代社会，网络化是计算机发展的必然趋势，特别是随着Internet 的飞速发展，计算机系统网络化已成为全社会的共识。如今，随着计算机系统网络化在各个领域的广泛应用，计算机网络的可靠性研究越来越引起计算机业界的广泛重视，对网络可靠性的研究工作也在计算机业界深入开展。
网络的可靠性研究起源于对通信网络的分析，而后，逐渐渗透到运输系统、工程系统等各个领域。网络系统可靠性的分析计算最初只限于两终端问题，但随着大型复杂通讯网络、计算机网络、电力网络等的发展，是网络系统的可靠性分析变得更为一般化，同时，出现不少新的算法及新的理论发展[5,6]。
研究网络系统的可靠性有着广泛的实际意义。现实中的实际系统除了具有串联、并联、旁联等典型结构外，还有许多典型结构无法表示的大型的复杂系统，例如通信网络系统、电路网络系统、交通网络系统、计算机网络系统等。这些具有任意结构的系统称之为一般系统。
对这些系统的可靠性分析不能用简单的数学模型来描述，必须采用更有效的处理方法[7-10]。
可以说，网络系统可靠性理论的出现和发展，为研究复杂系统可靠性铺平了道路，并将所有能用点和线的二元关系来描述的简单或复杂系统归类为网络系统，其可靠度也称为广义网络可靠度。
2. 计算机网络可靠性研究中的一些基本概念和假设
计算机网络系统是由节点和连接节点的弧组成。在结点不失效的情况下，一般讨论两终端问题，此时，节点分为输入节点、输出节点和中间节点。
输入节点：只有输出弧而无输入弧的节点。
输出节点：只有输入弧而无输出弧的节点。
中间节点：非输入、输出结点称为中间节点。
有向网络：全部由有向弧组成的网络。
无向网络：全部由无向弧组成的网络。
混合网络：由有向弧和无向弧组成的网络。
在无向网络中，根据研究问题的需要，人为指定输入节点和输出节点，则与输入节点或输出节点相连的弧，就成为有向弧。
具有任意结构的复杂系统，一般都可以用网络图表示，以便于计算机辅助分析复杂系统的可靠性。在研究计算网络系统可靠度时，为了简化问题，通常做以下几点假设：
⑴ 系统或弧只有2 种可能的状态，正常或故障状态；⑵ 无向弧两个方向的可靠度相同；⑶ 每条弧之间的故障是相互独立的，即任意一条弧的故障不会引起别的弧故障。
二、计算机网络的可靠性分析研究
1．网络系统的最小路集和最小割集
进行网络系统的可靠性分析，首先要明确网络系统的最小路集和最小割集。最小路集反映网络系统的正常工作模式，最小割集反映网络系统的故障模式。
中，弧的集合{A，B，C，D}，{E，F，G，H}，{A，I，J，D}等都是路集。
显然，在不考虑节点可靠度的情况下，若网络中所有的弧都正常，则系统正常。所以弧的全集合是一个路集。
如果一个路集，任意去掉一个弧（故障弧）就不再是路集时，这样的路集称为最小路集。如图1中的{A，B，C，D}，{A，I，J，D}{A，I，G，H}等是最小路集。集合{E，F，I，B，C，J，G，H}去掉{I，B，C，J}后仍是路集，故集合{E，F，I，B，C，J，G，H}不是最小路集。最小路集所含的弧数目称为路长或容量。一个n个节点构成的网络系统，最小路集可能的最大路长为n-1。
割集是从系统故障的角度考虑问题的。网络系统中一些弧故障时，使输入节点和输出节点无法沟通，这样的弧的集合称为网络系统的一个割集，即弧故障时，导致系统故障的弧的集合。如果一个割集任意去掉一条弧就不再是割集，这样的割集称为最小割集。例如图1中集合{A，E}，{D，H}，{A，F}，{C，J，G}等都是最小割集，集合{A，E，I，J}是割集但不是最小割集，因为去掉I，J弧（或I、J弧由故障变为正常）集合{A，E}仍是割集。
同一个系统最小割集之间，有可能存在共同的弧。例如最小割集{A，E}和{A，F}存在共同的弧A。
2．网络系统状态与最小路集或最小割集之间的关系
网络系统中有一个最小路集存在，则输入节点和输出节点能够连通，系统处于正常工作状态。如果系统工作状态用事件S表示所有最小路集用），，（miAiL21=表示，则系统正常工作状态表示为 网络系统存在一个最小割集，则输入节点与输出节点无法连通，系统处于故障状态。系统故障状态用系统正常工作状态的逆事件表示为UmiiAS1==S，所有最小割集用表示，则系统故障状态表示为： ），，（kiCiL21=UkiiCS1==3．网络系统最小路集的节点遍历法求网络系统最小路集的常用方法有：邻接矩阵法、布尔行列式法、节点遍历法[11]。
邻接矩阵又叫联络矩阵法，实质上是对一个矩阵进行乘法和多次乘法运算当网络中节点不多时，联络矩阵法适合手算；当节点数n很大时，矩阵阶次较高，运算量是相当大的，并且需要有大容量的计算机，运算时间也长，这种方法就不适用了。
布尔行列式法，它用一种类似于求矩阵行列式的运算代替矩阵乘法运算，数学概念和过程上易于理解，简便易于手工，但当网络中节点较多时，展开矩阵为布尔积的和比较烦琐。
节点遍历法条理清晰，且能求解节点数很大的复杂网络，但该方法判断条件较多，若考虑不周，容易出错。
下面简单介绍传统的节点遍历法。
求网络系统最小路集的节点遍历法基本思想：从输入节点I开始，逐个节点遍历，一直到输出节点L，直到找到所有最小路集为止。
传统的求网络系统最小路集的节点遍历法对于给定n个节点的有向网络（无向网络看作是双向的），运用节点遍历法，从输入节点开始，一步步向前走，直到输出节点，关键是做以下的几种判断：（１）判断当前节点是否与前面已走过之节点重复；（２）判断是否已找到了一条最小路集；（３）判断是否已找完所有最小路集。
4．最小路集法计算网络系统的可靠度
设已经求出输入节点和输出节点之间的所有最小路集。系统正常事件用事件S表示，系统正常意味着至少有一个最小路集存在，即 第i个最小路集存在意味着该最小路集中的每条弧均正常，即其中，如果网络系统中节点数目为n，则j≤n-1。系统正常事件S又可表示为即S表示为每条弧正常时间的积之和。
由于每条最小路集之间是有可能相交的，必须用相容事件的概率公式来计算系统的可靠度，为sR式中，P{S}为系统正常的概率，随着最小路集数目的增加，项数急剧增加（达到项），运算量也急剧增加，产生组合爆炸问题。12?m例网络系统具有3个最小路集求系统的可靠度表达式。
解：根据相容事件的概率公式，有显然，当有3个最小路集时，可靠度计算表达式有项。如果有40个最小路集，可靠度计算表达式有项，每一项（最小路集）又是逻辑事件的连乘积，如此规模的运算即使是大型计算机也难以胜任计算工作。
５．利用智能粒度计算分割的计算机网络系统最小路集运算
人类问题求解包括在不同粒度层次上对现实世界的问题及其解进行观察、抽象、表示和理解，这是人工智能的一个公认特点。1985年，Hobbs提出粒度(granularity)的概念并将其用于人工智能中的问题求解[1]；1990年，张钹、张铃提出问题求解的商空间理论，通过分解、合成及推理实现了在不同粒度层次上对问题求解并用于空间规划、时间表安排等问题[2,3]；迄今为止，关于粒度计算还没有统一的、无争议的定义。一种普遍接受的观点是：粒(granule) 是论域上的一簇点（物体）而这些点由于难以区别、接近或某种功能性结合在一起；而粒计算是盖住许多具体领域的问题求解方法的一把大伞，如区间分析、分治法、粗糙集理论等都可以看作粒计算的一种具体实现[4]。
由前文介绍的传统的求网络系统最小路集的节点遍历法可以看出，这一传统方法存在以下缺陷：
（１）该法采用一个二维数组P（V，W）存放全部最小路集，其中W为最小路集的序号，Y表示第W条最小路集中的节点序列中的第V个节点。在求出全部最小路集之前，并不能确定这个最小路集到底有几条，即不能确定W的大小。因此在实际应用中，实现必须开出一个足够大的数组P（V，W），来确保能存放下全部的最小路集。对于复杂的大型网络系统最小路集可达几十万个，而一条最小路集中的节点数目可能达到上百个，因此事先开一个这么大的内存空间对计算机内存要求很高，在普通计算机上难以实现。
（２）求出最小路集的目的是为了后继的网络系统的可靠性分析服务，参与运算的数据占用内存后得不到释放，给更大运算量的可靠性分析带来困难。
（３）表示最小路集的常用方法有节点表示法和弧表示法，为了后继可靠性分析的方便，需要增加用弧表示的最小路集的运算部分。
基于智能计算改进节点遍历法的计算机网络系统最小路集运算方法引入分层(不同粒度) 的概念，对其传统方法作改进如下：
（１）将传统网络系统最小路集节点遍历计算方法中的二维数组P（V，W）用一维动态数组P（V）表示，其容量为（n-1），因为n 个接点组成的网络系统最小路集的最大路长≤n-1。即启用一维动态数组P（V），从输入节点到输出节点，一个节点一个节点的遍历，结果存放在P（V），当找到一条最小路集后，将结果写进硬盘文件中，然后再找下一个最小路集，结果再写入硬盘文件中，依次类推，直到找到全部最小路集，释放一维动态数组。
（２）参与运算的数组全部蚕蛹动态数组，完成运算功能后立即释放，节省了内存，提高了运算速度。
（３）根据节点表示的最小路集文件，将其转换为用弧表示的最小路集，并存入相应文件中，方便了后继的有关计算。
（４）利用智能粒度计算分割对象的理论方法采用动态数组分层实现，从方法上提供了计算机网络系统的可靠性分析的手段。
三、结论
本论文的着眼点在于提供利用智能粒度计算分割的理论方法，采用动态数组分层实现计算机网络系统最小路集运算，从方法上提供了计算机网络系统的可靠性分析的手段。
从五十年代至今，可靠性理论这门新兴学科以惊人的速度发展着，各方面都已积累了丰富的经验。可靠性理论的应用也扩展到国民经济的许多领域。随着可靠性理论日趋完善，运用数学工具也越来越深刻。
可靠性是一门与实践紧密相连的学科，可靠性的考虑贯穿与研制、生产、使用和维修全过程；可靠性工程分析形成应用技术、转化为实际生产力的关键环节在于数学建模方法和数值计算分析方法；解决工程实际问题必须将定性分析方法上升到定量分析水平，可靠性数值定量计算复杂而繁琐，需要一定的计算技巧。
计算机网络系统可靠性从解决实际问题的角度来讲有研究的必要性，从理论的角度来看也有许多深入的问题需要进一步探讨，目前随着计算机网络系统的普及应用，网络系统可靠性成为计算机网络学科中一个非常活跃的领域，本着理论服务于实践的宗旨，将网络可靠性理论应用于实际生产中，将使计算机网络的建设更加科学、合理。
科技论文范文网专业提供计算机毕业论文代写，并提供科技论文写作指导，如有
