Advertisement

Heuristic Algorithms for Minimum Bandwith Consumption Multicast Routing in Wireless Mesh Networks

  • Pedro M. Ruiz
  • Antonio F. Gomez-Skarmeta
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3738)

Abstract

We study the problem of computing multicast trees with minimal bandwidth consumption in multi-hop wireless mesh networks. For wired networks, this problem is known as the Steiner tree problem, and it has been widely studied before. We demonstrate in this paper, that for multihop wireless mesh networks, a Steiner tree does not offer the minimal bandwidth consumption, because it neglects the wireless multicat advantage. Thus, we re-formulate the problem in terms of minimizing the numbrer of transmissions, rather than the edge cost of multicast trees. We show that the new problem is also NP-complete and we propose heuristics to compute good approximations for such bandwidth-optimal trees. Our simulation results show that the proposed heuristics offer a lower bandwidth consumption compared with Steiner trees.

Keywords

Relay Node Minimum Span Tree Steiner Tree Wireless Mesh Network Multicast Tree 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 1.
    Deering, S.: Multicast Routing in a Datagram Internetwork, Ph.D. Thesis, Electrical Engineering Dept., Stanford University (December 1991)Google Scholar
  2. 2.
    Deering, S.-E., Cheriton, D.-R.: Multicast Routing in datagram internetworks and extended LANs. Transactions on Computer Systems 8(2), 85–110 (1990)CrossRefGoogle Scholar
  3. 3.
    Moy, J.: Multicast routing extensions for OSPF. Computer communications of the ACM 37(8), 61–66 (1994)CrossRefGoogle Scholar
  4. 4.
    Ballardie, T., Francis, P., Crowcroft, J.: Core Based Trees (CBT) – An architecture for scalable inter-domain multicast routing. In: Proc. of ACM SIGCOMM 1993, San Francisco, CA, pp. 85–95 (October 1993)Google Scholar
  5. 5.
    Deering, S., Estrin, D.-L., Farinacci, D., Jacobson, V., Liu, C.-G., Wei, L.: The PIM architecture for wide-area multicast routing. IEEE/ACM Transactions on Networking 4(2), 153–162 (1996)CrossRefGoogle Scholar
  6. 6.
    Cordeiro, C., Gossain, H., Agrawal, D.: Multicast over Wireless Mobile Ad Hoc Networks: Present and Future Directions. IEEE Network (1), 52–59 (2003)Google Scholar
  7. 7.
    Karp, R.-M.: Reducibility among combinatorial problems. In: Complexity of computer computations, pp. 85–103. Plenum Press, New York (1975)Google Scholar
  8. 8.
    Waxman, B.-M.: Routing of Multipoint Connections. IEEE Journal on Selected Areas in Communications 6(9), 1617–1622 (1998)CrossRefGoogle Scholar
  9. 9.
    Kou, L., Markowsky, G., Berman, L.: A fast algorithm for Steiner trees. Acta Informatica 2(15), 141–145 (1981)CrossRefMathSciNetGoogle Scholar
  10. 10.
    Plesnik, J.: The complexity of designing a network with minimum diameter. Networks (11), 77–85 (1981)Google Scholar
  11. 11.
    Zelikovsky, A.: An 11/6-approximation algorithm for the network Steiner problem. Algorithmica (9), 463–470 (1993)Google Scholar
  12. 12.
    Rajagopalan, S., Vazirani, V.V.: On the bidirected cut relaxation for the metric Steiner tree problem. In: Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 742–751 (1999)Google Scholar
  13. 13.
    Even, S.: Graph Algorithms, pp. 204–209. Computer Science Press, Rockville (1979)zbMATHGoogle Scholar
  14. 14.
    Lim, H., Kim, C.: Multicast Tree Construction and Flooding in Wireless Ad Hoc Networks. In: Proceedings of the 3rd ACM international workshop on Modeling, analysis and simulation of wireless and mobile systems, Boston, MA, USA, pp. 61–68 (August 2000)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Pedro M. Ruiz
    • 1
  • Antonio F. Gomez-Skarmeta
    • 1
  1. 1.University of MurciaMurciaSpain

Personalised recommendations