Academy & Industry Research Collaboration Center
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.