Scheduling model and heuristic algorithm for tracking and data relay satellite considering breakpoint transmission

LI Xiamiao; CHEN Xinjiang; WU Guohua; HE Chuan; LONG Yunjun

doi:10.7527/S1000-6893.2019.23233

ACTA AERONAUTICAET ASTRONAUTICA SINICA >

2019 , Vol. 40 >Issue 11: 323233 - 323233

DOI: https://doi.org/10.7527/S1000-6893.2019.23233

Electronics and Electrical Engineering and Control

Scheduling model and heuristic algorithm for tracking and data relay satellite considering breakpoint transmission

LI Xiamiao ,
CHEN Xinjiang ,
WU Guohua ,
HE Chuan ,
LONG Yunjun

Expand

1. School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China;
2. Beijing Space Information Relay Transmission Technology Research Center, Beijing 100094, China

Received date: 2019-06-21

Revised date: 2019-06-24

Online published: 2019-08-12

Supported by

Natural Science Fund for Distinguished Young Scholars of Hunan Province (2019JJ20026); National Natural Science Foundation of China (61603404)

Fold

Abstract

To improve the efficiency of the tracking and data relay systems and increase the completion rate of tracking and data relay tasks, this paper investigates the breakpoint transmission mode in the scheduling of the tracking and data relay satellites. In the breakpoint transmission mode, a single data transmission task can be reasonably split into several subtasks that can be completed in multiple time windows. First, a mathematical model of the scheduling problem of TDRSs is constructed. Second, a conflict degree calculation method based on conflict risk assessment is proposed, and a two-stage scheduling algorithm considering breakpoint transmission is further designed. Finally, a large number of simulation experiments are carried out. And the algorithm is compared with the greedy algorithm, the heuristic algorithm based on minimum conflict, and the heuristic algorithm based on task priority, which do not consider breakpoint transmission. The experimental results show that in contrast to the three comparative heuristic algorithms, the proposed method can improve the task completion rate by 7.67%, 6.34% and 8.67%.

Key words： satellite scheduling; breakpoint transmission; tracking and data relay satellite; conflict degree; heuristic algorithm

Cite this article

