Data-Driven Heuristic Assisted Memetic Algorithm for Efficient Inter-Satellite Link Scheduling in the BeiDou Navigation Satellite System

Yonghao Du; Ling Wang; Lining Xing; Jungang Yan; Mengsi Cai

doi:10.1109/JAS.2021.1004174

Volume 8 Issue 11

Nov. 2021

IEEE/CAA Journal of Automatica Sinica

JCR Impact Factor: 15.3, Top 1 (SCI Q1)

CiteScore: 23.5, Top 2% (Q1)
Google Scholar h5-index: 77， TOP 5

Turn off MathJax

Article Contents

Article Navigation > IEEE/CAA Journal of Automatica Sinica > 2021 > 8(11): 1800-1816

Y. H. Du, L. Wang, L. N. Xing, J. G. Yan, and M. S. Cai, "Data-Driven Heuristic Assisted Memetic Algorithm for Efficient Inter-Satellite Link Scheduling in the BeiDou Navigation Satellite System," IEEE/CAA J. Autom. Sinica, vol. 8, no. 11, pp. 1800-1816, Nov. 2021. doi: 10.1109/JAS.2021.1004174

Citation:

Y. H. Du, L. Wang, L. N. Xing, J. G. Yan, and M. S. Cai, "Data-Driven Heuristic Assisted Memetic Algorithm for Efficient Inter-Satellite Link Scheduling in the BeiDou Navigation Satellite System," IEEE/CAA J. Autom. Sinica, vol. 8, no. 11, pp. 1800-1816, Nov. 2021. doi: 10.1109/JAS.2021.1004174

Citation:

Y. H. Du, L. Wang, L. N. Xing, J. G. Yan, and M. S. Cai, "Data-Driven Heuristic Assisted Memetic Algorithm for Efficient Inter-Satellite Link Scheduling in the BeiDou Navigation Satellite System," IEEE/CAA J. Autom. Sinica, vol. 8, no. 11, pp. 1800-1816, Nov. 2021. doi: 10.1109/JAS.2021.1004174

PDF( 1386 KB)

Data-Driven Heuristic Assisted Memetic Algorithm for Efficient Inter-Satellite Link Scheduling in the BeiDou Navigation Satellite System

doi: 10.1109/JAS.2021.1004174

Yonghao Du^{1, 2
,},
Ling Wang^3
,,
Lining Xing^{4
,
,},
Jungang Yan^4
,,
Mengsi Cai^4
,

1.
College of Systems Engineering, National University of Defense Technology, Changsha 410073, China
2.
Leiden Institute of Advanced Computer Science, Leiden University, Leiden 2332 CA, The Netherlands
3.
Department of Automation, Tsinghua University, Beijing 100083, China
4.
College of Systems Engineering, National University of Defense Technology, Changsha 410073, China

Funds: This work was supported by the National Natural Science Foundation of China (61773120), the National Natural Science Fund for Distinguished Young Scholars of China (61525304), the Foundation for the Author of National Excellent Doctoral Dissertation of China (2014-92), the Hunan Postgraduate Research Innovation Project (CX2018B022), and the China Scholarship Council-Leiden University Scholarship

More Information

Author Bio:
Yonghao Du received the B.S. degree in civil engineering from the Southeast University in 2015, and the M.S. degree in traffic and transportation engineering from the National University of Defense Technology in 2017, where he is currently working toward the Ph.D. degree in management science with the College of Systems Engineering. His research interests include intelligent optimization, resource scheduling, and mission planning

Ling Wang received the B.Sc. degree in automation and the Ph.D. degree in control theory and control engineering from Tsinghua University in 1995 and 1999, respectively. Since 1999, he has been with the Department of Automation, Tsinghua University, where he became a Full Professor in 2008. He has authored 5 academic books and over 260 refereed papers. His current research interests include intelligent optimization and production scheduling. Prof. Wang was a Recipient of the National Natural Science Fund for Distinguished Young Scholars of China, the National Natural Science Award (Second Place) in 2014, the Science and Technology Award of Beijing City in 2008, and the Natural Science Award (First Place in 2003 and Second Place in 2007) nominated by the Ministry of Education of China. He is currently the Editor-in-Chief of the International Journal of Automation and Control and an Associate Editor of the IEEE Transactions on Evolutionary Computation

