Transcript The Ant-Colony Based Routing Algorithm for MANETs

Swarm Intelligent Networking
Martin Roth
Cornell University
Wednesday, April 23, 2003
What is Swarm Intelligence?

Swarm Intelligence (SI) is the local
interaction of many simple agents to
achieve a global goal

Emergence


Unique global behavior arising from the
interaction of many agents
Stigmergy

Indirect communication

Generally through the environment
Properties of Swarm Intelligence

Properties of Swarm Intelligence are:
Agents are assumed to be simple
 Indirect agent communication
 Global behavior may be emergent



Behaviors are robust


Specific local programming not necessary
Required in unpredictable environments
Individuals are not important
Swarm Intelligence Example
The food foraging behavior of ants exhibits
swarm intelligence
Principles of Swarm Intelligence
What makes a Swarm Intelligent system
work?
 Positive Feedback
 Negative Feedback
 Randomness
 Multiple Interactions
SI: Positive Feedback
Positive Feedback reinforces good
solutions
 Ants are able to attract more help when
a food source is found
 More ants on a trail increases
pheromone and attracts even more ants
SI: Negative Feedback
Negative Feedback removes bad or old
solutions from the collective memory
 Pheromone Decay
 Distant food sources are exploited last

Pheromone has less time to decay on
closer solutions
SI: Randomness
Randomness allows new solutions to arise
and directs current ones
 Ant decisions are random


Exploration probability
Food sources are found randomly
SI: Multiple Interactions
No individual can solve a given problem.
Only through the interaction of many can
a solution be found
 One ant cannot forage for food;
pheromone would decay too fast
 Many ants are needed to sustain the
pheromone trail
 More food can be found faster
Swarm Intelligence Conclusion
SI is well suited to finding solutions that
do not require precise control over how a
goal is achieved
 Requires a large number of agents
 Agents may be simple
 Behaviors are robust

SI applied to MANETs

An ad hoc network consists of many simple
(cooperative?) agents with a set of problems
that need to be solved robustly and with as
little direct communication as possible
 Routing is an extension of Ant Foraging!



Ants looking for food…
Packets looking for destinations…
Can routing be solved with SI?

Can routing be an emergent behavior from the
interaction of packets?
SI Routing Overview
Ant-Based Control
 AntNet
 Mobile Ants Based Routing
 Ant Colony Based Routing Algorithm
 Termite

SI Routing Overview
Ant-Based Control
 AntNet
 Mobile Ants Based Routing
 Ant Colony Based Routing Algorithm
 Termite

Ant-Based Control Introduction

Ant Based Control (ABC) is introduced to
route calls on a circuit-switched
telephone network

ABC is the first SI routing algorithm for
telecommunications networks

1996
ABC: Overview

Ant packets are control packets
 Ants discover and maintain routes


Pheromone is used to identify routes to each node
Pheromone determines path probabilities

Calls are placed over routes managed by ants
 Each node has a pheromone table maintaining
the amount of pheromone for each destination
it has seen

Pheromone Table is the Routing Table
ABC: Route Maintenance
Ants are launched regularly to random
destinations in the network
 Ants travel to their destination according
to the next-hop probabilities at each
intermediate node



With a small exploration probability an ant
will uniformly randomly choose a next hop
Ants are removed from the network
when they reach their destination
ABC: Routing Probability Update

Ants traveling from source s to
destination d lay s’s pheromone
Ants lay a pheromone trail back to their
source as they move
 Pheromone is unidirectional


When a packet arrives at node n from
previous hop r, and having source s, the
routing probability to r from n for
destination s increases
ABC: Routing Probability Update

pr , s 

pn  r , s
p r , s  Dp
1  Dp
pn  r , s

1  Dp
Dp determined by age of packet
 Probabilities remain normalized

ABC: Route Selection (Call Placement)
When a call is originated, a circuit must
be established
 The highest probability next hop is
followed to the destination from the
source
 If no circuit can be established in this
way, the call is blocked

ABC: Initialization
Pheromone Tables are randomly
initialized
 Ants are released onto the network to
establish routes
 When routes are sufficiently short, actual
calls are placed onto the network

ABC Conclusion
Only the highest probability next hop is
used to find a route
 Probabilities are changed according to
current values and age of packet

Reference

R. Schoonderwoerd, O. Holland, J.
Bruten, L. Rothkranz, Ant-based load
balancing in telecommunications
networks, 1996.
SI Routing Overview
Ant-Based Control
 AntNet
 Mobile Ants Based Routing
 Ant Colony Based Routing Algorithm
 Termite

