17-03-2014, 07:28 PM
Abstract
Mobile ad-hoc networks are infrastructure-less
networks consisting of wireless, possibly mobile nodes
which are organized in peer-to-peer and autonomous
fashion. The highly dynamic topology, limited
bandwidth availability and energy constraints make
the routing problem a challenging one. Recently a new
family of algorithms emerged inspired by Swarm
Intelligence, which provides a novel approach to
distributed optimization problems. Initial studies have
unveiled a great deal of matching properties between
the routing requirements of ad-hoc networks and
certain features of SI, such as the ability of ant colony
to find a nearly optimal route between elements.
Several algorithms which are based on ant colony
optimization were introduced in recent years to solve
the routing problem in ad-hoc networks. In this paper
we offer a survey of ant-based routing algorithms for
MANETs. We categorize algorithms and summarize
their operation.
1. Introduction
Mobile ad hoc network is a collection of mobile
devices which form a communication network with no
pre-existing wiring or infrastructure. Routing in
MANETs is challenging since there is no central
coordinator that manage routing decisions. Multiple
routing protocols have been developed for MANETs.
In proactive protocols, every node maintains the
network topology information in the form of routing
tables by periodically exchanging routing information.
Routing information is generally flooded in the whole
network. Whenever a node requires a path to a
destination, it runs an appropriate path finding
algorithm on the topology information it maintains.
The destination sequenced distance vector routing
(DSDV) protocol, and wireless routing protocol (WRP)
Sam Jabbehdari∗
Islamic Azad University,
North Tehran branch, Tehran, Iran.
sjabbehdari[at]gmail.com
are some examples for the proactive protocols.
Reactive protocols do not maintain the network
topology information. They obtain the necessary path
when it is required, by using a connection
establishment process. Hence these protocols do not
exchange routing information periodically. The
dynamic source routing (DSR), Ad-hoc on-demand
distance vector routing (AODV), and temporally
ordered routing (TORA) algorithm are some examples
for the protocols that belong to this category.
Recently, a new family of algorithms emerged
inspired by swarm-intelligence, which provides a novel
approach to distributed optimization problems. The
expression “Swarm Intelligence” defines any attempts
to design algorithms inspired by the collective behavior
of social insect colonies and other animal societies.
Several algorithms which are based on ant colony were
introduced in recent years to solve the routing problem
in ad-hoc networks. These algorithms show that the
biologically inspired concepts can provide a significant
performance gain over traditional approaches. Antbased
routing algorithms in ad-hoc networks,
categorized to flat and hierarchical routing algorithms.
The reminder of this paper is structured as follows.
In section 2 we present the basics and the background
of ant colony optimization meta-heuristic. In section 3
and 4 we present flat and hierarchical ant routing
algorithms respectively. Section 5 present conclusions.
Mobile ad-hoc networks are infrastructure-less
networks consisting of wireless, possibly mobile nodes
which are organized in peer-to-peer and autonomous
fashion. The highly dynamic topology, limited
bandwidth availability and energy constraints make
the routing problem a challenging one. Recently a new
family of algorithms emerged inspired by Swarm
Intelligence, which provides a novel approach to
distributed optimization problems. Initial studies have
unveiled a great deal of matching properties between
the routing requirements of ad-hoc networks and
certain features of SI, such as the ability of ant colony
to find a nearly optimal route between elements.
Several algorithms which are based on ant colony
optimization were introduced in recent years to solve
the routing problem in ad-hoc networks. In this paper
we offer a survey of ant-based routing algorithms for
MANETs. We categorize algorithms and summarize
their operation.
1. Introduction
Mobile ad hoc network is a collection of mobile
devices which form a communication network with no
pre-existing wiring or infrastructure. Routing in
MANETs is challenging since there is no central
coordinator that manage routing decisions. Multiple
routing protocols have been developed for MANETs.
In proactive protocols, every node maintains the
network topology information in the form of routing
tables by periodically exchanging routing information.
Routing information is generally flooded in the whole
network. Whenever a node requires a path to a
destination, it runs an appropriate path finding
algorithm on the topology information it maintains.
The destination sequenced distance vector routing
(DSDV) protocol, and wireless routing protocol (WRP)
Sam Jabbehdari∗
Islamic Azad University,
North Tehran branch, Tehran, Iran.
sjabbehdari[at]gmail.com
are some examples for the proactive protocols.
Reactive protocols do not maintain the network
topology information. They obtain the necessary path
when it is required, by using a connection
establishment process. Hence these protocols do not
exchange routing information periodically. The
dynamic source routing (DSR), Ad-hoc on-demand
distance vector routing (AODV), and temporally
ordered routing (TORA) algorithm are some examples
for the protocols that belong to this category.
Recently, a new family of algorithms emerged
inspired by swarm-intelligence, which provides a novel
approach to distributed optimization problems. The
expression “Swarm Intelligence” defines any attempts
to design algorithms inspired by the collective behavior
of social insect colonies and other animal societies.
Several algorithms which are based on ant colony were
introduced in recent years to solve the routing problem
in ad-hoc networks. These algorithms show that the
biologically inspired concepts can provide a significant
performance gain over traditional approaches. Antbased
routing algorithms in ad-hoc networks,
categorized to flat and hierarchical routing algorithms.
The reminder of this paper is structured as follows.
In section 2 we present the basics and the background
of ant colony optimization meta-heuristic. In section 3
and 4 we present flat and hierarchical ant routing
algorithms respectively. Section 5 present conclusions.