# Minimum Cost Multicast Routing Using Ant Colony Optimization Algorithm

Authors: Xiao-Min Hu; Jun Zhang
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Multicast routing (MR) is a technology for delivering network data from some source node(s) to a group of destination nodes. The objective of the minimum cost MR (MCMR) problem is to find an optimal multicast tree with the minimum cost for MR. This problem is NP complete. In order to tackle the problem, this paper proposes a novel algorithm termed the minimum cost multicast routing ant colony optimization (MCMRACO). Based on the ant colony optimization (ACO) framework, the artificial ants in the proposed algorithm use a probabilistic greedy realization of Prim’s algorithm to construct multicast trees. Moving in a cost complete graph (CCG) of the network topology, the ants build solutions according to the heuristic and pheromone information. The heuristic information represents problem-specific knowledge for the ants to construct solutions. The pheromone update mechanisms coordinate the ants’ activities by modulating the pheromones. The algorithm can quickly respond to the changes of multicast nodes in a dynamic MR environment. The performance of the proposed algorithm has been compared with published results available in the literature. Results show that the proposed algorithm performs well in both static and dynamic MCMR problems.


---

## Body

## 1. Introduction

Multicast routing (MR) is one of the most important communication network routing technologies. It first appeared in ARPANET as selective broadcasting from a single source node to a subset of the other nodes in the network [1]. Different from unicast routing, MR sends only one data copy from the source node(s) to multiple destination nodes. Since MR is resource efficient, it has been implemented in most of the modern communication networks, including overlay multicast protocols [2–4], wireless networks [5–7], and satellite networks [8, 9]. These networks support multicast applications such as distributed data processing, internet telephone, interactive multimedia conferencing, and real-time video broadcasting [4].Different multicast applications have different definitions of the cost, such as minimum bandwidth [3, 5, 7] and minimum energy [6]. The objective of the minimum cost MR (MCMR) problem is to find an optimal multicast tree with minimum cost for MR. Such a tree is termed a Steiner minimal tree (SMT) in graphs [10]. Finding the SMT has been proven to be NP complete [11].Various algorithms have been tried for solving the MCMR problem. Traditional heuristic algorithms [12–15] use greedy strategies to construct a feasible multicast tree, but they lack effective guidance to improve the results. Geographic [7] and distributed algorithms [6] are only based on the information from neighbors or nodes within a constant hop distance to compute multicast paths. However, it may be difficult to build an efficient multicast tree without complete information [2]. Computational intelligence (CI) methods such as neural networks (NNs) and genetic algorithms (GAs) have been applied to MCMR. Gelenbe et al. [16] proposed a random neural network (RNN) to optimize a multicast tree. The RNN essentially enumerated the results by iteratively adding the most potential node to the tree. Leung et al. [17] proposed a GA to train the population of individuals by simulating natural evolution. Each individual represented a multicast tree indirectly through an encoding scheme. Except for the evaluation of the fitness of individuals, no tree construction information was utilized in the evolutionary process of the GA.In recent years, ant colony optimization (ACO) [18–20] has become an important CI method. ACO is inspired by the foraging behavior of natural ants. ACO dispatches a colony of artificial ants to cooperatively search for the optimum of the optimization problem represented on a graph. Each ant in ACO incrementally builds a solution according to the construction information in a stochastic way [18]. ACO has been applied successfully to various combinatorial optimization problems, such as the traveling salesman [19, 20], constraint satisfaction [21], allocation problems [22], scheduling [23–27], data mining [28, 29], water distribution systems [30], power electronic circuit design [31], and networks [32–37]. Using ACO for MR optimization is a promising research field, which is still under development. Singh et al. [38] proposed an ant algorithm for MR optimization. In their algorithm, one ant was initially placed at every node in the multicast group and started to move to the other node via an edge. If an ant stepped on a node that had been visited by another ant, it merged into the latter ant. When only one ant was left, the edges passed by the ants forming a multicast tree. The authors had tested three different sequences for moving the ants from one node to another and found that the random approach was the best. However, their algorithm still could not always find the optimal solutions of some of their test cases. Shen and Jaikaeo [39] and Shen et al. [40] applied swarm intelligence to a multicast protocol by connecting nodes in a multicast group through a designated node. Each node in the multicast group periodically sent a packet that behaved like an ant to explore different paths to the designated node. The designated node was not statically assigned and its location influenced the optimality of the multicast tree.In order to make better use of ACO, this paper proposes a novel minimum cost multicast routing ant colony optimization (MCMRACO) algorithm for solving MCMR problems. The algorithm has the following features.(1) Based on the ACO framework, the proposed algorithm adopts a probabilistic greedy realization of Prim’s algorithm [41] for the ants to construct multicast trees. (2) Moving in a cost complete graph (CCG) of the network topology, the ants build solutions according to the heuristic and pheromone information. (3) The heuristic information is designed to represent problem-specific knowledge for the ants to construct solutions and to bias the selection of nodes in the multicast group. (4) Representing the ants’ construction experience, pheromones are modulated by the local and global pheromone update mechanisms. The local pheromone update is applied after each ant has made a construction step, whereas the global pheromone update reinforces the pheromones in the best multicast tree after each iteration. Hence, the algorithm can quickly respond to the changes of multicast nodes in a dynamic MR environment. Utilizing heuristic and pheromone information effectively, the proposed MCMRACO is more suitable for solving MCMR problems than the other heuristic and CI algorithms. The comparison results show that the algorithm works successfully in both static and dynamic MCMR problems.The rest of the paper is organized as follows. In Section2, background information for the proposed algorithm is presented. Section 3 describes the implementation and main techniques of the proposed MCMRACO algorithm. In Section 4, the proposed algorithm is tested on static and dynamic MCMR problems. Its performance is compared with the published results available in the literature. Section 5 concludes this paper and discusses some issues for future research.


## 2. Background

This section is composed of three parts. In the first part, the MCMR optimization problem is formally defined. Then a method for transforming a network graph into a CCG is illustrated. The third part describes the ACO framework.


### 2.1. Definition of the MCMR Optimization Problem

In an MCMR optimization problem, a network graph is denoted asG=(VG,EG), where VG is the set of nodes in the network and EG is the set of edges which connect the nodes in VG. The set VG is divided into three subsets VS, VD, and VI, where VS is the set of source nodes, VD is the set of destination nodes, and VI is the set of intermediate nodes. VM=VS∪VD is the set of nodes in a multicast group. Intermediate nodes can be used for relaying multicast traffic, but they do not belong to the multicast group. In backbone IP networks, the nodes in VG generally are routers. Each edge e∈EG has a positive cost value c(e) that measures the quality of the edge. If there is no edge between two nodes in VG, the corresponding cost is denoted as ∞. The optimization objective of the problem is to find a tree T=(VM+Vθ,Eθ) that minimizes the cost for connecting the nodes in VM and that satisfies the multicast constraints Ω. Formally, the MCMR problem is defined as
(1)minimize∑e∈Eθc(e),TsatisfiestheconstraintsinΩ,
where Vθ⊆VI is a subset of the intermediate nodes, Eθ⊆EG is a subset of the edges in the network graph.Figure1 shows an example of MR in a network with twelve nodes and some edges. Node 1 is the source node. The black solid nodes 2, 4, 6, 12 are the destination nodes. A multicast tree connecting the multicast nodes via the intermediate nodes 5 and 7 is shown in the figure. In this paper, a multicast group has only one source node and multiple destination nodes.Figure 1
An example of multicast routing. The source node and the destination nodes belong to a multicast group. The heavy black lines indicate the multicast tree.


### 2.2. Cost Complete Graph (CCG)

