基于最小生成树模型的通信网络铺设方案构建

刘雅倩，王昌海，曾淑娴，朱家明

(安徽财经大学1．金融学院;2．统计与应用数学学院，安徽蚌埠233030)

基于最小生成树模型的通信网络铺设方案构建

刘雅倩1，王昌海2，曾淑娴2，朱家明2

(安徽财经大学1．金融学院;2．统计与应用数学学院，安徽蚌埠233030)

针对通信网络设计问题，通过有关数据分析，运用最小生成树模型并结合prim算法得出使通信网络的总铺设费用最省的铺设方案，分别考虑通信网络结点与链路的可靠性，对铺设方案进行进一步非线性规划，从而保证通信畅通的结点都能够达到90%。

通信网络;最小生成树;线性规划模型(LP);Netdraw

计算机网络技术在各个领域的应用范围已经逐步广泛起来，其发展也在不断地推动人类社会逐渐走向信息时代。与此同时也存在着很多不足，诸如安全隐患、信息漏洞等，这些对人们的工作和生活造成了很大的影响。对于一个系统，可靠性是其重要的整体指标，通信网络亦不例外。通信网络的可靠性不仅与通信设备、链路有关，而且还与网络结构有关。由于网络结构的复杂多变，通信网络的可靠性分析一直是个棘手的问题，本文试图以获取的数据为例进行研究，建立数学模型来制定一个具有较高可靠性的、成本较低的通信网络的铺设方案。(相关数据见2014年江西省研究生数学建模竞赛试题A题［1］)

1 铺设费用最省的通信网络铺设方案的制定

1．1研究思路。

制定一个铺设费用最省的通信网络铺设方案实际上是设计一条没有固定起点和终点，每个节点都能够实现信息通畅且使总费用最小的通信结构，属于典型的最小生成树［2］问题，应该铺设一条能够贯穿所有结点且不重复的线路，网络不存在自环现象，即不存在首尾相同的链路，并且网络中任两个节点之间最多只有一条边相连。

1．2数据处理。

首先对80个节点进行编号，80个节点分别从1编号至80，编的号码与数据中所给节点的顺序一一相对应。接着计算节点距离和节点间的单位铺设价格计算节点间铺设费用:

设G=100A．*B，根据节点间铺设费用采用prim算法构造最小生成树，［3］具体步骤如下。设置顶点集合V和边集E，它们的初始状态为空集;任意选取一个顶点A加入V中;重复以下过程直到V中已经包含原图的所有节点:选一条权值最小的边(U，V)，并使其满足U，V两节点只有一个在集合V中。将两个节点中不在V的点置入集合V中，并将边(U，V)加入边集E中;所得的子图G'=(V，E)即为所求的最小生成树。

1．3结果分析。

利用Matlab软件对模型进行求解得到图1，并利用Netdraw软件对模型进行求解得到图2。

虽然方案实现了费用最小化目标，但仍存在以下几点影响方案的可靠性:第一，某些重要节点没有多重保障，例如节点2、35、27等等，一旦这些节点发生故障，则会造成大面积的节点失去通信的情况，以节点22为例，一旦22节点发生故障，整个体系的瘫痪概率为66．4%;第二，铺设方案主要为链状和树状结构，结构单一，缺少适当的环形结构。环形结构是指首尾相接的线形结构，该结构为环中任意两个节点之间都提供了两个通路，环形结构本身就具有保护路由的功能，具有较好的可靠性。所以，该方案的可靠性不太理想，需要进一步完善。

图1 节点连接方案图

图2 铺设方案图

2 考虑通信网络结点可靠性的通信网络铺设方案的制定

2．1研究思路。

研究网络稳定性的重要方法之一是计算网络生成树的个数。如果删除某一节点造成网络中生成树的个数减少越多，该节点越重要。在研究1所得结果基础上，对节点进行分类，将与节点相连的链路的条数定义为度，则该结果的节点种类有1度、2度、3度、4度和5度五个种类。具体的节点分类情况见表1。

表1 节点分类表

对结点间能够保持通信畅通的可靠性都达到90%进行定义:如果一个节点i发生故障，其他节点间能够保持两两通信通畅的节点个数Ui与总的两两之间需要保持通信畅通的总个数C2n的比例大于等于90%，设定该比例为Ri，即为:Ri=Ui/C2n，i=1，2…80。这里将该比例定义为可靠性比率。一般而言，度数越高，影响越大，可靠性比率越小。对这五种种类的点遍历搜索，显然1度节点可以不考虑，其对整体的影响较小，一度节点总数为32个，则只需要计算48个点的可靠性比率。最后，对于那些可靠性比率小于90%的点予以重点考虑，重新设计网络结构，在保证费用最小的情况下使整体可靠性比率大于90%。将研究1所得的铺设方案图进行区域划分，分为M，N，P，Q四个区域，总体区域设为Ω，如图3所示。

