02-11-2012, 01:05 PM
Load Balancing of Ant Based Algorithm in MANET
Load Balancing.pdf (Size: 326.89 KB / Downloads: 58)
Abstract
MANETs hold the promise of future, with the capability to
establish networks at anytime, anywhere without the aid of
any established infrastructure. In MANETs all nodes are mobile
and can be connected dynamically. MANETs are inspired by
ant colony optimization framework and uses “ants” for route
discovery, maintenance & improvement. Due to dynamic nature
of MANETs, they can lead to end-to-end delay & overhead. The
algorithm is based on balancing the load among the routes by
calculating threshed value of each routing table & ants helps
to effectively balance the loads as it find a pair of under loaded
and over loaded nests. This paper defines implementation
of ad-hoc n/w and comparison of its performance with AODV
routing protocol based on ant algorithm is done in terms of
packet delivery ratio, end to end delay and load. Performance
of our algorithm in comparison with AODV is much better.
Introduction
Wireless technologies, in the simplest sense, enable one
or more devices to communicate with each other without
physical connections–without requiring network cabling.
Wireless communication technology is increasing daily; with
such growth sooner or later it would not be practical or simply
physically possible to have a fixed architecture for this kind of
network. Wireless LANs (WLANs); allow greater flexibility and
portability than traditional wired local area networks (LAN).
Unlike a traditional LAN, which requires a wire to connect a
user’s computer to the network, a WLAN connects computers
and other components to the network using an access point
(AP) device. [1]
Related Work
S. Prasad, Y.P.Singh, and C.S.Rai [5] presented a novel proactive
algorithm to routing called Probabilistic Ant Routing, in mobile
ad hoc networks, which is inspired by Ant Colony Optimization
(ACO) framework and uses “ants” for route discovery,
maintenance and improvement. The algorithm is based on a
modification of the state transition rule of ACO routing algorithm
that results in maintaining higher degree of exploration along
with congestion awareness in the search space. This leads
to reduced end-to-end delay and also lowers the overhead at
high node density. The comparative experimental results of
the proposed algorithm with the state-of-threat AODV reactive
routing algorithm of the MANET are provided keeping mobility
and density of nodes as the main consideration. The proposed
algorithm is tested for different network sizes and node mobility.
This proposed algorithm exhibits superior performance with
respect to reactive AODV routing algorithm in terms of end-to
end delay.
Proposed Approach
As we know that MANET is a dynamic topology based n/w, which
is having very low bandwidth. So we are using an Ant Based
Algorithm for efficient data transfer in this n/w. Sometimes
there is congestion due to the broadcasting of ants in this
algorithm. Currently, mobile ad hoc networks (MANETs) lack
load-balancing capabilities, and thus, they fail to provide good
performance especially in the case of a large volume of traffic.
Our objective is to do use the ant based algorithm for load
balancing by calculating threshold value of each routing table
through average number of requests accepted by each node.
According to this threshold value, we can control the number
of ants that has been send. If the threshold value is less, it
means the average number of requests to that particular node
is low. Then we simply broadcast the ants for updating their
pheromone table. If the average number of requests is high,
then a data packet will be send according to the pheromone
table of that particular node.
ANT BASED ALGORITHM
Swarm Intelligence (SI) is the local interaction of many simple
agents to achieve a global goal. SI is based on social insect
metaphor for solving different types of problems. Insects like
ants, bees and termites live in colonies. Every single insect
in a social insect colony seems to have its own agenda.
The integration of all individual activities does not have any
supervisor. In a social insect colony, a worker usually does
not perform all tasks, but rather specializes in a set of tasks.
This division of labor based on specialization is believed to
be more efficient than if tasks were performed sequentially
by unspecialized individuals. SI is emerged with collective
intelligence of groups of simple agents. This approach
emphasizes on distributedness, flexibility, robustness and
direct or indirect communication among relatively simple
agents [8].
Principles of Ant Based Algorithm
The ability of ants to self organize is based on four principles.
They are positive feedback, negative feedback, randomness
and multiple interactions.
• Positive feedback – This is used to improve the good solution.
When ants move from one node to another, the concentration
of the pheromone along that path increases. This helps other
ants to travel in this path. Ants deposit pheromone trails while
moving between a discovered food source and the anthill.
Positive feedback is achieved because ants can smell deposited
pheromone and have a natural tendency to follow the trail laid
out by other ants. These ants again deposit pheromone on the
same path, reinforcing the already existing pheromone trail,
which again enhances the probability of other ants to discover
the trail, thus yielding ever higher positive feedback as shown
in Fig. 4.3[9]
Route Maintenance Phase
Route Maintenance plays a very important role in MANET’s as
the network keeps dynamically changing and routes found good
during discovery may turn to be bad due to congestion, signal
strength, etc. Hence when a node starts sending packets to
the destination using the Probabilistic Route Finding algorithm
explained above, it is essential to find the goodness of a route
regularly and update the pheromone counts for the different
routes at the source nodes. To accomplish this, when a
destination node receives a packet, it probabilistically sends
a Congestion Update message to the source which informs the
source of the REM value for that route. This Congestion Update
message also serves an ACK to the source.
Packet Delivery Ratio
Packet delivery ratio is calculated by dividing the number of
packets received by the destination through the number of
packets originated by source. It specifies the packet loss rate,
which limits the maximum throughput of the network. The better
the delivery ration, the more complete and correct the routing
protocol.
Average End-to-End Delay
Average end-to-end delay is the average time it takes a data
packet to reach to destination in seconds. It is calculated
by subtracting “time at which first packet was transmitted
by source” from “time at which first data packet arrived to
destination. It includes all possible delays caused by buffering
during latency, queuing at the interface queue, retransmission
delays at MAC, Propagation and transfer times. It is the metric
significant in understanding the delay introduced by path
discovery.