A parallel ant colony optimization algorithm for all-pair routing in MANETs

A mobile ad hoc network (MANET) consists of mobile wireless nodes that communicate in a distributed fashion without any centralized administration. The nodes instantaneously and dynamically form a network on the fly when it is needed. We define an irregular application as one that changes the network dynamically during runtime, exhibits chaotic load balancing among the processors and unpredictable communication behavior among the nodes during runtime. An ad hoc network has all these characteristics and hence could be considered as an irregular application from the parallel computing perspective. In this paper, we design an on-demand routing algorithm called source update for MANET using a meta-heuristic based on the ant colony optimization (ACO) search technique. We develop a mechanism to detect cycles, parallelize this algorithm on a distributed memory machine using MPI, and study the performance of the parallel algorithm. On a distributed network of workstations, we obtain a relative speedup of 7 with 10 processors.