MISTRAL: efficient flooding in mobile ad-hoc networks

ABSTRACT

Flooding is an important communication primitive in mobile ad-hoc networks and also serves as a building block for more complex protocols such as routing protocols. In this paper, we propose a novel approach to flooding, which relies on proactive compensation packets periodically broadcast by every node. The compensation packets are constructed from dropped data packets, based on techniques borrowed from forward error correction. Since our approach does not rely on proactive neighbor discovery and network overlays it is resilient to mobilit.We evaluate the implementation of Mistral through simulation and compare its performance and overhead to purely probabilistic flooding. Our results show that Mistral achieves a significantly higher node coverage with comparable overhead.

REFERENCES

• 1: JiST/SWANS. http://jist.ece.cs.cornell.edu.
• 2: The network simulator - ns-2. http://www.isi.edu/nsnam/ns.
• 3: D. Allen. Hidden terminal problems in wireless LAN's. In IEEE 802.11 Working Group Papers, 1993.
• 4: Khaled M. Alzoubi , Peng-Jun Wan , Ophir Frieder, Message-optimal connected dominating sets in mobile ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513820]
• 5: Rimon Barr , Zygmunt J. Haas, An efficient, unifying approach to simulation using virtual machines, 2004
• 6: V. Bharghavan and B. Das. Routing in ad hoc networks using minimum connected dominating sets. In Proc. of the Int. Conference on Communications, Montreal, Canada, June 1997.
• 7: J. Byers, M. Luby, and M. Mitzenmacher. A digital fountain approach to asynchronous reliable multicast. IEEE Journal on Selected Areas in Communications, 20(8), Oct. 2002.
• 8: G. Carle and E. Biersack. Survey of error recovery techniques for ip-based audio-visual multicast applications. IEEE Network, Dec. 1997.
• 9: Rajiv Gandhi , Srinivasan Parthasarathy , Arunesh Mishra, Minimizing broadcast latency and redundancy in ad hoc networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778442]
• 10: Z. Haas, J. Halpern, and L. Li. Gossip-based ad hoc routing. In Proc. of InfoCom 2002, volume 21, pages 1707--1716, June 2002.
• 11: 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]
• 12: Christian Huitema, The case for packet level FEC, Proceedings of the TC6 WG6.1/6.4 Fifth International Workshop on Protocols for High-Speed Networks V, p.109-120, October 28-30, 1996
• 13: IEEE. 802.11 specification (part 11): Wireless LAN medium access control (MAC) and physical layer (PHY) specifications, June 1997.
• 14: D. Johnson and D. Maltz. Dynamic source routing in ad hoc wireless networks. In Imielinski and Korth, editors, Mobile Computing, volume 353. Kluwer Academic Publishers, 1996.
• 15: Young Bae Ko , Nitin H. Vaidya, Flooding-based geocasting protocols for mobile ad hoc networks, Mobile Networks and Applications, v.7 n.6, p.471-480, December 2002 [doi>10.1023/A:1020712802004]
• 16: Dariusz R. Kowalski , Andrzej Pelc, Broadcasting in undirected ad hoc radio networks, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.73-82, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872045]
• 17: Sung Ju Lee , William Su , Mario Gerla, On-demand multicast routing protocol in multihop wireless mobile networks, Mobile Networks and Applications, v.7 n.6, p.441-453, December 2002 [doi>10.1023/A:1020756600187]
• 18: W. Lou and J. Wu. Double-covered broadcast (DCB): A simple reliable broadcast algorithm in MANETs. In Proc. of INFOCOMM, 2004.
• 19: 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]
• 20: Jörg Nonnenmacher , Ernst W. Biersack , Don Towsley, Parity-based loss recovery for reliable multicast transmission, IEEE/ACM Transactions on Networking (TON), v.6 n.4, p.349-361, Aug. 1998 [doi>10.1109/90.720869]
• 21: 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
• 22: Charles E. Perkins , Elizabeth M. Royer, Ad-hoc On-Demand Distance Vector Routing, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.90, February 25-26, 1999
• 23: L. Rizzo and L. Vicisano. A reliable multicast data distribution protocol based on software FEC techniques. In Proc. of the 4th IEEE Workshop on the Architecture and Implementation of High Performance Communication Systems (HPCS'97), Sani Beach, Chalkidiki, Greece, June 1997.
• 24: Y. Sasson, D. Cavin, and A. Schiper. Probabilistic broadcast for flooding in wireless mobile ad hoc networks. In Proceedings of IEEE Wireless Communications and Networking Conference (WCNC 2003), Mar. 2003.
• 25: D. Scott and A. Yasinsac. Dynamic probabilistic retransmission in ad hoc networks. In Proc of the Int. Conference on Wireless Networks (ICWN'04), pages 158--164, Las Vegas, Nevada, June 2004. CSREA Press.
• 26: Adaptive Approaches to Relieving Broadcast Storms in a Wireless Multihop Mobile Ad Hoc Network, Proceedings of the The 21st International Conference on Distributed Computing Systems, p.481, April 16-19, 2001
• 27: Brad Williams , Tracy Camp, Comparison of broadcasting techniques for mobile ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513825]
• 28: J. Yoon, M. Liu, and B. Noble. Random waypoint considered harmful. In INFOCOM 2003, Apr. 2003.
• 29: Qi Zhang , Dharma P. Agrawal, Dynamic probabilistic broadcasting in MANETs, Journal of Parallel and Distributed Computing, v.65 n.2, p.220-233, February 2005 [doi>10.1016/j.jpdc.2004.09.006]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability; Fault tolerance

General Terms:
Algorithms, Reliability

Keywords:
MANET, compensation, flooding, forward error correction, mobile ad hoc networks