Application of Genetic Algorithms for Optimization of Anycast Routing in Delay and Disruption Tolerant Networks

Application of Genetic Algorithms for Optimization of Anycast Routing in Delay and Disruption Tolerant Networks

Éderson R. Silva (Federal University of Uberlândia, Brazil) and Paulo R. Guardieiro (Federal University of Uberlândia, Brazil)
DOI: 10.4018/978-1-61350-092-7.ch011

Abstract

Delay and disruption tolerant networks (DTNs) have the capacity of providing data communication to remote and rural areas where current networking technology does not work well. In such challenging areas characterized by long duration partition, routing is a common problem. Anycast routing can be used for many applications in DTNs, and it is useful when nodes wish to send messages to at least one, and preferably only one, of the members in an anycast destination group. In this chapter, an anycast routing algorithm for DTNs based on genetic algorithms (GAs) is presented and analyzed. The GA is applied to find the appropriate combination of each path to comply with the delivery needs of the group of anycast sessions simultaneously. The routing algorithm based on GAs under consideration uses the concept of subpopulation to produce the next generation of the population, a limited number of solutions to be evaluated, and yields minimum delay in achieving a specified rate of delivery. Simulation results show that the studied GA-based anycast routing algorithm can produce good results.
Chapter Preview
Top

Introduction

It has been awhile since the Internet has become very popular due to its flexibility, capacity, and robustness offered by the success of protocols used, such as TCP/IP. However, as the Internet is used more and more for communication, new challenges and working groups interested in proposing solutions arise. In this sense, there is a growing effort to allow communications in networks whose scenarios involve frequent disruption and/or long and uncertain delays, thus requiring new techniques and protocols. This general networking problem can be called delay and disruption tolerant networking (DTN) (Farrell & Cahill, 2006).

It turns out that there are many applications that can make use of DTNs. The DTNs 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 technology information for the population in developing countries that lack infrastructure, especially in remote and rural regions. DTNs have been investigated by the DTN research group (DTNRG), which is currently the main open venue for work on the DTN architecture (Cerf et al., 2007) and protocols. Many of the principles of DTN architecture are reviewed by Fall and Farrell (2008). More information about DTN can be found in a book on this subject (Farrell & Cahill, 2006).

One of the main challenges that arises in the design of DTNs that handle long/variable delays and frequent disconnections is routing. Zhang (2006) reviewed some of the routing protocols and categorized them as deterministic and stochastic, depending on the information available about the network. Deterministic protocols use information that nodes obtain about connectivity and network conditions to make efficient forwarding decisions. On the other hand, stochastic protocols address ways in which several copies of the messages can be disseminated among several carriers. The DTN architecture (Cerf et al., 2007) specified by the DTNRG offers a framework where a variety of routing protocols can be used, but it does not define any particular routing protocol. This way, routing is an open issue in DTNs and new proposals can contribute to the effective implementation of DTNs.

In order to operate efficiently in the vast diversity of environments in which the node may find itself, a number of routing algorithms that explore particular features are seen. In this chapter, the network is modeled for the problem of providing data communication to remote and rural areas. These regions, possibly disconnected, can use a car, bus, motorbike, and/or truck, equipped with a storage device, to act as a carrier (mobile nodes that exploit device mobility are used to enable the communication) to deliver messages. Based on this network model, a routing algorithm for DTNs in scenarios where the network topology may be known ahead of time is presented.

The routing for anycast delivery is a useful service in DTNs and it has not been very well explored yet. Anycast routing is aimed at networks where some client nodes require a route to any member from a certain group of service nodes. Anycast can be used for many applications in DTNs such as disaster rescue field (people may want to find a doctor or fireman without knowing their location and specific IDs), long distance education (students may want to get an article from any one of the libraries), battle fields (a command center may want to deliver a particular message to any soldier in a group) etc. Therefore, efficient anycast services are necessary for supporting these applications.

A critical issue in DTN routing is to find the appropriate combination of routes taking into account the node storage constraint and the network traffic dynamics (this problem is NP-complete). Thus, an anycast routing algorithm for DTNs making use of genetic algorithms (GAs) is analyzed, because GAs have the ability to solve complex optimization problems. Moreover, the DTNs can tolerate longer delays than the elaboration time required for GAs to converge toward the optimal solution. Hence, DTNs can be a good application field for GAs. To improve the performance of the GA-based algorithms, strategies, such as the concept of subpopulation (the next generation population is produced using four subpopulations) and a reduction of the number of solutions to be evaluated, are used.

Complete Chapter List

Search this Book:
Reset