CPGEI (Qualificação) Ana Cristina Barreiras Kochem Vendramin

Cultural Grant: Um protocolo de roteamento baseado em inteligência coletiva para redes tolerantes ao atraso

Resumo: Este trabalho apresenta um novo protocolo de roteamento voltado para as Redes Tolerantes a Atrasos que exibem comportamentos complexos e dinâmicos. O protocolo proposto chama-se Cultural GrAnt (do inglês Cultural Greedy Ant) uma vez que este utiliza um sistema híbrido composto por um Algoritmo Cultural (AC) e a meta-heurística de Otimização por Colônia de Formigas (ACO). No Cultural GrAnt o ACO atua como espaço populacional de um AC e utiliza uma regra de transição gulosa de modo a selecionar os nós encaminhadores de mensagens mais promissores, podendo neste caso explorar novos caminhos, ou prover a intensificação de bons caminhos já encontrados. A principal motivação para o uso do ACO é tirar proveito da sua busca baseada em população de indivíduos e da adaptação rápida da sua estrutura de aprendizado. A motivação para o uso do AC é utilizar informações obtidas ao longo da evolução e interação com o ambiente e utilizá-las de forma a guiar a população de indivíduos tendendo a gerar soluções mais eficientes e de forma mais rápida. Considerando informações de funções heurísticas, concentração de feromônio e conhecimentos do espaço de crenças do AC, o protocolo Cultural GrAnt inclui três módulos: roteamento; escalonamento; e gerenciamento de buffer. Esse é o primeiro protocolo de roteamento que emprega um ACO guloso e AC de modo a: determinar os encaminhadores de mensagens mais promissores através de informações oportunísticas de conectividade social entre os nós; determinar os melhores caminhos a seguir para que uma mensagem possa ser entregue ao seu destino final, enquanto limita o número de replicações e descartes de mensagens na rede; determinar a ordem de escalonamento das mensagens; gerenciar o espaço de armazenamento do buffer dos nós. O protocolo Cultural GrAnt é comparado com os protocolos Epidêmico e PROPHET em dois cenários de simulação distintos: um modelo de movimento baseado em atividades, onde simula-se o dia-a-dia de pessoas em suas atividades de trabalho, lazer e descanso; e um modelo de movimento baseado em comunidades de pessoas. Resultados de simulações obtidos através do simulador ONE mostram que em ambos os cenários, o protocolo Cultural GrAnt alcança uma taxa mais alta de entrega de mensagens, uma redundância menor de mensagens e um número menor de mensagens descartadas por falta de espaço em buffer se comparado com os protocolos Epidêmico e PROPHET.
Palavras-chave: Redes Tolerantes a Atrasos. Redes Ad-hoc Oportunísticas. Protocolo de Roteamento. Métricas Sociais. Otimização por Colônia de Formiga. Algoritmos Culturais.

Cultural GrAnt: A Routing Protocol Based on Swarm Intelligence for Delay Tolerant Networks

Abstract: This work presents a new routing protocol for the complex and dynamic Delay Tolerant Networks (DTN). The proposed protocol is called Cultural GrAnt (Greedy Ant) as it uses a hybrid system composed by Cultural Algorithm and Ant Colony Optimization (ACO) metaheuristic. In the Cultural GrAnt, ACO represents the populational space of cultural algorithm and it uses a greedy transition rule to select the most promising messages forwarder nodes, in which case it can explore new paths, 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. The motivation for the use of cultural algorithm is to use information gathered during an evolution and use them to guide the population in order to generate more efficient solutions and in a more rapid way. Considering information from heuristic functions, pheromone concentration, and knowledge of the cultural algorithm's belief space, the Cultural GrAnt protocol includes three modules: routing, scheduling, and buffer management. To the best of our knowledge, this is the first routing protocol that employs a greedy ACO and cultural algorithm which: infers best promising forwarders from opportunistic information of social connectivity between nodes; determines the best paths to be followed to a message reach its destination, while limiting the message replications and droppings in the network; performs message transmission scheduling; manage the nodes' buffer space. Cultural GrAnt is compared to Epidemic and PROPHET protocols in two different simulation scenarios: an activity-based movement model which simulates the daily lives of people in their work, leisure and rest activities; and a community-based movement model. Simulation results obtained by ONE simulator show that in both environments, Cultural GrAnt achieves higher delivery ratio, lower messages redundancy, and fewer dropped messages than Epidemic and PROPHET.
Keywords: Delay Tolerant Networks. Opportunistic Ad-hoc Networks. Routing Protocol. Social Metrics. Ant Colony Optimization. Cultural Algorithms.

Lista de publicações:
VENDRAMIN, A. C. B. K., MUNARETTO, A., DELGADO, M., VIANA, A. C. GrAnt: Inferring Best Forwarders from Complex Networks' Dynamics through a Greedy Ant Colony Optimization.
Computer Networks (1999), 2011 (Aceito para publicação).

VENDRAMIN, A. C. B. K. ; MUNARETTO, A. ; DELGADO, M. ; VIANA, A. C. A Greedy Ant Colony Optimization for Routing in Delay Tolerant Networks. In: First International Workshop on Smart Communication Protocols & Algorithms (SCPA 2011) in GLOBECOM 2011, Houston, Texas. Proceedings of IEEE GLOBECOM, 2011 (Aceito para publicação).

VENDRAMIN, A. C. B. K. ; MUNARETTO, A. ; DELGADO, M. ; VIANA, A. C. Protocolo de Roteamento para DTNs através de uma Otimização Gulosa por Colônia de Formigas. In: SBrT - XXIX Simpósio Brasileiro de Telecomunicações, 2011, Curitiba. Anais do SBrT 2011. Rio de Janeiro: Sociedade Brasileira de Telecomunicações, 2011. v. 1. p. 1-5.