Efficient Algorithm for Reducing Delay Variation on Delay-Bounded Multicast Trees in Heterogeneous Networks
Soobeen Ahn, Moonseong Kim, Hyunseung Choo · 2008
This paper investigates the construction of a multicast tree satisfying Quality of Service (QoS) real-time group communication in a heterogeneous network comprising multiple Mobile Ad-hoc NETworks (MANETs) attached to the backbone Internet. The main objective of our work is to optimize the Delay- and delay Variation Bounded Multicast Tree (DVBMT) problem, which has been proved to be NP-complete. This problem has to satisfy the minimum delay variation and the end-to-end delay within an upper bound. The well-known algorithms solved this problem are the DVMA, the DDVCA, the Cheng's algorithm, and so on. In this paper, we propose an algorithm that outperforms other algorithms in terms of the multicast delay variation in the realistic network environment. The enhancement increases to approximately 3.7%~ 32.9% in terms of that. The time complexity of the proposed algorithm is O(mn2), which is comparable to that of DDVCA.