刘 言 ，赵 锐 ，杜 磊 ，李 华

（1.军事交通学院 研究生管理大队，天津 300161；2.军事交通学院 基础部，天津 300161；3.武警指挥学院 管理与后勤系，天津 300250）

0 引言

近几年，随着大数据时代的到来，全球网络化概念的兴起，通信网络在传输速度、信息准确性、建设成本等方面发展迅速，在国防、国民经济和社会生活中的各个领域发挥了前所未有的重要作用。通信网络抗毁性（Invulnerability）作为通信网络可靠性和安全性的重要方面，成为了当前网络规划设计的研究热点。

通信网络抗毁性是指在自然故障或遭受攻击的条件下，通信网络仍维持正常通信的能力[1]。当前，评估指标研究是网络抗毁性研究的重要方面，国际上对抗毁性指标的研究成果有限[2]，大多以图论为基础，提出了一些表征连通性和效率的评价指标。例如：从连通性角度，参考文献[3]提出网络连通度、粘聚度指标；参考文献[4]分别研究了不同类型的复杂网络面对不同打击条件下最大连通分支（Giant Component）节点数与网络总节点数之比S、最大连通分支平均最短路径L与节点移除比例f的关系；从通信能力角度，参考文献[5]定义了网络通信效率e，用于刻画节点间的信息传输效率。在此基础上，参考文献[6]综合了连通性和通信效率两方面的考虑，以连通分支和平均最短路径作为测度定义了连通系数，对于网络抗毁性评价更加综合全面。网络的抗毁性指标为抗毁性评估提供了标准，通过数值仿真结果可以对比分析各种模型的抗毁性能[7]。

规划设计满足一定抗毁性指标要求的网络称为抗毁性网络设计（Suvrivable Network Design）。抗毁性网络设计工作往往是从网络拓扑结构开始的[8]。参考文献[9]探讨了在跳数限制下，构建满足一定连通度的抗毁网络模型，并采用生成树优化 （Spanning Tree Optimization，STO）算法求解模型。但是该算法规则复杂、不易仿真实现，且优化后成本开销较高。参考文献[10]针对广域测量系统通信网络，以跳数和连通度指标构建抗毁性网络模型，结合流量状况，采用改进的饱和割集算法求解网络拓扑结构，但该算法提出的网络结构代价相对较高，且负载均衡能力有限。

本文依据通信网络抗毁性需求，从网络拓扑结构出发，利用图论的方法，结合连通性和通信效率两方面的考虑，建立了以连通性和跳数约束为抗毁性指标的优化模型，提出了改进生成树优化（Improved Spanning Tree Optimization，ISTO）算法，实现对预定规模的通信网络进行抗毁性设计。

1 抗毁性网络模型构建

1.1 抗毁性指标分析

在抗毁性网络设计前，需将网络的抗毁性指标作为一个重要的衡量因素考虑进去，定义适合的抗毁性指标。根据网络抗毁性定义，抗毁性网络设计是使网络在自然灾害或遭受攻击的情况下，能够保持连通以维持正常通信，因此连通性是网络抗毁性的重要方面。连通度是衡量连通性的重要指标。

此外，网络在受攻击后信息的通信效率是决定网络性能的关键因素之一，也是网络抗毁性指标建立中需要考虑的。通信网络的节点间信息传输一部分是通过跳传实现，传输时延与服务质量与经过的节点数量有关。跳数是衡量节点间信息传输经过节点数量的指标。例如，以无线电波和光作为传输介质的网络，传输时延主要集中在节点设备上，如果节点间的跳数太多，就会增加通信设备的中转及路由开销，延长数据传输时间，降低传输质量。因此，在抗毁性通信网络设计时，两节点间跳数需要有一定的限制，以满足其传输需求，确保网络通信效率。

1.2 抗毁性网络设计模型

通信网络拓扑结构设计首先要确定各节点地理位置、各节点间构建线路的复杂情况以及节点间通信业务量，以此作为构建网络的成本开销。将其抽象为成本开销w。将通信网络的各子网、路由交换设备、调度中心等抽象为点集V，两点间构建链路所需的成本开销抽象为边集E，由此共同构成了通信网络构建的成本开销网络G（V，E）。

