Article

Determining a sequence of stable multicast Steiner trees in mobile ad hoc networks

Author:

Natarajan MeghanathanAuthors Info & Claims

ACMSE '06: Proceedings of the 44th annual ACM Southeast Conference

Pages 102 - 106

https://doi.org/10.1145/1185448.1185472

Published: 10 March 2006 Publication History

Get Access

Abstract

We show that given the complete knowledge of future topology changes, it is possible to determine the sequence of stable multicast Steiner trees (called the stable mobile multicast Steiner tree) in a multicast session such that the number of tree transitions is minimal. The algorithm to determine the stable mobile multicast Steiner tree and the minimum number of tree transitions is called OptTreeTrans. It is based on the following greedy approach: whenever a multicast Steiner tree is required, choose the Steiner tree that will exist for the longest time. The above strategy is repeated over the duration of the multicast session. We prove that OptTreeTrans gives the optimal number of tree transitions and simultaneously yields the stable mobile multicast Steiner tree. We study the performance of OptTreeTrans in terms of the number of tree transitions and the number of links constituting the Steiner tree for different conditions of node mobility and network density.

References

[1]

Bettstetter, C., Hartenstein, H., and Perez-Costa, X. "Stochastic Properties of the Random-Way Point Mobility Model," Wireless Networks, 10, 5, (Sep. 2004), 555--567.

Digital Library

Google Scholar

[2]

Chiang, C. C., Gerla, M., and Zhang, L. "Adaptive shared tree multicast in mobile wireless networks," In Proceedings of the IEEE Global Telecommunications Conference, (Nov. 1998), 1817--1822.

Google Scholar

[3]

Farago, A., and Syrotiuk, V. R. "MERIT: A Scalable Approach for Protocol Assessment," Mobile Networks and Applications, 8, 5, (Oct. 2003), 567--577.

Digital Library

Google Scholar

[4]

Kou, L., Markowsky, G., and Berman, L. "A Fast Algorithm for Steiner Trees," Acta Informatica, 15, (1981), 141--145.

Digital Library

Google Scholar

[5]

Kuhn, F., Moscibroda, T., and Wattenhofer, R. "Unit Disk Graph Approximation," In Proceedings of Joint Workshop on Foundations on Mobile Computing, (Oct. 2004), 17--23.

Digital Library

Google Scholar

[6]

Lee, M., and Kim, Y. "PatchODMRP: an ad hoc multicast routing protocol," In Proceedings of the 15th IEEE International Conference on Information Networking, (Jan. -- Feb. 2001), 537--543.

Digital Library

Google Scholar

[7]

Lee, S., and Kim, C. "Neighbor supporting ad hoc multicast routing protocol," In Proceedings of the 1st Annual Workshop on Mobile and Ad hoc Networking and Computing, (Aug. 2000), 37--44.

Digital Library

Google Scholar

[8]

Lee, S. J., Su, W., Hsu, J., Gerla, M., and Bagrodia, R. "A performance comparison study of ad hoc wireless multicast protocols," In Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies, 2, (Mar. 2000), 565--574.

Google Scholar

[9]

Toh, C. K., Guichal, G., and Bunchua, S. "ABAM: on-demand associativity-based multicast routing for ad hoc mobile networks," In Proceedings of the 52nd IEEE VTS Fall Vehicular Technology Conference, (Sep. 2000), 3, 987--993.

Google Scholar

Cited By

View all

Lertpratchya DBlough D(2016)Interference-aware multicast trees and meshes for wireless multihop networksAd Hoc Networks10.1016/j.adhoc.2016.05.00147:C(99-113)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1016/j.adhoc.2016.05.001
Zhou DShi TLv XBai W(2015)A research on banded topology control of wireless sensor networks along high-speed railways2015 34th Chinese Control Conference (CCC)10.1109/ChiCC.2015.7260868(7736-7740)Online publication date: Jul-2015
https://doi.org/10.1109/ChiCC.2015.7260868
Lertpratchya DBlough DRiley G(2014)Interference-aware multicast for wireless multihop networks2014 IEEE Wireless Communications and Networking Conference (WCNC)10.1109/WCNC.2014.6952968(3034-3039)Online publication date: Apr-2014
https://doi.org/10.1109/WCNC.2014.6952968
Show More Cited By

Index Terms

Determining a sequence of stable multicast Steiner trees in mobile ad hoc networks
1. Networks
  1. Network architectures

Recommendations

A weight-based clustering multicast routing protocol for mobile ad hoc networks

In mobile ad hoc networks, the mobile nodes can move arbitrarily without any centralised management mechanism. The topology of these networks can be very dynamic due to the mobility of mobile nodes. Under such changeable network topology, multicasting ...
Building multicast trees in ad-hoc networks
Autonomics '08: Proceedings of the 2nd International Conference on Autonomic Computing and Communication Systems

Multicast trees are used in a variety of applications, such as publish/subscribe systems or content distribution networks. Existing algorithms for ad-hoc networks typically produce multicast trees requiring many nodes to act as relays even though they ...
Energy-efficient broadcasting in ad-hoc networks: combining MSTs with shortest-path trees
PE-WASUN '04: Proceedings of the 1st ACM international workshop on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks

We investigate the problem of constructing a multicast tree in ad-hoc networks. In particular, we address the issue of the power consumption, that is, the overall energy that the stations must spend to implement such a tree. We focus on two extreme ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACMSE '06: Proceedings of the 44th annual ACM Southeast Conference

March 2006

823 pages

ISBN:1595933158

DOI:10.1145/1185448

General Chair:
Ronaldo Menezes
Florida Institute of Technology

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 March 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ACM SE06

ACM SE06: ACM Southeast Regional Conference

March 10 - 12, 2006

Florida, Melbourne

Acceptance Rates

ACMSE '06 Paper Acceptance Rate 100 of 244 submissions, 41%;

Overall Acceptance Rate 502 of 1,023 submissions, 49%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
175
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Lertpratchya DBlough D(2016)Interference-aware multicast trees and meshes for wireless multihop networksAd Hoc Networks10.1016/j.adhoc.2016.05.00147:C(99-113)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1016/j.adhoc.2016.05.001
Zhou DShi TLv XBai W(2015)A research on banded topology control of wireless sensor networks along high-speed railways2015 34th Chinese Control Conference (CCC)10.1109/ChiCC.2015.7260868(7736-7740)Online publication date: Jul-2015
https://doi.org/10.1109/ChiCC.2015.7260868
Lertpratchya DBlough DRiley G(2014)Interference-aware multicast for wireless multihop networks2014 IEEE Wireless Communications and Networking Conference (WCNC)10.1109/WCNC.2014.6952968(3034-3039)Online publication date: Apr-2014
https://doi.org/10.1109/WCNC.2014.6952968
Biradar RManvi S(2012)ReviewJournal of Network and Computer Applications10.1016/j.jnca.2011.08.00335:1(221-239)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.1016/j.jnca.2011.08.003

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

A weight-based clustering multicast routing protocol for mobile ad hoc networks

Building multicast trees in ad-hoc networks

Energy-efficient broadcasting in ad-hoc networks: combining MSTs with shortest-path trees