Informatica 35 (2011 ) 165-184 165 Performance Comparison Study of Multicast Routing Protocols for Mobile Ad hoc Networks under Default Flooding and Density and Mobility Aware Energy-Efficient (DMEF) Broadcast Strategies Natarajan Meghanathan Department of Computer Science Jackson State University Jackson, MS 39217, USA E-mail: natarajan.meghanathan@jsums.edu Keywords: mobile ad hoc networks, broadcast, energy-efficiency, multicast routing, stability, simulation Received: June 10, 2010 Recently, we had proposed a novel network density and mobility aware energy-efficient broadcast route discovery strategy (called DMEF) to discover stable routes in mobile ad hoc networks (MANETs). DMEF works by letting each node to dynamically choose its own broadcast transmission range for the route discovery messages depending on the perceived number of neighbour nodes in its default maximum transmission range and the node's own mobility values at the time of route discovery. A node surrounded by more neighbours makes itself available to a smaller neighbourhood and vice-versa. Similarly, a slow moving node broadcasts the route discovery message to a majority of its neighbours so that links formed using this node can be more stable. A fast moving node advertises itself only to the neighbours closer to it. The effectiveness of DMEF has been so far tested only for MANET unicast and multi-path routing protocols. In this paper, we study the impact of DMEF on the performance of MANET multicast routing protocols. We investigate the minimum-hop based Multicast Ad hoc On-demand Distance Vector (MAODV) routing protocol, the minimum-link based Bandwidth-Efficient Multicast Routing Protocol (BEMRP) and our recently proposed non-receiver aware and receiver aware multicast extensions to the Location Prediction Based Routing (NR-MLPBR and R-MLPBR) protocols. Exhaustive simulation studies of these multicast routing protocols with DMEF and the default flooding as the route discovery strategies have been conducted. Performance results for each multicast routing protocol illustrate DMEF to be effective in discovering multicast trees that exist for a longer time with a lower energy consumed per node and without any appreciable increase in the hop count per source-receiver path. Povzetek: Predstavljeno je testiranje nove metode DMEF za iskanje stabilnih povezav v mobilnih omrezjih. 1 Introduction A mobile ad hoc network (MANET) is a dynamic distributed system of mobile, autonomous wireless nodes. The network has limited bandwidth and the nodes have limited battery charge. In order to conserve battery charge, each node has a limited transmission range (i.e., transmits the data signals only to a limited distance). As a result, MANET routes are typically multi-hop in nature. As nodes move independent of each other, routes between a source and destination node often break and new routes have to be discovered. MANET routing protocols are of two types. Proactive protocols require the nodes to periodically exchange the table updates to pre-determine routes between any pair of source-destination nodes. Reactive protocols determine routes only when a route is required from a source to a destination. In dynamically changing environments, typical of MANETs, reactive on-demand routing protocols incur lower control overhead to discover routes compared to the proactive routing protocols [5], In this paper, we work only with the reactive routing protocols. Flooding is the default route discovery approach for on-demand MANET routing protocols [14], The flooding algorithm to discover routes can be briefly explained as follows: Whenever a source node needs a route to a destination node, it broadcasts a Route Request (RREQ) message to its neighbours. Neighbour nodes of the source node broadcast the received RREQ further, if they have not already done so. A RREQ message for a particular route discovery process is forwarded by a node exactly once. The destination node receives the RREQs along several routes, selects the best route according to the route selection principles of the particular routing protocol and notifies the selected route to the source 166 Informatica 35 (2011 ) 165-184 N. Meglianathan through a Route-Reply (RREP) packet. The source starts sending data packets on the discovered route. Flooding is inefficient and consumes significantly high energy and bandwidth. When a node receives a message for the first time in its neighbourhood, at least 39% of the neighbourhood would have seen it already and on the average only 41% of the additional area could be covered with a rebroadcast [15], In an earlier work [11], we had proposed a novel density and mobility aware energy-efficient broadcast strategy, referred to as DMEF, to reduce the energy consumption in broadcast route discoveries by letting a node to broadcast only within a limited neighbourhood. The neighbourhood size to which a node advertises itself as part of the route discovery process is independently decided at the node based on the number of neighbours surrounding the node and the mobility of the node. The neighbourhood size for rebroadcast is reduced in such a way that the RREQ packets still make it to the destination through one or more paths with a reduced energy spent per route discovery and such paths are also more stable compared to those discovered using flooding. The effectiveness of DMEF has been so far studied only for MANET unicast [11] and multi-path routing protocols [12], In this paper, we study the impact of DMEF on the performance of MANET multicast routing protocols. Multicasting is the process of sending a stream of data from one source node to multiple recipients by establishing a routing tree, which is an acyclic connected subgraph of the entire network. The set of receiver nodes form the multicast group. While propagating down the tree, data is duplicated only when necessary. This is better than multiple unicast transmissions. Multicasting in ad hoc wireless networks has numerous applications [21]: collaborative and distributing computing like civilian operations, emergency search and rescue, law enforcement, warfare situations and etc. We investigate the minimum-hop based Multicast Ad hoc On-demand Distance Vector (MAODV) routing protocol [18], the minimum-link based Bandwidth-Efficient Multicast Routing Protocol (BEMRP) [16] and our recently proposed non-receiver aware and receiver aware multicast extensions to the Location Prediction Based Routing protocol [9], referred to as NR-MLPBR and R-MLPBR protocols [10] respectively. Exhaustive simulation studies of these multicast routing protocols with DMEF and the default flooding as the route discovery strategies have been conducted in this paper. Performance results for each multicast routing protocol illustrate DMEF to be effective in discovering multicast trees that exist for a longer time with a lower energy consumed per node and without any appreciable increase in the hop count per source-receiver path. The rest of the paper is organized as follows: Section 2 briefly describes the DMEF strategy. Section 3 reviews the multicast routing protocols studied. Section 4 discusses the simulation environment and presents the simulation results illustrating the effectiveness of DMEF vis-à-vis flooding. Section 5 reviews state-of-the-art related work on different optimal broadcast route discovery strategies proposed in the literature and discusses the advantages of DMEF and differences with related work. Section 6 concludes the paper and discusses future work. Throughout this paper, the terms 'path' and 'route', 'link' and 'edge', 'message' and 'packet' are used interchangeably. They mean the same. 2 DMEF strategy 2.1 Terminology and assumptions Every node (say node u) in the network is configured with a maximum transmission range (RangeMax)• the distance between two nodes is less than or equal to the maximum transmission range, the two nodes are said to be within the "complete neighbourhood" of each other. Each node broadcasts periodically a beacon message in its complete neighbourhood. The time between two successive broadcasts is chosen uniform-randomly, by each node from the range [0...Twait], Using this strategy, each node learns about the number of nodes in its complete neighbourhood. 2.2 Basic idea of DMEF The twin objectives of DMEF are to discover stable routes with a reduced energy consumption compared to that incurred using flooding. DMEF achieves this by considering the number of neighbours of a node (a measure of node density) and node mobility. The basic idea behind DMEF is as follows: The transmission range of a RREQ broadcast for route discovery is not fixed for every node. A node surrounded by more neighbours in the complete neighbourhood should broadcast the RREQ message only within a smaller neighbourhood that would be sufficient enough to pick up the message and forward it to the other nodes in the rest of the network. On the other hand, a node that is surrounded by fewer neighbours in the complete neighbourhood should broadcast the RREQ message to a larger neighbourhood (but still contained within the complete neighbourhood) so that a majority of the nodes in the complete neighbourhood can pick up the message and rebroadcast it further. A node rebroadcasts a RREQ message at most once. The density aspect of DMEF thus helps to reduce the unnecessary transmission and reception of broadcast RREQ messages and conserves energy. To discover stable routes that exist for a longer time, DMEF adopts the following approach: A node that is highly mobile makes itself available only to a smaller neighbourhood around itself, whereas a node that is less mobile makes itself available over a larger neighbourhood (but still contained within the complete neighbourhood). The reasoning is that links involving a slow moving node will exist for a longer time. Hence, it is better for a slow moving node to advertise itself to a larger neighbourhood so that the links (involving this node) that are part of the routes discovered will exist for a longer time. On the other hand, a fast moving node will have links of relatively longer lifetime with neighbours that are closer to it. Hence, it is worth to let a fast moving node advertise only to its nearby neighbours. PERFORMANCE COMPARISON STUDY OF MULTICAST. Informatica 35 (2011 ) 165-184 167 2.3 DMEF mathematical model DMEF effectively uses the knowledge of neighbourhood node density and mobility so that they complement each other in discovering stable routes in a more energy-efficient fashion. The transmission range used by a node M' Range,RREQ, to rebroadcast a RREQ message is given by the following model: Range RREQ _ = Range, Max I Neighborsu a (1) The idea behind the formulation of equation (1) is that the larger the value of the term, | Neighborsu a the lower would be the transmission range chosen by a node for broadcasting the RREQ message. For a fixed value of parameters a and (3, the above term in equation (1) could become larger for a node if it has a larger number of neighbours and/or is moving faster with a larger velocity. In order to make sure, RangemE® always greater than or equal to zero, the value of parameter a should be chosen very carefully. For a given value of parameter /;. the necessary condition is: a > I Neighbor s t A Rangei Max J (2) In practice, the value of a has to be sufficiently larger than the value obtained from (2), so that the RREQ message reaches neighbours who can forward the message further to the rest of the network. Otherwise, certain source-destination nodes may not be reachable from one another even though there may exist one or more paths between them in the underlying network. 2.4 Dynamic selection of DMEF parameter values The specialty of DMEF is that it allows for each node to dynamically and independently choose at run-time the appropriate values for the critical operating parameters a and /; depending on the perceived number of nodes in the complete neighbourhood of the node and the node's own velocity. A node has to be simply pre-programmed with the appropriate values of a and [1 to be chosen for different values of the number of nodes in the complete neighbourhood and node velocity. Let the maximum number of neighbours a node should have in order to conclude that the complete neighbourhood density of the node is low and moderate be represented respectively by maxNeighb lowDensity, maxNeighb modDensity. If a node has more than maxNeighb modDensity number of neighbours, then the node is said to exist in a complete neighbourhood of high density. Let lowDensitya, modDensitya and highDensitya represent the values of a to be chosen by a node for complete neighbourhoods of low, moderate and high density respectively. Let maxVel low Mobility, maxVeljnodMobility represent the maximum velocity values for a node in order to conclude that the mobility of the node is low and moderate respectively. If the velocity of a node is more than maxVeljnodMobility, then the mobility of the node is said to be high. Let lowMobilityJi, modMobilityJi and highMobility represent the values of [1 to be chosen by a node when its mobility is low, moderate and high respectively. Let Neighbors^and represent the set of neighbours in the complete neighbourhood and velocity of a node u at time t. Note that the set Neighborslu 's determined by node u based on the latest periodic beacon exchange in the complete neighbourhood formed by the maximum transmission range, RangeMax ■ The algorithm, DMEF Parameter Selection, to dynamically choose the values of parameters a and [1 (represented as and) is illustrated below in Figure 1: Input: Neighborship v 140 -i » 120 > 100 ■ 1 MAODV □ NR-MLPBR □ R-MLPBR B BEMRP 40 -20 - • irna , 8TTB, 2 4 8 12 24 # Receivers per Multicast Group Figure 9.8: 75 nodes, 30 m/s. MAODV ■ NR-MLPBR □ R-MLPBR S BEMRP 4 8 12 24 # Receivers per Multicast Group Figure 9.9: 75 nodes, 50 m/s. Figure 9: Average Energy Consumed per Node (Tree Discovery Procedure: DMEF). 25 to 50 nodes and from 25 to 75 nodes, the energy consumed per node decreases. For multicast group sizes of 8, 12 and 24, as we increase the network density from 25 nodes to 50 nodes, the increase in the energy consumed per node for MAODV, NR-MLPBR. R-MLPBR and BEMRP is by factors of 54%-157%, 53%-156%, 48%-136% and 38%-118% respectively. As we increase the network density from 25 nodes to 75 nodes, the increase in the energy consumed per node for MAODV, NR-MLPBR. R-MLPBR and BEMRP is by factors of 49%-173%, 47%-172%, 42%-146% and 27%-114% respectively. MAODV and NR-MLPBR incur a relatively larger energy consumed per node at high network densities due to the nature of these multicast routing protocols to discover trees with minimum hop count. R-MLPBR and BEMRP discover trees with reduced number of links and hence incur relatively lower energy consumed per node at high network density. For a given network density, the energy consumed per node due to flooding can be as large'as 5%-16%, 12%-23% and 22%-37% more than that incurred using DMEF in the presence of low, medium and high node mobility respectively. Impact of Multicast Group Size: As we increase the multicast group size from 2 to 24, the energy consumed per node for MAODV and NR-MLPBR increases by a factor of 2.2 to 2.4, 5.6 to 5.8 and 6.0 to 7.1 for low, medium and high density networks respectively. In the case of BEMRP and R-MLPBR, as we increase the multicast group size from 2 to 24, the energy consumed per node increases by a factor of 2.2 to 2.4, 4.9 to 5.4 and 4.8 to 6.4 in networks of low, medium and high density respectively. The increase in the energy consumed per node is below linear. Hence, all the four multicast routing protocols are scalable with respect to the increase in multicast group size. 4.6 Energy throughput For each of the multicast routing protocols and for a given network density and node mobility, the energy throughput decreases with increase in the multicast group size. This can be attributed to the need to spend more energy to deliver a given multicast packet to more receivers vis-a-vis few receivers. For a given network density and multicast group size, the energy throughput of a multicast routing protocol decreases slightly as the node velocity is increased from low to moderate and high. For a given multicast group size and node mobility, the energy throughput of a multicast routing protocol PERFORMANCE COMPARISON STUDY OF MULTICAST. Informatica 35 (2011 ) 165-184 179 decreases with increase in network density. This can be attributed to the involvement of several nodes (for larger network density) in distributing the offered traffic load to the multicast group. For a given simulation condition, the energy throughput of BEMRP is slightly larger than that of the other multicast routing protocols. This can be attributed to the lower energy consumed per node (and less number of links) for BEMRP. Performance with Flooding as the Tree Discovery Strategy • Impact of Node Mobility. As we increase the node mobility, the energy throughput for a multicast protocol reduces as large as by 8%-12%, 12%-17% and 24%-26% in low, moderate and high density networks respectively. For a given network density. I MAODV □ NR-MLPBR □ R-MLPBR B BEMRP NR-MLPBR □ R-MLPBR a BEMRP 1 MAODV □ NR-MLPBR □ R-MLPBR E BEMRP 4 8 12 # Receivers per Multicast Group Figure 10.1: 25 nodes, 10 m/s. 2 4 8 12 24 # Receivers per Multicast Group Figure 10.2: 25 nodes, 30 m/s. 4 8 12 # Receivers per Multicast Group Figure 10.3: 25 nodes, 50 m/s. MAODV □ NR-MLPBR □ R-MLPBR B BEMRP 2 4 8 12 24 # Receivers per Multicast Group Figure 10.4: 50 nodes, 10 m/s. 4 8 12 # Receivers per Multicast Group Figure 10.5: 50 nodes, 30 m/s. .irfl.mm. 2 4 8 12 24 # Receivers per Multicast Group Figure 10.6: 50 nodes, 50 m/s. MAODV □ NR-MLPBR □ R-MLPBR B BEMRP 2 4 8 12 24 # Receivers per Multicast Group Figure 10.7: 75 nodes, 10 m/s. 4 8 12 # Receivers per Multicast Group Figure 10.8: 75 nodes, 30 m/s. 2 4 8 12 24 # Receivers per Multicast Group Figure 10.9: 75 nodes, 50 m/s. Figure 10: Energy Throughput: # Packets Delivered per Joule (Tree Discovery Procedure: Flooding). the reduction in the energy throughput with increase in node mobility is due to the relatively larger amount of energy spent for broadcast tree discoveries. Impact of Network Density. The decrease in energy throughput with increase in network density is more for MAODV and NR-MLPBR, relatively lower for R-MLPBR and is the least for BEMRP. At network density of 50 nodes, the energy throughput of MAODV and NR-MLPBR is 45%-64% and that of R-MLPBR and BEMRP is 50%-65% of that observed at network density of 25 nodes. At network density of 75 nodes, the energy through of MAODV, NR-MLPBR, R-MLPBR and BEMRP is 29%-48%, 30%-50%, 33%-50% and 38%-50% of that observed at network density of 25 nodes. Impact of Multicast Group Size: As the multicast group size is increased from 2 to 4, the energy throughput of the multicast routing protocols decreased by 30%-40%, 36%-40% and 24%-45% in networks of low, moderate and high density respectively. As the multicast group size is increased from 2 to 24, the energy throughput of the multicast routing protocols decreased by about 78%, 83% and 85% in networks of low, moderate and high density respectively. Performance with DMEF as the Tree Discovery Strategy • Impact of Node Mobility. As we increase the node mobility from low to moderate and high, the energy throughput for a multicast routing protocol reduces as large as by 7%-8%, 8%-12% and 16%-17% in networks of low, moderate and high density respectively. The relatively higher energy throughput while using DMEF can be attributed to the tendency of the broadcast strategy to involve only relatively slow moving nodes to be part of the trees. As a result, less energy consumed for broadcast tree discoveries. • Impact of Network Density. The decrease in energy throughput with increase in network density is more for MAODV and NR-MLPBR, relatively lower for R-MLPBR and is the least for BEMRP. At network density of 50 nodes, the energy throughput of MAODV, NR-MLPBR, R-MLPBR and BEMRP is 48%-63%, 47%-63%, 52%-64% and 58%-69% of that observed at network density of 25 nodes. At 180 Informatica 35 (2011 ) 165-184 N. Meglianathan network density of 75 nodes, the energy through of MAODV, NR-MLPBR, R-MLPBR and BEMRP is 32%-47%, 32%-48%, 36%-48% and 42%-50% of that observed at network density of 25 nodes. Impact of Multicast Group Size: As the multicast group size is increased from 2 to 4, the energy throughput of the multicast routing protocols decreased by 36%-44%, 35%-45% and 30%-47% in networks of low, moderate and high density respectively. As the multicast group size is increased from 2 to 24, the energy throughput of the multicast routing protocols decreased by about 80%, 84% and 84% in networks of low, moderate and high density respectively. 4.7 Energy consumed per tree discovery For a given broadcast strategy, the energy consumed per tree discovery is the same for all of the four multicast I MAODV □ NR-MLPBR □ R-MLPER B BEMRP MAODV ■ NR-MLPBR □ R-MLPBR □ BEMRP I! MAODV □ NR-MLPBR □ R-MLPBR S BEMRP 2 4 8 12 24 # Receivers per Multicast Group Figure 11.1: 25 nodes, 10 m/s. 2 4 8 12 24 # Receivers per Multicast Group Figure 11.2: 25 nodes, 30 m/s. 2 4 8 12 24 # Receivers per Multicast Group Figure 11.3: 25 nodes. 50 m/s. MAODV D NR-MLPBR □ R-MLPBR S BEMRP m MAODV n NR-MLPBR n R-MLPBR ta BEMRP MAODV □ NR-MLPBR □ R-MLPBR B BEMRP jicfllUii, 2 4 8 12 24 # Receivers per Multicast Group Figure 11.4: 50 nodes, 10 m/s. 4 8 12 # Receivers per Multicast Group Figure 11.5: 50 nodes, 30 m/s. 2 4 8 12 # Receivers per Multicast Group Figure 11.6: 50 nodes, 50 m/s. H MAODV □ NR-MLPBR □ R-MLPBR S BEMRP ITU MAODV n NR-MLPBR n R-MLPBR m BEMRP H MAODV □ NR-MLPBR □ R-MLPBR S BEMRP 4 8 12 # Receivers per Multicast Group Figure 11.7: 75 nodes, 10 m/s. 2 4 8 12 # Receivers per Multicast Group Figure 11.8: 75 nodes, 30 m/s. 2 4 8 12 # Receivers per Multicast Group Figure 11.9: 75 nodes, 50 m/s. Figure 11: Energy Throughput: # Packets Delivered per Joule (Tree Discovery Procedure: DMEF). routing protocols. For both flooding and DMEF, the energy consumed increases with increase in network density, attributed to the involvement of multiple nodes in the broadcast of the MTRMs. In low-density networks, the energy consumed per tree discovery using flooding is 10-22%,' 19-35% and 14-20% more than that of the energy consumed per tree discovery using DMEF in low, moderate and high node mobility conditions respectively. In moderate density networks, the energy consumed per tree discovery using flooding is about 15%, 23% and 28% more than that of the energy consumed per tree discovery using DMEF in low, moderate and high node mobility conditions respectively. In high-density networks, the energy' consumed per tree discovery using flooding is about 18%, 30% and 37% more than the energy consumed per tree discovery using DMEF. As observed, DMEF performs better than flooding with increase in network density and/or node mobility. E 3 W c o o > u> ® c Uj For a given multicast group size, the energy consumed while using flooding in moderate (50 nodes) and high density (75 nodes) networks is respectively about 3.8 and 8 times more than that incurred in networks of low density. This indicates that as the number of nodes is increased by x times (x = 2 for moderate density and x = 3 for high density), the energy consumed due to flooding increases by 2X times. In the case of DMEF, for a given multicast group size, the energy consumed in moderate density networks is about 3.7, 3.5 and 3.2 times more than that observed in low Flood-10 □ DMEF-10 □ Flood-30 □ DMEF-30 I ">.0.15 - 5 0.12 3 0.09 1» 5 0.06 I Flood-50 □ DMEF-50 2 4 8 12 24 # Receivers per Multicast Group Figure 12: Energy Consumed per Broadcast Tree Discovery: Flooding vs. DMEF (25 Nodes). PERFORMANCE COMPARISON STUDY OF MULTICAST. Informatica 35 (2011 ) 165-184 181 density networks for low, moderate and high node mobility conditions respectively. For a given multicast group size, the energy consumed during DMEF in high-density networks is about 7.8, 7.2 and 6.6 times more than that observed in low-density networks for low, moderate and high node mobility conditions respectively. Thus, the energy consumed while using DMEF does not increase exponentially as observed for flooding. DMEF performs appreciably well in lowering the energy consumed per tree discovery with increase in node mobility and/or increase in network density. G] Flood-10 □ DMEF-10 O Flood-30 □ DMEF-30 ■ Flood-50 □ DMEF-50 13 70.55 -| 4> > n £ ffl 0.44 - - « g 0.33 ■ o « O 5 0.22 ■ > rtj D) ® 0.11 - - 2 4 8 12 24 # Receivers per Multicast Group Figure 13: Energy Consumed per Broadcast Tree Discovery: Flooding vs. DMEF (50 Nodes). 5 Survey of MANET broadcast route discovery strategies We surveyed the literature for different broadcast route discovery strategies proposed to reduce the route discovery overhead and we describe below the strategies relevant to the research conducted in this paper. In Section 5.3, we qualitatively analyse the advantages of our DMEF broadcast strategy compared to the broadcast strategies described below in Sections 5.1 and 5.2. 5.1 Reliable route selection (RRS) Algorithm In [20], the authors proposed a Reliable Route Selection (referred to as RRS) algorithm based on Global Positioning System (GPS) [8], The RRS algorithm divides the circular area formed by the transmission range of a node into two zones: stable zone and caution zone. A node is said to maintain stable links with the neighbour nodes in its stable zone and maintain unstable links with the neighbour nodes lying in its caution zone. If R is the transmission range of a node, then the radius of the stable zone is defined as r = R-8S where S is the velocity of the node. The status zone is a circular region (with its own centre) inscribed inside the circular region formed by the transmission range of the node. The centre of the status zone need not be the centre of the circular region forming the transmission range of the node, but always lies in the direction of movement of the node. RRS works as follows: The Route-Request (RREQ) message of a broadcast route discovery process includes the co-ordinates representing the current position of the transmitter of the RREQ message, the co-ordinates representing the centre of the stable zone of the transmitter, the value of parameter 8 to be used by an intermediate node and the stable zone radius of the transmitter of the message. The source node of the route discovery process broadcasts the RREQ message in the complete neighbourhood formed by the transmission range R. The RRS-related fields are set to initial values corresponding to the source node. An intermediate node receiving the RREQ message broadcasts the message further, only if the node lies in the stable zone of the transmitter. If a route discovery attempt based on a set value of 8 is unsuccessful, the source node decrements the value of 8 and launches another global broadcast based route discovery. This process is continued (i.e., the value of 8 decremented and global broadcast reinitiated) until the source finds a path to the destination. If the source cannot find a route to the destination even while conducting route discovery with 8 set to zero, then the source declares that the destination is not connected to it. 5.2 Probability, counter, area and neighbour-knowledge based methods In [15], the authors propose several broadcast route discovery strategies that could reduce the number of retransmitting nodes of a broadcast message. These strategies can be grouped into four families: probability-based, counter-based, area-based and neighbour-knowledge based methods: (i) Probability-based method: When a node receives a broadcast message for the first time, the node rebroadcasts the message with a certain probability. If the message received is already seen, then the node drops the message irrespective of whether or not the node retransmitted the message when it received the message for the first time. (ii) Counter-based method: When a node receives a broadcast message for the first time, it waits for a certain time before retransmitting the message. During this broadcast-wait-time, the node maintains a counter to keep track of the number of redundant broadcast messages received from some of its other neighbours. If this counter value exceeds a threshold within the broadcast-wait-time, then the node decides to drop the message. Otherwise, the node retransmits the message. (iii) Area-based method: A broadcasting node includes its location information in the message header. The receiver node calculates the additional coverage area obtained if the message were to be rebroadcast. If the additional coverage area is less than a threshold ID Flood-10 □ DMEF-10 □ Flood-30 □ DMEF-30 □ Flood-50 □ DMEF-50 „7.1-10 1 5 0.88 3 > » § 0.66 o u> O 5 0.44 | ® 0.22 0) |Z c Z 0.00 mi o> a 2 4 8 12 24 # Receivers per Multicast Group Figure 14: Energy Consumed per Broadcast Tree Discovery: Flooding vs. DMEF (75 Nodes). 182 Informatica 35 (2011 ) 165-184 N. Meglianathan value, all future receptions of the same message will be dropped. Otherwise, the node starts a broadcast-wait-timer. Redundant broadcast messages received during this broadcast-wait-time are also cached. After the timer expires, the node considers all the cached messages and recalculates the additional coverage area if it were to rebroadcast the particular message. If the additional obtainable coverage area is less than a threshold value, the cached messages are dropped. Otherwise, the message is rebroadcast. (iv) Neighbour-knowledge based method: This method requires nodes to maintain a list of 1-hop neighbours and 2-hop neighbours, learnt via periodic beacon exchange. Using these lists, a node calculates the smallest set of 1-hop neighbours required to reach all the 2-hop neighbours. The minimum set of 1-hop neighbours that will cover all of the 2-hop neighbours is called the Multi Point Relays (MPRs). 5.3 Advantages of DMEF and differences with related work The DMEF strategy is very effective in discovering relatively long-living routes in an energy-efficient manner and differs from the RRS algorithm in the following ways: • RRS is highly dependent on location-service schemes like GPS, while DMEF is not dependent on any location-service scheme. • RRS requires the RREQ message header to be changed while DMEF does not require any change in the structure of the RREQ messages used for broadcasting. DMEF can be thus used without requiring any change in a MANET routing protocol. • In RRS, a node lying in the stable zone of the transmitter of the RREQ rebroadcasts the message in its complete neighbourhood. However, it is only the recipient nodes in the stable zone of the transmitter that rebroadcast the RREQ. Hence, RRS is not energy-efficient. In DMEF, the transmission range for broadcast at a node is dynamically and locally determined using the node's velocity and neighbourhood density and is usually considerably less than the maximum transmission range. • RRS does not properly handle the scenario where the value of d*S exceeds the transmission range, R. of the node. The value of d has to be iteratively reduced (by trial and error) to determine the connectivity between the source and destination nodes. DMEF is better than RRS because it requires only one broadcast route discovery attempt from the source to determine a route to the destination if the two nodes are indeed connected. The values of the DMEF parameters are dynamically determined at each node by the nodes themselves because a node knows better about its own velocity and neighbourhood, compared to the source of the broadcast process. • The network density does not influence the stable zone radius selected by RRS. In RRS, the number of nodes retransmitting the RREQ message in a neighbourhood increases significantly as the network density is increased. DMEF is quite effective in reducing the number of nodes retransmitting the RREQ message in high-density networks. The advantages of the DMEF scheme when compared with the broadcast route discovery strategies discussed in Section 5.2 are summarized as follows: • The probability and MPR-based methods do not guarantee that the broadcast message will be routed on a path with the minimum hop count or close to the minimum hop count. Previous research [13] on the impact of these broadcast strategies on the stability and hop count of DSR routes indicates that the hop count of the paths can be far more than the minimum and the routes have a smaller lifetime than the paths discovered using flooding. The probability-based method cannot always guarantee that the RREQ message gets delivered to the destination. Also, with increase in network density, the number of nodes retransmitting the message increases for both the probability-based and MPR-based methods. DMEF determines paths with hop count being close to that of the minimum hop count paths and such paths have a relatively larger lifetime compared to those discovered using flooding. DMEF almost always guarantees that a source-destination route is discovered if there is at least one such route in the underlying network. DMEF effectively controls the RREQ message retransmission overhead as the network density increases. • The counter and area-based methods require careful selection of the threshold values for their proper functioning. Each node has to wait for a broadcast-wait-time before retransmitting the message. This can introduce significant route acquisition delays. The area-based method also requires the nodes to be location-aware and include the location information in the broadcast messages. With DMEF, there is no waiting time at a node to rebroadcast a received RREQ message, if the message has been received for the first time during a particular route discovery. DMEF does not depend on any location-aware services for its operation and the structure of the RREQ message need not be changed. 5.4 Other relevant optimizations for multicast routing overhead In addition to the methods described in Sections 5.1 and 5.2, some of the other optimizations that have been proposed in the MANET literature include: (i) A Swarm Intelligence based multicast routing protocol for ad hoc networks (MANHSI) has been proposed in [1]; (ii) In [19], the authors propose an independent tree ad hoc multicast routing (ITAMAR) framework that includes a number of heuristics to compute a set of alternate trees to improve the mean time between interruptions in multicast communication, achieved with a small increase in the route discovery overhead; and (iii) A virtual PERFORMANCE COMPARISON STUDY OF MULTICAST. Informatica 35 (2011 ) 165-184 183 overlay mesh of unicast paths has been proposed for efficient discovery of multicast routes in [7], 6 Conclusions and future work Simulations have been conducted with both flooding and DMEF as the broadcast tree discovery strategies. DMEF helps the multicast routing protocols to discover stable trees and at the same time does not increase the source-receiver hop count appreciably. Hence, the energy consumed per node with DMEF is lower than that incurred with flooding. With the use of DMEF as the tree discovery strategy, the performance of NR-MLPBR and R-MLPBR with respect to the time between successive tree discoveries and energy consumed per node actually improved relatively more than that observed for BEMRP and MAODV. This can be attributed to the effective path prediction of the two multicast extensions, an idea inherited from LPBR, and complemented by DMEF. Thus, DMEF has been demonstrated to be an effective broadcast strategy to discover multicast trees. In a related work [12], we have also demonstrated the effectiveness of DMEF to discover node-disjoint multi-path routes for MANETs. Thus, DMEF is an effective broadcast strategy to discover stable unicast, multicast and multi-path routes for MANETs with relatively lower energy consumption than the default flooding approach. The related work listed in Sections 5.1 and 5.4 require the strategies to be embedded into the design of the protocols and require changes built-in to the route discovery procedure of the protocols. Ours is the first such effort to study the impact of protocol-independent broadcast strategies (like DMEF and flooding) on the performance of multicast routing protocols. In future, we will evaluate the impact of the probability, counter, area and neighbour-knowledge based methods on the performance of the multicast routing protocols. Acknowledgments Research was sponsored by the U. S. Army Research Laboratory and was accomplished under Cooperative Agreement Number W911NF-08-2-0061. The views and conclusions in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Laboratory or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein. References [1] Z. M. Alfawaer, H. W. Hua and N. Ahmed, "A Novel Multicast Routing Protocol for Mobile Ad Hoc Networks," American Journal of Applied Sciences, vol. 4, no. 5, pp. 333-338, 2007. [2] C. Bettstetter, H. Hartenstein and X. Perez-Costa, "Stochastic Properties of the Random-Waypoint Mobility Model," Wireless Networks, vol. 10, no. 5, pp. 555-567, 2004. [3] G. Bianchi, "Performance Analysis of the IEEE 802.11 Distributed Coordination Function," IEEE Journal of Selected Areas in Communication, vol. 18, no. 3, pp. 535-547, 2000. [4] L. Breslau et. al, "Advances in Network Simulation," IEEE Computer, vol. 33, no. 5, pp. 5967, May 2000. [5] J. Broch, D. A. Maltz, D. B. Johnson, Y. C. Hu and J. Jetcheva, "A Performance of Comparison of Multi-hop Wireless Ad hoc Network Routing Protocols," Proceedings of the 4th Annual ACM/IEEE Conference on Mobile Computing and Networking, pp. 85-97, October 1998. [6] L. M. Feeney, "An energy-consumption model for performance analysis of routing protocols for mobile ad hoc networks," Journal of Mobile Networks and Applications, vol. 3, no. 6, pp. 239249, June 2001. [7] C. Gui and P. Mohapatra, "Overlay Multicast for MANETs using Dynamic Virtual Mesh," Wireless Networks, vol. 13, no. 1, pp. 77-91, 2007. [8] B. Hofmann-Wellenhof, H. Lichtenegger and J. Collins, Global Positioning System: Theory and Practice, 5th rev. ed., Springer, September 2004. [9] N. Meghanathan, "A Location Prediction Based Reactive Routing Protocol to Minimize the Number of Route Discoveries and Hop Count per Path in Mobile Ad hoc Networks," The Computer Journal, Vol. 52, No. 4, pp. 461-482, July 2009. [10] N. Meghanathan, "Multicast Extensions to the Location Prediction Based Routing Protocol for Mobile Ad hoc Networks," ISAST Transactions on Computers and Intelligent Systems, vol. 1, no. 1, pp. 56-65, August 2009. [11] N. Meghanathan, "A Density and Mobility Aware Energy-efficient Broadcast Route Discovery Strategy for Mobile Ad hoc Networks," International Journal of Computer Science and Network Security, vol. 9, no. 11, pp. 15-24, November 2009. [12] N. Meghanathan, "A Node-Disjoint Multi-path Extension of the Location Prediction Based Routing Protocol for Mobile Ad hoc Networks," Proceedings of the 3rd International Conference on Signal Processing and Communication Systems, Omaha, Nebraska, USA, September 28-30, 2009. [13] N. Meghanathan, "Impact of Broadcast Route Discovery Strategies on the Performance of Mobile Ad Hoc Network Routing Protocols," in Proceedings of the International Conference on High Performance Computing, Networking and Communication Systems, pp. 144-151, July 2007. [14] C. S. R. Murthy and B. S. Manoj, "Ad Hoc Wireless Networks: Architectures and Protocols," Prentice Hall, June 2004. [15] S. Ni, Y. Tseng, Y. Chen and J. Sheu, "The Broadcast Storm Problem in a Mobile Ad Hoc Network," Proceedings of ACM International Conference on Mobile Computing and Networking, pp. 151-162, 1999. 184 Informatica 35 (2011 ) 165-184 N. Meglianathan [16] T. Ozaki, J-B. Kim and T. Suda, "Bandwidth-Efficient Multicast Routing for Multihop, Ad hoc Wireless Networks," Proceedings of the IEEE INFO.COM Conference, vol. 2, pp. 1182-1192, Anchorage, USA, April 2001. [17] C. E. Perkins and E. M. Royer, "The Ad hoc On-demand Distance Vector Protocol," Ad hoc Networking, edited by C. E. Perkins, pp. 173-219, Addison-Wesley, 2000. [18] 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. [19] S. Sajama and Z. J. Haas, "Independent-tree Ad hoc Multicast Routing (ITAMAR)," Mobile Networks and Applications, vol. 8, no. 5, pp. 551-566, October 2003. [20] Y.-J. Suh, W. Kim and D.-H. Kwon, "GPS-Based Reliable routing Algorithms for Ad Hoc Networks," The Handbook of Ad Hoc Wireless Networks, pp. 361 -374, CRC Press, 2003. [21] C. K. Toh, G. Guichal and S. Bunchua, "ABAM: On-demand Associatvity-based Multicast Routing for Ad hoc Mobile Networks," in Proceedings of the 52nd IEEE VTS Fall Vehicular Technology Conference, Vol. 3, pp. 987 - 993, September 2000.