Abstract
The quality of the multicast routing service (QoS) is an NP multi-objective optimization problem. It is one of the main issues of transmission in communication networks that consist of concurrently sending the same information from a source to a subset of all possible destinations in a computer network. Thus, it becomes an important technology communication. To solve the problem, a current approach for efficiently supporting a multicast session in a network is establishing a multicast tree that covers the source and all terminal nodes. This problem can be reduced to a minimal Steiner tree problem (MST), which aims to look for a tree that covers a set of nodes with a minimum total cost that has been proven to be NP-complete. In this paper, we propose a novel algorithm based on the greedy randomized search procedure (GRASP) for the Delay-Constrained Least-Cost problem. Constrained with the construction and improvement phase, the proposed algorithm makes the difference in the construction phase through using a new method called EB heuristic. The procedure was first applied to improve the KMB heuristic in order to solve the Steiner tree problem. Obtained solutions were improved by using the tabu search method in the enhancement process. Computational experiments on medium-sized problems (50–100 nodes) from literature show that the proposed metaheuristic gives competitive results in terms of cost and delay compared to the proposed results in the literature.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Diot, C., Levine, B.N., Lyles, B., Kassem, H., Balensiefen, D.: Deployment issues for the IP multicast service and architecture. IEEE Netw. 14(1), 78–88 (2000)
Striegel, A., Manimaran, G.: A survey of QoS multicasting issues. IEEE Commun. Mag. 40(6), 82–87 (2002)
Xu, Y.: Metaheuristic approaches for QoS multicast routing problems. Ph.D. thesis, University of Nottingham Nottingham (2011)
Qu, R., Xu, Y., Kendall, G.: A variable neighborhood descent search algorithm for delay-constrained least-cost multicast routing. In: Stützle, T. (ed.) LION 2009. LNCS, vol. 5851, pp. 15–29. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-11169-3_2
Lee, S.J., Gerla, M., Chiang, C.C.: On-demand multicast routing protocol. In: 1999 IEEE Wireless Communications and Networking Conference, WCNC (Cat. no. 99TH8466), vol. 3, pp. 1298–1302. IEEE (1999)
Boppana, A.: A scalable simplified multicast forwarding for mobile ad-hoc networks (2011)
Chelius, G., Fleury, É.: Performance evaluation of multicast trees in adhoc networks (2002)
Haghighat, A.T., Faez, K., Dehghan, M., Mowlaei, A., Ghahremani, Y.: GA-based heuristic algorithms for QoS based multicast routing. Knowl.-Based Syst. 16(5–6), 305–312 (2003)
Parsa, M., Zhu, Q., Garcia-Luna-Aceves, J.J.: An iterative algorithm for delay-constrained minimum-cost multicasting. IEEE/ACM Trans. Netw. 6(4), 461–474 (1998)
Zhengying, W., Bingxin, S., Erdun, Z.: Bandwidth-delay-constrained least-cost multicast routing based on heuristic genetic algorithm. Comput. Commun. 24(7–8), 685–692 (2001)
Skorin-Kapov, N., Kos, M.: A grasp heuristic for the delay-constrained multicast routing problem. Telecommun. Syst. 32(1), 55–69 (2006). https://doi.org/10.1007/s11235-006-8202-2
Zhang, L., Cai, L.B., Li, M., Wang, F.H.: A method for least-cost QoS multicast routing based on genetic simulated annealing algorithm. Comput. Commun. 32(1), 105–110 (2009)
Wei, W., Qin, Y., Cai, Z.: A multi-objective multicast routing optimization based on differential evolution in MANET. Int. J. Intell. Comput. Cybern. 11(1), 121–140 (2018)
Zhang, X., Shen, X., Yu, Z.: A novel hybrid ant colony optimization for a multicast routing problem. Algorithms 12(1), 18 (2019)
Matta, I., Guo, L.: QDMR: an efficient QoS dependent multicast routing algorithm. J. Commun. Netw. 2(2), 168–176 (2000)
Kou, L., Markowsky, G., Berman, L.: A fast algorithm for Steiner trees. Acta Informatica 15(2), 141–145 (1981). https://doi.org/10.1007/BF00288961
Oliveira, C.A., Pardalos, P.M.: Mathematical Aspects of Network Routing Optimization. Springer, New York (2011). https://doi.org/10.1007/978-1-4614-0311-1
Fujita, M., Kimura, T., Jin’no, K.: An effective construction algorithm for the Steiner tree problem based on edge betweenness. J. Sig. Process. 20(4), 145–148 (2016)
Ghaboosi, N., Haghighat, A.T.: Tabu search based algorithms for bandwidth-delay-constrained least-cost multicast routing. Telecommun. Syst. 34(3–4), 147–166 (2007). https://doi.org/10.1007/s11235-007-9031-7
Skorin-Kapov, N., Kos, M.: The application of Steiner trees to delay constrained multicast routing: a tabu search approach. In: 2003 Proceedings of the 7th International Conference on Telecommunications, ConTEL 2003, vol. 2, pp. 443–448. IEEE (2003)
Youssef, H., Al-Mulhem, A., Sait, S.M., Tahir, M.A.: QoS-driven multicast tree generation using tabu search. Comput. Commun. 25(11–12), 1140–1149 (2002)
Zhang, K., Wang, H., Liu, F.: Multicast routing for delay and delay variation bounded Steiner tree using simulated annealing. In: Proceedings of the 2005 IEEE Networking, Sensing and Control, pp. 682–687. IEEE (2005)
Askari, Z., Avokh, A.: EMSC: a joint multicast routing, scheduling, and call admission control in multi-radio multi-channel WMNs. Front. Comput. Sci. 14(5), 1–16 (2020). https://doi.org/10.1007/s11704-019-8199-9
Feo, T.A., Resende, M.G.: Greedy randomized adaptive search procedures. J. Global Optim. 6(2), 109–133 (1995). https://doi.org/10.1007/BF01096763
Liu, Q., Tang, R., Ren, H., Pei, Y.: Optimizing multicast routing tree on application layer via an encoding-free non-dominated sorting genetic algorithm. Appl. Intell. 50(3), 759–777 (2019). https://doi.org/10.1007/s10489-019-01547-9
Liu, Q., Ren, H.P., Tang, R.J., Yao, J.L.: Optimizing co-existing multicast routing trees in IP network via discrete artificial fish school algorithm. Knowl.-Based Syst. 191, 105276 (2020)
Hassan, M., Hamid, A., Alkinani, M.: Ant colony optimization for multi-objective multicast routing. Comput. Mater. Continua 63(3), 1159–1173 (2020)
Xu, Y., Qu, R.: A GRASP approach for the delayconstrained multicast routing problem. In: Proceedings of the 4th Multidisplinary International Scheduling Conference (MISTA4), Dublin, Ireland, pp. 93–104 (2009)
Koch, T., Martin, A., Voß, S.: SteinLib: an updated library on steiner tree problems in graphs. In: Cheng, X.Z., Du, D.Z. (eds.) Steiner Trees in Industry. COOP, vol. 11, pp. 285–325. Springer, Boston (2001). https://doi.org/10.1007/978-1-4613-0255-1_9
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Boudjelida, A., Lemouari, A. (2021). A Novel Heuristic Optimization Algorithm for Solving the Delay-Constrained Least-Cost Problem. In: Renault, É., Boumerdassi, S., Mühlethaler, P. (eds) Machine Learning for Networking. MLN 2020. Lecture Notes in Computer Science(), vol 12629. Springer, Cham. https://doi.org/10.1007/978-3-030-70866-5_23
Download citation
DOI: https://doi.org/10.1007/978-3-030-70866-5_23
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-70865-8
Online ISBN: 978-3-030-70866-5
eBook Packages: Computer ScienceComputer Science (R0)