An Adaptive Redundancy Protocol for Mesh Based Multicasting - eScholarship (2005)

An Adaptive Redundancy Protocol for Mesh Based Multicasting Ravindra Vaishampayan Department of Computer Science University of California Santa Cruz Santa Cruz, CA 95064 ravindra@soe.ucsc.edu J.J. Garcia-Luna-Aceves Department of Computer Engineering Palo Alto Research Center University of California Santa Cruz 3333 Coyote Hill Road Santa Cruz, CA 95064 Palo Alto, CA 94304 jj@soe.ucsc.edu Katia Obraczka Department of Computer Engineering University of California Santa Cruz Santa Cruz, CA 95064 katia@soe.ucsc.edu Abstract— Mesh-based multicast routing protocols for multi-hop wireless ad hoc networks (MANETs) build multiple paths from senders to receivers. Higher redundancy results in higher reliability because packets can be delivered even in the presence of links breaking. However, in less dynamic environments, in which links break less frequently, the additional redundancy may not be needed in terms reliability and may significantly increase overhead. This paper investigates the tradeoffs between reliability and efficiency in mesh- based multicast protocols for MANETs. We introduce an adaptive mesh-based multicast mechanism that controls mesh redundancy based on link lifetime. Mesh redundancy is measured by the number of paths from each receiver to the core of the group’s mesh, which serves as the address of the group. Through simulations, we compare the performance of the adaptive mesh-building protocol against the non-adaptive version (which builds the mesh with maximum redundancy), and against ODMRP for a wide range of scenarios with varying mobility, group members, number of senders, traffic load, number of multicast groups and terrain size. Our results show that adjusting mesh redundancy based on link lifetime can maintain high packet delivery ratios with less overhead compared to non-adaptive mesh-based multicast protocols. Keywords— Ad hoc networks, routing, multicasting, multicast mesh, multicast tree. I. I NTRODUCTION The objective of a multicast routing protocol for mobile ad hoc networks (MANETs) is to support the dissemination of information from a sender to all multicast group members while trying to use the available bandwidth efficiently in the presence of frequent topology changes. In MANETs, node mobility and the fact that wireless links are more prone to transmission errors result in higher packet drop probability when compared to wired networks. Therefore, multicast routing protocols that provide route redundancy (i.e., routing packets along multiple paths from source to receivers), typically outperformed multicast routing mechanisms that offer no redundancy. Based on this observation, numerous MANET multicast protocols that provide route redundancy by building a mesh connecting senders to receivers have been proposed including [1], [2], [3], [4], [5]. Section II describes this prior work. Because MANET nodes typically have limited power, processing, storage, and commu- nication capabilities, redundancy can incur significant overhead in these resource-constrained networks, even though it provides higher packet delivery ratios. 1 This work was supported in part by the Jack Baskin Chair of Computer Engineering at UCSC and by the National Science Foundation under grant CNS-0435522 The contributions of this paper are two-fold. First, in Section III, we introduce an adaptive mesh-based multicast mechanism that controls mesh redundancy based on link lifetime. This is moti- vated by experimental results showing that the impact of redun- dancy is directly correlated to the lifetime of network links. In other words, when link lifetime is high, having larger redundancy in the network does not significantly increase packet delivery ratio. However, when links are more volatile, having greater redundancy has considerable impact on reliability. The proposed adaptive mesh-based multicast mechanism con- trols mesh redundancy based on link lifetime. It elects a core and every node in the network knows its distance to the core based on multicast announcements exchanged periodically by every node. Neighbors of a node with a shorter distance to the core are considered its parents. Mesh redundancy is measured by the number of paths from each receiver to the mesh’s core. Every node in the network estimates link lifetime and redundancy in its neighborhood as described in Section III-F. Mesh redundancy is increased as link lifetime decreases. The process of mesh building is receiver initiated. If the measured redundancy is too low for the measured link lifetime, a receiver increases the number of parents it includes in the mesh. Similarly, if the measured redundancy is too high for the measured link lifetime, the number of parents which are included in the mesh are reduced. If the measured redundancy is within the permissible range for the measured link lifetime, then the number of parents included in the mesh is left unchanged. The other contribution of the paper is to investigate the trade- offs between reliability and efficiency in mesh-based MANET multicast protocols. To this end, we compare the performance of adaptive mesh-based multicast against its non-adaptive version and ODMRP [3] in Section IV, a widely-known mesh-based MANET multicast protocol. Through extensive simulations using a wide range of MANET scenarios with varying mobility, traffic load, group members, number of senders, number of multicast groups and terrain size, we show that adjusting mesh redundancy based on link lifetime can maintain high packet delivery ratios at higher protocol efficiency when compared to non-adaptive mesh- based multicast protocols. II. R ELATED W ORK As many of the possible applications for ad hoc networks e.g. battlefield scenarios, search and rescue operations, policing, firefighting etc. have the need for one to many communication,