Comparison of broadcasting techniques for mobile ad hoc networks

ABSTRACT

Network wide broadcasting in Mobile Ad Hoc Networks provides important control and route establishment functionality for a number of unicast and multicast protocols. Considering its wide use as a building block for other network layer protocols, the MANET community needs to standardize a single methodology that efficiently delivers a packet from one node to all other network nodes. Despite a considerable number of proposed broadcasting schemes, no comprehensive comparative analysis has been previously done. This paper provides such analysis by classifying existing broadcasting schemes into categories and simulating a subset of each, thus supplying a condensed but comprehensive side by side comparison.The simulations are designed to pinpoint, in each, specific failures to network conditions that are relevant to MANETs, e.g., bandwidth congestion and dynamic topologies. In addition, protocol extensions using adaptive responses to network conditions are proposed, implemented and analyzed for one broadcasting scheme that performs well in the comparative study.

REFERENCES

• 1: J. Boleng. Normalizing mobility characteristics and enabling adaptive protocols for ad hoc networks. In Proceedings of the IEEE Local and Metropolitan Area Networks Workshop (LANMAN), pages 9--12, 2001.
• 2: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 3: T. Camp, J. Boleng, B. Williams, L. Wilcox, and W. Navidi. Performance evaluation of two location based routing protocols. In Proceedings of INFOCOM, 2002. To appear.
• 4: T. Clausen, P. Jacquet, A. Laouiti, P. Minet, P. Muhlethaler, A. Qayyum, and L. Viennot. Optimized link state routing protocol. Internet Draft: draft-ietf-manet-olsr-06.txt, September 2001.
• 5: I. S. Committee. Wireless LAN medium access control (MAC) and physical layer (PHY) specifications. In IEEE 802.11 Standard. IEEE, New York, 1997. ISBN 1-55937-935-9.
• 6: Sudipto Guha , Samir Khuller, Approximation Algorithms for Connected Dominating Sets, Proceedings of the Fourth Annual European Symposium on Algorithms, p.179-193, September 25-27, 1996
• 7: Christopher Ho , Katia Obraczka , Gene Tsudik , Kumar Viswanath, Flooding for reliable multicast in multi-hop ad hoc networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.64-71, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313291]
• 8: J. Jetcheva, Y. Hu, D. Maltz, and D. Johnson. A simple protocol for multicast and broadcast in mobile ad hoc networks. Internet Draft: draft-ietf-manet-simple-mbcast-01.txt, July 2001.
• 9: Hyojun Lim , Chongkwon Kim, Multicast tree construction and flooding in wireless ad hoc networks, Proceedings of the 3rd ACM international workshop on Modeling, analysis and simulation of wireless and mobile systems, p.61-68, August 20-20, 2000, Boston, Massachusetts, United States [doi>10.1145/346855.346865]
• 10: L. Lovasz. On the ratio of optimal integral and fractional covers. Discrete Mathematics, 1975.
• 11: Sze-Yao Ni , Yu-Chee Tseng , Yuh-Shyan Chen , Jang-Ping Sheu, The broadcast storm problem in a mobile ad hoc network, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.151-162, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313525]
• 12: W. Peng and X. Lu. Efficient broadcast in mobile ad hoc networks using connected dominating sets. Journal of Software - Beijing, China, 1999.
• 13: Wei Peng , Xi-Cheng Lu, On the reduction of broadcast redundancy in mobile ad hoc networks, Proceedings of the 1st ACM international symposium on Mobile ad hoc networking & computing, November 20, 2000, Boston, Massachusetts
• 14: W. Peng and X. Lu. AHBP: An efficient broadcast protocol for mobile ad hoc networks. Journal of Science and Technology - Beijing, China, 2002.
• 15: A. Qayyum, L. Viennot, and A. Laouiti. Multipoint relaying: An efficient technique for flooding in mobile wireless networks. Technical Report 3898, INRIA - Rapport de recherche, 2000.
• 16: I. Stojmenovic1 , M. Seddigh , J. Zunic, Internal Nodes based Broadcasting in Wireless Networks, Proceedings of the 34th Annual Hawaii International Conference on System Sciences ( HICSS-34)-Volume 9, p.9005, January 03-06, 2001
• 17: J. Sucec and I. Marsic. An efficient distributed network-wide broadcast algorithm for mobile ad hoc networks. CAIP Technical Report 248 - Rutgers University, September 2000.
• 18: Jie Wu , Hailan Li, On calculating connected dominating set for efficient routing in ad hoc wireless networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.7-14, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313261]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
      C.2.2 Network Protocols
          Subjects: Routing protocols
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Algorithms, Design, Performance

Keywords:
IEEE 802.11, MANET, ad hoc networks, broadcast protocols, flooding protocols, mobile networks