# Improved Quantum Chaotic Animal Migration Optimization Algorithm for QoS Multicast Routing Problem

Mohammed Mahseur, Abdelmadjid Boukra, Yassine Meraihi

► To cite this version:

Mohammed Mahseur, Abdelmadjid Boukra, Yassine Meraihi. Improved Quantum Chaotic Animal Migration Optimization Algorithm for QoS Multicast Routing Problem. 6th IFIP International Conference on Computational Intelligence and Its Applications (CIIA), May 2018, Oran, Algeria. pp.128-139, 10.1007/978-3-319-89743-1_12. hal-01913908

HAL Id: hal-01913908

https://inria.hal.science/hal-01913908

Submitted on 7 Nov 2018

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Improved Quantum Chaotic Animal Migration
Optimization algorithm for QoS multicast
routing problem

Mohammed Mahseur¹, Abdelmadjid Boukra¹, and Yassine Meraihi²

¹ Department of Informatics, Faculty of Electronics and Informatics, University of Sciences and Technology Houari Boumediene, El Alia Bab Ezzouar, Algiers 16025, Algeria

² Automation Department, University of MHamed Bougara Boumerdes,35000 Avenue of Independence, Boumerdes.Algeria

mahseur.mohammed@gmail.com

aboukra@usthb.dz

yassine.meraihi@yahoo.fr

**Abstract.** In recent years, we are witnessing the spread of many and various modern real-time applications implemented on computer networks such as video conferencing, distance education, online games, and video streaming. These applications require the high quality of different network resources such as bandwidth, delay, jitter, and packet loss rate. In this paper, we propose an improved quantum chaotic animal migration optimization algorithm to solve the multicast routing problem (Multi-Constrained Least Cost MCLC). We used a quantum representation of the solutions that allow the use of the original AMO version without discretization, as well as improving AMO by introducing chaotic map to determine the random numbers. These two contributions improve the diversification and intensification of the algorithm. The simulation results show that our proposed algorithm has a good scalability and efficiency compared with other existing algorithms in the literature.

**Keywords:** Animal Migration Optimization, Quantum Representation, Chaotic Maps, Quality of Service (QoS), Multicast routing.

# 1 Introduction

The evolution of computer networks has been accompanied by the emergence of a new range of real-time multimedia network applications that exchange and share data, images, videos, sound files, etc. These applications require multicast transmissions with strict QoS guarantees as essential capabilities, where the same data streams are delivered from the source node to a selected group of nodes simultaneously. The most important requirements of QoS parameters are cost, delay, delay jitter, bandwidth, and packet loss rate. Therefore, it is essential to use the different network resources in a rational way. The QoS multicast
routing problem (MCLC) is a nonlinear combinatorial optimization problem for transmission in the areas of networks. It is proved to be NP-Hard [1] and has recently attracted an increasing attention from researchers. Its main objective consists in finding the optimal multicast routing tree by minimizing the cost under multiple constraints such as delay, delay-jitter, bandwidth, and packet loss rate. It was approached by various algorithms based on meta-heuristics such as Genetic Algorithm (GA), Tabu Search (TS), Particle Swarm Optimization (PSO), Bat Algorithm (BA), and Optimization Based on Biogeography (BBO).

Hwang et al. [2] proposed a GA-based algorithm for multicast routing problem without constraints, the optimization of the multicast tree is achieved through a serial path selection, by crossover and mutation operation. Results showed that the proposed algorithm is able to find a better solution than the RSR algorithm. Haghighat et al. [3] proposed a novel QoS-based multicast routing algorithm based on the GA to find a multicast tree with least cost satisfying the constraints of delay and bandwidth. Simulation results showed that the proposed algorithm outperformed other algorithms.

