AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Complex System Modeling and Simulation Article
PDF (4.6 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

Multicommodity Flow Modeling for the Data Transmission Scheduling Problem in Navigation Satellite Systems

College of Systems Engineering, National University of Defense Technology, Changsha 410073, China
Department of Computer Science, KU Leuven, Kortrijk 8500, Belgium
Show Author Information

Abstract

Introducing InterSatellite Links (ISLs) is a major trend in new-generation Global Navigation Satellite Systems (GNSSs). Data transmission scheduling is a crucial problem in the study of ISL management. The existing research on intersatellite data transmission has not considered the capacities of ISL bandwidth. Thus, the current study is the first to describe the intersatellite data transmission scheduling problem with capacity restrictions in GNSSs. A model conversion strategy is designed to model the aforementioned problem as a length-bounded single-path multicommodity flow problem. An integer programming model is constructed to minimize the maximal sum of flows on each intersatellite edge; this minimization is equivalent to minimizing the maximal occupied ISL bandwidth. An iterated tree search algorithm is proposed to resolve the problem, and two ranking rules are designed to guide the search. Experiments based on the BeiDou satellite constellation are designed, and results demonstrate the effectiveness of the proposed model and algorithm.

Keywords

intersatellite linknavigation satellite systemdata transmissionmulticommodity flowtree search

References

[1]

Z. Yan, J. A. Fraire, K. Zhao, H. Yan, P. G. Madoery, W. Li, and H. Yang, Distributed contact plan design for GNSSs, IEEE Transactions on Aerospace Electronic Systems, vol. 56, no. 1, pp. 660–672, 2019.
Google Scholar
[2]

S. C. Fisher and K. Ghassemi, GPS IIF-the next generation, Proceedings of the IEEE, vol. 87, no. 1, pp. 24–47, 1999.
Crossref Google Scholar
[3]

D. Yang, J. Yang, and P. Xu, Timeslot scheduling of inter-satellite links based on a system of a narrow beam with time division, GPS Solutions, vol. 21, no. 3, pp. 999–1011, 2016.
Google Scholar
[4]

O. Luba, L. Boyd, A. Gower, and J. Crum, GPS III system operations concepts, IEEE Aerospace and Electronic Systems Magazine, vol. 20, no. 1, pp. 10–18, 2005.
Crossref Google Scholar
[5]
K. Maine, P. Anderson, and F. Bayuk, Communication architecture for GPS III, in Proc. of 2004 IEEE Aerospace Conference (IEEE Cat. No. 04TH8720), Big Sky, MT, USA, 2004, p. 1539.
[6]
Y. Wu, J. Yang, J. Chen, and J. Lin, Route analysis of satellite constellation based on directional crosslink with narrow-beam antenna, in Practical Applications of Intelligent Systems. Berlin, Germany: Springer, 2011, pp. 639-650.
[7]

F. A. Fernández, Inter-satellite ranging and inter-satellite communication links for enhancing GNSS satellite broadcast navigation data, Advances in Space Research, vol. 47, no. 5, pp. 786–801, 2011.
Crossref Google Scholar
[8]
B. Xu, D. Wang, W. Liu, and G. Sun, A hybrid navigation constellation inter-satellite link assignment algorithm for the integrated optimization of the inter-satellite observing and communication performance, in Proc. of China Satellite Navigation Conference (CSNC) 2015, Xi'an, China, 2015, pp. 283-296.
[9]
Z. Hou, X. Yi, Y. Zhao, and Y. Zhang, Data transfer problem in navigation satellite network based on agility link, in Proc. of China Satellite Navigation Conference (CSNC), https://doi.org/10.1007/978-981-10-4591-2_41, 2021.
[10]

X. Chu and Y. Chen, Time division inter-satellite link topology generation problem: Modeling and solution, International Journal of Satellite Communications and Networking, vol. 36, no. 2, pp. 194–206, 2018.
Crossref Google Scholar
[11]
H. Yan, Q. Zhang, Y. Sun, and J. Guo, Contact plan design for navigation satellite network based on simulated annealing, in Proc. of 2015 IEEE International Conference on Communication Software and Networks (ICCSN), Chengdu, China, 2015, pp. 12-16.
[12]
Z. Hou, X. Yi, Y. Zhao, C. Li, and Y. Xie, Contact plan design for navigation satellite network based on maximum matching, in Proceedings of the 2nd International Conference on Vision, Image and Signal Processing, New York, NY, USA, 2018, pp. 1-6.
[13]

L. Sun, Y. Wang, W. Huang, J. Yang, Y. Zhou, and D. Yang, Inter-satellite communication and ranging link assignment for navigation satellite systems, GPS Solutions, vol. 22, no. 2, p. 38, 2018.
Crossref Google Scholar
[14]

S. Liu, J. Yang, X. Guo, and L. Sun, Inter-satellite link assignment for the laser/radio hybrid network in navigation satellite systems, GPS Solutions, vol. 24, no. 2, pp. 24–49, 2020.
Google Scholar
[15]

H. S. Chang, B. W. Kim, C. G. Lee, S. L. Min, Y. Choi, H. S. Yang, D. N. Kim, and C. S. Kim, FSA-based link assignment and routing in low-earth orbit satellite networks, IEEE Transactions on Vehicular Technology, vol. 47, no. 3, pp. 1037–1048, 1998.
Crossref Google Scholar
[16]

K. Murota and A. Shioura, Dijkstra's algorithm and L-concave function maximization, Mathematical Programming, vol. 145, nos. 1&2, pp. 163–177, 2014.
Google Scholar
[17]
X. K. Jiang, H. J. Fan, and D. Kang, Optimization strategy based on shortest path algorithm of Dijkstra, in Proc. of 2nd International Conference on Communication Technology (ICCT), Melbourne, Australia, 2015, pp. 78-82.
[18]

H. Masri, S. Krichen, and A. Guitouni, A multi-start variable neighborhood search for solving the single path multicommodity flow problem, Applied Mathematics and Computation, vol. 251, pp. 132–142, 2015.
Crossref Google Scholar
[19]
J. M. Kleinberg, Approximation algorithms for disjoint paths problems, PhD dissertation, MIT, Cambridge, MA, USA, 1996.
[20]

F. Zhao, S. Di, J. Cao, J. Tang, and Jonrinaldi, A novel cooperative multi-stage hyper-heuristic for combination optimization problems, Complex System Modeling and Simulation, vol. 1, no. 2, pp. 91–108, 2021.
Crossref Google Scholar
[21]

W. Gong, Z. Liao, X. Mi, L. Wang, and Y. Guo, Nonlinear equations solving with intelligent optimization algorithms: A survey, Complex System Modeling and Simulation, vol. 1, no. 1, pp. 15–32, 2021.
Crossref Google Scholar
[22]

G. J. Oyewole and O. Adetunji, Solving the facility location and fixed charge solid transportation problem, Journal of Industrial and Management Optimization, vol. 17, no. 4, pp. 1557–1575, 2021.
Crossref Google Scholar
[23]

H. B. Zhu, Maximizing group performance while minimizing budget, IEEE Transactions on Systems Man Cybernetics-Systems, vol. 50, no. 2, pp. 633–645, 2020.
Crossref Google Scholar
Complex System Modeling and Simulation
Volume 1 Issue 3,
September 2021
Pages 232-241
DOI: 10.23919/CSMS.2021.0019
Cite this article:
Yan J, Xing L, Li C, et al. Multicommodity Flow Modeling for the Data Transmission Scheduling Problem in Navigation Satellite Systems. Complex System Modeling and Simulation, 2021, 1(3): 232-241. https://doi.org/10.23919/CSMS.2021.0019

704

Views

56

Downloads

7

Crossref

6

Scopus

Altmetrics
Received: 23 May 2021
Revised: 03 August 2021
Accepted: 29 August 2021
Published: 29 October 2021
© The author(s) 2021

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).
Return