有线通讯网络的连通路径与性能研究分析

Research and Analysis on Connectivity Path and Performance of Wired Communication Network

摘要: 本文针对全国多个城市构建的无向图进行研究、分析与建模，采用python运行图算法，利用python计算引入的连通性判断标准——连通度，构建最小生成树，并生成图。通过利用AHP层次分析法，MATLAB等数学软件工具进行计算，并将已经量化的数据进行模型比较，进而得出较优模型。

Abstract: In this paper, the undirected graph of many cities in China is studied and modeled, and the minimum spanning tree is constructed and the graph is generated by using the python running graph algorithm and the connectivity judgment standard introduced by Python calculation. AHP analytic hierarchy process and MATLAB mathematical software are used for calculation. The quantified data are compared with models and a better model is obtained.

1. 引言

现代社会是信息化高度发达的社会，现代战争也由数字化战争转化为信息化战争，因此加强我军信息化战队的建设，构建兼顾连通性和经济性的通信网络尤为重要 [1]。要构建包含多个大中型城市作为节点的有线通信网络，在每个城市内设置一架专用网络连接设备 [2]。也就是说，将多个城市作为图中的节点，现实中的通信线路作为图中的边，同时要考虑到经济性，网络的连通性，网络的抗攻击性，以及重要城市的连通性 [3] [4] [5]。

2. 模型建立与求解

2.1. 城市的最短长度的模型——Prim算法

由最小生成树MST性质知，假设 $G=\left(V,\left\{E\right\}\right)$ 是一个连通网，U是顶点集V的一个非空子集，若 $\left(u,v\right)$ 是一条具有最小权值(代价)的边，其中 $u\in U$， $v\in V\text{-}U$，则必存在一颗包含边 $\left(u,v\right)$ 的最小生成树。

假设 $G=\left(V,\left\{E\right\}\right)$ 是连通图，TE是G上最小生成树中边的集合。算法从 $U=\left\{u_0\right\}\left(u_0\in V\right)$， $T_E=\left\{1\right\}$ 开始，重复执行下述操作：在所有 $u\in U$， $v\in V\text{-}U$ 的边 $\left(u,v\right)\in E$ 中找一条代价最小的边 $\left(u_0,v_0\right)$ 并入集合TE，同时 $v_0$ 并入U，直至 $U=V$ 为止。此时，TE中必有n-1条边，则 $T=\left(V,\left\{T_E\right\}\right)$ 为G的最小生成树，

使用matpoltlib库 [6] 进行绘制，得到效果图，总边数为138条，总长度约为25,342.380千米，具体连接如图1所示。

Figure 1. Design sketch

图1. 效果图

2.2. 启用战备节点的个数和地理坐标的模型

删去三个城市后，整张图分为4个连通分量，备用节点的选取为与北京相连的三个城市(图中以绿色表示)，张家口，天津，保定的中心点，并再度与之相连(用绿色的点线连接)，红色字表示毁坏的城市。如图2所示。

Figure 2. Beijing connected graph

图2. 北京连通图

备用节点坐标为(115.85738151138278, 39.58078078596456)，武汉同上，如图3所示。

Figure 3. Wuhan connected graph

图3. 武汉连通图

备用节点坐标为(114.5698910377149, 31.175871971198767)。

对于上海，由于上海在图中属于边缘节点，只有一个相连城市，毁坏后不影响整体的连通性，但考虑到上海本身较为重要，可以在原址启用备用节点并与原来相连的城市保持连接。

2.3. 区域性结点被集中毁灭与衡量网络连通性能指标的模型

删去九个城市后，整张图有5个连通分量，如图4所示。

Figure 4. Delete nine city connectivity map

图4. 删掉九市连通图

针对区域性结点被集中毁灭的情况，寻找被毁灭区域的中心点，生成中心点的节点集合选取标准是若原通信线路中包含路线(s,t)，s或t中一个节点被摧毁，则另一节点加入生成中心点的集合中。计算中心点。

