Printer Friendly

Survey of topology-based multicast routing protocols for mobile ad hoc networks.

1. Introduction

A mobile ad hoc network (MANET) comprises of wireless nodes that move independent of each other forming a dynamically changing distributed resource-constrained system. The wireless nodes are often limited in their transmission range and multi-hop routing is a common phenomenon that has been of significant interest. There are several application domains in which MANETs have been deployed. These include: disaster recovery, military operations in a battlefield, outdoor entertainment activities, crowd control, conferences, and etc. One-to-many multicast communication is a characteristic feature of all these applications. Several multicast routing protocols have been proposed in the literature to support these MANET applications.

Depending on the underlying topology used for communication, the multicast protocols are mainly classified as: tree-based and mesh-based protocols. In tree-based protocols, only one route exists between a source and a destination and hence these protocols are efficient in terms of the number of link transmissions. There are two major categories of tree-based protocols: source tree-based (the tree is rooted at the source) and shared tree-based (the tree is rooted at a core node and all communication from the source nodes to the receiver nodes is routed through this core node). Even though shared tree-based multicast protocols are more scalable with respect to the number of sources, these protocols suffer under a single point of failure, the core node. On the other hand, source tree-based protocols are more efficient in terms of traffic distribution. The source tree-based protocols are further classified into the following sub-categories: (i) Minimum hop-based, (ii) Minimum link-based, (iii) Stability-based, and (iv) Zone-based protocols. The shared tree-based multicast protocols are further classified into: (i) Cluster-based, (ii) Session-specific, and (iii) IP multicast session-based protocols.

In mesh-based multicast routing, multiple routes exist between the source node and each of the receivers of the multicast group. A receiver node receives several copies of the data packets, one copy through each of the multiple paths. Mesh-based multicast routing protocols provide robustness in the presence of node mobility; however, at the expense of a larger number of link transmissions leading to inefficient bandwidth usage. The mesh-based protocols are classified into source-initiated and receiver-initiated protocols depending on the entity (the source node or the receiver nodes) that initiates mesh formation.

In this paper, we review widely studied, characteristic, representative multicast routing protocols for each of the above sub-categories and explain the salient features of the particular sub-categories through these protocols. We discuss the pros and cons of each of these multicast routing protocols and the categories to which they belong. A classification tree of the different categories and their representative multicast routing protocols that would be discussed in the paper is given in Figure 1.

The rest of the paper is organized as follows: Section 2 presents the background information on MANETs, routing and multicast protocols. In the subsequent sections, we discuss representative routing protocols for each of the four categories of source tree-based MANET multicast protocols (Section 3), for each of the 3 categories of shared tree-based multicast protocols (Section 4); followed by representative protocols for the source initiated (Section 5) and receiver-initiated categories (Section 6) of the mesh-based multicast protocols. Section 7 concludes the paper and presents future research directions. Throughout the paper, the terms 'node' and 'vertex', 'path' and 'route', 'edge' and 'link', 'message' and 'packet' are used interchangeably. They mean the same.

[FIGURE 1 OMITTED]

2. Background

Wireless networks provide location-independent access to information for users on the move and hence are known for ubiquitous communication capability. A mobile ad hoc network (MANET) is a self-organizing wireless network that can dynamically reconfigure itself without any centralized administration and lacks a fixed infrastructure. Nodes that are part of a MANET often function in a "peer-to-peer" mode--being the source, destination and intermediate forwarding node for different communication sessions.

Multicasting has become a de facto one-to-many communication standard for applications running in wired and wireless networks. A sample list of multicast applications includes: distance learning, collaborative and groupware applications, audio/video conferencing, stock quotes, news distribution and etc. Multicasting differs from multiple unicasting. With multicasting, a single stream of data is distributed to multiple recipients and data is duplicated only when required; but, with uncasting, data is transferred independently from the source to each of the receivers and this could lead to network clogging.

MANETs are resource-constrained networks: limited bandwidth, battery operated nodes, limited CPU and memory capacities, and a shared medium leading to interference. MANET topology dynamically changes due to random node mobility. Due to such unique characteristics and constraints, multicast routing protocols developed for traditional wired networks and wireless cellular networks cannot be directly applied for MANETs. The routing algorithms need to be more robust to dynamically changing topology of MANETs.

Ad hoc routing protocols can be either proactive or reactive, depending on when the routes are determined. Proactive routing protocols pre-determine routes to destinations by continuous exchange of routing information among nodes. Routes are immediately available when packets are to be transmitted. Examples of proactive ad hoc routing protocols are the Destination Sequenced Distance Vector (DSDV) routing protocol [23] and the Wireless Routing Protocol (WRP) [20]. Reactive routing protocols determine routes only upon demand. A node queries the network for a route when it has a packet to transmit. Examples of reactive ad hoc routing protocols are TORA [22], DSR [13] and AODV [24]. But, neither pure proactive nor pure reactive routing protocols are suitable for MANETs. In MANETs, the changes in network topology can be more frequent than routing requests. In such situations, the routing information generated by proactive routing protocols becomes stale. Reactive routing protocols perform a global-search on-demand route discovery process that requires significant control traffic. As a result, the bandwidth-constrained MANETs can easily become saturated in a short interval of time. Hence, several ad hoc multicast routing protocols, that are not just extensions of the above unicast routing protocols, are proposed in the literature. This is contrary to what is seen in wired networks where many multicast routing protocols are just multicast extensions of their corresponding unicast routing protocols (e.g., DVMRP [30], MOSPF [19]). A robust and efficient ad hoc multicast routing protocol must be independent and should not rely on any underlying unicast routing protocol for route determination and updates.

3. Source-Tree based Multicast Protocols

In this section, we describe a representative protocol from each of the following major categories of source-tree based multicast routing protocols: (i) Minimum hop-based, (ii) Minimum link-based, (iii) Stability-based, and (iv) Zone-based protocols.

3.1 Minimum-hop based Multicast Protocols

The minimum hop-based multicast routing protocols aim for a minimum hop path between the source node and every receiver node that is part of the multicast group. Each receiver node is connected to the source node on the shortest (i.e., the minimum hop) path and the path is independent of the other paths connecting the source node to the rest of the multicast group. The Multicast extension to the Ad hoc On-demand Distance Vector (MAODV) protocol [25] is a classical example of minimum hop-based multicast routing protocols for MANETs. In this sub-section, we describe the working of MAODV in detail.

Tree Formation (Expansion) Phase: In MAODV, a receiver node joins the multicast tree through a member node that lies on the minimum hop path to the source. A potential receiver wishing to join the multicast group broadcasts a Route-Request (RREQ) message. If a node receives the RREQ message and is not part of the multicast tree, the node broadcasts the message in its neighborhood and also establishes the reverse path by storing the state information consisting of the group address, requesting node id and the sender node id in a temporary cache. If a node receiving the RREQ message is a member of the multicast tree and has not seen the RREQ message earlier, the node waits to receive several RREQ messages and sends back a Route-Reply (RREP) message on the shortest path to the receiver. The member node also informs in the RREP message, the number of hops from itself to the source. The prospective receiver receives several RREP messages and selects the member node which lies on the shortest path to the source. The receiver node sends a Multicast Activation (MACT) message to the selected member node along the chosen route. The route from the source to receiver is set up when the member node and all the intermediate nodes in the chosen path update their multicast table with state information from the temporary cache.