Lining Xing received the double B.S. degrees in economics and science from Xi’an Jiaotong University in 2002, and the Ph.D. degree in management science from the National University of Defense Technology in 2009. He is currently a Professor with the College of Systems Engineering, National University of Defense Technology. His research interests include intelligent optimization, resource scheduling, and mission planning. Prof. Xing was the Recipient of the National Excellent Ph.D. Dissertation of China Award, in 2014, the Excellent Talent Support Program in New Century from the Ministry of Education, China, and the Funds for Distinguished Young Scientists from the Natural Science Foundation of Hunan

Jungang Yan received the B.S. degree and M.S. degree in management science and engineering from the National University of Defense Technology in 2014 and 2016, respectively, where he is currently working toward the Ph.D. degree in management science and engineering with the College of Systems Engineering. His research interests include intelligent optimization, inter-satellite link scheduling, and path planning

Mengsi Cai received the B.E. degree and M.E. degree in information science from the Xiangtan University in 2014 and 2017, respectively. She is currently working toward the Ph.D. degree in management science and engineering with the College of Systems Engineering, National University of Defense Technology. Her research interests include data mining, natural language processing, and complex networks
Corresponding author: Lining Xing, e-mail: xinglining@gmail.com
Received Date: 2020-10-27
Accepted Date: 2020-12-16

Available Online: 2021-01-15

Abstract

Abstract

Inter-satellite link (ISL) scheduling is required by the BeiDou Navigation Satellite System (BDS) to guarantee the system ranging and communication performance. In the BDS, a great number of ISL scheduling instances must be addressed every day, which will certainly spend a lot of time via normal metaheuristics and hardly meet the quick-response requirements that often occur in real-world applications. To address the dual requirements of normal and quick-response ISL schedulings, a data-driven heuristic assisted memetic algorithm (DHMA) is proposed in this paper, which includes a high-performance memetic algorithm (MA) and a data-driven heuristic. In normal situations, the high-performance MA that hybridizes parallelism, competition, and evolution strategies is performed for high-quality ISL scheduling solutions over time. When in quick-response situations, the data-driven heuristic is performed to quickly schedule high-probability ISLs according to a prediction model, which is trained from the high-quality MA solutions. The main idea of the DHMA is to address normal and quick-response schedulings separately, while high-quality normal scheduling data are trained for quick-response use. In addition, this paper also presents an easy-to-understand ISL scheduling model and its NP-completeness. A seven-day experimental study with 10 080 one-minute ISL scheduling instances shows the efficient performance of the DHMA in addressing the ISL scheduling in normal (in 84 hours) and quick-response (in 0.62 hour) situations, which can well meet the dual scheduling requirements in real-world BDS applications.
- BeiDou Navigation Satellite System (BDS),
- data-driven heuristic,
- inter-satellite link (ISL) scheduling,
- memetic algorithm,
- metaheuristic,
- quick-response

FullText(HTML)

References(45)

References

