New technologies and the deployment of mobile and nomadic services are driving the emergence of complex communications networks that have highly dynamic behaviour. This naturally engenders new route-discovery problems under changing conditions over these networks. Unfortunately, the temporal variations in the network topology are hard to be effectively captured in a classical graph model. In this paper, we use and extend a recently proposed graph theoretic model, which helps capture the evolving characteristic of such networks, in order to compute multicast trees with minimum overall transmission time for a class of wireless mobile dynamic networks. We first show that computing different types of strongly connected components in this model in NP-Complete, and then propose an algorithm to build all rooted directly minimum spanning trees in already identified strongly connected components.

Wireless networks, mobile networks, multicast, evolving graphs, LEO satellites, minimum spanning trees, strongly connected components, graph theoretic models, NP-complete

[1]. Y. J Chu amd T H. Liu. On the shortest arborescence of a directed graph. Science Sincia, 14:1396- 1400, 1965
[2]. T. Cormen, C. Leiserson and R. Rivest. Introduction to Algorithms. The MIT Press, 1990
[3]. C.Scheideler. Models and techniques for communication in dunamic networks. In In H. Alt and A. Ferreira, editors, Proceedings of the 19th International Symposium on Theoretical Aspecys of Computer Science, volume 2285, pages 27-19. Springer-Verlag, March 2002.
[4]. E. Ekici, I. F Akyildiz, and M. D. Bender. Datagram routing algorithm for LEO satellite networks. In IEEE infocom, pages 500-508,2000.
[5]. Ferreira, on models and algorithms for dmanic communication networks: The case for evolving graphs. In Proceedings of 4e rencontres francophnes sur les Aspects Algorithmiques des Telecommunications (ALGOTEL ’2002), Meze, France, May 2002.
[6]. Fereira, J. Galtier, and P. Penna. Topological design, routing and handover in satellite networks. In I. Stojmenovic, editor, Handbook of wireless Networks and Mobile Computing, pages 473-493, John Wiley and Sons, 2002.
[7]. P. A Humblet. A distributed algorithm for minimum weight directed spanning trees. IEEE transactions on communications, COM-31(6): 756-762, 1983.
[8]. R. E. Tarjan. Finding optimum branching. Networks, pages 25-35, 1977.
[9]. P.-J. Wan, G, Calinescue, X. Li, and O. Frieder. Minimum-energy broadcast routing in static ad hoc wireless networks. In Proc. IEEE infocom, pages 1162-1171, Anchorage Alaska, 2001.
[10]. M. Werner and G. Maral. Traffic flows and dynamic routing in leo intersatellite link networks. In In Proceedings 5th International Mobile Satellite Conference (IMSC ’97), Pasadena, California, USA, June 1997.
[11]. M. Werner and F. Wauquiez. Capacity dimensioning of ISL networks in broadband LEO satellite systems. In sixth International Mobile Satellite Conference : IMSC ’99, pages 334-341, Ottawa, Canada, June 1999.
[12]. J. Wieselthier, G. Nguyen, and A. Ephremides. On the construction of energy-efficient broadcast and multicast trees in wireless networks. In proc. IEEE infocom, pages585-594, Tel Aviv, 2000