图3 铺设方案按照节点可靠性区域划分图

如果要重新设计通信网络铺设结构，就应该重点考虑故障危险点的网络铺设，才能尽可能地实现整体的可靠性比率大于90%。

通信网络重建的基本思路:①拓扑结构主要有五种:总线型拓扑、星型拓扑、环型拓扑、树型拓扑和混合型拓扑，考虑到总线型拓扑、星型拓扑和树型拓扑三种拓扑结构会使总费用成本过高，而环型拓扑不仅能解决生成树通信通畅的问题，而且会在一定范围内保证费用较低。所以这里我们主要考虑环型拓扑和混合型拓扑结构;②研究1所得铺设方案里有三个主要的生成树分支，即为三个区域，如若提高整体的可靠性比率，则新设的链路端点至少有3个分别分布在三个区域，其他端点可以分布于整个区域的任何位置，并且新设链路必须能够覆盖整个区域，才能保证一旦生成树的分支发生故障，整体通信不受影响;③考虑到环型拓扑和混合型拓扑结构，则新设链路数应该小于等于3条方能实现通信通畅且费用尽可能小。则研究2主要解决的就是在保证费用最少的基础上，设计新设链路的节点(节点个数小于等于6个)的位置分布问题。

2．2研究方法。

计算48个点可靠性比率，提取可靠性比率小于90%的节点，即为61，70，62，47，2，5，35，27，42，53，22，45，76，77，71，16，52，18，30，51，12这些点一旦发生故障，那么通信畅通的可靠性比率低于90%，这里将这些节点定义为故障危险点。如果要重新设计通信网络铺设结构，就应该重点考虑故障危险点的网络铺设，才能尽可能地实现整体的可靠性比率大于90%。建立如下模型:

在实际问题求解时，对区域进行划分，如图4所示。

图4 铺设方案按照节点可靠性优化区域划分图

将26、1、34、61、50、32划为i区域，14、36、70、66、67、62、47、2、29、19、49、28、78、5、79、63、40、35、20、80、24、39、13、7、3、27、42、53、37、56为j区域，15、44、10、17、74、72、71、 11为m区域，77、23、75、64、6、57、76、45、54、22为n区域，30、38、31、59、60、48、4、58为q区域，剩下的划分为p区域。利用matlab进行编程算出最小费用网络铺设区域分布。

表2 连接方案表

并用Netdraw软件作图，求得最小费用为3054200元，具体的节点连接图如图5。

图5 考虑节点可靠性的铺设方案优化图

在通信网络结点的可靠性求解过程中，假设连接各区域的链路数小于或等于3条，现对连接各区域的链路数进行灵敏度分析，分析不同区域的链接链路数大小对总费用的影响。

分析可知，当连接各区域的链路数为4时，对应5个链端点，将各链路端点所在区域进行调整，分别计算不同调整类型所对应的费用，找到链路数为4时的最小费用，同理，当链路数为5，6，7，8，9时，用同样方法得到最小费用，将不同链路数对应的最小费用汇总，得表3。

表3 不同链路数对应的最小费用表

为了便于观察链路数与最小费用之间的关系，用excel画出折线图，得到图6。

图6 不同链路数对应的最小费用折线图

结合表3、图6的结果分析可知，连接各区域的链路数与最小费用呈线性关系，当连接各区域的链路数增加时，最小费用也随之增加;反之则减少。由此可知，当连接各区域的链路数为2时，就能够保持通信畅通的可能性都达到90%且达到最小费用，链路数再增加，只会增加费用，但是考虑实际情况，有时候可能会选择多种链路数的结合来实现费用与效率最优。

3 考虑通信网络链路可靠性的通信网络铺设方案的制定［4 ］

3．1研究思路。

假设通信网络的80个节点全部绝对可靠，网络结构的可靠性仅仅考虑每条链路的可靠度，并且失效链路互相独立，即为各条链路发生故障的情况互不影响。

