Abstract
The past years have seen an intense research effort directed at study of delay/disruption tolerant networks and related concepts (intermittently connected networks, opportunistic mobility networks). As a fundamental primitive, routing in such networks has been one of the research foci. While multiple network models have been proposed and routing in them investigated, most of the published results are of heuristic nature with experimental validation; analytical results are scarce and apply mostly to networks whose structure follows deterministic schedule.
In this paper, we propose a simple model of opportunistic mobility network based on oblivious carriers, and investigate the routing problem in such networks. We present an optimal online routing algorithm and compare it with a simple shortest-path inspired routing and the optimal offline routing. In doing so, we identify the key parameters (the minimum non-zero probability of meeting among the carrier pairs, and the number of carriers a given carrier comes into contact) driving the separation among these algorithms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Biswas, S., Morris, R.: Opportunistic routing in multi-hop wireless networks. Computer Communication Review 34(1), 69–74 (2004)
Boehlert, G.W., Costa, D.P., Crocker, D.E., Green, P., O’Brien, T., Levitus, S., Le Boeuf, B.J.: Autonomous pinniped environmental samplers: Using instrumented animals as oceanographic data collectors. Journal of Atmospheric and Oceanic Technology 18(11), 1882–1893 (2001)
Burgess, J., Gallagher, B., Jensen, D., Levine, B.N.: Maxprop: Routing for vehicle-based disruption-tolerant networks. In: INFOCOM, IEEE, Los Alamitos (2006)
Burleigh, S., Hooke, A., Torgerson, L.: Delay-tolerant networking: an approach to interplanetary internet. IEEE Communications Magazine 41, 128–136 (2003)
Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. In: CoRR, abs/1012.0009 (2010)
Chaintreau, A., Hui, P., Crowcroft, J., Diot, C., Gass, R., Scott, J.: Impact of human mobility on opportunistic forwarding algorithms. IEEE Trans. Mob. Comput. 6(6), 606–620 (2007)
Chen, Z.D., Kung, H., Vlah, D.: Ad hoc relay wireless networks over moving vehicles on highways. In: Mobile Ad Hoc Networking & Computing (MobiHoc), pp. 247–250. ACM, New York (2001)
Clementi, A.E.F., Monti, A., Silvestri, R.: Modelling mobility: A discrete revolution. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6199, pp. 490–501. Springer, Heidelberg (2010)
Doria, A.: Providing connectivity to the saami nomadic community. In: Open Collaborative Design for Sustainable Innovation (2002)
Ferreira, A.: Building a reference combinatorial model for manets. IEEE Network 18(5), 24–29 (2004)
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, pp. 534–543. Springer, Heidelberg (2009)
Jain, S., Fall, K.R., Patra, R.K.: Routing in a delay tolerant network. In: SIGCOMM, pp. 145–158. ACM, New York (2004)
Juang, P., Oki, H., Wang, Y., Martonosi, M., Peh, L.-S., Rubenstein, D.: Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with zebranet. In: ASPLOS, pp. 96–107 (2002)
Kempe, D., Kleinberg, J., Kumar, A.: Connectivity and inference problems for temporal networks. In: Symposium on Theory of Computing (STOC), pp. 504–513. ACM, New York (2000)
Leguay, J., Friedman, T., Conan, V.: Dtn routing in a mobility pattern space. In: ACM SIGCOMM Workshop on Delay-Tolerant Networking (WDTN), pp. 276–283. ACM, New York (2005)
Leskovec, J., Kleinberg, J., Faloutsos, C.: Graph evolution: Densification and shrinking diameters. ACM Trans. Knowl. Discov. Data 1(1), 2 (2007)
Lindgren, A., Doria, A., Schelén, O.: Probabilistic routing in intermittently connected networks. SIGMOBILE Mob. Comput. Commun. Rev. 7, 19–20 (2003)
Pentland, A.S., Fletcher, R., Hasson, A.: Daknet: Rethinking connectivity in developing nations. Computer 37, 78–83 (2004)
Shah, R.C., Roy, S., Jain, S., Brunette, W.: Data mules: modeling and analysis of a three-tier architecture for sparse sensor networks. Ad Hoc Networks 1(2-3), 215–233 (2003)
Shen, C., Borkar, G., Rajagopalan, S., Jaikaeo, C.: Interrogation-based relay routing for ad hoc satellite networks. In: IEEE Globecom 2002, pp. 17–21 (2002)
Spyropoulos, T., Psounis, K., Raghavendra, C.S.: Spray and wait: an efficient routing scheme for intermittently connected mobile networks. In: ACM SIGCOMM Workshop on Delay-Tolerant Networking (WDTN), pp. 252–259. ACM, New York (2005)
Spyropoulos, T., Psounis, K., Raghavendra, C.S.: Efficient routing in intermittently connected mobile networks: the single-copy case. IEEE/ACM Trans. Netw. 16(1), 63–76 (2008)
Tang, J., Musolesi, M., Mascolo, C., Latora, V.: Characterising temporal distance and reachability in mobile and online social networks. SIGCOMM Comput. Commun. Rev. 40, 118–124 (2010)
Vahdat, A., Becker, D.: Epidemic routing for partially connected ad hoc networks. Technical Report CS-200006, Duke University (April 2000)
Wu, H., Fujimoto, R.M., Guensler, R., Hunter, M.: Mddv: a mobility-centric data dissemination algorithm for vehicular networks. In: Vehicular Ad Hoc Networks, pp. 47–56. ACM, New York (2004)
Zhang, Z.: Routing in intermittently connected mobile ad hoc networks and delay tolerant networks: Overview and challenges. IEEE Communications Surveys and Tutorials 8(1-4), 24–37 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brejová, B., Dobrev, S., Královič, R., Vinař, T. (2011). Routing in Carrier-Based Mobile Networks. In: Kosowski, A., Yamashita, M. (eds) Structural Information and Communication Complexity. SIROCCO 2011. Lecture Notes in Computer Science, vol 6796. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22212-2_20
Download citation
DOI: https://doi.org/10.1007/978-3-642-22212-2_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22211-5
Online ISBN: 978-3-642-22212-2
eBook Packages: Computer ScienceComputer Science (R0)