通信网络的抗毁性设计目标就是要设计出满足一定抗毁性指标要求，且成本开销最小化的网络[10]。针对一般通信网络的特性，抗毁性网络设计模型需要满足以下抗毁性指标条件：

（1）网络连通度至少为2。连通度为2的要求能够保证网络在任意单条链路中断的情况下仍保持连通。

（2）任意两节点最小跳数不大于K。跳数约束可确保网络正常状态的时延要求，而在两点间最小跳数链路遭遇毁伤后，用户可能不在乎时延是否有所延长，而更加关心信息能否顺利送达。因此，最小跳数不大于K的要求能够确保通信网络业务传输的抗毁性。

基于此，本文构建的抗毁性网络设计模型如下：

其中，xij是所求拓扑结构的邻接矩阵X的元素，满足：

wij为节点间建立链路的成本开销矩阵W中的元素，代表在节点 vi、vj的成本开销；N为节点总数；κ为节点连通度；Dij是节点 vi与 vj最短路径的跳数。

2 改进生成树优化算法

2.1 算法步骤

本文在求解模型的过程中，利用图论的相关理论，基于生成树增加边的设计思想，对模型的部分指标进行了转化，进一步提出了ISTO算法。

算法的基本流程如图1所示。

图1 ISTO算法基本流程

首先在已知的成本开销网络中选取一个节点作为根节点，然后构建一棵深度为D=K/2（若K是奇数，则D=（K-1）/2）的最小生成树，其中K是任意两点之间的跳数上限，生成树能够满足网络连通度为1的要求；然后在生成树基础上进行加边优化，使其能够满足连通度为2的要求；最后得到最小跳数不大于K的2-连通最小开销网络。

具体步骤如下：

输入：带权网络W，跳数上限K。

输出：优化后的网络邻接矩阵B；权值w。

（1）令 i=1；

（2）构建以vi为根节点，带跳数限制的最小生成树Ti；

（3）基于 Ti进行加边优化，得到优化后网络邻接矩阵Bi；

（4）求 Bi边的权值和 wi，若 i＜N，i++，则执行步骤（2）；若 i=N，则执行下一步；

（5）选出 B1到 BN中连接边权和最小的结构 Bj，令其为B。

2.2 带跳数约束的最小生成树构建

构建最小生成树是在已知一个加权无向图G（V，E）的前提下，求出以节点n为根节点，深度为 D的最小生成树。构造过程采用改进的Prim算法。改进的Prim算法与标准Prim算法的区别在于，在待入选边染成蓝色的选择过程中，引入了与待入选边相连的未入选节点与根节点的跳数判断。若满足跳数限制D的要求，则按标准Prim算法步骤继续执行；若超出了跳数限制，则将与该入选节点相连的所有未入选边染成红色。

具体步骤如下：

输入：G（V，E，L）的邻接矩阵 A；所选根节点 n；最大跳数限制D；

输出：带跳数约束的最小生成树T。

（1）取 G（V，E，L）节点 n 作为初始蓝子树 T，初始浅蓝与蓝子树的集合C，置i=0；并把与T关联的长度边（n，j）着以浅蓝色，其中 j∉T，C=C∪（n，j）；

（2）在所有浅蓝色边中，选择最小长度边（i，j）（其中，i∈T，j∉T），将其着成蓝色，置 T=T∪（i，j）；

（3）若节点 p∉C，且在图 T中，j到 n点的跳数＜D，则把（j，p）着为浅蓝色；否则将与点 j关联的∉T的边都着红色，重新执行步骤（3）；

（4）如果存在与 p关联的一条浅蓝色边（w，p），且（j，p）为浅蓝色，l（w，p）＞l（j，p），则把边（w，p）着成红色，C=C∪（j，p）；否则，不作任何处理；

（5）置 i=i+1；

（6）如果 i=N-1，则算法终止；若 i＜N-1，则返回步骤（2）。

