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.,
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
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
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
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.
|| 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.
|| Simulation settings
|| Nodes vs. delay
|| 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.
||Nodes vs. del. ratio
|| Receivers vs. delay
|| 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.
|| Receivers vs. del. ratio
|| Pcket size vs. delay
|| Packet size vs. throughput
|| 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.
|| 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.