Abstract
Deep space networks, satellite networks, ad hoc networks, and the Internet can be modeled as DTNs (Delay Tolerant Networks). As a fundamental problem, the maximum flow problem is of vital importance for routing and service scheduling in networks. However, there exists no permanent end-to-end path since the topology and the characteristics of links are time-variant, resulting in a crucial maximum flow problem in DTNs. In this paper, we focus on the single-source-single-sink maximum flow problem of buffer-limited DTNs, followed by a valid algorithm to solve it. First, the BTAG (Buffer-limited Time Aggregated Graph) is constructed for modeling the buffer-limited DTN. Then, on the basis of BTAG, the two-way cache transfer series and the relevant transfer rules are designed, and thus a BTAG-based maximum flow algorithm is proposed to solve the maximum flow problem in buffer-limited DTNs. Finally, a numerical example is given to demonstrate the effectiveness of the proposed algorithm.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
C. Caini, H. Cruickshank, S. Farrell, et al. Delay- and disruption-tolerant networking (DTN): an alternative solution for future satellite networking applications [J]. Proceedings of the IEEE, 2011, 99(11): 1980–1997.
J. Fraire, J. M. Finochiett. Routing-aware fair contact plan design for predictable delay tolerant networks [J]. Adhoc networks, 2015, 25:303–313.
Y. Lu, X. Li, Y. T. Yu, et al. Information-centric delay-tolerant mobile ad-hoc networks [C]//IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), Toronto, Canada, 2014:428–433.
H. L. Chen, W. Lou. On protecting end-to-end location privacy against local eavesdropper in wireless sensor networks [J]. Pervasive and Mobile Computing, 2015, 16(Part A): 36–50.
M. Auzias, Y. Mah´eo, F. Raimbault. CoAp over BP for a delay-tolerant Internet of Things [C]//The 3rd International Conference on Future Internet of Things and Cloud (FiCloud), Rome, Italy, 2015:118–123.
J. Rodrigues, V. Soares. Advances in Delay-Tolerant Networks (DTNs) [M]. Oxford: Woodhead Publishing, 2015:1–21.
M. Werner. A dynamic routing concept for atm-based satellite personal communication networks [J]. IEEE journal on selected areas in communications, 1997, 15(8): 1636–1648.
E. Köhler, K. Langkau, M. Skutella. Time-expanded graphs for flow-dependent transit times [C]//European Symposium on Algorithms, Berlin, Germany, 2002:599–611.
A. Ferrira. Building a reference combinatorial model for MANETs [J]. IEEE network, 2004, 18(5): 24–29.
B. George, S. Kim, S. Shekhar. Spatio-temporal network databases and routing algorithms: a summary of results [C]//International Symposium on Spatial and Temporal Databases, Berlin, Germany, 2007:460–477.
B. George, S. Shekhar. Time-aggregated graphs for modeling spatio-temporal networks [C]//Journal on Data Semantics XI, Berlin, Germany, 2008:191–212.
L. R. Ford, D. R. Fulkerson. Flows in networks [M]. Princeton: Princeton University Press, 1962.
Author information
Authors and Affiliations
Corresponding author
Additional information
This work is supported by the National Science Foundation (Nos. 91338115, 61231008), National S&T Major Project (No. 2015ZX03002006), the Fundamental Research Funds for the Central Universities (Nos. WRYB142208, JB140117), Shanghai Aerospace Science and Technology Innovation Fund (No. 201454), the 111 Project (No. B08038).
Tao Zhang received the B.Eng. degree in telecommunication engineering from HeFei University of Technology, Hefei, China, in 2015. He is currently pursuing the Ph.D. degree with the State Key Laboratory of Integrated Service Networks, Institute of Information and Science, Xidian University, Xi'an. His research interests include integration of heterogeneous networks, routing algorithm design and spatial information networks.
Songfeng Deng received the M.Eng. degree in signal and information processing from University of Electronic Science and Technology of China, Chengdu, China, in 2007. He is currently working in Shanghai Institute of Aerospace Electronic Technology, Shanghai. His research interests include spatial image processing technology, application design of space network technology, etc.
Hongyan Li [corresponding author] received the M.S. degree in control engineering from Xi'an Jiaotong University, Xi'an, China, in 1991 and the Ph.D. degree in signal and information processing from Xidian University, Xi'an, in 2000. She is currently a professor with the State Key Laboratory of Integrated Service Networks, Xidian University. Her research interests include spatial information networks, cognitive networks, integration of heterogeneous networks, and mobile ad hoc networks.
Ronghui Hou received the B.Eng., M.Eng., and Ph.D. degrees in communication engineering from Northwestern Polytechnical University, Xi'an, China, in 2002, 2005, and 2007, respectively. She is currently a professor with the State Key Laboratory of Integrated Service Networks, Xidian University. Her research interests include spatial information networks, network quality-of-service issues, routing algorithm design, and wireless networks.
Haichao Zhang received the B.Eng. degree in telecommunication engineering from HeFei University of Technology, Hefei, China, in 2016. She is currently pursuing the M.S. degree with the State Key Laboratory of Integrated Service Networks, Institute of Information and Science, Xidian University, Xi’an. her research interests include spatial information networks and routing algorithm design.
Rights and permissions
About this article
Cite this article
Zhang, T., Deng, S., Li, H. et al. A maximum flow algorithm for buffer-limited delay tolerant networks. J. Commun. Inf. Netw. 2, 52–60 (2017). https://doi.org/10.1007/s41650-017-0016-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s41650-017-0016-8