R.Ghazali ,A.Movaghar

Ra_arpanet2000@yahoo.com,movaghar@sharif.edu

A novel routing scheme for mobile ad hoc

networks (MANETs), which combines the ondemand

routing capability of Ad Hoc On-

Demand Distance Vector (AODV) routing

protocol with a distributed topology discovery

mechanism using ant-like mobile agents is

proposed in this paper. The proposed hybrid

protocol reduces route discovery latency and the

end-to-end delay by providing high connectivity

without requiring much of the scarce network

capacity. On the one side the proactive routing

protocols in MANETs like Destination

Sequenced Distance Vector (DSDV) require to

know, the topology of the entire network. Hence

they are not suitable for highly dynamic

networks such as MANETs, since the topology

update information needs to be propagated

frequently throughout the network. These

frequent broadcasts limit the available network

capacity for actual data communication. On the

other hand, on-demand, reactive routing schemes

like AODV and Dynamic Source Routing

(DSR), require the actual transmission of the

data to be delayed until the route is discovered.

Due to this long delay a pure reactive routing

protocol may not be applicable for real-time data

and multimedia communication. Through

extensive simulations in this paper it is proved

that the proposed Ant-AODV hybrid routing

technique, is able to achieve reduced end-to-end

delay compared to conventional ant-based and

AODV routing protocols.

To overcome the problems associated with the

link-state and distance-vector algorithms a

number of routing protocols have been proposed

for MANETs. These protocols can be classifed

into three different groups: global/proactive, on

demand/reactive and hybrid. In proactive routing

protocols, the routes to all the destination (or

parts of the network) are determined at the start

up, and maintained by using a periodic route

update process.

In reactive protocols, routes are determined when

they are required by the source using a route

discovery process. Hybrid routing protocols

combine the basic properties of the two classes

of protocols into one. That is, they are both

reactive and proactive in nature. Each group has

a number of different routing strategies, which

employ a flat or a hierarchical routing structure.

The current paper tries to overcome these

shortcomings of ant-based routing and AODV by

combining them to develop a hybrid routing

scheme. The Ant-AODV hybrid routing protocol

is able to reduce the end-to-end delay and route

discovery latency by providing high connectivity

as compared to AODV and ant-based routing

schemes. The hybrid scheme also does not

overload the available network capacity with

control messages like the proactive protocols.

Keywords: Manet -Ant Routing-AODV-ANT

AODV

The Ad Hoc On-Demand Distance-Vector

Protocol [2] (AODV) is an other distance vector

routing for mobile ad-hoc networks. AODV is an

on-demand routing approach, i.e.there are no

periodical exchanges of routing information. The

protocol consists of two phases: i) route

discovery, and ii) route maintenance.

A node wishing to communicate with another

node first seeks for a route in its routing table. If

it finds one the communication starts

consists of a route-request message(RREQ)

which is broadcasted. If a node has a valid route

to the destination, it replies to the route-request

with a route-reply (RREP) message.

Additionally, the replying node creates a so

which contains the address of the source node,

the number of hops to the source, and the next

hop's address, i.e. the address of the node from

which the message was received. A lifetime is

associated with each reverse route entry, i.e. if

the route entry is not used within the lifetime it

will be removed.

and can be subdivided into: i) source node

moves: source node initiates a new route

discovery process, ii) destination or an

intermediate node moves: a route error message

(RERR) is sent to the source node. Intermediate

nodes receiving a RERR update their routing

table by setting the distance of the destination to

infinity. If the source node receives a RERR it

will initiate a new route discovery.

To prevent global broadcast messages AODV

introduces a local connectivity management.

This is done by periodical exchanges of so called

HELLO messages which are small RREP

packets containing a node's address and

additional information.

Routing algorithms for MANET which

employ ants have been previously explored by

[4,5,6]. Ants in network routing applications are

simple agents embodying intelligence and

moving around in the network from one node to

the other and updating the routing tables of the

nodes they visit with what they have learned in

their traversal so far [4,5,6,]. Routing ants keep a

history of the nodes previously visited by them.

When an ant arrives at a node it uses the

information in its history for updating the routing

table at that node with the best routes it has for

the other nodes in the network. The higher the

history size the larger the overhead, hence a

careful decision on the history size of the ants

has to be made. All the nodes in the network rely

on the ants for providing them the routing

information, as they themselves do not run any

program for finding routes. The ant-based

routing algorithm implemented in this paper does

not consider any communication among the ants.

Each ant works independently. The population

size of the ants is another important parameter,

