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

详细信息	查看全文 | 推荐本文 |

• 作者：Ana Cristina Kochem Vendramin^a ; ^{cristina@dainf.ct.utfpr.edu.br}  ; [Author Vitae] ; Anelise Munaretto^a ; ^{anelise@utfpr.edu.br}  ; [Author Vitae] ; Myriam Regattieri Delgado^a ; ^{myriamdelg@utfpr.edu.br}  ; [Author Vitae] ; Aline Carneiro Viana^b ; ^{aline.viana@inria.fr}  ; [Author Vitae]
• 关键词：Social network ; Routing protocol ; Bio-inspired optimization ; Delay tolerant networks ; Node centrality
• 刊名：Computer Networks
• 出版年：2012
• 期刊代码：28_13891286
• 类别：cp
• 出版时间：23 February, 2012
• 卷：56
• 期：3
• 页码：997-1015
• 文件大小：1857 K

摘要

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.