通信网络的设计与抗毁性研究

段宗皓，司贺兵，刘 占

1. 中国人民公安大学 研究生院，北京 100038；2. 中国人民警察大学 智慧警务学院，河北 廊坊 065000

1 研究内容

稳定通畅的通信网络不仅可以提高军事通信的安全性，也会增加部队作战的协同性与机动性，在军事战争中，拥有先进通信网络技术的一方往往能占据战争的主动性，引导战争走向。同时通信设施也是现代战争中最先被攻击对象之一，其一旦被破坏往往造成通信网络中断，使各节点成为孤立的“聋子”“瞎子”，处于被动境地，丧失战场主动性。本文针对假定的军事战备过程，构建以139 个大中型城市为节点的有线通信网络。假定在每个城市设置一个网络设备进行专用网络连接，城市与城市之间的通信线路以最短距离方式连接，这是解决最短网络连接与修复线路问题的关键。本文主要研究如下4个问题。

问题1：按照通信线路总长度最短的连接方案要求，计算出我国139 个城市网络连接方案。问题2：假定战争期间通信网络中的某个城市节点被攻击，并会破坏通信网络的整体连通性，且被攻击城市节点遭到的破坏短时间内无法修复，整个连通网络被分解成具有局部连通性的多个独立分支。为恢复网络的整体连通性，需要启用预先在139 个城市之外设置的战备节点。战备节点设置需与被破坏节点城市距离最近，且启动战备节点后，可形成新的与整个通信网络连通的分支，从而恢复通信网络的整体连通性能。假设北京、武汉、上海3 个城市遭到破坏，设计给出战备节点数量、地理坐标，以及修复线路的连接方式。问题3：假定武汉、黄石、岳阳、沙市、宜昌、信阳、南昌、九江、安庆等9 个城市节点被同时摧毁，设计给出战备节点的数量及地理坐标，同时提出衡量城市节点网络连通性能评价方法。问题4：分析网络线路总长度最短要求下网络连通性差和抗攻击能力弱的问题。通过增加城市节点间连通线路提高网络连通性，其相关成本也将大大提高。所以，在通信线路总长度最短的基础上，城市的通信网络应具备更优良的特点，尤其是要确保一些重要的城市高质量连通，要在同时满足网络经济性与抗攻击性的基础上规划最优方案。

2 对研究问题的分析

2.1 问题1的分析

地球是球体，对于问题1 首先要将城市节点地理坐标转化为球面距离，这样问题1 就转化为图论问题。将139个城市看作139个节点，假定任意两个节点都有边连接，连接边不区分方向，设定每条连接边的权值是其两个节点的球面距离，从而构成一个无向完全带权图，即任意两节点间都有边连接，每条边都有对应权值。连接139 个节点通信线路总长度最短的网络连接方案，转化为求这个无向完全带权图的最小连通图。在无向图中，从某个节点到另外一个节点之间有路径相连，称两个节点为连通的。当图中任意两节点间都至少有一条路径相连称为连通图。当构成连通图的边权值之和最小时，称为图的最小连通图［1］。问题1 中节点城市之间通信线路总长度最短连接方案，即图的最小连通图。

构建无向完全带权图最小连通图常用方法有Prim 算法［2］和Kruskal 算法［3］。Prim 算法构建具有最小权值且连接所有节点的图，生成图中没有回路。其做法为：先以一个节点作为最小连通图的初始节点，然后以迭代的方式找出最小连通图与其他节点权值最小的边，将其加入生成图中；如产生回路则跳过这条边，继续下一节点。当所有节点都加入生成图后，就找出了给定图的最小连通图。Kruskal 算法在查找最小连通图之前，先对所有连接边按权值从小到大排序。将排好序的权值边依次加入生成图中，如果加入时产生回路就跳过该边，继续加入下一条边。当所有节点都加入生成图后，就找出了给定图的最小连通图。

Kruskal 算法需要对权重边进行排序，从最小权值边开始构建最小连通图。而Prim算法可从任意节点开始构建最小连通图，将所有节点逐一加入生成图。Prim算法和Kruskal算法的时间复杂度分别为O（n2）和O（eloge）（n为节点数量，e为连接边数量）。Prim 算法时间复杂度与图中边的数量无较大关系，适合稠密图构建最小连通图；而Kruska 算法需要对图的边进行访问，它的时间复杂度取决于图中边的数量，更适合稀疏图。本文从无向完全图基础上构建最小连通图，为稠密图，连接边数量多，因此，采用Prim算法构建城市节点的最小连通图。