Youssef H et al. [4] present a TS algorithm to build the near optimal solution, their algorithm starts with an initial feasible solution and builds a tree of the sink for each destination with the shortest path of Dijkstra algorithm, in each iteration the algorithm refines the tree at a lower cost. Experimental results showed that TS is able to find better solutions that other reported multicast algorithms. Ghaboosi and Haghighat [5] used the PRA, which is a progressive method. They construct solutions by the combination of elements of a couple of solutions chosen randomly (an initial solution and a guide one) using systematic and deterministic rules.

Liu et al. [6] proposed a PSO algorithm to solve the QoS multicast routing problem by means of serial path selection to obtain a feasible multicast tree by exchanging paths in the vector. Experimental results indicated that the proposed algorithm can converge to the optimal or near the optimal solution with lower computational cost. It also appeared that PSO outperformed GA on QoS the tested multicast routing problem. Qu et al. [7] developed a PSO algorithm based on the jump (JPSO), such that each particle moves either based on its position, either based on a chosen attractor, once the particle reaches his new position, it performs a local search to improve its position.

Mahseur and Boukra [8] proposed two approaches to solve the MCLC Problem, the first one is based on BBO and the second on BA, the results of their experimentation are encouraging in comparison with other existing algorithms. Meraihi et al. [9] proposed an improved chaotic binary bat algorithm to solve the QoS multicast routing problem. Simulation results reveal the efficiency of the proposed algorithm compared with some other existing algorithms in the literature.

In this paper, we have applied a new meta-heuristic called Animal Migration Optimization (AMO) to resolve the problem of MCLC. To improve diversification and intensification, we have used the quantum representation of solutions and integrated the chaotic maps in some characteristic equations of AMO.
The rest of the paper is organized as follows. section 2 presents the math- ematical multicast routing problem formulation followed by Section 3 which describes the AMO algorithm. In Section 4, we propose the improved quantum chaotic animal migration optimization algorithm. In section 5 we study three scenarios, we investigate the performance of our algorithm in first one, the con- vergence and scalability in the second one, and the robustness and speed in the last one. Finally section 6 summarizes the findings.

## 2 Multicast Routing Problem formulation

Throughout this work, the communication network is modeled as a directed weighted graph $G = (V, E)$ where $V$ denotes the set of nodes, and $E$ denotes the set of the edges representing wireless links between nodes. $|V| = n$ is the number of nodes and $|E| = l$ is the number of links in the network. Each link $e = (i, j) \in E$ that connects node $i$ with node $j$ is associated with link cost $C(e) : E \to R^+$, link delay $D(e) : E \to R^+$,link delay jitter $J(e) : E \to R^+$, link bandwidth $B(e) : E \to R^+$, and link packet loss rate $PL(e) : E \to R^+$, where $R^+$ is the set of all nonnegative real numbers. We assume that $s \in V$ represents the source node and $M \subseteq \{V - \{s\}\}$ represents a set of multicast destination nodes such that $s$ and $M$ construct a multicast tree $T(s, M)$.

The multicast tree has the following parameters [10], [11]:

The total cost of the multicast tree $T(s, M)$, denoted by $Cost(T(s, M))$, is defined as the sum of the costs of all links in that tree. It can be given by:

$$ Cost(T(s, M)) = \sum_{e \in T(s, M)} C(e) \quad (1) $$

The total delay of the path $P_T(s, m)$, denoted by $Delay(P_T(s, m))$, is simply the sum of the delays of all links along the path:

$$ Delay(P_T(s, m)) = \sum_{e \in P_T(s, m)} D(e) \quad (2) $$

Where $P_T(s, m)$ denotes the routing path of the multicast tree $T(s, M)$ that connects the source node $s$ with the destination node $m \in M$ (clearly $P_T(s, m)$ is a subset of $T(s, M)$).

The delay jitter of the path $P_T(s, m)$, denoted by $Jitter(P_T(s, m))$, is defined as the sum of the delays-jitter of all links along the path and can be given by:

