Efficient location-aided flooding scheme initiated by receiver for MANETs

ABSTRACT

Flooding is a fundamental, critical, and indispensable operation for supporting various applications and protocols in wireless ad hoc networks. The traditional flooding scheme generates excessive redundant packet retransmissions, however, causing contention and packet collisions, and ultimately wasting precious limited bandwidth and energy. Recently, some flooding schemes have been studied to avoid those problems, but these algorithms either perform well in redundant transmissions or require that the node maintain information about neighbors more than one hop away. One of the most efficient approaches is found in the work of Liu et al., which uses only 1-hop neighbor information. The advantage of this scheme is that it achieves local optimality in terms of the number of retransmitting nodes, although it still produces many redundant transmissions. In this paper, we propose an efficient flooding protocol that minimizes flooding traffic by leveraging location information of 1-hop neighbor nodes. Our scheme is receiver-based, which means that each receiver of a flooding message determines whether it should forward the message based on the given retransmission rule. Simulation results show that our scheme is highly efficient. It is able to reduce the number of forward nodes almost to that of the lower bound but maintains a high delivery ratio.

REFERENCES

• 1: Andreas Savvides , Chih-Chieh Han , Mani B. Strivastava, Dynamic fine-grained localization in Ad-Hoc networks of sensors, Proceedings of the 7th annual international conference on Mobile computing and networking, p.166-179, July 2001, Rome, Italy [doi>10.1145/381677.381693]
• 2: P. Bahl and V. Padmanabhan. RADAR: An In-Building RF-Based User Location and Tracking System. In Proceeding of the Conference on Computer Communications, pages 775--784, 2000.
• 3: 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]
• 4: C. Perkins , E. Belding-Royer , S. Das, Ad hoc On-Demand Distance Vector (AODV) Routing, RFC Editor, 2003
• 5: Fei Dai , Jie Wu, An Extended Localized Algorithm for Connected Dominating Set Formation in Ad Hoc Wireless Networks, IEEE Transactions on Parallel and Distributed Systems, v.15 n.10, p.908-920, October 2004 [doi>10.1109/TPDS.2004.48]
• 6: I. Getting. The global positioning system. IEEE Spectrum, 30:36--47, 1993.
• 7: Hai Liu , Xiaohua Jia , Peng-Jun Wan , Xinxin Liu , Frances F. Yao, A Distributed and Efficient Flooding Scheme Using 1-Hop Information in Mobile Ad Hoc Networks, IEEE Transactions on Parallel and Distributed Systems, v.18 n.5, p.658-671, May 2007 [doi>10.1109/TPDS.2007.1023]
• 8: Z. Haas and M. Pearlman. The Zone Routing Protocol (ZRP) for Ad Hoc Networks. Internet draft -- mobile ad hoc networking (monet) working group of the internet engineering task force (ietf), 1997.
• 9: D. M. J. Jetcheva, Y. Hu and D. Johnson. A Simple Protocol for Multicast and Broadcast in Mobile Ad Hoc Networks. Internet draft: draft-ietf-manet-simple-mbcast-01.txt (outdated), 2001.
• 10: D. Johnson and D. Maltz. Mobile Computing: Dynamic Source Routing in Ad Hoc Wireless Networks. Kluwer Academic Publishers, Dordrecht, The Netherlands, 1996.
• 11: Young-Bae Ko , Nitin H. Vaidya, Location-aided routing (LAR) in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.66-75, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288252]
• 12: D. Niculescu and B. Nath. Ad Hoc Positioning System (APS) using AoA. In Proceeding of the Conference on Computer Communications, pages 1734--1743, 2003.
• 13: R. S. P. Sinha and V. Bharghavan. Enhancing Ad hoc Routing with Dynamic Virtual Infrastructures. In Proceeding of the Annual Joint Conference of the IEEE Computer and Communications Societies, pages 1763--1772, 2001.
• 14: Charles E. Perkins, Ad Hoc Networking, Addison-Wesley Professional, 2008
• 15: K. A. P. J. Wan and O. Frieder. Distributed Construction of Connected Dominating Set in Wireless Ad hoc Networks. In Proceeding of the Conference on Computer Communications, pages 1597--1604, 2002.
• 16: 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]
• 17: 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]
• 18: K. H. Y. Cai and A. Phillips. Leveraging 1-hop Neighborhood Knowledge for Efficient Flooding in Wireless Ad Hoc Networks. In Proceeding of the International Performance Computing and Communications Conference, pages 7--9, 2005.
• 19: 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

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance, Reliability

Keywords:
broadcasting, mobile ad-hoc networks, receiver-based