Working Example: In Figure 2, we illustrate tree formation (expansion) under the MAODV protocol using an example. Here, the multicast tree is already established between the source node S and the two receivers R1 and R2 of the multicast group. A node is considered a multicast tree node if it is a source, receiver or an intermediate node of the multicast tree. Now, consider a new member node R3 joining as the receiver of the multicast group. To become part of the multicast tree, R3 broadcasts a Route Request (RREQ) control packet to its neighbors. If a neighbor node is a multicast tree node, it does not further propagate the RREQ packet; otherwise, it broadcasts the packet to its neighbors. The multicast tree node that receives a RREQ packet waits for a certain time period to receive any more RREQ packets and then responds back with a Route Reply (RREP) packet on the shortest (minimum hop) path to the initiator (R3). In the RREP packet, the tree node also includes the number of hops between itself and the source. In our example, intermediate tree node I1 (on the shortest path from S to R2) and the receivers R1 and R2 respond back with RREP packets to R3. The number of hops on the shortest path from R3 to each of R1 and R2 is 4; whereas the number of hops from I1 to R3 is 3. Also, the number of hops from S to R1 and R2 on the shortest path is respectively 2 and 3; whereas, the number of hops from S to I1 is 1. Considering all these, the shortest path from R3 to the source S would be the path that goes through the intermediate tree node I1. Hence, R3 decides to join the multicast tree through I1 and sends a Multicast Activation (MACT) message to I1. The intermediate nodes I5 and I8 that forwarded all of the three control packets (RREQ, RREP and MACT) now become part of the multicast tree.

[FIGURE 2 OMITTED]

Tree Maintenance Phase: Tree maintenance in MAODV is based on the expanding ring search (ERS) approach, using the RREQ, RREP and MACT messages. The downstream node of a broken link is responsible for initiating ERS to issue a fresh RREQ for the group. This RREQ contains the hop count of the requesting node from the multicast source node and the last known sequence number for that group. It can be replied only by the member nodes whose recorded sequence number is greater than that indicated in the RREQ and whose hop distance to the source is smaller than the value indicated in the RREQ.

3.2 Minimum-link based Multicast Protocols

The minimum link-based multicast protocols aim for an overall minimum number of links in the multicast tree connecting a source node to all the receiver nodes of the multicast group. Such a tree would use the bandwidth efficiently and facilitate simultaneous use of the wireless channel for several node pairs whose communication will not interfere with each other. The Bandwidth Efficient Multicast Routing Protocol (BEMRP) is a classical example of the minimum link-based source-tree multicast routing protocols as the protocol attempts to minimize the number of additional links that get incorporated when a new receiver node joins an already existing multicast tree. In this subsection, we describe the working of BEMRP in detail. Tree Formation (Expansion) Phase: According to BEMRP, a newly joining node to the multicast group opts for the nearest forwarding node in the existing tree, rather than choosing a minimum hop count path from the source of the multicast group. As a result, the number of newly added links in the multicast tree is minimum leading to savings in the network bandwidth. Multicast tree construction is receiver-initiated. When a node wishes to join the multicast group as a receiver, it initiates the flooding of Join control packets targeted towards the nodes that are currently members of the multicast tree. On receiving the first Join control packet, the member node waits for a certain time before sending a Reply packet. The member node sends a Reply packet on the path, traversed by the Join control packet, with the minimum number of intermediate forwarding nodes. The newly joining receiver node collects the Reply packets from different member nodes and would send a Reserve packet on that path that has the minimum number of forwarding nodes from the member node to itself.

Working Example: The working of BEMRP is illustrated using an example shown in Figure 3. Assume there exists a minimum link multicast tree connecting the source node S and the two receivers R1 and R2 of the multicast group (the darkened links shown in Figure 3 form the multicast tree). Similar to our terminology used for the MAODV example, we refer to a tree node to be either a multicast group member (source and receiver nodes) or an intermediate node in the tree. Now, when a third receiver node, R3, wants to join the multicast group, it broadcast the Join control packets in its neighborhood and the packets get forwarded further until they are received by a tree node. After receiving the first Join control packet, the tree node waits for a while and sends back a Reply packet on the path that has the minimum hop count to the initiator of the Join control packet (R3). However, unlike MAODV, the number of hops from the responding tree node to the source of the multicast group is not included in the Reply packet and only the hop count of the path from the tree node to the receiver is included. The receiver R3 collects all the Reply packets and decides to join the multicast tree through the closest tree node so that the number of new links (3, in this case) that will be added to the multicast tree will be the minimum. R3 then sends a Reserve packet to the chosen intermediate tree node and the end nodes of the links traversed by this Reserve packet are now part of the minimum link-based multicast tree.

[FIGURE 3 OMITTED]

Note that if R3 had chosen to send the Reserve packet directly to the source S by responding to its Reply packet, R3 would have been connected to the source on a minimum hop path. However, including such a path to the already existing multicast tree would create an addition of 4 new links to the tree and hence R3 prefers to go through I1 (that resulted in only 3 new links getting added to the tree). The tradeoff is that the number of hops from the source S to the receiver R3 is now 5 and this is larger than the minimum number of hops between S and R3 in the network.

Tree Maintenance Phase: To provide more bandwidth efficiency, the tree maintenance approach in BEMRP is hard-state based, i.e. a member node transmits control packets only after a link breaks. BEMRP uses two schemes to recover from link failures: Broadcast-multicast scheme the upstream node of the broken link is responsible for finding a new route to the previous downstream node; Local-rejoin scheme--the downstream node of the broken link tries to rejoin the multicast group using a limited flooding of the Join control packets.

3.3 Stability-based Multicast Protocols

The stability-based multicast protocols aim for a long-living tree connecting the source node to the receiver nodes of the multicast group. In pursuit of this, at the time of joining the tree, each receiver node selects the most stable path to the source node. This would minimize the number of tree reconfigurations. In order to determine stable paths and trees, routing protocols use metrics that are a measure of the longevity of the links in the network. Metrics such as predicted link expiration time (LET) [27], link affinity [1], associativity ticks [29] have been used by the routing protocols for determining stable paths as well as stable trees. In this sub-section, we will discuss one such multicast routing protocol called the Associativity-Based Ad hoc Multicast (ABAM) routing protocol [28] which along with its unicast version (Associativity-Based Routing, ABR [29]) have been quite popular and well-studied in the MANET literature for stability-based routing.

Tree Formation (Expansion) Phase: The stability of a link for a node with its neighbor is characterized by the associativity ticks, which is the number of beacons periodically received from that neighbor since the link was formed. Each node stores the value of the associativity ticks with its neighbors. Multicast tree construction is sourceinitiated and it could be repaired or expanded through receiver-initiated broadcast queries.

The source node initiates the tree construction phase by broadcasting a Multicast Broadcast Query (MBQ) message in the network to inform all prospective receiver nodes. When an intermediate node receives the MBQ message, it appends its node ID, the associativity ticks with the upstream node and then rebroadcasts it. Upon receiving several MBQ messages through different paths, a receiver node of the multicast group selects the most stable path and sends a MBQ-Reply packet along the selected path. The most stable path is the path with the largest proportion (i.e., percentage) of stable links. A link is said to be stable if the value of the associativity ticks is greater than or equal to the associativity threshold, calculated based on the node velocity and transmission range per node. In case of a tie (i.e., if two or more paths have the same largest proportion of stable links), then the minimum hop path among the contending paths is chosen. After receiving MBQ-Reply packets from each receiver of the group, the source sends MC-Setup messages to all receivers in order to establish the multicast tree.

[FIGURE 4 OMITTED]

Working Example: The working examples presented so far in the previous sections (on MAODV and BEMRP) are receiver-initiated. Receiver-initiated tree repair and expansion of ABAM would also be similar. The only difference is that the route selection metric adopted by the tree node receiving the Join Query packets would be based on the associativity ticks of the links traversed by the Join Query packets. The tree node chooses the path with the largest proportion of stable links and sends a Join Reply packet. So, for a change, we present here a working example that is source-initiated and is based on the concept of choosing paths with the largest proportion of stable links.

