Construction of an optimal multicast tree for group communication in a cellular network using genetic algorithm

The recent advances in wireless technology has enabled users of Mobile cellular networks in different parts of the world not only to communicate with each other but also to participate in real time applications, viz., video conferencing, multiparty games, online auctions, access to distributed databases, etc., on the fly. All these applications require a Multicast Tree (MT) to be constructed among the group users with the source being the root of the MT. Traditional methods used in a wired network to construct a MT take into account only the distance or delay between the nodes. These methods when extended to mobile networks fail because of the inherent dynamism in a mobile network. To overcome this problem and to give an optimized solution to this problem, a novel Genetic Algorithm (GA) based approach to construct an Optimal Multicast Tree (OMT) with four constraints viz., probability of delay over a path, queuing delay at a node, residual bandwidth of a link, and the speed of the user is proposed in this paper. Further, for a network of N nodes and E edges, with k independent constraints, it has been derived that the time complexity and space complexity for GA based algorithm are O (N2) and O (N), respectively, whereas the time complexity and space complexity for the non-GA based multi constrained algorithm are O (N2k) and O (N2). These results show that the GA based algorithm is insensitive to the number of constraints and it constructs OMT faster than the traditional algorithms.