The network graph is usually a noncomplete but connected graph. The edges in a network graph are termed physical edges. In a CCG, however, each pair of nodes is connected by a logical edge with the minimum cost between the two nodes. One of the classical algorithms for transforming a network graph into a CCG is Floyd’s algorithm [42]. The pseudocode of the algorithm is shown in Algorithm 1. The input cost matrix of the network graph is denoted by C|VG|×|VG|, where its element cij is the cost of the edge connecting nodes i and j(i,j=1,2,…,|VG|). The output of the Floyd’s algorithm consists of two matrixes. One is the cost matrix C^|VG|×|VG| of the CCG, where the value of its elements c^ij denotes the minimum cost from node i to node j. The other is O|VG|×|VG|, where each element oij records the next node of node i on the minimum cost route from node i to node j in the network graph. Figure 2(a) presents an undirected network graph. The values in the figure indicate the cost of the corresponding physical edges. Suppose Ω=⌀ and take the edges (b1,b2) and (b1,b4) as examples. Nodes b1 and b2 are not adjacent, but they are connected via node b3 or b4 or nodes b5,b6,b4. In the CCG (Figure 2(b)), nodes b1 and b2 are logically adjacent with c^b1b2=c^b2b1=2.5 and ob1b2=ob2b1=b3. For nodes b1 and b4, although they are already adjacent, there is a shorter path via nodes b5 and b6. So c^b1b4=c^b4b1=1.5, whereas ob1b4=b5, ob4b1=b6.Algorithm 1:Pseudocode of Floyd’s algorithm.
Floyd's Algorithm
Input: C|VG|×|VG|[cij]: the cost matrix of the network graph
Output:  C^|VG|×|VG|[c^ij]: the cost matrix of the cost complete graph (CCG)
O|VG|×|VG|[oij]: records the next node on the minimum cost route
from nodei to node j
For  i:=1  to  |VG|
For  j:=1  to  |VG|
c^ij=cij;
If  cij=∞
oij:=-1;
Else
oij:=j;
End  If
End  For
End  For
For  k:=1  to  |VG|
For  i:=1  to  |VG|
For  j:=1  to  |VG|
If  i≠j  and  c^ik+c^kj<c^ij
c^ij:=c^ik+c^kj;
oij:=oik;
End  If
End  For
End  For
End  ForAn example of transforming edge (b1,b2) and edge (b1,b4) in the CCG. (a) The original undirected graph showing the physical edges and the edge cost. (b) The graph showing the transformed edges (b1,b2) and (b1,b4) and the corresponding edge cost in the CCG.
(a)
(b)The CCG of the network is obtained before the proposed MCMRACO algorithm starts. Generally, the CCG is maintained by the network routers or a central network controlling apparatus. For example, in [2], master multicast routers are used to deal with all the multicast-related tasks. They gather routing information, make MR decisions, and manage the other routers to perform MR. The proposed MCMRACO algorithm can be implemented by the master multicast router to find a high-quality multicast tree for MR.


### 2.3. Ant Colony Optimization

Once the CCG is available, the ants can be dispatched to construct multicast trees. The ants in ACO can move in parallel or sequentially to construct their solutions [18]. Before introducing the proposed algorithm, the ACO framework is briefly presented.The ACO algorithm used in this paper is ant colony system (ACS) [20], which is characterized by its state transition rule and the pheromone update mechanisms. At each iteration, a colony of ants is dispatched to search for solutions. Choosing an edge for the completion of the solution is termed a construction step. Each ant makes every construction step according to the state transition rule. After an ant makes a construction step, the local pheromone update is applied to the selected edge. The local pheromone update reduces the chances for the other ants to choose the same edge repetitively and thus ensures diversity in the search. After every ant has constructed a complete solution, the global pheromone update mechanism is applied to the edges of the best-so-far solution in order to intensify the attraction of the edges.Figure3 illustrates the ants’ behavior in one iteration by showing the local and global pheromone update operations on the edges of a graph. When the ants are moving, the pheromones on the visited edges are changed by the local pheromone update, resulting in the reduction of pheromones. After all the ants have completed their solutions, the global pheromone update reinforces the pheromones on the edges of the best-so-far solution. In a complex search environment with multiple ramifications, the previous mechanisms were shown to be able to find high-quality solutions [18].An illustration of the ants’ behavior in one iteration. The thickness of the edges denotes the pheromone density. (a) The distribution of pheromones from the last iteration. (b) When the three ants are moving, the pheromones on the passed edges are changed by the local pheromone update, resulting in the reduction of pheromones. (c) The global pheromone update reinforces the pheromones on the edges of the best-so-far solution.
(a)
(b)
(c)


## 2.1. Definition of the MCMR Optimization Problem

In an MCMR optimization problem, a network graph is denoted asG=(VG,EG), where VG is the set of nodes in the network and EG is the set of edges which connect the nodes in VG. The set VG is divided into three subsets VS, VD, and VI, where VS is the set of source nodes, VD is the set of destination nodes, and VI is the set of intermediate nodes. VM=VS∪VD is the set of nodes in a multicast group. Intermediate nodes can be used for relaying multicast traffic, but they do not belong to the multicast group. In backbone IP networks, the nodes in VG generally are routers. Each edge e∈EG has a positive cost value c(e) that measures the quality of the edge. If there is no edge between two nodes in VG, the corresponding cost is denoted as ∞. The optimization objective of the problem is to find a tree T=(VM+Vθ,Eθ) that minimizes the cost for connecting the nodes in VM and that satisfies the multicast constraints Ω. Formally, the MCMR problem is defined as
(1)minimize∑e∈Eθc(e),TsatisfiestheconstraintsinΩ,
where Vθ⊆VI is a subset of the intermediate nodes, Eθ⊆EG is a subset of the edges in the network graph.Figure1 shows an example of MR in a network with twelve nodes and some edges. Node 1 is the source node. The black solid nodes 2, 4, 6, 12 are the destination nodes. A multicast tree connecting the multicast nodes via the intermediate nodes 5 and 7 is shown in the figure. In this paper, a multicast group has only one source node and multiple destination nodes.Figure 1
An example of multicast routing. The source node and the destination nodes belong to a multicast group. The heavy black lines indicate the multicast tree.


## 2.2. Cost Complete Graph (CCG)

The network graph is usually a noncomplete but connected graph. The edges in a network graph are termed physical edges. In a CCG, however, each pair of nodes is connected by a logical edge with the minimum cost between the two nodes. One of the classical algorithms for transforming a network graph into a CCG is Floyd’s algorithm [42]. The pseudocode of the algorithm is shown in Algorithm 1. The input cost matrix of the network graph is denoted by C|VG|×|VG|, where its element cij is the cost of the edge connecting nodes i and j(i,j=1,2,…,|VG|). The output of the Floyd’s algorithm consists of two matrixes. One is the cost matrix C^|VG|×|VG| of the CCG, where the value of its elements c^ij denotes the minimum cost from node i to node j. The other is O|VG|×|VG|, where each element oij records the next node of node i on the minimum cost route from node i to node j in the network graph. Figure 2(a) presents an undirected network graph. The values in the figure indicate the cost of the corresponding physical edges. Suppose Ω=⌀ and take the edges (b1,b2) and (b1,b4) as examples. Nodes b1 and b2 are not adjacent, but they are connected via node b3 or b4 or nodes b5,b6,b4. In the CCG (Figure 2(b)), nodes b1 and b2 are logically adjacent with c^b1b2=c^b2b1=2.5 and ob1b2=ob2b1=b3. For nodes b1 and b4, although they are already adjacent, there is a shorter path via nodes b5 and b6. So c^b1b4=c^b4b1=1.5, whereas ob1b4=b5, ob4b1=b6.Algorithm 1:Pseudocode of Floyd’s algorithm.
Floyd's Algorithm
Input: C|VG|×|VG|[cij]: the cost matrix of the network graph
Output:  C^|VG|×|VG|[c^ij]: the cost matrix of the cost complete graph (CCG)
O|VG|×|VG|[oij]: records the next node on the minimum cost route
from nodei to node j
For  i:=1  to  |VG|
For  j:=1  to  |VG|
c^ij=cij;
If  cij=∞
oij:=-1;
Else
oij:=j;
End  If
End  For
End  For
For  k:=1  to  |VG|
For  i:=1  to  |VG|
For  j:=1  to  |VG|
If  i≠j  and  c^ik+c^kj<c^ij
c^ij:=c^ik+c^kj;
oij:=oik;
End  If
End  For
End  For
End  ForAn example of transforming edge (b1,b2) and edge (b1,b4) in the CCG. (a) The original undirected graph showing the physical edges and the edge cost. (b) The graph showing the transformed edges (b1,b2) and (b1,b4) and the corresponding edge cost in the CCG.
(a)
(b)The CCG of the network is obtained before the proposed MCMRACO algorithm starts. Generally, the CCG is maintained by the network routers or a central network controlling apparatus. For example, in [2], master multicast routers are used to deal with all the multicast-related tasks. They gather routing information, make MR decisions, and manage the other routers to perform MR. The proposed MCMRACO algorithm can be implemented by the master multicast router to find a high-quality multicast tree for MR.


