GrAnt: Inferring Best Forwarders from Complex Networks' Dynamics through a Greedy Ant Colony Optimization - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2011

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

Résumé

This paper presents a new prediction-based forwarding protocol for the complex and dynamic Delay Tolerant Networks (DTN). The proposed protocol is called GrAnt (Greedy Ant) as it uses a greedy transition rule for the Ant Colony Optimization (ACO) metaheuristic to select the most promising forwarder nodes or to provide 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 buffer management. To the best of our knowledge, this is the first unicast protocol that employs a greedy ACO which: (1) infers best promising forwarders from nodes' social connectivity, (2) determines the best paths to be followed to a message reach its destination, while limiting the message replications and droppings, (3) performs message transmission scheduling and buffer space management. GrAnt is compared to Epidemic and PROPHET protocols in two different scenarios: a working day and a community mobility model. Simulation results obtained by ONE simulator show that in both environments, GrAnt achieves higher delivery ratio, lower messages redundancy, and fewer dropped messages than Epidemic and PROPHET.
Cet article porte sur la proposition d'un protocole d'acheminement pour les réseaux complexes et dynamiques du type tolérants aux délais (DTN), qui est basé sur l'estimation de possibilités futures de contact. Le protocole proposé est appelé GrAnt (Greedy Ant) car il utilise une règle de transition greedy pour la méta-heuristique d'optimisation par colonies de fourmis (ACO). Cette méta-heuristique donne à GrAnt la possibilité de sélectionner les relais les plus prometteuses ou d'exploiter les bons chemins préalablement trouvé. La motivation principale pour l'utilisation de l'ACO est de profiter de son mécanisme de recherche basée sur population et de son apprentissage et adaptation rapide. En utilisant des simulations basées sur des modèles synthétiques de mobilité, nous montrons que GrAnt est en mesure d'adapter conformément son acheminement dans des différents scénarios et possède une meilleure performance comparée à des protocoles comme Epidemic et PROPHET, en plus de la génération de faible surcharge.
Fichier principal
Vignette du fichier
RR-7694.pdf (967.79 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00610558 , version 1 (22-07-2011)
inria-00610558 , version 2 (22-07-2011)

Identifiants

  • HAL Id : inria-00610558 , version 1

Citer

Ana Cristina Kochem Vendramin, Anelise Munaretto, Myriam Regattieri Delgado, Aline Carneiro Viana. GrAnt: Inferring Best Forwarders from Complex Networks' Dynamics through a Greedy Ant Colony Optimization. [Research Report] RR-7694, 2011, pp.25. ⟨inria-00610558v1⟩

Collections

INRIA-RRRT
319 Consultations
360 Téléchargements

Partager

Gmail Facebook X LinkedIn More