{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,21]],"date-time":"2026-09-21T02:54:46Z","timestamp":1789959286660,"version":"4.0.1"},"reference-count":43,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2025,4,17]],"date-time":"2025-04-17T00:00:00Z","timestamp":1744848000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>Efficient data transmission in low Earth orbit (LEO) satellite networks is critical for supporting real-time global communication, Earth observation, and numerous data-intensive space missions. A fundamental challenge in these networks involves solving the maximum flow problem, which determines the optimal data throughput across highly dynamic topologies with limited onboard energy and data processing capability. Traditional algorithms often fall short in these environments due to their high computational costs and inability to adapt to frequent topological changes or fluctuating link capacities. This paper introduces an accelerated maximum flow algorithm specifically designed for dynamic LEO networks, leveraging a prediction-enhanced approach to improve both speed and adaptability. The proposed algorithm integrates a novel energy-time expanded graph (e-TEG) framework, which jointly models satellite-specific constraints including time-varying inter-satellite visibility, limited onboard processing capacities, and dynamic link capacities. In addition, a learning-augmented warm-start strategy is introduced to enhance the Ford\u2013Fulkerson algorithm. It generates near-optimal initial flows based on historical network states, which reduces the number of augmentation steps required and accelerates computation under dynamic conditions. Theoretical analyses confirm the correctness and time efficiency of the proposed approach. Evaluation results validate that the prediction-enhanced approach achieves up to a 32.2% reduction in computation time compared to conventional methods, particularly under varying storage capacity and network topologies. These results demonstrate the algorithm\u2019s potential to support high-throughput, efficient data transmission in future satellite communication systems.<\/jats:p>","DOI":"10.3390\/s25082555","type":"journal-article","created":{"date-parts":[[2025,4,17]],"date-time":"2025-04-17T20:05:56Z","timestamp":1744920356000},"page":"2555","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["An Accelerated Maximum Flow Algorithm with Prediction Enhancement in Dynamic LEO Networks"],"prefix":"10.3390","volume":"25","author":[{"given":"Jiayin","family":"Sheng","sequence":"first","affiliation":[{"name":"College of Computer and Information Engineering, Nanjing Tech University, Nanjing 211816, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1158-3366","authenticated-orcid":false,"given":"Xinjie","family":"Guan","sequence":"additional","affiliation":[{"name":"College of Computer and Information Engineering, Nanjing Tech University, Nanjing 211816, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fuliang","family":"Yang","sequence":"additional","affiliation":[{"name":"College of Computer and Information Engineering, Nanjing Tech University, Nanjing 211816, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xili","family":"Wan","sequence":"additional","affiliation":[{"name":"College of Computer and Information Engineering, Nanjing Tech University, Nanjing 211816, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2025,4,17]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Foreman, V.L., Siddiqi, A., and Weck, O.D. (2017, January 12\u201314). Large Satellite Constellation Orbital Debris Impacts: Case Studies of OneWeb and SpaceX Proposals. Proceedings of the AIAA SPACE and Astronautics Forum and Exposition, Orlando, FL, USA.","DOI":"10.2514\/6.2017-5200"},{"key":"ref_2","unstructured":"(2015, January 3\u20136). OneWeb-company. Oneweb constellation. Proceedings of the 2015 3rd IAPR Asian Conference on Pattern Recognition (ACPR), Kuala Lumpur, Malaysia."},{"key":"ref_3","first-page":"15","article-title":"Is Amazon Going to Dominate Space?","volume":"254","author":"Marks","year":"2022","journal-title":"NewScientist"},{"key":"ref_4","unstructured":"Union of Concerned Scientists (2025, April 08). UCS Satellite Database. Available online: https:\/\/www.ucs.org\/resources\/satellite-database."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"102409","DOI":"10.1016\/j.rineng.2024.102409","article-title":"Integration of 5G, 6G and IoT with Low Earth Orbit (LEO) networks: Opportunity, challenges and future trends","volume":"23","author":"Shayea","year":"2024","journal-title":"Results Eng."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Lin, H., Kishk, M.A., and Alouini, M.S. (2025). Connectivity of LEO Satellite Mega Constellations: An Application of Percolation Theory on a Sphere. arXiv.","DOI":"10.1109\/TAES.2025.3553461"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","article-title":"Maximal Flow Through a Network","volume":"8","author":"Ford","year":"1956","journal-title":"Can. J. Math."},{"key":"ref_8","first-page":"1277","article-title":"Algorithm for solution of a problem of maximum flow in networks with power estimation","volume":"11","author":"Dinic","year":"1970","journal-title":"Sov. Math Dokl."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"106487","DOI":"10.1016\/j.ipl.2024.106487","article-title":"Learning-augmented maximum flow","volume":"186","author":"Polak","year":"2024","journal-title":"Inf. Process. Lett."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"121692","DOI":"10.1016\/j.ins.2024.121692","article-title":"Intelligent congestion control of data transmission in low Earth orbit satellite networks based on reinforcement learning: Analysis and optimization","volume":"694","author":"Zhu","year":"2025","journal-title":"Inf. Sci."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Shi, K., Li, H., and Suo, L. (2021, January 21\u201324). Temporal Graph based Energy-limited Max-flow Routing over Satellite Networks. Proceedings of the 2021 IFIP Networking Conference (IFIP Networking), Espoo, Finland.","DOI":"10.23919\/IFIPNetworking52078.2021.9472794"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Kang, Y., Zhu, Y., Wang, D., and Han, Z. (2025). Efficient Path Selection Design for Large Scale LEO Satellite Constellations Using Graph Embedding-Based Reinforcement Learning. IEEE Trans. Netw. Sci. Eng., 1\u201314.","DOI":"10.1109\/TNSE.2025.3543161"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"360","DOI":"10.1109\/LWC.2018.2872996","article-title":"Time-Expanded Graph-Based Resource Allocation Over the Satellite Networks","volume":"8","author":"Wang","year":"2019","journal-title":"IEEE Wirel. Commun. Lett."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"3869","DOI":"10.1109\/JSAC.2016.2611860","article-title":"Towards Energy-Efficient Routing in Satellite Networks","volume":"34","author":"Yang","year":"2016","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"102498","DOI":"10.1016\/j.phycom.2024.102498","article-title":"Dynamic resource allocation for low earth orbit satellite networks","volume":"67","author":"Lu","year":"2024","journal-title":"Phys. Commun."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1145\/321694.321699","article-title":"Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems","volume":"19","author":"Edmonds","year":"1972","journal-title":"J. ACM"},{"key":"ref_17","unstructured":"Chen, J.Y., Silwal, S., Vakilian, A., and Zhang, F. (2022). Faster Fundamental Graph Algorithms via Learned Predictions. arXiv."},{"key":"ref_18","unstructured":"Sakaue, S., and Oki, T. (2022). Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictions. arXiv."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Lu, P., Ren, X., Sun, E., and Zhang, Y. (2021, January 11\u201312). Generalized Sorting with Predictions. Proceedings of the SIAM Symposium on Simplicity in Algorithms (SOSA 2021), Virtually.","DOI":"10.1137\/1.9781611976496.13"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"103302","DOI":"10.1016\/j.adhoc.2023.103302","article-title":"Realization of maximum flow in DTN and application in CGR","volume":"152","author":"Li","year":"2024","journal-title":"Ad Hoc Netw."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Spridon, D.E., Deaconu, A.M., and Tayyebi, J. (2025). Novel GPU-Based Method for the Generalized Maximum Flow Problem. Computation, 13.","DOI":"10.3390\/computation13020040"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Gupta, R., and Roughgarden, T. (2016, January 14\u201317). A PAC approach to application-specific algorithm selection. Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA.","DOI":"10.1145\/2840728.2840766"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Balcan, M.F., Deblasio, D., Dick, T., Kingsford, C., Sandholm, T., and Vitercik, E. (2021, January 21\u201325). How much data is sufficient to learn high-performing algorithms? generalization guarantees for data-driven algorithm design. Proceedings of the Symposium on the Theory of Computing, Rome, Italy.","DOI":"10.1145\/3406325.3451036"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Sherman, J. (2013, January 26\u201329). Nearly Maximum Flows in Nearly Linear Time. Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, Berkeley, CA, USA.","DOI":"10.1109\/FOCS.2013.36"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Kelner, J.A., Lee, Y.T., Orecchia, L., and Sidford, A. (2014, January 5\u20137). An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations. Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Portland, OR, USA.","DOI":"10.1137\/1.9781611973402.16"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Chen, L., Kyng, R., Liu, Y.P., Peng, R., Gutenberg, M.P., and Sachdeva, S. (November, January 31). Maximum flow and minimum-cost flow in almost-linear time. Proceedings of the 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), Denver, CO, USA.","DOI":"10.1109\/FOCS54457.2022.00064"},{"key":"ref_27","unstructured":"Altner, D., and Ergun, \u00d6. (2008). Rapidly solving an online sequence of maximum flow problems with extensions to computing robust minimum cuts. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems: 5th International Conference, CPAIOR 2008, Paris, France, May 20\u201323, 2008 Proceedings, Springer."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1109\/MCOM.2015.7060482","article-title":"Software Defined Networking and Virtualization for Broadband Satellite Networks","volume":"53","author":"Bertaux","year":"2015","journal-title":"IEEE Commun. Mag."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"812","DOI":"10.1109\/COMST.2018.2862350","article-title":"A survey on emerging SDN and NFV security mechanisms for IoT systems","volume":"21","author":"Farris","year":"2018","journal-title":"IEEE Commun. Surv. Tutor."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"1432","DOI":"10.1109\/TNSM.2020.2993400","article-title":"Design and Evaluation of Reconfigurable SDN LEO Constellations","volume":"17","author":"Papa","year":"2020","journal-title":"IEEE Trans. Netw. Serv. Manag."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/2740070.2631454","article-title":"OpenSAN: A software-defined satellite network architecture","volume":"44","author":"Bao","year":"2014","journal-title":"ACM SIGCOMM Comput. Commun. Rev."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Ayofe, O.A., Okafor, K.C., Longe, O.M., Alabi, C.A., Tekanyi, A.M.S., Usman, A.D., Musa, M.J., Abdullahi, Z.M., Agbon, E.E., and Adikpe, A.O. (2024). SDN-Based Integrated Satellite Terrestrial Cyber\u2013Physical Networks with 5G Resilience Infrastructure: Future Trends and Challenges. Technologies, 12.","DOI":"10.3390\/technologies12120263"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Kim, S., Park, J., Youn, J., Ahn, S., and Cho, S. (2024). Online Service Function Chain Planning for Satellite\u2013Ground Integrated Networks to Minimize End-to-End (E2E) Delay. Sensors, 24.","DOI":"10.3390\/s24227286"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Salau, A.O., and Beyene, M.M. (2024). Software defined networking based network traffic classification using machine learning techniques. Sci. Rep., 14.","DOI":"10.1038\/s41598-024-70983-6"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Yu, Q. (2018). Topology Analysis of Inter-Layer Links for LEO\/MEO Double-Layered Satellite Networks. Space Information Networks, Springer.","DOI":"10.1007\/978-981-10-7877-4"},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Wang, P., Sourav, S., Li, H., and Chen, B. (2023, January 17\u201320). One Pass is Sufficient: A Solver for Minimizing Data Delivery Time over Time-varying Networks. Proceedings of the IEEE INFOCOM 2023\u2014IEEE Conference on Computer Communications, New York, NY, USA.","DOI":"10.1109\/INFOCOM53939.2023.10228959"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"2202","DOI":"10.1109\/JSAC.2018.2869717","article-title":"Auction Design and Analysis for SDN-Based Traffic Offloading in Hybrid Satellite-Terrestrial Networks","volume":"36","author":"Du","year":"2018","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"454","DOI":"10.1109\/TCOMM.2024.3429166","article-title":"Iris: Toward Intelligent Reliable Routing for Software-Defined Satellite Networks","volume":"73","author":"Wei","year":"2025","journal-title":"IEEE Trans. Commun."},{"key":"ref_39","unstructured":"AGI (2025, April 08). Systems Tool Kit (stk). Available online: https:\/\/www.agi.com\/products\/stk."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Wang, C., Ren, Z., Cheng, W., Zheng, S., and Zhang, H. (April, January 29). Time-Expanded Graph-Based Dispersed Computing Policy for LEO Space Satellite Computing. Proceedings of the 2021 IEEE Wireless Communications and Networking Conference (WCNC), Nanjing, China.","DOI":"10.1109\/WCNC49053.2021.9417247"},{"key":"ref_41","first-page":"369","article-title":"Some circular orbit patterns providing continuous whole earth coverage","volume":"24","author":"Walker","year":"1971","journal-title":"J. Br. Interplanet. Soc."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Vallado, D., and Crawford, P. (2008, January 18\u201321). SGP4 orbit determination. Proceedings of the AIAA\/AAS Astrodynamics Specialist Conference and Exhibit, Honolulu, HI, USA.","DOI":"10.2514\/6.2008-6770"},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Gushchin, A., Walid, A., and Tang, A. (2015, January 21). Scalable routing in SDN-enabled networks with consolidated middleboxes. Proceedings of the 2015 ACM SIGCOMM Workshop on Hot Topics in Middleboxes and Network Function Virtualization, London, UK.","DOI":"10.1145\/2785989.2785999"}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/25\/8\/2555\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T17:16:51Z","timestamp":1760030211000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/25\/8\/2555"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,17]]},"references-count":43,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2025,4]]}},"alternative-id":["s25082555"],"URL":"https:\/\/doi.org\/10.3390\/s25082555","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,17]]}}}