2.2 问题2的分析

该问题中假定3 个城市节点分别遭到破坏，不能提供正常网络连接功能，导致原本连通的网络被分割为多个连通子图。此时需要根据被破坏节点关键重要程度和剩余节点连通情况对网络进行修复，以最大限度保障网络正常运转。对于未受损节点，设置战备节点与其中某个距离最近的节点相连接即可。对需要多个战备节点情况，则需根据剩余节点连通情况考虑战备节点的个数和位置。确定连通子图数量，可以分为三种情况：（1）如果连通子图数量为1，可以不用设置战备节点，其余节点仍保持连接；（2）如果连通子图数量为2，两个连通子图最近节点直接连接即可保持连接；（3）如果连通子图数量大于2，需设置战备节点，确保战备节点到达连通子图的距离和最小。

新增加的战备节点是在已有连通子图继续保持连通情况下，使所有节点能够全连通的最小代价方案，且不影响已有连通子图的连接。即在139 个城市节点之外的所有坐标中选择能够使其构成全连通的最小代价总和坐标方案。设置的战备节点数量越多计算越复杂，战备节点数量越大，需要计算的战备节点与各连通子图的距离总和就会越大，计算代价越大。同时，被破坏的城市若是特别重要的城市节点，如北京、上海等，需要考虑增设战备节点以承接其关键节点功能。

2.3 问题3的分析

与问题2相比，问题3在假定被破坏城市节点数量和程度上有所不同。问题2 中假定某一个城市节点遭到严重破坏，问题3中假定9个城市节点被同时摧毁。若采用与问题2 同样方式解决问题3，随着不连通子网数量的增加，程序计算时间复杂度增加，搜索时间变长。因此，寻找收敛速度更快的算法十分必要［1］。本文构建了以平均连通度（Cˉ）［4］、连通总距离（L）［5］和节点关键性（k）三项指标为依据的通信网络综合评价指标，衡量通信网络的连通效率。

2.3.1 平均连通度

在城市节点无向图中，与节点i相连接的连接边数量称为该节点的连通度，记为ci，连通度反映了节点与其他节点连通程度。连通度值越大，节点与其他节点连通路径数量越多。图中所有节点连通度的平均值，称为图的平均连通度，记为Cˉ，其计算见公式（1）。

式中：n为城市节点数量。平均连通度值越大，节点间相连接的路径就越多，网络的整体稳定性就越强，同时网络建设的投入也越大。

2.3.2 连通总距离

网络中所有连通节点之间的距离总和，称为连通总距离，记为L，其计算见公式（2）。在城市节点对（vi，vj）（i≠j）之间存在直接路径连通时，才计入连通总距离，间接连通的节点间距离不计入连通总距离。

式中：dij为城市节点i与城市节点j之间的直接连通路径距离（无向图中重复边只计算1 次）。连通总距离反映了城市通信节点网络建设总投入，总距离越大，对应的网络建设投入就越多。

2.3.3 节点关键性

每个城市节点的连通性对整个城市节点网络连通重要性并不相同。与多个节点城市相连接的节点，可以被视为局部网络中枢，一旦其节点功能被破坏，会造成多个城市节点网络通信故障。对于首都、省会等大城市节点，其节点功能一旦被破坏，除引发整体网络通信故障外，还会带来更大负面影响，此类节点关键性值要高于一般小城市。

节点关键性是根据节点地理位置、节点在网络中的关连节点数量、城市规模等因素综合给出的评价指标。计算整体网络综合性时，节点关键性参数可设置为1。

本文综合平均连通度、连通总距离和节点关键性等因素，综合评价通信网络连通性能，特别在城市节点被破坏情况下，对重建节点、备用节点选择提供参考。通信网络综合评价指标反映了网络整体连通性能和效率，对通信网络评价和网络可靠性都提出了要求。

2.4 问题4的分析

