Please use this identifier to cite or link to this item: https://repositorio.ufu.br/handle/123456789/14270
Document type: Tese
Access type: Acesso Aberto
Title: Algoritmo de roteamento Anycast baseado em algoritmos genéticos para redes tolerantes a atrasos e desconexões
Alternate title (s): Anycast Routing Algorithm Based on Genetic Algorithms for Delay and Disruption Tolerant Networks
Author: Silva, Éderson Rosa da
First Advisor: Guardieiro, Paulo Roberto
First member of the Committee: Yamanaka, Keiji
Second member of the Committee: Carrijo, Gilberto Arantes
Third member of the Committee: Nogueira, José Marcos Silva
Fourth member of the Committee: Rezende, José Ferreira de
Summary: As redes tolerantes a atrasos e desconexões ou DTNs (Delay and Disruption Tolerant Networks) possuem o potencial de conectar dispositivos e áreas do mundo que não são servidas por redes tradicionais. O desenvolvimento dessas redes permite levar a revolução da informação tecnológica às populações dos países em desenvolvimento carentes de infraestrutura, especialmente nas regiões remotas e rurais. Neste cenário, as DTNs contribuem oferecendo uma arquitetura alternativa de redes de baixo custo, tolerante a enlaces intermitentes com atrasos variáveis e, possivelmente, longos. Um dos principais desafios que surge no projeto de redes com essas características é o roteamento, sendo este um tópico de grande interesse e importância na área das DTNs. Atualmente, a arquitetura DTN especificada pelo grupo de pesquisa DTNRG (DTN Research Group) oferece uma framework na qual uma variedade de protocolos de roteamento podem ser utilizados, mas não define nenhum protocolo de roteamento particular. Além disso, os nós DTN, provavelmente, terão que suportar diferentes estratégias de roteamento, a fim de operar eficientemente na enorme diversidade de ambientes em que o nó pode se encontrar. Assim, neste trabalho é proposto um algoritmo de roteamento para DTNs em cenários onde a topologia da rede pode ser conhecida ao longo do tempo. Mais precisamente, o roteamento visa a entrega anycast, por ser um serviço ainda pouco pesquisado e que possui diversas aplicações importantes nas DTNs. O algoritmo de roteamento anycast para DTNs, proposto neste trabalho, utiliza algoritmos genéticos ou GAs (Genetic Algorithms), que possuem a capacidade de resolver problemas complexos com múltiplos objetivos. Para aumentar o desempenho do algoritmo baseado em GA proposto, algumas estratégias, como o conceito de subpopulação e a redução do número de soluções a ser avaliado pelo algoritmo, são utilizadas. Nesta tese, é apresentado todo o ambiente de simulação desenvolvido para modelagem das características das DTNs utilizando grafos evolutivos. A proposta de algoritmo de roteamento anycast baseado em GA é implementada e comparada com outras estratégias, e os resultados mostram uma significante melhora no objetivo de entregar mensagens visando otimizar as medidas de desempenho da rede. Como consequência, o tráfego de mensagens é adequadamente distribuído na rede e o esquema utilizado proporciona altas taxas de entrega e atrasos limitados. Desta forma, os estudos baseados em modelagem e simulação mostram que a proposta de algoritmo de roteamento anycast baseado em GA conduz a bons resultados na DTN modelada por grafos evolutivos.
Abstract: DTNs (Delay and Disruption Tolerant Networks) have the potential to interconnect devices and areas of the world that are underserved by traditional networks. The development of these networks can lead to the revolution of the technology information for the population in developing countries which lack infrastructure, especially in remote and rural regions. In this scenario, the DTNs can help offering an alternative network architecture with low cost, tolerant to intermittent connections and having variable and possibly long delays. One of the main challenges that arises in the design of networks with these characteristics is the routing, and this is a topic of great interest and importance of DTNs subject. Currently, the DTN architecture specified by the research group DTNRG (DTN Research Group) offers a framework where a variety of routing protocols can be used, but it does not define any particular routing protocol. Moreover, DTN nodes will likely have to support a number of different routing strategies in order to operate efficiently in the diversity of environments in which the node may find itself. Thus, in this work it is proposed a routing algorithm for DTNs in scenarios where the network topology may be known ahead of time. More specifically, the routing aims anycast delivery, because it is a service that has not been very well explored yet and with many important applications in DTNs. The proposed anycast routing algorithm for DTNs makes use of GAs (Genetic Algorithms), which have the ability to solve complex problems with multiple objectives. To improve the performance of the proposed algorithm based on GA, strategies as, concept of subpopulation and reduction of the number of solutions to be evaluated, are used. In this thesis, it is presented a complete simulation environment developed for modeling the DTNs using evolving graphs. The proposed GA-based anycast routing algorithm is implemented and compared with other strategies, and results show a significant improvement in order to deliver messages to optimize the network performance metrics. As a result, the message traffic is properly distributed in the network and the proposed scheme provides high rates of delivery and limited delays. This way, studies based on modeling and simulation show that the proposed GA-based anycast routing algorithm leads to good results in the DTNs modeled by evolving graphs.
Keywords: DTNs
Roteamento anycast
Algoritmos genéticos
Anycast routing
Genetic algorithms
Internet (Redes de computação)
Redes de computação (Protocolos)
Area (s) of CNPq: CNPQ::ENGENHARIAS::ENGENHARIA ELETRICA
Language: por
Country: BR
Publisher: Universidade Federal de Uberlândia
Institution Acronym: UFU
Department: Engenharias
Program: Programa de Pós-graduação em Engenharia Elétrica
Quote: SILVA, Éderson Rosa da. Anycast Routing Algorithm Based on Genetic Algorithms for Delay and Disruption Tolerant Networks. 2010. 165 f. Tese (Doutorado em Engenharias) - Universidade Federal de Uberlândia, Uberlândia, 2010.
URI: https://repositorio.ufu.br/handle/123456789/14270
Date of defense: 23-Sep-2010
Appears in Collections:TESE - Engenharia Elétrica

Files in This Item:
File Description SizeFormat 
AlgoritmoRoteamentoAnycast.pdf1.16 MBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.