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

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: Christian Bettstetter , Hannes Hartenstein , Xavier Pérez-Costa, Stochastic properties of the random waypoint mobility model, Wireless Networks, v.10 n.5, p.555-567, September 2004 [doi>10.1023/B:WINE.0000036458.88990.e5]
• 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.
• 3: András Faragó , Violet R. Syrotiuk, MERIT: a scalable approach for protocol assessment, Mobile Networks and Applications, v.8 n.5, p.567-577, October 2003 [doi>10.1023/A:1025193929081]
• 4: Kou, L., Markowsky, G., and Berman, L. "A Fast Algorithm for Steiner Trees," Acta Informatica, 15, (1981), 141--145.
• 5: Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, Unit disk graph approximation, Proceedings of the 2004 joint workshop on Foundations of mobile computing, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1022630.1022634]
• 6: Meejeong Lee , Ye Kyung Kim, PatchODMRP: An Ad-hoc Multicast Routing Protocol, Proceedings of the The 15th International Conference on Information Networking, p.537, January 31-February 02, 2001
• 7: Seungjoon Lee , Chongkwon Kim, Neighbor supporting ad hoc multicast routing protocol, Proceedings of the 1st ACM international symposium on Mobile ad hoc networking & computing, November 20, 2000, Boston, Massachusetts
• 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.
• 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.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

General Terms:
Algorithms, Performance

Keywords:
mobile ad hoc networks, multicast trees, simulation, stability