考虑节点和链接失效的抗毁性网络设计

发布时间：2018-07-06 08:06

本文选题：图论 + 边连通子图　；参考：《东华大学》2017年硕士论文

【摘要】：现代社会中,无论是日常的工作、生活、学习都离不开网络。而随着人口数量、信息量等的不断增大,网络的规模和复杂度也日益增加。网络中节点或链接的失效都有可能导致整个网络的瘫痪,对社会造成巨大的损失。因此,网络的抗毁性研究也变得至关重要。本文介绍了抗毁性网络的研究背景及意义,并综述了国内外对于抗毁性网络的研究现状,得出目前的两大主要研究方向:(1)复杂网络抗毁度的测量;(2)抗毁性能好的网络优化设计。本文从第二个方向出发,考虑节点和链接均失效的情况下,设计抗毁性能好,并且传输速率不受影响的网络。首先,为了保证网络的传输速率,本文建立了以最小成本流模型为基础,基于直径约束的最小生成树模型,简称为DCMST模型。其次,为了使得网络在节点和链接均失效的情况下,仍能保持网络的正常运行,本文建立了λ-边连通k节点-子图(k-MST问题和λ-边连通问题的一般化)的整数规划模型,简称为(k,λ)子图模型。根据图论的特性,建立有效的不等式约束,简化模型。另一方面,由于(k,2)子图模型具有独特的特征,如:无桥性,故根据特征构建(k,2)-子图的整数规划模型。采用C++调用Cplex求解模型,比较不同模型,以及不同模型加入不同不等式约束后的求解时间。最后构建通信网络,验证网络在不同边连通度下的抗毁能力。然后综合考虑DCMST问题和(k,λ)子图问题,建立基于直径约束的λ-边连通k节点-子图模型,简称为DC(k,λ)子图模型,运用整数规划求解。之后根据直径D的奇偶性,采用Hop约束,分别建立当D为偶数,以及当D为奇数时的模型。采用C++调用Cplex求解模型,比较不同模型在不同条件下的求解时间。最后构建通信网络,验证网络在不同直径下的抗毁能力。
[Abstract]:In modern society, whether daily work, life, learning are inseparable from the network. With the increase of population and information, the scale and complexity of network are increasing. The failure of nodes or links in the network may lead to the paralysis of the whole network, causing huge losses to the society. Therefore, the research of network survivability becomes very important. This paper introduces the research background and significance of the invulnerability network, and summarizes the research status of the invulnerable network at home and abroad, and concludes two main research directions: (1) the measurement of the survivability of the complex network; (2) the optimal design of the network with good survivability. From the second direction, considering the failure of both nodes and links, a network with good survivability and unaffected transmission rate is designed. Firstly, in order to guarantee the transmission rate of the network, a minimum spanning tree model based on the minimum cost flow model and diameter constraint is established in this paper, which is called DCMST model for short. Secondly, in order to keep the network running normally when the nodes and links fail, the integer programming model of 位 -edge connected k-node-subgraph (k-MST problem and 位 -edge connected problem) is established. It is referred to as (k, 位) subgraph model. According to the characteristics of graph theory, an effective inequality constraint is established and the model is simplified. On the other hand, due to the unique characteristics of the (kt2) subgraph model, for example, there is no bridge, the integer programming model of (kk2) -subgraph is constructed according to the feature. C call Cplex is used to solve the model, and the solving time of different models and different inequality constraints is compared. Finally, the communication network is constructed to verify the survivability of the network under different edge connectivity. Then considering the DCMST problem and (k, 位) subgraph problem, a 位 -edge-connected k-node-subgraph model based on diameter constraint is established, which is called DC (k, 位) subgraph model, and solved by integer programming. Then, according to the parity of diameter D, using the Hop constraint, the models are established when D is even and if D is odd. C call Cplex is used to solve the model, and the solving time of different models under different conditions is compared. Finally, the communication network is constructed to verify the survivability of the network under different diameters.
【学位授予单位】：东华大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TN915.02;O157.5

【参考文献】