AntNet Introduction
AntNet is introduced to route information
in a packet switched network
 AntNet is related to the Ant Colony
Optimization (ACO) algorithm for solving
Traveling Salesman type problems

AntNet Overview
Ant packets are control packets
 Packets are forwarded based on nexthop probabilities
 Ants discover and maintain routes



Internode trip times are used to adjust nexthop probabilities
Ants are sent between sourcedestination pairs to create a test and
feedback signal system
AntNet Route Maintenance(F)


Forward Ants, F, are launched regularly to random
destinations in the network
F maintains a list of visited nodes and the time
elapsed to arrive there



Forward Ant packet grows as it moves through the network
Loops are removed from the path list
F is routed according to next-hop probability
maintained in each node’s routing table


A uniformly selected next hop is chosen with a small
exploration probability
If a particular next hop has already been visited, a uniformly
random next hop is chosen
AntNet Route Maintnence(B)

When F arrives at its destination, a Backward
Ant, B, is returned to the source
 B follows the reverse path of F to the source
 At each node, B updates the routing table


Next-hop probability to the destination
Trip time statistics to the destination


Mean
Variance
AntNet Routing
Data packets are routed using the nexthop probabilities
 Forward ants are routed at the same
priority as data packets



Forward Ants experience the same
congestion and delay as data
Backward ants are routed with higher
priority than other packets
AntNet Conclusion
AntNet is a routing algorithm for
datagram networks
 Explicit test and feedback signals are
established with Forward and Backward
Ants
 Routing probabilities are updated
according to trip time statistics

AntNet Reference

G. Di Caro, M. Dorigo, Mobile Agents for
Adaptive Routing, Technical Report,
IRIDIA/97-12, Universit Libre de
Bruxelles, Beligium, 1997.
SI Routing Overview
Ant-Based Control
 AntNet
 Mobile Ants Based Routing
 Ant Colony Based Routing Algorithm
 Termite

Mobile Ants-Based Routing Intro
Mobile Ants-Based Routing (MABR) is a
MANET routing algorithm based on
AntNet
 Location information is assumed


GPS
MABR Overview
MABR consists of three protocols:
 Topology Abstracting Protocol (TAP)


Mobile Ants-Based Routing (MABR)


Simplifies network topology
Routes over simplified topology
Straight Packet Forwarding (SPF)

Forward packets over simplified topology
MABR: Topology Abstracting Protocol
TAP generates a simplified network
topology of logical routers and logical
links
 All individual nodes are part of a logical
router depending on their location


A single routing table may be distributed
over all nodes that are part of a logical
router
MABR: TAP
•Zones are created, each
containing more logical
routers than the last
•Zones are designated by
their location
•Logical links are defined
to these zones
MABR Routing

An AntNet-like protocol with Forward and
Backward ants is applied on the logical
topology supplied by TAP
 Forward ants are sent to random destinations



Ants are sent to the zones containing these
destinations
Ants collect path information during their trip
Backward ants distribute the path information
on the way back their source

Logical link probabilities are updated
MABR: Routing
MABR: Straight Packet Forwarding
Straight Packet Forwarding is
responsible for moving packets between
logical routers
 Any location based routing protocol
could be used
 MABR is responsible for determining
routes around holes in the network


SPF should not have to worry about such
situations
MABR Conclusion

The network topology is abstracted to logical
routers and links


Routing takes place on the abstracted
topology


MABR
Packets are routed between logical routers to
their destinations


TAP
SPF
MABR is still under development

Results are not yet available
SI Routing Overview
Ant-Based Control
 AntNet
 Mobile Ants Based Routing
 Ant Colony Based Routing Algorithm
 Termite

Ant Colony Based Routing Overview
Ant-Colony Based Routing (ARA) uses
pheromone to determine next hop
probability
 Employs a flooding scheme to find
destinations

ARA Route Discovery
To discover a route:
 A Forward Ant, F, is
flooded through the
network to the
destination
 A Backward Ant, B,
is returned to the
source for each
forward ant received
ARA Route Discovery
Reverse routes are automatically
established as forward ants move
through the network
 Backward ants reinforce routes from
destination to source

ARA Routing


Next Hop Probabilities are determined from
the pheromone on each neighbor link
pn , d 
Pn,d
N
P
i 1
i ,d
ARA Pheromone Update
When a packet is received from r at n with
source s and destination d:
 r updates its pheromone table

Pn ,d  Pn ,d  

n updates its pheromone table

