Swarm based Reliable and Power Efficient Multicast Routing in Mobile Ad Hoc Network

INTRODUCTION

A mobile ad-hoc network (MANET) is composed of mobile nodes without any infrastructure. Mobile nodes self-organize to form a network over radio links. The goal of MANETs is to extend mobility into the realm of autonomous, mobile and wireless domains, where a set of nodes form the network routing infrastructure in an ad-hoc fashion. The majority of applications of MANETs are in areas where rapid deployment and dynamic reconfiguration are necessary and wired network is not available. These include military battlefields, emergency search, rescue sites, classrooms and conventions, where participants share information dynamically using their mobile devices. These applications lend themselves well to multicast operations (Junhai et al., 2008).

Multicasting is aimed to deliver data to a set of selected receivers. There is no restriction on the location or number of members in a host group. Multicast can be classified into one to many or many to many communication applications. The important member identifications and functions are: group member, sources, destination, forwarding nodes, non-group member. The group membership is dynamic means that hosts may join and leave groups at any time multicast packets are delivered to each member of a multicast group with the same best-efforts reliability and performance as unicast packets to members. Multicast groups may be of arbitrary size, may change membership dynamically and may have either a global or local scope. The senders do not need to know membership groups and needs not to be a member of that group (Baryun and Al-Begain, 2008). In addition, within a wireless medium, it is crucial to reduce the transmission overhead and power consumption. Multicasting can improve the efficiency of the wireless link when sending multiple copies of messages by exploiting the inherent broadcast property of wireless transmission. Hence, reliable multicast routing plays a significant role in MANETs (Junhai et al., 2008).

Multicasting can be used to improve the efficiency of the wireless link when sending multiple copies of messages to exploit the inherent broadcast nature of wireless transmission. So, multicast plays an important role in MANETs. Unlike typical wired multicast routing protocols, multicast routing for MANETs must address a diverse range of issues due to the characteristics of MANETs, such as low bandwidth, mobility and low power. MANETs deliver lower bandwidth than wired networks; therefore, the information collection during the formation of a routing table is expensive (Junhai et al., 2008).

For designing the multicast protocol, the following wireless mobile network characteristics have to be considered, which are; limited BW, frequent handoff of mobile hosts, error-prone wireless links and limited battery life of mobile device. In contrast, for the design optimization, minimizing the consumption of network resources and overheads are very essential (Baryun and Al-Begain, 2008).

Reliable multicasting means that all nodes of a multicast group should acquire a packet that is sent to the group address. These multicast routing protocols which are on the basis of IP offers good data delivery, but doesn’t provide any assurance of the delivery. For a reliable data delivery, there should be another protocol which must function on top of IP such that it identifies packet losses and starts the mechanism to recover them. It is proven that providing reliability of data delivery is a difficult job. Besides we notice that retransmission is the only solution that is left to recover lost packets (Kone et al., 2005).

Conventional multicasting routing protocols basically aspire to lessen the propagation delay, because most of the multicast applications are delay sensitive but they do not consider the problem of energy consumption as an issue. In recent times, the importance has been given for the design of energy efficient multicast routing protocols due to the limited battery power supply of mobile nodes. For that reason, to design a suitable energy efficient multicast routing protocol to save power at the maximum level and yet to attain better system performance is a difficult task (Hwang and Pang, 2007).

In this study, we propose a multicast routing scheme by using swarm intelligence with the help of reliability metric. It identifies the reliable nodes and connects it through intermediate nodes there by constructing a backbone for multicasting. Reliability metric is based on the energy, bandwidth and mobility factors.

Di Caro et al. (2005a) have presented AntHocNet, a routing algorithm for MANETs which was taken from the concept of MANHSI Intelligence and from the structure of ACO. Their algorithm merges reactive and proactive behavior to deal with the particular hindrances of MANETs in a proficient way. AntHocNet outplayed AODV over a variety of tested models in terms of delivery ratio, average end-to-end delay and average jitter, while producing a considerable measure of control overhead. It was noticed that the positive thing of AntHocNet over AODV increased for larger networks, particularly in terms of overhead, which shows that AntHocNet is highly scalable than AODV.

Ducatelle et al. (2008) have analyzed the performance of two MANHSI intelligence MANET routing algorithms in a practical urban environment. ANSI and AntHocNet are the two algorithms, which were compared to AODV, a contemporary reactive algorithm and OLSR, a contemporary proactive algorithm. They aspired to explore the utility of the various methods implemented by the algorithms when dealt with the individuality of urban environments and the necessities of real-world applications.

