Abstract
Several multicast protocols for mobile ad hoc networks (MANETs) have been proposed that build multicast trees using location information available from GPS or localization algorithms and use geographic forwarding to forward packets down the multicast trees. These stateless multicast protocols carry encoded membership, location and tree information in each packet. Stateless protocols are more efficient and robust than stateful protocols (ADMR, ODMRP) as they avoid the difficulty of maintaining distributed states in the presence of frequent topology changes in MANETs. However, stateless locationbased multicast protocols are not scalable to large groups because they encode group membership in the header of each data packet, i.e. they incur a per-packet encoding overhead. Additionally, such protocols involve centralized group membership and location management, either at the tree root or the traffic source. In this work, we present the Hierarchical Rendezvous Point Multicast (HRPM) protocol which significantly improves the scalability of stateless location-based multicast with respect to the group size. HRPM incorporates two key design ideas: (1) hierarchical decomposition of multicast groups, and (2) use of distributed geographic hashing to construct and maintain such a hierarchy efficiently. HRPM organizes a large group into a hierarchy of recursively organized manageable-sized subgroups in an effort to reduce per-packet encoding overhead. More importantly, HRPM constructs and maintains this hierarchy at virtually no cost using distributed hashing; distributed hashing is recursively applied at each subgroup for group management and avoids the potentially high cost associated with maintaining distributed state at mobile nodes. The hierarchical organization and the distributed hashing property also allows HRPM to scale to large networks and large numbers of groups. Performance results obtained via detailed simulations demonstrate that HRPM achieves enhanced scalability and performance. Coupled with its leverage of stateless geographic forwarding, HRPM scales well in terms of the group size, the number of groups, the number of sources, as well as the size of the network. In particular, HRPM maintains close to 95% multicast delivery ratio while incurring on average 5.5% per packet tree-encoding overhead for up to 250 group members in a 500-node network. Furthermore, it achieves a steady 95% delivery ratio while incurring nearly constant overhead as the number of groups increases from 2 to 45, while keeping the total number of receivers constant at 180, in a 500-node network. Lastly, it steadily achieves above 90% delivery ratio as the network scales up to 1000 nodes with up to 30% group members. As a reference, we also compared HRPM to ODMRP, a state-of-the-art topology-based multicast protocol that is scalable to large groups. HRPM performs comparably to ODMRP across a wide range of group sizes. More over, HRPM outperforms ODMRP when the network size, the number of groups, or the number of sources increases.
Keywords
Simulations, location based multicast, MANETs, scalability, distributed hashing.
Date of this Version
May 2006