首先，对通信畅通的结点都能够达到90%进行定义:即如果一条链路发生故障，其他节点间能够保持两两通信通畅的节点个数ui与总的两两之间需要保持通信畅通的总个数的比例大于等于90%，即为2…80。其次，在研究1基本网络铺设方案的基础上，采取同研究2一样的思路，即提取那些使可靠性小于90%的链路，在保证分支生成树尽可能不变的情况下，对这些链路进行重新设计。［5］

3．2研究方法。

如图7所示，对研究1所得基本网络铺设方案图进行区域划分。将32、50、61、34、1、26、67、66、70、36、3、14划分为P区域，62、69、47、2、29、19、49、28、5、35、20、80、24、39、79、63、40、27、3、7、13、42、53、37、56为Q区域，15、44、10、17、74、72、71、11、77、75、23、64、6、57为E区域，76、45、54、22为F区域，25、55、16、52、21、43、9、18为M区域，剩下部分是A区域。这五个区域为网络铺设方案图的生成树的主要分支部分。

剔除生成树的分支，重点考虑剩下节点之间的连接。因为链路可靠性分析和节点可靠性分析不同，在对链路分析中，如果尽可能提高整体可靠性，则应该使链路尽量成环或者聚集，即应该尽可能地实现星型拓扑和环型拓扑结构。并且在这两种拓扑结构中，一个中心节点的连接的总节点数应该小于等于8(因为总结点数为80，则80×10%=8)，才能尽可能实现可靠性大于90%。

根据分析，设度数超过1的节点所处的区域为D，建立

如下模型:［6］

其中第一个约束条件表示的是每个节点至少有一个链路与之相连，第二个约束条件表示的是生成树的所有分支的总节点数应该小于等于8个，从而能保证整体的可靠性大于90%。

3．3结果分析。

在对连接方案进行一一分析剔除之后，求得最少费用为3047600元，使用Netdraw软件进行绘图，得到图7。

图7 考虑链路可靠性的铺设方案优化图

4 总结

本文针对通信网络链路可靠性与结点可靠性的问题，通过有关数据分析，建立了相应模型。首先结合prim算法，结合最小生成树模型，设计出了铺设费用较少的铺设方案，接着对重点结点与链路予以重点考虑，建立非线性规划模型，对铺设方案进行区域划分，重新设计出保证链路可靠性大于90%的铺设方案优化图。本文对解决在尽量满足总铺设费用最小和方案可靠性最大的条件下，设计理想通信网络铺设方案问题提出了建议，对该问题的继续研究具有重要的参考价值。

［1］中国数学建模网［EB/OL］．http://www．shumo． com/home/html/2338．html，2014－11－10．

［2］陈国龙，郭文忠，涂雪珠，陈火旺求解多目标最小生成树问题的改进算法［J］．软件学报，2006(03)．

［3］杨成慧，殷红，孟建军，姜虎强．基于Prim算法的通信网络架设仿真研究与应用［J］．计算机仿真，2007(10)．

［4］刘晓娥，唐涛，万丽军，黄樟灿．基于链路可靠性的网络拓扑结构设计［J］．武汉理工大学学报(信息与管理工程版)，2002(3):18－24．

［5］孙慧丽．基于可靠性约束的网络拓扑多准则满意优化研究［D］．成都:西南交通大学，2007．

［6］姜启源，谢金星，叶俊．数学模型［M］．北京:高等教育出版社，2003．

The establishment of communication network laying scheme based on minimum spanning tree model

Liu Yaqian1，Wang Changhai2，Zeng Shuxian2，Zhu Jiaming2
(Anhui University of Finance and Economics 1．School of Finance;2．School of Statistics and Applied Math，Bengbu，Anhui 233030，China)

Aimed at the communication network designing，after analyzing relevant data，this paper use the minimum spanning tree model and combine the prim algorithm，which makes the cost as lower as possible．Considering the reliability of communication network nodes and links respectively，this paper uses nonlinear programming model to ensure the number of smooth nodes of this communication network can reach 90%．

communication network，minimum spanning tree，nonlinear programming model，netdraw

TP393．02

A

1672－6758(2015)05－0029－5

(责任编辑:郑英玲)

刘雅倩，学生，安徽财经大学金融学院。研究方向:国际金融。

王昌海，学生，安徽财经大学金融学院。研究方向:信息与计算科学。

曾淑娴，学生，安徽财经大学金融学院。研究方向:统计学。

朱家明，硕士，副教授，安徽财经大学数学建模实验室。研究方向:应用数学与数学建模。

国家自然科学基金(编号:11301001);安徽财经大学教研项目(编号:acjyzd201429)。

Class No．:TP393．02 Document Mark:A