Multicast tree construction and flooding in wireless ad hoc networks

ABSTRACT

In an ad hoc network, each host assumes the role of a router and relays packets toward final destinations. This paper studies efficient routing mechanisms for multicast and broadcast in ad hoc wireless networks. Because a packet is broadcast to all neighboring nodes, the optimality criteria of wireless network routing is different from that of wired network routing. In this paper, we point out that the number of packet forwarding is the more important cost factor than the number of links in the ad hoc network. After we show constructing minimum cost multicast tree is hard, we propose two new flooding methods, self pruning and dominant pruning. Both methods utilize neighbor information to reduce redundant transmissions. Performance analysis shows that both methods perform significantly better than blind flooding. Especially, dominant pruning performs close to the practically achievable best performance limit.

REFERENCES

• 1: Vincent D. Park , M. Scott Corson, A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.1405, April 09-11, 1997
• 2: Stefano Basagni , Imrich Chlamtac , Danilo Bruschi, A mobility-transparent deterministic broadcast mechanism for ad hoc networks, IEEE/ACM Transactions on Networking (TON), v.7 n.6, p.799-807, Dec. 1999 [doi>10.1109/90.811446]
• 3: Z. J. Haas, A new routing protocol for the reconfigurable wireless networks, ICUPC 97 (1997) 562- 566.
• 4: 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
• 5: S. Guha, S. Khuller, Approximation algorithms for connected dominating sets, Algorithmica 20 (4) (1998) 374-387.
• 6: P. Sinha, R. Sivakumar, V. Bharghavan, CEDAR: A core-extraction distributed ad hoc routing algorithm, INFOCOM 99 (1999) 202-209.
• 7: Andrew S. Tanenbaum, Computer networks (3rd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 8: D. B. Johnson, D. A. Maltz, Dynamic source routing in ad hoc wireless networks, Mobile Computing, Academic Publishers (1996) 153-181.
• 9: Shimon Even, Graph Algorithms, W. H. Freeman & Co., New York, NY, 1979
• 10: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 11: Elizabeth M. Royer , Charles E. Perkins, Multicast operation of the ad-hoc on-demand distance vector routing protocol, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.207-218, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313538]
• 12: I. Chlamtac, S. Kutten, On broadcasting in radio networks-problem analysis and protocol design, IEEE Transactions on Communications 33 (12) (1985) 1240-1246.
• 13: S. Lee, M. Gerla, C.-C. Chiang, On-demand nmlticast routing protocol, WCNC 99 (1999) 1298- 1302.
• 14: L. Lovasz, On the ratio of optimal integral and fractional covers, Discrete mathematics 13 (1975) 383-390.
• 15: Reuven Bar-Yehuda , Amos Israeli , Alon Itai, Multiple communication im multihop radio networks, SIAM Journal on Computing, v.22 n.4, p.875-887, Aug. 1993 [doi>10.1137/0222055]
• 16: Charles J. Colbourn , Lorna K. Stewart, Permutation graphs: connected domination and Steiner trees, Discrete Mathematics, v.86 n.1-3, p.179-189, Dec. 14, 1990 [doi>10.1016/0012-365X(90)90359-P]
• 17: D. Lichtenstein, Planar formulae and their uses, SIAM Journal on Computing 11 (2) (1982) 329- 343.
• 18: R. M. Karp, Reducibility among combinatorial problems, Complexity of computer computations (Plenum Press, 1972) 85-104.
• 19: Elena Pagani , Gian Paolo Rossi, Reliable broadcast in mobile multihop packet networks, Proceedings of the 3rd annual ACM/IEEE international conference on Mobile computing and networking, p.34-42, September 26-30, 1997, Budapest, Hungary [doi>10.1145/262116.262125]
• 20: K. Bharath-Kumar, J. M. Jaffe, Routing to multiple destinations in computer networks, IEEE Transactions on Communications 31 (3) (1983) 343-351.
• 21: 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]
• 22: I. Chlamtac, O. Weinstein, The wave expansion approach to broadcasting in multihop radio networks, IEEE Transactions on Communications 39 (3) (1991) 426-433.
• 23: I. Chlamtac , S. Kutten, Tree-based broadcasting in multihop radio networks, IEEE Transactions on Computers, v.36 n.10, p.1209-1223, Oct. 1987 [doi>10.1109/TC.1987.1676861]

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Design, Measurement, Performance, Theory