Abstract
Most highly dynamic infrastructure-less networks have in common that the assumption of connectivity does not necessarily hold at a given instant. Still, communication routes can be available between any pair of nodes over time and space. These networks (variously called delay-tolerant, disruptive-tolerant, challenged) are naturally modeled as time-varying graphs (or evolving graphs), where the existence of an edge is a function of time. In this paper we study deterministic computations under unstructured mobility, that is when the edges of the graph appear infinitely often but without any (known) pattern. In particular, we focus on the problem of broadcasting with termination detection. We explore the problem with respect to three possible metrics: the date of message arrival (foremost), the time spent doing the broadcast (fastest), and the number of hops used by the broadcast (shortest). We prove that the solvability and complexity of this problem vary with the metric considered, as well as with the type of knowledge a priori available to the entities. These results draw a complete computability map for this problem when mobility is unstructured.
Chapter PDF
Similar content being viewed by others
Keywords
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.
References
Bettstetter, C., Resta, G., Santi, P.: The node distribution of the random waypoint mobility model for wireless ad hoc networks. IEEE Trans. on Mobile Comp. 2(3), 257–269 (2003)
Bui-Xuan, B., Ferreira, A., Jarry, A.: Computing shortest, fastest, and foremost journeys in dynamic networks. Intl. J. of Foundations of Comp. Science 14(2), 267–285 (2003)
Burgess, J., Gallagher, B., Jensen, D., Levine, B.N.: Maxprop: Routing for vehicle-based disruption-tolerant networks. In: Proc. of the 25th Conference on Computer Communications (INFOCOM’06), pp. 1–11 (2006)
Cardei, I., Liu, C., Wu, J.: Routing in Wireless Networks with Intermittent Connectivity. In: Encyclopedia of Wireless and Mobile Communications. CRC Press, Taylor & Francis (2007)
Casteigts, A., Chaumette, S., Ferreira, A.: Characterizing topological assumptions of distributed algorithms in dynamic networks. In: Kutten, S., Žerovnik, J. (eds.) SIROCCO 2009. LNCS, vol. 5869, pp. 126–140. Springer, Heidelberg (2010)
Casteigts, A., Flocchini, P., Mans, B., Santoro, N.: Deterministic computations in time-varying graphs: Broadcasting under unstructured mobility. Technical report, University of Ottawa (May 2010)
Clementi, A., Macci, C., Monti, A., Pasquale, F., Silvestri, R.: Flooding time in edge-markovian dynamic graphs. In: Proc. of the 27th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 213–222. ACM, New York (2008)
Clementi, A., Monti, A., Pasquale, F., Silvestri, R.: Information spreading in stationary markovian evolving graphs. In: Proc. of the 23rd IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 1–12. IEEE Computer Society, Los Alamitos (2009)
Dimitriou, T., Nikoletseas, S., Spirakis, P.: The infection time of graphs. Discrete Applied Mathematics 154(18), 2577–2589 (2006)
Ferreira, A.: Building a reference combinatorial model for MANETs. IEEE Network 18(5), 24–29 (2004)
Fiore, M., Härri, J.: The networking shape of vehicular mobility. In: Proc. of the 9th ACM intl. symposium on Mobile ad hoc networking and computing, pp. 261–272. ACM, New York (2008)
Flocchini, P., Kellett, M., Mason, P., Santoro, N.: Mapping an unfriendly subway system. In: Proc. 5th International Conference on Fun with Algorithms (to appear, 2010)
Flocchini, P., Mans, B., Santoro, N.: Exploration of periodically varying graphs. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878. Springer, Heidelberg (2009)
Guo, S., Keshav, S.: Fair and efficient scheduling in data ferrying networks. In: Proceedings of the 2007 ACM CoNEXT conference. ACM, New York (2007)
Jacquet, P., Mans, B., Rodolakis, G.: Information propagation speed in mobile and delay tolerant networks. In: Proc. of the 28th Conference on Computer Communications (INFOCOM’09), Rio de Janeiro, Brazil (2009)
Jain, S., Fall, K., Patra, R.: Routing in a delay tolerant network. In: Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, pp. 145–158. ACM, New York (2004)
Kempe, D., Kleinberg, J.: Protocols and impossibility results for gossip-based communication mechanisms. In: 43rd Symp. on Found. of Comp. Sci (FOCS), pp. 471–480 (2002)
Kim, M., Kotz, D., Kim, S.: Extracting a mobility model from real user traces. In: Proceedings of IEEE Infocom, vol. 6, pp. 1–13 (2006) (Citeseer)
Leguay, J., Friedman, T., Conan, V.: Evaluating mobility pattern space routing for DTNs. In: 25th IEEE Int. Conf. on Computer Communications (INFOCOM’06), p. 18 (2006)
Liu, C., Wu, J.: Scalable routing in cyclic mobile networks. IEEE Trans. Parallel Distrib. Syst. 20(9), 1325–1338 (2009)
O’Dell, R., Wattenhofer, R.: Information dissemination in highly dynamic graphs. In: DIALM-POMC ’05: Proceedings of the 2005 joint workshop on Foundations of mobile computing, pp. 104–110. ACM, New York (2005)
Spyropoulos, T., Psounis, K., Raghavendra, C.S.: Spray and wait: an efficient routing scheme for intermittently connected mobile networks. In: Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p. 259. ACM, New York (2005)
Zhang, X., Kurose, J., Levine, B.N., Towsley, D., Zhang, H.: Study of a bus-based disruption-tolerant network: mobility modeling and impact on routing. In: Proc. of 13th ACM intl. conf. on Mobile computing and networking, pp. 195–206. ACM, New York (2007)
Zhang, Z.: Routing in intermittently connected mobile ad hoc networks and delay tolerant networks: Overview and challenges. IEEE Comm. Surveys & Tutorials 8(1), 24–37 (2006)
Zhao, W., Ammar, M., Zegura, E.: A message ferrying approach for data delivery in sparse mobile ad hoc networks. In: MobiHoc ’04: Proc. of the 5th ACM intl. symposium on Mobile ad hoc networking and computing, pp. 187–198. ACM, New York (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 IFIP
About this paper
Cite this paper
Casteigts, A., Flocchini, P., Mans, B., Santoro, N. (2010). Deterministic Computations in Time-Varying Graphs: Broadcasting under Unstructured Mobility. In: Calude, C.S., Sassone, V. (eds) Theoretical Computer Science. TCS 2010. IFIP Advances in Information and Communication Technology, vol 323. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15240-5_9
Download citation
DOI: https://doi.org/10.1007/978-3-642-15240-5_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15239-9
Online ISBN: 978-3-642-15240-5
eBook Packages: Computer ScienceComputer Science (R0)