A heuristic approximation algorithm for the Steiner tree based on prior multicast nodes. (2018)

• Record Type: Journal Article
• Authors: Yang, Weijun; Zhang, Yun; Chen, Yuanfeng; Liu, Jianqi; Liu, Genyi
• Is Part Of: International journal of autonomous and adaptive communications systems. Volume 11:Number 3(2018)
• Page Start: 193
• Page End: 208
• Publication Date: 2018
• Subjects: multicast routing -- Steiner tree -- approximation algorithm -- prior nodes; Adaptive computing systems -- Periodicals; Wireless communication systems -- Periodicals; Computer networks -- Periodicals; 004.6
• Languages: English
• ISSNs: 1754-8632

Abstract

Multicast routing is regarded as a critical component in networks, especially the real-time applications for multimedia become increasingly popular. Finding such a Steiner tree in multicast routing is an NP-complete problem as for as we know. This paper devises a novel and improved prior nodes minimum cost path heuristic approximation algorithm (IPNMPH) to deal with it. Some paths passing through adjusted prior destination nodes are selected, and they partly share links in the network and decrease the cost of the multicast routing tree. The theoretical validations for the proposed algorithm show that its approximation ratio is 2(1 - 1/ q ) and the time complexity is O ( n 3 ). The simulation experiments on special networks for the proposed algorithm are presented to show its performance and efficiency, and the results indicate that the cost of the IPNMPH algorithm is superior to previous algorithms in most cases.