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.
Paper
Full text
A NOVEL ANT COLONY ALGORITHM FOR MULTICAST ROUTING IN WIRELESS AD H OC NETWORKS
Semantic Scholar · Computer Science · 2012
Abstract
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.