which affects the routing overhead.

Ants that take the “no return rule” [4] while

selecting the next hop at a node have been

implemented in this paper. In the conventional

ant algorithms the next hop is selected randomly.

If the next hop selected is the same as the

previous node (from where the ant came to the

current node) then this route would not be

optimal. Data packets sent on such routes would

just be visiting a node and going back to the

previous node in order to reach the destination.

Every node frequently broadcasts HELLO

messages to its neighbors so that every node can

maintain a neighbor list, which is used for

selecting the next hop by the ants.

Ant-AODV technique, forms a hybrid of

both ant-based routing and AODV routing

protocols to overcome some of their inherent

drawbacks. The hybrid technique enhances the

node connectivity and decreases the end-to-end

delay and route discovery latency. Route

establishment in conventional ant-based routing

techniques is dependant on the ants visiting the

node and providing it with routes. If a node

wishes to send data packets to a destination for

which it does not have a fresh enough route, it

will have to keep the data packets in its send

buffer till an ant arrives and provides it with a

route to that destination. Also, in ant routing

algorithms implemented so far there is no local

connectivity maintenance as in AODV. Hence

when a route breaks the source still keeps on

sending data packets unaware of the link

breakage. This leads to a large number of data

packets being dropped. AODV on the other hand

takes too much time for connection

establishment due to the delay in the route

discovery process whereas in ant-based routing if

a node has a route to a destination it just starts

sending the data packets without any delay. This

long delay in AODV before the actual

connection is established may not be applicable

in real-time communication applications. Fig. 1.

Propagation of route reply and traversal of ant

packet in Ant-AODV routing protocol. In Ant-

AODV ant agents work independently and

provide routes to the nodes as shown in fig. 1.

The nodes also have capability of launching ondemand

route discovery (fig. 1) to find routes to

destinations for which they do not have a fresh

enough route entry. The use of ants with AODV

increases the node connectivity (the number of

destinations for which a node has un-expired

routes), which in turn reduces the amount of

route discoveries. Even if a node launches a

RREQ (for a destination it does not have a fresh

enough route), the probability of its receiving

replies quickly (as compared to AODV) from

nearby nodes is high due to the increased

connectivity of all the nodes resulting in reduced

route discovery latency. Lastly, as ant agents

update the routes continuously, a source node

can switch from a longer (and stale) route to a

newer and shorter route provided by the ants.

This leads to a considerable decrease in the

average end-to-end delay as compared to both

AODV and ant-based routing. Ant-AODV uses

route error messages (RERR) to inform upstream

nodes of a local link failure similar to AODV.

Routing table in Ant-AODV is common to both

ants and AODV. Frequent HELLO broadcasts

are used to maintain a neighbor table. This table

is used to select a randomly chosen next hop

(avoiding the previously visited node) from the

list of neighbors by the ant agents. IV.

Fig. 1. Propagation of route reply and

traversal of ant packet in Ant-AODV routing

protocol.

Extensive simulations were carried out to

compare the Ant-AODV hybrid routing protocol

proposed in this paper with the conventional antbased

and AODV routing protocols. Network

Simulator (NS-2) [7] is used to simulate these

protocols. NS-2 is a discrete event simulator. The

latest version of NS-2 (ns-2.7) which can model

and simulate a multi-hop wireless ad hoc

network was used for the simulations. The

physical layer for the simulation uses two-ray

ground reflection as the radio propagation model.

The link layer is implemented using IEEE

802.11 Distributed Coordination Function

(DCF), Media Access Control Protocol (MAC).

It uses “RTS/CTS/Data/ACK” pattern for unicast

packets and “data” for broadcast packets. Carrier

Sense Multiple Access with Collision Avoidance

(CSMA/CA) is used to transmit these packets.

All protocols simulated maintain a send buffer of

64 data packets, containing the data packets

waiting for a route. Packets sent by routing layer

are queued at the interface queue till MAC layer

can transmit them, which has a maximum size of

50 data packets. The interface queue gives

priority to routing packets in being served. The

transmission range for each of the mobile nodes

is set to 250m and the channel capacity is

2Mbps. Simulations were run for 600 simulated

seconds. The routing table used for all the three

protocols are similar. Every route entry in the

routing table has a destination node address,

number of hops to reach that destination, the next

hop to route the packets, the sequence number of

the destination and the time to live for that route.

Several combinations of ant population and

history sizes were used in the simulations to

arrive at the values that gave the best

performance. These values of ant population and

history size were then chosen so as to keep a

balance between control overhead and efficient

