Skip to main content

Simple Ant Routing Algorithm (SARA)

The Simple Ant Routing Algorithm (SARA) offers a low overhead solution, by optimizing the routing process.

Three complementary strategies were used in our approach: during the route discovery we have used a new broadcast mechanism, called the Controlled Neighbor Broadcast (CNB), in which each node broadcasts a control message (FANT) to its neighbors, but only one of them broadcast this message again. During the route maintenance phase, we further reduce the overhead, by only using data packets to refresh the paths of active sessions. Finally, the route repair phase is also enhanced, by using a deep search procedure as a way of restricting the number of nodes used to recover a route. Thus, instead of discovering a new path from the source to the destination, we start by trying the discovery of a new path between the two end-nodes of the broken link. A broadest search is only executed when the deeper one fails to succeed.

The Route Discover and Route Repair procedures introduced in SARA can be considerated as general proposed and used in other routing
protocols.

Actually I am extending SARA' features to include different pheromone management models and different concepts about to
deal with broken link situations on a mobile environment.

SARA simulation code

This is ns-2 simulation code for SARA (sara, aux_obj, tx_cbr) used in preparation of my Elsvier and Phd thesis paper. The install instructions are here.

To test this code use the following scripts. In there it is used both FTP over TCP traffic and the TxCBR module.


NOTE: the ns-2 version that I used was Vrs. 2.31.



Files

Description

sara/sara.cc

main class which includes all procedures to discover, select,
maintain, and repair the routes.

sara/sara_ngh.cc

creates an object for each node in the neighborhood. Has
ara_base as root object.

sara/sara_rt.cc

creates an object for each route found by each network node.
sara_rt has a pointer to a list of the sara_rotas object. Has ara_base
as root object.

sara/sara_rotas.cc

for each known route, sara_rotas object indicate which is the
link for the next hop. Has ara_base as root object.

sara/sara_seq_num.cc

creates an object for each route discovery procedures. This
object will keep track of the FANT agents sent to the network. Has
ara_base as root object.

sara/sara_session.cc

it is used identify which are the route repair procedure
active. Has ara_base as root object.

sara/sara_pkt.h

definitions used in the SARA control agents - FANT, BANT,
RFANT, RBANT, RRERROR

ara/ara_base.cc

this is the top class for this architecture. It works with
ara_vector, in which is implemented a list of ara_base object.

ara/ara_vector.cc

this class that implements a list of ara_base objects, i.e.,
it can hold different list, one for each sara class.

ara/ara_alg.cc

this class has several general purpose function.

ara/ara_rqueue.cc

this class implements a temporay queue to keep the data
packets transported by TCP while SARA is discovering / repairing the
route

ara/ara_path.cc

this is used to record information about the path used just
for statistical information. Has ara_base as root object.

tx_cbr/tx_cbr.cc

the tx_cbr class allows SARA to implement CBR traffic in both
directions. The tx_cbr works directly over IP. It allows to connect
multiple sources to one destination node on a wireless environment.



TCL configuration variables for
SARA and TX_CBR

TCL configuration variable

SARA value

Function

F_

1

route convergence factor - F

ph_valid_

1.0

pheromone activity interval (sec)

rand_seed_

0

use in random number generator. '0' indicates NS2 choose the
seed to be used

bcast_limit_

2

broadcast limit for the route repair procedure

hello_int_

5.0

hello transmission interval (sec)

rd_int_

0.5

interval to generate FANT during the route discovery procedure
- T0 (sec)

sd_int_

0.2

FANT confirmation in terval - T1 (sec)

rr_int_

1

type to repair a route. After this time an error message is
send to the source node (sec)

retry_

3

maximum consecutive transmission attempts before consider the
link is disable - MAX_TX

delta_

0.1

link recover index (0 < delta_ < 1)

ph_max_level_

50

maximum pheromone value allowed on each link when is used
PPR-MV model (ph_mod_ = 3)

metrica_

0

identify the metric used in the path selection function. The
only value admited is '0' (other values wait future development)

gps_

0

activate GPS information to be used in the hello messages: 0 -
no GPS, 1 - yes

log_cbr_

0.5

log interval for CBR traffic (sec)

ph_mod_

3

pheromone management model: 0 - AS model, 1 - TAP, 2 - PPR, 3
- PPR-MV (see paper Models for pheromone evaluation in

Ant Systems for Mobile Ad-hoc networks - IARIA2008)

taxa_evaporacao_

0.5

evaporation value for AS pheromone model (0 <
taxa_evaporacao_ < 1)

TCL configuration variable

TX_CBR value

Function

packet_size_

1000

CBR packet size (bytes)

txInt_

0.16

transmission interval - for each 160ms, sending 1000B = 50kbps



SARA trace symbols

SARA can write some usefull informationdirectly into the trace file.
That information has the following code:

*P  (PATH)                                  - <sim_time> <node_id> <#used path>

*D  (DISCOVERY)                     - <node_id> <#route discovery procedure calls> <#route repair procedure calls>

*RT (ROUTE TABLE)               - <node_id> <#rt_entries> <max_rt_entries> <rt_size_B> <max_rt_size_B>

*C   (CONTROL)                        - <node_id> <pkt_control_size> <next_node_id> <msg_type> <next_hop>

*S   (DATA SEND)                     - <node_id> <pkt_data_size> - for TCP - IP and TCP header included, for TxCBR only the data bytes 

*R   (DATA RECEIVED)           - <node_id> <data_size> <delay>

*TD (TIME DISCOVERY)         - <route_disc_time> <no_id> <#hops> <src_node> <dst_node> <sim_time>

*MSG (PACKET SEQUENCE) - <dst_node> <src_node> <pkt_sn> <OK|KO> <sim_time>