在构建通信网络的过程中，如果单纯追求网络线路总长度最短，容易导致网络的抗攻击能力减弱，而提高网络抵抗攻击能力往往又意味着增加网络建设经济成本。在问题1 构造的通信网络最小连通图基础上，构建连通性能更高、抗攻击性能更优的网络非常必要，尤其是对一些重要城市节点，需要确保其在通信网络中保持持续连通。因此，设计方案在考虑网络抗毁性、可靠性、通信能力等约束的同时，还需要考虑网络重建的经济性和可行性等约束。连通性约束指复杂信息网络拓扑结构改变后，任意节点之间至少存在一条路径相连，这是网络连通的最低要求。本文对通信网络中的重要城市节点，如首都、直辖市和省会城市，采取预先战备节点设置策略，一旦遭受攻击可以将节点功能切换到战备节点，确保通信网络的连通性能。

3 问题的解决方案

3.1 问题1模型建立与求解

3.1.1 地理坐标的转化

通过城市间的地理坐标计算出地球上这两个城市节点所在位置大圆的劣弧长［6-7］LAB，假设地球为球体且半径为R，而A、B的地理坐标分别为A（JA，WA）、B（JB，WB）。如图1 所示球体，O 为球心，C 与A 纬度相同，C 与B 经度相同，F 为BC 延长线与过球心直线的交点，CH与BE都垂直于OF，BD垂直于CH。由此可以推导出AB间距离，见公式（3）。

图1 地球的球面模型

采用总长度最短的方案连接139 个节点之间的通信线路，本质上就是求139 个节点的最小连通图，与平面图形最小连通图的差别在于球体上根据经纬度设置每个节点坐标，球体两点距离根据两点经纬坐标计算劣弧长。球体上点与点之间距离需要单独计算和处理。

3.1.2 最小连通图生成模型的建立

计算每个节点与其他节点的距离（任意两个节点都可建立通信线路），利用Prim算法构建最小连通图［8］。算法描述：（1）城市节点集合V1，带权无向边集合E1，其边权值为城市节点之间的坐标距离，集合V2存放生成的最小连通图节点，集合E2存放生成的最小连通图的边。（2）从V1中选取节点x，将x加入V2中，此时V2=｛x｝，以x作为最小连通图起始节点，由该节点开始构建最小连通图；集合E2初始为空。（3）在集合E1中，选取V1中节点到V2中节点权值最小的连接边（u，v），v在V2中、u在V1中；将u加入V2，同时将u从V1中删除，并将（u，v）加入边集合E2。重复操作此步骤，直到集合V1中节点全部添加到V2中。（4）E2即为集合V1中城市节点的最小连通图，其各节点之间的距离总和最小。

构建的总长度最短连接方案：（阿克苏，喀什）；（喀什，和田）；（阿克苏，塔城）；（塔城，阿勒泰）；（阿勒泰，乌鲁木齐）；（乌鲁木齐，哈密）……（呼和浩特，二连浩特）；（二连浩特，锡林浩特）；（齐齐哈尔，海拉尔）；（海拉尔，满洲里）；（齐齐哈尔，黑河）；（格尔木，拉萨）；（拉萨，日喀则）。连接139 个节点通信线路总长度最短的网络连接方案如图2所示。

图2 城市节点最小连通图连接方案

3.2 问题2求解方案与讨论

假定北京、武汉和上海3 个城市节点分别遭到破坏，讨论如下：

3.2.1 假定上海节点被破坏

图3 所示为假定上海节点遭到破坏后的连通图，该节点遭到破坏后连通子图数量为1。此种情况下，除被破坏节点外，整个网络仍然连通。考虑上海节点的重要性，需在距离上海节点最近位置选取战备节点，将上海节点功能转移到该战备节点即可，无需改动其余节点连接状态。

图3 假定上海节点被破坏后的连通图

3.2.2 假定武汉节点被破坏

图4 所示为假定武汉节点遭到破坏后的连通图情况，武汉节点遭到破坏后连通子图数量为2，连通网络被分割为两个互不连通的子网，因此，需要选择新的战备节点并修复网络，从而使整个网络连通。经检索得到两个不连通子图中距离最近城市节点为（营口，大连），计算距离为203 km（给定坐标点间球面距离，下同），连通这两个城市节点可以在最小距离代价下重新连通整个网络。但由于武汉节点地理位置重要，该节点功能不能废弃，因此，需要在该节点附近位置选择战备节点，并将该节点功能转移至战备节点。

