ABSTRACT

In order to optimize the network coding resources in a multicast network, an improved adaptive quantum genetic algorithm (AM-QEA) was proposed. Firstly, the optimization problem was translated into a graph decomposition problem. Then the graph decomposition problem was represented by the binary coding, which can be processed by quantum genetic algorithm. At last, a multiple-operators based adaptive quantum genetic algorithm was proposed to optimize the network coding resources. In the algorithm, the individual fitness evaluation operator and population mutation adjustment operator were employed to solve the shortcomings of common quantum genetic algorithm, such as high convergence rate, easy to fall into local optimal solution and low diversity of the population in later stage. The experimental results under various topologies show that the proposed algorithm has the advantages of high multicast success rate, fast convergence speed and strong global search ability in resolving the network coding resource optimization problems.

Keywords:

Network Coding, Quantum Genetic Algorithm, Multicast Networks, Optimization

1. Introduction

Multicast allows the information transmitted from single point to multiple points in networks. Compared with the traditional unicast and broadcast methods, multicast dramatically improves transmission efficiency. Multicast technology can provide critical technical support for most services, such as distance learning, video on demand, data distribution in the data center and etc. [1] . Network coding is an effective technique for improving network throughput, and it also can bring many benefits for the multicast transmission. It allows intermediate network nodes to perform arbitrary mathematical calculations to combine (encode) the input packets, and then output the encoded packets to the downstream nodes [2] . The key problem network coding based multicast technology is how to quickly and efficiently determine the coding nodes of each route in the network. Therefore, the point-to-multipoint multicast rate can reach the upper limit specified by Shannon’s “maximum stream-minimum cut” theorem [3] . As an emerging technology, network coding technology has received much attention. However, this problem belongs to the NP-hard problem, and there is currently no clear and efficient solution.

The research on network coding technology initially focused on creating different coding constructs. For example, a polynomial time algorithm for network coding was proposed by P. Sander et al. [4] , an algebraic construction method for network coding was given by R. Koetter and M. Medard of MIT [5] [6] . Recently, research on network coding technology has become more diverse. For example, Sudipta Sengupta et al. [7] studied coding in wireless networks. In order to solve the Network Coding problem for Critical Infrastructure Networks, Rakesh Kumar et al. [8] proposed an architecture that realizes linear NC by decomposing the linear NC functions. Imad El Qachchach et al. [9] implemented an efficient multi-source network coding by using low-rank parity check code.

In 1996, A. Narayanan and M. Moore first combined the quantum computing theory with evolutionary algorithms and proposed the concept of the quantum genetic algorithm [10] . The quantum genetic algorithm has the advantages of small population size, maintaining population diversity, and being easy to parallelize. Compared with traditional genetic algorithms, it can solve the shortcomings of the traditional genetic algorithm such as sensitivity to population size, more iterations, easy falling into the local optimum solution, and slow convergence speed.

Quantum genetic algorithms have a wide range of applicability. In recent years, it has been the focus of research on solving optimization problems. For example, Lijun Mao et al. [11] applied the quantum genetic algorithm to the cloud computing job scheduling. Ye Zhang et al. [12] used it to solve the observing and downloading integrated scheduling problem of earth observation satellite. Kong Haipeng et al. [13] presented an adaptive double chain quantum genetic algorithm (ADCQGA) for solving constrained optimization problems. Kim et al. [14] first introduced genetic algorithm to solve the network coding resources optimization problem in a multicast network. However, due to the instability of genetic algorithm, the effect is general. Based on Kim’s method, Qu et al. [15] [16] proposed a genetic algorithm to optimize network coding resources with transmission restriction in a multicast network.

The key problems of the quantum genetic algorithm are to determine the quantum bit coding, the quantum revolving gate mechanism, and the population fitness evaluation function. For each individual, the evolutionary parameters should be considered carefully because the adjustment of the rotation angle is flexible. If the rotation angle is too small, the convergence speed of the algorithm is slow, and the rotation angle is too large, which makes the algorithm easy to fall into the local optimal solution.

