© 2004 by British Computer Society
A New Intelligent Agent-based Strategy for Constrained Multiple Destination Routing Problems
School of Computer Science and IT, Nottingham University, Nottingham, UK
The Multiple Destination Routing (MDR) problem can be formulated as finding a minimum cost Steiner tree that satisfies certain constraints in a given communication network. This problem is known to be computationally intractable, as it is a typical NP-hard problem. In this paper, a new intelligent agent-based algorithm is developed to solve the MDR problem in large networks. The algorithm describes an efficient integration and adoption of mobile agents and swarm optimization for the construction of constrained multicast trees. The proposed strategy is based on a group of autonomous agents that traverse the network in an intelligent and parallel manner forming an adaptive search. Routing decisions can be made on the basis of local information about the current network state and the knowledge constructed by a previous set of behaviours of other agents. The advantages of such a paradigm are fault tolerance against some network dynamics, the ability to find optimal regions in complex search spaces through the interaction of individuals in a population of agents and a reduction in the congestion at busy network nodes by favouring paths of low traffic load. The proposed algorithm demonstrated good performance and robustness under all the experimental conditions in comparison to its competitors. The simulation study for both sparse and dense networks showed that the proposed algorithm is highly robust and efficient in the sense of rapidly yielding high-quality solutions.
Received 29 November 2002. Revised 20 January 2004.
Email: