Optimizing the CMTS to Improve Quality of Service in Next Generation Networks based on ACO Algorithm

Full Text (PDF, 294KB), PP.25-30

Views: 0 Downloads: 0


Dac-Nhuong Le 1,*

1. Faculty of Information Technology, Haiphong University, Haiphong, Vietnam

* Corresponding author.

DOI: https://doi.org/10.5815/ijcnis.2013.04.04

Received: 24 Aug. 2012 / Revised: 15 Nov. 2012 / Accepted: 12 Jan. 2013 / Published: 8 Apr. 2013

Index Terms

Capacitated Minimum Spanning Tree (cMTS), Communication Network, Quality of Service (QoS), Next Generation Network, Ant Colony Optimization


In this paper, we focus on the network topological design for providing Quality of Service (QoS) in Next Generation Network (NGN) and propose an effective Ant Colony Optimization (ACO) algorithm to solve the capacitated minimum spanning tree (cMTS) problem in dynamic environment. To improve QoS of communication network with considering the network provisioning capability and dynamic environment, we formulate this problem with minimizing the communication cost (as a kind of performance measures for network's QoS). Our objective functions are determined by pheromone matrix of ants satisfies capacity constraints to find good approximate solutions of cMST problems. Numerical experiments show that our algorithm have achieved much better than recent researches.

Cite This Paper

Dac-Nhuong Le, "Optimizing the CMTS to Improve Quality of Service in Next Generation Networks based on ACO Algorithm", International Journal of Computer Network and Information Security(IJCNIS), vol.5, no.4, pp.25-30, 2013. DOI:10.5815/ijcnis.2013.04.04


[1]Sun, W., QoS/Policy/Constraint Based Routing, Technical Report, Ohio State University, 1999.
[2]Braden, R., Clark, D. and S. Shenker, Integrated Services in the Internet Architecture: an Overview, RFC 1633, 33 pages, 1994. http:/ /www.ietf.org/rfc/rfc1633.txt
[3]Blake, S. et. All, An Architecture for Differentiated Service, RFC 2475, 36 papes. ftp://ftp.isi.edu/in-notes/rfc2475.txt
[4]Callon, R., et. al., A frramework for Multiprotocol Label Switching, 69 pages, draft-ietf-mpls-framework-05.txt
[5]Lin Lin and Mitsuo Gen, Auto-tuning Evolutionary Algorithm for a Capacitated QoS Model in Communication Network, 2008.
[6]Hu, T.C, Optimum Communication Spanning Trees, SIAM Journal of Computing, 3(3), 188–195 (1974)
[7]Raidl, G and Julstrom, B.A, Edge Sets: An Effective Evolutionary Coding of Spanning Trees, IEEE Trans, on Evolutionary Computing, Vol. 7, No.3, pp.225-239, 2003.
[8]Chou, H., Premkumar, G. and Chu, C., Genetic algorithms for communication network design – an empirical study of the factors that influence performance, IEEE Trans, on Evolutionary Computing, Vol. 5, No.3, pp.236-249, 2001.
[9]Gen, M., Zhou, G and Takayama, M., Matrix-based genetic algorithm approach on bicriteria minimum spanning tree problem with interval coefficients, J.of Japan Society for Fuzzy Theory and Systems, vol.10, no.6, pp.643-656, 2000.
[10]Anh Tuan Hoang, Vinh Trong Le, Nhu Gia Nguyen, A Novel Particle Swarm Optimization- based Algorithm for the Optimal Communication Spanning Tree problem, Proceedings of The 2010 International Conference on Communication Software and Network (ICCSN 2010).pp.232-236, 2010.
[11]Dac-Nhuong Le, Nhu Gia Nguyen, and Nguyen Dang Le, A Novel Ant Colony Optimization-based Algorithm for the Optimal Communication Spanning Tree problem, 5th International Conference on Computer Science and Information Technology (ICCSIT 2012), December 29-30, 2012, IPCSIT, Vol.55, pp.81-86, Hongkong.
[12]L. Davis, D. Orvosh, A. Cox and Y. Qiu, A genetic algorithm for survivable network design, in Proc. 5th Int. Conf. Genetic Algorithms, pp. 408-415, 1993
[13]J. C. Bean, "Genetic algorithms and random keys for sequencing and optimization," ORSA J. Comput., vol. 6, no. 2, pp. 154-160, 1994
[14]P. Piggott and F. Suraweera. Encoding graphs for genetic algorithms: An investigation using the minimum spanning tree problem. In X. Yao, editor, Progress in Evolutionary Computation, LNAI 956, pages 305–314. Springer, Berlin, 1995
[15]Knowles, J. and Corne, D, A new evolutionary approach to the degree-constrained minimum spanning tree problem, IEEE Trans, on Evolutionary Computing, Vol. 4, No.2, pp.125-134, 2000.
[16]Rail, G, A weighted coding in a genetic algorithm for the degree-constrained minimum spanning tree problem, Proc. SAC(1), pp. 440-445, 2000.
[17]Raidl, G. and Drexe, C, A predecessor coding in an evolutionary algorithm for the capacitated minimum spanning tree problem, Proc. GECCO, pp. 309-316, 2000.
[18]A. Cayley, A theorem on trees, Quart. J. Math. 23 (1889), 376–378.
[19]Zho, G. and Gen, M., A note on genetic algorithm approach to the degree-constrained spanning tree problems, Networks, vol.30, pp. 105-109, 1997
[20]Zho, G. and Gen, M., Genetic algorithm approach on multi-criteria minimum spanning tree problem, E. J. of Operational Research, vol. 114, no. 1, pp. 141-152, 1999.
[21]Zho, G. and Gen, M., Approach to degree-contrainted minimum spanning tree problem using genetic algorithm, in M. Gen and R. Chen, Genetic algorithms & Engineering Design, New York: John Wiley, 2000
[22]Lin, L. and Gen, M, Node-based genetic algorithm for communication spanning tree problem, IEICE Transactions on Communications, vol.E89-B, no.4, pp.1091-1098, April 2006.
[23]M. Dorigo, V. Maniezzo, and A. Colorni, Ant system: Optimization by a colony of cooperating agents, IEEE Trans. on System, MAN, and Cybernetics-Part B, vol. 26, pp. 29-41, 1996
[24]E.Rajo-Iglesias, O.Quevedo-Teruel, Linear Array Synthesis using an Ant Colony Optimization based Algorithm, IEEE Trans. on Antennas and Propagation, 2005.
[25]M. Dorigo, M. Birattari, and T. Stitzle, Ant Colony Optimization: Artificial Ants as a Computational Intelligence Technique", IEEE computational intelligence magazine, November, 2006
[26]Dac-Nhuong Le, and Nhu Gia Nguyen, A New Evolutionary Approach for Gateway Placement in Wireless Mesh Networks, International Journal of Computer Networks and Wireless Communications (IJCNWC), Vol.2, No.5, pp.550-555, October 2012, India.