图4 假定武汉节点破坏后的连通图

连通子图1（图4 中蓝色部分）中距离武汉较近的城市节点为黄石（83 km），连通子图2（图4 中红色部分）中距离武汉较近的城市节点为信阳（174 km）、岳阳（177 km），同时黄石距离岳阳（206 km）较信阳（235 km）更近一些。为便于将武汉节点功能转移到战备节点，选取黄石作为连接点之一，连接（黄石，岳阳）两个节点，并选取武汉到两节点连线的垂足为战备节点，计算得到战备节点坐标为（114.72，30.08），如图5所示。

图5 启用（黄石，岳阳）后连通图

3.2.3 假定北京节点被破坏

图6 所示为假定北京节点遭到破坏后的连通图情况，北京节点遭到破坏后连通子图数量为3，连通网络被分割为3 个互不连通子网。结合前面对问题2 的分析，连通子图数量大于2，需要设置战备节点，并且需要确保战备节点到达连通子图的距离和最小。战备节点是在不影响已有连通子图的连接状态，同时使已有连通子图不间断持续工作情况下，满足所有节点全连通的最小代价方案。需要在139 个城市节点之外的所有坐标中选择能够使其全连通的最小代价总和坐标方案。设置的战备节点数量越多，计算就越复杂。

图6 假定北京节点破坏后的连通图

如图6 所示，北京节点遭到严重破坏时原来的连通图被分成3 个连通子图。经检索得到不连通子图中最近距离的3 个城市节点为天津、保定、张家口，其中（天津，保定）距离152 km，（保定，张家口）距离217 km，（天津，张家口）距离271 km。为保证所有正常运行城市节点网络的全连通，需要将3 个不连通的子网络进行连通。同时，考虑假定节点功能的重要性，需将其相关节点功能进行转移。在（天津，保定，张家口）三节点组成三角形的费马点设置战备节点，可满足最小开销实现网络的全连通。计算得到该战备节点的坐标为（115.79，39.22），该战备节点与天津距离122 km，与保定距离48 km，与张家口距离188 km，与功能被转移节点北京距离92 km，如图7所示。

图7 启用战备节点后的连通图

3.3 问题3求解方案与讨论

3.3.1 假定多个节点被摧毁的战备节点

如果多个城市节点通信功能被摧毁，通信网络被分割为多个相互不连通子网，被摧毁的城市节点通信功能不能正常运转，相互不连通的子网间通信功能不能正常运转。此时，需要确定连通子网数量，采取非连通图中距离最近点连接，以保证网络连通。假定武汉、黄石、岳阳、沙市、宜昌、信阳、南昌、九江和安庆9 个城市节点功能同时被损毁，如图8 所示，连通网络被分割为5个独立的连通子图。

图8 假定武汉等9个城市节点破坏后的连通图

5 个不连通子网距离最近的5 个节点为襄樊（112.12，32.01）、长沙（112.94，28.23）、合肥（117.23，31.82）、常德（111.7，29.03）、景德镇（117.18，29.27），这些节点分布在被摧毁的9 个城市节点附近。考虑战备节点建设经济性，只讨论1个或2个战备节点情况。

如果仅设置1 个战备节点，则该节点需遵循到5个待连通节点的距离和最小原则，在上述5 个待连通节点区域进行检索，得到节点（113.66，29.75）符合要求，经计算该节点到达上述5 个城市节点连接总长为1 437.9 km。

如果设置2个战备节点，则采用战备节点1连接上述5 个城市节点中的3 个，战备节点2 连接另外两个，此外还需两个战备节点之间相连接，同时需遵循距离和最小原则。战备节点1 设置时通过两条两城市节点连线垂直平分线交点进行确定，战备节点2设置则遵循距离战备节点1 和另外两城市节点连线距离最小原则进行确定。经计算和检索，得到战备节点1 坐标（113.40，30.31），战备节点2 坐标（116.35，30.43），连接总长为1 290.2 km。

