考虑断点续传的中继卫星调度模型及启发式算法

doi:10.7527/S1000-6893.2019.23233

电子电气工程与控制

本期目录 | 过刊浏览 | 高级检索

前一篇 | 后一篇

考虑断点续传的中继卫星调度模型及启发式算法

李夏苗¹, 陈新江¹, 伍国华¹, 贺川², 龙运军²

1. 中南大学交通运输工程学院, 长沙 410075;
2. 北京空间信息中继传输技术研究中心, 北京 100094

收稿日期:2019-06-21 修回日期:2019-06-24 出版日期:2019-12-03 发布日期:2019-08-12
通讯作者: 伍国华 E-mail:guohuawu@csu.edu.cn
基金资助:
湖南省自然科学杰出青年基金（2019JJ20026）；国家自然科学基金青年基金（61603404）

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

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

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:2019-06-21 Revised:2019-06-24 Online:2019-12-03 Published:2019-08-12
Supported by:
Natural Science Fund for Distinguished Young Scholars of Hunan Province (2019JJ20026); National Natural Science Foundation of China (61603404)

摘要/Abstract

摘要： 为提高中继卫星系统的应用效能及数传任务的完成率，在中继卫星调度中考虑了断点续传这一应用模式，即对单个数传任务进行合理拆分，使其在多个时间窗口内完成。首先构建面向断点续传的中继卫星单址天线的调度模型，然后提出一种基于冲突风险评估的冲突度量化方法，并设计考虑断点续传的两阶段调度算法。最后开展大量的仿真实验将该算法与贪婪算法、基于最小冲突度的启发式算法和基于任务优先级的启发式算法这3个不考虑断点续传的算法进行对比。实验结果表明，所提出的算法在任务完成率方面分别提高了7.67%、6.34%和8.67%。

关键词: 卫星调度, 断点续传, 中继卫星, 冲突度, 启发式算法

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

中图分类号:

V19
TP278

李夏苗, 陈新江, 伍国华, 贺川, 龙运军. 考虑断点续传的中继卫星调度模型及启发式算法[J]. 航空学报, 2019, 40(11): 323233-323233.

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.

参考文献 33

[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).

E-mail：hkxb@buaa.edu.cn

关于我们

期刊社服务

专业学科

封面文章

友情链接

主管单位：中国科学技术协会主办单位：中国航空学会北京航空航天大学

考虑断点续传的中继卫星调度模型及启发式算法

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

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献 33

相关文章 10

编辑推荐

Metrics

本文评价

[1]	伍国华, 王天宇. 基于自适应模拟退火的大规模星座测控资源调度算法[J]. 航空学报, 2023, 44(12): 327759-327759.
[2]	芦方旭, 米志超, 马骏, 李艾静, 王海. 基于势博弈的多QoS无人机基站空间优化部署[J]. 航空学报, 2022, 43(9): 326137-326137.
[3]	王通, 黄攀峰, 董刚奇. 启发式多无人机协同路网持续监视轨迹规划[J]. 航空学报, 2020, 41(S1): 723753-723753.
[4]	王建江, 朱晓敏, 吴朝波, 邱涤珊. 面向应急条件的多星动态调度方法[J]. 航空学报, 2013, 34(5): 1151-1164.
[5]	张光宇, 李庆民, 李华. 零备件的多点库存单向转运模型与算法[J]. 航空学报, 2013, 34(5): 1092-1100.
[6]	薛羽, 庄毅, 张友益, 倪思如, 赵学健. 基于启发式自适应离散差分进化算法的多UCAV协同干扰空战决策[J]. 航空学报, 2013, 34(2): 343-351.
[7]	伍国华, 马满好, 王慧林, 邱涤珊. 基于任务聚类的多星观测调度方法[J]. 航空学报, 2011, 32(7): 1275-1282.
[8]	孙小松;耿云海;杨涤. 中继卫星H_∞姿态稳定控制研究[J]. 航空学报, 2006, 27(3): 468-474.
[9]	孙小松;杨涤;耿云海;杨旭. 中继卫星天线指向控制策略研究[J]. 航空学报, 2004, 25(4): 376-380.
[10]	周泓;冯允成. 一种启发式混合遗传算法及其在车间作业排序问题中的应用[J]. 航空学报, 1998, 19(1): 74-77.