Pr , s  Pr , s  
ARA Pheromone Decay
Pheromone is periodically decayed according to
a decay rate, t
t
 Pn,d  Pn,d  e
n N d  D
ARA Loop Prevention
Loops may occur because route
decisions are probabilistic
 If a packet is received twice, an error
message is returned to the previous hop



Packets identified based on source address
and sequence number
The previous hop sets Pn,d = 0

No more packets to destination d will be
sent through next hop n
ARA Route Recovery
A route error is recognized by the lack of
a next-hop acknowledgement
 The previous hop node sets Pn,d = 0
 An alternative next hop is calculated

If no alternative next hop exists, the packet
is returned to previous hop
 A new route request is issued if the data
packet is returned to the source

ARA Conclusion
ARA is a MANET routing algorithm
 Flooding is used to discover routes
 Automatic retransmit used to recover
from a route failure



Packet backtracking used if automatic
retransmit fails
Next Hop probability proportional to
pheromone on each link
ARA Reference

M. Gunes, U. Sorges, I. Bouaziz, ARA –
The Ant-Colony Based Routing Algorithm
for MANETs, 2003.
SI Routing Overview
Ant-Based Control
 AntNet
 Mobile Ants Based Routing
 Ant Colony Based Routing Algorithm
 Termite

Termite Overview
Termite is a MANET routing algorithm
 Termite uses pheromone to produce
next-hop probabilities


Random routing
Termite aims to reduce control traffic
 Termite should scale across network size
and volatility

Termite Routing


Each packet is forwarded probabilistically
based on the amount of destination
pheromone on each neighbor link
pn , d 
( Pn ,d  K ) F
N
F
(
P

K
)
 i ,d
i 1

F, K used to tune the routing probabilities
 No packet is routed out the link it arrived on
Termite Pheromone Update

When a packet arrives at a node n from
previous hop r originally from source s, n
updates it Pheromone Table

Pr , s  Pr , s  
Termite Pheromone Decay
Pheromone is periodically decayed according to
a decay rate, t
t
 Pn,d  Pn,d  e
n N d  D
Termite Route Recovery
If a transmission to a neighbor fails:
 The neighbor is removed from the
Pheromone Table
 An alternative next-hop is calculated and
the packet is resent
 If no alternative exists, the packet is
dropped
Termite Route Discovery(RREQ)
If a node does not contain a needed
destination in its pheromone table, a
route request is issued
 A route request (RREQ) packet follows a
random walk through the network until a
node is encountered containing some
destination pheromone


A route reply (RREP) is returned to the
source
Termite Route Discovery(RREP)

A route reply (RREP) packet follows the
pheromone trail normally back to the
RREQ source
The source of the RREP is the requested
node, regardless of which node actually
originates the packet
 The requested node’s pheromone is
automatically spread through the network

Termite
Termite minimizes control traffic by
allowing all packets to explore the
network
 Path discovery uses random walk


Route Discovery packets are unicast
Open Issues
Termite still has many open questions
 How to automatically determine routing
parameters based on local information



Decay rate, t
Seed rate and distance
Number of RREQs per Route Request


How good is random walk route discovery
How exactly are the various parameters
related? Can some be determined from
others? How do they affect performance?
Simulation Implementation
Simulation Environment
•10 m transmission radius
•1 Mbps channel
•64B data packets
•CBR source
•2 packets per second
with acknowledgement
Network Performance vs. Mobility
Path Length vs. Mobility
Next Hop PDF vs. Mobility
Termite Reference

M. Roth, S. Wicker, Termite: Emergent
Ad-Hoc Networking, 2003.
SI Advantages
SI based algorithms generally enjoy:
 Multipath routing


Fast route recovery


Probabilistic routing will send packets all over the
network
Packets can easily be sent to other neighbors by
recomputing next-hop probabilities
Low Complexity

Little special purpose information must be
maintained aside from pheromone/probability
information
More SI Advantages

Scalability


As with any colonies numbering in the
millions, SI algorithms can potentially scale
across several orders of magnitude
Distributed Algorithm

SI based algorithms are inherently
distributed
SI Disadvantages
SI also suffers from:
 Directional Links


Bidirectional links are generally assumed by
using reverse paths
Novelty

SI is a relatively new approach to routing. It
has not been characterized very well,
analytically
Swarm Intelligence Conclusion
The fundamental idea behind using SI
for routing in MANETs is to use the
interaction of many packets to generate
routing tables while minimizing the use of
explicit routing packets
 The arrival of packets is observed, which
influences next-hop routing probabilities


Critical packets may include specialized ant
packets or all packets