As shown in Figure 4, the source node S initiates a broadcast query reply cycle of the MBQ packets. The link weight shown in the figure represents the associativity tick value. The associativity threshold value is assumed to be 6. Accordingly, if the associativity tick value for a link is greater than or equal to the threshold, the link is said to be "stable"; otherwise, unstable. When a multicast receiver node receives MBQ packets across several paths, it calculates the proportion of stable links on each of these paths and chooses the path with the largest proportion of stable links. In the example, R3 receives MBQ packets across three paths from S: S [right arrow] I4 [right arrow] I6 [right arrow] I7 [right arrow] I5 [right arrow] R3 (3/5); S I1 [right arrow] I8 [right arrow] I5 [right arrow] R3 (2/4) and S [right arrow] I1 [right arrow] I2 [right arrow] I3 [right arrow] I10 [right arrow] I9 [right arrow] R3 (4/6). The ratios included inside the parenthesis represent the proportion of stable links on each of the above paths. R3 chooses the path S [right arrow] I1 [right arrow] I2 [right arrow] I3 [right arrow] I10 [right arrow] I9 [right arrow] R3 with the maximum proportion (4/6 = 67%) of stable links and sends a MBQ-Reply packet to the source along this path. Likewise, the receiver nodes R1 and R2 choose the paths S I4 [right arrow] I11 R1 (2/3) and S I1 [right arrow] I2 [right arrow] R2 (2/3) respectively. For simplicity in the illustration, we do not show the source S sending the MC-Setup message on each of the paths traversed by the MBQ-Reply packets.

Tree Maintenance Phase: Tree maintenance is by using a Local Query Reply cycle. The upstream node of the broken link attempts to fix a route to the receiver node by broadcasting a Local Query message with TTL value of 1. When the receiver node receives the Local Query message, it responds with a Local Reply message. The upstream node then sends the MC-Setup message to the receiver. If the upstream node could not find a route to the receiver, then it transfers the responsibility of fixing the route to its immediate upstream node on the path from the receiver to the source. This upstream node then initiates a broadcast of the Local Query message with TTL set to 2. This procedure is continued until the timer at the receiver node expires and it broadcasts a Join Query message to join the multicast group.

The Join Query message is broadcast by a newly joining receiver node or a receiver node that got cut off from the multicast tree and could not join the tree using a Local Query Reply cycle. The Join Query message propagates until it reaches a tree node. During its propagation, the forwarding nodes append their node ID and the associativity tick values with the downstream node from which the message was received. When a tree node receives a specific Join Query message (identified using a sequence number) for the first time, it waits for a while to receive the Join Query messages along different paths; chooses the path with the largest proportion of stable links and sends a Join Reply message on the selected stable path. The receiver node confirms its participation in the multicast session by sending a Reserve message on the path traversed by the Join Reply message.

3.4 Multicast Zone-based Routing Protocol (MZRP)

MZRP [34] is the multicast extension of the unicast Zone Routing Protocol (ZRP) [11], a hybrid of both proactive and reactive routing strategies. A zone in the network comprises of nodes that are within 2 or 3 hops from each other. There exists multiple zones in the network and often these zones overlap with each other. A border node is the node that is part of more than one zone. ZRP employs proactive routing for intra-zone communication and a combination of proactive and reactive routing protocols for inter-zone communication. For example, if a source node s has to communicate with a destination node d that is in the same zone of s, then it utilizes the services of the proactive routing protocol for that zone; on the other hand, if the destination is in some other zone, then the source node has to utilize the proactive routing protocols implemented in their respective zones and a reactive routing protocol that is implemented for inter-zone communication. ZRP does not depend on any specific proactive and reactive routing protocol for intrazone and inter-zone communication. Likewise, MZRP does not depend on any underlying unicast routing protocol. The proactive routing mechanism within a zone is realized through periodic beacon-exchange and the reactive routing mechanism for communication across zones is realized through on-demand flooding and multicast tree construction.

Node Advertisement and Zone Initialization: Each node advertises itself to its zone members by broadcasting an Advertisement packet whose propagation is controlled using a time-to-live (TTL) value that is normally set to the zone radius. Nodes receiving the Advertisement packet create a route entry for the source in their zone routing table and update their neighbor table with the upstream node that sent the Advertisement packet. ZRP operates in soft state i.e., nodes expunge route entries for a node that fails to send periodic Advertisement packets to indicate its presence in the zone. Thus, topology changes within a zone are often localized and not broadcast to other zones.

Multicast Tree Creation inside a Zone: Multicast tree creation within a zone (illustrated in Figure 5 [34]) is done as follows: The source node broadcasts a Tree-Create packet, uniquely identified using a session id, with a TTL value set to the zone radius. An intermediate node upon receiving the Tree-Create packet creates a multicast route entry with an empty list of downstream nodes and the upstream node is set to the node that sent the Tree-Create packet. Any zone node that is interested to be a receiver of the multicast session responds with a Tree-Create-ACK packet that travels back to the source on the reverse path traversed by the Tree-Create packet. Intermediate nodes that receive the Tree-Create-ACK packet, for a multicast session for which an entry has been already created in the routing table, updates the downstream node list by adding the ID of the neighbor node from which the Tree-Create-ACK packet was received.

[FIGURE 5 OMITTED]

Extension of the Multicast Tree to the Entire Network: To extend the multicast tree to the entire network (refer Figure 6), the source node unicasts a Tree-Propagate packet to the border nodes of its own zone. After receiving a Tree-Propagate packet, a border node creates a route entry for the session in its multicast table and initiates the zone-wide broadcast of a Tree-Create packet. Any interested node in the zone of the border node responds with a Tree-Create-ACK packet that is duly forwarded by the border node to the multicast source. The source specifies, in the Tree-Propagate packet, a network-wide TTL value indicating the number of zones the packet can be forwarded by a border node. A border node decrements this TTL value by 1 and if it is still above zero, the Tree-Propagate packet is sent to the other border nodes within that zone. Once the multicast tree is constructed, the source node starts sending data on the tree and is propagated across zones, as per the downstream node list maintained at the intermediate forwarding nodes.

[FIGURE 6 OMITTED]

Zone and Multicast Tree Maintenance: Multicast route entries are maintained in soft state: The source node periodically, for every Refresh-Interval, refreshes the entries at the intermediate nodes and receiver nodes (collectively referred to as member nodes) by sending a Tree-Refresh packet that propagates down the tree across zones. If a member node gets disconnected from the tree, it sends a Join packet, identifying the multicast session, to all of its zone nodes. Any member node that is in the multicast tree, and has not suffered any disconnection, responds with a Join-ACK packet and adds the neighbor node that sent the Join packet to the list of downstream nodes. A similar procedure is adopted at all the nodes that receive the Join and/or Join-ACK packets. Figure 7 (adapted from [34]) illustrates the rejoin process within a zone. If a disconnected member node fails to receive any Join-ACK packets from its zone nodes within a certain time, then it sends a Join-Propagate packet to all of its border nodes, which in turn send Join packets to all their zone nodes. This process continues until a border node gets a Join-ACK packet that is duly forwarded to the disconnected member node. A receiver node disconnects from the multicast session by sending a Tree-Prune message to its upstream node in the tree. The upstream node will remove the receiver node from its list of downstream nodes for the tree; if the list becomes empty after the removal and the node is not an interested receiver node (i.e., has been just an intermediate tree node), then the node sends a Tree-Prune message to its upstream node further up in the tree.

[FIGURE 7 OMITTED]

4. Shared-Tree based Multicast Protocols

Shared tree-based protocols construct a single tree that is rooted at a central control point called the Rendezvous Point (RP). Typically, MANETs operate on a 2-level mobility model with only a fraction of the nodes moving fast and the rest of the nodes moving relatively very slowly [10]. The RP is often chosen to be the slowest moving node in a MANET so that the shared tree can be maintained irrespective of the mobility of the source nodes. The RP is connected to the receiver nodes of the multicast session and the source nodes send the data packets to the RP based on the underlying unicast routing protocol.