最后得到的蓝子树T即为任意两节点跳数不大于K的最小生成树。

对于跳数的计算，采用的是将所有边的权赋值为1，然后应用 Dijkstra算法求两点的最短路径，所得到的结果即为该两点间的跳数。

2.3 基于最小生成树的加边优化

由于最小生成树已满足跳数约束要求，因此加边优化的目标是增加尽可能少的边，使优化后的网络连通度为2。由图论可知，一个节点数量大于2的网络的连通度至少为2（当且仅当网络中不存在割点）。而一棵树除了叶子节点（度为1的节点），其他所有节点都是割点。因此要使生成树通过加边优化达到2-连通网络要求，首先要消除其割点。本文采用叶子节点之间增加边的方式，能够利用尽可能少的边，消除更多的割点，从而用更少的开销，达到连通度为2的目的。

如图2所示，TA与TB为连接了同一棵树中的叶子节点后的网络，且TA与TB均增加了两条边。TA与TB的不同之处在于，TA仍是一个1-连通网络，而 TB是 2-连通的。显然TB达到了优化目标。通过分析发现，TA与TB的区别是TA中选择相连的叶子节点v4与v5以及v6与v7，在原树中的通路v4-v2-v5没有经过根节点 v1，v6-v3-v7也没有经过 v1，而 TB中 v5与 v6在原树中通路为 v5-v2-v1-v3-v6经过了根节点v1，同理，v4与v7的通路也经过了v1。

图2 两种悬挂点增加边的方式

因此，在加边优化之前，需判定两叶子节点在原树中的通路是否经过根节点。只有经过了根节点的两点才进行加边优化。例如图2的TB中，优化前因v5与v6之间的通路经过了 v1，因此可以为 v5与v6增加边。此外，若叶子节点数量为奇数，则在两两加边优化后还剩余一个叶子节点，这时应选择该叶子节点与旁支的节点加边。

加边优化具体步骤如下：

假设T（V，E）是一棵无权最小生成树，其邻接矩阵为A，节点数量为N。

输入：最小生成树的邻接矩阵A，生成树根节点n；

输出：优化后的网络图邻接矩阵B；

（1）初始化 TB=T，求出网络中各节点的度，按度从小到大的顺序将节点进行排序，其节点分别为 v1，v2，…，vN，统计度 d=1的点的个数为 L；置 i=1；执行下一步；

（2）置 j=i+1，执行下一步；

（3）分下列 4种情况：

①若 di＜2，dj＜2，且节点 vj与 vi在 T 中的路径经过根 节 点 vn，则增加边（vi，vj） （di与 dj均+1），TB=TB∪（vi，vj），执行下一步；

②若 di＜2，dj＜2，但节点 vj与 vi的路径不经过根节点 vn，或是 di＜2，dj≥2，j＜L，则 j=j+1，重新执行步骤（3）；

③若 di＜2，dj≥2，j≥L，且节点 vj与 vi在T中的路径经过根节点 vn，则增加边（vi，v1），TB=TB∪（vi，v1），执 行下一步；

④若 di≥2，则执行下一步；

（4）若 i＜L，置 i=i+1，返回步骤（2）；否则执行下一步；

（5）返回结果图 B。

3 算法分析

3.1 实例分析

以某智能园区通信网络建设为例，该园区有14个主要通信节点，其主干网采用万兆光缆，因此可认为该园区网有足够的链路冗余，不考虑流量。根据14个节点建设的地理位置、通信线路的建设成本以及建设难度等，对成本开销进行了评估，其成本开销网络以邻接矩阵表示，如图3。抗毁性网络的设计要求满足至少2-连通，任意两点间最小跳数不超过4跳，且总建设成本开销尽可能小。

图3 某智能园区通信网络成本开销矩阵

其中，矩阵中i行j列对应的是wij的值。

首先，任意取节点（假设是节点4）作为初始树的根节点，通过改进的Prim算法生成带跳数限制的最小生成树，如图4所示。

图4 节点间跳数不大于4的最小生成树

图5 是通过加边优化后生成的网络G1，图中虚线是在最小生成树基础上增加的边，可以看出，G1满足2-连通且最小跳数为4的要求，且有18条边。