To optimize the network coding resource in a multicast network, an adaptive quantum genetic algorithm based on the multi-operator coordination mechanism was presented. The algorithm can solve the problem of easy to fall into the optimal local solution by improving the diversity of the population in the later evolution stage.

2. Problem Formulation

In order to facilitate the research, this paper simplifies the network coding resources problem to be studied as follows: assume that the communication network is represented by a directed graph G (V, E) with all sides being unit flows. The edge with capacity K can be replaced with the side of the K unit flow in this graph. Then the single source multicast problem can be represented by a quaternion (G, s, T, R), where G represents a directed topology, s is a multicast source node, $T=\left\{t_1,t_2,\cdots ,t_n\right\}$ is the set of destination nodes, and R is the multicast rate of node s to all target nodes. We combine the coded nodes linearly. A coding strategy that the multicast rate from s to all target nodes is R called a feasible linear network coding. For a particular (G, s, T, R), we hope that the last established multicast tree has as little coding as possible while achieving the given multicast rate R.

We use the number of encoded edges to measure the task quantities of the encoding operation. As shown in Figure 1, a coding node v has three input edges and two exit edges, where $y_1=x_1+x_2$ , $y_2=x_1+x_2+x_3$ . If at least two input edges need to output information from an output edge simultaneously, then this output edge is defined as the coded edge. Therefore, the node has two coding edges and thus has two encoding operations. For a particular node in (G, s, T, R), it can be considered a potential coding node if and only if its number of input edges $m\ge 2$ and the exit edge $n\ge 1$ .

In order to facilitate the design of the fitness function, we split all potential coding nodes. Assuming that an encoding node has m input edges and n output

edges, we introduce p auxiliary nodes $\left\{u_1,u_2,\cdots ,u_p\right\}$ to connect with the nodes of the input links, and introduce q auxiliary nodes $\left\{w_1,w_2,\cdots ,w_q\right\}$ is connected with the nodes of the output links. Then all traffic flowing through the node can be represented as a linear combination between the secondary node $u_i$ and the secondary node $w_j$ . The topological maps of each algorithm in this paper are all decomposed topological maps. For example, the topological map after the decomposition of the coding node v in Figure 1 is as shown in Figure 2.

3. Algorithm Description

3.1. Algorithm Flow

The whole algorithm includes three parts: the rotation angle adaptive adjustment mechanism, the multi-operator synergy mutation mechanism, and the population fitness evaluation. The overall algorithm flow can be described, as shown in Figure 3.

3.2. Rotation Angle Adaptive Adjustment Mechanism

The method of population update in this algorithm uses a quantum revolving door update strategy. Its update matrix can be expressed as follows.

$\left[\begin{array}{c}{{\alpha }^{\prime }}_i\\ {{\beta }^{\prime }}_i\end{array}\right]=\left[\begin{array}{cc}\cos \left({\theta }_i\right)& -\sin \left({\theta }_i\right)\\ \sin \left({\theta }_i\right)& \cos \left({\theta }_i\right)\end{array}\right]\left[\begin{array}{c}{\alpha }_i\\ {\beta }_i\end{array}\right]$ (1)

In Equation (1), $\left({\alpha }_i,{\beta }_i\right)$ is the i-th qubit in the chromosome and ${\theta }_i$ is a rotation angle. The adaptive adjustment mechanism modifies the rotation angle of individual evolution according to the fitness of different individuals. The rotation angle lookup table used in this algorithm is shown in Table 1.

In Table 1, f(x) represents the fitness value of the individual x, $x_i^j$ represents the i-th position of the j-th individual, represents the i-th position of the optimal individual in the current population, and $S\left({\alpha }_i^j,{\beta }_i^j\right)$ represents the rotation angle in the polar coordinates. ${\theta }^j$ is the rotation angle step used by the j-th individual. Its definition is as follows.

