通信网络的设计问题..docVIP

通信网络的设计问题 摘要 计算机网络技术推动了时代的发展，对于通信网络的研究于人们有着十分重要的意义。本文就某通信公司拟建一个具有80个结点的通信网络问题，建立了以下相关模型并给出具体的实施方案。 针对问题一，本文运用图与网络的知识，巧妙运用prim算法，将求解通信网络总的铺设费用最省的问题转化成求解连通图中的最小生成树的算法，运用matlab软件求解得出相应的结果： 关键词： 问题重述 1.1问题的背景 由于计算机通信网络广泛应用于事业单位、交通、通信、工业、国防等重要领域，所以对于通信网络的研究有着十分中重要的价值和意义。随着社会信息化的进一步加强，人们将越来越多地依赖于网络，要求方便、迅速、准确、安全的质量服务。那么对于这些结构复杂、功能强大的系统而言，若是出现故障则会造成不同程度的损失。 为了保障系统能够安全可靠的工作，理论研究需要集中于对网络的可靠性进行设计优化，并且兼顾优化系统的其他相关指标。所以在通信网络的构建中需要确定满足一定要求的构建方案。 1.2 问题的重述 某通信公司拟建一个具有80个结点的通信网络，需要在这些结点之间铺设线路，进行数据传输。结点之间的距离和铺设线路的单位费用见附件1，请对以下问题进行研究： 问题1．要使得通信网络的总铺设费用最省，请建立问题的数学模型，设计求解算法，给出铺设方案，并讨论方案的可靠性； 问题2．考虑到通信网络结点的可靠性，若要求任意一个结点出现故障时，其它结点间仍然能够保持通信畅通的可能性都达到90%，请建立问题的数学模型，设计求解算法，并给出使总铺设费用最少的铺设方案； 问题3：考虑到通信网络链路的可靠性，若要求任意一条链路被破坏时，能够保持通信畅通的结点都能够达到90%，请建立问题的数学模型，设计求解算法，并给出使总铺设费用最少的铺设方案； 问题4：综合考虑网络的可靠性以及铺设费用，试确定合理的铺设方案。 问题的分析 在通信网络的构建工程中需要使得公司的效益最大化，既需要极小化投资成本（通信网络的总铺设费用最省），又得极大化通信网络可靠度。本文衡量通信网络的可靠性指标就是连通性可靠度，即结点和链路保持畅通的可靠性。 本文就给定的一个具有80个结点的通信网络的拟建问题，需要我们做出以下研究：其一就是建立一个数学模型使得通信网络的总铺设费用最低，并且讨论建立的模型的可靠性；其二就是以网络可靠度为约束条件，使得总的铺设费用最低；最后需要探讨在一定的约束条件下，使得通信网络的可靠度极大化，总的铺设成本极小化的方案。 对于问题一就如何设计出一种通信网络的铺设线路，使得总的铺设费用最低问题的分析研究：由于通信网络是连通的，任意两点之间不多于一条直接相连的链路，连线问题的数学模型就是图论中在连通的赋权图上求权最小的生成树。结合运筹学中图与网络的知识，我们将问题转化成求解连通图当中最小生成树的模型来求解，本文运用prim算法求解最小的生成树，在这里我们给出prim算法的思想，即：任意时刻的中间结果都是一棵树，每次花费最小的代价，用一条边把不在树中的结点加进来。最后通过运用数学软件matlab来编程求解。 对于问题二 对于问题三 对于问题四 模型的基本假设 符号说明 模型的建立与求解 5.1问题一的模型建立与求解 运用Excel软件对第i个结点到第j个结点的铺设费用进行求解 由于附件中表一提供的是节点的距离表，表二提供的是节点间单位铺设费用表，我们利用Excel对节点间的铺设费用编辑计算公式进行求解。 求解的公式如下： 得出第i个结点到第j个结点的铺设费用（单位的换算已在表格中注明），铺设费用的汇总表格见附录一。 运用prim算法求解最小生成树 求解的算法步骤如下： 1） 2） 3） 4） 利用matlab编程输出结果 模型的检验 模型的评价与改进 参考文献 附录 附录一：第i个结点到第j个结点的铺设费用汇总表格 附录二：prim算法基于matlab编程的实现及输出结果 运用matlab软件编写的程序： function?A?=?fun(W)?[m,n]?=?size(W);?e?=?0;for?i?=?1?:?n????for?j?=?i?:?n????????if?W(i,?j)?~=?0????????????e?=?e?+?1;????????????E(e,?:)?=?[i,?j,?W(i,?j)];????????end????endend?%?sort?Ws?edge?by?weightfor?i?=?1?:?e?-?1????for?j?=?i?+?1?:?e????????if?E(i,?3)??E(j,?3)??