Tese
Algoritmo de roteamento Anycast baseado em algoritmos genéticos para redes tolerantes a atrasos e desconexões
Anycast Routing Algorithm Based on Genetic Algorithms for Delay and Disruption Tolerant Networks
Registro en:
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.
Autor
Silva, Éderson Rosa da
Institución
Resumen
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. Fundação de Amparo a Pesquisa do Estado de Minas Gerais Doutor em Ciências 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.