[1]	The BDS-3 constellation deployment is fully completed six months ahead of schedule UNOOSA sends a congratulation letter. [Online]. (23/06/2020) Available: http://en.beidou.gov.cn/WHATSNEWS/202006/t20200623_20692.html
[2]	BeiDou Navigation Satellite System. [Online]. (23/06/2020) Available: http://en.beidou.gov.cn/SYSTEMS/System.
[3]	S. C. Fisher and K. Ghassemi, “GPS IIF-the next generation,” Proc. IEEE, vol. 87, no. 1, pp. 24–47, 1999. doi: 10.1109/5.736340
[4]	L. Y. Sun, Y. K. Wang, W. D. Huang, J. Yang, Y. F. Zhou, and D. N. Yang, “Inter-satellite communication and ranging link assignment for navigation satellite systems,” GPS Solut., vol. 22, no. 2, 2018. doi: 10.1007/s10291-018-0704-3
[5]	L. Y. Sun, W. D. Huang, Y. F. Zhou, J. Yang, and Y. K. Wang, “Monitor link assignment for reentry users based on BeiDou inter-satellite links,” Adv. Space Res., vol. 64, no. 3, pp. 747–758, 2019. doi: 10.1016/j.asr.2019.05.015
[6]	F. A. Fernández, “Inter-satellite ranging and inter-satellite communication links for enhancing GNSS satellite broadcast navigation data,” Adv. Space Res., vol. 47, no. 5, pp. 786–801, 2011. doi: 10.1016/j.asr.2010.10.002
[7]	X. W. Wang, G. H. Wu, L. N. Xing, and W. Pedrycz, “Agile earth observation satellite scheduling over 20 years: Formulations, methods and future directions,” IEEE Syst. J., 2020. DOI: 10.1109/JSYST.2020.2997050
[8]	Y. H. Du, L. N. Xing, F. Yao, and Y. G. Chen, “Survey on models, algorithms and general techniques for spacecraft mission scheduling, ” Acta Autom. Sinica, 2020. DOI: 10.16383/j.aas.c190656.
[9]	S. Xiang, Y. G. Chen, G. L. Li, and L. N. Xing, “Review on satellite autonomous and collaborative task scheduling planning,” Acta Autom. Sinica, vol. 45, no. 2, pp. 252–264, 2019.
[10]	D. N. Yang, J. Yang, and P. J. Xu, “Timeslot scheduling of inter-satellite links based on a system of a narrow beam with time division,” GPS Solut., vol. 21, no. 3, pp. 999–1011, 2017. doi: 10.1007/s10291-016-0587-0
[11]	S. Y. Liu, J. Yang, X. Y. Guo, and L. Y. Sun, “Inter-satellite link assignment for the laser/radio hybrid network in navigation satellite systems,” GPS Solut., vol. 24, no. 2, p. 49, 2020.
[12]	T. J. Zhang, L. K. Ke, J. S. Li, J. Li, Z. X. Li, and J. Q. Huang, “Fireworks algorithm for the satellite link scheduling problem in the navigation constellation,” in Proc. IEEE Congr. Evolutionary Computation, Vancouver, Canada, 2016, pp. 4029–4037.
[13]	L. Wang, C. X. Jiang, L. L. Kuang, S. Wu, and S. Guo, “TDRSS scheduling algorithm for non-uniform time-space distributed missions,” in Proc. IEEE Global Communications Conf., Singapore, 2017, pp. 1–6.
[14]	J. H. Huang, Y. X. Su, W. X. Liu, and F. X. Wang, “Optimization design of inter-satellite link (ISL) assignment parameters in GNSS based on genetic algorithm,” Adv. Space Res., vol. 60, no. 12, pp. 2574–2580, 2017. doi: 10.1016/j.asr.2016.12.027
[15]	X. G. Chu and Y. W. Chen, “Time division inter-satellite link topology generation problem: Modeling and solution,” Int. J. Satell. Comm. N., vol. 36, no. 2, pp. 194–206, 2018. doi: 10.1002/sat.1212
[16]	M. J. Dong, B. J. Lin, Y. C. Liu, and L. S. Zhou, “Topology dynamic optimization for inter-satellite laser links of navigation satellite based on MOSA,” China Laser, vol. 45, no. 7, pp. 217–228, 2018.
[17]	S. Liu, G. Q. Bai, and Y. W. Chen, “Prediction method for imaging task schedulability of earth observing network,” J. Astronaut., vol. 36, no. 5, pp. 583–588, 2015.
[18]	L. N. Xing, Y. Wang, Y. M. He, and L. He, “An earth observation satellite task schedulability prediction method based on BP artificial network,” Chinese J. Manage. Sci., vol. 23, no. s1, pp. 117–124, 2015.
[19]	Y. H. Du, T. Wang, B. Xin, L. Wang, Y. G. Chen, and L. N. Xing, “A data-driven parallel scheduling approach for multiple agile earth observation satellites,” IEEE Trans. Evol. Comput., vol. 24, no. 4, pp. 679–693, 2020. doi: 10.1109/TEVC.2019.2934148
[20]	Y. J. Song, Z. Y. Zhou, Z. S. Zhang, F. Yao, and Y. W. Chen, “A framework involving MEC: Imaging satellites mission planning,” Neural Comput. Appl., vol. 32, pp. 15329–15340, 2020. doi: 10.1007/s00521-019-04047-6
[21]	L. Wang and J. W. Lu, “A memetic algorithm with competition for the capacitated green vehicle routing problem,” IEEE/CAA J. Autom. Sinica, vol. 6, no. 2, pp. 516–526, 2019. doi: 10.1109/JAS.2019.1911405
[22]	Y. Yu, S. C. Gao, Y. R. Wang, and Y. Todo, “Global optimum-based search differential evolution,” IEEE/CAA J. Autom. Sinica, vol. 6, no. 2, pp. 379–394, 2019. doi: 10.1109/JAS.2019.1911378
[23]	Y. H. Du, L. N. Xing, J. W. Zhang, Y. G. Chen, and Y. M. He, “MOEA based memetic algorithms for multi-objective satellite range scheduling problem,” Swarm Evol. Comput., vol. 50, 2019. doi: 10.1016/j.swevo.2019.100576
[24]	T. Huang, Y. J. Gong, S. Kwong, H. Wang, and J. Zhang, “A niching memetic algorithm for multi-solution traveling salesman problem,” IEEE Trans. Evol. Comput., vol. 24, no. 3, pp. 508–522, Jun. 2020.
[25]	A. V. Eremeev and Y. V. Kovalenko, “A memetic algorithm with optimal recombination for the asymmetric travelling salesman problem,” Memet. Comput., vol. 12, no. 1, pp. 23–36, 2020. doi: 10.1007/s12293-019-00291-4
[26]	L. Wang, S. Y. Wang, and X. L. Zheng, “A hybrid estimation of distribution algorithm for unrelated parallel machine scheduling with sequence-dependent setup times,” IEEE/CAA J. Autom. Sinica, vol. 3, no. 3, pp. 235–246, 2016. doi: 10.1109/JAS.2016.7508797
[27]	J. Deng, L. Wang, S. Y. Wang, and X. L. Zheng, “A competitive memetic algorithm for the distributed two-stage assembly flow-shop scheduling problem,” Int. J. Prod. Res., vol. 54, no. 12, pp. 3561–3577, 2016. doi: 10.1080/00207543.2015.1084063
[28]	J. Deng and L. Wang, “A competitive memetic algorithm for multi-objective distributed permutation flow shop scheduling problem,” Swarm Evol. Comput., vol. 32, pp. 121–131, 2017. doi: 10.1016/j.swevo.2016.06.002
[29]	H. E. Kiziloz and T. Dokeroglu, “A robust and cooperative parallel Tabu search algorithm for the maximum vertex weight clique problem,” Comput. Ind. Eng., vol. 118, pp. 54–66, 2018. doi: 10.1016/j.cie.2018.02.018
[30]	L. G. B. Ruíz, M. I. Capel, and M. C. Pegalajar, “Parallel memetic algorithm for training recurrent neural networks for the energy efficiency problem,” Appl. Soft Comput., vol. 76, pp. 356–368, 2019. doi: 10.1016/j.asoc.2018.12.028
[31]	U. Pferschy and J. Schauer, “Approximation of knapsack problems with conflict and forcing graphs,” J. Comb. Optim., vol. 33, no. 4, pp. 1300–1323, 2017. doi: 10.1007/s10878-016-0035-7
[32]	Z. Y. Zhao, S. X. Liu, M. C. Zhou, X. W. Guo, and L. Qi, “Decomposition method for new single-machine scheduling problems from steel production systems,” IEEE Trans. Autom. Sci. Eng., vol. 17, no. 3, pp. 1376–1387, 2020.
[33]	K. Z. Gao, Z. G. Cao, L. Zhang, Z. H. Chen, Y. Y. Han, and Q. K. Pan, “A review on swarm intelligence and evolutionary algorithms for solving flexible job shop scheduling problems,” IEEE/CAA J. Autom. Sinica, vol. 6, no. 4, pp. 904–916, 2019. doi: 10.1109/JAS.2019.1911540
[34]	H. T. Yuan, M. C. Zhou, Q. Liu, and A. Abusorrah, “Fine-grained resource provisioning and task scheduling for heterogeneous applications in distributed green clouds,” IEEE/CAA J. Autom. Sinica, vol. 7, no. 5, pp. 1380–1393, 2020.
[35]	Z. Zhao, S. Liu, M. C. Zhou, D. You, and X. Guo, “Heuristic scheduling of batch production processes based on petri nets and iterated greedy algorithms,” IEEE Trans. Autom. Sci. Eng., 2020. DOI: 10.1109/TASE.2020.3027532.
[36]	G. S. Peng, R. Dewil, C. Verbeeck, A. Gunawan, L. N. Xing, and P. Vansteenwegen, “Agile earth observation satellite scheduling: An orienteering problem with time-dependent profits and travel times,” Comput. Oper. Res., vol. 111, pp. 84–98, 2019. doi: 10.1016/j.cor.2019.05.030
[37]	L. He, X. L. Liu, G. Laporte, Y. W. Chen, and Y. G. Chen, “An improved adaptive large neighborhood search algorithm for multiple agile satellites scheduling,” Comput. Oper. Res., vol. 100, pp. 12–25, 2018. doi: 10.1016/j.cor.2018.06.020
[38]	L. He, M. de Weerdt, and N. Yorke-Smith, “Time/sequence-dependent scheduling: The design and evaluation of a general purpose Tabu-based adaptive large neighbourhood search algorithm,” J. Intell. Manuf., vol. 31, pp. 1051–1078, 2020. doi: 10.1007/s10845-019-01518-4
[39]	T. Q. Chen and C. Guestrin, “XGBoost: A scalable tree boosting system,” in Proc. 22nd ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, San Francisco, USA, 2016, pp. 785–794.
[40]	J. C. Zhong, Y. S. Sun, W. Peng, M. Z. Xie, J. H. Yang, and X. W. Tang, “XGBFEMF: An XGBoost-based framework for essential protein prediction,” IEEE Trans. NanoBiosci., vol. 17, no. 3, pp. 243–250, 2018. doi: 10.1109/TNB.2018.2842219
[41]	H. Nguyen, X. N. Bui, H. B. Bui, and D. T. Cuong, “Developing an XGBoost model to predict blast-induced peak particle velocity in an open-pit mine: A case study,” Acta Geophys., vol. 67, no. 2, pp. 477–490, 2019. doi: 10.1007/s11600-019-00268-4
[42]	W. J. Zhu, X. K. Liu, M. L. Xu, and H. M. Wu, “Predicting the results of RNA molecular specific hybridization using machine learning,” IEEE/CAA J. Autom. Sinica, vol. 6, no. 6, pp. 1384–1396, 2019. doi: 10.1109/JAS.2019.1911756
[43]	A. Samat, E. Li, W. Wang, S. Liu, C. Lin, and J. Abuduwaili, “Me-ta-XGBoost for hyperspectral image classification using extended MSER-guided morphological profiles,” Remote Sensing, vol. 12, no. 12, p. 1973, 2020.
[44]	S. Raschka and V. Mirjalili, Python Machine Learning, Packt Publishing Ltd, 2017.
[45]	D. C. Montgomery, Design and Analysis of Experiments, John Wiley & Sons, 2017.

Supplements(0)

Cited By

Proportional views

Proportional views

通讯作者: 陈斌, bchen63@163.com

1.
沈阳化工大学材料科学与工程学院沈阳 110142

Figures(10) / Tables(11)

Get Citation

PDF

XML

Article Metrics

Article views (986) PDF downloads(59)

Highlights

A well-designed framework to address both normal and quick-response ISL scheduling
A high-performance memetic algorithm via multi-strategies for normal ISL scheduling
A quick data-driven heuristic via probability prediction for quick ISL scheduling
An easy-to-understand ISL scheduling model and its NP-completeness
Efficient performance of our algorithm in a seven-day experiment (10,080 instances)

Data-Driven Heuristic Assisted Memetic Algorithm for Efficient Inter-Satellite Link Scheduling in the BeiDou Navigation Satellite System

doi: 10.1109/JAS.2021.1004174

Abstract

References

Proportional views

Catalog

通讯作者: 陈斌, bchen63@163.com

Article Metrics

Highlights

Export File

Citation

Format

Content