$$ Jitter(P_T(s, m)) = \sum_{e \in P_T(s, m)} J(e) \quad (3) $$

The bandwidth of the path $P_T(s, m)$, denoted by $B(P_T(s, m))$, is defined as the minimum required bandwidth at any link along $P_T(s, m)$:

$$ B(P_T(s, m)) = \min_{e \in P_T(s, m)} (B(e)) \quad (4) $$
The Packet loss rate of the path from source node s to destination node m, denoted by $PL(P_T(s, m))$ is given by:

$$PL(P_T(s, m)) = 1 - \prod_{e \in P_T(s, m)} (1 - PL(e)) \quad (5)$$

The MCLC problem can be formulated as follows:

$$\text{Minimize Cost}(T(s, M)) \quad (6)$$

Subject to:

$$\text{Delay}(P_T(s, m)) \le D_{max} \quad (7)$$

$$\text{Jitter}(P_T(s, m)) \le J_{max} \quad (8)$$

$$\text{Min}(B(P_T(s, m))) \ge B_{min} \quad (9)$$

$$PL(P_T(s, m)) \le PL_{max} \quad (10)$$

## 3 Animal Migration Optimization AMO

Animal Migration Optimization Algorithm (AMO), developed by Li et al. in 2014 [12], is a novel interesting nature-inspired metaheuristic optimization algorithm used to solve various optimization problems. This optimization algorithm is inspired by the migration behavior of animals in groups to ensure their survival. These animals can be found in several families such as mammals, birds, fish, reptiles, amphibians, insects, and crustaceans. These families are leaving their current habitats and migrating to other geographically distant habitats that can provide better living conditions. There are several reasons for migration such as food shortage, drought, reproduction, and seasonal change. For simplicity, AMO uses the following two idealized rules [12]:

1. The leading animal with high position quality will be kept for the next generation;

2. The number of animals in the group is fixed, and the animal leaving the group will be replaced by a new individual with a probability $Pa$.

AMO algorithm works based on two processes. In the first process, the algorithm simulates how the groups of animals move from the current position to the new position. In the second process, the algorithm simulates how some animals leave the group and some join the group during the migration.

Each individual $i$ changes its current position during the iteration $G + 1$ by changing the components of its vector $X_i$ according to one of the neighbors according to the following formula:

$$X_{i,G+1} = X_{i,G} + \delta(X_{neighborhood,G} - X_{i,G}) \quad (11)$$

Where $\delta$ is a parameter defined according to the problem treated, and the neighboring individual is randomly selected from the neighbors. Remember that the
topology and the size of the population are fixed. An animal is asked to leave the group with probability Pa and replaced by another obtained by the following formula:

$$X_{i,G+1} = X_{r1,G} + rand.(X_{best,G} - X_{i,G}) + rand.(X_{r2,G} - X_{i,G}) \quad (12)$$

# 4 IQCAMO for QoS multicast routing

## 4.1 Improved Quantum Chaotic AMO algorithm

In order to improve the effectiveness and the robustness of the AMO algorithm, we have proposed two modification methods. The first modification method introduces the quantum representation of the solutions to allow the use of the original AMO version without discretization.

The second modification method adopts the chaotic map to overcome the problem of choosing the right value of the two random numbers used in equation 12. There are several chaotic maps like logistic map, circle map, tent map, piecewise map, iterative map, Chebyshev map, sine map, sinusoidal map etc. Logistic map is the most representative chaotic map with simple operations and well dynamic randomness [13]. So this chaotic behavior map is adopted in this paper to generate the two random numbers at each iteration. The random number generated by a logistic map is given by:

$$CM_{t+1} = aCM_t(1 - CM_t), t = 0, 1, 2... \quad (13)$$

