Building multicast trees in ad-hoc networks

ABSTRACT

Multicast trees are used in a variety of applications, such as publish/subscribe systems or content distribution networks. Existing algorithms for ad-hoc networks typically produce multicast trees requiring many nodes to act as relays even though they are not part of the multicast group. In this paper, we propose an algorithm for building efficient multicast trees that strives to minimize the number of non-member relay nodes and the number of transmissions required to reach all the group members, and to balance the degree of members when acting as internal nodes of the multicast tree. Our algorithm relies upon a lightweight distributed hash table (DHT) to construct and optimize the multicast trees. We evaluate the efficiency and scalability of our algorithm by simulations with various network configurations and sizes.

REFERENCES

• 1: Filipe Araujo , Luus Rodrigues , Jorg Kaiser , Changling Liu , Carlos Mitidieri, CHR: A Distributed Hash Table for Wireless Ad Hoc Networks, Proceedings of the Fourth International Workshop on Distributed Event-Based Systems (DEBS) (ICDCSW'05), p.407-413, June 06-10, 2005 [doi>10.1109/ICDCSW.2005.48]
• 2: Nuno Carvalho , Filipe Araujo , Luis Rodrigues, Reducing Latency in Rendezvous-Based Publish-Subscribe Systems for Wireless Ad Hoc Networks, Proceedings of the 26th IEEE International ConferenceWorkshops on Distributed Computing Systems, p.28, July 04-07, 2006 [doi>10.1109/ICDCSW.2006.89]
• 3: Franca Delmastro, From Pastry to CrossROAD: CROSS-Layer Ring Overlay for AD Hoc Networks, Proceedings of the Third IEEE International Conference on Pervasive Computing and Communications Workshops, p.60-64, March 08-12, 2005 [doi>10.1109/PERCOMW.2005.38]
• 4: V. Devarapalli and D. Sidhu. MZR: a multicast protocol for mobile ad hoc networks. volume 3, pages 886--891, 2001.
• 5: Z. Haas. A new routing protocol for the reconfigurable wireless networks. In IEEE 6th International Conference on Universal Personal Communications Record, volume 2, pages 562--566, San Diego, CA, USA, 1997.
• 6: Philippe Jacquet , Georgios Rodolakis, Multicast Scaling Properties in Massively Dense Ad Hoc Networks, Proceedings of the 11th International Conference on Parallel and Distributed Systems - Workshops, p.93-99, July 20-22, 2005
• 7: R. Kummer, P. Kropf, and P. Felber. Distributed lookup in structured peer-to-peer ad-hoc networks. In R. Meersman and Z. Tari, editors, On the Move to Meaningful Internet Systems 2006: CoopIS, DOA, GADA, and ODBASE, volume 4276 of Lecture Notes in Computer Science, pages 1541--1554. Springer Berlin / Heidelberg, 2006.
• 8: Andrea Passarella , Franca Delmastro , Marco Conti, XScribe: a stateless, cross-layer approach to P2P multicast in multi-hop ad hoc networks, Proceedings of the 1st international workshop on Decentralized resource sharing in mobile computing and networking, July 25-25, 2006, Los Angeles, California [doi>10.1145/1161252.1161255]
• 9: C. E. Perkins and E. M. Royer. Ad-hoc on-demand distance vector routing. MILCOM '97, 1997.
• 10: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 11: Antony I. T. Rowstron , Anne-Marie Kermarrec , Miguel Castro , Peter Druschel, SCRIBE: The Design of a Large-Scale Event Notification Infrastructure, Proceedings of the Third International COST264 Workshop on Networked Group Communication, p.30-43, November 07-09, 2001
• 12: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

Keywords:
MANETs, ad-hoc wireless networks, mobile ad-hoc computing, mobile networking, multicast trees, wireless networks protocol