GrAnt: Inferring Best Forwarders from Complex Networks' Dynamics through a Greedy Ant Colony Optimization

Ana Christina K. Vendramin 1 Anelise Munaretto 1 Aline Carneiro Viana 2 Myriam Regattieri Delgado 1
2 HIPERCOM - High performance communication
Inria Paris-Rocquencourt, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : This paper presents a new prediction-based forwarding protocol for the 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 selecting the most promising forwarder nodes or providing the exploitation of good paths previously found. The main motivation for the use of ACO is to take advantage of its population-based search and of the rapid adaptation of its learning framework. Considering data from heuristic functions and pheromone concentration, the GrAnt protocol includes three modules: routing, scheduling, and bu er management. To the best of our knowledge, this is the rst unicast protocol that employs a greedy ACO which: (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 the message replications and droppings, (3) performs message transmission scheduling and bu er space management. GrAnt is compared to Epidemic and PROPHET protocols in two di erent mobility scenarios: one activity-based scenario (named Working Day) and another based on Points of Interest. Simulation results obtained by ONE simulator show that in both scenarios, GrAnt achieves higher delivery ratio, lower messages redundancy, and fewer dropped messages than Epidemic and PROPHET.
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/hal-00758862
Contributor : Aline Carneiro Viana <>
Submitted on : Thursday, November 29, 2012 - 2:32:10 PM
Last modification on : Thursday, February 7, 2019 - 5:14:46 PM

Links full text

Identifiers

Collections

Citation

Ana Christina K. Vendramin, Anelise Munaretto, Aline Carneiro Viana, Myriam Regattieri Delgado. GrAnt: Inferring Best Forwarders from Complex Networks' Dynamics through a Greedy Ant Colony Optimization. Computer Networks, Elsevier, 2012, 56 (3), pp.997-1015. ⟨10.1016/j.comnet.2011.10.028⟩. ⟨hal-00758862⟩

Share

Metrics

Record views

337