As shared tree-based protocols are vulnerable to make data packets take a circuitous route (source to RP; RP to receiver), shortest paths between the source nodes and the RP is usually the preferred unicast routing strategy. Still, shared tree-based protocols are known to yield a lower throughput compared to per source tree-based protocols. A compromise solution called "adaptive-tree multicast" is applicable wherein if the receivers request the source, the source node may construct its own rooted tree to deliver the packets on the shortest path [10]. In this section, we review the features and performance of the Shared-Tree WIreless Multicast (ST-WIM) protocol, Ad hoc Multicast Routing protocol utilizing Increasing id numberS (AMRIS) and the Ad hoc Multicast Routing protocol (AMRoute) as representatives of the Cluster-based, Session-specific and IP-multicast session based protocols.

4.1 Cluster-based Shared-Tree Wireless Multicast Protocol (ST-WIM)

Shared-tree wireless multicast protocol (ST-WIM) [4] is based on sparse PIM [8], a unicast protocol for wired networks. ST-WIM is portable to different wireless platforms as it is independent of the underlying wireless routing protocol. Each intermediate node in a shared-tree must keep track of the state of its downstream members. ST-WIM uses two schemes for shared-tree maintenance: hard state and soft state. ST-WIM is implemented in an architecture that uses cluster routing and the token access protocol for inter-cluster and intra-cluster communication [5]. So, we first briefly describe here the cluster networks that form the backbone of ST-WIM. More details regarding cluster networks and token access protocol can be found in [5].

Clusters are aggregation of nodes under a cluster-head. Each node in a cluster can directly communicate with the cluster-head and possibly with each other. Gateways are nodes located in more than one cluster and provide support for adjacent clusters to communicate. Cluster-heads are commonly selected using the lowest-ID or highest-connectivity algorithms. But frequent changes to the cluster-head affect the performance of the protocols using them as well as in scheduling and resource allocation. A least-cluster-head-change algorithm has been proposed in [5] that advocates only two conditions for change in cluster-head: (a) when two or more cluster-heads come within the range of each other and (b) a node gets disconnected from any cluster. Clustering provides efficient allocation of wireless channels among different clusters. It permits spatial reuse of different spreading codes across different clusters, which reduces inter-cluster interference [4]. Orthogonal codes are used across adjacent clusters. Clustering algorithms converge in O(1) time and hence the presence of clusters does not deter the convergence of the routing algorithm.

Hard State Approach: In the hard state approach, a node that wishes to join the multicast group sends an explicit Join-Request message to the RP and waits for an acknowledgement to become a member. An upstream node maintains the link with its downstream node until it receives an explicit Quit-Request from the downstream node or the downstream link is disconnected. The hard-state approach relies heavily on the underlying medium access control (MAC) protocol to provide information regarding the connectivity of the downstream links. The MAC protocol uses a periodic beaconing mechanism to detect node connectivity. Downstream nodes can also disconnect from one upstream node and send an explicit Join-Request message to the RP to join another upstream node. When a parent link is disconnected, a downstream node recovers by either sending a Join-Request message to rejoin the tree via a new parent node or by broadcasting a Flush-Tree message to its children [4]. In the latter scenario, the Flush-Tree message propagates down the entire subtree and the downstream leaf nodes rejoin the tree individually. Rejoin by an internal node is bound to sometimes create loops when it forms a link with its own downstream node. Hence, in MANET, rejoin using the flush scheme is preferred.

Soft State Approach: In the soft state approach, a node wishing to remain in the multicast group must send a periodic Join-Request packet to the RP. No acknowledgment packets are sent back. An upstream node receiving a Join-Request packet from the downstream node creates a state for the downstream neighbor and attaches a timestamp to it. Nodes receiving the Join-Request packet forward them directly to the RP using the underlying routing scheme and there is no need to keep track of the upstream nodes. This is different from the hard state approach where a node needs to keep track of both its upstream and downstream nodes.