给定n个点的经纬度值， $\left({\text{lon}}_{\text{1}}{\text{,lat}}_{\text{1}}\right)\left({\text{lon}}_{\text{2}}{\text{,lat}}_{\text{2}}\right)\cdots \left({\text{lon}}_n{\text{,lat}}_n\right)$，

将 ${\text{lat}}_{\text{1}}$ 和 ${\text{lon}}_{\text{1}}$ 转化为弧度，

${\text{lon}}_{\text{1}}={\text{lon}}_{\text{1}}\pi /\text{180}$

${\text{lat}}_{\text{1}}={\text{lat}}_{\text{1}}\pi /\text{180}$.

将 ${\text{lon}}_{\text{1}}$ 和 ${\text{lat}}_{\text{1}}$ 转化到笛卡尔坐标系，

$\begin{array}{l}{x}_1=\text{cos}\left({\text{lat}}_{\text{1}}\right)\text{*cos}\left({\text{lon}}_{\text{1}}\right)\\ y_1=\text{cos}\left({\text{lat}}_{\text{1}}\right)\text{*sin}\left({\text{lon}}_{\text{1}}\right)\\ z_1=\text{sin}\left({\text{lat}}_{\text{1}}\right),\end{array}$

对上述所有节点做1-2操作。

计算笛卡尔坐标系下的x，y，z坐标，

$\begin{array}{l}x=\left(x_1+x_2+\cdots +x_n\right)/n\\ y=\left(y_1+y_2+\cdots +y_n\right)/n\\ z=\left(z_1+z_2+\cdots +z_n\right)/n,\end{array}$

将笛卡尔系坐标(x,y,z)转化，

$\text{lon}={\text{arctan}}^{\text{2}}\left(y,x\right)$

$\text{hyp}=\sqrt{x^2+y^2}$

$\text{lat}={\text{arctan}}^{\text{2}}\left(z\text{,hyp}\right)$.

将经纬度从弧度换算成角度，

$\text{lon=lon*}\text{180}/\pi$

$\text{lat=lat*}\text{180}/\pi$.

设经过计算得到中心点为M $\left({\text{lon}}_m{\text{,lat}}_m\right)$ ；设经过摧毁的后，原网络被分割成了k个连通分量，在每个连通分量重选取距离M最近的点将其连线，重新生成一个完全连通的网络 [7]。

根据两点球面距离公式，对于 $\left({\text{lon}}_x{\text{,lat}}_x\right)\left({\text{lon}}_y{\text{,lat}}_y\right)$ 其球面劣弧距离，

$L=2R\times \arcsin \left(\sqrt{{\sin }^2\left(\frac{{\text{lat}}_x-{\text{lat}}_y}{2}\right)+\text{con}\left({\text{lat}}_x\right)+\text{con}\left({\text{lat}}_y\right)\times {\sin }^2\left(\frac{{\text{lon}}_x-{\text{lon}}_y}{2}\right)}\right)$.

对于每一个因为节点被摧毁而断开形成的连通分量(简称为C)，其中的节点表示为 $V_1,V_2,\cdots ,V_n$。在C中，对任意的 $V_i$ 与M相连，选取 $\arg \min L\left(V_i,M\right)$，如图5所示。

Figure 5. Five city connectivity map

图5. 五市连通图

选取出的每个连通分量的城市分别为，襄樊，合肥，景德镇，长沙，常德，将上述五个城市与备用节点相连，即为连接方案。战备节点的坐标为(113.9505006856059, 30.579120212841232)，对于衡量网络连通性能的指标 [8]，引入了连通度 $H\left(G\right)$ 这一概念。

对于一个无向图G，其中有n个连通分量，用 $C_i$ 来表示， $i\in \left(1,n\right)$ ； $m\left(C_i\right)$ 表示 $C_i$ 这一连通分量的阶数，也就是节点数； $m\left(G\right)$ 表示总节点数。

$H\left(G\right)=\frac{{\displaystyle {\sum }_{i=1}^{n}m{\left(C_i\right)}^2}+n-1}{m{\left(G\right)}^2}$

当毁坏城市数为0时，连通分量个数为1，也就是最小生成树构造的连通图， $H\left(G\right)=1$，连通度这一概念，会作为下个模型中AHP层次分析法的一个衡量准则。