LI Xiamiao , CHEN Xinjiang , WU Guohua , HE Chuan , LONG Yunjun . Scheduling model and heuristic algorithm for tracking and data relay satellite considering breakpoint transmission[J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2019 , 40(11) : 323233 -323233 . DOI: 10.7527/S1000-6893.2019.23233

References

[1] BRANDEL D L, WATSON W A, WEINBERG A. NASA's advanced tracking and data relay satellite system for the years 2000 and beyond[J]. Proceedings of the IEEE, 1990, 78(7):1141-1151.
[2] 杨红俊. 国外数据中继卫星系统最新发展及未来趋势[J]. 电讯技术, 2016, 56(1):109-116. YANG H J. Latest development progress and trends of foreign data relay satellite systems[J]. Telecommunication Engineering, 2016, 56(1):109-116(in Chinese).
[3] TELES J, SAMII M V, DOLL C E. Overview of TDRSS[J]. Advances in Space Research, 1995, 16(12):67-76.
[4] ROJANASOONTHON S. Parallel machine scheduling with time windows[D]. Austin:University of Texas, 2004.
[5] GRAMLING J, CHRISSOTIMOS N. Three generations of NASA's tracking and data relay satellite system[C]//SpaceOps 2008 Conference. Reston, VA:AIAA, 2008.
[6] HEINE F, MVHLNIKEL G, ZECH H, et al. The European data relay system, high speed laser based data links[C]//Advanced Satellite Multimedia Systems Conference and the 13th Signal Processing for Space Communications Workshop (ASMS/SPSC). Piscataway, NJ:IEEE Press, 2014:284-286.
[7] ROJANASOONTHON S, BARD J F, REDDY S D. Algorithms for parallel machine scheduling:A case study of the tracking and data relay satellite system[J]. Journal of the Operational Research Society, 2003, 54(8):806-821.
[8] 方炎申, 陈英武,王军民. 中继卫星多址链路调度问题的约束规划模型及算法研究[J]. 航天返回与遥感, 2006, 27(4):62-67. FANG Y S, CHEN Y W, WANG J M. Constraint programming model and algorithms for multiple access links scheduling of Tracking and Data Relay Satellite System (TDRSS)[J]. Spacecraft Recovery & Remote Sensing, 2006, 27(4):62-67(in Chinese).
[9] 王志淋, 李新明. 跟踪与数据中继卫星系统资源调度优化问题[J]. 中国空间科学技术, 2015, 35(1):36-42. WANG Z L, LI X M. Resources scheduling optimization problem of the TDRSS[J]. Chinese Space Science and Technology, 2015, 35(1):36-42(in Chinese).
[10] HE L, LI J, SHENG M, et al. Dynamic scheduling of hybrid tasks with time windows in data relay satellite networks[J]. IEEE Transactions on Vehicular Technology, 2019, 68(5):4989-5004.
[11] WANG L, JIANG C, KUANG L, et al. Mission scheduling in space network with antenna dynamic setup times[J]. IEEE Transactions on Aerospace and Electronic Systems, 2019, 55(1):31-45.
[12] LIU R, SHENG M, XU C, et al. Antenna slewing time aware mission scheduling in space networks[J]. IEEE Communications Letters, 2017, 21(3):516-519.
[13] LIN P, KUANG L, CHEN X, et al. Adaptive subsequence adjustment with evolutionary asymmetric path-relinking for TDRSS scheduling[J]. Journal of Systems Engineering and Electronics, 2014, 25(5):800-810.
[14] 贺川,李亚晶,丘震. 按需申请模式下的中继卫星任务规划模型与算法设计[J]. 中国空间科学技术, 2017, 37(6):46-55. HE C, LI Y J, QIU Z. Task programming models and algorithms of tracking and data relay satellite in application-on-demand[J]. Chinese Space Science and Technology, 2017,37(6):46-55(in Chinese).
[15] 刘润滋,盛敏,唐成圆,等. 基于任务拆分聚合的中继卫星系统任务规划方法[J]. 通信学报, 2017, 38(z1):110-117. LIU R Z, SHENG M, TANG C Y, et al. Tasking planning based on task splitting and merging in relay satellite network[J]. Journal on Communications,2017, 38(z1):110-117(in Chinese).
[16] 顾中舜. 中继卫星动态调度问题建模及优化技术研究[D]. 长沙:国防科学技术大学, 2008. GU Z S. Research on the relay satellite dynamic scheduling problem modeling and optimizational technology[D]. Changsha:National University of Defense Technology, 2008(in Chinese).
[17] DENG B, JIANG C, KUANG L, et al. Two-phase task scheduling in data relay satellite systems[J]. IEEE Transactions on Vehicular Technology, 2018, 67(2):1782-1793.
[18] 开彩红,肖瑶,方青. 基于人工蜂群算法的中继卫星任务调度研究[J]. 电子与信息学报, 2015(10):2466-2474. KAI C H, XIAO Y, FANG Q. Relay satellite scheduling based on artificial bee colony algorithm[J]. Journal of Electronics and Information Technology, 2015(10):2466-2474(in Chinese).
[19] 王磊,匡麟玲,黄惠明. 基于时空特征的中继卫星系统业务模型[J]. 清华大学学报(自然科学版), 2017, 57(1):55-60. WANG L, KUANG L L, HUANG H M. TDRSS traffic model based on time and spatial characteristics[J]. Journal of Tsinghua University (Science and Technology), 2017, 57(1):55-60(in Chinese).
[20] NET M S, PORTILLO I D, CAMERON B G, et al. Architecting space communication networks under mission demand uncertainty[C]//Aerospace Conference. Piscataway, NJ:IEEE Press, 2015:1-10.
[21] FANG Y, CHEN Y. Constraint programming model of TDRSS single access link scheduling problem[C]//International Conference on Machine Learning & Cybernetics. Piscataway, NJ:IEEE Press, 2006:948-951.
[22] DU J, JIANG C, QIAN Y, et al. Resource allocation with video traffic prediction in cloud-based space systems[J]. IEEE Transactions On Multimedia, 2016, 18(5):820-830.
[23] DU J, JIANG C, GUO Q, et al. Cooperative earth observation through complex space information networks[J]. IEEE Wireless Communications, 2016, 23(2):136-144.
[24] ZHU X, JIANG C, KUANG L, et al. Non-orthogonal multiple access based integrated terrestrial-satellite networks[J]. IEEE Journal on Selected Areas in Communications, 2017, 35(10):2253-2267.
[25] HORAN S. Nontracking antenna performance for inertially controlled spacecraft using TDRSS[J]. IEEE Transactions on Aerospace and Electronic Systems, 2003, 39(4):1263-1269.
[26] ARCHETTI C, FEILLET D, GENDREAU M, et al. Complexity of the VRP and SDVRP[J]. Transportation Research Part C, 2011, 19(5):741-750.
[27] 王慧林,伍国华,马满好. 多类异构对地观测平台协同任务规划方法[J]. 航空学报, 2016, 37(3):997-1014. WANG H L,WU G H, MA M H. Coordinated task planning of heterogeneous earth-observation platforms[J]. Acta Aeronautica et Astronautica Sinica, 2016, 37(3):997-1014(in Chinese).
[28] 白保存,贺仁杰,李菊芳,等. 考虑任务合成的成像卫星调度问题[J]. 航空学报, 2009, 30(11):2165-2171. BAI B C, HE R J, LI J F, et al. Imaging satellite observation scheduling with task merging[J]. Acta Aeronautica et Astronautica Sinica, 2009, 30(11):2165-2171(in Chinese).
[29] BIANCHESSI N, RIGHINI G. Planning and scheduling algorithms for the COSMO-SkyMed constellation[J]. Aerospace Science and Technology, 2008, 12(7):535-544.
[30] ALMEIDA F, GIMÉNEZ D, LÓPEZ-ESPÍN J J, et al. Parameterized schemes of metaheuristics:Basic ideas and applications with genetic algorithms, scatter search, and GRASP[J]. IEEE Transactions On Systems, Man, and Cybernetics:Systems, 2013, 43(3):570-586.
[31] PEREA F, VAZQUEZ R, GALAN-VIOGUE J. Swath-acquisition planning in multiple-satellite missions:An exact and heuristic approach[J]. IEEE Transactions On Aerospace and Electronic Systems, 2015, 51(3):1717-1725.
[32] 何敏藩,朱燕麒,贾学卿. 考虑多滑动窗口的中继卫星调度模型及启发式算法[J]. 郑州大学学报(工学版), 2018, 39(5):11-21. HE M P, ZHU Y Q, JIA X Q. Scheduling model and heuristic algorithm for tracking and data relay satellite considering multiple slide windows[J]. Journal of Zhengzhou University(Engineering Science), 2018, 39(5):11-21(in Chinese).
[33] 郭超,熊伟,郝利云. 基于双层优先级的中继卫星系统任务调度算法[J]. 计算机应用研究, 2018, 35(5):1506-1510. GUO C, XIONG W, HAO L Y. Relay satellite system task scheduling algorithm based on double-layer priority[J]. Application Research of Computers,2018, 35(5):1506-1510(in Chinese).

Options

Outlines

模态框（Modal）标题

Abstract

Cite this article

References