20-12-2012, 05:56 PM
Ant-based Energy Aware Disjoint Multipath Routing Algorithm in MANETs
Ant-based Energy Aware Disjoint.pdf (Size: 139.38 KB / Downloads: 18)
Abstract
A Mobile Ad hoc Network (MANET) is one
consisting of a set of mobile hosts capable of
communicating with each other without the assistance
of base stations. Earlier research has proposed
several unipath routing protocols specifically on
MANET. However, the single path is easily broken
and needs to perform a route discovery process again
due to the dynamic topology of ad hoc networks. This
leads to increase in both delay and control overhead
as well as decrease in packet delivery ratio. To
alleviate these problems, a new routing algorithm
called Ant-based Energy Aware Disjoint Multipath
Routing Algorithm (AEADMRA) is proposed.
AEADMRA is based on swarm intelligence and
especially on the ant colony based meta heuristic.
AEADMRA extends GRID to enable path
accumulation in route request/reply packets and
discover multiple energy aware routing paths with a
low routing overhead. Simulation results indicate that
performance of AEADMRA is much better than that of
GRID.
Introduction
In the near future, a pervasive computing
environment can be expected based on the recent
progresses and advances in computing and
communication technologies. Next generation of
mobile communications will include both prestigious
infrastructured wireless networks and novel
infrastructureless mobile ad hoc networks (MANETs).
A mobile ad hoc network is a temporary network
that consists of mobile nodes that can communicate
with each other without relying on any infrastructure.
Thus, a mobile ad hoc network is inherently quite
dynamic due to frequent and unpredictable node
mobility. Mobile ad hoc networks find application in
many fields such as military deployments, disaster
rescue missions, and electronic classrooms.
System model
Grid architecture
In AEADMRA, the network area is partitioned into
non-overlapping square zones with the same size (see
Fig.1). Each zone is named with a unique ID(a,b) as
the conventional coordinate. Suppose every node can
obtain its location information from GPS or other
positioning system, hence knows which zone it is
located by calculation at any time. Routing is
performed in a grid-by-grid manner. One mobile host
will be elected as the grid head for each grid. This grid
head is responsible for (1) forwarding route discovery
requests to neighboring grids, (2) propagating data
packets to neighboring grids, and (3) maintaining
routes for each entry and exit of a host in the grid. No
non-grid head hosts are responsible for these jobs
unless they are sources/destinations of the packets.
Route discovery
Data structure
A data structure of FA can be (s, d, ttl,
recvNodeList, GridID, nodeType, SearchedArea,
LinkCost, SumOfLinkCost), Where s is source address,
d is destination address. ttl is the time-to-live of the
message. The value of ttl may be used to limit the
number of intermediate nodes to forward that copy of
FA. As the FA is forwarded, this value is decremented,
and the FA message is discarded if ttl reaches zero
before finding the destination. The recvNodeList field
is of variable length and contains the ID list of the
grid head that have already received the packet.
GridID represents the ID of the grid. The field of
nodeType records the node is a grid head or an
ordinary node. The rectangle area of SearchedArea is
decided by GridID of source node and destination
node, but actually selected searched area may be
bigger than the original rectangle area in order to
satisfy the demand of maximum multiple paths
discovery.
Forwarding the FA
In AEADMRA, the routing table and neighbor
table are established in a grid-by-grid manner, instead
of in a host-by-host manner. Therefore, only the grid
head is needed to maintain the routing table and the
neighbor table.
The creation of new routes requires the use of the
forward ants (FAs) and backward ants (BAs). The
forward ants phase is the flooding process to searching
usable paths, and the backward ants phase is the
routing developed phase.
When an ant walking on a path, it deposits
pheromone on it. With time the concentration of
pheromone decreases due to diffusion effects. The
probability of ants backing source to choose path
depends on the amount of pheromone. So the more
ants visit, the larger amount of pheromone is
deposited. Each grid head in AEADMRA contains a
routing table to record routing information and a
neighbor table to maintain local connectivity. In
AEADMRA, the structure of node routing table can be
represented as (s, d, PNode, GridID, LinkCost).
Where s is source address, d is destination address.
PNode records the address of the previous grid head.
GridID represents the ID of the grid. LinkCost
represents energy consumption of a link. The
LinkCost of heuristic value is local link energy
information collection, and it is used for selecting
route when existing multipath.
Simulation environment
We used the event driven simulator ns-2 [13] along
with the wireless extensions provided by CMU [14].
The simulation environment consists of 50 mobile
hosts in a physical region of size 1000 * 1000 square
meters. All mobile hosts have the same transmission
range of 250 meters. A grid head broadcasts its
existence by sending a GRIDHEAD packet every 10
seconds. Hosts move according to the random
waypoint model [15]. The radio interface uses the
802.11 MAC protocol and has a data rate of 2 Mbps.
Traffic sources with 512 byte data packets are CBR
(constant bit rate). The energy consumption model
described in [16] is employed.
Conclusions
In this paper, we propose an Ant-based Energy
Aware Disjoint Multipath Routing Algorithm
(AEADMRA). The routing algorithm is based on
swarm intelligence and especially on the ant colony
based meta heuristic. AEADMRA extends GRID and
discover multiple energy aware routing paths with a
low routing overhead.
The effectiveness of our AEADMRA was also
validated using the simulation experiments. Our study
indicates that AEADMRA outperforms GRID because
energy aware disjoint routing paths provide robustness
to mobility.