2.4. 网络增强方案模型优化比较

70年代初期，美国运筹学家T.LSaaty教授提出层次分析法，它是对一些比较复杂、比较模糊的问题作出决策的一种方法，它可以将复杂的评价对象用一个有序的递阶层次结构整体表现出来。其步骤大致上可以分为四步：建立递阶层次结构模型；构造比较判别矩阵；层次单排序及一致性检验；层次总排序及一致性检验。

2.4.1. 递阶层次结构的建立

应用层次分析法解决问题时，首先应把问题条理化、层次化，构造出一个层次清晰的结构模型。层次结构一般分为目标层、准则层和方案层：目标层是分析问题的预定目标或理想结果，这一层只有一个元素；准则层包含了实现目标所涉及的中间环节，它可以有若干个层次组成；方案层包括了为实现目标可供选择的各种措施，决策方案等。

采取以下5种方案。

A：最小生成树基础上，添加最近2个点连线，如图6所示；

B：最小生成树基础上添加最近3个点连线，如图7所示；

C：最小生成树基础上添加重要城市最近2个点连线 非重要城市1个点连线，如图8所示；

D：最小生成树基础上添加重要城市最近3个点连线，非重要城市2个点连线，如图9所示；

E：最小生成树基础上添加重要城市最近4个点连线，非重要城市2个点连线，如图10所示。

Figure 6. Programme A

图6. 方案A

Figure 7. Programme B

图7. 方案B

Figure 8. Programme C

图8. 方案C

Figure 9. Programme D

图9. 方案D

Figure 10. Programme E

图10. 方案E

Figure 11. Three criteria

图11. 三个准则层

如图11所示：

准则一：经济性，即路线总长度，总长度越短，花费越少，越低越好；

准则二：连通度，主要计算方法为，使用python随机进行1000次破坏，求 的平均数；

准则三：重要城市，采用的标准为重要城市的连接度数。

2.4.2. 比较判别矩阵的构造

在现实中，当对一个问题的影响因素较多时，直接比较各因素对问题的影响程度往往比较困难的，常常会因顾此失彼而做出错误的判断，通过各因素两两进行对比便容易的多。两两对比的具体方法为：用 $a_{ij}$ 来表示层次中第i个因素对第j个因素的相对重要性， $a_{ij}$ 的取值为正整数1~9及其倒数。

2.4.3. 层次单排序及其一致性检验

对应于判断矩阵 [9] 最大特征根 ${\lambda }_{\max }$ 的特征向量，经归一化(使向量中各元素之和为1)后记为W。W的元素为同一层次元素对于上一层因素某因素相对重要性的排序权值，这一过程称为层次单排序。

定义一致性指标：

$\text{CI}=\frac{\lambda -n}{n-1}$

CI = 0有完全的一致性；CI接近于0，有满意的一致性；CI越大，不一致越严重。

为了衡量CI的大小，引入随机一致性指标RI，如表1所示：

Table 1. Random consistency index

表1. 随机一致性指标

定义一致性比率：

$\text{CR}=\frac{\text{CI}}{\text{RI}}$

一般认为一致性比率 $\text{CR}<0.\text{1}$ 时，认为A的不一致程度在容许范围之内，有满意的一致性，通过一致性检验。可用其归一化特征向量作为权向量，否则要重新构造成对比较矩阵A，对 $a_{ij}$ 加以调整。

构造准则层对目标的成对比较阵：

$A=\begin{array}{ccc}1& 1/2& 1\\ 2& 1& 1\\ 2& 1& 1\end{array}$

$权向量w=\begin{array}{ccc}0.2& 0.4& 0.4\end{array}$.

其中，CR = CI = 0，符合一致性。

2.4.4. 层次总排序及一致性检验

层次单排序 [10] 得到的是一组元素对其上一层中对应元素的权重向量，最终要得到层次总排序，总排序权重要将层次单排序的权重进行合成。设准则层对目标层的权重为 $W_j$，方案层对准则层的单层次排序权重为 $W_{ij}$，则方案层对目标层的总目标的排序权重为：

