Skip to main content
Springer Nature Link
Log in

Distributed formation of core-based forwarding multicast trees in mobile ad hoc networks

  • Published:
Telecommunication Systems Aims and scope Submit manuscript

Abstract

A core-based forwarding multicast tree is a shortest path tree rooted at core node that distributes multicast packets to all group members via the tree after the packets are sent to the core. Traditionally, the bandwidth cost consumed by transmitting a packet from the core via the tree is evaluated by the total weights of all the edges. And, the bandwidth cost is minimized by constructing the multicast tree that has minimum total weights of edges to span all group members. However, when the local broadcast operation is used to multicast a packet, we found that the bandwidth cost is supposed to be evaluated by the total weights of all senders that include the core and all non-leaves. Since the multicast tree with the number of nodes greater than or equal to three has minimum bandwidth cost only when the core is not a leaf, it leads us to find the multicast tree with the minimum number of non-leaves when each sender node has a unit weight. However, no polynomial time approximation scheme can be found for the minimum non-leaf multicast tree problem unless P = NP since the problem is not only NP-hard but also MAX-SNP hard. Thus, a heuristic is proposed to dynamically reduce the number of non-leaves in the multicast tree. Experimental results show that the multicast tree after the execution of our method has smaller number of non-leaves than others in the geometrically distributed network model.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
€32.70 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (France)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. A. Ballardie, Core Based Trees (CBT) Multicast Routing Architecture, Internet RFC 2201, (1997).

  2. T. Camp, J. Boleng and V. Davies, A survey of mobility models for ad hoc network research, Wireless Communications and Mobile Computing 2(5) (2002) 483–502.

    Article  Google Scholar 

  3. K. Chen and K. Nahrstedt, Effective location-guided tree construction algorithm for small group multicast in MANET, in: Proc. of Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM) (2002), pp. 1180–1189.

  4. C.C. Chiang, M. Gerla and L. Zhang, Adaptive shared tree multicast in mobile wireless networks, in: Proc. of IEEE Global Telecommunications Conference (GLOBECOM) (1998), pp. 1817–1822.

  5. C.C. Chiang, M. Gerlar and L. Zhang, Forwarding group multicast protocol (FGMP) for multihop mobile wireless networks, ACM/Baltzer Journal of Cluster Computing: Special Issue on Mobile Computing 1(2) (1998) 187–196.

    Google Scholar 

  6. S.K. Das, B.S. Manoj and C.S.R. Murthy, A dynamic core based multicast routing protocol for ad hoc wireless networks, in: Proc. of ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC) (2002), pp. 24–35.

  7. D. Estrin, D. Farinacci, A. Helmy, D. Thaler, S. Deering, M. Handley, V. Jacobson, C. Liu, P. Sharma and L. Wei, Protocol Independent Multicast—Sparse Mode (PIM-SM): Protocol Specification, Internet RFC 2362 (1998).

  8. E. Fleury and Y. Huang, On the performance and feasibility of multicast core selection heuristics, in: Proc. of IEEE International Conference on Computer Communications and Networks (ICCCN) (1998), pp. 296–303.

  9. G. Galbiati, F. Maffioli and A. Morzenti, A short note on the approximability of the maximum leaves spanning tree problem, Information Processing Letters 52(1) (1994) 45–49.

    Article  Google Scholar 

  10. J.J. Garcia-Luna-Aceves and E.L. Madruga, The core-assisted mesh protocol, IEEE Journal on Selected Areas in Communications 17(8) (1999) 1380–1394.

    Article  Google Scholar 

  11. M.R. Garey and D.S. Jonson, Computers and Intractability: A Guide to the Theory of NP-Completeness, (Freeman Press, San Francisco, 1979).

    Google Scholar 

  12. M. Gerla, S.J. Lee and W. Su, On-demand multicast routing protocol (ODMRP) for ad hoc networks, Internet draft, draft-ietf-manet-odmrp-02.txt, 2000.

  13. S. Guha and S. Khuller, Improved methods for approximating node weighted steiner trees and connected dominating sets, Information and Computing 150 (1999) 57–74.

    Article  Google Scholar 

  14. S.K.S. Gupta and P.K. Srimani, Adaptive core selection and migration method for multicast routing in mobile ad hoc networks, IEEE Transactions on Parallel and Distributed Systems 14(1) (2003) 27–38.

    Article  Google Scholar 

  15. L. Ji and M.S. Corson, A lightweight adaptive multicast algorithm, in: Proc. of IEEE Global Telecommunications Conference (GLOBECOM) (1998), pp. 1036–1042.

  16. R.M. Karp, Reducibility Among Combinatorial Problems, Complexity of Computer Computations, (Plenum Press, New York, 1972).

    Google Scholar 

  17. P. Klein and R. Ravi, A nearly best-possible approximation algorithm for node weighted steiner trees, Journal of Algorithms 19(1) (1995) 104–115.

    Article  Google Scholar 

  18. Y.B. Ko and N.H. Vaidya, Geocasting in mobile ad hoc networks: Location-based multicast algorithms, in: Proc. of IEEE Workshop on Mobile Computing Systems and Applications (WMCSA) (1999), pp. 101–110.

  19. M. Kochhal, L. Schwiebert, S.K.S. Gupta and C. Jiao, An efficient core migration protocol for qos in mobile ad hoc networks, in: Proc. of IEEE International Conference on Performance Computing and Communications (IPCCC) (2002), pp. 387–391.

  20. S. Lee and C. Kim, Neighbor supporting ad hoc multicast routing protocol, in: Proc. of ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC) (2000), pp. 37–44.

  21. D. Li, X. Jia and H. Liu, Energy efficient broadcast routing in static ad hoc wireless networks, IEEE Transactions on Mobile Computing 3(2) (2004) 144–151.

    Article  Google Scholar 

  22. T. Ozaki, J.B. Kim and T. Suda, Bandwidth efficient multicast routing protocol for ad hoc networks, in: Proc. of IEEE International Conference on Computer Communications and Networks (ICCCN) (1999), pp. 10–17.

  23. E.M. Royer and C.E. Perkins, Multicast operation of the ad hoc on-demand distance vector routing protocol, in: Proc. of the ACM International Conference on Mobile Computing and Networking (MOBICOM) (1999), pp. 207–218.

  24. E.M. Royer and C.K. Toh, A review of current routing protocols for ad hoc mobile wireless networks, IEEE Personal Communications Magazine 6(2) (1999) 46–55.

    Article  Google Scholar 

  25. P. Sinha, R. Sivakumar and V. Bharghavan, MCEDAR: Multicast core extraction distributed ad hoc routing, in: Proc. of IEEE Wireless Communications and Networking Conference (WCNC) (1999), pp. 1313–1318.

  26. C.W. Wu and Y.C. Tay, AMRIS: A multicast protocol for ad hoc wireless networks, in: Proc. of the IEEE Military Communications Conference (MILCOM) (1999), pp. 25–29.

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, National Tsing Hua University, Hsing Chu, Taiwan, ROC

    Bing-Hong Liu, Wei-Chieh Ke & Ming-Jer Tsai

Authors
  1. Bing-Hong Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wei-Chieh Ke
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ming-Jer Tsai
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ming-Jer Tsai.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Liu, BH., Ke, WC. & Tsai, MJ. Distributed formation of core-based forwarding multicast trees in mobile ad hoc networks. Telecommun Syst 32, 263–281 (2006). https://doi.org/10.1007/s11235-006-9002-4

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11235-006-9002-4

Keywords

Search

Navigation