通讯网络连接的最短路径问题探究

Research on the Shortest Path of Communication Network Connection

摘要: 本文研究了旅行商模型(TSP)的蚁群法算法和树模型的最小生成树法，构建了139个节点的通讯网络线路，结果表明采用TSP模型的蚁群法得到单连通网络线路总长度在320附近，低于平均值；而树模型的最小生成树法得到了更佳优化的具有唯一性的网络连接线路，其总路径最小值为254。从网络连接图中明显的看出后者在连通性和抗摧毁性上明显的优于前者。

Abstract: In this paper, the Ant Clony Optimization of the Travelling Salesman Problem (TSP) and the Minimum Spanning Tree of the tree model was studied. Communication network lines with 139 nodes are constructed. The results show that the total length of simply connected network lines obtained by Ant Clony Optimization is around 320, which is lower than the average. The Minimum Spanning Tree has a better simply connected network lines, and its total path minimum value is 254. It is clear from the network connection diagram that the latter is significantly superior to the former in terms of connectivity and destructibility.

1. 引言

有线通信网络作为保障军队指挥的基本手段，是衡量军队战斗力的重要要素之一，在军事战争中发挥着重要作用。为满足军事斗争战备需要，现需要构建包括139个大中型城市作为节点的有线通信网络，在每个城市内设一架专用网络连接设备，并且假设通信线路以两城市间的最短距离方式连接，即地球上过这两个城市节点所在位置大圆的劣弧长。本文讨论了使139个城市节点的通信线路总长度最短的网络连接的两种方案，通过对两种方案求解出的最短路径进行评价和比较，得出最优连接方案。

2. 模型假设

为了使实际问题理想化，本文对问题中的诸多问题进行了假设。假设通信线路以两城市间的最短距离方式连接，即地球上过这两个城市节点所在位置大圆的劣弧长；假设不考虑地球的几何形状对两点间距离产生的影响；假设每个城市只能设立一个通讯网络节点；假设中国城市坐标抽象在一维平面中假设每一个城市都可以直达其他城市。

3. 数据预处理

文中139个大中型城市的经纬度，由于所涉及的地理区域的几何尺寸远远的小于地球半径，根据上述假设，利用微元分割，化曲为直，化曲面为平面的数学思想，从而忽略掉地球经度间隔随纬度的变化，直接采用经度和纬度作为横纵坐标，将地球曲面简化为平面。使用Origin 8.6画图软件，将所给的139个大中型城市的经纬度数据导入，以经度作为横坐标，纬度作为纵坐标，将所有城市以节点编号的形式刻画在一维坐标图中，如图1所示。

4. 模型建立与求解

4.1. TSP模型

一种解决解决通信线路总长度最短问题的方案是把该问题看作是图论中旅行商问题(即Travelling salesman problem，简称TSP模型)，也叫推销员问题，就是为一名旅行得商人设计一条最短的旅行路线，使得旅行商从某一个城市出发，经过每个城市恰好各一次，最后回到原来城市 [1] 。所以连接139个节点通信线路总长度最短的网络连接方案也可抽象为旅行商问题，假设每一个城市都可以直接到达其他的城市，把每个城市都用一个点表示，并将城市与城市之间的交通线路的长度用带权的边来表示，这样旅行商问题就可以用图论来建立相应的模型，也就是说，在一个赋权完全图中，只要能找出一个有最小权的哈密顿圈，这种圈就是最佳通讯网络的连接方案，也称为最优圈 [2] 。

然而旅行商模型并没有确定有效的算法，是图论中NPC问题(Non-deterministic polynomial complete problem) [2] [3] ，解决这一问题的算法很多，本文采用蚁群算法 [1] [4] [5] [6] ，建立模型求解线路总长度最短连接方案。

Figure 1. City coordinate map

图1. 城市坐标图

4.1.1. 蚁群算法求解TSP模型

蚁群算法是一种用来寻找最优化路径的概率型算法，1991年，Marco Dorigo在他的博士论文中提出的这个说法，其灵感主要来源于蚂蚁在寻觅食物时用来寻找路径的行为。它是一种信息正反馈的启发式全局优化算法 [1] [4] [5] [7] 。

设定一个城市节点只能与两个城市相连，以此假设该模型的连接方式达到最短，在程序上，首先将城市的坐标信息转换为城市间的距离矩阵，实现相关参数(如最大迭代次数、启发函数因子、信息素常数、信息素因子、信息素挥发因子等)的初始化，然后采用穷举法(即迭代法)列举出500种连接方案(即迭代500次)，计算以任意个城市为起点的时所经过的路径长度，并计算两个城市间的欧式距离，并对所有城市距离求和，记录当前迭代次数最优解，同时对路径上的信息素浓度进行更新。通过每种连接方式的比较，得出一个最优的连接方案，当然，在这个过程中，随着迭代次数的不同，列举产生的最短连接方式的距离会有些许差异，在本模型中，仅以500种连接方案为模型求解最佳连接方案。

