04-08-2012, 12:07 PM
BeeAdHoc: An Energy Efficient Routing Algorithm for Mobile Ad Hoc Networks Inspired by Bee Behavior
BeeAdHoc.pdf (Size: 279.45 KB / Downloads: 33)
ABSTRACT
In this paper we present BeeAdHoc, a new routing algorithm
for energy efficient routing in mobile ad hoc networks. The
algorithm is inspired by the foraging principles of honey
bees. The algorithm mainly utilizes two types of agents,
scouts and foragers, for doing routing in mobile ad hoc networks.
BeeAdHoc is a reactive source routing algorithm and
it consumes less energy as compared to existing state-of-theart
routing algorithms because it utilizes less control packets
to do routing. The results of our extensive simulation experiments
show that BeeAdHoc consumes significantly less
energy as compared to DSR, AODV, and DSDV, which
are state-of-the-art routing algorithms, without making any
compromise on traditional performance metrics (packet delivery
ratio, delay and throughput).
INTRODUCTION
Mobile Ad Hoc Networks (MANETs) is becoming an active
area of research [13]. All nodes in such networks take
two roles: producer/consumer of data packet streams, and
routers for data packets destined for the other nodes. The
most important challenges in MANETs are: mobility and
limited battery capacity of the nodes. Mobility of nodes results
in continuously evolving new topologies and the routing
algorithms have to adapt the routes according to these
changes. The limited battery capacity poses yet another
challenge for the routing algorithms: to distribute the packets
on multiple paths in such a manner that the battery of
different nodes deplete at an equal rate, as a result, the life
time of the network could be increased [16] [8]. The metrics
for energy efficient routing are also introduced in [8] and it is
evident that an energy aware routing algorithm is expected
to degrade the traditional performance metrics of a routing
algorithm i.e.
Related Work
The first algorithm which presented a detailed scheme for
MANET routing based on ant colony principles is ARA [6].
The algorithm has its roots in ABC [14] and AntNet [2]
routing algorithms for fixed networks, which are inspired by
the pheromone laying behavior of ant colonies. The algorithm
floods ants to the destinations while establishing reverse
links to the source nodes of the ants. Nodes launch ant
agents in a reactive manner in order to limit the overhead
caused by them. AntHocNet has been recently proposed in
[3] which is a hybrid algorithm having both reactive and
proactive components. The algorithm tries to keep most of
the features of the original AntNet and shows promising results
in the simulation tests over AODV. Termite is another
MANET routing algorithm inspired from termite behavior
[12]. In this algorithm, no special agents are needed for
updating the routing tables rather data packets are delegated
this task. Each data packet follows the pheromone
for its destination and leaves the pheromone for its source.
Pheromone is a quality metric representing the goodness of
a link. The data packets are biased toward the paths that
have higher pheromone values. An exponential pheromone
decay is introduced as a mean of a negative feedback to prevent
old routes from remaining in the routing tables.
Foragers
Foragers are the main workers in our BeeAdHoc algorithm.
They receive the data packets from packers and then transport
them to their destination. Each forager has a special
type: delay or lifetime. The delay foragers collect the delay
information from the network while the lifetime foragers collect
the remaining battery capacity of the nodes that they
visit. The first ones try to route packets along a path that
has a minimum delay while the second ones try to route
packets in such a manner that the life time of the network
is increased.
The Dance Floor
The dance floor is the heart of the hive because it takes
important routing decisions. Once a forager returns after
its journey it recruits new foragers by dancing according to
the quality of path that it traversed. However, the quality
metric for each forager is different. As mentioned before,
a lifetime forager evaluates the quality of its route based
on the average remaining battery capacity of the nodes on
its route. A lifetime forager might allow itself to be cloned
many times (forager bees in Nature dance enthusiastically
and consequently recruit more foragers) in two scenarios:
one, the nodes on the route have enough remaining battery
capacity (good route), two, if large number of packers are
waiting for it even though its route might be having nodes
with little battery capacity. In second case, it is sensible
to send the packets through less good routes as well. On
the other hand, if none of the packers are waiting then a
forager with a very good route might not dance because its
colleagues are doing a nice job in transporting the data packets.
This concept is directly borrowed from the behavior of
scout/forager bees in Nature, and it helps in regulating the
number of foragers for each route.
SIMULATION FRAMEWORK
We evaluated the performance of our algorithm BeeAd-
Hoc using mobility enhancements made to ns-2 simulator
by the authors of [1]. The authors also evaluated the performance
of different state-of-the-art algorithms like AODV,
DSR, DSDV and TORA in their work. Our test scenarios
are derived from the base scenario used in [1]. We use the
same implementations of DSR, AODV and DSDV, which are
distributed with the ns-2 simulator to factor out any implementation
related error in the algorithms.
CONCLUSION
In this paper we presented a new routing algorithm for
MANET which is inspired by the honey bee behavior. The
algorithm is simple and mainly needs two types of messages
for routing: scouts, which on-demand discover new routes
to the destinations and forgers, which transport data packets
and simultaneously evaluate the quality of the discovered
routes. This simplicity results in substantially smaller
number of control packets sent, as a result, the algorithm is
energy efficient. We have verified through extensive simulations,
which represent a wide spectrum of network conditions,
that BeeAdHoc delivers the same/better performance
as that of the state-of-the-art algorithms but at a significantly
smaller energy expenditure.