通信网络的设计问题

1通信网络的设计问题摘要本文针对通讯网络设计问题，使用图论中最小生成树法、节点排除法、网络故障分析法、对比分析法等方法，分别构建普里姆（prim）模型、节点故障模型、链路故障模型等模型，使用Matlab软件编辑算法，得到通讯网络总费用最省的铺设方案、可靠性条件下最省铺设方案以及综合条件下最省铺设方案。针对问题一要求，具体要求为使得通信网络的总铺设费用最省，首先使用了简化模型分析、反证法等方法，证明最小生成树算法能测算无向图遍历节点的最省方案，其次应用最小生成树法中的普里姆（prim）算法构造通讯网络总费用最省模型使用Matlab软件编程，得到最优铺设方案并作图。针对问题二要求任意一个结点出现故障时，其它结点间仍然能够保持通信畅通的可能性都达到90%时最省铺设方案设计问题，首先使用节点排除法进行处理，找到重要节点，利用树图将节点分类，再通过分类失效节点与有效节点连接达到通畅性要求，最后使用Matlab软件编程得出节点故障模型下最省铺设方案。针对问题三要求，任意一条链路被破坏时，能够保持通信畅通的结点都能够达到90%时最省铺设方案设计问题，首先找到重要链路，并分析链路影响的节点，用树图将节点分类，再通过分类失效节点与有效节点连接达到通畅性要求，最后使用Matlab软件编程得出链路故障模型下最省铺设方案。针对问题四要求，综合考虑网络的可靠性以及铺设费用确定合理的铺设方案问题，首先对比分析问题二与问题三的节点分类，得出节点稳定性比链路稳定性更重要的结论；再通过节点故障模型分别构造通信畅通的可能性都达到85%、90%、95%时所对应的最低铺设费用，使用Matlab软件编程，得到综合考虑下的铺设方案。本文后续对模型进行了误差分析。还基于对问题四中可靠性不仅仅与节点和链路的稳定性有关，还与节点的度有关，故引进节点的度对模型进行改进，并利用蚁群算法建立综合目标下的铺设模型；最后对模型做出了纵向的推广和横向的推广。关键词：网络通讯设计；最小生成树法；故障分析法；蚁群算法；matlab2§1问题的重述一、背景知识传统的通信网络是由传输、交换和终端三大部分组成。传输是传送信息的媒体，交换是各种终端交换信息的中介体，终端是指用户使用的话机、手机、传真机和计算机等。现代电信网是由专业机构以通信设备（硬件）和相关工作程序（软件）有机建立的通信系统，为个人、企事业单位和社会提供各类通信服务的总和。现在计算机网络技术在各个领域的应用范围已经逐步广泛起来，其发展也在不断的推动人类社会逐渐走向信息时代。网络技术的发展不仅促进了社会生产力的提高，也为人们的生活带来了很大的方便。然而，与此同时也存在着很多不足，诸如安全隐患、信息漏洞等，这些对于人们的工作和生活造成了很大的影响。我们在需要在研究通信网络铺设问题时的费用问题时，也要充分考虑其的可靠性。可靠性是其重要的整体指标，通信网络的可靠性不仅与通信设备、链路有关，而且还与网络结构有关。由于网络结构的复杂多变，通信网络的可靠性分析一直是个棘手的问题。二、相关资料1．80个节点之间的距离表和铺设线路的单位费用表（见附表1）；三、要解决的问题问题1．要使得通信网络的总铺设费用最省，请建立问题的数学模型，设计求解算法，给出铺设方案，并讨论方案的可靠性；问题2．考虑到通信网络结点的可靠性，若要求任意一个结点出现故障时，其它结点间仍然能够保持通信畅通的可能性都达到90%，请建立问题的数学模型，设计求解算法，并给出使总铺设费用最少的铺设方案；问题3：考虑到通信网络链路的可靠性，若要求任意一条链路被破坏时，能够保持通信畅通的结点都能够达到90%，请建立问题的数学模型，设计求解算法，并给出使总铺设费用最少的铺设方案；问题4：综合考虑网络的可靠性以及铺设费用，试确定合理的铺设方案。§2问题的分析一、问题的总分析对于问题的总分析，可以给出四个问题整体框架图，见图13图1四个问题的整体框架图二、对具体问题的分析1．对问题一的分析某通信公司拟建一个具有80个结点的通信网络，需要在这些结点之间铺设线路，进行数据传输。我们需要根据附件内容建立数学模型，并设计算法使得通信网络的总铺设费用最省，并证明可靠性。我们引入图论中普里姆算法（Prim算法），算法对通信网络的每条路的铺设费用总额进行模拟测算，形成铺设费用的最小生成树，并通过简化模型进行检验算法的可靠性。2．对问题二的分析问题要求这80个节点任意一个节点出现故障时，其它节点间仍然能够保持通信畅通的可能性都达到90%，在问题一所得出的最小生成树的的基础上，若其中只有一个重要节点发生故障时，会造成八个节点以上故障，那么通信畅通的可能性就不能达到90%，故通过节点删除法找到重要节点，再从重要节点引起故障的其他失效节点中找到一个节点与其他正常节点连通使得发生故障的节点数少于八个即可，并且改进方案所铺设的费用是最省的。3．对问题三的分析问题要求79个链路中任意一条链路被破坏时，能够保持通信畅通的节点都能够达到90%。同样在问题一所得出的最小生成树的的基础上，我们考虑到若其中只要有一个重要链路被破坏时，会造成八个节点以上故障，那么通信畅通的可能性就不能保证达到90%，所以，我们可以通过逐个分析每条链路，找到重要链路，一个链路被破坏会使最小生成树分割成两个部分，其中一部分则是失效的，然后再从重要链路被破坏而引起的其他失效节点中找到一个节点与其他正常节点连通使得发生故障的节点数少于或等于八个，我就能保证通信畅通的可能性达到90%，并且我们要找到的这个节点与其他正常4节点连通所铺设的费用是最省的。4．对问题四的分析问题要求是综合考虑网络的可靠性以及铺设，试确定合理的铺设方案。首先对比分析问题二与问题三的节点分类，发现问题三中节点的分类包含了问题二中节点的分类，若满足了了节点稳定性的要求，则一定能满足链路稳定性的要求，故得出节点稳定性比链路稳定性更重要的结论；再通过节点故障模型分别构造通信畅通的可能性都达到85%、90%、95%时所对应的最低铺设费用，使用Matlab软件编程，综合考虑稳定性和铺设费用得出铺设方案。§3模型的假设1．两个节点之间的费用仅由节点之间的距离和铺设线路的单位费用决定；2．各节点和各链条间发生故障是相互独立的，节点1发生故障不影响节点2发生故障；3．每个节点的重要性是相等的，不存在次级差别；4．任意两个节点之间可以进行连接，且一个节点可以连接的节点不受限制；5．网路的稳定性与节点所连的链路条数无关，即每个节点和链路出现故障的可能性是相等的；§4名词解释与符号说明一、名词解释1．最小生成树：一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个结点，并且有保持图连通的最少的边。2．普里姆算法（Prim算法）指可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。二、主要符号说明序号符号符号说明1V表示加权连通图的节点集合2E表示加权连通图的边集合3t表示V集合中的任意节点40V表示初始的节点集合5u表示集合0V中的元素6v表示V中的节点但不是0V中的节点7ijx表示一个0、1变量，0，1分别表示选中和未选中8ijw表示节点i到节点j铺设线路所花费的费用9Z表示所选的铺设方案所花费的总费用10e表示最小生成树的链路5§5模型的建立与求解一、问题一的分析与求解1．问题的分析问题要求根据附件内容建立数学模型，并设计算法使得通信网络的总铺设费用最省，并证明可靠性；我们引入图论中普里姆算法（Prim算法），算法对通信网络的每条路的铺设费用总额进行模拟测算，形成铺设费用的最小生成树，并通过简化模型进行检验算法的可靠性。本文中连通图的顶点为80个通讯网络的节点，所有边的权值为两节点之间的铺设通讯链路的总费用，通过普里姆算法可以得出联通所有顶点并且使总铺设费用最低的树图，即相对于问题一的最优铺设方案。2．问题的求解模型Ⅰ总铺设费用最省模型⑴模型的建立普里姆算法（Prim算法）的步骤：从单一点开始，普里姆算法按照以下步骤逐步扩大树中所含节点的数目，直到遍历连通图的所有节点。首先设加权连通图的节点集合为V，边集合为E，初始化}{0tV，其中t为集合V中的任意节点，其次在集合E中选取权数最小的边),(vu，其中u为集合0V中的元素，而v不是，如果存在权数一样的可任选其中之一，再次，将v加入到0V，重复第二第三步，直到VV0。引入一个变量ijx，0ijx时说明该路径未被选中，1则表示被选中)(Vcount为总结点数建立的数学模型如下0,11111)(1..minVjiijninjijninjijijVcountxnxtsxwZ算法流程图见图26图2问题一的算法流程图为了更好的表现算法内容，用以下简化模型来表示并验证：表1普里姆算法示例图①设置一个加权连通图，顶点集合为V，边集合为E。（d、、、、cbaS0为顶点，连线为边,边上数字为权值）7②选择顶点集合中任意顶点，此处选择0S为初始点。顶点a、b、c、d都有与0S直接相连的边，选取其中权重最小的点（图中为a）③下一个顶点为距离a或0S最近的顶点，a距离c为10，距d为6，距b为5；0S距c为10，距d为15，距b为15；所以最短的距离是a到b得距离为5，连接a与b④继续重复上面的步骤。可以发现距离a,b和0S最短的是b到c得距离为5，连接b和c。8⑤最后d与a,b,c,0S之中最短的距离为c到d的连线为6，故连接c到d,得出了最小生成树。轨迹为0S到a到b到c到d⑵模型可靠性的检验反证法：设生成的树为,假设存在'使得总花费)'(cos)(costt；则一定存在一个),(vu不属于'；将),(vu加入，而vu,在本被其他点连接，加入),(vu后会形成一个环；而),(vu一定小于环中某一边的权重，这与在生成树时每次都取权重最小值的步骤矛盾；故假设不成立，原模型成立。⑶模型的求解根据matlab运行结果见表1（程序见附录1），可以得到通信网络的总铺设费用1Z为2947800元。得到的最优铺设方案如图3。表1问题一结果图连接顺序12345678节点序号346170623647219连接顺序910111213141516节点序号5352737849713连接顺序1718192021222324节点序号4028425366672254连接顺序2526272829304647节点序号1652561851127417连接顺序4849505152535455节点序号10442367564821连接顺序5657585960616263节点序号1129201550327226连接顺序6465666768697071节点序号439637924396569连接顺序7273747576777879节点序号57374825411460809图3最优铺设方案图二、问题二的分析与求解1．对问题的分析在问题一所得出的最小生成树的的基础上，我们考虑到若其中只要有一个重要节点发生故障时，会造成八个节点以上故障，那么通信畅通的可能性就不能保证达到90%，所以，我们可以通过节点删除法找到重要节点，然后再从重要节点引起故障的其他失效节点中找到一个节点与其他正常节点连通使得发生故障的节点数少于八个，我们就能保证通信畅通的可能性达到90%，并且我们要找到的这个节点与其他正常节点连通所铺设的费用是最省的。可以给出具体的算法流程图，如图4，图4问题二的算法流程图2．对问题的求解10我们以节点22为中心节点，可以将最小生成树分成四个大部分：1A为节点22左边部分，2A为节点22右上方部分，3A为节点22右下方部分，4A即为剩下的部分，即4A={225654}。例如1A部分，当这部分有节点出现故障时，我们通过2A或3A的点与这个故障点引起的失效点之间用最省的方案再铺设一条线路后，保证任一点发生故障后也能使通信畅通的可能性达到90%。通过此方法，我们可以在1A部分找到重要节点70，2A部分找到重要节点51，3A部分找到重要节点77。找到重要节