04-08-2012, 11:53 AM
ARA – The Ant-Colony Based Routing Algorithm for MANETs
3The Ant-Colony.pdf (Size: 77.26 KB / Downloads: 24)
Abstract
A mobile ad-hoc network (MANET) is a collection of mobile
nodes which communicate over radio. These kind of
networks are very flexible, thus they do not require any existing
infrastructure or central administration. Therefore, mobile
ad-hoc networks are suitable for temporary communication
links. The biggest challenge in this kind of networks
is to find a path between the communication end points,
what is aggravated through the node mobility.
In this paper we present a new on-demand routing algorithm
for mobile, multi-hop ad-hoc networks. The protocol
is based on swarm intelligence and especially on the
ant colony based meta heuristic. These approaches try to
map the solution capability of swarms to mathematical and
engineering problems.
Introduction
A mobile ad-hoc network (MANET) is a set of mobile
nodes which communicate over radio and do not need any
infrastructure. This kind of networks are very flexible and
suitable for several situations and applications, thus they allow
the establishing of temporary communication without
pre installed infrastructure. Due to the limited transmission
range of wireless interfaces, the communication traffic has
to be relayed over several intermediate nodes to enable the
communication between two nodes. Therefore, this kind of
networks are also called mobile multi-hop ad-hoc networks.
Simple ant colony optimization meta-heuristic
algorithm
Let G = (V,E) be a connected graph with n = |V |
nodes. The simple ant colony optimization meta-heuristic
can be used to find the shortest path between a source node
vs and a destination node vd on the graph G. The path
length is given by the number of nodes on the path. Each
edge e(i, j) ∈ E of the graph connecting the nodes vi and
vj has a variable ϕi,j (artificial pheromone), which is modified
by the ants when they visit the node. The pheromone
concentration, ϕi,j is an indication of the usage of this edge.
An ant located in node vi uses pheromone ϕi,j of node
vj ∈ Ni to compute the probability of node vj as next hop.
Ni is the set of one-step neighbors of node vi.
Basic ant algorithm
The basic idea of the ant colony optimization meta
heuristic is taken from the food searching behavior of real
ants. When ants are on they way to search for food, they
start from their nest and walk toward the food. When an
ant reaches an intersection, it has to decide which branch to
take next. While walking, ants deposit pheromone1, which
marks the route taken. The concentration of pheromone on
a certain path is an indication of its usage. With time the
concentration of pheromone decreases due to diffusion effects.
This property is important because it is integrating
dynamic into the path searching process.
The Routing Algorithm
In this section we discuss the adaptation of the ant colony
optimization meta-heuristic for mobile ad-hoc networks and
describe the Ant colony based Routing Algorithm (ARA).
The routing algorithm is very similar constructed as many
other routing approaches and consists of three phases.
Route Discovery Phase
In the route discovery phase new routes are created. The
creation of new routes requires the use of a forward ant
(FANT) and a backward ant (BANT). A FANT is an agent
which establishes the pheromone track to the source node.
In contrast, a BANT establishes the pheromone track to the
destination node. The FANT is a small packet with a unique
sequence number. Nodes are able to distinguish duplicate
packets on the basis of the sequence number and the source
address of the FANT
Route Failure Handling
The third and last phase of ARA handles routing failures,
which are caused especially through node mobility and thus
very common in mobile ad-hoc networks. ARA recognizes
a route failure through a missing acknowledgement. If a
node gets a ROUTE ERROR message for a certain link, it
first deactivates this link by setting the pheromone value to
0.
Then the node searches for an alternative link in its routing
table. If there exists a second link it sends the packet via
this path. Otherwise the node informs its neighbors, hoping
that they can relay the packet. Either the packet can be
transported to the destination node or the backtracking continues
to the source node. If the packet does not reach the
destination, the source has to initiate a new route discovery
phase.
Conclusions and FutureWork
Mobile multi-hop ad-hoc networks are flexible networks,
which do not require pre-installed infrastructure. With upcoming
wireless transmission technologies and highly so-
phisticated devices their application will increase. However
the main challenge in mobile multi-hop ad-hoc networks is
still the routing problem, which is aggravated by the node
mobility. Various approaches were introduced in the recent
years which try to handle the problems in this kind of networks,
but no one fits best for all applications.