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

IEEE/CAA Journal of Automatica Sinica, vol. 8, pp. 1800–1816

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.

Authors 5

1. Yonghao Du Aachen Leiden Institute of Advanced Computer Science

   Leiden University · National University of Defense Technology

   Affiliation as printed

   College of Systems Engineering, National University of Defense Technology, Changsha, China

   Leiden Institute of Advanced Computer Science, Leiden University, Leiden, CA, The Netherlands

2. Ling Wang

   Tsinghua University

   Affiliation as printed

   Department of Automation, Tsinghua University, Beijing, China

3. Lining Xing

   National University of Defense Technology

   Affiliation as printed

   College of Systems Engineering, National University of Defense Technology, Changsha, China

4. Jungang Yan

   National University of Defense Technology

   Affiliation as printed

   College of Systems Engineering, National University of Defense Technology, Changsha, China

5. Mengsi Cai

   National University of Defense Technology

   Affiliation as printed

   College of Systems Engineering, National University of Defense Technology, Changsha, China