Where $CM_t$ is the chaotic map value at the t-th iteration, it is in [0, 1]. Here a is a control parameter and $0 < a < 4$. The chaotic system is very sensitive to the initial values, to make the logistic map in a complete chaos, we adopt the parameter a = 4 and $CM_t$ does not belong to {0, 0.25, 0.5, 0.75, 1} otherwise the logistic equation does not show chaotic behavior [14]. In our experiments, we take $CM_0 = 0.7$. Algorithm 1 describes the pseudo-code of the IQCAMO algorithm for multicast routing problem.

## 4.2 Representation of the solution

The solution representation of the i-th Qbit individual is defined by a real vector $Q_i^t = (q_{i1}^t, q_{i2}^t, ..., q_{im}^t), j = 1, 2, ..., m$, where m represents the length of the vector which is equal to the total number of links in the network.

The Qbit vector $Q_i$ is defined as follows:

$$\begin{bmatrix} \alpha_{i1}^t | \alpha_{i2}^t | \dots | \alpha_{im}^t \\ \beta_{i1}^t | \beta_{i2}^t | \dots | \beta_{im}^t \end{bmatrix} \quad (14)$$

The binary representation of the solution which is a multicast tree is a binary vector $X_i^t = (x_{i1}^t, x_{i2}^t, ..., x_{im}^t), j = 1, 2, ..., m$, where $x_{ij}^t = 0$ or 1, which indicates
whether the corresponding link *i* is selected or not to construct the multicast tree. The binary vector $X_i^t$ is defined as follows:

$$x_{ij} = \begin{cases} 1; & \text{if } rand(0, 1) > |\alpha_{ij}^t|^2 \ (i \text{ is selected to construct the multicast tree}). \\ 0; & \text{otherwise.} \end{cases} \qquad (15)$$

## 4.3 Initial population

Before the generation of the initial population, we delete all link with bandwidths less than the bandwidth constraint $B_{min}$. The initial population is produced by the Depth First Search (DFS) method, we take the source node and connect it randomly to one of its successors and compare it with the set of destination nodes $M$, if it is a destination so it is a valid path, otherwise we redo the same approach until obtaining a solution in natural form. If the path is saturated (blocked road), we restart the operation from the source node. Each connection of a node, a check is made to avoid the construction of loops.

## 5 Simulation results

The performances of the proposed approach are studied and compared with the implemented algorithms: GA [2] and JPSO [7]. The three algorithms were implemented using Visual C++ on a PC Intel Core 2 Duo 2.0 GHz. The nodes are randomly distributed in a rectangle of 4000km x 2400km, links are generated according to the topology model Waxman [15]. In this model, the existence of a link between two nodes $u$ and $v$ depends on a probability $p(u, v)$ given by the following formula: $P(u, v) = B \exp(-l(u, v)/AL)$ Where: $l(u, v)$ represents the Euclidean distance between two nodes $u$ and $v$. $L$ is the maximum distance between any two points in the network. $B$ is a parameter that controls the number of links in the network. $A$ is a parameter that controls the number of short links in the network. $A$ and $B$ are set to 0.8 and 0.7 respectively like in [7]. The cost, delay, packet loss rate and bandwidth of the links are taken randomly in the interval [1, 100], [1ms, 30], [0.0001, 0.01] and [2Mbps, 10] respectively. The thresholds constraints $\Delta$, $\xi$, and $\delta$ are set to 120ms, 60ms and 0.05 respectively. The bandwidth required by the flow to send $\beta$ is randomly generated in the interval [2Mbps, 10] [15]. The source and destination nodes are selected randomly from the network. We perform tree scenarios:

1. In the first scenario, and in order to evaluate the performance of each algorithm, we evaluate the cost of the multicast tree while varying the number of nodes in the network with 10% of destinations;

2. In the second scenario, we observe the cost of the best solution for each algorithm according to the number of iterations and the size of network to study the convergence and scalability of algorithms;
3. In the third scenario, we have varied the number of destination nodes to evaluate for each algorithm the cost of the optimal solution and the convergence time in order to study the robustness and speed of algorithms.

