Algoritmo de roteamento Anycast baseado em algoritmos genéticos para redes tolerantes a atrasos e desconexões

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.