通信网络拓扑可靠性层次与测度研究

摘 要：梳理讨论了目前通信网络可靠性研究之间的层次关系，讨论了拓扑可靠性所处的地位、任务、指标等。其次，分析了拓扑可靠性的非概率测度，指出了连通度的核心作用。再次，研究了基于边连通度与节点连通度进行可靠性评价的思想与算法。最后，通过一个算例展示了通信网络拓扑可靠性评价的具体过程。

关键词：通信网路 可靠性 层次 测度

中图分类号：TN93 文献标识码：A 文章编号：1672-3791（2013）07（c）-0003-02

随着通信、信息、网络技术的高速发展与广泛应用，人们对通信网络的依赖愈加明显，随之而来的可靠性问题日益成为用户关注的焦点领域。现代通信网络是一个复杂系统，融合了多学科领域，因此对其可靠性的研究是一项系统工程。

从目前的公开文献来看，通信网络可靠性研究分布于网络应用的各个层次与领域，一般可对应于OIS（Open System Interconnect）系统模型的划分。同时，通信网络的复杂性、动态性、多态性等属性为可靠性评估与优化提出了新的挑战，导致了研究的视角与侧重点也不尽相同。拓扑结构是通信网络的核心特征，其依据拓扑来组织网络形态，进而体现通信网络系统的整体性。因此，对通信网络拓扑可靠性的研究处于整个通信网络可靠性研究的中心地位。

1 通信网络可靠性研究的层次体系

1.1 拓扑可靠性处于核心地位

如引言中所述，拓扑可靠性并不能完全表征整个通信网络的可靠性，其研究对象只关注于网络的拓扑结构，忽略了网络通信设备、路由策略、承载业务、管理效率等因素所带来的可靠性变化。拓扑层高于设备层，同时是路由层、业务层等高层可靠性的基础，在整个通信网络可靠性中处于承上启下的中间环节，其影响可见一斑。

通信网络可靠性可分层讨论，每层均应设计相应的指标与测度方法，以完成对通信网络可靠性的定量描述。因此，通信网络可靠性应具备一个同向、协调、完备的指标体系。在对目前文献梳理的基础之上，可得可靠性指标体系。同时，各文献对可靠性的理解与划分具有相互重叠性，而且关于同一类指标的描述也不尽相同，新的指标也不断被提出。

1.2 拓扑可靠性指标分析

在网络拓扑可靠性的指标描述上是想通的，即在抗毁性与生存性上具有广泛共识。同时可见，连通度是两者的指标与测度设计的基础因素。

（1）网络拓扑抗毁性。主要用于刻画在确定的网络组织结构（即网络拓扑）、预定的破坏（攻击）方案下，通信网络依然能够保持全网或部分连通（物理可达）的能力。在对实际网络进行拓扑抽象之后，抗毁性指要破坏（中断）部分网络节点连接需要移除（破坏）的最少网络节点或链路（边）的数目，从而表征出破坏整个或部分通信网络的困难程度。可见，抗毁性完全由网络拓扑结构所决定，是可靠性的一个确定型指标。

（2）网络拓扑生存性。生存性最显著的变化是引入了网络部件的失效（故障）概率，用于刻画在随机故障或蓄意破坏之下，保持通信网络整体或部分连通的概率。其建立在图论与概率论基础之上的可靠性分析，不仅受网络拓扑结构的影响，同时还依附于网络部件（设备）的故障概率与模式、网络维修与管理等因素，因此网络拓扑生存性是广义的拓扑层可靠性。

2 基于连通的通信网络拓扑可靠性测度

通信网络拓扑可靠性问题可抽象为图的可靠性问题，用图G（V，E）来描述拓扑结构。其中，V表示网络中节点的集合，例如用户终端、服务端、路由服务器等；E表示连接网络中节点的边（链路）集合。同时，本节主要讨论拓扑可靠性的非概率（静态）测度，即不考虑上层业务或下层设备影响，将问题视角完全限定在拓扑层面。

目前，关于拓扑可靠性的静态测度研究很多，可谓仁者见仁，测度设计的侧重点各不相同。例如：连通度（vertex connectivity）、坚韧度（toughness）、完整度（integrity）、粘连度（tenacity）、离散数（scattering number）、膨胀系数（expansion coefficient）等。其中，连通度是拓扑的基础指标，后续的测度均建立在对连通性的充分考虑的基础之上。因此，本节以连通度为重点展开讨论。