## 5.1 Results of the first scenario

In the first scenario, we varied the size of the network from 20 to 120 nodes. Each time, the source node and the destinations (10% of the nodes) are chosen randomly. The results are represented in Figure 1.

Figure 1 shows the multicast tree cost of GA, JPSO, and IQCAMO, according to the network size. First, we observe that the multicast tree cost increases with the increase of the network size. Second, we observe that the multicast tree cost generated by IQCAMO is less than the other multicast tree costs.

<figure><img src="image_2.png" /><figcaption>Fig. 1. The cost of the multicast tree while varying the number of nodes in the network.</figcaption></figure>

## 5.2 Results of the second scenario

In the second scenario, we have studied three kinds of networks: small network (50 nodes), medium network (200 nodes), and large network (500 nodes) with 10% destinations, then we evaluated the optimal solution of each algorithm during the iterations. The results are represented in Figures: 2, 3, and 4.

Figure 2 shows solutions obtained by the three algorithms in a small network, we observe that the solutions proposed by JPSO are the best.

We observe in Figure 3 and Figure 4 that our algorithm has the best speed of convergence; this is provided by the use of quantum principles.
<figure><img src="image_3.png" /><figcaption>Fig. 2. Convergence of algorithms in a small network.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 3. Convergence of algorithms in a medium network.</figcaption></figure>

## 5.3 Results of the third scenario

In the third test, we study the cost of multicast routing and the convergence time by varying the number of destination nodes. The results are represented in Figure 5 and Figure 6.

Figure 5 shows the multicast tree cost of GA, JPSO, and IQCAMO while varying the number of destination nodes. We observe that IQCAMO gives the best routing cost. This is due to the use of the quantum representation and the chaotic maps which are more efficient in exploring large search space. Figure 6 shows that the convergence time increases while increasing the number of destination nodes and we observe that IQCAMO gives the best convergence
<figure><img src="image_5.png" /><figcaption>Fig. 4. Convergence of algorithms in large network.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Fig. 5. The cost of the multicast tree while varying the number of destination nodes.</figcaption></figure>

time. Thus, the proposed approach is more robust and fast. This is due to the use of the quantum mechanism and the chaotic maps which are more efficient in exploring large search space.

## 5.4 Friedman test

In order to study the difference between the three algorithms in terms of multicast tree cost, we use the Friedman test. The results are given in table 1. We observe that the significance level is less than 5%, so the null hypothesis $H_0$ is rejected which implies that the Friedman test is significant. Furthermore, IQCAMO is classed as the best algorithm in terms of multicast tree cost.
<figure><img src="image_7.png" /><figcaption>Fig. 6. The convergence time while varying the number of destination nodes.</figcaption></figure>

<table><caption>Table 1. Friedman test.</caption><thead><tr><th colspan="2">Friedman test</th></tr><tr><th>Algo</th><th>Mean Rank</th></tr></thead><tbody><tr><td>GA</td><td>2.70</td></tr><tr><td>JPSO</td><td>2.01</td></tr><tr><td>IQCAMO</td><td>1.30</td></tr></tbody><thead><tr><th colspan="2">Test statistics</th></tr></thead><tbody><tr><td>N</td><td>64</td></tr><tr><td>Chi-Square</td><td>73.495</td></tr><tr><td>df</td><td>2</td></tr><tr><td>Asymp.sig</td><td>.000</td></tr></tbody></table>

## 6 Conclusion