## 2.3. Ant Colony Optimization

Once the CCG is available, the ants can be dispatched to construct multicast trees. The ants in ACO can move in parallel or sequentially to construct their solutions [18]. Before introducing the proposed algorithm, the ACO framework is briefly presented.The ACO algorithm used in this paper is ant colony system (ACS) [20], which is characterized by its state transition rule and the pheromone update mechanisms. At each iteration, a colony of ants is dispatched to search for solutions. Choosing an edge for the completion of the solution is termed a construction step. Each ant makes every construction step according to the state transition rule. After an ant makes a construction step, the local pheromone update is applied to the selected edge. The local pheromone update reduces the chances for the other ants to choose the same edge repetitively and thus ensures diversity in the search. After every ant has constructed a complete solution, the global pheromone update mechanism is applied to the edges of the best-so-far solution in order to intensify the attraction of the edges.Figure3 illustrates the ants’ behavior in one iteration by showing the local and global pheromone update operations on the edges of a graph. When the ants are moving, the pheromones on the visited edges are changed by the local pheromone update, resulting in the reduction of pheromones. After all the ants have completed their solutions, the global pheromone update reinforces the pheromones on the edges of the best-so-far solution. In a complex search environment with multiple ramifications, the previous mechanisms were shown to be able to find high-quality solutions [18].An illustration of the ants’ behavior in one iteration. The thickness of the edges denotes the pheromone density. (a) The distribution of pheromones from the last iteration. (b) When the three ants are moving, the pheromones on the passed edges are changed by the local pheromone update, resulting in the reduction of pheromones. (c) The global pheromone update reinforces the pheromones on the edges of the best-so-far solution.
(a)
(b)
(c)


## 3. ACO for Minimum Cost Multicast Routing

In this section, the minimum cost multicast routing ant colony optimization (MCMRACO) algorithm is proposed for solving the unconstrained MCMR problems. A complete flowchart of the algorithm is shown in Figure4(a).Figure 4
Flowchart of the proposed minimum cost multicast routing ant colony optimization (MCMRACO).


### 3.1. Prim’s Algorithm, Pheromone, and Heuristic Mechanisms

