Sunita Prasad¹, Zaheeruddin² and D.K.Lobiyal³, ¹Center for Development of Advanced Computing, India, ²JMI, India and ³JNU, India

The Steiner tree is the underlying model for multicast communication. This paper presents a novel ant colony algorithm guided by problem relaxation for unconstrained Steiner tree in static wireless ad hoc networks. The framework of the proposed algorithm is based on ant colony system (ACS). In the first step, the ants probabilistically construct the path from the source to the terminal nodes. These paths are then merged together to generate a Steiner tree rooted at the source. The problem is relaxed to incorporate the structural information into the heuristic value for the selection of nodes. The effectiveness of the algorithm is tested on the benchmark problems of the OR-library. Simulation results show that our algorithm can find optimal Steiner tree with high success rate

Multicast routing, Steiner Tree, Wireless Ad Hoc Networks, Ant Colony Optimization (ACO)