Meta-Heuristics Methods for a NP-Complete Networking Problem
Floriano De Rango, Amilcare Francesco Santamaria, Mauro Tropea, S. Marano · 2008
Multimedia communications and, in particular, multicast communications are widely used to distribute multimedia contents. When a certain quality of service (QoS) level must be guaranteed in the multicast tree construction then a Steiner tree problem is obtained, therefore a NP-complete problem must be faced. QoS multicast has a great relevance in the research community because it can offer high performances and better resource allocation. This is relevant in the modern networks, which are composed of wireless networks, wired networks, 3G-4G networks, delay tolerant networks and so on. A better resources allocation permits to have a greater number of connected users. In order to obtain these results it is important to have a multicast tree that can satisfy some QoS requirements. In this work two meta-heurist such as genetic algorithms and simulate annealing algorithms have been considered. Moreover, new procedures and new approaches are proposed in order to obtain better algorithms performances.