Prasad et al. (2009) presented Probabilistic Ant Routing, a novel proactive algorithm, in mobile ad hoc networks for routing. This proactive algorithm is motivated by Ant Colony Optimization (ACO) framework and it employs ants for route discovery, maintenance and development. Their algorithm is on the basis of an alteration of the state transition rule of ACO routing algorithm which results in sustaining greater level of degree of investigation in the search space together with congestion knowledge. Their proposed algorithm is tested for various network sizes and node mobility.

Alfawaer et al. (2007) have introduced MANHSI (Multicast for Ad hoc Network with hybrid MANHSI Intelligence) protocol, which is based on a MANHSI intelligence based optimization technique to learn and find out an efficient multicast connectivity. The given protocol shows that it can launch initial multicast connectivity in a fast and efficient way. It can also enhance the resulting connectivity through different optimization methods.

Pinto et al. (2005) have proposed a new multi-objective algorithm which is on the basis of ant colonies. Their proposed algorithm is employed in constructing the multicast tree for data transmission in a computer network. The given algorithm was motivated from a Multi-Objective Ant Colony System (MOACS).

Huang et al. (2007) have presented an algorithm which is based on the Ant System algorithm. This efficient algorithm is utilized for generating a low-cost multicast routing subject to delay constraints (ASDLMA). The AS algorithm which is used in ASDLMA, to support group communication in multimedia, is described here. For quality of service, the necessity of multimedia group communication is assured by the algorithm.

ANT COLONY OPTIMIZATION AND SWARM INTELLIGENCE

Ant Colony Optimization (ACO): Ant Colony Optimization (ACO) can be defined as a paradigm for designing metaheuristic algorithms for combinatorial optimization problems. The important attribute of ACO algorithms is the combination of prior information about the structure of an encouraging result with posterior information about the structure of the results obtained earlier. In 1991, AS, the first algorithm on the lines of this framework was presented, since then many varied variants of the basic principle have been described in the literature. The key fundamental idea, which is heavily motivated by the behavior of real ants, is that of a parallel search over several constructive computational threads, which is on the basis of local problem data and on a dynamic memory structure which contains information about the quality of earlier acquired result. The collective behavior originating from the interaction of the different search threads has resulted to be fruitful in solving Combinatorial Optimization (CO) problems (Maniezzo et al., 2004).

ANTS is an enhancement of the AS which gives some under-defined elements of the general algorithm, for example the attractiveness function to use or the initialization of the trail distribution. The first algorithm that used an ACO based algorithm to a more common version of the ATSP problem is Hybrid Ant System for the Sequential Ordering Problem (HAS-SOP) (Maniezzo et al., 2004). MAX-MIN Ant System (MMAS) is one of the most thriving ACO variants (Alaya et al., 2007). M. Dorigo and G. Di Caro invented AntNet, which is a routing protocol for packet switched networks. It is a backup routing algorithm for the recognized OSPF protocol, which is based on Ant Colony Optimization (ACO) (Verstraete et al., 2006). AntHocNet is a hybrid routing algorithm for MANETs. AntHocNet's design is on grounds of a specific self-organizing behavior noticed in ant colonies, the shortest paths discovery and on the related optimization framework of Ant Colony Optimization (ACO) (Di Caro et al., 2005b).

Cases of ACO have been employed widely to a diversity of discrete combinatorial optimization problems like the Traveling Salesman Problem (TSP), Sequential Ordering, the Network Communication Routing Problem, Vehicle Routing Problem, the Quadratic Assignment Problem (QAP), Job-Shop scheduling, graph Coloring, time tabling, shape optimization, etc. Continuous Ant Colony Optimization (CACO), the first method, was presented by Bilchev and Parmee and later it was used by some people. Some of the other methods are Asynchronous Parallel Implementation (API) algorithm by Monmarche and Continuous Interacting Ant Colony (CIAC) by Dreo and Siarry. For reservoir operation, Jalali et al. presented Discrete Ant Colony Optimization (DACO) algorithms (Afshar et al., 2006).

Swarm intelligence: The self-organizing systems in nature, for instance, the insect societies exhibit desirable properties. By employing only a few numbers of relatively simple biological agents (namely, the ants) a range of diverse organized behaviors is created at the system-level from the local communications among the agents and with the environment. The strength and efficiency of such collective behaviors relating to variations of environment conditions are main features of biological success. These kinds of systems are commonly related to the term SWARM Intelligence.

Recently, SWARM systems have become a cause of motivation for the design of distributed and adaptive algorithms particularly, routing algorithms. SWARM intelligence is the evolving collective intelligence of group of simple autonomous agents. Here, an autonomous agent is a subsystem that interacts with its environment which perhaps comprises of other agents, but, acts comparatively independent from all other agents. The autonomous agent does not pursue commands from a head, or some comprehensive plan. For instance, if a bird has to join a flock, it modifies only its movements to synchronize with the movements of the other birds, in other words, its neighbors that are close to it in the flock (Shirodkar et al., 2009).

