First published 2 September 2013
ASAP: an Ant resource Search Algorithm for swarm-like P2P networks
António Homem Ferreira, Carlos Martinho
The Ant Colony Optimization (ACO) meta-heuristic is a proven approach for solving complex distributed problems, being the routing problem one of such. By exploring the surroundings and indirect communication through pheromones, ants can find and follow the shortest path between a food source and its nest. Based on these characteristics, we present an ant-based algorithm for performing in-network resource search in a swarm-like Peer-to-Peer network. By marking connections that share same interests with a synthetic pheromone, a node can easily find a resource without having a significant impact on the network performance. Our approach focuses on decreasing the number of messages generated by each search, without having a negative impact on user experience. To achieve this, we present an algorithm that dynamically adapts based on the information a node has of its surroundings. The more information a node has of its neighbors, the higher the probability of choosing an exploitation strategy over an exploration one. Furthermore, the higher the number of nodes visited by an ant (and thus different paths followed), the lower the number of nodes explored in an exploration strategy. In order to decrease the number of messages sent to nodes that have already processed it, the parent ant informs each of its cloned ants about all the nodes to which each of these cloned ants will be sent to. Through simulation, we show the impact of these design choices in the algorithm's performance and discuss how it can be configured in order to adapt it to different networks.