${\theta }^j=\{\begin{array}{l}\frac{f_j-f_{\min }}{f_{\max }-f_{\min }}\cdot \left(K_2-K_1\right)+K_1,f_{\max }\ne f_{\min }\\ K_1,f_{\max }=f_{\min }\end{array}$ (2)

In the current population, the i-th evolutionary rotation angle step and rotation direction of the jth individual can be calculated by the Equation (3).

$\Delta {\theta }_i^j={\theta }^j\cdot S\left({\alpha }_i^j,{\beta }_i^j\right)$ (3)

3.3. Fitness Function Design

For the convenience of solving problems, we translate the minimization problem

into the maximization problem. For a single chromosome X, the fitness formula is designed as follows:

$Fitness\left(X\right)=\{\begin{array}{l}W-need,f=1\\ W-n_{\max },f=0\end{array}$ (4)

In this equation, $n_{\max }$ is the number of all coding edges in the topology map corresponding to chromosome X, and need is the number of coding edges in the generated multicast tree, and W is a constant much larger than $n_{\max }$ .

The variable need can be calculated by the following steps. First, we generate the topological map corresponding to chromosome X and then use the topology map as input. Second, we use the dinic algorithm to solve the maximum flow (s, t) of the source point s to all other target nodes $t\in T$ . If there is any flow (s, t) less than multicast rate R, this indicates that the topology can’t meet the condition. That is, if f = 0, then need = $n_{\max }$ , otherwise f = 1. For all target nodes $t\in T$ , we use the Dijkstra algorithm to solve the path set $P\left(s,t\right)=\left\{P_1\left(s,t\right),P_2\left(s,t\right),\cdots ,P_R\left(s,t\right)\right\}$ . For each target node, we run R times Dijkstra algorithm. It is necessary to ensure that for every $P_j\left(s,t\right)$ path set, for any $i\ne j$ , $P_i\left(s,t\right)\cap P_j\left(s,t\right)=\varnothing$ . We record the passing edges in the tag array when we run the Dijkstra algorithm, which ensures that the repeated edges will not be taken during the next iteration of the algorithm. The path set P is all sides of the multicast tree. In this multicast tree, if the number of incident edges of a node is not less than 2, the corresponding output edge of the node is the coding edge. In the process of the Dijkstra algorithm, we could define two sets for all potential coding nodes. In this way, we record the edges emitted from the point, and the edges injected into the point, respectively. The need can be quickly calculated through these two sets. The whole process of the fitness evaluation function is shown in Figure 4.

3.4. Multi-Operator Synergy Mutation Mechanism

The adaptive quantum genetic algorithm can assign different rotation angle steps

according to the characteristics of each individual, which greatly improves the convergence speed of the algorithm. However, in the later stage of the algorithm, the algorithm is easy to fall into the optimal local solution due to the decline of population diversity. Based on this, the multi-operator synergy mutation mechanism is added. The current population status is evaluated by multiple operators, which increases the diversity of populations in the late stage of the algorithm. And the algorithm can jump out of the optimal local solution with a large probability. The stability of the algorithm is enhanced.

The individual similarity evaluation operator $X_{sim}$ is used to evaluate the differences between individuals in the current population. As shown in the Equation (5), where $d_{\max }$ and $d_{\min }$ respectively represent the largest and smallest individual between the current population and the optimal individual. The $d_{avg}$ is the average value of the Hamming distance between all individuals in the current population.

$X_{sim}=\{\begin{array}{l}\frac{d_{avg}-d_{\min }}{d_{\max }-d_{\min }},d_{\max }\ne d_{\min }\\ 0,d_{\max }=d_{\min }\end{array}$ (5)

The larger the similarity $X_{sim}$ , the more the majority of the current population is farther from the optimal solution. In this case, the larger mutation probability can be used. The smaller the similarity $X_{sim}$ , the more the current population distance solution is closer. The individual mutation probability can be reduced to make the algorithm converge faster.

The role of the individual fitness assessment operator is to evaluate the performance of each in the current population. The $f_{\max }$ and $f_{\min }$ respectively represent the optimal fitness and the worst fitness value of the current population. The $f_i$ indicates the fitness value of the current individual.

$y_{fit}=\{\begin{array}{l}\frac{f_{\max }-f_i}{f_{\max }-f_{\min }},f_{\max }\ne f_{\min }\\ 0,f_{\text{max}}=f_{\min }\end{array}$ (6)

The larger the operator $y_{fit}$ , the worse the performance of the current individual. the greater the probability of mutation should be given to the current individual so that it will mutate more quickly. The smaller the operator $y_{fit}$ , the better the performance of the current individual. A smaller probability of mutation should be given to the current individual. It could maintain its excellent traits.

The population variation adjustment operator $F_{acc}\left(n\right)$ is a function related to evolutionary algebra to avoid the premature occurrence of the algorithm. When the algorithm falls into the optimal local solution, the operator can increase the mutation probability and make the algorithm jump out of the optimal local solution.

$F_{acc}\left(n\right)=\{\begin{array}{l}{F}_{acc}\left(n-1\right)+C\cdot \frac{s-n}{s},\text{where}{f}_{\max }\left(n\right)=f_{\max }\left(n-T\right)\wedge n>T\\ F_{acc}\left(n-1\right),\text{where}{f}_{\max }\left(n\right)\ne f_{\max }\left(n-T\right)\wedge n>T\\ 0,\text{where}n\le T\end{array}$ (7)

The n is the current evolutionary algebra, s is the maximum evolution algebra, T is the algebra of the optimal solution in the iterative process of the algorithm, $C\left(0\le C\le 1\right)$ is the adjustment constant, $f_{\max }$ is the optimal adaptation in the nth generation population degree. It can be known from the definition that when the optimal fitness in the population does not change T generation continuously, the mutation probability will increase correspondingly in the T + 1 generation.

The mutation probability of each individual in each evolution is determined by the individual similarity evaluation operator, the individual fitness evaluation operator, and the population variation adjustment operator. The formula for calculating the mutation probability is shown in Equation (8).

$p_n^i=\{\begin{array}{l}{p}_0\cdot y_{fit}^n\cdot x_{sim}+F_{acc}\left(n\right),f_{\max }\ne f_{\min }\\ 0,f_{\max }=f_{\min }\end{array}$ (8)

In Equation (8), $p_n^i$ is the mutation probability of the i-th individual of the n-th generation population, $p_0$ is the initial mutation probability constant determined according to different problems.

The multi-operator synergistic mutation mechanism mainly includes individual similarity evaluation operator, individual fitness evaluation operator, and population variation adjustment operator. Their combined action is to determine the mutation probability of each in the current population.

4. Simulations and Analysis

In order to verify the effectiveness of the algorithm, this paper compares GA, QGA, and AM-QGA, and carries out the following experiments.

The software and hardware environment used in the experiment is: CPU: Intel(R) Core(TM) i5-6200U CPU4 core 2.30 GHz; memory: 4 G; Windows10; Codeblocks 16.0; GCC 5.4.0.

Firstly, we experimented with a small number of cases, as shown in Figure 5. The capacity of each link in the figure is unit capacity. The s is the source node, and t₁, t₂, t₃, and t₄ are destination nodes. According to the maximum flow minimum cut theorem, the multicast throughput between s and t₁, t₂, t₃, and t₄ is two units of capacity. In this experiment, the multicast throughput is set to 2 units. In Figure 5, the potential coding nodes are nodes 7, 8, 9, 10, 12, $n_{\max }$ is 9. And the required number of chromosome coding bits is 18. The minimum

number of encodings required for Figure 5 using the exhaustive method is 0. In this experiment, the population size of GA, QGA, and AM-QGA was 30, and the termination algebra was 200.

In the evaluation of algorithm performance, three evaluating indicators are the average optimal algebra, average optimal coding times, and the minimum number of coding times in ten experiments. They show as follows: FBG (first best solution generation), BSR (best solution success ratio), and MOP (minimum operation). The experimental results are shown in Table 2.

It can be seen from Table 2 that the three algorithms in this paper are the same as the results obtained by the violence calculation, so the correctness of the three algorithms can be proved.

In order to ensure the experimental results, this paper generated a larger scale topological map according to the literature [1] strategy. As shown in Figure 6, the original topology map is a directed topology map of one source point and two target nodes.

We copy Figure 6 into two copies and use the target starting point as the source point of the duplicated image to obtain the topological map, as shown in Figure 7. We named it 3-copy. Similarly, we get 7-copy, 15-copy, and 31-copy topologies, respectively. The total nodes, the number of edges, the number of target nodes, the number of potential coding nodes, the number of individual chromosome bits, the maximum number of coding operations, and all possible coding operands for these topological maps are shown in Table 3.

For the four topological maps in the above table, the same index is used for evaluation. The population size of GA, QGA, and AM-QGA is set to 30, and the ending algebra MAXGEN is 500. The average result of 10 experiments is obtained. The experimental results are shown in Table 4.

Figures 8-11 show the relationship between the optimal coding operands and evolutionary algebras of different algorithms in four different multicast scenarios.

From the data in the table, it can be found that the convergence rate of AM-QGA

is the fastest, and it has the best global search ability and anti-early maturity ability. The convergence performance of the QGA is second only to AM-QGA. GA has the worst convergence performance and anti-local search ability. Because AM-QGA adopts adaptive adjustment mechanism and multi-operator co-evolution mechanism, the search efficiency of the algorithm is much improved. And AM-QGA is not easy to fall into local optimum. It has the best performance among the three algorithms. Because QGA uses qubit coding, population diversity is superior to a genetic algorithm, so its algorithm performance is better than the GA algorithm. Figures 8-11 show the relationship between the optimal operation codes calculated by different algorithms and their evolutionary algebras. It can be seen that when the GA and QGA calculate the big data graph, the optimal solution cannot be found after 500 generations sometimes. This shows that the quantum genetic algorithm is very easy to fall into local optimum, although it converges quickly. By comparison, the BSR of AM-QGA is 100%. It can be seen that AM-QGA has strong global search ability in resolving the network coding resources problem. It can also maintain the diversity of the population well in the later period of the algorithm so that it can easily jump out of the optimal local solution. It can be concluded that AM-QGA has better stability and better global convergence performance after fully considering individual distribution in the population and adjusting the mutation probability.

5. Conclusion

Network coding technology has changed the traditional IP multicast mode which can only store and forward information. It effectively increases the multicast throughput, improves the bandwidth utilization efficiency, and has broad application prospects. In order to solve the problem that QGA is likely to fall into local optimum solution with high convergence rate, the AM-QGA was proposed. It mainly consists of three parts: a cooperative decision-making mechanism based on individual similarity evaluation operator, individual fitness evaluation algorithm, and population mutation adjustment operator. The AM-QGA is used to optimize the network coding resources in multicast network. The AM-QGA has the advantages of fast convergence, the high success rate of multicast, and a strong ability to get rid of the local optimum solution. However, due to the high complexity of the evaluation function, the algorithm has the problem that the time complexity constant is too large and the running time is long. The next research direction is to optimize the evaluation function algorithm or use parallel operations to increase the speed of the algorithm.

Acknowledgements

This work was supported by Natural Science Foundation of Shandong Province (NO. ZR2016FM18); A Project of Shandong Province Higher Education Science and Technology Program (NO. J16LN20).

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

Cite this paper

Xu, H.B., Wang, S.S. and Qu, Z.J. (2019) A Cooperative Evolution of Multiple Operators Based Adaptive Quantum Genetic Algorithm for Network Coding Resources Optimization. Journal of Computer and Communications, 7, 147-161. https://doi.org/10.4236/jcc.2019.77014

References