Design Of Invulnerability Network Under Node And Link Failures

In modern society,the Internet is inseparable from daily work,?ife and study.The scale and complexity of the network is increasing as human population and data size increase.Failure of nodes or links in the network may lead to the paralysis of the entire network,causing significant social damage.As a result,the invulnerability analysis of network becomes critical.In this dissertation,we first introduce the research background and significance of invulnerability network,then summarize the invulnerability network research status at home and abroad,which can be concluded into two main directions:(1)invulnerability measurement of complex network;(2)network optimization design of invulnerability network.This dissertation was written in the second direction,when considering the failure of nodes and links,design a network with good invulnerability and transmission speed.Firstly,in order to ensure the speed of network transmission,this dissertation establishes Diameter Constrained Minimum Spanning Tree,which call DCMST for short,based on Minimum Cost Flow Model.Secondly,for the purpose of maintaining the normal operation of the network,under the failure of both nodes and links,this dissertation established ?-edge connected k-subgraph(generalization of k-MST problem and ?-edge connected problem)integer programming model,referred to(k,?)-subgraph model.According to the characteristics of the graph theory,a valid inequality constraint is established for the simplification of model.On the other hand,because of the unique characteristic of the(k,2)-subgraph model,such as bridgeless,so we establish the(k,2)-subgraph model with this characteristic.Then we use C++ call Cplex to solve these models,then compare different models with different inequalities for the solving time of the problem.Finally,the communication network is built to verify the invulnerability of network to the different edge connectivity.Thirdly,by considering DCMST problem and(k,?)-subgraph problem,we establish the Diameter Constrained ?-edge connected k-subgraph model,referred to DC(k,?)-subgraph model,then use integer programming to solve.After that,according to the parity of the Diameter D,use Hop constraint to establish models separately.Then we use C++ call Cplex to solve these models and compare the solving time of different models under different situations.At last,the communication network is built to verify the invulnerability of network to the different network diameters.