A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Volume 8 Issue 11
Nov.  2021

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 7.847, Top 10% (SCI Q1)
    CiteScore: 13.0, Top 5% (Q1)
    Google Scholar h5-index: 51, TOP 8
Turn off MathJax
Article Contents
Yonghao Du, Ling Wang, Lining Xing, Jungang Yan and Mengsi 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: Yonghao Du, Ling Wang, Lining Xing, Jungang Yan and Mengsi 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

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

doi: 10.1109/JAS.2021.1004174
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
  • 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.

     

  • loading
  • [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.

Catalog

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

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

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(10)  / Tables(11)

    Article Metrics

    Article views (790) PDF downloads(36) Cited by()

    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)

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return