此外，设置1 个战备节点情况下，增加节点数量1，连通后增加总连通度为10，计算得到连通网络的总平均度值为1.98。设置2 个战备节点情况下，增加节点数量2，连通后增加总连通度11，计算得到连通网络的总平均度值为1.97。若仅增加1 个战备节点，该节点连接节点过多，一旦再被破坏，将造成网络更大损失。增加2 个战备节点可以减少节点城市连接负载，降低网络风险，并可以满足将周边被破坏城市节点功能向战备节点转移的要求。综合以上考虑，在此种情况下，选择增加2个战备节点的策略。

3.3.2 通信网络综合评价指标

网络连通性指标一般有连通度、通达度、回路数等［9-11］，在本文所研究的节点城市通信网络中，特别是有节点被破坏后的重建网络设计方案中，衡量网络方案优劣不能简单以连通与否作为标准，还要考虑城市节点关键性、通信网络建设投入最优等具体情况［12］。对于关键城市需要设置战备节点，对于一般节点需要考虑重建时效，能在最短时间内恢复重建保障网络整体通信畅通。本文在确保城市节点网络最小连通图正常通信前提下，提出以平均连通度、连通总距离和节点关键性为参考因素的通信网络综合评价指标，用于更优的网络建设方案评价，见公式（4）。

式中：p代表综合评价指标；k为节点关键性指标，反映节点城市关键重要性，首都、省会等大城市的关键性值要高于一般小城市；Cˉ为城市节点网络的平均连通度，反映整体网络的连通复杂程度，在整体网络连通情况下，Cˉ值越高，网络连通越复杂；L为连通总距离，是网络中所有连通节点之间的距离总和。

在本文构建的城市通信网络中，节点的连通度越大，表明能与其直接通信的节点越多，而该节点一旦被破坏带来的网络中断则越严重，所以，将平均连通度作为反相关指数之一。连通总距离越大，则表明连通网络线路越长，需付出相应建设费用越高。从经济角度考虑，将连通总距离作为反相关指数之一。节点关键性体现的是节点城市在经济、军事等方面的重要程度。首都、省会或人口超千万的大城市，或者处于经济、军事关键地域的城市，在整个连通网络中除连通节点功能外，还担负其他重要功能，k值较大。节点关键性高的城市节点一旦被破坏，需要在其周围建立战备节点，并将城市节点功能向战备节点转移。

3.4 问题4模型建立与讨论

在构建通信网络的过程中，不能一味追求网络线路总长度最短，还需考虑网络的连通性和抗攻击能力，而提高连通性往往意味着网络构建的经济成本增加。本文提出的综合评价指标既考虑构建网络的经济性，又考虑网络的抗攻击性。网络结构的微小不同都会引起网络连通度的不同，连通度主要由网络的拓扑结构决定，它取决于网络拓扑结构中的以下因素：（1）对既有网络添加边，会增加网络的连通度；（2）两个相同节点数和边数的网络，其连通度会因为边的位置不同而不同，此处边的位置指边的邻接节点。在通信网络设计中，“加边”必定会增加网络的连通性，但是边加在网络中的不同位置也会影响网络的连通度。

对通信网络而言，连通度越高，表明节点与其他节点连接的边越多，中心节点负载越大，则该节点被破坏后带来的网络中断影响越大。因此，通信网络设计需要采用综合评价指标衡量网络的连通效率，以及单个城市节点在网络中的连通性能。特别是在局部节点出现损毁时，需要根据网络连通情况调整或增加战备节点，使网络以最快速度、最小代价恢复连通。

4 结束语

稳定通畅的通信网络对国家安全和社会安全至关重要。本文从构建城市通信网络入手，利用Prim算法构建最小生成网络，并对连通网络局部节点损毁进行恢复连通策略分析和设计。若假定的城市节点被损毁，通信网络被分割为多个不连通网络，从最大效率保障整体网络通信连通性策略入手，提出网络综合评价指标策略，综合网络连通度、网络连通距离和节点关键性等因素整体评估网络的效能和战备节点构建策略。同时，本研究也存在一些不足，如计算城市节点距离采用球面坐标计算，对多个城市节点被破坏仅提出了解决思路和定性分析等，要进一步解决这些问题还需后续深入研究。