$W_i={\displaystyle \underset{j=1}{\overset{m}{\sum }}{W}_{ij}\times W_j},i=1,2,\cdots ,n$

根据下面通信线路总长度的表，如图12所示，构建对于准则一的矩阵

$B1=\left[\begin{array}{ccccc}1& 6/3.8& 2.5/3.8& 3.9/3.8& 4.2/3.8\\ 3.8/6& 1& 2.5/6& 3.9/6& 4.2/6\\ 3.8/2.5& 6/2.5& 1& 3.9/2.5& 4.2/2.5\\ 3.8/3.9& 6/3.9& 2.5/3.9& 1& 4.2/3.9\\ 3.8/4.2& 6/4.2& 2.5/4.2& 3.9/4.2& 1\end{array}\right]$

$W1=\left[\begin{array}{ccccc}0.1987& 0.1258& 0.3020& 0.1936& 0.1798\end{array}\right]$

CR = 0，一致性可以接受。

Figure 12. Table of total length of signal line

图12. 通信线路总长度的表

根据下面平均连通度，如图13所示，选取破坏城市数为14作为基准，构建对于准则二的矩阵：

$B2=\left[\begin{array}{ccccc}1& 40/74& 40/21& 40/45& 40/49\\ 74/40& 1& 74/21& 74/45& 74/49\\ 21/40& 21/74& 1& 21/45& 21/49\\ 45/40& 45/74& 45/21& 1& 45/49\\ 49/40& 49/74& 49/21& 49/45& 1\end{array}\right]$

$W2=\left[\begin{array}{ccccc}0.1747& 0.3231& 0.0917& 0.1965& 0.2140\end{array}\right]$

CR = 0一致性可以接受。

Figure 13. Average connectivity

图13. 平均连通度

最后，根据重要城市连接数的平方构建对于准则三的矩阵，重要城市连接数分别为 $\text{494916}$，

$B3=\left[\begin{array}{ccccc}1& 4/9& 1& 4/9& 4/16\\ 9/4& 1& 9/4& 74/45& 9/16\\ 1& 4/9& 1& 4/9& 4/16\\ 9/4& 1& 9/4& 1& 9/16\\ 16/4& 16/9& 16/4& 16/9& 1\end{array}\right]$

$W3=\left[\begin{array}{ccccc}0.0952& 0.2143& 0.0952& 0.2143& 0.3810\end{array}\right]$

CR = 0一致性可以接受。

方案n的最终结果 $Sn=A[1]\times B1[n]+A[2]\times B2[n]+A[3]\times B3[n]$，

最终结果为 $S=\left[\begin{array}{ccccc}0.1477& 0.24012& 0.13516& 0.20304& 0.27396\end{array}\right]$。

方案E的权重最高，即在考虑到经济性，连通度，重要城市这三种因素时，方案E的总体效果最好。

方案E在最小生成树基础上添加重要城市最近4个点连线，非重要城市2个点连线，如图14所示。

Figure 14. Scheme E improvement chart

图14. 方案E完善图

随机攻击10%的城市(14个)后的结果之一，如图15所示。

Figure 15. Random attack on 10% city connection graph

图15. 随机攻击10%的城市连接图

随机摧毁1000次的连通度平均值为0.48268774908131074。

3. 结论和分析

模型的优点，兼备经济性，连通性于一身，抗攻击性强，而且对重要城市做了加强。通过模拟随机摧毁，以及连通度这一衡量标准，我们得以精确的衡量出模型在面对攻击时的网络连通性能。模型的缺点，过于抽象，没有对具体城市的战略意义进行具体分析，仅仅是将城市抽象为节点，并加上重要城市的判别。在真正的推广中，必然要考虑真实城市的战略地位这一因素。在此类网络图中，单连接的连通性能很差，一旦遭受攻击，立刻会导致多的连通分量出现，大大降低连通度，而一旦构建起最邻n点连接的网络图后，抗攻击性大大提高。而对重要城市的加强，也在此模型中大大提高了权重。

基金项目

海军大连舰艇学院科研发展基金资助(2021)。