routing. For simulating ant-based routing

protocol the number of ants was kept equal to the

number of nodes (which was 50) with a history

size of 15. For Ant-AODV, 10 ants with a

history size of 12 were used.

A network of 50 mobile nodes migrating within

an area of 1500m X 300m with a speed of 0 -

10m/s was simulated. A rectangular space was

chosen in order to force the use of longer routes

between nodes than would be there in a square

space with the same amount of nodes [8]. The

in the rectangular field. The simulations were run

multiple times for 6 different pause times: 0, 30,

60, 120, 300 and 600 seconds. After pausing for

pause time seconds the mobile node again selects

a new destination and proceeds at a speed

distributed uniformly between 0 and a maximum

speed.

The simulations carried out consisted of 20

Continuous Bit Rate (CBR) sources. CBR traffic

sources were chosen, as the aim was to test the

routing protocols. Source nodes and destination

nodes were chosen at random with uniform

probabilities. The sending rate used was 4

packets per second with a packet size of 64

bytes. Each data point in the comparison results

represents an average of multiple runs with

identical traffic models but with different

movement scenarios. Same movement and traffic

scenarios were used for all the three protocols

simulated.

The average end-to-end delay includes buffering

delay during route discovery, queuing delay at

interface queue, retransmission delays and

propagation and transfer times. The average endto-

end delay for AODV and Ant-AODV hybrid

protocol (fig. 2) is very less. But in case of Ant

routing technique (fig. 3) the average end-to-end

delay is high. The high end-to-end delay in antbased

routing is attributed to the lack of ondemand

route discovery capability of the nodes

in ant routing. Due to this the packets to be sent

by a node keep waiting in the send buffer till the

ants visit that node and provide it with routes.

Fig. 2. Average end-to-end delay provided by

AODV and Ant-AODV routing protocols.

Fig. 3. Average end-to-end delay provided by

Ant-based and Ant-AODV routing protocols.

Comparing Ant-AODV and AODV it can be

observed that the end-to-end delay (fig. 2) is

considerably reduced in Ant-AODV as compared

to AODV. Ants help in maintaining high

connectivity in Ant-AODV, hence the packets

need not wait in the send buffer till the routes are

discovered. Even if the source node does not

have a ready route to the destination, due to the

increased connectivity at all the nodes the

probability of its receiving replies quickly from

nearby nodes is high resulting in reduced route

discovery latency. Lastly, the dynamic nature in

which routes are kept updated by the ants leads

to the source node switching from a longer (and

stale) route to newer and shorter ones hence

reducing end-to-end delay for active routes.

Goodput is the total number of useful packets

received at all the destination nodes and packet

delivery fraction is the ratio of number of data

packets sent to the number of data packets

received. Packet delivery fraction is very high

for AODV and Ant-AODV (fig. 4) as compared

to ant-based routing. Goodput is also higher for

Ant-AODV and AODV as compared to antbased

routing (fig. 5).

Fig. 4. Packet delivery fraction provided by Antbased,

AODV and Ant-AODV hybrid routing

protocols.

Fig. 5. Goodput of Ant-based, AODV and

AntAODV routing protocols.

High packet delivery fraction and goodput in

Ant-AODV and AODV is because they make

use of link failure detection and route error

messages. Whereas in case of ant-based routing

there is no such feature and so the source nodes

keep on sending packets unaware of the link

failures. This leads to a large amount of data

packets being dropped which reduces the packet

delivery fraction and the goodput. Also seen in

the graphs for packet delivery fraction (fig. 4)

and goodput (fig. 5) is that as the pause time

increases the goodput and packet delivery ratio

increase due to less link failures at low mobility

number of routing packets transmitted per data

packet received at the destination. The routing

overhead in case of ant-based routing is

independent of the traffic. Even if there is no

communication the ants would still be traversing

the network and update the routing tables.

However in case of AODV, the overhead is

dependent on the traffic and if there is no

communication then there will be no control

messages generated in the network. In Ant-

AODV the overhead has two components. It has

the ants traversing in the network, and the route

discovery and route reply messages being

generated in case the nodes do not have routes

provided to them by the ants for some

destinations. From the comparison results (fig. 6)

it is seen that the normalized overhead is too

high in case of ant-based routing scheme. The

reason for this is that the actual data packets

delivered are too less and hence the ratio of

control overhead to data packets delivered

becomes too high. In case of AODV (fig. 6) the

normalized overhead is the least. The normalized

overhead (fig. 6), is slightly greater in Ant-

AODV as compared to AODV because of the

