Ant algorithms and swarm intelligence systems have been offered as a novel computational approach that replaces the traditional emphasis on control, preprogramming and centralization with designs featuring autonomy, emergence and distributed functioning. These designs provide scalable, flexible and robust, able to adapt quickly changes to changing environments and to continue functioning even when individual elements fail. These properties make swarm intelligence very attractive for mobile ad hoc networks. These algorithms also provide potential advantages for conventional routing algorithms. Ant Colony Optimization is popular among other Swarm Intelligence Techniques.In this paper a detailed comparison of different Ant based algorithms is presented. The comparative results will help the researchers to understand the basic differences among various existing Ant colony based routing algorithms.
ABSTRACT
Ant algorithms and swarm intelligence systems have been offered as a novel computational approach that replaces the traditional emphasis on control, preprogramming and centralization with designs featuring autonomy, emergence and distributed functioning. These designs provide scalable, flexible and robust, able to adapt quickly changes to changing environments and to continue functioning even when individual elements fail. These properties make swarm intelligence very attractive for mobile ad hoc networks. These algorithms also provide potential advantages for conventional routing algorithms. Ant Colony Optimization is popular among other Swarm Intelligence Techniques. In this paper a detailed comparison of different Ant based algorithms is presented. The comparative results will help the researchers to understand the basic differences among various existing Ant colony based routing algorithms.
Categories and Subject Descriptors
I.2 Artificial Intelligence; F.2 Analysis of Algorithms and Problem Complexity
General Terms
Algorithms
Keywords
ACO, Swarm Intelligence, Ad hoc routing protocols.
1. INTRODUCTION
Ad hoc networks are characterized by multi-hop wireless connections and frequently changing network topology[14]. It is a self-organizing network consisting of wireless nodes without any central control. Here each node functions simultaneously as a host and a router. Due to the time varying nature of network topology, traditional routing techniques such as distance-vector and link-state algorithms cannot be directly applied to mobile ad hoc networks. The constraints of ad hoc networks demand the need of specialized routing algorithms that can work in a decentralized and self-organizing way. The routing protocols have to adapt quickly and elegantly to frequent and unpredictable changes to conserve memory, power and bandwidth resources. Most routing protocols use a derivative of either link-state or distance-vector routing. The routing schemes in mobile ad hoc networks are classified into two major categories: Proactive and Reactive[13]. Proactive or table-driven routing protocols attempt to maintain at all times the information necessary to route information to any node within the network and are usually the derivative of link state algorithm. Reactive routing protocols only acquire the routes on demand and are usually a derivative of distance vector algorithm. Some protocols share the characteristics of both of these types and are therefore classified as hybrid routing protocols[22].
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
ACAI 2011, July 21-22, 2011, Rajpura, Punjab, India. Copyright © 2011 ACM 978-1-4503-0678-2/11/07…$10.00”
2. SWARM INTELLIGENCE
Swarm Intelligence (SI)[17] is an innovative artificial distributed intelligent paradigm based on the study of emergent behavior in decentralized, self-organized systems for solving optimization problems[1].SI is the emergent collective intelligence of groups of simple autonomous agents. The ants navigate their designated intelligent paradigm based on the study of emergent behavior in decentralized, self-organized systems for solving optimization selection of paths while depositing a certain amount of substance called pheromone on the ground, marking a trail. The idea behind this technique is that the more ants follow a particular trail, the more attractive is that trail for being followed by other ants. They therefore dynamically find a path on the fly, using the explained notion of stigmergy to communicate indirectly amongst them. An ant chooses a trail depending on the amount of pheromone deposited on the ground[16]. Each ant compares the amounts of trails, for the selected destination on each link, toward the neighboring nodes. The larger the concentration of pheromone in a particular trail, the greater is the probability of trail being selected by an ant. The concentration of the pheromone on the links formed evaporates with time at a certain rate. Each node in the network has a routing table which helps it determine where to send the next packet or ant. These routing tables have the neighbors of the node as rows, and all of the other nodes in the network as columns.
3. ANT COLONY OPTIMIZATION
ACO algorithms have been employed to solve numerous problems in ad hoc networks [2]. Ant algorithms were first proposed by Dorigo and colleagues as a multi-agent approach to difficult combinatorial optimizations problems [9] such as the travelling salesman problem, graph coloring, quadratic assignment problem and routing in communication networks and so on [18]. The list of ACO applications for solving optimization problems [20, 25] have been given in table 1.
[...]
- Quote paper
- Anuj Gupta (Author), Harsh Sadawarti (Author), Anil Verma (Author), 2011, Analysis of various Swarm-based & Ant-based Algorithms, Munich, GRIN Verlag, https://www.grin.com/document/205047