2.1 边连通度与节点连通度的定义

（1）边连通度。

记为，其大小等于使网络成为不连通图所需去掉链路（边）的最少条数。它反映网络节点间的内聚程度，是网络可靠性的一个基本度量指标。例如：通过分析可知，所示的网络分割至少需要移除3条边，即边连通度。

（2）节点连通度。

也成为点连通度，记为，其大小等于使网络成为不连通图所需去掉的节点的最少个数。同理，网络的连通度。从某种意义上讲，点连通度是比边连通度更重要的网络可靠性度量指标，这是因为在网络中去掉某个节点就意味着与之关联的所有链路将失去意义。

2.2 边连通度与节点连通度的算法

（1）算法的基本思想。

通常，要求给定网络的边连通度，需要首先确定任意不同两点的链路割集。设和是的两个不同节点，所谓的一个链路割集是指这样的链路集合：若去掉其中所有链路，网络将被分割成两个分支，一个包含节点；另一个包含节点。假设是中所有链路割集中链路的最小数，则就是切断和之间所有路由所需从中删去的最小链路数，故网络的边连通度可按（1）式计算：

2）网络边连通度计算步骤。

由前所述，计算网络边连通度的算法思路是：先按标号算法求分离任两点的最小链路数，然后，再求所有这些数的最小数即可。但是，上述求的算法是针对有向图给出的，而网络边连通度是针对无向图的，因此，算法需首先将原无向网络转换成等效的有向网络。具体计算步骤如下：

第1步：对给定网络，任选一对节点和，按下面的步骤求分离和的最小链路数：

①首先将转换成有向图。方法是：将链路集中以为端点的链路转换成中以为起点的到相应节点的有向链路，将中以为端点的链路转换成中从相应节点到节点的有向链路，又将中其他链路转换成中2条有向链路和。

②用标号算法，求中分离与的最小链路数。

第2步：对所有节点对，，重复上述步骤计算，最后计算：，即网络的边连通度。需要注意的是：由于，对于含有个节点的图，第2步中需要计算的共有个。

3）网络节点连通度计算步骤。

算法的思路是：将割点问题转换成割边问题，从而使求网络节点连通度的问题转换成求网络的边连通度问题。转换的方法是：在网络中任选一对节点和，首先，类似于边连通度算法一样，将转换成有向网络，然后，再将构造另一个有向图，构图规则是：将中除和外的每个节点拆成2个新的中的节点和，并用中的有向链路将它们连接起来。将中每一链路换成中的链路，并把标为，标为。

由构图规则可知，在新的网络中，从发点到收点的包含节点的一条路由，必定包含一个顶点拆成的两部分之间的那条弧。并且原图的一对相邻点及其间的边被转换成等效的由4个节点组成的“8”字形有向回路。因此，一个链路割集在切断中到的所有有向路由方面，与在原始无向图中去掉节点割集有相同作用，即中等于中。综上，可得网络节点连通度算法计算步骤如下。

第1步：对原网络的任一节点对和，按上述规则构造新的有向网络，并用标号法求中分离和的最小链路数，即中分离和的最小割点集点数。

第2步：对所有节点，计算，即得的边连通度。

3 结论

本文讨论了通信网络可靠性的层次划分与影响因素，针对性的分析了拓扑层可靠性的指标与测度，指出了“连通度”作为拓扑层可靠性基础测度，以及其对其它测度设计的重要性。同时，详细分析了节点连通度与边连通度的计算思想与算法步骤。最后，通过一个相对简单的算例演示了通过边与节点连通度计算来评价某一通信网络拓扑可靠性的主要流程。

参考文献

[1]罗鹏程，金光，周经伦.通信网可靠性研究综述[J].小型微型计算机系统，2000，21（10）：1073-1077.

[2]陈建国.通信网络拓扑抗毁性评估算法研究[J].通信系统与网络技术，2006，32（1）：6-7.

[3]饶育萍，林竞羽，周东方.网络抗毁度和节点重要性评价方法[J].计算机工程，2009，35（6）：14-16.