Hard State vs. Soft State: Simulation experiments in [4] show that the hard state acknowledgment delay is less than that of the soft state join latency which is less than the hard state data delay. The values for the [T.sub.refresh] and [T.sub.timeout] time periods must be carefully chosen to account for mobility and channel access overhead. Even though short refresh periods are desirable in a highly mobile network, it will cause an increase in the channel overhead. Large values of [T.sub.timeout], will result in the network having stale links with wasteful duplicate transmissions. With decreasing [T.sub.refresh[, the control traffic for soft state is higher than that of hard state.

4.2 Session-specific Ad hoc Multicast Routing Protocol utilizing Increasing Id Numbers (AMRIS)

AMRIS [32] provides a unique session-specific multicast session member id (msm id) to each participant. The msm id indicates the logical height of a node in the multicast delivery tree rooted at the sender that has the smallest msm id (Sid) in the tree. All other nodes in the tree have an msm id that is higher than that of its parent. In case of a multiple-sender environment, the Sid is elected among the senders. AMRIS uses the underlying MAC layer beaconing mechanism to detect the presence of neighbors.

Tree Initialization Phase: During the tree-initialization phase, the Sid broadcasts a New-Session message (containing the Sid, msm id and other routing metrics) in its neighborhood. A node, receiving the New-Session message, updates the msm id in the message with a newly computed larger value that is also used to identify the node in the tree. If a node receives more than one New-Session messages from several neighbors within a random jitter amount of time, then the message with the best routing metric is selected and updated with a newly computed msm id value. The updated New-Session message is then rebroadcast. The above strategy prevents broadcast storms. Note that the newly computed msm ids are not consecutive and the gaps can be used to locally repair the delivery tree.

To join the multicast group, a downstream node X sends a unicast Join-Request message to one of a randomly chosen neighbor node that is also a potential parent node (having a lower msm id), say Y. If Y is already part of the multicast tree, then Y sends a Join-ACK message to X. Otherwise, Y forwards the Join-Request message to a set of potential parents of itself. The above process continues until the Join-Request message reaches a parent node that is part of the multicast delivery tree. The parent node responds back with a Join-ACK message to X, which can now confirm its participation in the multicast session by sending back a Join-Conf message to the parent node.

Tree Maintenance Phase: Upon link failure, the downstream node (with a relatively higher msm id) is responsible to rejoin the multicast tree [32]. Before broadcasting a Join-Request message, the downstream node of a broken link attempts to find potential parent nodes by locally repairing the route using an expanded-ring search process. Even the Join-Request message is broadcast with a TTL value that restricts the number of hops the message can propagate. If a node has no valid msm id to (re)join a multicast tree, it computes an msm id for itself based on the msm ids of its neighboring nodes and then joins the multicast tree through the branch reconstruction process explained above [32]. The beacon update period at the MAC layer has to be properly chosen to avoid detection of micro-term breakages that can unnecessarily trigger the branch reconstruction process and incur a lot of control overhead.

4.3 IP Multicast Session-based Ad hoc Multicast Routing Protocol (AMRoute)

The ad hoc multicast routing protocol (AMRoute) [33] is an attempt to enable the use of IP multicast in MANETs. AMRoute make use of the underlying unicast routing protocol to detect network dynamics while it takes care of the frequent tree reconfigurations. The AMRoute distribution tree assumes unicast connectivity among member nodes and continues to function despite network changes. The two key features that make AMRoute robust and efficient are [33]: (1) User-multicast trees allow group members to replicate and forward over unicast tunnels and (2) Core node migrating dynamically resulting in changes to the group membership and network connectivity. Since non-member nodes in the tree need not be even multicast enabled, user-multicast trees eliminate the need to reconfigure the tree frequently in highly dynamic MANETs. But, the tradeoff is a reduction in bandwidth efficiency as non-member nodes cannot replicate packets on user-multicast trees.

The AMRoute protocol consists of a mesh creation phase following a tree creation phase. Each group member forms a 1-node mesh identifying itself as the core. The core node in pursuit of other group members periodically broadcasts Join-Request messages in an expanded ring fashion. A member node, receiving Join-Request messages from a core node in a different mesh, responds back with a Join-ACK establishing a bi-directional tunnel between the two nodes. Multiple cores result due to mesh mergers. All the core nodes elect a single core for the unified mesh using a core resolution algorithm (for e.g., the node with the highest IP address could be selected as the core node). The core node need not be static. It can migrate dynamically according to group membership and network connectivity [33].

The core node of the unified mesh is responsible for the tree creation process. The core node periodically sends Tree-Create messages along the links incident on it in the mesh. The mesh size and node mobility in the mesh determines the periodicity of Tree-Create messages. Group members that receive non-duplicate Tree-Create messages forward it to all the links except the incoming link. If the link is not used as part of the tree, a Tree-Create-NAK is transmitted through the incoming link. Upon receiving a Tree-Create-NAK, the group member marks the incoming link as a mesh link. A member node forwards data received on a tree link but discards it when received on a mesh link and sends a Tree-Create-NAK along that link.

Simulation studies of AMRoute show that the broadcast traffic is independent of group size. This reflects on the JOIN-REQs being generated at a fixed rate by the core. For a constant network size, the join latency increases as the group size increases. The major disadvantage of the protocol is it forms temporary loops during tree creation and non-optimal trees at high mobility [17]. At high mobility and small group size, critical links (unidirectional links) are formed among the group members. Prolonged existence of critical links may sometime isolate the sources. A performance comparison of the major ad hoc multicast routing protocols in [17] shows AMRoute to be the least effective.

5. Source-initiated Mesh-based Multicast Protocols

A mesh is a set of nodes in the network such that all the nodes in the mesh forward multicast packets via scoped flooding [14]. As stated before, mesh-based protocols are more robust to link failures than tree-based protocols. Mesh-based protocols can be either source-initiated or receiver-initiated. In most of the cases, the forwarding mesh in source-initiated protocols is a union of per-source meshes, while receiver-initiated mesh protocols form a single shared mesh for all the sources. In this section, we discuss the source-initiated mesh based multicast routing protocols and in the next section, we discuss the receiver-initiated mesh based protocols. In the category of source-initiated mesh based multicast routing protocols, we discuss the well-known On-Demand Multicast Routing Protocol (ODMRP) along with its extensions to handle high mobility and low node density (i.e., sparse networks), and the Neighbor Supporting multicast Mesh Protocol (NSMP).

5.1 On-Demand Multicast Routing Protocol (ODMRP)

ODMRP [16] is a mesh-based multicast routing protocol based on the notion of a forwarding group (shown in Figure 8)--a set of nodes that forward data on the shortest paths between any two multicast members [2][6]. Multicast group membership and routes are established and updated by the source in an on-demand basis. This leads to reduction in channel/storage overhead and an increase in scalability. A soft-state approach is used for mesh maintenance and member nodes are not required to explicitly send leave messages while quitting a group. A performance comparison of the major ad hoc multicast routing protocols in [17] shows ODMRP to be the most advantageous and preferred protocol in mobile wireless networks. ODMRP can also operate independently as an efficient unicast routing protocol.

ODMRP operates through a request phase and a reply phase. Multicast sources, which are not aware of the routes or membership, broadcast a Join-Data packet. When a node receives the Join-Data packet for the first time, it updates its routing table by storing the upstream node id (backward learning process) and rebroadcasts the packet. Upon receiving a non-duplicate Join-Data packet, a multicast receiver creates and broadcasts a Join-Reply packet in its neighborhood. When a node receives the Join-Reply packet, it checks if it is listed as the next node ID in the packet. If so, the node is located on the path to the source and becomes part of the forwarding group. A FG (forwarding group) flag is set in its routing table and the node broadcasts its own Join-Reply packet. Likewise, the Join-Reply packet gets forwarded by the FG member nodes until it reaches the multicast source on the shortest path. As a result of this source-receiver route construction and update process, a mesh of nodes referred to as the forwarding group is built.

ODMRP makes use of the IEEE 802.11 MAC protocol to reliably transmit the Join-Reply packets that are critical to establishing and refreshing the forwarding groups and the associated multicast routes. Once the forwarding group is established and multicast routes are constructed, a source node sends down data packets to the receivers [16]. To leave a multicast group, the source node and receiver nodes can respectively stop sending the Join-Query and Join-Reply packets meant for that group. If a FG member node does not receive a Join-Reply packet before a timeout period, the node demotes itself to a non-forwarding node of the mesh.

The performance of ODMRP heavily depends on the values selected for the route refresh interval and the FG timeout interval [16]. With small route refresh interval, there will be frequent broadcast of fresh route and membership information that may lead to a deluge of packets causing network congestion. On the other hand, if a larger route refresh interval is selected, nodes may not be aware of the latest route and multicast membership changes and this could lead to poor performance. The FG timeout value must be at least 3-5 times larger than the route refresh interval value. For networks with a heavy traffic load, a smaller value for the FG timeout interval will help to reduce redundancy of membership messages [16]; whereas, in the case of high mobility, a larger FG timeout value can make way for more alternative paths.

[FIGURE 8 OMITTED]

ODMRP based on Mobility Prediction: Since ODMRP requires periodic flooding of JOIN-QUERY messages to refresh routes and group membership, finding an optimal refresh interval is critical for its performance. An improved version of ODMRP is proposed in [2] that adapts the refresh interval to mobility patterns and speeds. The duration of time the routes will remain valid is predicted using the location and mobility information provided by Global Positioning System (GPS) [12]. Using the predicted time of route disconnection, Join-Query messages are sent only when there are imminent route breaks of ongoing data sessions [2].

The prediction method used in [2], originally proposed in [27], assumes a free-space propagation model, in which the received signal strength solely depends on its distance to the transmitter. Also, all nodes in the network are assumed to have their clocks synchronized using the network time protocol (NTP) or the GPS clock itself. With all these assumptions, if the motion parameters of two neighbors (e.g., speed, direction and radio propagation range) are known, the duration of time the two nodes will remain connected can be determined [27]. Let two mobile nodes i and j be within the transmission range r of each other. Let ([x.sub.i], [y.sub.i]) and ([x.sub.i], [y.sub.j]) be the co-ordinates of i and j respectively. Let [v.sub.i] and [v.sub.j] be the speeds and [[theta].sub.i] and [[theta].sub.j] (0 [[theta].sub.i], [[theta].sub.j] < 2[pi]) be the moving directions of i and j respectively. The amount of time, the two nodes will remain connected is predicted [27] as:

[D.sub.t] = - (ab + cd_ + [square root or ([a.sup.2] + [c.sup.2]) [r.sup.2] - [(ad - bc).sup.2] / [a.sup.2] + [c.sup.2]

where:

a = [v.sub.i]cos[[theta].sub.i] -[v.sub.j]cos[[theta].sub.j] b = [x.sub.k] - [x.sub.j],

c = [v.sub.i][[theta].sub.i] - v.sub.j]sin][theta].sub.j] d = [y.sub.i] - [y.sub.j],

The structure of the Join-Query and the Join-Reply packets need to be slightly modified to accommodate the information derived from mobility prediction. The Min-LET (minimum link expiration time) value field in the Join-Query packet indicates the minimum expiration time of the links traversed by the packet, starting from the source. The Min-LET value set by the source in the Join-Query packet is the Max-LET value (theoretically [infinity]), as the source is not connected to any upstream node. An intermediate node, upon receiving a non-duplicate Join-Query packet, will predict the LET of the link with the immediate upstream sender of the packet, and set the Min-LET value in the packet to be the minimum of its current value and the predicted LET. The same procedure is followed at the member nodes too and the final value of Min-LET in the Join-Query packet is referred as to the Route Expiration Time (RET) of the path from the source to the receiver node. A member node waits for a certain time before responding back with a Join-Reply packet. If more than one Join-Query packet is received, the member node chooses the (stable) path with the largest RET and sends a Join-Reply packet (with the RET value included) on this path. If a forwarding group node receives several Join-Reply packets, it chooses the path with the minimum RET and sends its own Join-Reply packet with the chosen RET value. After receiving Join-Reply packets across several paths, the source sets the predicted expiration time of the mesh to be the minimum of the RET values of these packets. The source starts sending data packets using the constructed stable mesh. Before the predicted mesh expiration time approaches, the source node floods a Join-Query packet.

Some of the drawbacks of the mobility prediction technique is that if a node suddenly changes direction and/or speed, the predicted expiration time of the mesh and the RET values of the paths involving that node may be no longer valid. Also, since route and mesh construction is source-initiated, a new receiver node wishing to become a multicast member, has to wait for the next sequence of Join-Query packets coming from the source. However, the performance of ODMRP has been reported to be significantly improved [2] with the use of mobility prediction.

PatchODMRP: In ODMRP, the forwarding group (FG) for a multicast group is an aggregate of the per-source meshes. For multicast groups with fewer sources, the forwarding mesh will be sparsely populated and may require frequent reconfiguration using flooding of Join-Query packets. To handle this problem, the PatchODMRP protocol has been proposed in [15], according to which whenever a FG member node sees the possibility of it getting separated from the mesh, it starts a patching procedure to reconnect itself to the mesh through a temporary path. With PatchODMRP, the Join-Query interval can be sufficiently long (the tradeoff is multicast group join latency for new receivers) even in the presence of high mobility. Simulation results in [15] illustrate that for larger Join-Query intervals, the packet delivery ratio of PatchODMRP increases while that of the original ODMRP decreases. For a given degree of node mobility, the control overhead of PatchODMRP is 6 to 7 times lower than that of original ODMRP.

The routing table at a FG node contains a HopCount field (not in the original ODMRP) specifying the hop count from the destination to the node and the field is updated when a FG node processes a Join-Query packet. The forwarding group table also contains two additional fields (compared to ODMRP): the Upstream FG nodes (has the next hop information) and Source list (list of multicast source nodes); these two fields are processed when an FG node processes the Join-Reply packets. When a node is no longer a neighbor, an FG node checks its forwarding group table whether the lost neighbor is in its Upstream FG nodes list.

If an FG node loses connectivity to an upstream FG node, it initiates a local patching procedure by flooding an advertisement (ADVT) packet with a limited HopCount value (typically set to 2 or 3) for propagation. The ADVT packet contains the 3-field tuple {MGID, SrcAddr, SrcHopCount} where MGID, SrcAddr, SrcHopCount respectively refer to the multicast group ID, the multicast source address and the number of hops from SrcAddr to the initiator of the ADVT packet. When an FG node receives the ADVT packet, it checks whether it has a table entry for the MGID specified in the packet--if so, the FG node checks the value for the HopCount field in its routing table for the path from itself to the SrcAddr listed in the ADVT packet. If the HopCount value in the routing table is less than the SrcHopCount specified in the ADVT packet, it means that the FG node lies on a non-cyclic path from the initiator of the ADVT packet to the multicast source--SrcAddr. The FG node sends back a Patch packet to the initiator of the ADVT packet and the nodes located in the path traversed by the Patch packet become the new FG nodes of the multicast group. If any or all of the above conditions are not met, then the FG node decrements the HopCount field value in the ADVT packet by

1 and if the value is still above zero, the packet is broadcast to the neighbor nodes with the PreHopAddress set to the address of the FG node.

5.2 Neighbor Supporting Multicast Mesh Protocol (NSMP)

NSMP [18] is an efficient mesh-based multicast routing protocol that reduces the number of control message broadcasts as much as possible. NSMP resorts to networkwide flooding only during initial route establishment and during network partition repair. For normal periodic mesh maintenance, a local route discovery is initiated with control messages sent and forwarded only by nodes that are part of the mesh. When a node wants to join the multicast mesh as a receiver, it selects a path that contains a maximum number of the existing FG nodes. By reducing the number of forwarding nodes, NSMP enhances route efficiency (less contention and lower end-to-end delay) [18]. Simulation experiments in [18] indicate that irrespective of the number of sources, NSMP (compared to ODMRP) reduces the control overhead and the number of redundant data transmissions by more than 15% and 30% respectively.

[FIGURE 9 OMITTED]

An example for NSMP multicast mesh creation is illustrated in Figure 9. The initial network is shown in Figure 9.a and the final multicast mesh (with node 4 as the source; nodes 6 and 13 as the receivers) is shown in Figure 9.b. To start with, node 4 broadcasts a Flood-REQ packet to its neighbors. Upon receiving the Flood-REQ, node 5 creates a reverse path entry for node 4 in its routing table and forwards the packet to its neighbor nodes. Receiver node 6, upon receiving the Flood-REQ packet, responds with a REP packet that reaches the source node 4 through node 5. Upon receiving the REP packet, node 5 updates its routing table by creating an entry for the multicast group and becomes part of the mesh. Similarly, receiver node 13 responds to the Flood-REQ through node 9 that becomes a forwarding node for the mesh.

Group neighbor nodes are nodes that are adjacent to at least one forwarding node in the mesh for the group. Nodes 1, 2, 3, 7, 8, 10, 12 and 17 are the group neighbor nodes for the mesh shown in Figure 9.b. If a neighbor node 17 is interested in becoming a receiver for the multicast group, then it chooses a path (4, 5, 9, 13, 17) that will introduce the least number of new forwarding nodes to the mesh. Thus, NSMP offers route efficiency at the cost of route robustness [18]. However, NSMP can be configured with a cost function that will enable a receiver node to choose a robust path over a more efficient path or vice-versa. The cost function is (1-a)*FC+a*NC where 0 [less than or equal to] a [less than or equal to] 1 and FC, NC are respectively the number of forwarding nodes and the number of non-forwarding nodes traversed by the Local-REQ packets (used for mesh maintenance, explained below) along different paths from the multicast source to the interested receiver. Larger the value of the weight factor 'a,' more robust is the path chosen.

NSMP mesh maintenance is through a source-initiated local route discovery involving Local-REQ packets that are forwarded only by the mesh nodes and the group neighbor nodes. Nodes that are two-hops away from the mesh receive these Local-REQ packets and could join the mesh as receiver or as a forwarding/ group neighbor node by responding back with REP packets. However, a non-member node that is more than two hops away from the mesh can join the mesh only by flooding a MEM-REQ (membership request) packet towards the mesh. NSMP operates in soft-state: the forwarding nodes and group neighbor nodes of a mesh are to be refreshed within a pre-defined timeout period in order for them to stay committed to the mesh.

[FIGURE 10 OMITTED]

An example for NSMP mesh maintenance is illustrated in Figure 10 (adapted from [18]). Consider the link (9, 13) between a FG node 9 and a receiver node 13 to fail. The source node 4 eventually sends out a Local-REQ packet that is forwarded down the mesh by the group neighbor nodes 8 and 12. When node 13 receives the Local-REQ packet, it responds with a REP packet through node 12 to build a new route to the source. The repaired mesh is shown in Figure 10.b. Note that local route discovery cannot repair all link failures--for example, the failure of link (8, 12) in Figure 10.b cannot be repaired.

6. Receiver-initiated Mesh-based Multicast Protocols

Receiver-initiated mesh protocols are more robust to node mobility as they attempt to maintain a shared mesh involving all the source nodes of the multicast group. The multicast source nodes forward packets on the reverse shortest path from the receiver nodes to the source. This section reviews the working of two receiver-initiated multicast mesh protocols: the core-assisted mesh protocol (CAMP) [9] and the intelligent on-demand multicast routing protocol (IOD- MRP) [31].

6.1 Core-Assisted Mesh Protocol (CAMP)

CAMP designates nodes into three categories: duplex, simplex and non-members [9]. Duplex nodes are the regular mesh nodes having the functionality seen in the routing protocols discussed in the previous sections. Simplex members can forward packets from the source-nodes to the rest of the mesh; but cannot respond for any membership query packets. CAMP maintains one or more core nodes per mesh. A node interested to join the multicast mesh first queries its neighbor nodes to see if any of them are part of the mesh. If none of the neighbors are part of the mesh, the prospective receiver node initiates a scoped flooding of the Join-Request messages targeted towards the core nodes of the mesh. Upon receiving a non-duplicate Join-Request message, a duplex member node or the core node responds with a Join-ACK message that is propagated back to the initiator of the Join-Request message. CAMP lets core nodes to leave the multicast mesh if these nodes are not required to provide efficient dissemination paths. A core node leaves the multicast group by broadcasting a Quit notification message to its neighbors.

A receiver node periodically checks whether the multicast data packets traverse the reverse shortest path back to the source. If it is not the case, the receiver node sends a Heart-Beat or the Push-Join message along the reverse shortest path to the source [9]. A member node (including the receiver node) forwards the Hear-Beat message to its successor node on the reverse shortest path if the latter is already a member of the mesh; otherwise, the member node sends a Push-Join message to the neighbor successor node asking it to join the multicast mesh and waits for an ACK from that node. Duplex members respond with a regular ACK, while simplex members send an ACK-Simplex message. If no ACK is received within a certain time, the Push-Join message is propagated further until a member node that is directly connected to the source is reached.

CAMP allows the member nodes of a mesh to select their "anchor" nodes--defined as neighbor nodes that are required to re-broadcast any non-redundant data packets received. The member nodes can periodically refresh their "anchor" nodes by broadcasting updates. A neighbor node can deny the "anchor" request or discontinue from that role if it is no longer interested at. CAMP heavily needs the support of the underlying unicast routing protocol to provide route updates [9]. In this context, CAMP prefers to co-exist with an underlying unicast routing protocol called wireless routing protocol (WRP) [20] that marks a subset of destinations as unreachable during periods of network re-convergence. CAMP piggybacks its control messages onto the back of WRP updates and the control overhead is bound to increase exponentially with traffic. Also, CAMP cannot be used directly with unicast routing protocols based on the Bellman-Ford algorithm [7] as well as extensions are needed to work with on-demand routing protocols [9].

6.2 Intelligent On-Demand Multicast Routing Protocol (IOD-MRP)

Even though, the concept of receiver-initiated joining in ad hoc multicast routing protocols seemed to have more advantages than source-initiated joining [9], CAMP has its own set of disadvantages that require serious modifications in order to be competent with ODMRP and its extensions. In this direction, an intelligent on-demand multicast routing protocol (IOD-MRP) has been proposed in [31] that removes the concept of cores from CAMP and manages to reduce the control overhead, using an intelligent mobility management scheme, to 3-13% to that of CAMP. In CAMP, prospective receiver nodes unicast a Join-Request message to the core node to join the mesh. However, this may not be successful due to the dynamically changing network topology and routing information need not be always accurate and available. As part of the IOD-MRP mobility management procedure, receiver nodes search for the shortest path to join the multicast mesh in an on-demand fashion.

IOD-MRP designates nodes into two categories: I-nodes (nodes interested in the multicast session) and U-nodes (nodes not interested in the multicast session). A node opening the multicast session, floods a Broadcast-Join-REQ message if it cannot find any information about the session in its multicast routing table. Upon receiving a non-duplicate Broadcast-Join-REQ message, an I-node responds with a Unicast-Join-REQ message to the sender of the Broadcast-Join-REQ message and joins the multicast session.

IOD-MRP allows prospective receiver nodes to join the multicast mesh through two modes: Unicast-Join-REQ mode (preferred) and Broadcast-Join-REQ. An I-node first sends a Unicast-Join-REQ message to join the multicast session. When an active member node receives the Unicast-JoinREQ message for which it is also the targeted destination, the intermediate node responds with a positive ACK message sent back to the I-node. When a non-member node receives the Unicast-Join-REQ message, it will either send a negative ACK to the I-node or propagate the Unicast-Join-REQ message further towards the intended destination node. If an I-node does not receive a positive ACK within a certain time, it enters into the Broadcast-Join-REQ mode and initiates a scoped flooding of the Broadcast-Join-REQ message using expanding ring search. A non-member node receiving the Broadcast-Join-REQ message creates an entry for the multicast group in its routing table, decrements the TTL flag in the message by 1 and forwards the message further if the TTL is still positive. If a U-node receives either the JoinREQ packets or the multicast data packets, it can simply record the multicast session information in its routing table. Later, if the U-node becomes an I-node, it can simply initiate a Unicast-Join-REQ message to join the multicast group.

After a node joins the multicast session, the quality of the path traversed by the data packets sent from the multicast source is continuously monitored through an intelligent procedure (described below) so that the receiver node stays connected to the multicast source on the best path, called the anchor path. A path between the multicast source and a receiver is said to be an anchor path if (1) the path is traversed by most of the multicast data packets sent from the source to the receiver and (2) the path has a low packet loss rate. The receiver periodically monitors the quality of the paths traversed by the multicast data packets and notifies the multicast source of the anchor path it has chosen by sending a Set-Anchor message through that path. Intermediate nodes along the chosen anchor path are forced to stay in the mesh. If the receiver node determines a new path that is better than the current anchor path, then it sends a Reset-Anchor message on the recently used anchor path and sends a Set-Anchor message on the newly chosen best path. If no anchor paths can be found, the receiver resorts to unicast communication with the multicast source. When a source node leaves the multicast group, it sends a Session-Leave message that is forwarded down the mesh so that the member nodes can purge any table entries associated with the leaving multicast source.

7. Conclusions and Future Research Directions

In this survey, we reviewed various multicast routing protocols for MANETs. Most of the multicast routing protocols for MANETs are either mesh-based or tree-based. Tree-based protocols can be either shared-trees or per-source based shortest trees. Mesh protocols can be either source-initiated (union of per-source meshes) or receiver-initiated (shared mesh). Tree-based protocols are efficient in data transmission while mesh-based protocols are robust to topology changes and are more stable than tree-based protocols. The routes chosen using tree-based protocols are fragile and require frequent reconfiguration. Each of the protocols discussed in this survey has its own advantages and disadvantages. An ideal protocol that satisfies all the requirements of MANETs is tough to design. For example, a protocol that aims at routing efficiency has to sacrifice for route robustness.

Future research would involve a comprehensive simulation analysis of all of these representative multicast routing protocols in a discrete-event simulator and study their performance under identical scenarios. A lot of research papers that are currently available on performance comparison studies of MANET multicast routing protocols do not conduct a comprehensive simulation analysis of the different categories of multicast routing protocols (identified in this chapter) under identical scenarios. So, it is not easy to generalize the performance tradeoffs between the different categories and the representative multicast routing protocols. This could lead to development of more hybrid tree and mesh based protocols that could neutralize the tradeoffs and yield optimal performance simultaneously for more than one performance metric.

Another potential research could be to study the behavior of these multicast routing protocols under different topology control graphs (e.g., Relative neighborhood graph, Gabriel graph, Yao graph and Delaunay triangulation) [3][26]. Currently, the simulation studies available in the literature model the underlying network topology to be a unit disk graph wherein there is a link between any two nodes if the Euclidean distance between the two nodes is less than or equal to the transmission range of the nodes. While the unit disk graph model can yield significantly high network connectivity, each node will have a relatively larger number of neighbors. In a shared medium, typical of wireless networks, a larger neighborhood could severely drain the energy resources of a node as well as the network capacity due to the receipt of unintended packets and redundant transmissions. As the wireless nodes are battery charged, it is imperative to extend the operational lifetime of these devices as much as possible. Topology control is a potential solution to enhance the energy-efficiency and the capacity of the network. The focus of the topology control algorithms is to maintain the connectivity of the network with a reduced number of links as well as with a reduced transmission power per node (rather than the transmission power corresponding to the maximum transmission range) and thus optimize node lifetime.

References

[1] S. Agarwal, A. Ahuja, J. P. Singh and R. Shorey, "Route-Life Time Assessment Based Routing Protocol for Mobile Ad Hoc Networks," Proceedings of the IEEE International Conference on Communications, pp. 1697-1701, June 2000.

[2] S. Bae, S. Lee, W. Su and M. Gerla, "The Design, Implementation, and Performance Evaluation of the Ondemand Multicast Routing Protocol in Multi-hop Wireless Networks," IEEE Network, vol. 4, no. 1, pp. 70-77, August 2002.

[3] N. Burri, P. Rickenbach, R. Wattenhofer and Y. Weber, "Topology Control Made Practical: Increasing the Performance of Source Routing," Lecture Notes in Computer Science, vol. 4325, pp. 1-12, November 2006.

[4] C. C. Chiang, M. Gerla and L. Zhang, "Shared Tree Wireless Network Multicast," Proceedings of the 6th International Conference on Computer Communications and Networks, pp. 28-33, September 1997.

[5] C. C. Chiang, H. K. Wu, W. Liu and M. Gerla, "Routing in Clustered Multihop, Mobile Wireless Networks with Fading Channel," Proceedings of the IEEE Singapore International Conference on Networks (SICON), pp. 197-211, April 1997.

[6] C. C. Chiang, M. Gerla and M. Zhang, "Forwarding Group Multicast Protocol (FGMP) for Multi-hop, Mobile Wireless Networks," Baltzer Cluster Computing, vol. 1, no. 2, pp. 187-196, 1998.

[7] T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, "Introduction to Algorithms," 2nd Edition, MIT Press/ McGraw-Hill, September 2001.

[8] S. Deering, D. L. Estrin, D. Farinacci, V. Jacobson, C.-G. Liu and L. Wei, "The PIM Architecture for Wide-Area Multicast Routing," IEEE/ACM Transactions on Networking, vol. 4, no.2, pp. 153-162, April 1996.

[9] J. J. Garcia-Luna-Aceves and E. L. Madruga, "The Core-assisted Mesh Protocol," IEEE Journal on Selected Areas in Communications, vol. 17, no. 8, pp. 1380-1394, 1999.

[10] M. Gerla, C. C. Chiang, and L. Zhang, "Tree Multicast Strategies in Mobile, Multi-hop Wireless Networks," ACM/ Baltzer Mobile Networks and Applications, vol. 4, no. 3, pp. 193-207, October 1999.

[11] Z. J. Haas and M. R. Pearlman, "The Performance of Query Control Schemes for the Zone Routing Protocol," IEEE/ACM Transactions on Networking, vol. 9, no. 4, pp. 427-438, August 2001.

[12] B. Hofmann-Wellenhof, H. Lichtenegger and J. Collins, Global Positioning System: Theory and Practice, 5th ed., Springer, September 2004.

[13] D. B. Johnson, "Routing in Ad Hoc Networks of Mobile Hosts," Proceedings of the Workshop on Mobile Computing Systems and Applications, pp. 158-163, December 1994.

[14] C. Y. Lee and H. K. Cho, "Multicast Routing Considering Reliability and Network Load in Wireless Ad hoc Networks," Proceedings of the 53rd IEEE VTS Spring Vehicular Technology Conference, vol. 3, pp. 2203-2207, May 2001.

[15] M. Lee and Y. Kim, "PatchODMRP: An Ad hoc Multicast Routing Protocol," Proceedings of the 15th IEEE International Conference on Information Networking, pp. 537-543, January-February 2001.

[16] S. Lee, M. Gerla, C. C. Chiang, "On-demand Multicast Routing Protocol," Proceedings of the IEEE Wireless Communications and Networking Conference, vol. 3, pp. 1298-1302, 1999.

[17] S. Lee, W. Su, J. Hsu, M. Gerla and R. Bagrodia, "A Performance Comparison Study of Ad hoc Wireless Multicast Protocols," Proceedings of the 19th IEEE Annual Joint Conference on Computer Communications, vol. 2, pp. 565-574, March 2000.

[18] S. Lee and C. Kim, "Neighbor Supporting Ad hoc Multicast Routing Protocol," Proceedings of the 1st Annual Workshop on Mobile and Ad hoc Networking and Computing, pp. 37-44, August 2000.

[19] J. Moy, "Multicast Extensions to OSPF," Request for Comments: 1584, March 1994.

[20] S. Murthy and J. J. Garcia-Luna-Aceves, "An Efficient Routing Protocol for Wireless Networks," Mobile Networks and Applications, vol. 1, no. 2, pp. 183-197, October 1996.

[21] T. Ozaki, J. B. Kim and T. Suda, "Bandwidth-Efficient Multicast Routing Protocol for Ad hoc Networks," Proceedings of the 8th International Conference on Computer Communications and Networks, pp. 10-17, October 1999.

[22] V. D. Park and M. S. Corson, "A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks," Proceedings of the 16th Annual International Conference on Computer Communications, vol. 3, pp. 1405-1413, April 1997.

[23] C. E. Perkins and P. Bhagwat, "Highly Dynamic Destination Sequenced Distance Vector Routing for Mobile Computers," Proceedings of ACM (Special Interest Group on Data Communications) SIGCOMM, pp. 234-244, October 1994.

[24] C. E. Perkins and E. M. Royer, "Ad Hoc On-demand Distance Vector Routing," Proceedings of the 2nd Annual IEEE International Workshop on Mobile Computing Systems and Applications, pp. 90-100, February 1999.

[25] E. Royer and C. E. Perkins, "Multicast Operation of the Ad-hoc On-demand Distance Vector Routing Protocol," Proceedings of the 5th ACM/IEEE Annual Conference on Mobile Computing and Networking, pp. 207-218, Seattle, USA, August 1999.

[26] P. Santi, "Topology Control in Wireless Ad Hoc and Sensor Networks," Wiley Publishers, September 2005.

[27] W. Su and M. Gerla, "IPv6 Flow Handoff in Ad hoc Wireless Networks using Mobility Prediction," Proceedings of the IEEE Global Telecommunications Conference, pp. 271-275, December 1999.

[28] C. K. Toh, G. Guichal and S. Bunchua, "ABAM: On demand Associativity-based Multicast Routing for Ad hoc Mobile Networks," Proceedings of the 52nd IEEE Fall Vehicular Technology Conference, vol. 3, pp. 987-993, 2000.

[29] C. K. Toh, "Associativity-Based Routing for Ad hoc Mobile Networks," IEEE Personal Communications, vol. 4, no. 2, pp. 103-139, March 1997.

[30] D. Waitzman, C. Partridge and S. Deering, "Distance Vector Multicast Routing Protocol," Request for Comments: 1075, November 1998.

[31] K. Wang and C.-T. Chang, "An Intelligent On-Demand Multicast Routing Protocol in Ad hoc Networks," Proceedings of the 15th International Conference on Information Networking, pp. 909-914, 2001.

[32] C. W. Wu and Y. C. Tay, "AMRIS: A Multicast Protocol for Ad hoc Wireless Networks," Proceedings of the IEEE Military Communications Conference, vol. 1, pp. 25-29, 1999.

[33] J. Xie, R. R. Talpade, A. Mcauley and M. Liu, "AMRoute: Ad hoc Multicast Routing Protocol," Mobile Networks and Applications, vol. 7, no. 6, pp. 429-439, December 2002.

[34] X. Zhang and L. Jacob, "Multicast Zone Routing Protocol in Mobile Ad hoc Wireless Networks," Proceedings of the 28th Annual IEEE International Conference on Local Computer Networks, pp. 150-159, 2003.

Natarajan Meghanathan

Department of Computer Science, Jackson State University, P. O. Box 18839, 1400 John R. Lynch Street, Jackson, MS 39217, USA natarajan.meghanathan@jsums.edu
COPYRIGHT 2011 Kohat University of Science and Technology
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2011 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Meghanathan, Natarajan
Publication:International Journal of Communication Networks and Information Security (IJCNIS)
Article Type:Report
Date:Aug 1, 2011
Words:12055
Previous Article:Impact of varying channel model mixtures on radio resource management for the Ofdma downlink.
Next Article:Survey on opportunistic routing in multihop wireless networks.
Topics:

Terms of use | Privacy policy | Copyright © 2018 Farlex, Inc. | Feedback | For webmasters