Multiple Interface Parallel Approach of Bioinspired Routing Protocol for Mobile Ad Hoc Networks

1. Introduction

A mobile ad hoc network (MANET) [1] is a collection of mobile devices, which form a network of communication without predefined infrastructure. This fact determines the design of routing protocols for this type of network to suppose an arduous task. Particular types of routing protocols are called bioinspired [2], taking into account the behavior of some animals (insects, etc.) to obtain their food. Related to theses, the algorithms based on Ant Colony Optimization (ACO) [3], are particularly relevant. A representative protocol of so-called bioinspired is AntOR [4], adaptive and multihop routing protocol based on AntHocNet [5, 6]. The specification of this protocol includes two versions: disjoint-link routes (AntOR-DLR) and disjoint-node routes (AntOR-DNR). A parallel approximation of AntOR-DNR is PAntOR [7, 8] improving performances of AntOR-DNR through thread programming based on shared memory in the phases of routing information setup, route local repair, and link failure notification. This paper presents a new parallel approximation of AntOR-DNR, called PAntOR-Multiple Interface (PAntOR-MI) which, as its name suggests, differs essentially from PAntOR in the use of multiple interfaces. This paper consists of 6 sections, with this introduction being the first of them. The rest of the paper is structured as follows: Section 2 briefly discusses the most representative work on parallel techniques for bioinspired protocols based on the behavior of ants. Section 3 briefly comments on AntOR-DNR and PAntOR, also showing a comparison between both. Section 4 presents PAntOR-MI, with emphasis on differences from its predecessor, PAntOR. Section 5 shows a comparative study between AntOR-DNR, PAntOR, and PAntOR-MI. Finally, the conclusions are exposed in Section 6.

2. Related Works

In this section we present the most representative parallelization techniques that make ACO more efficient. First of which, introduced by [9], explains a method that can solve difficult combinatorial optimization problems. Stützle [10] applies an approximation master/slave to parallelize several different search methods of ACO solutions. Reference [11] shows a hybrid system of parallelization which consists of evaluating the performance of communication multithreading Message Passing Interface (MPI). This approach applies MPI between nodes and multithreading within nodes. Finally, [7, 8] presents PAntOR, an approximation parallel based on programming by threads, which constitutes the starting point of the present paper. The main idea of this protocol is to replace each broadcast message by a message managed by a thread that is addressed to each one-hop neighbour, that is, launches a thread by each node in the neighbour table. This is done in protocol phases: routing information setup, route local repair, and link failure notification.

3. AntOR versus PAntOR

AntOR [4] has the following characteristics which are different from AntHocNet [5, 6]:

PAntOR [7, 8] paralyze Disjoint-node version (AntOR-DNR) that consists of nodes from routes which are not shared. We have chosen this version because routes are more difficult to get and maintain. To understand how P-AntOR works, it is necessary to use three concepts well.

We use POSIX Thread because it allows a new concurrent process flow to expand, which is the most efficient multicore systems, generating a flow of processes that can be scheduled to run on another processor, thus speed through distributed processing is achieved. Programming with threads carries less overhead than expanding a new process, because the system does not initialize a new environment and virtual memory space for that process.

This version tries to replace each broadcast message by a message managed by a thread that is addressed to each one-hop neighbour.

This parallel technique, which launches a thread by each node in the neighbour table, is used in the following phases of AntOR.

3.1. Routing Information Setup

Figure 1 shows a flow chart representing the parallelism in the route discovery process. When a source node is ready to send data to the destination node, it activates the route discovery process. This process is parallelized using threads, so that it launches a Reactive Forward Ant (RFA) reactive to the one-hop neighbours through an independent thread. When an intermediate node receives this ant repeats the process, but whether it is a destination node, this node sends its corresponding Reactive Backward Ant (RBA).

OPEN IN VIEWER

Figure 1

Parallelization of route discovery phase.

3.2. Route Local Repair

The operation is similar to route discovery, unless it is done locally, as shown in Figure 2.

OPEN IN VIEWER

Figure 2

Parallelization of local route repair phase.

3.3. Link Failure Notification

This process updates the routing table to link failures. It is required to be taken promptly because of its importance. The nodes send ants through independent threads until an intermediate node has some alternative route to the destination after updating the routing table, as shown Figure 3.

OPEN IN VIEWER

Figure 3

Parallelization of link failure notification phase.

