|

 

Monet059_main.dvi

Ad hoc Multicast Routing Algorithm with Swarm Intelligence Chien-Chung Shen1 Chaiporn Jaikaeo2 Department of Computer and Information Sciences University of Delaware Tel: (302) 831-1951 Fax: (302) 831-8458 Department of Computer Engineering Faculty of Engineering, Kasetsart University 50 Phahonyothin Rd., Lardyaw JatuJak, Bangkok 10900 Swarm intelligence refers to complex behaviors that arise from very simple individual behaviors and interac- tions, which is often observed in nature, especially among social insects such as ants. Although each individual(an ant) has little intelligence and simply follows basic rules using local information obtained from the environ-ment, such as ant's pheromone trail laying and following behavior, globally optimized behaviors, such as findinga shortest path, emerge when they work collectively as a group. In this paper, we apply this biologically inspiredmetaphor to the multicast routing problem in mobile ad hoc networks. Our proposed multicast protocol adapts acore-based approach which establishes multicast connectivity among members through a designated node (core).
An initial multicast connection can be rapidly setup by having the core flood the network with an announcementso that nodes on the reverse paths to the core will be requested by group members to serve as forwarding nodes. Inaddition, each member who is not the core periodically deploys a small packet that behaves like an ant to oppor-tunistically explore different paths to the core. This exploration mechanism enables the protocol to discover newforwarding nodes that yield lower total forwarding costs, where cost is abstract and can be used to represent anymetric to suit the application. Simulations have been conducted to demonstrate the performance of the proposedapproach and to compare it with certain existing multicast protocols.
Keywords: Ad hoc networks, multicast routing, swarm intelligence
This work is supported in part by National Science Foundation under grant ANI-0240398.
Mobile wireless ad hoc networks consist of mobile nodes that autonomously establish connectivity via multihopwireless communications. Without relying on any existing, pre-configured network infrastructure or centralizedcontrol, they are useful in many situations where impromptu communication facilities are required, such as battle-field communications and disaster relief missions. In many applications, nodes are likely to collaborate to achievecommon goals and are expected to communicate as a group rather than as pairs of individuals (point-to-point). For in-stance, soldiers roaming in the battlefield may need to keep listening to their group commander (point-to-multipoint),or a group of commanders exchange current mission scenarios with one another (multipoint-to-multipoint). There-fore, multicast communication serves as one critical operation to support these applications.
Many different multicast protocols have been proposed for ad hoc networks. Some protocols are based on constructing a tree spanning all the group members. A node then accepts packets only when they are coming fromanother node with which a tree branch has been established. However, since there is only a single path between apair of sender and receiver, the scheme is vulnerable to network dynamics. Consequently, several protocols aim toconstruct a mesh that allows data packets to be transmitted over more than one path from a sender to a receiver toincrease robustness at the price of redundancy in data transmission. Multicast protocols can also be classified by howmulticast connectivity is established and maintained. In a source-based approach, a tree or a mesh is constructed permulticast sender, where the construction process is often initiated by the sender. While in a group-shared tree/meshapproach, a single multicast connection is shared by all senders of the same group. One common technique usedin this approach is to assign a node, known as the rendezvous point or the core [2], to accept join requests frommembers. The multicast connection then consists of shortest paths from the core to each of the members.
In this paper, we propose a novel multicast routing protocol for mobile ad hoc networks that adopts swarm intelligence to reduce the number of nodes used to establish multicast connectivity. We name the protocol Multicastfor Ad hoc Networks with Swarm Intelligence or MANSI for short. Swarm intelligence refers to complex behaviorsthat arise from very simple individual behaviors and interactions, which is often observed in nature, especially amongsocial insects such as ants and honeybees. Although each individual (for instance, an ant) has little intelligence andsimply follows basic rules using local information obtained from the environment, global optimization objectives1emerge when they work collectively as a group. Similarly, MANSI utilizes small control packets equivalent to antsin the physical world. These packets, traveling like biological ants, deposit control information at nodes they visit,similar to the way ants laying pheromone trails. This information, in turn, affects the behavior of other ant packets.
With this form of indirect communication (known as stigmergy), the deployment of ant-like packets resembles anadaptive distributed control system that evolves itself to a more efficient state, accommodating the current conditionof the environment.
For each multicast group, MANSI determines a set of intermediate nodes, forming a forwarding set, that connect all the group members together and are shared among all the group senders. By adopting a core-based approach,the forwarding set is initially formed by nodes that are on the shortest paths between the core and the other groupmembers, where the core may be one of the group members or senders. In addition, during the lifetime of themulticast session (i.e., when there is at least one active sender), the forwarding set will evolve, by means of swarmintelligence, over time into states that yield lower cost, which is expressed in terms of total cost of all the nodes inthe forwarding set. This evolving, including exploring and learning, mechanism differentiates MANSI from otherexisting ad hoc multicast routing protocols. Since a node's cost is abstract and may be defined to represent different 1An example of these is that ants often find a shortest path from their nest to the food source Figure 1: Examples of multicast connectivity among three group members: (a) a forwarding set of six nodes formedby shortest paths from the core to the other two members, and (b) another forwarding set when A partially sharesthe same path to the core with B, which results in more efficient data packet forwarding metrics, MANSI can be applied to many variations of multicast routing problems for ad hoc networks such as loadbalancing, secure routing, and energy conservation.
The remainder of the paper is organized as follows. We first describe the motivation and overview of the MANSI protocol in the next section. Section 3 explains the protocol in details. Simulation results are then presented anddiscussed in Section 4. Related works are reviewed in Section 5. And Section 6 concludes the paper with futureresearch efforts.
Overview of MANSI
MANSI is an on-demand multicast routing protocol that creates a multicast connection among group members bydetermining a set of intermediate nodes that serve as forwarding nodes. This set, called a forwarding set, is sharedamong all the senders of the group. The protocol exploits a core-based technique where each member joins thegroup via the core node in order to establish a connection with the other group members. Unlike the core-based tree(CBT) protocol [2], however, the core of each group is not statically assigned to a particular node in the networkand is not known in advance by the members. Instead, the first member who becomes an active source (i.e., startssending data to the group) takes the role of the core and announces its existence to the others by flooding the networkwith a CORE ANNOUNCE packet. Each member node then relies on this announcement to reactively establish initialconnectivity by sending a JOIN REQUEST back to the core via the reverse path. Nodes who receive a JOIN REQUESTaddressed to themselves become forwarding nodes of the group and are responsible for accepting and rebroadcastingnon-duplicated data packets, regardless of which node the packets were received from. Therefore, MANSI does notrely on any unicast routing protocol. To maintain connectivity and allow new members to join, the core floods COREANNOUNCE periodically as long as there are more data to be sent. As a result, these forwarding nodes form amesh structure that connects the group members together, while the core serves as a focal point for forwarding setcreation and maintenance. Since this process is performed only when there is an active source sending data to thegroup, we do not waste valuable network bandwidth to unnecessarily maintain group connectivity in such dynamicenvironments.
Table 1: A few variations of the multicast routing problem and how each node would compute its cost in MANSI Cost calculation per node
Current traffic load or the current queue size Power-aware routing Node's transmission power Energy conservation Inverse of the remaining energy of the node Security risk of the area the node is located in Figure 2: Behavior of forward and backward ants: (1) a FORWARD ANT deployed from the member A choosing Cas the next hop and encountering a forwarding node D, and (2) at D, the FORWARD ANT becoming a BACKWARDANT and following the reverse path back to A while depositing pheromone along the way Similar to other core-based protocols, this process creates a forwarding set consisting of all the intermediate nodes on the paths on which CORE ANNOUNCEs are accepted and forwarded from the core to the other members,which are often shortest paths, as illustrated in Figure 1(a). However, group connectivity can be made more efficientby having A choose another path that is partially shared by B to reduce the size of the forwarding set, as shown inFigure 1(b), which lowers the total cost of forwarding data packets. Note that the cost is considered on a per-nodebasis, not per-link, due to the fact that wireless communication is broadcast in nature (i.e., a single data packetbroadcast by a node is expected to arrive at all of its immediate neighbors in one transmission). In general, the costof the forwarding set does not always reflect the number of nodes in the set. Instead, the cost associated with eachnode can represent different measurements, depending on the desired properties of the forwarding set. For instance,if we aim to reduce the number of nodes in the forwarding set for efficient data forwarding, the cost associated witheach node could be one. Table 1 lists a few more examples of what node cost would represent when MANSI isapplied to other variations of the multicast routing problem in wireless ad hoc networks.
We adopt the swarm intelligence metaphor to allow nodes to learn a better multicast connection that yields a lower (total) forwarding cost. Each member who is not the core periodically deploys a small packet, called aFORWARD ANT, that opportunistically explores different, and hopefully better paths toward the core. This exploring Figure 3: An example illustrating how heights are assigned to forwarding nodes used by the members with IDs 3, 6and 8 process is illustrated in Figure 2. If a FORWARD ANT arrives at a node who is currently serving as a forwarding nodefor the group (node D in this case), it turns itself into a BACKWARD ANT and travels back to its originator via thereverse path. When the BACKWARD ANT arrives at each intermediate node, it estimates the cost of having the nodeit is currently at join the forwarding set via the forwarding node it previously found. The computed cost, as well asa pheromone amount that is inversely proportional to the cost, are updated on the node's local data structure. Thesepheromone amounts are then used by subsequent FORWARD ANTs that arrive at this node to make a decision whichnode they will travel to next, similar to how pheromone is used by biological ants. Let us consider the same exampleshown in Figure 2, when the BACKWARD ANT leaves D and arrives at C, the cost of having C join the forwardingset via D is zero since D is already a forwarding node and is directly connected to C. When the ant comes back to A, the cost of having A join the forwarding set via D is the same as the cost associated with C because C would be required to become a forwarding node to allow A to join the group via D. If A sees that the pheromone amounton the link to C becomes the highest among links to all neighboring nodes, it will switch to join the group via C bysending a JOIN REQUEST to C. Consequently, C will become a forwarding node, while E, F , and G will removethemselves from the forwarding set (since they no longer hear requests from A), which is similar to the connectivityshown in Figure 1(b).
To prevent the race condition where members attempt to establish group connectivity via one another's for- warding path and nobody remains connected to the core, each forwarding node is associated with a height which isidentical to the highest ID of the nodes that use it to connect to the core. In addition, the core has its height set toinfinity. Figure 3 shows an example illustrating how heights are assigned to forwarding nodes. A FORWARD ANTmust stop and turn into a BACKWARD ANT only when it encounters a forwarding node whose height is higher thanthe ID of the member who originated the ant. That means a member is allowed to connect to the core via an existingpath that belongs to another member with a higher ID, but not vice versa, to assure that the core, whose height isalways the highest, will eventually be connected to all the other members.
By following these simple rules, a majority of FORWARD ANTs from each member will choose a path that con- nects to an existing forwarding node with a smaller total path cost. Nodes on this path are then used to forwardmulticast data packets, resulting in a lower data forwarding cost. This exploring and learning mechanism enables MANSI to learn a better forwarding set for each group, depending on how node cost is defined, as well as differen-tiates MANSI from other existing ad hoc multicast routing protocols. Note that, by doing so, MANSI attempts toevolve multicast connectivity into states that yield lower cost. It, however, does not guarantee that minimum-costconnectivity can be achieved.
MANSI Protocol Description
This section explains the operations of MANSI in details.
Local Data Structures
Each node in the network is assigned a unique ID. A node with a unique ID i maintains a list of neighboring nodes, ntab(i), obtained via a neighbor discovery protocol such as periodic hello messaging. The node cost associated with i is denoted by cost(i), where cost(i) 0, which should be appropriately defined to reflect the performance metric subject to minimization. In addition, for each multicast group g, MANSI maintains the following data structures ateach node i.
Join table: maintains a list of nodes that have requested to join a multicast group via node i. The join table
of node i for multicast group g is denoted by join (i). This table is updated when i hears a JOIN REQUEST packet intended to itself. Each entry in join (i) is of the form r; h , where r is a requesting node's ID and h is its height (as described in Section 2) that it has sent along with its JOIN REQUEST. The join table is initially empty for each node. The node i becomes a forwarding node of the group g as long as join (i) = .
When a neighbor j is removed from ntab(i) due to a link failure, i will remove all the corresponding entries j;h from all the join tables.
Core ID: denoted by core (i) to indicate the current core of group g. core (i) is initially set to INVALID ADDRESS.
Core sequence number: keeps track of the latest CORE ANNOUNCE's sequence number, denoted by seqNo (i),
and initially set to zero.
Height: represents the height of i if it is currently a member or a forwarding node of the group g, defined as:
if i is a member of group g As described in Section 2, the height of i is the highest ID of the nodes, including i itself if it is a member,that are using i to connect to the core, and the core has an infinite height.
Pheromone table: maps neighboring nodes and heights to pheromone intensities. For node i, the pheromone
intensity associated to the height h of the link (i; j) for the multicast group g is denoted by  (i; j; h), where 0  (i;j;h) 1. This table is initially empty. Similar to maintaining the join table, if a neighbor j is removed from ntab(i), all entries  (i; j; h); g; h are removed as well. The maximum pheromone intensity of one is defined to prevent pheromone trails from being overly intensified, which, therefore, gives ants enoughprobabilities to explore different paths in a timely manner.
Best cost table: keeps track of how close node i thinks it is to forwarding nodes of certain heights in terms of
path costs. The cost of the best path to any forwarding node of height h for group g that i has seen so far isrepresented by bestCost (i; h). This best cost information is used to determine whether a BACKWARD ANT has returned from a good path or a bad path. Initially, this table is also empty.
Forwarding Set Initialization
Since MANSI is a reactive protocol, it does not send any control packet out (except hello packets for neighbordiscovery) when there is no active source of multicast traffic. When a member c of a group g has data to send and itsees that the core does not exist for the group yet (i.e., core (c) = INVALID ADDRESS), it sets core (c) to its own ID and floods the network with a CORE ANNOUNCE packet to announce that it is becoming the core. The COREANNOUNCE contains the node ID, c, the multicast group ID, g, a sequence number, and a cost which is initially setto zero, as shown in Figure 5. Upon receiving this CORE ANNOUNCE, each node i discards the packet if it has seenan announcement from the same node with the same sequence number before, or if core (i) > c. This is to assure that duplicate CORE ANNOUNCEs will not be processed, and only one CORE ANNOUNCE is allowed to be floodedif more than one node are attempting to become the core and flooding their CORE ANNOUNCEs simultaneously.
Algorithm 1 presents the pseudo code of how node i processes a CORE ANNOUNCE packet. If the conditions aresatisfied, i sets its core (i) to c, increases the packet's cost field by its own cost, then rebroadcasts the packet.
In addition, i updates the best cost table, as well as the pheromone amount corresponding to the height the core's height) and the neighbor from which the CORE ANNOUNCE was received, by invoking the procedureUpdatePheromoneAndCost shown in Algorithm 2. The operations of Algorithm 2 will be explained later in details.
For every node i, core (i) is reset back to INVALID ADDRESS if it has not heard any CORE ANNOUNCE within the ANNOUNCE INTERVAL time period. The core node c also keeps sending out an announcement packet forgroup g every ANNOUNCE INTERVAL time period as long as core (c) = c and it had at least one data packet for the group to send within the last ANNOUNCE INTERVAL time period.
As long as a member or a current forwarding node i of group g keeps hearing CORE ANNOUNCE from the core node, i.e., core (i) = INVALID ADDRESS, it periodically broadcasts a JOIN REQUEST packet to its neighbors. The JOIN REQUEST packet contains an entry g; k; height (i) , where k is defined as: bestCost (i;h) + 1: The above formula implies that node i who is willing to join a group should send a request to a neighbor whosegoodness was recently confirmed by BACKWARD ANTs (i.e., having high pheromone intensity) and also potentiallyyields the lowest joining cost. In addition, node i only takes into account the best cost information and pheromoneintensities of heights greater than its own height since it is not allowed to connect to an existing forwarding node ofa smaller height, as discussed in Section 2. At this moment, however, no actual ant packets are involved and eachnode has only one entry, whose height is (i.e., the core's height), in each of its best cost table and pheromone table. In other words, each node has just enough information to establish a connection directly to the core via thereverse path. As a result, the initial forwarding set generally consists of all the nodes that are on the (often times,shortest) paths on which the CORE ANNOUNCE are forwarded to the members. Figures 4(a), 4(b), and 4(c) illustratethe forwarding set initialization process.
If i is a member or a forwarding node belonging to more than one group, it can combine multiple join entries into a single JOIN REQUEST packet, as shown in Figure 6. When a node j receives a JOIN REQUEST from i and Figure 4: Sample network snapshots illustrating the operations of MANSI: (a) network setup with three members:nodes 1 (lower-left), 47 (upper-right), and 50 (upper-left), where node 1 is the core, (b) dissemination of COREANNOUNCE indicated by arrows, (c) initial multicast connectivity using reverse paths to the core, resulting in aforwarding set of ten nodes (shown in gray), and (d) forwarding set of four nodes learned by ants later in time Figure 5: CORE ANNOUNCE packet format ::: group nextHop height Figure 6: JOIN REQUEST packet format Algorithm 1 Node i processing a CORE ANNOUNCE packet
1: Input:
incoming CORE ANNOUNCE the node from which announce was received 4: Begin:
6: if coreId (i) = INVALID ADDRESS
Update local information: coreId (i) announce:coreId seqNo (i) announce:seqNo Invoke UpdatePheromoneAndCost (lastHop; ; announce:cost; T RUE) Update cost in the announcement packet: announce:cost announce:cost + cost(i) Rebroadcast announce 11: end if
Algorithm 2 Procedure UpdatePheromoneAndCost (next; height; cost; detF lag) executed by node i
neighbor ID indicating which pheromone table entry to be updated height associated with this update cost of joining the group g at a forwarding node of height height via next flag indicating whether this update is deterministic 6: Begin:
7: if  (i; next; height) is not defined then
 (i;next;height) 0 10: if detF lag = T RU E then
11:
bestCost (i;height) cost  (i;next;height)  (i;next;height) + 1 if bestCost (i; height) is not defined OR cost < bestCost (i; height) then
bestCost (i;height) cost  (i;next;height) 1 /* set intensity to max */  (i;next;height)  (i;next;height) + 1 20: end if
21:  (i; next; height) min  (i;next;height);1) /* pheromone intensity is at most one */ group height f exLimit d cost costLimit visitedNodes Figure 7: Ant packet format used by both FORWARD ANT and BACKWARD ANT sees that its ID is in the packet, it realizes that it should become a forwarding node for the group g. It then insertsthe sender's ID and height in its join table join (j) and broadcasts its own JOIN REQUEST containing the ID of the next hop obtained by the same formula above. Therefore, requests made by members will eventually be propagatedto the core, thus creating multicast connectivity among all the members. On the other hand, if node j hears a JOINREQUEST from i again without its ID, or i is removed from ntab(j) by neighbor discovery due to a link failure, itremoves i from its join table. Each node i remains to serve as a forwarding node for group g as long as join (i) is Forwarding Set Evolution
Once the initial forwarding set is formed, each group member who is not the core attempts to learn a better connectionto the core, in order to minimize the overall cost of the forwarding set, by deploying a FORWARD ANT everyANT INTERVAL time period. A FORWARD ANT packet deployed by member i for multicast group g, whose formatis shown in Figure 7, contains the following fields: group: multicast group ID height: height of the forwarding node found by this ant. This field is used only after this ant has been turned to a BACKWARD ANT.
f: forwarding flag indicating whether this ant is a FORWARD ANT or a BACKWARD ANT (since they share the same structure). Since i is deploying a FORWARD ANT, this flag is set to TRUE.
exLimit: the number of times the ant is allowed to probabilistically pick a next hop that is not the current best one in order to prevent it from aimlessly traversing the network. This field is initially set to EXPLORE LIMITand decrements every time the ant makes a decision on a next hop probabilistically, instead of deterministicallychoosing the next hop given by (2).
d: deterministic flag indicating whether the ant should always follow the current best path in order to obtain the actual current cost for the best cost table. The reason for using deterministic ants is that costs in the bestcost table may no longer reflect the actual costs due to node mobility, dynamics of nodes' costs, or dynamicsof the forwarding set itself. If this flag is set, the exLimit field is always ignored. Every other ant deployedby each member is deterministic.
cost: the total cost of the nodes this ant has visited, initially set to zero.
costLimit: the cost limit of the path that the ant is allowed to traverses after leaving its originator. This field is used in conjunction with the cost field to prevent the ant from traversing forward after the accumulatedcost exceeds the limit. Usually this limit is set to min bestCost (i;h), the lowest known cost to a current forwarding node of group g that i is allowed to connect to, plus some threshold. By this way, the ant can stopproceeding once it is certain that it will not find any better path than what its originator currently has. This cost limit is ignored if the ant is deterministic since its goal is not to find a better cost, but to find the actualcurrent best cost.
visitedNodes: the set of nodes visited by the ant, initially set to i .
Algorithm 3 Procedure ReleaseForwardAnt (fant) executed by node i
a FORWARD ANT to be released 3: Begin:
4: Compute a desirability, d , for node n; n ntab(i) from summations of only entries whose heights are higher than fant:height in the main pheromone table: if  (i; n; h) exists n;d = 0 then
return /* ant has no place to go */ 8: If f ant is not deterministic (f ant:d = F ALSE) and it is allowed to explore (f ant:exLimit > 0), with probability 0.5, fant decides to randomly choose a next hop n, where the probably of choosing n depends onits desirability as follows: fant:exLimit fant:exLimit 1 /* ant just performs one more exploration */ 9: Otherwise, the next hop is set to the one whose desirability is maximum: 10: append n to f ant:visitedN odes and broadcast f ant A node deploying a FORWARD ANT invokes the procedure ReleaseForwardAnt described in Algorithm 3 to find the next hop that the ant will travel to. A desirability, defined in (3), is computed for each the neighboring nodesby giving higher values to neighbors that have higher pheromone intensities and potentially yield lower costs toconnect to an existing forwarding node. On the other hand, zero desirability is given to all the nodes that have beenvisited before. If the ant is not deterministic and is still allowed to explore, these desirabilities are then normalizedto obtain a probability of choosing each of the neighboring nodes. Otherwise the neighbor node that gives themaximum desirability is chosen, which has the same effect as using (2) except that it excludes all the nodes in the visitedNodes field. Once a next hop is chosen, its ID is appended to the end of visitedNodes and the ant is When a node j receives a FORWARD ANT, it checks if its ID matches the ID at the end of the ant's visitedNodes field. If not, the ant is discarded. Otherwise, j knows that this ant is intended to itself and accepts it. Algorithm 4 Algorithm 4 Node i processing a FORWARD ANT packet
1: Input:
incoming FORWARD ANT 3: Begin:
4: if i = last entry in f ant:visitedN odes then
5:
if join (i) =  AND fant:visitedNodes[0] < height (i) then
Convert fant to a BACKWARD ANT fant:height height (i) Remove last entry from fant:visitedNodes and broadcast fant fant:cost fant:cost + cost(i) if fant:cost < fant:costLimit OR fant:d = T RUE then
Invoke ReleaseForwardAnt (fant) 15: end if
shows how a FORWARD ANT is processed. First, j checks if it is currently a forwarding node of the group and itsheight is higher than the ID of the ant's originator. If so, j realizes that the member who deployed the ant is eligibleto join the group via j itself. This ant is then turned into a BACKWARD ANT by resetting its f flag. Its cost is thenreset to zero in order to start computing the total cost on the way back, and its height field is set to j's height. Thelast entry of its visitedNodes is removed in order to send this ant back to the previous hop.
If the condition is not satisfied to convert the ant to a BACKWARD ANT, j increases the ant's cost field by its own cost cost(j). It then invokes the procedure ReleaseForwardAnt to forward the ant to a next hop, if the updatedcost does not exceed the limit or the ant is deterministic.
When a node k hears a BACKWARD ANT from j, it invokes the procedure UpdatePheromoneAndCost, described in Algorithm 2, which updates the entries in k's pheromone and best cost tables in accordance with j and the heightfield. If the ant is deterministic, the cost that it carries back is the actual cost of the path its originator is currentlyusing to join the group. Therefore, the best cost corresponding to the height field is updated to this value. If the antis not deterministic, however, the best cost is updated only when it is higher than the returned cost, which means thatthe ant has found a better path to join the group from this node. The pheromone intensity on this link is also updatedto the maximum in order to encourage subsequent FORWARD ANTs to use the same link, as well as to redirectjoin request to this link instead. If the ant comes back with a higher cost, a pheromone amount of 1=(1 + cost)is added instead. In case of deterministic ant, the added amount is reduced by half since this link already hasthe highest pheromone intensity as it has just been chosen by a deterministic FORWARD ANT. Note that we havementioned this procedure before when we explained how a node uses it while processing a CORE ANNOUNCE (line8 of Algorithm 1). This is because a CORE ANNOUNCE more or less serves as a deterministic BACKWARD ANTreturning from the core.
Algorithm 5 Node i processing a BACKWARD ANT packet
1: Input:
incoming BACKWARD ANT the node from which bant was received 4: Begin:
6: Invoke UpdatePheromoneAndCost (lastHop; bant:height; bant:cost; bant:d) 7: if i = last entry in f ant:visitedN odes then
8:
Remove the last entry from bant:visitedNodes if bant:visitedNodes =  then
bant:cost bant:cost + cost(i) 13: end if
After updating the pheromone and the best cost tables, k checks if the BACKWARD ANT was intended to itself by examining the last entry in the visitedNodes field. If its ID matches, it adds its cost into the cost field, removesthe last entry from visitedNodes, and rebroadcasts as long as there is at least one entry left in visitedNodes.
Algorithm 5 presents the pseudo code of how a node processes a BACKWARD ANT.
Similar to pheromone evaporation of biological ants, each node i updates all the entries  (i; j; h) in its pheromone table by reducing their values by DECAYING FACTOR at every DECAY INTERVAL time period:  (i;j;h) = (1 DECAYING FACTOR)  (i;j;h); where 0 < DECAYING FACTOR < 1.
By probabilistically selecting next hops, the majority of the FORWARD ANTs will choose paths with high pheromone intensity, while some of them may explore totally different new paths. If a BACKWARD ANT comesback with a better cost on a new branch, the pheromone amount on that branch will be increased significantly. Asa result, a change in multicast connectivity (i.e., forwarding set) is triggered due to the periodic broadcast of JOINREQUEST packets, as illustrated in Figure 4(d).
MANSI also takes advantage of broadcast nature of wireless communication to speed up the learning process as follows. When a node i overhears a JOIN REQUEST for group g from j but not intended to itself, it invokesUpdatePheromoneAndCost (j; h ; 0; T RUE), where h is the height that j reports in its JOIN REQUEST. This implies that i could join the group via j with no cost, given that its height is less than h . However, a drawback of this idea is that some members who are not forwarding nodes will broadcast JOIN REQUESTs as well and might bemistaken as forwarding nodes by its neighbors.
Multicast Data Forwarding
Since MANSI is a mesh-based protocol which allows forwarding nodes and members to accept data packets arrivingfrom any node, each data packet is assigned a unique sequence number when it is transmitted from the source.
The sequence numbers are checked by each forwarding node and member node to make sure that no duplicate datapackets are rebroadcast or delivered to the application. When a node i receives a non-duplicate data packet of group g, it checks whether it is currently a forwarding node of the group, i.e., join (i) = . If so, it rebroadcasts the packet. Otherwise, the packet is silently discarded.
In MANSI, mobility and other network dynamics are handled inherently rather than as exceptions. With thepheromone laying/following behavior of BACKWARD ANTs and FORWARD ANTs, each path comprising the for-warding set keeps being reinforced as long as no link on the path is broken. However, network dynamics can causeoptimal connectivity to change from time to time even though the current connectivity may still be valid. With theprobabilistic nature of FORWARD ANTs to explore new paths, the multicast forwarding set should be able to evolveinto a configuration that is more efficient for the new topology.
When a link currently used by a member or a forwarding node to send JOIN REQUESTs breaks, the pheromone table entries corresponding to that link are also removed. Therefore, all subsequent FORWARD ANTs will be redirectto other paths, while the majority of them will take the next hop whose pheromone intensity was the second highestbefore the link failure. If this next hop leads to a forwarding node of a higher height, BACKWARD ANTs willreturn and update pheromone on the new path, hence reestablishing a connection to the group. However, in casethat FORWARD ANTs fail to find a new path, CORE ANNOUNCEs flooded periodically will eventually restore theconnectivity.
Although MANSI is considered a mesh-based protocol by its way of forwarding data packets, connectivity of the forwarding set may still be fragile if the network is sparse and members are far apart from each other, especially withthe presence of mobility. To make data forwarding more effective under mobility, while maintaining good efficiencywhen the network is static, we incorporate a mobility-adaptive mechanism into MANSI. With this mechanism, eachnode i keeps track of the normalized link failure frequency, denoted by nlff(i), which reflects the dynamic conditionof the area surrounding i in terms of the number of link failures per neighbor per second. A calculation of nlff(i) isperformed every NLFF TIME WINDOW time period as follows: current nlff (i) = NLFF TIME WINDOW nlff(i) = [current nlff (i) + nlff (i)]=2; where f is the number of link failures detected during the last NLFF TIME WINDOW time period. Initially nlff(i)is set to zero.
Each member or forwarding node then uses this nlff to determine the stability of its surrounding area. If its nlff is lower than a threshold NLFF THRESHOLD, the node will consider its area stable and join the group by sendingJOIN REQUESTs toward its best next hop as usual. If nlff exceeds the threshold, however, it will add another entryfor the second best next hop into its JOIN REQUESTs. Since all the neighbors are ranked by their goodness in termsof pheromone intensities, the second best next hop can be easily determined. Formally, if k is the best next hop for ito join the group g, as defined in (2), then the second best next hop k0 is defined as: bestCost (i;h) + 1: Figure 8: A network of 50 nodes moving at 10 m/s, where members are in black and forwarding nodes are in gray:(a) without mobility-adaptive mechanism, and (b) with mobility-adaptive mechanism where NLFF THRESHOLD is0.01 Figure 8(a) illustrates the forwarding set created by MANSI without the mobility-adaptive mechanism for a multicast group of three members in a network of 50 nodes, where each node is moving at 10 m/s. The groupconnectivity is almost a straight line and is vulnerable to link failures. With the mobility-adaptive mechanismenabled, most members and forwarding nodes request two of their neighbors to be in the forwarding set, as shownin Figure 8(b), so that the group connectivity becomes more robust.
Experimental Results and Discussion
To study the characteristics and evaluate the performance of MANSI, we have conducted simulation experimentsusing the QualNet simulator [10]. Ten random networks were generated with 50 nodes uniformly distributed over aterrain of size 1000 1000 m2. Each node was equipped with a radio transceiver which was capable of transmitting signals up to approximately 250 meters over a 2 Mbps wireless channel, using the two-ray path loss model withoutfading. We used IEEE 802.11DCF as the MAC layer protocol, and IP as the network layer. Since MANSI does notrely on any unicast routing protocol, no other routing protocols were employed. For each network, a multicast groupsof 5 members was setup, where each member generated a constant bit rate (CBR) traffic at 2 packets/sec to the groupfor 20 minutes. The size of data payload was 512 bytes. The MANSI parameter values used in our simulation areshown in Table 2. Note that NLFF THRESHOLD is used only when the mobility-adaptive mechanism is enabled.
Our first set of experiments were setup without mobility in order to study how MANSI maintains forwarding sets in static environments. For comparison purposes, we used two baseline protocols: FLOOD and CORE, as Table 2: Parameter values for MANSI HELLO INTERVAL ANNOUNCE INTERVAL ANT INTERVAL EXPLORE LIMIT DECAY INTERVAL DECAYING FACTOR NLFF THRESHOLD Table 3: Average size of the forwarding set formed in MANSI, CORE, and FLOOD for each network references. FLOOD is a simple flooding protocol where a data packet is rebroadcast by every node in the network.
And CORE is a generic core-based protocol that operates exactly like MANSI, but with no ants deployed, whereCORE ANNOUNCEs are periodically flooded as usual. The cost of each node was set to one, which implies thatMANSI would attempt to reduce the size of the forwarding set.
We first look at the average size of forwarding sets maintained by CORE and MANSI over time for the ten sample networks, as shown in Figure 9. Due to random delays added to avoid packet collisions when broadcasting,the dissemination pattern of a CORE ANNOUNCE is unpredictable when it is flooded, which causes a forwarding setto be formed differently for each announcement. Consequently, the average size of forwarding sets keeps changingfrom time to time in CORE. In contrast, forwarding sets maintained by MANSI start of at around the same size asthat of CORE but keep reducing in size during the first 200 seconds. Their size then becomes stable and stays lowmost of the time as each member or forwarding node tends to join the group via a low-cost path (i.e., small hop countin this case), whose existence was recently confirmed by BACKWARD ANTs. Although another CORE ANNOUNCEmay arrive at a member from a different node, the member will not send a JOIN REQUEST to this new node as long #nodes in the forwarding set Simulation time (s) Figure 9: Average size of the forwarding set as a function of time for CORE and MANSI as the current joining cost is low and the pheromone intensity on the link it currently uses to join the group is high.
Table 3 summarizes the sizes, averaged over the entire simulation time, of the forwarding sets maintained by MANSI, CORE, and FLOOD on each simulated network. (FLOOD does not really maintain a forwarding set,but the set consists of every node in the network.) The results show that in all cases, except one, MANSI yieldsforwarding sets that are approximately 15%-20% smaller than those of CORE, and much smaller than FLOOD.
Since the size of the forwarding set indicates how many nodes are involved to relay a data packet from one memberto the others, this demonstrates the efficiency of MANSI in terms of data forwarding.
We have performed another set of experiments to compare the performance of MANSI, in terms of effectiveness and efficiency, with ODMRP. ODMRP [1] is an on-demand, mesh-based multicast protocol that attempts to establisha forwarding group—similar to a forward set in MANSI—only when a source of the group has data to send. Thenodes in the forwarding group form a mesh that connects the group members together. When a multicast source hasdata to send for the first time, it broadcasts to its neighbors a JOIN QUERY packet, which is a data packet with thequery flag set. Upon receiving a non-duplicate JOIN QUERY, each node stores the upstream node ID in its routingtable and rebroadcasts the packet. When a member of the multicast group receives a JOIN QUERY, it constructsand broadcasts a JOIN REPLY packet containing the source ID and the upstream node ID to all of its neighbors.
Upon receiving a JOIN REPLY, a node whose ID matches the upstream ID in the packet realizes that it is on thepath between the source and a member, so it becomes a forwarding node for the group by setting its FG FLAG(Forwarding Group Flag). It then constructs and broadcasts its own JOIN REPLY using its corresponding upstreamnode ID. The broadcasting of JOIN REPLY packets therefore propagates the information from all the members back to the source on the reverse paths. Once the source has sent out a JOIN QUERY, it sends all subsequent data packetsnormally with no query flag set. This will allow only nodes that are currently in the forwarding group to rebroadcastthese data packets, thus reducing data forwarding overhead. To deal with dynamics of the network topology andgroup membership, each source floods the network with JOIN QUERYs every REFRESH INTERVAL as long as itstill has data to be sent to the group. The FG FLAG on each node will be reset if it has not been refreshed by JOINREPLY for some period of time, which implies that the source has no data to send, or it is no longer needed as aforwarding node. If nodes are equipped with GPS, a mobility prediction method can also be used to adaptively adjustthe value of REFRESH INTERVAL to suit the current mobility condition.
In this comparison, we used QualNet's implementation of ODMRP, which followed the specification in the Internet Draft draft-ietf-manet-odmrp-02.txt [7] but without mobility prediction which requires GPS.
The value of REFRESH INTERVAL was fixed at 3 seconds. Each node moved constantly with the predefined speed,which was varied from 0 m/s to 20 m/s. The following statistics were collected and used in the comparison, whereeach measurement will be shown with a 95% confidence interval: Packet delivery ratio: The ratio of the number of non-duplicate data packets successfully delivered to the
receivers versus the number of packets supposed to be received. This metric reflects the effectiveness of aprotocol.
Number of total packets transmitted per data packet received: The ratio of the number of data and control
packets transmitted versus the number of data packets successfully delivered to the application. HELLOpackets are also considered as packets transmitted. This measure shows efficiency of a protocol in terms ofchannel access. The lower the number, the more efficient the protocol.
Number of total bytes transmitted per data byte received: This metric is similar to the second metric
except that number of bytes is considered instead. Here, bytes transmitted include everything that is sent tothe MAC layer (i.e., IP and UDP headers, as well as HELLO packets), where data bytes received involve onlythe data payloads. This metric presents efficiency of a protocol in terms of bandwidth utilization. Similar tothe second metric, the lower the number, the more efficient the protocol.
Figure 10 presents packet delivery ratio of the protocols at different mobility speeds. MANSI without the mobility-adaptive mechanism, denoted by MANSI-Basic, shows significant performance degradation as mobilityincreases due to the fact that the forwarding set lacks redundant paths when each member and forwarding nodealways requests only one of its neighbor to be part of the forwarding set. However, when the mobility-adaptivemechanism is enabled, as denoted by MANSI-Mobile, its results are comparable with ODMRP and FLOOD. Al-though the delivery ratio is a bit lower than that of the other two protocols, more than 90% of data packets can bedelivered at every mobility speed.
In terms of efficiency, both MANSI-Basic and MANSI-Mobile give significantly better performance than ODMRP and FLOOD at low mobility in both channel access and bandwidth utilization aspects, as shown in Figure 11 and Fig-ure 12, respectively. The reason is that every multicast sender floods JOIN QUERY packets periodically in ODMRP,while in MANSI, only the core of the group performs periodic flooding. Moreover, ODMRP requires each memberto send a Join Reply toward each sender via the reverse path on which the JOIN QUERY was received, resultingin a fairly large forwarding group, especially with high number of senders. MANSI, in contrast, has each memberestablish connectivity toward the core, which keeps the number of forwarding nodes low.
Without adapting their behaviors to mobility, data forwarding characteristics of MANSI-Basic, ODMRP, and FLOOD remain almost the same regardless of mobility speeds, where FLOOD employs the highest number of Packet delivery ratio (%) Mobility speed (m/s) Figure 10: Packet delivery ratio as a function of mobility speed forwarding nodes, and MANSI-Basic uses the least number, but suffers low packet delivery ratio under high mobility.
With its mobility-adaptive mechanism, MANSI-Mobile is shown to perform as efficiently as MANSI-Basic at lowmobility2 and as ODMRP at high mobility, while yielding consistently high packet delivery ratio for the entire rangeof speeds.
Related Work
There have been numerous multicast routing protocols proposed for ad hoc networks. Protocols such as AM-Route [8], AMRIS [12], and MAODV [9] are based on constructing a tree spanning all the group members, wherea node can only accept packets coming from a node with which a tree branch has been established. Since a treestructure provides only one forwarding path between a pair of sender and receiver, group connectivity may suf-fer from frequent topology changes in dynamic networking environments. Other protocols such as CAMP [5] andODMRP [1], including MANSI, employ a mesh-based approach to increase redundancy by allowing packets to beforwarded over more than one path, thus giving a higher chance of successful delivery.
Based on the way they establish and maintain connectivity within each multicast group, multicast protocols can also be broadly classified as either a source-based approach or a group-shared tree/mesh approach. In a source-basedapproach, a multicast tree or mesh is constructed for each sender. The construction process is usually initiated bya sender that floods a request message to all other nodes in the network so that the other members of the group 2In fact, they behave exactly the same Total pkts transmitted per data pkt received Mobility speed (m/s) Figure 11: Total packets transmitted per data packet received at the destinations as a function of mobility speed can establish connectivity via the reverse paths. In ODMRP, each sender also exploits periodic flooding of controlpackets to refresh group connectivity and handle mobility. This is suitable with dense multicast groups but yieldshigh overhead as the network size and the number of senders increase. In contrast, a group-shared tree/mesh ap-proach aims to construct a tree/mesh for each multicast group, which is shared by all senders within the group. Acommon technique for creating group connectivity is to designate a node in the network the role of the rendezvouspoint, or the core, for each group. Each member then establishes connectivity, often via the shortest path, to thecore, which in turn connects all the group members together. For each group, one of the members, the first sender, orany node in the network can take the role of the core. Examples of ad hoc multicast protocols that are based on thistechnique are MAODV, AMRIS, and CAMP. In contrast, in MANSI, group connectivity can be made more efficientby having some members share common paths to the core with other members in order to further reduce the totalcost of forwarding data packets. Moreover, the forwarding cost may adopt different performance metrics for differ-ent objectives, in general, in addition to the number of nodes used to forward data. MANSI extends a core-basedtechnique by adopting the metaphor of swarm intelligence to learn a better multicast connection that yields a lowertotal forwarding cost.
Swarm intelligence appears in biological swarms of certain insect species. It gives rise to complex and of- ten intelligent behavior through simple, unsupervised interactions between a sheer number of autonomous swarmmembers. The end result is the emergence of very complex forms of social behavior which fulfill a number ofoptimization objectives and other tasks. Its metaphor has been applied to many combinatorial optimization prob-lems like the traveling salesman problem (TSP) and the quadratic assignment problem (QAP). In communicationsnetworks, a number of routing and load balancing mechanisms based on swarm intelligence have been proposed.
Total bytes transmitted per data byte received Mobility speed (m/s) Figure 12: Total bytes transmitted per data byte received at the destinations as a function of mobility speed Ant-based Control (ABC) [11] has applied swarm intelligence to achieve load balancing in telecommunicationsnetworks. Simulated on a model of the British Telecom (BT) telephone network, ABC has been shown to resultin fewer call failures than other methods such as shortest-path routing. In [3, 4], a distributed adaptive routing fordatagram networks, called AntNet, has been described. Several variations of AntNet have been developed but all ofthem rely on the same concept where forward ants are launched toward destinations and backward ants travel backand update pheromone along the backward paths. The amount of added pheromone is proportional to the goodnessof the path measured by the forward ant. The same concept has been extended and applied to Adaptive Swarm-based Distributed Routing (Adaptive-SDR) [6] for routing in wireless and satellite networks, which incorporates amechanism to cluster nodes into colonies so as to resolve the scalability issue in large networks.
We exploit the concept of forward and backward ant deployment in the MANSI protocol to provide multicast support for ad hoc networks. Within a multicast group, each member launches a forward ant in order to find anexisting forwarding node where it can use to establish connectivity to the group with lower cost. Once such a nodeis found, the forward ant turns into a backward ant and returns to its origin via the reverse path, while depositingpheromone along the way to attract more future forward ants. To our best knowledge, no ad hoc multicast routingprotocol has been proposed to exploit the concept of swarm intelligence.
Conclusion and Future Work
Inspired by swarm intelligence, we have introduced an alternative approach to solving the multicast routing problemin mobile ad hoc networks. Our protocol, called MANSI (Multicast for Ad hoc Networks with Swarm Intelligence),is an on-demand multicast routing protocol that creates a multicast mesh shared by all the members within eachgroup. The protocol uses a core-based scheme, where each member initiates a request to the core node to establishmulticast connectivity with other members. Intermediate nodes who receive such a request become forwarding nodesthat are used to relay data packets from one member to the others. Unlike other core-based protocols, MANSI doesnot always rely on the shortest paths between the core and the members to establish group connectivity. Instead,each member who is not the core periodically deploys a small packet that behaves like an ant to opportunisticallyexplore different paths. This exploring mechanism enables the protocol to discover paths that comprise a better setof forwarding nodes yielding a lower total cost of data forwarding, where the "cost" of forwarding (nodes) can bedefined in terms of different application specific performance metrics. MANSI also incorporates a mobility-adaptivemechanism that allows the protocol to remain effective as mobility increases. The simulation results have shownthat MANSI performs both effectively and efficiently in static or low-mobility environments, yet still effectively inhighly dynamic environments.
Research is in progress to apply MANSI with other objectives such as load balancing, energy conservation, and [1] S. Bae, S. Lee, W. Su, and M. Gerla. The Design, Implementation, and Performance Evaluation of the On- Demand Multicast Routing Protocol in Multihop Wireless Networks. IEEE Network, Special Issue on Multi-casting Empowering the Next Generation Internet, 14(1):70–77, January/February 2000.
[2] Tony Ballardie, Paul Francis, and Jon Crowcroft. Core-based trees (CBT): An Architecture for Scalable Inter- Domain Multicast Routing. In Communications, architectures, protocols, and applications, San Francisco,CA, USA, 13-17 September 1993.
[3] Gianni Di Caro and Marco Dorigo. AntNet: A Mobile Agents Approach to Adaptive Routing. Technical Report IRIDIA/97-12, Universite Libre de Bruxelles, Belgium, 1997.
[4] Gianni Di Caro and Marco Dorigo. Two Ant Colony algorithms for Best-Effort Routing Datagram Networks.
In the Tenth IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS'98),Las Vegas, Nevada, October 28–31 1998.
[5] J. Garcia-Luna-Aceves and E. Madruga. The Core-Assisted Mesh Protocol. IEEE Journal on Selected Areas in Communications, 17(8), August 1999.
[6] Ioannis N. Kassabalidis, Mohamed A. El-Sharkawi, Robert J. Marks II, Payman Arabshahi, and Andrew A.
Gray. Adaptive-SDR: Adaptive Swarm-based Distributed Routing. In IEEE WCCI 2002, IJCNN 2002 SpecialSession: Intelligent Signal Processing for Wireless Communications, Honolulu, Hawaii, May 12-17 2002.
[7] Sung-Ju Lee, William Su, and Mario Gerla. On-Demand Multicast Routing Protocol (ODMRP) for Ad Hoc Networks, 2000. IETF Internet Draft. http://www.ietf.org/proceedings/00jul/I-D/manet-odmrp-02.txt.
[8] Mingyan Liu, Rajesh R. Talpade, and Anthony McAuley. AMRoute: Adhoc Multicast Routing Protocol.
Technical Report 99, The Institute for Systems Research, University of Maryland, 1999.
[9] R. Royer and C. Perkins. Multicast using ad-hoc on demand distance vector routing. In Mobicom'99, pages 207–218, Seattle, WA, August 1999.
[10] Scalable Network Technologies, Inc. QualNet Simulator. http://www.scalable-networks.com.
[11] Ruud Schoonderwoerd, Owen Holland, Janet Bruten, and Leon Rothkrantz. Ant-Based Load Balancing in Telecommunications Networks. Technical Report HPL-96-76, Hewlett-Packart Laboraties Bristol, Bristol,UK, May 21 1996.
[12] C.W. Wu and Y.C. Tay. AMRIS: A Multicast Protocol for Ad hoc Wireless Networks. In IEEE Military Communications Conference (MILCOM), pages 25–29, Atlantic City, NJ, November 1999.

Source: https://www.cpe.ku.ac.th/~cpj/publications/shen05adhoc.pdf