Selecting forwarding neighbors in wireless Ad Hoc networks

ABSTRACT

Broadcasting is a fundamental operation which is frequent in wireless ad hoc networks. A simple broadcasting mechanism, known as flooding, is to let every node retransmit the message to all its 1-hop neighbors when receiving the first copy of the message. Despite its simplicity, flooding is very inefficient and can result in high redundancy, contention, and collision. One approach to reducing the redundancy is to let each node forward the message only to a small subset of 1-hop neighbors that cover all of the node's 2-hop neighbors. In this paper, we propose two practical heuristics for selecting the minimum number of forwarding neighbors: an Ο(n log n) time algorithm that selects at most 6 times more forwarding neighbors than the optimum, and an Ο(n²) time algorithm with an improved approximation ratio of 3, where n is the number of 1- and 2-hop neighbors. The best previously known algorithm, due to Bronnimann and Goodrich [2], guarantees Ο(1) approximation in Ο(n³ log n) time.

References

1. 1.J. Broch, D. B. Johnson, and D. A. Maltz, The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks, IETF Internet Draft, draft-ietf-manet-dsr-05.txt, March 2001.
2. 2.H. Bronnimann and M.T. Goodrich, Almost Optimal Set Covers in Finite VC-Dimension. Proc. lOth ACM Syrup. on Computational Geometry (SCG), 1994, 293-302.
3. 3.V. ChvAtal. A greedy heuristic for the set-covering problem. Mathematics of Operation Research, 4(3):233-235, 1979.
4. 4.B. N. Clark, C. J. Colbourn, and D. S. Johnson, "Unit Disk Graphs", Discrete Mathematics, 86:165-177, 1990.
5. 5.M. GrStschel, L. LovLsz, and A. Schrijver Geometric Algorithms and Combinatorial Optimization, second edition, Springer-Verlag, 1991.
6. 6.Z. J. Haas, M. R. Pearlman, and P. Samar. The Interzone Routing Protocol (IERP) for Ad Hoc Networks, IETF Internet Draft, draft-ietf-manet-zone-ierp-00.txt, January 2001.
7. 7.D. S. Hochbaum and W. Maass, "Approximation schemes for covering and packing problems in imageprocessing and VLSr', Journal of the A CM, 32(1): 130-136, 1985.
8. 8.H. B. Hunt III, M. V. Marathe, V. Radhakrishnan, S. S. Ravi, D. J. Rosenkrantz, and R. E. Stearns, "NC-Approximation schemes for NP- and PSPACE-hard problems for geometric graphs", Journal of Algorithms, 26(2):238-274, 1998.
9. 9.P. Jacquet, P. Muhlethaler, A. Qayyum, A. Laouiti, L. Viennot, and T. Clansen, Optimized Link State Routing Protocol, IETF Internet Draft, draft-ietf-manet-olsr-04.txt, March 2001.
10. 10.M. V. Marathe, H. Breu, H. B. Hunt III, S. S. Ravi and D. J. Rosenkrantz, "Simple Heuristics for Unit Disk Graphs", Networks, Vol. 25, 1995, pp. 59-68.
11. 11.B.M.E. Moret and H.D. Shapiro. Algorithms from P to NP, Volume I: Design and Efficiency. Benjamin/Cummings, 1991.
12. 12.S.-Y. Ni, Y.-C. Tseng, Yuh-Shyan Chen, and J.-P. Sheu, The Broadcast Storm Problem in a Mobile Ad Hoc Network", Proceedings of the fifth annual ACM/IEEE international conference on Mobile computing and networking, 1999, Pages 151 - 162.
13. 13.C. E. Perkins, E. M. Royer, and S. Das, Ad Hoc On Demand Distance Vector (AODV) Routing, IETF Internet Draft, draft-ietf-manet-aodv-08.txt, March 2001.
14. 14.P. Sinha, R. Sivakumar, and B. Vaduvur, Enhancing Ad Hoc Routing with Dynamic Virtual Infrastructures, to appear in IEEE INFOCOM 2001.

Index Terms

• Computer systems organization

  • Architectures

    • Parallel architectures

      • Cellular architectures

• Computing methodologies

  • Artificial intelligence

    • Search methodologies

      • Heuristic function construction

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Network flows

  • Mathematical analysis

    • Functional analysis

      • Approximation

• Networks

  • Network protocols

  • Network types

    • Mobile networks

    • Wireless access networks

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

    • Graph algorithms analysis

      • Network flows