Optimal capacity reliability design of networks based on genetic algorithm

1. Introduction

Networks are complex nonlinear systems with dynamical failure behavior. For networks with limited capacity, the network reliability is evaluated using capacity reliability [1]. The capacity reliability of networks [2] is the probability that the network can transmit a given amount of traffic in a given time. In the network design, as reliability, capacity and cost of components vary in different component types, how to select the proper network components, including nodes and links, becomes a problem. Optimal network capacity reliability design becomes a hot research topic. Its goal is to minimize the total cost which can satisfy the network capacity reliability requirement, or maximize the network capacity reliability under the total cost constraint [3].

Kumar and Ahuja [4] proposed an optimization method by minimizing both total cost and transmission delay of the communication network under the constraint of capacity reliability requirement. However, the decision variables of this problem are network topology, node locations and link paths, but not component type. Kumar et al. [5] optimized the throughput between source and destination under the constraint of total cost, and the links capacity and node storage size were determined. However, all link reliability is set as a fixed value in the network, which is not the real situation. With the objective of minimizing the cost, Goyal and Misra [6] presented an optimal network design problem by constraining on network capacity reliability, and proposed a general gradient method to solve this optimization problem. However, this optimization method can only be applied to component candidates whose reliability and capacity monotonically increase along with the cost. Moreover, the search space of the gradient method is so limited that it may easily fall into local optimal solution.

To solve the above problems, a new optimal network capacity reliability design method is proposed in this paper. Section 2 presents the optimization model, and Section 3 describes the optimization method based on the Genetic Algorithm (GA) method. In Section 4, the ARPA network is used as the case to verify the efficient of our proposed method compared with the general gradient one. Finally, Section 5 concludes our results.

2. Optimal capacity reliability design model

For networks with limited capacity, network capacity reliability needs to be considered in the optimal network design. Our goal is to minimize total cost of the network under the constraint of the network capacity reliability requirement. The decision variables are component types, which determines the component reliability, capacity and cost. In this paper, we study the optimal network capacity reliability design based on the following assumptions (which is also frequently used in traditional optimal reliability design problems [7]):

1) The capacity of both nodes and links is limited in the network;

2) Nodes and links have only two states, fault and normal;

3) The failure probability of nodes and links in the network is statistically independent.

In this problem, the following parameters are already given, including network capacity reliability requirement $R^{\mathrm{*}}$, the source and destination of the transmission, the required system capacity $C^{\mathrm{*}}$, and the network topology. The optimization model can be presented as:

where $n$ is the number of components (including both links and nodes), $i$ is the component number, $j$ is the type number. For the component $i$ with type $j$, $v_{ij}$ is its cost, $w_{ij}$ is its reliability, and $l_{ij}$ is its length for links, or $l_{ij}=$1 for nodes. $g(v_{ij},l_{ij},x_{ij})$ is the total cost, the sum of all component cost, and it can be calculated as:

$f(w_{ij},l_{ij},x_{ij})$ is the calculation of capacity reliability. The capacity reliability calculation method proposed by Aggarwal [2]is applied in this problem. It is an early method but can effectively estimate the reliability of networks with limited capacity [8]. The topology and capacity of networks are modeled via connection matrix. All valid groups (i.e., path sets, including the minimal path sets and their combinations that can satisfy the required system capacity) can be obtained by the algorithm. The capacity reliability is computed based on the valid groups using the principle of inclusion-exclusion [9] as follows:

where $m$ is the number of minimal path sets, event $A_i$ is the occurrence of minimal path set $i$, and the value range of $i$, $j$, $k$ is [1, $n$]. The detail flow diagram of the method is shown in Fig. 1.

3. Optimization based on genetic algorithm

GA provides a generic solution for the system optimization problem. It searches global optimal solutions by the population iteration. It is applicable for large scale and high nonlinear optimization problems without analytical expressions [10]. Different from traditional single-point search algorithm, GA can handle multiple individuals in the search space simultaneously and evaluate multiple solutions simultaneously [11]. So it has better global search capability. These features make GA capable to solve such complex problems as optimal network capacity reliability design.

Fig. 1The calculation method of capacity reliability

3.1. The procedure of GA

In this paper, GA is used to solve the optimization model in Eq. (1). The procedure of the optimal capacity reliability design based on GA is shown in Fig. 2.

Fig. 2Flowchart of optimal network capacity reliability design based on genetic algorithm

For a network with $n$ components, decision variables of GA are [$S_1$, $S_2$, …, $S_n$], where $S_i$ is the selected type number of the $i$th component. These variables are encoded, and the initial population is randomly generated. The fitness of each individual is calculated, and then use selection, crossover and mutation operations to generate the next generation. Some possible choices of selection, crossover and mutation operations are listed in Table 1.

These procedures are iterated until the maximum number of the generation is achieved. Finally, the component combination with the minimum cost is determined as the optimal solution.

Table 1Operations of selection, crossover and mutation

Items	Set
Selection	Roulette selection, random universal selection, elitism strategy
Crossover	Single-point crossover, two-point crossover, multi-point crossover
Mutation	Simple mutation, uniform mutation, boundary mutation

4. Case study

The ARPA network shown in Fig. 3 is used as an example to verify the effectiveness of our proposed method. Assume that 50 units of traffic is required to be transmitted from Node 1 to Node 5. Let the capacity reliability requirement of the network be 0.98. Attributes of possible types of components are shown in Table 2.

From Table 2, one can see that the capacity is not always increased with the cost, and the gradient method in [6] cannot be used. Our method with the following parameters are used to find the optimal solution.

The optimal result can be obtained in Table 4, and the optimization process is shown in Fig. 4. One can see that both the average and optimal values of the objective function in the population decline gradually. It shows that GA has good convergence and search performance in solving this problem.

Fig. 3The topology of the ARPA network: Note: (1) the number in the circle is the node number; (2) the number out of parentheses is the link number; and (3) the number in parentheses is the link length

Fig. 4Optimization process with genetic algorithm

The optimization results show that: (1) the GA is applicable for solving optimal network capacity reliability design problems and has good convergence, and (2) compared to the gradient method, the GA can be applied to those component candidates whose capacity and/or reliability do not increase with cost.

5. Conclusions

In this paper, an optimization method based on genetic algorithm is proposed for optimal network capacity reliability design problem. The optimization model is presented, and the GA optimization procedure and its fitness function is detailed addressed. Our proposed method can be used for component candidates whose capacity and/or reliability is not monotonically increase with the cost.

It is not easy to calculate the capacity reliability for large scale networks, the related topics will be studied in our future research.