The ant’s construction behavior in MCMRACO is similar to the generation of a minimum spanning tree (MST) by Prim’s algorithm [41]. Suppose that V is the set of nodes in an undirected connected graph and W is a set containing only one node. The classical Prim’s algorithm continuously moves a node d from V-W to W, provided that s∈W and the cost of edge (s, d) is minimum. In the proposed algorithm, the selection criterion for the next node is not simply based on the cost of the edges but is based on the product of the pheromone and heuristic values.The pheromone and heuristic values of an edge(s,d) are denoted by τ(s,d) and η(s,d), respectively. The initial pheromone value is τ0=1/c(TKMB), where c(TKMB) is the cost of the initial tree generated by the Kou-Markowsky-Berman (KMB) method [12].The heuristic valueη(s,d) of the edge connecting nodes s and d is a function of the cost of the edge (s, d) and the type of the node d, that is
(2)η(s,d)={μc^sd,ifd∈VM1c^sd,otherwise,
where μ (μ>1) is a reinforcement rate to the nodes in the multicast group. Heuristic values represent the quality of the candidate edges. Lower cost edges in the CCG are preferred. Moreover, multicast nodes have higher probabilities to be selected than intermediate nodes. If μ→∞, the ants perform similarly to KMB, which only considers multicast nodes during the construction. If μ=1, the ants cannot differentiate multicast nodes from the intermediate nodes. So the value of μ influences the ants’ sensitivity to the multicast nodes in the network.


### 3.2. The Ants’ Search Behavior

In this subsection, we describe an ant’s search behavior step by step. The corresponding flowchart is shown in Figure4(b).Step 1 (initialization).
Initially, an antk is placed on a randomly chosen multicast node s. The visited node set of ant k is denoted by W(k)={s}. The unvisited node set is U(k)=VG-W(k). The product of the pheromone and heuristic values for every unvisited node i∈U(k) is computed as
(3)ωi=maxj∈W(k)(τ(j,i)·η(j,i)).
That is, ωi=τ(s,i)·η(s,i) as W(k)={s}. By using χi to denote the corresponding visited node that connects to node i∈U(k) with the maximum product, we have
(4)χi=argmaxj∈W(k)(τ(j,i)·η(j,i))=s.Step 2 (exploitation or exploration).
Based on the state transition rule [20], the ant probabilistically chooses to do exploitation or exploration, which is controlled by
(5)d={argmaxr∈U(k)ωr,ifq≤q0(exploitation)D,otherwise(biasedexploration),
where q0 is a predefined parameter in [0,1] controlling the proportion of exploitation to exploration, q is a uniform random number in [0, 1), and D is a random number selected according to a probability distribution as (6). If q≤q0, the ant will choose the next unvisited node d that has the maximum product of the pheromone and heuristic values. This is called the exploitation step. Otherwise, the next node d is chosen according to (6), which is called the exploration step. 									(6)pk(d)={ωd∑r∈U(k)ωr,ifd∈U(k)0,otherwise.Step 3 (edge extension and local pheromone update).
When an ant is building a solution, the pheromone values on the visited edges are reduced. After choosing the next noded, ant k moves from node s=χd to node d. Since the ant moves in the CCG, the logical edge (s, d) can be extended to a physical route 〈b0,b1,b2,…,bψ〉, where b0=s, bψ=d, bl=obl-1,d, and l=1,…,ψ-1. The edges (bi,bj) (i=0,…,ψ,j=0,…,ψ,i≠j) have the pheromones updated by
(7)τ(bi,bj)⟵(1-ρ)·τ(bi,bj)+ρ·τmin,
where ρ∈(0,1) is the pheromone evaporation rate. The larger the value of ρ, the more pheromones are evaporated on the edges that the ant has just passed. The lower boundary of the pheromone value is set as τmin=τ0 so that the updated value will not be smaller than the initial pheromone value. The unvisited nodes in b1,b2,…,bψ are marked as visited by moving them from U(k) to W(k).Step 4 (has the ant finished the mission?).
If an ant has visited all the multicast nodes (VM⊆W(k)), the ant has finished constructing a multicast tree. Otherwise, foralli∈U(k), update the values of ωi and χi as
(8)ωi⟵maxj∈{χi,b1,b2,…,bψ}(τ(j,i)·η(j,i)).χi⟵argmaxj∈{χi,b1,b2,…,bψ}(τ(j,i)·η(j,i)).
Then return to Step 2 for a further search.


### 3.3. Redundancy Trimming

After an ant has finished building a multicast tree connecting all multicast nodes, the tree must be checked for redundancy. The flowchart of this process is given in Figure5.Figure 5
Flowchart of the redundancy trimming.Firstly, apply the classical Prim’s algorithm to the visited nodes in the network graph. If the cost of the generated MST is smaller than that of the tree built by the ant, the ant’s solution is replaced by the MST.Secondly, check for useless intermediate nodes. Delete the one-degree intermediate nodes and their connected edges.


### 3.4. Global Pheromone Update

After all them ants have finished the tree construction, the ants’ solutions are evaluated and the best-so-far tree is updated. The global pheromone update is applied only to the best-so-far tree. The pheromone values on the edges (i,j) of the best-so-far (bsf) tree Tbsf are updated as
(9)τ(i,j)⟵(1-ρ)·τ(i,j)+α·Δτ,
where Δτ=1/(c(Tbsf))c(Tbsf) is the cost of Tbsf and α is the pheromone reinforcement rate with α≥ρ.Moreover, the pheromone values on some logical edges in the treeTbsf are also updated. If the extended physical route between a pair of nodes i and j(i,j∈Tbsf) is 〈b0,b1,b2,…,bψ〉, which satisfies b0=i, bψ=j, br=obr-1,j, r=1,…,ψ-1, (bl,bl+1)∈Tbsf, l=0,1,…,ψ-1, and ψ>1 is the number of edges in the route, then the new pheromone value of edge (i,j) becomes
(10)τ(i,j)⟵∑l=0ψ-1τ(bl,bl+1)ψ.
The updated pheromone value of edge (i, j) is in accordance with the average pheromone value of the corresponding physical edges in the tree.


### 3.5. The Complexity and Convergence of MCMRACO

The time complexity of the proposed MCMRACO can be estimated by counting the number of multicast trees that are generated during the optimization process. In each iteration of MCMRACO, a colony ofm ants construct m trees and the classical Prim’s algorithm is performed m times for redundancy trimming. As the time complexity for constructing a multicast tree is O(|VG|2) and 2m trees are constructed in each iteration, the time complexity of MCMRACO is approximately O(2nm|VG|2), where n is the predefined maximum iteration number.According to [43], the convergence condition for the proposed algorithm is to satisfy 0<τmin<τmax<+∞, where τmin and τmax are the lower and upper boundaries of the pheromone value, respectively. Although the heuristic and pheromone mechanisms have been redesigned in the proposed algorithm, the convergence of the algorithm is still maintained. The lower boundary of the pheromone value is τmin=τ0 > 0. The upper boundary of the pheromone value is (α/ρ)·(1/c(Topt)), where c(Topt) is the cost of the optimal tree. Furthermore, every ant in MCMRACO builds a feasible multicast solution. Therefore, the proposed MCMRACO can converge to an optimal solution.


## 3.1. Prim’s Algorithm, Pheromone, and Heuristic Mechanisms

The ant’s construction behavior in MCMRACO is similar to the generation of a minimum spanning tree (MST) by Prim’s algorithm [41]. Suppose that V is the set of nodes in an undirected connected graph and W is a set containing only one node. The classical Prim’s algorithm continuously moves a node d from V-W to W, provided that s∈W and the cost of edge (s, d) is minimum. In the proposed algorithm, the selection criterion for the next node is not simply based on the cost of the edges but is based on the product of the pheromone and heuristic values.The pheromone and heuristic values of an edge(s,d) are denoted by τ(s,d) and η(s,d), respectively. The initial pheromone value is τ0=1/c(TKMB), where c(TKMB) is the cost of the initial tree generated by the Kou-Markowsky-Berman (KMB) method [12].The heuristic valueη(s,d) of the edge connecting nodes s and d is a function of the cost of the edge (s, d) and the type of the node d, that is
(2)η(s,d)={μc^sd,ifd∈VM1c^sd,otherwise,
where μ (μ>1) is a reinforcement rate to the nodes in the multicast group. Heuristic values represent the quality of the candidate edges. Lower cost edges in the CCG are preferred. Moreover, multicast nodes have higher probabilities to be selected than intermediate nodes. If μ→∞, the ants perform similarly to KMB, which only considers multicast nodes during the construction. If μ=1, the ants cannot differentiate multicast nodes from the intermediate nodes. So the value of μ influences the ants’ sensitivity to the multicast nodes in the network.


## 3.2. The Ants’ Search Behavior

In this subsection, we describe an ant’s search behavior step by step. The corresponding flowchart is shown in Figure4(b).Step 1 (initialization).
Initially, an antk is placed on a randomly chosen multicast node s. The visited node set of ant k is denoted by W(k)={s}. The unvisited node set is U(k)=VG-W(k). The product of the pheromone and heuristic values for every unvisited node i∈U(k) is computed as
(3)ωi=maxj∈W(k)(τ(j,i)·η(j,i)).
That is, ωi=τ(s,i)·η(s,i) as W(k)={s}. By using χi to denote the corresponding visited node that connects to node i∈U(k) with the maximum product, we have
(4)χi=argmaxj∈W(k)(τ(j,i)·η(j,i))=s.Step 2 (exploitation or exploration).
Based on the state transition rule [20], the ant probabilistically chooses to do exploitation or exploration, which is controlled by
(5)d={argmaxr∈U(k)ωr,ifq≤q0(exploitation)D,otherwise(biasedexploration),
where q0 is a predefined parameter in [0,1] controlling the proportion of exploitation to exploration, q is a uniform random number in [0, 1), and D is a random number selected according to a probability distribution as (6). If q≤q0, the ant will choose the next unvisited node d that has the maximum product of the pheromone and heuristic values. This is called the exploitation step. Otherwise, the next node d is chosen according to (6), which is called the exploration step. 									(6)pk(d)={ωd∑r∈U(k)ωr,ifd∈U(k)0,otherwise.Step 3 (edge extension and local pheromone update).
When an ant is building a solution, the pheromone values on the visited edges are reduced. After choosing the next noded, ant k moves from node s=χd to node d. Since the ant moves in the CCG, the logical edge (s, d) can be extended to a physical route 〈b0,b1,b2,…,bψ〉, where b0=s, bψ=d, bl=obl-1,d, and l=1,…,ψ-1. The edges (bi,bj) (i=0,…,ψ,j=0,…,ψ,i≠j) have the pheromones updated by
(7)τ(bi,bj)⟵(1-ρ)·τ(bi,bj)+ρ·τmin,
where ρ∈(0,1) is the pheromone evaporation rate. The larger the value of ρ, the more pheromones are evaporated on the edges that the ant has just passed. The lower boundary of the pheromone value is set as τmin=τ0 so that the updated value will not be smaller than the initial pheromone value. The unvisited nodes in b1,b2,…,bψ are marked as visited by moving them from U(k) to W(k).Step 4 (has the ant finished the mission?).
If an ant has visited all the multicast nodes (VM⊆W(k)), the ant has finished constructing a multicast tree. Otherwise, foralli∈U(k), update the values of ωi and χi as
(8)ωi⟵maxj∈{χi,b1,b2,…,bψ}(τ(j,i)·η(j,i)).χi⟵argmaxj∈{χi,b1,b2,…,bψ}(τ(j,i)·η(j,i)).
Then return to Step 2 for a further search.


## 3.3. Redundancy Trimming

After an ant has finished building a multicast tree connecting all multicast nodes, the tree must be checked for redundancy. The flowchart of this process is given in Figure5.Figure 5
Flowchart of the redundancy trimming.Firstly, apply the classical Prim’s algorithm to the visited nodes in the network graph. If the cost of the generated MST is smaller than that of the tree built by the ant, the ant’s solution is replaced by the MST.Secondly, check for useless intermediate nodes. Delete the one-degree intermediate nodes and their connected edges.


## 3.4. Global Pheromone Update

After all them ants have finished the tree construction, the ants’ solutions are evaluated and the best-so-far tree is updated. The global pheromone update is applied only to the best-so-far tree. The pheromone values on the edges (i,j) of the best-so-far (bsf) tree Tbsf are updated as
(9)τ(i,j)⟵(1-ρ)·τ(i,j)+α·Δτ,
where Δτ=1/(c(Tbsf))c(Tbsf) is the cost of Tbsf and α is the pheromone reinforcement rate with α≥ρ.Moreover, the pheromone values on some logical edges in the treeTbsf are also updated. If the extended physical route between a pair of nodes i and j(i,j∈Tbsf) is 〈b0,b1,b2,…,bψ〉, which satisfies b0=i, bψ=j, br=obr-1,j, r=1,…,ψ-1, (bl,bl+1)∈Tbsf, l=0,1,…,ψ-1, and ψ>1 is the number of edges in the route, then the new pheromone value of edge (i,j) becomes
(10)τ(i,j)⟵∑l=0ψ-1τ(bl,bl+1)ψ.
The updated pheromone value of edge (i, j) is in accordance with the average pheromone value of the corresponding physical edges in the tree.


## 3.5. The Complexity and Convergence of MCMRACO

The time complexity of the proposed MCMRACO can be estimated by counting the number of multicast trees that are generated during the optimization process. In each iteration of MCMRACO, a colony ofm ants construct m trees and the classical Prim’s algorithm is performed m times for redundancy trimming. As the time complexity for constructing a multicast tree is O(|VG|2) and 2m trees are constructed in each iteration, the time complexity of MCMRACO is approximately O(2nm|VG|2), where n is the predefined maximum iteration number.According to [43], the convergence condition for the proposed algorithm is to satisfy 0<τmin<τmax<+∞, where τmin and τmax are the lower and upper boundaries of the pheromone value, respectively. Although the heuristic and pheromone mechanisms have been redesigned in the proposed algorithm, the convergence of the algorithm is still maintained. The lower boundary of the pheromone value is τmin=τ0 > 0. The upper boundary of the pheromone value is (α/ρ)·(1/c(Topt)), where c(Topt) is the cost of the optimal tree. Furthermore, every ant in MCMRACO builds a feasible multicast solution. Therefore, the proposed MCMRACO can converge to an optimal solution.


## 4. Experiments and Discussions

The experiments in this paper are composed of two parts. The first part is the experiment on the static MR cases, whereas the second part is the one on the dynamic MR cases. All the results in the experiments are computed by a computer with CPU Pentium IV 2.8 GHZ, memory 256 MB.


### 4.1. Static Multicast Routing Cases

The static MR cases are the Steiner problems in group B from the OR-Library [44]. The eighteen problems are tabulated in Table 1, with the graph size from 50 to 100. In the table, |VG| stands for the number of nodes, |VM| is the number of multicast nodes, |EG| is the number of physical edges in the graph, and c(Topt) is the cost of the optimal tree. The performance of the proposed algorithm is compared with the KMB heuristic algorithm in [12], the random neural network (RNN) algorithm in  [16], the genetic algorithm (GA) in [17], and the ant algorithm in [38].Table 1
Eighteen Steiner B test cases.
No.
|
V
G
|
|
E
G
|
|
V
M
|
c
(
T
opt
)
1
50
63
9
82
2
50
63
13
83
3
50
63
25
138
4
50
100
9
59
5
50
100
13
61
6
50
100
25
122
7
75
94
13
111
8
75
94
19
104
9
75
94
38
220
10
75
150
13
86
11
75
150
19
88
12
75
150
38
174
13
100
125
17
165
14
100
125
25
235
15
100
125
50
318
16
100
200
17
127
17
100
200
25
131
18
100
200
50
218Firstly, the parameter settings of the proposed MCMRACO algorithm are analyzed. The proposed algorithm has five parameters, which are the number of antsm, the reinforcement rate to destination nodes μ, the proportion of exploitation q0, the pheromone evaporation rate ρ, and the pheromone reinforcement rate α. The number of ants m depends on the number of nodes in the network. More ants may perform better in a large network, but it will take longer time in one iteration. If the number of ants is not enough, the algorithm may be trapped easily in suboptimal results. The value m=50 is suitable for most of the networks in our empirical study.The other four parametersμ, q0, ρ, and  α are analyzed by testing μ=5,6,…,19, q0=0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.85, 0.9, 0.95, ρ=0.1,0.2,…,0.5, and α=0.1,0.2,…,1.1 with α≥ρ. Each combination of parameter values (μ,q0,ρ,α) is termed a parameter configuration. Each configuration is tested in ten independent runs by MCMRACO on each of the eighteen instances. Each run of MCMRACO terminates when it cannot find a better result in three consecutive iterations. The performance of MCMRACO by configuration θ on instance i is measured as
(11)Θ(θ,i)=100σ-t-,
where σ is the successful percentage and t- denotes the average time in seconds of the ten independent runs by configuration θ on instance i for obtaining the optimal solution.Figure6 shows the average performance of MCMRACO with different parameter values in solving some static MR instances. Each point in the figure is drawn as follows. For example, the total measurements of the performance Θ for μ=5 of B9 are 31235.4. When μ equals to 5, there are 10 choices for q0 and 45 choices for the combinations of (ρ,α). So the total configuration number of (μ, q0, ρ, α) with μ=5 is 450. The average measurement of performance Θ for μ=5 of B9 is thus computed as 31235.4/450=69.412, which has been plotted as a point in Figure 6(a). Only the instances that cannot be solved successfully by the KMB algorithm are considered in the figure. The curves show that the parameter values have similar influences on different instances. (1) The successful percentage increases when the value of μ becomes bigger. It means that the ants should have a strong bias towards the multicast nodes. (2) The desirable value of q0 is in the range of [0.6,0.9]. The results indicate that the probability for performing exploitation is better to be higher than that of the exploration. (3) With α≥ρ, the influences for choosing different values of α and ρ are quite small for the same instance.Average performance of MCMRACO with different parameter values in solving the static MR cases. (a) Average value ofΘ with μ=5,6,…,19. (b) Average value of Θ with q0 = 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.85, 0.9, 0.95. (c) Average value of Θ with ρ=0.1,0.2,…,0.5. (d) Average value of Θ with α=0.1,0.2,…,1.1.
(a)
(b)
(c)
(d)After analyzing the influence of different parameter values, the values of the four parametersμ, q0, ρ, and α are selected based on a statistically sound approach, that is, a racing algorithm termed F-Race [45]. According to the results by F-Race, the parameter values of the proposed MCMRACO are set as m=50, μ=19, q0=0.8, ρ=0.3, and α=0.5.The results for solving the Steiner B instances are tabulated in Table2. As there is no stochastic factor in KMB and RNN, the results are unique in different runs. The ant algorithm in [38], the GA in [17], and the proposed MCMRACO are probabilistic algorithms, so they are tested ten times independently for each instance. If the results are equal to the optima, they are bold in the table.Table 2
Optimization results for the static experiment.
No.
c
(
T
opt
)
KMB
RNN
Ant
GA
MCMRACO
Best
Mean
Best
Mean
Best
Mean
1
82
82
82
82
82
82
82
82
82
2
83
88
83
83
83
83
83
83
83
3
138
138
138
138
138
138
138
138
138
4
59
64
59
59
59
59
59
59
59
5
61
61
61
61
61
61
61
61
61
6
122
127
122
—
—
122
122
122
122
7
111
111
111
—
—
111
111
111
111
8
104
104
104
104
104
104
104
104
104
9
220
221
220
220
220
220
220
220
220
10
86
91
87
86
87.4
86
86
86
86
11
88
92
90
88
89
88
88.2
88
88
12
174
174
174
—
—
174
174
174
174
13
165
175
175
165
167.3
165
165.8
165
165
14
235
237
237
235
235.3
235
237.3
235
235
15
318
318
318
318
318
318
318.6
318
318
16
127
135
135
132
133
127
127.3
127
127
17
131
134
132
—
—
131
131.1
131
131
18
218
221
219
224
225.5
218
218.4
218
218The results show that KMB only solves seven instances successfully, whereas RNN obtains eleven successful results out of the eighteen instances. The ant algorithm in [37] can find the best multicast trees of the instances at least once except for B16 and B18. However, it can only achieve 100% success in eight instances. GA terminates when it cannot find a better result in twenty consecutive generations with a population size of 50. Note that the termination condition of GA is more stringent than the one used in [17] but is looser than that of MCMRACO. The results show that GA can find the optima of all the eighteen instances, but it can only solve eleven instances with 100% success. The proposed MCMRACO has the best performance among the algorithms, for it can solve all the static instances with 100% success. To further study the performance of the algorithms, a dynamic environment is designed in the next subsection.


### 4.2. Dynamic Multicast Routing Cases

Nodes in the network may join or leave the multicast group. Suppose the network topology is stable without failure. We design the following dynamic scenario to test the stability of the algorithm. When the multicast nodes are changed, the algorithm is invoked to find a new multicast tree.Suppose thatv multicast nodes in the multicast group leave and v new nodes join the group alternatively, forming a dynamic situation. Note that the nodes in the multicast group remain unchanged when the algorithm is still running. Initially, there is a network G=(VG,EG) including a multicast group VM(0)⊆VG. At time 1, v multicast nodes are chosen randomly to become intermediate nodes, indicating that v nodes leave the multicast group. Then the multicast group becomes VM(1)=VM(0)-ΔVM(1) and a multicast tree T(1) is computed. At time 2, v intermediate nodes are chosen randomly to become multicast nodes, indicating that v nodes join the multicast group. Then the multicast group becomes VM(2)=VM(1)+ΔVI(2) and a new multicast tree T(2) is computed. Given the value of v, the nodes in the multicast group are changed 2K times and the objective of the experiment is to minimize the total cost of the multicast trees. The formal definition is
(12)Φv=min∑i=12K∑e∈E(i)c(e),T(i)=(VM(i)+Vθ(i),E(i)),i=1,2,…,2K,VM(i)=VM(i-1)-ΔVM(i),ifi=1,3,5,…,2K-1,VM(i)=VM(i-1)+ΔVI(i),ifi=2,4,6,…,2K,
where Vθ(i)⊆VG-VM(i), E(i)⊆EG. ΔVM(i) is the set of the v randomly chosen multicast nodes to leave the multicast group when i=1,3,5,…,2K-1. ΔVI(i) is the set of the v randomly chosen intermediate nodes to join the multicast group when i=2,4,6,…,2K.There are eighteen dynamic multicast routing instances, which use the static Steiner B instances as their initial MR networks, respectively. For each instance, the valuesv=1,2,…,|VM|-3 are tested. When the value of v grows, the multicast group becomes more and more unstable.The proposed MCMRACO takes advantage of pheromones to encode a memory about the ants’ search process. After the search for a multicast tree is finished, the pheromones are still maintained in the network, reflecting the previous routing information. Once the multicast nodes are changed, the ants’ construction is restarted. The pheromones still bias the ants to select the previous edges. As the ants reduce pheromones on edges by the local pheromone update, the influences of the obsolete routing information decrease.The results of the summation cost of the 2K multicast trees, which are computed by MCMRACO, RNN, and GA, are denoted by Φv(M), Φv(R), and Φv(G), respectively. The comparison result of the tree cost between RNN and MCMRACO is denoted by δ(R), whereas the one between GA and MCMRACO is denoted by δ(G). The definitions of δ(R) and δ(G) are
(13)δ(R)=Φv(R)-Φv(M)Φv(M),δ(G)=Φv(G)-Φv(M)Φv(M).Table3 lists the tree cost of MCMRACO and the comparison results of the eighteen initial MR networks when v=1, ⌊(|VM|-3)/2+1⌋, |VM|-3, and K=100. As the comparison results are all positive, the proposed MCMRACO can obtain multicast trees with less cost than RNN and GA. Figure 7 shows the comparison results of the tree cost with B18 as the initial MR network when the values of v are changed from 1 to 47. The differences between RNN and MCMRACO are always larger than those between GA and MCMRACO. The figure presents that the proposed MCMRACO can steadily achieve better results than RNN and GA.Table 3
Comparison results of the tree cost for the dynamic experiment.
No.
v
Φ
v
(
M
)
δ
(
R
)
δ
(
G
)
1
1
16381
1.33%
0.00%
4
12570
0.99%
0.00%
6
10426
0.55%
0.00%
2
1
17345
1.32%
0.00%
6
17553
1.88%
0.01%
10
14399
1.51%
0.03%
3
1
25656
0.27%
0.00%
12
23588
0.45%
0.01%
22
17162
0.41%
0.02%
4
1
10756
1.78%
0.01%
4
9243
1.36%
0.02%
6
7736
1.31%
0.00%
5
1
12687
1.14%
0.00%
6
10374
1.33%
0.03%
10
8320
0.91%
0.02%
6
1
22206
0.43%
0.04%
12
18168
0.62%
0.04%
22
13142
0.69%
0.02%
7
1
22392
0.64%
0.02%
6
18322
1.66%
0.04%
10
14574
1.22%
0.06%
8
1
25664
1.48%
0.00%
9
22945
1.16%
0.02%
16
17236
0.68%
0.02%
9
1
44687
0.41%
0.01%
18
38390
0.51%
0.02%
35
26371
0.40%
0.04%
10
1
16525
1.11%
0.11%
6
13361
2.63%
0.08%
10
10803
2.02%
0.19%
11
1
16823
0.81%
0.08%
9
15501
1.90%
0.19%
16
11748
2.03%
0.14%
12
1
31642
0.63%
0.02%
18
27443
0.89%
0.08%
35
19069
0.79%
0.06%
13
1
30795
1.90%
0.25%
8
25326
3.03%
0.08%
14
21049
2.91%
0.11%
14
1
40368
0.97%
0.13%
12
33929
1.45%
0.18%
22
24475
1.03%
0.24%
15
1
62009
0.84%
0.09%
24
52308
1.13%
0.10%
47
35118
0.81%
0.06%
16
1
19557
1.71%
0.25%
8
17001
2.06%
0.38%
14
13228
1.81%
0.26%
17
1
24107
1.08%
0.17%
12
18215
1.18%
0.15%
22
13003
1.12%
0.20%
18
1
45115
0.68%
0.23%
24
36000
0.67%
0.27%
47
24589
0.69%
0.15%Figure 7
Comparison results of the tree cost between RNN and MCMRACO and between GA and MCMRACO with different values ofv when the initial MR network is B18.When the multicast group is changed, the time used for finding the solution is the response delay. The time needed by RNN is determined by its enumeration subset. The smaller the multicast group, the more nodes that may be used for enumeration, resulting in longer computation time. However, for GA and MCMRACO, the time used for a small group is generally shorter than a large group in the same termination condition. Figure8 illustrates the average time used by RNN, GA, and MCMRACO with different values of v when the initial multicast network is B18. The curves show that the average time needed by GA and MCMRACO reduces as the value of v becomes bigger, but the time used by RNN is growing upwards.Figure 8
Average time delay of RNN, GA, and MCMRACO with different values ofv when the initial MR network is B18.Table4 tabulates the average time used for finding a multicast solution in the 18 instances when =1,⌊(|VM|-3)/2+1⌋, |VM|-3. Although the average time used by RNN is shorter than that of MCMRACO in some cases, the results obtained by MCMRACO are always better than those of RNN (as Table 3). Moreover, MCMRACO performs faster than RNN in instances Nos. 7, 10, 13, 14, 16, and 17. For GA and MCMRACO, the results show that even if GA takes longer time than MCMRACO, the results obtained by GA are still worse than those of the proposed algorithm. For example, the proposed MCMRACO uses only 7.42 microseconds (ms) on average to find the result of instance No. 1 when v=1, whereas the GA needs 17.42 ms. For the instance No. 18 when v=47, the proposed MCMRACO uses only 29.61 ms to obtain the result, whereas GA needs 70.00 ms and the result is still 0.15% worse than the proposed algorithm. Overall, the proposed MCMRACO performs better than RNN and GA in solving the MCMR problems.Table 4
Computation time delay for the dynamic experiment.
No.
v
Time (microsecond)
RNN
GA
MCMRACO
1
1
4.69
17.42
7.42
4
5.00
15.08
5.39
6
5.08
14.07
5.00
2
1
4.38
19.92
8.60
6
4.61
18.60
7.34
10
4.85
16.80
6.02
3
1
3.05
33.05
14.06
12
3.52
28.83
12.27
22
4.22
23.44
8.91
4
1
5.08
16.88
6.10
4
5.32
15.00
4.92
6
5.39
14.30
4.30
5
1
4.69
20.71
8.44
6
5.00
18.05
7.03
10
5.16
16.17
5.47
6
1
3.36
35.78
13.91
12
3.91
29.77
11.80
22
4.45
23.91
8.52
7
1
15.08
27.42
13.28
6
15.55
24.61
11.25
10
16.02
22.03
8.91
8
1
13.75
36.25
17.42
9
14.53
31.33
15.08
16
15.47
26.80
11.48
9
1
9.14
68.05
30.16
18
10.94
56.48
26.56
35
13.05
43.91
18.29
10
1
15.63
27.74
11.88
6
16.10
24.54
10.00
10
16.64
22.11
7.89
11
1
14.38
35.86
15.86
9
15.16
31.80
14.22
16
15.86
26.96
10.71
12
1
10.47
68.44
28.99
18
12.11
56.72
24.92
35
13.99
44.38
17.50
13
1
40.16
42.11
22.74
8
36.48
36.25
19.69
14
38.20
32.97
16.49
14
1
31.10
59.85
33.60
12
33.05
49.84
27.50
22
35.40
40.94
20.16
15
1
21.95
116.88
51.80
24
26.02
91.96
45.32
47
30.31
69.92
30.39
16
1
35.08
42.50
21.18
8
36.33
38.52
18.68
14
37.50
33.36
14.53
17
1
31.64
58.44
30.47
12
33.75
47.74
25.63
22
35.78
39.46
18.36
18
1
22.27
121.09
53.44
24
27.11
91.10
42.50
47
31.49
70.00
29.61


## 4.1. Static Multicast Routing Cases

The static MR cases are the Steiner problems in group B from the OR-Library [44]. The eighteen problems are tabulated in Table 1, with the graph size from 50 to 100. In the table, |VG| stands for the number of nodes, |VM| is the number of multicast nodes, |EG| is the number of physical edges in the graph, and c(Topt) is the cost of the optimal tree. The performance of the proposed algorithm is compared with the KMB heuristic algorithm in [12], the random neural network (RNN) algorithm in  [16], the genetic algorithm (GA) in [17], and the ant algorithm in [38].Table 1
Eighteen Steiner B test cases.
No.
|
V
G
|
|
E
G
|
|
V
M
|
c
(
T
opt
)
1
50
63
9
82
2
50
63
13
83
3
50
63
25
138
4
50
100
9
59
5
50
100
13
61
6
50
100
25
122
7
75
94
13
111
8
75
94
19
104
9
75
94
38
220
10
75
150
13
86
11
75
150
19
88
12
75
150
38
174
13
100
125
17
165
14
100
125
25
235
15
100
125
50
318
16
100
200
17
127
17
100
200
25
131
18
100
200
50
218Firstly, the parameter settings of the proposed MCMRACO algorithm are analyzed. The proposed algorithm has five parameters, which are the number of antsm, the reinforcement rate to destination nodes μ, the proportion of exploitation q0, the pheromone evaporation rate ρ, and the pheromone reinforcement rate α. The number of ants m depends on the number of nodes in the network. More ants may perform better in a large network, but it will take longer time in one iteration. If the number of ants is not enough, the algorithm may be trapped easily in suboptimal results. The value m=50 is suitable for most of the networks in our empirical study.The other four parametersμ, q0, ρ, and  α are analyzed by testing μ=5,6,…,19, q0=0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.85, 0.9, 0.95, ρ=0.1,0.2,…,0.5, and α=0.1,0.2,…,1.1 with α≥ρ. Each combination of parameter values (μ,q0,ρ,α) is termed a parameter configuration. Each configuration is tested in ten independent runs by MCMRACO on each of the eighteen instances. Each run of MCMRACO terminates when it cannot find a better result in three consecutive iterations. The performance of MCMRACO by configuration θ on instance i is measured as
(11)Θ(θ,i)=100σ-t-,
where σ is the successful percentage and t- denotes the average time in seconds of the ten independent runs by configuration θ on instance i for obtaining the optimal solution.Figure6 shows the average performance of MCMRACO with different parameter values in solving some static MR instances. Each point in the figure is drawn as follows. For example, the total measurements of the performance Θ for μ=5 of B9 are 31235.4. When μ equals to 5, there are 10 choices for q0 and 45 choices for the combinations of (ρ,α). So the total configuration number of (μ, q0, ρ, α) with μ=5 is 450. The average measurement of performance Θ for μ=5 of B9 is thus computed as 31235.4/450=69.412, which has been plotted as a point in Figure 6(a). Only the instances that cannot be solved successfully by the KMB algorithm are considered in the figure. The curves show that the parameter values have similar influences on different instances. (1) The successful percentage increases when the value of μ becomes bigger. It means that the ants should have a strong bias towards the multicast nodes. (2) The desirable value of q0 is in the range of [0.6,0.9]. The results indicate that the probability for performing exploitation is better to be higher than that of the exploration. (3) With α≥ρ, the influences for choosing different values of α and ρ are quite small for the same instance.Average performance of MCMRACO with different parameter values in solving the static MR cases. (a) Average value ofΘ with μ=5,6,…,19. (b) Average value of Θ with q0 = 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.85, 0.9, 0.95. (c) Average value of Θ with ρ=0.1,0.2,…,0.5. (d) Average value of Θ with α=0.1,0.2,…,1.1.
(a)
(b)
(c)
(d)After analyzing the influence of different parameter values, the values of the four parametersμ, q0, ρ, and α are selected based on a statistically sound approach, that is, a racing algorithm termed F-Race [45]. According to the results by F-Race, the parameter values of the proposed MCMRACO are set as m=50, μ=19, q0=0.8, ρ=0.3, and α=0.5.The results for solving the Steiner B instances are tabulated in Table2. As there is no stochastic factor in KMB and RNN, the results are unique in different runs. The ant algorithm in [38], the GA in [17], and the proposed MCMRACO are probabilistic algorithms, so they are tested ten times independently for each instance. If the results are equal to the optima, they are bold in the table.Table 2
Optimization results for the static experiment.
No.
c
(
T
opt
)
KMB
RNN
Ant
GA
MCMRACO
Best
Mean
Best
Mean
Best
Mean
1
82
82
82
82
82
82
82
82
82
2
83
88
83
83
83
83
83
83
83
3
138
138
138
138
138
138
138
138
138
4
59
64
59
59
59
59
59
59
59
5
61
61
61
61
61
61
61
61
61
6
122
127
122
—
—
122
122
122
122
7
111
111
111
—
—
111
111
111
111
8
104
104
104
104
104
104
104
104
104
9
220
221
220
220
220
220
220
220
220
10
86
91
87
86
87.4
86
86
86
86
11
88
92
90
88
89
88
88.2
88
88
12
174
174
174
—
—
174
174
174
174
13
165
175
175
165
167.3
165
165.8
165
165
14
235
237
237
235
235.3
235
237.3
235
235
15
318
318
318
318
318
318
318.6
318
318
16
127
135
135
132
133
127
127.3
127
127
17
131
134
132
—
—
131
131.1
131
131
18
218
221
219
224
225.5
218
218.4
218
218The results show that KMB only solves seven instances successfully, whereas RNN obtains eleven successful results out of the eighteen instances. The ant algorithm in [37] can find the best multicast trees of the instances at least once except for B16 and B18. However, it can only achieve 100% success in eight instances. GA terminates when it cannot find a better result in twenty consecutive generations with a population size of 50. Note that the termination condition of GA is more stringent than the one used in [17] but is looser than that of MCMRACO. The results show that GA can find the optima of all the eighteen instances, but it can only solve eleven instances with 100% success. The proposed MCMRACO has the best performance among the algorithms, for it can solve all the static instances with 100% success. To further study the performance of the algorithms, a dynamic environment is designed in the next subsection.


## 4.2. Dynamic Multicast Routing Cases

Nodes in the network may join or leave the multicast group. Suppose the network topology is stable without failure. We design the following dynamic scenario to test the stability of the algorithm. When the multicast nodes are changed, the algorithm is invoked to find a new multicast tree.Suppose thatv multicast nodes in the multicast group leave and v new nodes join the group alternatively, forming a dynamic situation. Note that the nodes in the multicast group remain unchanged when the algorithm is still running. Initially, there is a network G=(VG,EG) including a multicast group VM(0)⊆VG. At time 1, v multicast nodes are chosen randomly to become intermediate nodes, indicating that v nodes leave the multicast group. Then the multicast group becomes VM(1)=VM(0)-ΔVM(1) and a multicast tree T(1) is computed. At time 2, v intermediate nodes are chosen randomly to become multicast nodes, indicating that v nodes join the multicast group. Then the multicast group becomes VM(2)=VM(1)+ΔVI(2) and a new multicast tree T(2) is computed. Given the value of v, the nodes in the multicast group are changed 2K times and the objective of the experiment is to minimize the total cost of the multicast trees. The formal definition is
(12)Φv=min∑i=12K∑e∈E(i)c(e),T(i)=(VM(i)+Vθ(i),E(i)),i=1,2,…,2K,VM(i)=VM(i-1)-ΔVM(i),ifi=1,3,5,…,2K-1,VM(i)=VM(i-1)+ΔVI(i),ifi=2,4,6,…,2K,
where Vθ(i)⊆VG-VM(i), E(i)⊆EG. ΔVM(i) is the set of the v randomly chosen multicast nodes to leave the multicast group when i=1,3,5,…,2K-1. ΔVI(i) is the set of the v randomly chosen intermediate nodes to join the multicast group when i=2,4,6,…,2K.There are eighteen dynamic multicast routing instances, which use the static Steiner B instances as their initial MR networks, respectively. For each instance, the valuesv=1,2,…,|VM|-3 are tested. When the value of v grows, the multicast group becomes more and more unstable.The proposed MCMRACO takes advantage of pheromones to encode a memory about the ants’ search process. After the search for a multicast tree is finished, the pheromones are still maintained in the network, reflecting the previous routing information. Once the multicast nodes are changed, the ants’ construction is restarted. The pheromones still bias the ants to select the previous edges. As the ants reduce pheromones on edges by the local pheromone update, the influences of the obsolete routing information decrease.The results of the summation cost of the 2K multicast trees, which are computed by MCMRACO, RNN, and GA, are denoted by Φv(M), Φv(R), and Φv(G), respectively. The comparison result of the tree cost between RNN and MCMRACO is denoted by δ(R), whereas the one between GA and MCMRACO is denoted by δ(G). The definitions of δ(R) and δ(G) are
(13)δ(R)=Φv(R)-Φv(M)Φv(M),δ(G)=Φv(G)-Φv(M)Φv(M).Table3 lists the tree cost of MCMRACO and the comparison results of the eighteen initial MR networks when v=1, ⌊(|VM|-3)/2+1⌋, |VM|-3, and K=100. As the comparison results are all positive, the proposed MCMRACO can obtain multicast trees with less cost than RNN and GA. Figure 7 shows the comparison results of the tree cost with B18 as the initial MR network when the values of v are changed from 1 to 47. The differences between RNN and MCMRACO are always larger than those between GA and MCMRACO. The figure presents that the proposed MCMRACO can steadily achieve better results than RNN and GA.Table 3
Comparison results of the tree cost for the dynamic experiment.
No.
v
Φ
v
(
M
)
δ
(
R
)
δ
(
G
)
1
1
16381
1.33%
0.00%
4
12570
0.99%
0.00%
6
10426
0.55%
0.00%
2
1
17345
1.32%
0.00%
6
17553
1.88%
0.01%
10
14399
1.51%
0.03%
3
1
25656
0.27%
0.00%
12
23588
0.45%
0.01%
22
17162
0.41%
0.02%
4
1
10756
1.78%
0.01%
4
9243
1.36%
0.02%
6
7736
1.31%
0.00%
5
1
12687
1.14%
0.00%
6
10374
1.33%
0.03%
10
8320
0.91%
0.02%
6
1
22206
0.43%
0.04%
12
18168
0.62%
0.04%
22
13142
0.69%
0.02%
7
1
22392
0.64%
0.02%
6
18322
1.66%
0.04%
10
14574
1.22%
0.06%
8
1
25664
1.48%
0.00%
9
22945
1.16%
0.02%
16
17236
0.68%
0.02%
9
1
44687
0.41%
0.01%
18
38390
0.51%
0.02%
35
26371
0.40%
0.04%
10
1
16525
1.11%
0.11%
6
13361
2.63%
0.08%
10
10803
2.02%
0.19%
11
1
16823
0.81%
0.08%
9
15501
1.90%
0.19%
16
11748
2.03%
0.14%
12
1
31642
0.63%
0.02%
18
27443
0.89%
0.08%
35
19069
0.79%
0.06%
13
1
30795
1.90%
0.25%
8
25326
3.03%
0.08%
14
21049
2.91%
0.11%
14
1
40368
0.97%
0.13%
12
33929
1.45%
0.18%
22
24475
1.03%
0.24%
15
1
62009
0.84%
0.09%
24
52308
1.13%
0.10%
47
35118
0.81%
0.06%
16
1
19557
1.71%
0.25%
8
17001
2.06%
0.38%
14
13228
1.81%
0.26%
17
1
24107
1.08%
0.17%
12
18215
1.18%
0.15%
22
13003
1.12%
0.20%
18
1
45115
0.68%
0.23%
24
36000
0.67%
0.27%
47
24589
0.69%
0.15%Figure 7
Comparison results of the tree cost between RNN and MCMRACO and between GA and MCMRACO with different values ofv when the initial MR network is B18.When the multicast group is changed, the time used for finding the solution is the response delay. The time needed by RNN is determined by its enumeration subset. The smaller the multicast group, the more nodes that may be used for enumeration, resulting in longer computation time. However, for GA and MCMRACO, the time used for a small group is generally shorter than a large group in the same termination condition. Figure8 illustrates the average time used by RNN, GA, and MCMRACO with different values of v when the initial multicast network is B18. The curves show that the average time needed by GA and MCMRACO reduces as the value of v becomes bigger, but the time used by RNN is growing upwards.Figure 8
Average time delay of RNN, GA, and MCMRACO with different values ofv when the initial MR network is B18.Table4 tabulates the average time used for finding a multicast solution in the 18 instances when =1,⌊(|VM|-3)/2+1⌋, |VM|-3. Although the average time used by RNN is shorter than that of MCMRACO in some cases, the results obtained by MCMRACO are always better than those of RNN (as Table 3). Moreover, MCMRACO performs faster than RNN in instances Nos. 7, 10, 13, 14, 16, and 17. For GA and MCMRACO, the results show that even if GA takes longer time than MCMRACO, the results obtained by GA are still worse than those of the proposed algorithm. For example, the proposed MCMRACO uses only 7.42 microseconds (ms) on average to find the result of instance No. 1 when v=1, whereas the GA needs 17.42 ms. For the instance No. 18 when v=47, the proposed MCMRACO uses only 29.61 ms to obtain the result, whereas GA needs 70.00 ms and the result is still 0.15% worse than the proposed algorithm. Overall, the proposed MCMRACO performs better than RNN and GA in solving the MCMR problems.Table 4
Computation time delay for the dynamic experiment.
No.
v
Time (microsecond)
RNN
GA
MCMRACO
1
1
4.69
17.42
7.42
4
5.00
15.08
5.39
6
5.08
14.07
5.00
2
1
4.38
19.92
8.60
6
4.61
18.60
7.34
10
4.85
16.80
6.02
3
1
3.05
33.05
14.06
12
3.52
28.83
12.27
22
4.22
23.44
8.91
4
1
5.08
16.88
6.10
4
5.32
15.00
4.92
6
5.39
14.30
4.30
5
1
4.69
20.71
8.44
6
5.00
18.05
7.03
10
5.16
16.17
5.47
6
1
3.36
35.78
13.91
12
3.91
29.77
11.80
22
4.45
23.91
8.52
7
1
15.08
27.42
13.28
6
15.55
24.61
11.25
10
16.02
22.03
8.91
8
1
13.75
36.25
17.42
9
14.53
31.33
15.08
16
15.47
26.80
11.48
9
1
9.14
68.05
30.16
18
10.94
56.48
26.56
35
13.05
43.91
18.29
10
1
15.63
27.74
11.88
6
16.10
24.54
10.00
10
16.64
22.11
7.89
11
1
14.38
35.86
15.86
9
15.16
31.80
14.22
16
15.86
26.96
10.71
12
1
10.47
68.44
28.99
18
12.11
56.72
24.92
35
13.99
44.38
17.50
13
1
40.16
42.11
22.74
8
36.48
36.25
19.69
14
38.20
32.97
16.49
14
1
31.10
59.85
33.60
12
33.05
49.84
27.50
22
35.40
40.94
20.16
15
1
21.95
116.88
51.80
24
26.02
91.96
45.32
47
30.31
69.92
30.39
16
1
35.08
42.50
21.18
8
36.33
38.52
18.68
14
37.50
33.36
14.53
17
1
31.64
58.44
30.47
12
33.75
47.74
25.63
22
35.78
39.46
18.36
18
1
22.27
121.09
53.44
24
27.11
91.10
42.50
47
31.49
70.00
29.61


## 5. Conclusion

This paper proposes a minimum cost multicast routing ant colony optimization (MCMRACO) algorithm for solving the minimum cost multicast routing (MCMR) problems. Different from the traditional algorithms for MCMR, the proposed MCMRACO utilizes the ant colony optimization (ACO) technique to search for an optimal multicast tree in the network graph. The artificial ants in the algorithm are based on a modified Prim’s algorithm to build a tree. The heuristic information represents problem-specific knowledge for the ants to construct solutions, whereas the pheromones on edges reserve the previous routing information. By designing effective heuristic and pheromone mechanisms, the proposed MCMRACO is very competitive for solving MCMR problems. The performance of MCMRACO has been compared with the published results available in the literature. The comparison results show that the proposed MCMRACO works successfully in both static and dynamic MCMR cases. The proposed algorithm is protocol independent so that it can be implemented conveniently in different network environments. Extending the proposed algorithm to heterogeneous networks is a promising future research topic.



---

*Source: 432686-2013-05-12.xml*