In this study, we proposed to design a Reliable and Power Efficient Multicast Routing (RPEMR) protocol by using swarm intelligence with the help of reliability metric. In this protocol, reliability metric is computed by each node based on the power, bandwidth and mobility. Then the reliable nodes with the high reliability metric are determined. The swarms forward and backward agents construct a backbone for multicasting, by estimating the best path which connects the reliable nodes through intermediate nodes. The established paths provide reliable, shorter and faster communication. By simulation results, we show that the proposed protocol provides reliable and power efficient multicasting routing, by attaining high packet delivery ratio and low energy consumption, compared to the existing protocols.
PDF Abstract XML References Citation
How to cite this article
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 doesnt 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.
|•||Node power index (PI): It is the ratio of existing battery power to the maximum battery power|
|•||Bandwidth index (BI): It is the ratio of the bandwidth consumed to the maximum bandwidth available in its area of coverage|
|•||Mobility index (MI): It is ratio of number of movements made to maximum allowed movements for stability in the recent interval|
Then RM can be calculated as:
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 others 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 groups 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.
|•||Join table: Maintains a list of nodes that have requested to join the multicast group via the node. This table is updated when node hears a JOIN REQUEST packet intended to itself|
|•||Pheromone table: Maps the neighboring nodes and their heights to pheromone intensity|
Any active source of the group which has the data to send chooses its 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.
Simulation model and parameters: The NS2 is used to simulate the proposed algorithm. In this simulation, the channel capacity of mobile hosts is set to the same value: 2 Mbps. The Distributed Coordination Function (DCF) of IEEE 802.11 for wireless LANs as the MAC layer protocol is used. It has the functionality to notify the network layer about link breakage.
In the simulation, mobile nodes move in a 600x600 m rectangular region for 50 sec simulation time. Initial locations and movements of the nodes are obtained using the random waypoint (RWP) model of NS2. I assume each node moves independently with the same average speed. All nodes have the same transmission range of 250 m. In this mobility model, a node randomly selects a destination from the physical terrain. It moves in the direction of the destination in a speed uniformly chosen between the minimal speed and maximal speed. After it reaches its destination, the node stays there for a pause time and then moves again.
Performance metrics: Our proposed Reliable and Power efficient Multicasting Routing (RPEMR) protocol is compared with MANHSI (Prasad et al., 2009) protocol. The evaluation is mainly based on performance according to the following metrics:
Delay: It is average end-to-end-delay of the transmission.
Throughput: It is the number of packets received successfully.
Packet delivery fraction: It is the ratio of the fraction of packets received successfully and the total No. of packets sent.
Average energy: It is the average energy consumption of all nodes in sending, receiving and forward operations, our simulation settings and parameters are summarized in Table 1.
Results Based on nodes: In our initial experiment, we vary the number of nodes as 10, 20, 30, 40 and 50.
|Table 1:||Simulation settings|
|Fig. 2:||Nodes vs. delay|
|Fig. 3:||Nodes vs. throughput|
From Fig. 2, we can see that the average end-to-end delay of the proposed RPEMR protocol is less when compared with MANHSI protocol.
Figure 3 shows the throughput of both the protocols when the number of nodes is increased. As we can see from the figure, the throughput is more in the case of RPEMR than the MANHSI protocol.
Figure 4 shows the packet delivery ratio of both the protocols. Since, the packet drop is less and the throughput is more, RPEMR achieves good delivery ratio, compared to the MANHSI protocol.
Based on number of receivers: In the second experiment, we vary the group size or the number of receivers as 5, 10, 15, 20 and 25.
|Fig. 4:||Nodes vs. del. ratio|
|Fig. 5:||Receivers vs. delay|
|Fig. 6:||Receivers vs. throughput|
From Fig. 5, we can see that the average end-to-end delay of the proposed RPEMR protocol is less when compared with MANHSI protocol.
Figure 6 shows the throughput of both the protocols when the number of receivers is increased. As we can see from the figure, the throughput is more in the case of RPEMR than SWAN protocol.
Figure 7 shows the packet delivery ratio of both the protocols. Since, the packet drop is less and the throughput is more, RPEMR achieves good delivery ratio, compared to the MANHSI protocol.
Based on packet size: In the third experiment, we vary the packet size as 250, 500, 750 and 1000.
From Fig. 8, we can see that the average end-to-end delay of the proposed RPEMR protocol is less when compared with MANHSI protocol.
|Fig. 7:||Receivers vs. del. ratio|
|Fig. 8:||Pcket size vs. delay|
|Fig. 9:||Packet size vs. throughput|
|Fig. 10:||Packet size vs. del. ratio|
Figure 9 shows the throughput of both the protocols when the number of nodes is increased. As we can see from the figure, the throughput is more in the case of RPEMR than the MANHSI protocol.
Figure 10 shows the packet delivery ratio of both the protocols. Since, the packet drop is less and the throughput is more, RPEMR achieves good delivery ratio, compared to the MANHSI protocol.
|Fig. 11:||Packet size vs. energy|
Figure 11 shows the results of energy consumption for the packet size 250, 500, 750 and 1000. From the results, we can see that RPEMR scheme has less energy than MANHSI scheme.
In this study, we have designed a Reliable and Power Efficient Multicast Routing (RPEMR) protocol by using swarm intelligence with the help of reliability metric. In this protocol, reliability metric is computed by each node based on the power, bandwidth and mobility factors. Then the reliable nodes with the high reliability metric are determined. 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. The swarms forward and backward agents construct a backbone for multicasting, by estimating the best path which connects the reliable nodes through intermediate nodes. The established paths provide reliable, shorter and faster communication. Simulation results shows that the proposed protocol provides reliable and power efficient multicasting routing, by attaining high packet delivery ratio and low energy consumption, compared to the existing protocols.
- Pinto, D., B. Baran and R. Fabregat, 2005. Multi-objective multicast routing based on ant colony optimization. Frontiers Artif. Intell. Appl., 131: 363-370.
- Ducatelle, F., G.A. Di Caro and L.M. Gambardella, 2008. An evaluation of two swarm intelligence MANET routing algorithms in an urban environment. Proceedings of the IEEE Swarm Intelligence Symposium, Sept. 21-23, St. Louis, Missouri, USA., pp: 1-8.
- Alaya, I., C. Solnon and K. Ghedira, 2007. Ant colony optimization for multi-objective optimization problems. Proceedings of the 19th IEEE International Conference on Tools with Artificial Intelligence, October 29-31, 2007, Patras, Greece, pp: 450-457.
- Hwang, I.S. and W.H. Pang, 2007. Energy efficient clustering technique for multicast routing protocol in wireless ad hoc networks. Int. J. Compt. Sci. Network Security, 7: 74-81.
- Huang, L., H. Han and J. Hou, 2007. Multicast routing based on the ant system. Applied Math. Sci., 1: 2827-2838.
- Shirodkar, B.D., S.S. Manvi and A.J. Umbarkar, 2009. Multicast routing for mobile ad-hoc networks. Int. J. Recent Trends Eng., 1: 36-40.
- Prasad, S., Y.P. Singh and C.S. Rai, 2009. Swarm based intelligent routing for MANETs. Int. J. Recent Trends Eng., 1: 153-158.
- Verstraete, V., M. Strobbe, E. van Breusegem, J. Coppens, M. Pickavet and P. Demeester, 2006. AntNet: ACO routing algorithm in practice. Proceedings of the 8th INFORMS Telecommunications Conference, (ITC'06), Texas, USA., pp: 1-3.