The Optimization Of Network Reliability And Its Application Research

In this paper, we consider the optimal problem of network reliability and its application in wireless sensor networks. The dissertation is divided into four parts:In Chapter 1, we first introduce elementary knowledge about network reliability and list the main network structures and three models of reliability. Second we review the exact and approximation reliability algorithms. In the end we introduce the new results of uniformly optimal and least reliable graph.In Chapter 2, we mainly prove several problems of uniformly least reliable graph. The uniformly least reliable graph is an important research topic of network reliability. Under the reliability of edge failure, we consider the definitions of all-terminal reliability and uniformly least reliable graph and prove that any graph G is the uniformly least reliable graph in the classΩ(n, e) as e≤n-1. LetΩ1(n, e) denote the class in which each graph contains a triangle, while e=n. LetΩ2(n, e) be the class in which each graph has a cycle whose length is more then 3, while e=n. That is,Ω(n, e)=Ω1(n, e)∪Ω2(n, e), andΩ1(n, e)∩Ω2(n, e)=φ. By considering the characters of the classΩ1(n, e) andΩ2(n, e), we prove that graph G∈Ω1(n, e) is the uniformly least reliable graph in the classΩ(n, e), where e=n. LetΩ3(n, e) denote the class in which each graph contains a kite, where e=n+1. By the factoring theorem, we obtain a new graph M which has two topology structures. Let S,(M) and Si(G) be the coefficient of reliability for graph M and G, respectively. We compare the coefficient Si(M) and Si(G) and prove that graph G∈Ω3(n, e) is the uniformly least reliable graph in the classΩ(n, e), where e=n+1. LetΩ4(n, e) denote the class in which each graph contains a complete graph K4, where e=n+2. By the factoring theorem, we get a new graph M which has eight topology structures. We evaluate the lower bound of the Si(M) and prove that graph G∈Ω4(n, e) is the uniformly least reliable graph in the classΩ(n, e), where e=n+2.In Chapter 3, we propose a new reliability definition named residual edge connectedness network reliability. Under the edge failure model, all-terminal reliability of disconnected network is zero. And all-terminal reliability of different structure trees is equal in the same class. In order to study the difference of disconnected network reliability and the variety of reliability of different structure trees, we give the definition of residual edge connectedness network reliability. Based on the proposed definition, we can measure the reliability of disconnected network and different trees in the same class. This could help us to select the better structure for communication. And we prove two necessary conditions of the uniformly optimal graph and"partial-star"is the uniformly optimal graph, while e≤n-1 under the new network model.In Chapter 4, we introduce the development of wireless sensor network (WSN) and its application and present a reliability measure of reparability. In WSN, the disconnected network often appears and the reliability of the repaired network is different. Considering this case, we give a repairability definition based on reliability. From the experiment, we obtain that the reliability of edge can affect the repairability of network. While the reliability of edge increases, the repairability of the repaired network increases. If the value of edge reliability more than a fixed value, the repairability decreases. At a fixed middle value of edge reliability, the repairability has the most value.