Implementation of Ant Colony Optimization Algorithm for Mobile Ad hoc Network Applications: OpenMP Experiences

Abstract

There is a large class of applications where the pattern of data distributions is non-uniform and sparse. The algorithms for these applications are usually asynchronous. These applications are generally classified as irregular problems. From the parallel computing perspective, an ad hoc network is one such application since the network changes dynamically at runtime, exhibits chaotic load balancing and unpredictable communication behavior among the nodes during runtime.

Ant Colony Optimization (ACO) meta-heuristic, a subset of swarm intelligence, is an inherently parallelizable search technique recently proposed to determine routing in ad hoc networks. One of the many interesting features of swarm based approach is their ability to solve problems that are not static but are spatially distributed and changing over time. In this paper we report our experiences in design, development and implementation of a parallel algorithm for mobile ad hoc networks (MANETs) using the ACO technique on a shared memory architecture with OpenMP. We have experimented with three scheduling policies provided by OpenMP for varying data sizes. Also we report comparison of the performance results with message passing environment (MPI).