A Genetic Algorithm for Delay-Constrained Minimum-Cost Multicasting

The problem of computing delay-constrained minimum-cost multicast trees is of great interest in the last few years. The best known solution to this problem is the Bounded Shortest Multicast Algorithm (BSMA), which has unfortunately very large computation time. In this paper, we propose a genetic algorithm for computing such delay-constrained low-cost multicast trees. The proposed algorithm is based on a bit-string encoding of selected Steiner nodes and an efficient deterministic delay-constrained multicast heuristic. Simulation results show that the proposed genetic algorithm can achieve a smaller average tree cost than BSMA with a much smaller running time for relatively large networks. Keywords: Multicast, minimum-cost tree, delay constraint, multimedia, genetic algorithm 1 Introduction Multicasting involves the transport of the same information from a sender to multiple receivers along a multicast tree. In the past, much work has been focused on algorithms for computing low-cost ..