通信网络的设计问题2

12014高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：A3我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：重庆邮电大学参赛队员(打印并签名)：1.王桃2.杨太海3.江海欢指导教师或指导教师组负责人(打印并签名)：鲜思东日期：2014年9月2日2高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：1通信网络的设计问题摘要计算机网络技术在各个领域的应用范围已经逐步广泛起来，其发展也在不断的推动人类社会逐渐走向信息时代。网络技术的发展不仅促进了社会生产力的提高，也为人们的生活带来了很大的方便。然而，与此同时也存在着很多不足，诸如安全隐患、信息漏洞等，这些对于人们的工作和生活造成了很大的影响。对于一个系统，可靠性是其重要的整体指标，通信网络亦不例外。通信网络的可靠性不仅与通信设备、链路有关，而且还与网络结构有关。针对问题一，是最小费用问题，根据附件用MATLAB【1】编程计算出80个节点任意两点间铺设道路的费用，然后用Prim算法求出最小生成树，即铺设的路径，再算出总的费用为29478百元。分析所建网络结构的可靠性，要求出网络中所有节点正常工作的概率以及网络链路连通的概率，从而得到整个网络的可靠度，本文算出该网络的可靠性较低。针对问题二，在第一问的基础上，要使任意一个节点出现故障时，其它节点间的通信畅通率达到90%，即考虑至少有72个点仍然保持连通，本文采用MATLAB编程求出不符合要求的节点，并找出关键的3个节点，并从其引起故障的失效节点中找出使之连通后保证仍然90%的节点畅通，且使铺设的费用最少的点。本文求得需要连通的节点为61,68与38,35，最少费用为30542百元。针对问题三，在第一问的基础上，要使任意一条链路发生故障时，其它节点间的通信畅通率仍然达到90%，即至少有72个节点保持连通，通过MATLAB编程求出不符合条件的链路，可以将失效的节点与其它正常工作的相连接，保证至少有72个节点还正常工作，用MATLAB编程求出需要连接的节点以及最少的费用。本文求得需要连通的节点为61，68与46,71，所需的总费用为30534百元。针对问题四，我们根据题目要求，我们首先将此问简单话，做出合理假设，建立最优化方案模型，通过分析问题一、问题二、问题三的求解即铺设方案情况情况，利用目标值W函数，及相关约束条件，找出前三问只有问题二的铺设方案满足条件，得出W=2.189×10-5，然后在问题二的铺设方案下进行改进，查找最佳方案，最终通过分析比较，得出问题二的铺设方案为最佳铺设方案。关键词：可靠性分析MATLAB编程畅通率最优化方案模型1一、问题重述计算机网络技术在各个领域的应用范围已经逐步广泛起来，其发展也在不断的推动人类社会逐渐走向信息时代。网络技术的发展不仅促进了社会生产力的提高，也为人们的生活带来了很大的方便。然而，与此同时也存在着很多不足，诸如安全隐患、信息漏洞等，这些对于人们的工作和生活造成了很大的影响。对于一个系统，可靠性是其重要的整体指标，通信网络亦不例外。通信网络的可靠性不仅与通信设备、链路有关，而且还与网络结构有关。某通信公司拟建一个具有80个结点的通信网络，需要在这些结点之间铺设线路，进行数据传输。结点之间的距离和铺设线路的单位费用见附件1，请对以下问题进行研究：问题1．要使得通信网络的总铺设费用最省，请建立问题的数学模型，设计求解算法，给出铺设方案，并讨论方案的可靠性；问题2．考虑到通信网络结点的可靠性，若要求任意一个结点出现故障时，其它结点间仍然能够保持通信畅通的可能性都达到90%，请建立问题的数学模型，设计求解算法，并给出使总铺设费用最少的铺设方案；问题3：考虑到通信网络链路的可靠性，若要求任意一条链路被破坏时，能够保持通信畅通的结点都能够达到90%，请建立问题的数学模型，设计求解算法，并给出使总铺设费用最少的铺设方案；问题3：综合考虑网络的可靠性以及铺设费用，试确定合理的铺设方案。二、模型假设1.假设每个节点故障率为10-5，每条链路的故障率为10-7。【2】2.假设两个节点之间的费用仅由单位费用和距离决定。3.假设整个网络的连通情况仅仅只受结点与链路影响。4.假设仅仅只考虑一个结点发生故障或者一条链路被破坏，不考虑其他情况。三、符号说明1每个节点的故障率2每条链路的故障率t网络结构运行的时间NODER网络中所有节点正常工作的概率LINKR网络链路连通的概率NETR整个网络的可靠度ki第i素回路对应的生成树数目W方案目标值2R网络可靠度P方案费用四、问题分析4.1问题一的分析对于问题一，题目要求通信网络的总铺设费用最省，就要使80个节点的加权总路径最短，先根据附件计算出80个节点任意两点间铺设道路的费用，然后用Prim算法求出最小生成树。要分析所建网络结构的可靠性，要求出网络中所有节点正常工作的概率以及网络链路连通的概率。4.2问题二的分析对于问题二，在问题一的最小生成树基础上【3】，要使任意一个结点出现故障时，其它结点间仍然能够保持通信畅通的可能性都达到90%，即80个点中任意一个节点出现故障时，至少有72个点仍然连通，可以将失效的节点与其它正常工作的节点相连接，用MATLAB编程算出需要连接的节点最少的费用。4.3问题三的分析与第二问相似，在第一问的最小生成树基础上，要使任意一条链路出现故障时，其它链路仍然能否保持通信畅通的可能性达到90%，即至少有72个节点连通，可以将失效的节点与其它正常工作的相连接，保证至少有72个节点还正常工作，用MATLAB编程求出需要连接的节点以及最少的费用。4.4问题四的分析针对问题四，我们建立最优化方案模型，给出相应的约束条件，在问题一、问题二、问题三的基础上进行求解，得出最优铺设方案。五、模型的建立与求解5.1问题一的模型及求解5.1.1最小费用要使得通信网络的总铺设费用最少，首先通过附件中任意两个节点之间距离以及节点间单位铺设费用，用MATLAB编程（附录1）计算出任意两节点之间铺设线路的总费用(附录1).用prim算法【4】（附录2）求出80个节点的最小生成树如下34根据最小生成树，算出的总费用为29478百元。5.1.2可靠性分析通信网络的可靠性是指在规定条件下、规定时间内，全网保持连通的概率【1】。网络的可靠度就是在规定条件下、规定时间内,全网保持连通的概率。素回路：任意两个节点有一条链路当且仅当它们是相邻节点的回路，(N,M)网络有M-N+1个素回路【1】。根据定义,通信网络可靠性的评估应从分析网络是否连通入手，设一个网络结构由N个结点，M条链路构成，用G（N,M）表示。设kj是(N,M)网络中(N,N+k-1)连通子网的数目。设每个节点的故障率为1,每条链路的故障率为2,则节点和链路的可靠度分别为tner1,tler2网络中所有节点正常工作的概率RNODE=rnN=tNe1,网络链路连通的概率：1)1(10)1(22jNMttjNNMjjLINKeekR;整个网络的可靠度：RNET=RNODERLINK;根据我们的求解方案，生成的网络结构为（80,79）的最小生成树网络，明显可以得到，该网络中通路为1，素回路为0，因此，我们可以算出假定在100小时、500小时内整个网络的可靠度如下：500小时内网络的可靠度由上表可知，通信网络运行100个小时时，网络的可靠性为92%，随着时间的增加，可靠性降低，网络结构运行500小时时，可靠性降低至67%，可以看出，该系统的可靠性较低。5.2问题二的模型及求解根据题目要求，在任意一个节点出现故障时其它节点间仍然能够保持通信畅通的可能性都达到90%时，就是在任何的一个节点发生故障时，要保证至少有72个节点仍然连通，用MATLAB编程（附录3）找出第一问所构建网络中不符合要求的点，如下图所示t（小时）RNODERLINKRNET1000.92310.99920.92242000.85210.99840.85083000.78660.99760.78474000.72610.99680.72385000.67030.99610.667756标有红色括号的即为不符合要求的点，从图中可以看出点70，,51和77为三个最关键的点。将点70连接的点集[13426615032]记为区域a，将点51连接的点集[303138594486058]记为区域b，将点77连接的点集[7111727417104415]记为区域c，将点集[1342661507032666736814]记为区域d，将点集[5112304668313833655944173486058]记为区域e，将点集[772371664751172745717104415]记为区域f。为了满足90%的可靠性，需要将a,b,c三个区域连通。为了使总的铺设费用最少，要使三个区域之间联通的路径与铺设单位距离的费用的乘积最少，用MATLAB编程（附录4）可以得到。所得结果如下表所示：连通的点所需的费用（百元）连通的区域161,68528a238,15536bc310,2470c461,602091a,b51,71680a,c因为要将a,b,c三个区域连通，所选的线路必须包含a,b,c三个区域。根据上表，一共有5种连接方式，如下：连通线路所需费用（百元）1+210642+426272+5131673+425614+52871要使总的费用最少所以选出最优的路径为1+2，即将点61，68连接，38,35连接。所以铺设线路的最佳方案为在第一问的基础上，将点61与68连接，点38与35连接（如下图所示），计算出总的费用为29478+1064=30542百元。8可靠性分析：考虑问题二的可靠性，利用问题一的可靠性模型可以得到：首先，在我们增加两条边之后，可以得到一个网络结构G（80,82）；因此，我们可以分析该网络结构得到，k0=272,k1=33,k2=1;考虑到精确性，我们只分析了在500小时的时间内的可信度，首先，RNODE=tNe1=0.6703；9976.0)1(1)1(1022jNMttjNNMjjLINKeekR；所以：ＲNET=RNODE*RLINK=0.6687,因此对比问题一的可靠度，我们可以知道可靠度提高，因此该网络结构的可靠性比问题一的可靠性要好。5.3问题三的模型及求解与第二问相似，根据题目要求，在任意一个链路出现故障时其它节点间仍然能够保持通信畅通的可能性都达到90%时，就是在任何的一个链路发生故障时，要保证不会因此超过8个点出现故障，用MATLAB编程（附录5）找出第一问所构建网络中不符合要求的链路，如下图所示910标注红线的地方记为不符合要求的链路，将点集[1342661507032666736814]之间连接的区域记为a，将点集[5112304668313833655944173486058]之间连接的区域记为b，将点集[772371664751172745717104415]之间连接的区域记为c。根据题目要求任意一条链路被破坏时，能够保持通信畅通的结点都能够达到90%，同样需要将a,b,c三区域连通。同时为了满足所铺设的费用最少的条件，通过MATLAB编程（附录6）可以求出，如下表