A GA-based Method For Delay And Delay Variation Constrained Multicast Routing

With the development of multimedia communication, multicast routing has become more and more important. In the interactive real-time applications, it is an NP-complete problem that computing an optimal constrained Steiner tree under the cost of the tree with the constraints of delay and delay variation. This paper presents a new heuristic algorithm: GA-based method for delay and delay variation constrained multicast routing (GADVMA) problem. In GADVMA, the pool of paths is based on all the k-shortest paths, which connect the source nodes to the destination ones and are subject to the delay constraints, and then the coding space of GA can be built. Furthermore, both the trees and the initial population of individuals can be created on the base of randomized path-selection among the pool. In the computation, the evolution is performed by the rule of minimizing delay variation and optimizing tree cost at the same time. In this paper, the method of path coding has been used. The code length only depends on the number of destination node and has nothing to do with the scale of network, so GADVMA can be applied in a large-scale network. Selection operator uses the strategy of best-individual reservation. Thus the good solution will not be destroyed after crossover and mutation. In the crossover operator, the common links preservation could reduce the cost of the tree. And there may be mutation by changing the sequence of adding the paths from the destinations to the tree. And mutation operator could effectively avoid the premature convergence. Our experimental simulations show that GADVMA can acquire a tree in which delay variation is close to what it produced by DVMA. Both GADVMA and DVMA are superior to MPH in delay variation of tree. And the tree cost of GADVMA is less than double of MPH. Both GADVMA and MPH are superior to DVMA on tree cost.