In this paper, we have applied a new meta-heuristic called AMO on multicast routing problem which is an NP-hard problem. We used a quantum representation of the solutions that allowed us to use the original AMO version without discretization, as well as improving AMO by introducing chaotic Maps into the calculation of some equations. These two contributions improve the diversification and intensification of the algorithm. We performed an optimization on the graph representing the network and another on the initial population which accelerated the exploration of the search space. To evaluate the performance of our solution we tested three comparative scenarios with two other algorithms: in the first scenario, we compared the multicast tree cost with varying the network size and using 10% as destinations. We notice that IQCAMO produces the minimum cost. In the second scenario, we study the convergence of the three algorithms; we observe that IQCAMO is the best. In the last scenario, we evaluate the cost
and the convergence time while varying the size of the set of destination nodes. We found that our approach has an ability to deliver the best results. The experimental results lead to conclude that our algorithm increases the overall research capacity. As future work, we intend to investigate the multi-objective aspect of the problem. Indeed, to have a better resolution of the problem, other objectives must be considered, like delay, bandwidth, jitter etc.

## References

1. Wang, Z., Crowcroft, J.: Quality-of-service routing for supporting multimedia applications. Selected Areas in Communications, IEEE Journal on, 14(7), 1228-1234 (1996)

2. Hwang, R. H., Do, W. Y., Yang, S. C.: Multicast routing based on genetic algorithms. J. Inf. Sci. Eng., 16(6), 885-901 (2000)

3. Haghighat, A. T., Faez, K., Dehghan, M., Mowlaei, A., Ghahremani, Y.: GA-based heuristic algorithms for QoS based multicast routing. Knowledge-Based Systems, 16(5), 305-312 (2003)

4. Youssef, H., Al-Mulhem, A., Sait, S. M., Tahir, M. A.: QoS-driven multicast tree generation using tabu search. Computer Communications, 25(11), 1140-1149 (2002)

5. Ghaboosi, N., Haghighat, A. T.: A path relinking approach for delay-constrained least-cost multicast routing problem. In Tools with Artificial Intelligence, 2007. IC-TAI 2007. 19th IEEE International Conference on (Vol. 1, pp. 383-390). IEEE (2007)

6. Liu, J., Sun, J. Xu, W.: QoS multicast routing based on particle swarm optimization, In Intelligent Data Engineering and Automated Learning IDEAL 2006, pp.936-943, Springer Berlin Heidelberg (2006)

7. Qu, R., Xu, Y., Castro, J. P., Landa-Silva, D.: Particle swarm optimization for the Steiner tree in graph and delay-constrained multicast routing problems. Journal of Heuristics, 19(2), 317-342 (2013)

8. Mahseur, M., Boukra, A.: Using bio-inspired approaches to improve the quality of service in a multicast routing. International Journal of Communication Networks and Distributed Systems, 19(2), 186-213 (2017)

9. Meraihi, Y., Acheli, D., Ramdane-Cherif, A.: An Improved Chaotic Binary Bat Algorithm for QoS Multicast Routing. International Journal on Artificial Intelligence Tools, 25(04), 1650025 (2016)

10. Sun, J., Fang, W., Wu, X., Xie, Z., Xu, W.: QoS multicast routing using a quantum-behaved particle swarm optimization algorithm. Engineering Applications of Artificial Intelligence, vol. 24, no. 1, pp. 123-131, (2011)

11. Abdel-Kader, R. F.: An improved discrete PSO with GA operators for efficient QoS-multicast routing. International Journal of Hybrid Information Technology, 4(2), 23-38 (2011)

12. Li, X., Zhang, J., Yin, M.: Animal migration optimization: an optimization algorithm inspired by animal migration behavior. Neural Computing and Applications, 24(7-8), 1867-1877 (2014)

13. Kanso, A., Smaoui, N.: Logistic chaotic maps for binary numbers generations. Chaos, Solitons & Fractals, 40(5), 2557-2568 (2009)

14. dos Santos Coelho, L., Sauer, J. G., Rudek, M.: Differential evolution optimization combined with chaotic sequences for image contrast enhancement. Chaos, Solitons & Fractals, 42(1), 522-529 (2009)

15. Waxman, B. M.: Routing of multipoint connections. Selected Areas in Communications, IEEE Journal on, 6(9), 1617-1622 (1988)