continuous movement of ants in the network.

The continuous gradual drop in normalized

routing overhead (fig. 6) for all the three

protocols is attributed to the increased packet

delivery fraction and goodput at higher pause

times (normalized load is the ratio of total

control packets generated to actual data packets

received).

Connectivity is the average number of nodes in

the network for which a node has un-expired

routes. In case of Ant-AODV and ant-based

routing protocols (fig. 7), ant agents

continuously traverse the network and update the

routing table entries. Due to this, a node has

fresh enough (or un-expired) routes to a large

number of nodes in the network at any given

point of time. Connectivity in Ant-AODV and

ant-based routing schemes is more than double

the connectivity in AODV (fig. 7). Higher

connectivity leads to lesser route discoveries and

reduced end-to-end delay.

Fig. 6. Normalized routing overhead of Antbased,

AODV and Ant-AODV routing protocols.

Fig. 7. Average connectivity provided by Antbased,

AODV and Ant-AODV routing protocols.

During the simulations an important

characteristic of ant agents for routing in

MANETs was observed. After a certain period

(nearly 100 simulation seconds), the ant activity

(ant hopping from one node to the other and

updating routes) would almost subside. This

could be due to various reasons such as (i) the

ant packets could be lost in wireless

transmission, (ii) the next node which was to

receive the ant packet moves out of the wireless

range of the sending node, or (iii) the ant bearing

node goes out of wireless range of every node in

the network and there is no next hop node

available for the ant. In such situations the

number of ants actually available for routing

purpose decreases. To overcome this decrease in

number of ants available for routing, a

“minimum ant visit period” was set. If no ant

visited a node within this period the node would

generate a new ant and transmit it to one of its

neighbors selected randomly. This way the ant

activity would never subside and the network

would not become devoid of ants. The

simulations carried out used a minimum ant visit

period of 5 seconds.

It is evident from the simulation results that by

combining ant-like mobile agents with the ondemand

route discovery mechanism of AODV,

the Ant-AODV hybrid routing protocol would

give reduced end-to-end delay and route

discovery latency with high connectivity. Such

low end-to-end delay cannot be achieved from

either of the two base protocols (ant-based and

AODV) because of their inherent shortcomings.

The shortcomings of on-demand routing

protocols like AODV and ant-based routing have

been tried to overcome in this paper by

combining both of them to enhance their

capabilities and alleviate their weaknesses. Ant-

AODV hybrid protocol is able to provide

reduced end-to-end delay and high connectivity

as compared to AODV. As a result of increased

connectivity the number of route discoveries is

reduced and also the route discovery latency.

This makes Ant-AODV hybrid routing protocol

suitable for real-time data and multimedia

communication. As a direct result of providing

topology information to the nodes (using ants),

the foundations for designing a distributed

network control and management get

automatically laid. Higher connectivity and

reduced end-to-end delay are achieved at the cost

of extra processing of the ant messages and the

slightly higher overhead occupying some

network capacity. However this does not

adversely affect the packet delivery fraction or

the goodput. The future work would be to

explore the use of back up or multiple routes

provided to the nodes by ants in their frequent

and continuous visits to the node.

[1] C. E. Perkins and P. Bhagwat, “Highly

dynamic Destination Sequenced Distance-Vector

234-244, Aug. 1994.

[2] C. E. Perkins, E. M. Royer and S. R. Das,

“Ad Hoc On-Demand Distance Vector (AODV)

100, Feb. 1999.

[3] D. B. Johnson and D. A. Maltz, “Dynamic

Source Routing in ad hoc wireless networks,”

and Hank Korth, chapter 5, pp. 153-181. Kluwer

Academic Publishers, 1996.

[4] N. Minar, K. H. Kramer and P. Maes,

“Cooperating Mobile Agents for Dynamic

Verlag, 1999.

[5] H. Matsuo and K. Mori, “Accelerated Ants

Aug. 2001.

[6] R. R. Choudhary, S. Bhandhopadhyay and K.

Paul, “A Distributed Mechanism for topology

discovery in Ad Hoc Wireless Networks Using

146, Aug. 2000.

[7] K. Fall and K. Varadhan, editors. The ns

manual. The VINT Project, UC Berkeley, LBL,

USC/ISI and XEROX PARC, 2001.

http://www.isi.edu/nsnam/ns/nsdocumentation.

html

[8] J. Broch, D. Maltz, D. Johnson, Y.-C. Hu and

J. Jetcheva, “A Performance Comparison of

Multi-Hop Wireless Ad Hoc Network Routing

1998.