图5 加边优化后生成的抗毁性网络G1

依次选择每一个节点作为初始树的根节点，按照算法进行抗毁网络生成后，得到网络开销比较，如表1所示。

表1 选取不同根节点生成的抗毁网络开销列表

由表1可见，当以节点4为初始树根节点时，生成后的网络总开销最小，为60。因此，G1是满足抗毁性指标且成本开销最少的抗毁性网络，达到了设计目的。

3.2 比较分析

为了进一步验证算法性能，将ISTO算法与参考文献[9]提出的STO算法进行比较。STO算法的基本流程同样是在成本开销矩阵的基础上构建一个带跳数约束的最小生成树，再通过加边优化构建2-连通的网络。

两者区别在于，在加边优化过程中，ISTO算法不要求最后生成的网络在最小跳数路径中断后，备用路径也满足跳数限制要求。这是基于两个方面的考虑。一是在网络发生故障后，重点不是保证网络传输时延一定与毁伤前一致，而是要求网络连通，重要信息能够顺利通达。二是STO算法因过于要求跳数限制，导致算法规则复杂、不易仿真实现，且优化后的网络成本开销过大。

以图4中智能园区通信网络为例，若采用参考文献[9]中的 STO算法，同样以节点 4为根节点，优化后得到拓扑结构 G2（图6）。其中，G2有 24条边，成本开销为166。两算法生成网络的性能比较如表2所示。

图6 基于STO算法构建的网络拓扑结构G2

比较后发现，G1的成本开销仅是 G2的 36.2%，即使以最大的v1为根节点，以ISTO算法生成的智能园区网络也仅是G2的79.5%。因此，本文提出的ISTO算法更具有易于实现、成本开销低的优点。

4 结束语

通信网络抗毁性是目前通信网络技术发展过程中需要重视和亟待解决的问题，连通性和通信效率尤其重要。本文提出的ISTO算法能够用于求解连通度和跳数约束的抗毁性模型，并为抗毁性网络设计提供了一个定量标准和有效的计算方法。实际通信网络中情况较为复杂，抗毁性通信网络设计应与具体工程需求密切相关。而ISTO算法默认链路容量足够大，不会出现信息拥塞，没有考虑流量状况。

下一步可以结合具体业务流量与链路带宽等因素，从通信网络路由算法入手，制定适合的路由策略，使网络在毁伤前后都能顺利选择最优路径传输，提高网络整体资源利用率，进一步提升网络抗毁性。

[1]陈建国，张永静.通信网络拓扑抗毁性评估算法研究[J].无线电通信技术，2006，32（1）：6-7.

[2]SAVOLA R.Towards a security metrics taxonomy for the information and communication technology industry[C].In proceedingsofthe InternationalConference on Software Engineering Advances，ICSEA，Washington，2007：60.

[3]FRANK H，FRISCH I T.Analysis and design of survivable networks[J].IEEE Transactions on Communication Technology，1970，8（5）：501-519.

[4]ALBERT R，JEONG H，BARABÁSI A L.Error and attack tolerance of complex networks[J].Nature，2000，406：378-382.

[5]CRUCITTI P，LATORA V，MARCHIORI M，et al.Efficiency of scale-free networks：error and attack tolerance[J].Physica A： StatisticalMechanics and its Applications，2003，320： 622-642.

[6]吴俊，谭跃进.复杂网络抗毁性测度研究[J].系统工程学报，2005，20（2）：128-131.

[7]杨琴.网络拓扑模型的演化机制及抗毁性研究 [D].郑州：解放军信息工程大学，2009.

[8]张中伟，陈建国.抗毁通信网络设计[J].无线电通信技术，2000，26（2）：33-38.

[9]刘啸林.带跳数限制的抗毁性网络设计[J].计算机应用与软件，2007，24（7）：138-139.

[10]熊小萍，谭建成，林湘宁.基于改进饱和割集算法的广域测量系统通信网络架构设计 [J].电力系统自动化，2013，37（9）：97-102.