رشد درخت مبتنی بر الگوریتم کلونی مورچه ها برای مشکل مسیریابی چند پخشی

QoS multicast routing is a non-linear combinatorial optimization problem. It tries to find a multicast routing tree with minimal cost that can satisfy constraints such as bandwidth, delay, and delay jitter. This problem is NP-complete. The solution to such problems is often to search first for paths from the source node to each destination node and then integrate these paths into a multicast tree. Such a method, however, is slow and complex. To overcome these shortcomings, we propose a new method for tree-based optimization. Our algorithm optimizes the multicast tree directly, unlike the conventional solutions to finding paths and integrating them to generate a multicast tree. It applies ant colony optimization to control the tree growth in order to generate a multicast tree. Via orthogonal experiments, the most efficient combination of various parameters is selected so that the quality of optimization is improved. We then evaluate the performance and efficiency of the proposed algorithm in comparison with other existing algorithms. Simulation results show that our algorithm performs well in searching, converging speed and adaptability scale.

The rapid development of network technology and multimedia technology gradually enables network multimedia services such as computer conferencing, distance education, and coordinative work to become mainstream Internet activities. Multicasting is very convenient for these services, which usually have strict requirements of QoS (Quality of Service) parameters like bandwidth, delay, jitter and so on. In addition, as there is larger variation of parameters like bandwidth, delay and loss rate on wireless network studies of QoS multicast on wireless network is becoming a hotspot (Chiang et al., 2009, De Rango et al., 2009, Huang and Liu, 2009, Junhai et al., 2009, Su et al., 2008 and Zeng et al., 2009). Therefore, it is an important and urgent research problem to set up multicast routing quickly and with high QoS. The support of multipoint connections for multimedia applications requires the development of efficient multicast routing algorithms. Multicast routing is to find a tree which is rooted in source node and connects with all multicast destination nodes. Multicast employs a tree structure of the network to efficiently deliver the same data stream to a group of receivers. In multicast routing, one or more constraints must be applied to the entire tree. The main goal in developing multicast routing algorithm is to minimize the communication resources used by the multicast session. This is achieved by minimizing the cost of the multicast tree (Cheng et al., 2006, Gong et al., 2007 and Raghavan et al., 1999), which is the sum of the costs of the edges in the multicast tree. The least cost tree can be formalized as a Steiner problem (Hakimi, 1971 and Hwang et al., 1992). In other words, to solve the Steiner tree problem is to find the least-cost multicast tree. In addition to the Steiner tree problem, several well-known multicast routing problems have also been studied. For instance, delay-constrained least-cost multicast routing belongs to the class of tree-constrained optimization problems. Finding either a Steiner tree or a constrained Steiner tree is NP-complete (Karp, 1972). In this paper, we consider a multi-constrained least-cost multicast routing more complex than the above mentioned problems. It is NP-complete, too. For the purpose of clarity, in this paper we establish a least-cost tree with four constraints: bandwidth constraint in all the links of the tree, end-to-end delay, loss ratio constraint from the source node to each of the destinations, and delay jitter constraint of the tree. Since deterministic heuristic algorithms for QoS multicast routing are usually very slow, methods based on computational intelligence such as meta-heuristic algorithms may be more suitable. In recent years, many scholars have adopted meta-heuristic algorithms such as ant colony algorithm (Cheng et al., 2006, Gong et al., 2007, Lu and Liu, 2000, Mullen et al., 2009 and Raghavan et al., 1999), genetic algorithm (Haghighat et al., 2004 and Zhou et al., 2009), and tabu search algorithm (Ghaboosi & Haghighat, 2007) to solve multi-constrained QoS routing problems and have made some important findings. The purpose of the genetic algorithm used by Haghighat et al. (2004) is to find a multicast tree satisfying the constraints of bandwidth and delay with least cost. This algorithm has three operators: selection, crossover, and mutation. Individuals are stored in connective matrixes, adopting binary system coding. The initial colony is generated randomly without considering QoS constraints. The operation of selection adopts roulette algorithm to select good individuals from the parent generation to pass on to child generation. Two crossovers are used. The penalty function thought is adopted to solve QoS constraints in the multicast trees which do not satisfy QoS constraints. The results show that the algorithm has good performance. Ghaboosi and Haghighat propose a tabu search method (Ghaboosi & Haghighat, 2007) to look for the multicast tree with least cost which satisfies the constraints of bandwidth and delay. This algorithm obtains a complete graph of all group members at the initial step and obtains the initial Steiner tree via the generated tree of the complete graph. And on this basis, k shortest paths replace the edges to find chances of getting better results. Gong et al. (2007) use ant colony algorithm to find a multicast tree with least cost satisfying the constraints of bandwidth, delay, and delay jitter. The process of searching for a multicast tree consists of finding the shortest path from the source to destination nodes and then merging into the tree. Many ants are sent out to search for the path. The optimal paths are then selected from those paths. Pheromones are updated on the basis of the optimal path. The edge connecting the current node and meanwhile satisfying QoS constraints can become candidate edge. The tree obtained by following the abovementioned steps is a multicast tree satisfying multi-constraints. Lu and Liu (2000) use ant colony algorithm to find a multicast tree with least cost satisfying the constraints of delay and delay jitter. The process of searching multicast tree adopts a similar mode of looking for the shortest path from the source node to the destination node. A multicast tree is generated when the search process ends. There is no need of merging trees and pruning. Pheromones are updated according to the cost value of paths obtained from source to destination nodes. These algorithms, when examined carefully, have both strong and weak points. Among them, ant colony algorithm is widely adopted for its features of being robust, parallel, and flexible, and it needs no intervention and has high precision. The ant colony algorithm, however, has high demand for parameter setting in large scale optimization. If the setting of parameter is improper it is liable for local optimization. The most obvious weakness of ant colony algorithm is it converges slowly at the initial step and takes more time to converge (Dorigo, Maniezzo, & Colorni, 1996). To overcome those setbacks researchers have been working to improve this algorithm (Dorigo & Di Caro, 1999). For example, they propose radically based self-adaptive ant colony algorithm (Katja & Ann, 2002), ant colony algorithm via mutation and dynamic pheromone updating strategies (Yang, Shi, Marchese, & Liang, 2008), and maximal and minimal ant colony algorithm (Sttzle & Hoos, 2000). Owing to the complexity of network environment, these algorithms are not applicable to multi-constrained QoS multicast routing optimization. How to improve ant colony algorithm in current network for the solution of multi-constrained QoS multicast routing is a subject worth studying. Therefore, we propose an algorithm which generates a multicast tree in the way of tree growth and optimizes ant colony algorithm parameters through orthogonal experiments. The former means helps improve the efficiency of algorithm via simplifying the mechanism of searching a tree while the latter taps the issue of high demand on parameter setting through selecting the most efficient combination of various parameters as our final solution. The rest part of the paper is organized as follows. The problem description and formulation is given in Section 2. In Section 3, we describe basic ant colony algorithm (ACO) and its application in multicast routing. In Section 4, we describe the proposed algorithms. We then discuss the convergence of the proposed algorithms in Section 5. Section 6 gives the performance evaluation of the proposed algorithms in comparison with other similar algorithms. Section 7 concludes this research and discusses future work.

This paper proposed a tree-based ant colony algorithm for multi-constrained QoS multicast routing. Simulation indicates that TGBACA is much faster than conventional ant colony algorithm and the cost of the multicast tree always excels that of ACT. TGBACA proposed in this paper can obtain better cost of multicast tree than the abovementioned four algorithms, and the larger the network scale, the more obvious the merit of TGBACA in the use of less time. When the network scale increases it has better performance. The automatic modifying mechanism of parameters of the algorithm is the next research goal in our future study. We will explore the relationship between parameters and topology on the basis of simulation results, thus establishing mathematic model of modifying parameters to enable the algorithm to modify the values of parameters in the operation by referring to the current network topology information. In this way the algorithm can perform its best to the full.