根据蚁群算法得到从第i个城市到第j个城市的转移概率 [1] [6] ：

$p_{ij}^k=\{\begin{array}{l}\frac{\left({\tau }_{ij}^{\mu }/d_{ij}^{\gamma }\right)}{\left({\displaystyle {\sum }_{l=1,l\notin J}^n{\tau }_{ij}^{\mu }/d_{ij}^{\gamma }}\right)}j\notin J\\ 0j\in J\end{array}$ (1)

其中， $p_{ij}^k$ 表示种群中第k只蚂蚁从第i个城市移动到第j个城市的概率， ${\tau }_{ij}$ 表示第i个城市和第就个城市间的信息素强度； $d_{ij}$ 表示从第i个城市移动到第j个城市的距离； $\mu$ 表示信息素的相对重要性； $\gamma$ 表

示启发式信息的相对重要性；J为禁忌列表，即蚂蚁不能重复通过一个城市数量，即 $\Delta {\tau }_{ij}^k=\frac{Q}{L_k}$ ，第i个城

市和第j个城市第j个城市的信息素的更新法则为 ${\tau }_{ij}=\left(1-\rho \right){\tau }_{ij}+{\displaystyle {\sum }_{k=1}^m\Delta {\tau }_{ij}^k}$ ，式中 $\rho$ 表示信息素挥发率。

利用蚁群算法的原理，在MATLAB上建立模型，具体用于MATLAB流程图如图2所示。

Figure 2. Ant Clony Optimization flow chart

图2. 蚁群算法流程图

4.1.2. 蚁群算法运行结果

通过多次运行MATLAB程序，得到了不同输出结果。例如当起点为38号城市宜宾时，用蚁群算法计算结果：最短距离：321.8788

最短路径：38，54，58，68，71，70，77，81，83，82，87，96，99，105，115，106，104，102，113，108，114，111，97，85，94，75，76，74，67，61，65，55，51，43，34，30，28，20，15，21，17，14，10，6，5，4，9，8，1，2，7，3，11，16，25，32，19，12，45，41，90，103，118，132，136，125，121，109，110，92，84，101，86，79，72，95，98，124，127，138，137，130，134，131，128，129，133，135，139，122，120，107，117，119，123，126，112，116，100，93，91，80，89，88，78，69，66，60，52，46，37，35，42，47，40，50，59，56，48，36，33，22，24，57，62，64，73，63，53，49，39，29，18，13，23，27，31，44，26，38。

输出网络图如图3所示。

Figure 3. Network diagram of the shortest total hourly length starting from No. 38 City

图3. 起点为38号城市时总长最短网络图

当起点为70号城市西安时，用蚁群算法计算结果为：最短距离为：319.6066。

最短路径为：70，71，72，79，86，101，92，84，109，110，121，125，136，132，118，90，103，41，45，12，19，25，32，38，54，58，44，31，27，23，26，16，11，3，7，2，1，8，9，4，6，5，10，14，17，24，22，33，36，48，56，59，50，40，47，57，62，64，73，80，89，88，78，69，66，60，52，42，35，37，46，49，53，63，67，61，65，55，51，43，34，30，28，20，15，21，18，13，29，39，74，75，76，82，87，96，99，105，102，104，115，106，116，112，117，119，123，126，120，107，100，93，91，130，134，131，128，122，129，133，135，139，137，138，127，113，108，114，111，124，94，83，81，77，97，85，95，98，68，70。

输出网络图如图4所示：

Figure 4. Network diagram of the shortest total hourly length starting from No. 70 City

图4. 起点为70号城市时总长最短网络图

出现不同的结果是由于蚁群算法在每次运行时选择不同的起始点，运行结果不同，但是通过各代最短距离与平均距离对比，我们发现蚁群算法得到的最短距离均小于平均距离。图5给出了其中一次运行结果与平均距离的对比图。

Figure 5. Comparison of shortest distance and average distance

图5. 最短距离与平均距离对比

4.1.3. TSP模型的蚁群算法评价

蚁群算法的优点：这种计算转移概率搜索方式不容易陷入局部最优，易于寻找到全局最优解；由于蚁群算法采用了两点间的最短距离，从而保证总距离无限接近最短。

正因为蚁群算法无限的追求总距离最短从而导致了其网络的连通性最差。由图可以看出，蚁群算法得到的网络图是单连通的简单图，这种网络图在一个城市节点被摧毁之后，就使得整个网络处于瘫痪。这就是利用TSP问题的蚁群算法的最大弊端，这样的网络连接方式是不适合通讯网络的。鉴于以上缺点，尝试最小生成树法建立网路连接。

4.2. 树模型

上述通信线路总长度最短问题解决的另一个方案是，把通信网络看作“树”，即无圈的连通图，利用最小生成树法结合Dijkstra算法来求解通信线路总长度最短路径问题 [2] [3] [8] 。

4.2.1. 最小生成树法

原始森林中生长着的每一棵树都可以化为统一的图论模型来刻画，如果是一个无圈的连通图，则称G为树，记为 $G=\left(V,E\right)$ [2] [9] ，如图6所示。

树有以下显而易见的性质：树中任意两顶点间必有且仅有一条链；在树的两个不相邻的顶点间添加一条边，就得到一个圈；在树中去掉任何一条边，图就不连通；含有n个顶点的树有 $n-1$ 条边。

生成树：如果 $G=\left(V.E\right)$ 的生成图 $G^{\prime }=\left(V,E^{\prime }\right)$ 是树，则称 $G^{\prime }$ 是 $G$ 的一棵生成树。

具体计算时采用Dijkstra算法，Dijkstra算法的基本思路是：任选个顶点，将其标记与其它顶点作以区分，从该顶点出发的所有边中找一条权最小的边记录，再以该边的端点作以标记，作为下一个新的

Figure 6. Tree diagram

图6. 树示意图

端点；如此，每次将一条边和一个顶点作以标记，直到所有顶点都标记一边为止。最终的标记过的边和顶点便是最小生成树 [2] 。

首先输入加权连通图 $G$ 的带权邻接矩阵 $A_{n\times n}=\left(a\left(i,j\right)\right)$ ，然后建立初始候选边表 $B$ ， $T\leftarrow \phi$ ，在候选边表中选取最短边 $\left(u,v\right)$ ， $T\leftarrow T\cup \left(u,v\right)$ 。再调整候选边表 $B$ 。重复上述过程直到 $T$ 含有 $n-1$ 条边。

4.2.2. 最小生成树法求解

利用最小生成树的思想，采用MATLAB编写算法求解程序。首先利用程序生成初始的最小生成树，并生成初始的网络节点框架，在对节点进行编号后，用for循环语句计算所有节点之间的距离，并产生一个 $139\times 139$ 的矩阵，再以第139个城市为起点，从节点139开始找最小生成树，并找出除第一个点以外的所有点的权值。部分MATLAB程序如下：

for i=1:139

temp=['',int2str(i)];

text(xx(i),yy(i),temp)

end

hold on

A=zeros(139,139);

for i=1:139

for j=1:139

A(i,j)=sqrt((xx(i)-xx(j))^2+(yy(i)-yy(j))^2);

end

end

A(A==0)=inf;

result=[];

p=139;

tb=1:length(A)-1;

while length(result)~=length(A)-1

temp=A(p,tb);

temp=temp(:);

d=min(temp)%

[jb,kb]=find(A(p,tb)==d);

j=p(jb(1));

k=tb(kb(1));

result=[result,[j;k;d]];

p=[p,k];

tb(tb==k)=[];

end

Wt=sum(result(3,:));

disp(['最短架设电线总长度：', int2str(Wt)]);

for i=1:138

plot(xx(1,result(1:2,i)),yy(1,result(1:2,i)),'r');

end

text(0.35,0.1,['最小生成树的权为','',num2str(Wt)])

title('红色连线为最小生成树');

通过程序计算求得最小生成树的最小值为254，最佳连接方案如图7所示。

Figure 7. Shortest connection network diagram of 139 nodes

图7. 139个节点的最短连接网络图

4.2.3. 树模型的最小生成树法评价

最小生成树法得出的通信线路连接方案是无圈的连通网络，得到的总长度为254，远小于TSP模型的蚁群算法得到的结果。而且从连接的图像可以看出，最小生成树的连接方式较蚁群算法更具有网络的连通性，表现在若某个城市的节点遭受攻击，不至于导致所有的网络节点受到破坏和影响，并且使用该算法的得出的结果是一个定值，不会有由于迭代次数不同而造成的影响，因此树模型的最小生成树法能得到了较为好的网络连接方案。

5. 结束语

TSP模型的蚁群算法易于寻找到全局最优解，并保证了总距离无限接近最短，也正是如此导致了其网络的连通性最差，得到的网络图仅是单连通的简单图，使其抗摧毁性较差，这样的连接是不适合通讯网络的。树模型的最小生成树算法能构建更短的连接方案且有更好的网络连通性。基于上述分析论述，在通讯网络连接的实际应用中可选用树模型的最小生成树法求解的较佳的网络连接方案。

基金项目

武警工程大学基础前沿创新项目：WJY202301“BiFeO₃掺杂(Na_0.5K_0.5) NbO₃基无铅压电陶瓷的烧结工艺和极化工艺研究”。