通信网络的设计优化问题-研赛建模论文.docxVIP

2013高教社杯全国大学生数学建模竞赛

承诺书

我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参

赛规则》(以下简称为“竞赛章程和参赛规则”,可从全国大学生数学建模竞赛网站下载)。

我们完全明白，在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网

上咨询等)与队外的任何人(包括指导教师)··、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料(包括网上查到的资料),必须按照规定的参考文献的表述方式在正文

引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有

违反竞赛章程和参赛规则的行为，我们将受到严肃处理。

我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展

示(包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等)。

我们参赛选择的题号是(从A/B/C/D中选择一项填写):

我们的参赛报名号为(如果赛区设置报名号的话):

所属学校(·填写完整的全名):

参赛队员(打印并签名):1.

2.

3.

指导教师或指导教师组负责人(打印并签名):

(论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。)

日期：年月日

赛区评阅编号(由赛区组委会评阅前进行编号):

2013高教社杯全国大学生数学建模竞赛

编号专用页

赛区评阅编号(由赛区组委会评阅前进行编号):

赛区评阅记录(可供赛区评阅时使用):

评阅人

评分

备注

全国统一编号(由赛区组委会送交全国前编号):

全国评阅编号(由全国组委会评阅前进行编号):

摘要

本文主要就通信网络的铺设费用及可靠性进行研究和讨论。当今社会计算机网络技术的发展不仅促进了社会生产力的提高，也为人们的生活带来了很大的方便。然而通信网络也存在着很多不足，对于一个系统，可靠性是其重要的整体指标，通信网络的可靠性不仅与通信设备、链路有关，而且还与网络结构有关。因此研究通信网络的设计对我

们的生活有着重要的意义。

研究通信网络在不同目标下的铺设策略。为满足不同需求，建立网络终端之间的距离矩阵并将其转化为一个全连通无向赋权图。根据网络设计标准，以最低成本为唯一目标建立最短路径模型，利用Prim算法求解得到最小生成树。在最小生成树逻辑结构上建立稳定性度约束模型，给出满足度约束的铺设方案，利用MATLAB程序计算得出最小的铺

设费用为29478元。

考虑到通信网络的可靠性，那么对复杂网络中节点的重要度进行评估将是一项非常有意义的工作，本文首先用节点收缩法，即将于节点v;相连接的k;个节点都与节点v;融合，也就是用一个新的节点来代替k;+1个节点，构建邻接矩阵，通过算法对80个节点的重要度进行了评估，找出了17个重要度在90%的节点，其任一节点发生故障都将导致通信网络的连通效率低于90%,从中选取3个边界节点51,70,77作为依据将问题一求得的通

信网络图划分为pl,p2,p3,p4,四个区域，通过求前三个区域间的最短路径得出方案

(15-38,61-68)的铺设路线的最少费用为30542元。

对通信网络中链路重要性的评估是考虑链路稳定性的另一大方面，这里运用链路收缩法，构建关联矩阵，通过MATLAB程序计算各链路的重要度。分析得到重要的链路即重要的节点所在的链路，再以分界点(51,70,77)为分区依据，划分为我、W1,W2,W3,

W4,四个区域，进而求前三个区域的最短路径问题。

网络的可靠性及铺设的费用最优就要综合考虑节点和链路的最优问题，将第二问所

求方案转化为关联矩阵利用第三问解法，得出结果。

关键词：最小生成树prim算法节点收缩法链路收缩法邻接矩阵关联矩阵

目录

摘要 1

问题重述 3

一、问题分析 3

二、模型假设 4

三、符号说明 4

四、模型的建立与求解 5

5.1通信网络的总铺设费用 5

5.1.1构造最小生成树计算最小铺设费用 5

5.1.2最小铺设费用模型的结果 5

5.2通信网络节点可靠度评估及最小费用计算 6

5.2.1节点重要度评估：几种节点重