Open Access Open Access  Restricted Access Subscription or Fee Access

Ant Colony Based Algorithm for Constructing Broadcasting Tree with Constraint Satisfaction

Sushant Fulzele, Rashmi Sahay


In this paper, we proposed solution for the construction of degree, delay and bandwidth constrained Minimum Spanning Tree (MST) of the network with the help of Ant Colony Optimization approach. The degree, delay and bandwidth constrained broadcasting problem with minimum-cost appears to be NPcomplete.Given the lack of an exact algorithm to obtain the optimal solutions for NP-complete problems within a polynomial time, many meta-heuristic methods such as tabu search, genetic algorithm and ant colony system were proposed to solve these problems. Ant colony optimization is a well-known meta-heuristic for network optimization problems.


Minimum Spanning Tree, Ant Colony Optimization, QoS. ACO-DDBCMST

Full Text:



Dorigo, M., & Gambardella, L. M. (1997). “Ant colony system: A cooperative learning approach to travelling salesman problem’” IEEE Transactions on Evolutionary Computation, 1(1), 53–66.

Sriram Raghavan, G. Manimaran and C.Siva Ram Murthy "A Rearrangeable Algorithm for the Construction of Delay Constrained Dynamic Multicast Trees" IEEE VOL. 7, NO. 4, AUGUST 1999

Dorigo, M., Maniezzo, V., & Colorni, A. (1996). “‘The ant system:Optimization by a colony of cooperating agents”. IEEE Transaction on System, Man and Cybernetics, 26(1), 1–13.

Sheng-Yuan Tseng, Chang-Chun Lin, Yueh-Min Huang "Ant colonybased algorithm for constructing broadcasting tree with degree and delay constraints".Elsevier(2008)

CHIEN-CHUNG SHEN and KE LI, CHAIPORN JAIKAEO,VINAY SRIDHARA "Ant-Based Distributed Constrained Steiner Tree Algorithm for Jointly Conserving Energy and Bounding Delay in AdHoc Multicast Routing". ACM Transactions on Autonomous and Adaptive Systems, Vol. 3, No. 1, Article 3, Publication date: March 2008.

Zongming Fei, Mengkun Yang "A Proactive Tree Recovery Mechanism for Resilient Overlay Multicast".IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 15, NO. 1, FEBRUARY 2007.

Luca Gambardella, ´Eric Taillard, and Giovanni Agazzi. Macs-vrptw:“A multiple ant colony system for vehicle routing problems with time windows.” Technical Report IDSIA-06-99, Lugano, Switzerland, 1999.

Marco Dorigo, Vittorio Maniezzo, and Alberto Colorni. “The ant system: Optimization by a colony of cooperating agents”. IEEE Transaction on Systems, Man and Cybernetics, 26(1):29 41, 1996.

Sadiq Sait and Habib Youseff. “ Iterative Computer Algorithms with Applications in Engineering”. IEEE - Computer Society, 1997.

Wang, Z., Shi, B., & Zhao, E. (2001). “Bandwidth-delay constrained leastcost multicast routing based on heuristic genetic algorithm.”Computer Communications, 24, 685–692.

Ian Parmee. Evolutionary and Adaptative Computing in Engineering Design. Springer-Verlag, 2001.

M. Dorigo, G.D. Caro, and L.M. Gambardella, “Ant algorithms for Discrete Optimization”, Artificial Life, 1999, 5, pp. 1-10.

M. Dorigo, C. Blum, “Ant colony optimization theory: A survey.,”Theoretical Computer Science, 2005, 344, pp. 243–278.

Shan Hong-bo, Li shuxia, “The Comparison Between Genetic Simulated Annealing Algorithm and Ant Colony Optimization Algorithm for ASP,” 2008 IEEE.

Mauro Birattari, Paola Pellegrini, Marco Dorigo, ” On the Invariance of Ant Colony Optimization”, VOL. 11, NO. 6, DECEMBER 2007.IEEE.



  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.