GrAnt: Inferring best forwarders from complex networks' dynamics through a greedy Ant Colony Optimization

This paper presents a new prediction-based forwarding protocol for complex and dynamic delay tolerant networks (DTNs). The proposed protocol is called GrAnt (Greedy Ant), as it uses the Ant Colony Optimization (ACO) metaheuristic with a greedy transition rule. This allows GrAnt to select the most promising forwarder nodes or allow for the exploitation of previously found good paths. The main motivation for using ACO is to take advantage of its population-based search and the rapid adaptation of its learning framework. Considering data from heuristic functions and pheromone concentration, the GrAnt protocol includes three modules: routing, scheduling, and buffer management. To the best of our knowledge, this is the first unicast protocol that employs a greedy ACO and that (1) infers best promising forwarders from nodes' social connectivity, (2) determines the best paths a message must follow to eventually reach its destination while limiting message replications and droppings, and (3) performs message transmission scheduling and buffer space management. GrAnt is compared to the Epidemic and PROPHET protocols in two different mobility scenarios: one activity-based scenario (Working Day) and another based on Points of Interest. Simulation results obtained by the ONE simulator show that, in both scenarios, GrAnt achieves a higher delivery ratio, lower message redundancy, and fewer dropped messages than Epidemic or PROPHET. (C) 2011 Elsevier B.V. All rights reserved.