Routing algorithms for MANETs must be robust, decentralized, self organized and adaptive. The MANHSI intelligence which is based on ants and birds possess such a kind of qualities, which encourage us to use SWARM for routing tasks in MANET.

RELIABLE AND POWER EFFICIENT MULTICAST ROUTING

System design: A MANET has been considered (Fig. 1), which comprises of several nodes that are randomly scattered across a given geographical area. It consists of a backbone which is constructed with the help of reliable nodes. By means of some intermediate nodes, a reliable node can connect to another reliable node. Multicast group members can be linked to any one of the reliable node. Multicast operations are supported by all the reliable nodes but intermediate nodes merely forward packets from one reliable node to another reliable node. Mobility is supported by the reliable nodes, group member nodes and intermediate nodes. When mobility is considered, multicast routes will be reconfigured by employing different set of reliable and intermediate nodes. All the nodes comprise of mobile agent platform that supports mobility, communication, security and persistence.

Fig. 1:	System architecture

In the proposed scheme, at every node in the network, it comprises of a multicast routing agency. The multicast routing agency contains the Swarm agents called FA (Forwarding ants) and BA (Backward ants). FAs, the mobile agents, travel from node to node to find out the best route in forward direction. BAs are the mobile agents that travel in the reverse direction to the FAs to validate the best path and update the routing table at each of the visited intermediate nodes.

Forwarding Ants (FA) compute the current network state with the help of trip times, hop count or Euclidean distance. They are commenced towards the randomly chosen geographical locations. In this scheme we prefer to assign the node ID of the next hop.

Backward Ants (BA) does the function of informing the beginning node about the information gathered by the FA. BAs carry extra data from the FAs and so they are able to update both forward and backward paths at the same time. The destination node gets the trip time and hops count and places it into the BA (Maniezzo et al., 2004).

Reliability metric (RM) of a node: For each node, the Reliability Metric (RM) is calculated on the basis of the following parameters.

Then RM can be calculated as:

(1)

where, c1,c3 and c3 are the minimum threshold constants varying in the range 0 to 1 as determined by the network nodes. These threshold constants are helpful in the conditions where the network resources are not obtainable at a specific time, for example, in case of high values of BI and MI, a node that is nearly depleted can still become a reliable node.

A reliable node can be defined as the one that has highest Reliability Metric (RM). It takes the task of providing connection to its neighbor nodes known as children nodes whenever a multicast group joining is needed. In general, children nodes do not take part in packet forwarding. Reliable node keeps its children list. At times reliable nodes may not be in each other’s range, therefore there is a need of selecting intermediate nodes to form interconnections between the reliable nodes. Some of the other actions of the intermediate nodes are in packet forwarding actions and maintenance of connection list.

Backbone construction: For describing the proposed scheme, a two dimensional environment grid is taken into account. Mobile nodes are arranged on the grid in a scattered manner. Each ant is modeled as autonomous software agent that is capable of hopping from node to node. The multicast group’s size is predefined.

The swarm agent at each node computes the RM for that node and exchanges the RM to its neighbors. The swarm agent at each node receives the RM values of other nodes and finds the node which has highest RM. The node with the highest RM will affirm itself as a reliable node and notify to other nodes.

The FA may find a reliable node within its three hop movement. If it discovers the path, then it pushes the found path to the host node by the BA. Incase, if it does not discovers the path, then it notifies the parent agent and demolishes itself. After getting the paths from the BAs, swarm agent decides the best path with minimum hops and maximum reliability.

The FA at each reliable node travels over selected path between the reliable nodes and sets the connection list at intermediate nodes and produces a packet forwarding table. Packet forwarding is supported by the reliable and intermediate nodes. FA at each reliable node finds all its child nodes and makes a children list. Now the backbone is set for communication.

Multicast routing: The routing scheme is described in the following sequences. The parameters stored in routing table are as follows.

Any active source of the group which has the data to send chooses it’s nearest reliable node by estimating its RM and announces that as reliable node by sending a reliable node notification packet RELNOTE. The member nodes that receive the packet respond by choosing their reliable nodes and send RELNOTE packets.

The chosen reliable nodes use FAs to find the path to other reliable nodes. FAs once reach the target reliable nodes generates BAs that move in the reverse direction and update the pheromone table. The pheromone intensity of the link increases through which backward ants visit. Thus routes between the reliable nodes are discovered.

Each member node then relies on the reliable nodes to establish initial connectivity by sending a JOIN REQUEST. The forwarding nodes deploy the FAs to find the best path to connect group member after finding all possible paths.