3.4. Results

Next we show a comparison between PAntOR and AntOR. To this end, the metrics used in the simulations were as follows.

 (i)

Throughput: consists of volume of work or information flowing through a system. It is calculated by dividing the total number of bits delivered to the destination by the packet delivery time.

 (ii)

Delivered Data Packet Ratio: relationship between number of packets sent and the number of packets delivered successfully.

 (iii)

Overhead in number of packets: relationship between the total numbers of transmitted control packets by the nodes of network and the number of delivered data packets to their destinations.

Experiments with the Network Simulator NS-3 have been realized. Simulations parameters are as follows: we have used 100 nodes configured according to the Standard IEEE 802.11b, moving in a random scenario of dimensions 1200 m × 1200 m according to the mobility pattern Random WayPoint (RWP). The application of data traffic is Constant Bit Rate (CBR) with a rate of packet sending of 2048 bps (4 packets of 64 bytes per second). We apply 5 random data sessions, where mobility is variable from 0 m/s up to a maximum of 10 m/s. Pause time is kept constant to a value of 30 s. Total simulation time is 120 s. In Figure 4 we can observe how the Throughput is better at PAntOR at AntOR.

OPEN IN VIEWER

Figure 4

Constant speed against Throughput.

In Figure 5 see how overhead in number of packets is better in the parallel version than in the original, because the creation of routes is faster.

OPEN IN VIEWER

Figure 5

Constant speed against overhead in number of packets.

Figure 6 behaves similar to the representation in Figure 4, but using another scale. It notes that the performance of the packet delivery remains reasonably good even at high speeds.

OPEN IN VIEWER

Figure 6

Constant speed against Delivered Data Packet Ratio.

4. PAntOR-Multiinterface

This variant of PAntOR consists of having more than one interface, and to parallelize the sending of broadcast messages by interface through threads. Each interface is managed by a thread. The main idea of this parallelization is to be applied to systems with several multiinterfaces, which launches an ant broadcast mode in an independent thread for each interface that provides the node. The main difference with PAntOR is that PAntOR-MI uses more than one interface, parallelizing each interface by means of a thread.

To understand this variant we provide Algorithm 1.

Algorithm 1: Parallelization core in PAntOR-MI.

It can be seen that while running the routing information setup, a reactive message is launched in a broadcast way for each interface that have the node, and such an interface via a thread is managed.

5. PAntOR-MI versus AntOR and PAntOR

The performance metric analyzed in this comparison is Delivered Data Packet Ratio, which consists of the relationship between the number of packets sent and the number of packets delivered correctly. To perform this comparison Network Simulator NS-3 has been used with the following parameters: a random scenario with dimensions of 1200 m × 1200 m has been designed, where 100 nodes configured according to the Standard IEEE 802.11b; they move according to the mobility pattern Random WayPoint (RWP). The application of data traffic is based on Constant Bit Rate (CBR) with a packet sending rate of 2048 bps (4 packets of 64 bytes per second). We apply 5 random data sessions, where mobility is variable from 0 m/s up to a maximum of 10 m/s. Pause time is kept constant to a value of 30 s. Total simulation time is 120 s. In this comparison PAntOR-MI use nodes with two interfaces.

In Figure 7 we appreciate how the delivered packet ratio is better in these two parallel versions than in AntOR. Also we see how PAntOR-MI improves to AntOR and PAntOR. Also a greater tolerance to the mobility of the nodes is observed, behaving better in the more dynamic scenarios.

OPEN IN VIEWER

Figure 7

Constant Speed against Delivered Data Packet Ratio.

6. Conclusions

This work has presented a new bioinspired routing protocol for mobile ad hoc networks obtained thanks to new parallelization techniques of a base protocol called AntOR which has two versions, the so-called Disjoint-link (AntOR-DLR) and Disjoint-node (AntOR-DNR). The new parallel approach (PAntOR-MI) used the disjoint-node version of AntOR (AntOR-DNR) as the main protocol, as well as the existing (PAntOR). The parallelization technique employed is a large-grained approach, in which a multicore machine in a shared memory system has been used. The novelty of PAntOR-MI is that we have more than one interface, and we parallelize the sending of broadcast messages by interface using threads. Each interface is managed by a thread. The obtained simulation results indicate that PAntOR-MI improves performances of PAntOR, with further observations showing that this improvement is most evident in most dynamic environments.