基于滚动时域策略的中继卫星多目标动态调度优化方法
收稿日期: 2023-10-12
修回日期: 2023-10-28
录用日期: 2023-12-22
网络出版日期: 2024-01-11
基金资助
国家自然科学基金(62073341)
Multi⁃objective dynamic scheduling optimization method for relay satellites based on rolling horizon strategy
Received date: 2023-10-12
Revised date: 2023-10-28
Accepted date: 2023-12-22
Online published: 2024-01-11
Supported by
National Natural Science Foundation of China(62073341)
为提高中继卫星系统应对突发状况的能力，提出了基于滚动时域策略的中继卫星动态调度方法，将复杂动态调度过程分解为数个静态调度子问题，同时根据中继卫星动态调度需求，设计了多目标优化算法对子问题进行求解。首先构建了以最大任务完成率和最小调度方案调整幅度为优化目标的中继卫星动态调度模型，然后基于动态调度特性提出了动态任务调度方法，该方法采用周期和事件驱动的混合重调度机制，将调度过程分成多个调度区间，在每个区间内利用自适应邻域搜索的多目标进化算法对窗口任务进行调度。为了验证所提出的动态调度模式及算法的有效性，开展了大量仿真实验。实验结果证明了所提方法在解决中继卫星动态调度问题方面的优越性，与前沿的多目标优化方法NSGA-Ⅱ、MDSA-NSGA-Ⅱ和MODJA相比，本文设计的算法能生成更高质量的解。
李恒伟 , 罗启章 , 顾轶 , 范才智 , 伍国华 . 基于滚动时域策略的中继卫星多目标动态调度优化方法[J]. 航空学报, 2024 , 45(16) : 329706 -329706 . DOI: 10.7527/S1000-6893.2023.29706
To improve the ability of responding to emergencies in the scheduling of relay satellite system， a dynamic scheduling model is proposed based on the rolling horizon strategy in this paper， which decomposes the complex dynamic scheduling process into several static scheduling subproblems. A multi-objective optimization algorithm is designed to solve the subproblems according to the demand for dynamic scheduling of the relay satellite. Firstly， a dynamic scheduling model for the relay satellite is constructed to obtain the maximum task completion rate and the minimum adjustment range of scheduling scheme. Then， based on dynamic scheduling characteristics， a dynamic task scheduling method is proposed. The method adopts a hybrid rescheduling mechanism based on cycle and event-driven， divides the scheduling process into scheduling intervals， and uses a multi-objective evolutionary algorithm based on adaptive neighborhood search to schedule the window tasks in each interval. To verify the effectiveness of the proposed dynamic scheduling model and algorithm， a large number of simulation experiments are carried out. The experimental results prove the superiority of the proposed method in solving the dynamic scheduling problem of relay satellite. Compared with the cutting-edge multi-objective optimization methods of NSGA-Ⅱ， MDSA-NSGA-Ⅱ， and MODJA， the algorithm designed in this paper can generate higher quality solutions.
| 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 | HORAN S. Nontracking antenna performance for inertially controlled spacecraft using TDRSS［J］. IEEE Transactions on Aerospace and Electronic Systems， 2003， 39（4）： 1263-1269. |
| 3 | WANG J J， JIANG C X， ZHANG H J， et al. Aggressive congestion control mechanism for space systems［J］. IEEE Aerospace and Electronic Systems Magazine， 2016， 31（3）： 28-33. |
| 4 | WANG X Y， ZHAO S H， LI Y J， et al. An enhanced MAC protocol based on the IEEE 802.11 for data relay satellite systems［J］. International Journal of Satellite Communications and Networking， 2020， 38（3）： 272-283. |
| 5 | WU G H， MA M H， ZHU J H， et al. Multi-satellite observation integrated scheduling method oriented to emergency tasks and common tasks［J］. Journal of Systems Engineering and Electronics， 2012， 23（5）： 723-733. |
| 6 | PECORELLA T， RONGA L S， CHITI F， et al. Emergency satellite communications： research and standardization activities［J］. IEEE Communications Magazine， 2015， 53（5）： 170-177. |
| 7 | ZHAI X J， NIU X N， TANG H， et al. Robust satellite scheduling approach for dynamic emergency tasks［J］. Mathematical Problems in Engineering， 2015， 2015： 482923. |
| 8 | 顾中舜. 中继卫星动态调度问题建模及优化技术研究［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）. | |
| 9 | 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. |
| 10 | ROJANASOONTHON S， BARD J. A GRASP for parallel machine scheduling with time windows［J］. INFORMS Journal on Computing， 2005， 17（1）： 32-51. |
| 11 | ZHUANG S F， YIN Z D， WU Z L， et al. The relay satellite scheduling based on artificial bee colony algorithm［C］∥ 2014 International Symposium on Wireless Personal Multimedia Communications （WPMC）. Piscataway： IEEE Press， 2014： 635-640. |
| 12 | WANG L， JIANG C X， KUANG L 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. |
| 13 | CHEN X J， LI X M， WANG X W， et al. Task scheduling method for data relay satellite network considering breakpoint transmission［J］. IEEE Transactions on Vehicular Technology， 2021， 70（1）： 844-857. |
| 14 | 郭超， 熊伟， 郝利云. 基于双层优先级的中继卫星系统任务调度算法［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）. | |
| 15 | WU G H， LUO Q Z， ZHU Y Q， et al. Flexible task scheduling in data relay satellite networks［J］. IEEE Transactions on Aerospace and Electronic Systems， 2022， 58（2）： 1055-1068. |
| 16 | LI J X， WU G H， LIAO T J， et al. Task scheduling under a novel framework for data relay satellite network via deep reinforcement learning［J］. IEEE Transactions on Vehicular Technology， 2023， 72（5）： 6654-6668. |
| 17 | DAI C Q， LI C， FU S， et al. Dynamic scheduling for emergency tasks in space data relay network［J］. IEEE Transactions on Vehicular Technology， 2021， 70（1）： 795-807. |
| 18 | DENG B Y， JIANG C X， KUANG L L， et al. Two-phase task scheduling in data relay satellite systems［J］. IEEE Transactions on Vehicular Technology， 2018， 67（2）： 1782-1793. |
| 19 | HE L J， LI J D， 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. |
| 20 | LIN X H， WANG L H， XU H， et al. Event-trigger rolling horizon optimization for congestion management considering peer-to-peer energy trading among microgrids［J］. International Journal of Electrical Power & Energy Systems， 2023， 147（5）： 108838. |
| 21 | JIA Y J， WANG C J， WANG L M. A rolling horizon procedure for dynamic pickup and delivery problem with time windows［C］∥ 2009 IEEE International Conference on Automation and Logistics. Piscataway： IEEE Press， 2009： 2087-2091. |
| 22 | QIU D S， HE C， LIU J， et al. A dynamic scheduling method of earth-observing satellites by employing rolling horizon strategy［J］. The Scientific World Journal， 2013（3）： 304047. |
| 23 | 庄树峰. 跟踪与数据中继卫星系统资源调度技术研究［D］. 哈尔滨： 哈尔滨工业大学， 2017. |
| ZHUANG S F. Research on resource scheduling technology of tracking and data relay satellite system［D］.Harbin： Harbin Institute of Technology， 2017 （in Chinese）. | |
| 24 | 陈英武， 方炎申， 顾中舜. 中继卫星单址链路调度模型与算法研究［J］. 中国空间科学技术， 2007， 27（2）： 52-58. |
| CHEN Y W， FANG Y S， GU Z S. Algorithms for the single access link scheduling model of tracking and data relay satellite system［J］. Chinese Space Science and Technology， 2007， 27（2）： 52-58 （in Chinese）. | |
| 25 | DU J， JIANG C X， GUO Q， et al. Cooperative earth observation through complex space information networks［J］. IEEE Wireless Communications， 2016， 23（2）： 136-144. |
| 26 | CHAND S， HSU V N， Forecast SETHI S.， solution， and rolling horizons in operations management problems ： A classified bibliography［J］. Manufacturing & Service Operations Management， 2002， 4（1）： 25-43. |
| 27 | DEB K， AGRAWAL S， PRATAP A， et al. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization： NSGA-II［C］∥ Proceedings of the 6th International Conference on Parallel Problem Solving from Nature. Berlin， Heidelberg： Springer， 2000： 849-858. |
| 28 | YU W W， ZHANG L， GE N. An adaptive multiobjective evolutionary algorithm for dynamic multiobjective flexible scheduling problem［J］. International Journal of Intelligent Systems， 2022， 37（12）： 12335-12366. |
| 29 | CALDEIRA R H， GNANAVELBABU A. A Pareto based discrete Jaya algorithm for multi-objective flexible job shop scheduling problem［J］. Expert Systems with Applications， 2021， 170： 114567. |
| 30 | 李夏苗， 陈新江， 伍国华， 等. 考虑断点续传的中继卫星调度模型及启发式算法［J］. 航空学报， 2019， 40（11）： 323233. |
| LI X M， CHEN X J， WU G H， et al. Scheduling model and heuristic algorithm for tracking and data relay satellite considering breakpoint transmission［J］. Acta Aeronautica et Astronautica Sinica， 2019， 40（11）： 323233 （in Chinese）. | |
| 31 | 王志淋， 李新明. 跟踪与数据中继卫星系统资源调度优化问题［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）. | |
| 32 | 孙刚， 彭双， 陈浩， 等. 面向测控数传资源一体化场景的卫星地面站资源多目标优化方法［J］. 航空学报， 2022， 43（9）： 326114. |
| SUN G， PENG S， CHEN H， et al. Multi-objective optimization method oriented to integrated scenario of TT & C resources and data transmission resources［J］. Acta Aeronautica et Astronautica Sinica， 2022， 43（9）： 326114 （in Chinese）. | |
| 33 | 孙刚， 陈浩， 彭双， 等. 一种基于偏好MOEA的卫星地面站资源多目标优化算法［J］. 航空学报， 2021， 42（4）： 524475. |
| SUN G， CHEN H， PENG S， et al. Multi-objective optimization algorithm for satellite range scheduling based on preference MOEA［J］. Acta Aeronautica et Astronautica Sinica， 2021， 42（4）： 524475 （in Chinese）. | |
| 34 | 龙运军， 李恒伟， 尹谦， 等. 基于多目标优化的中继卫星重调度方法［J］. 无线电工程， 2022， 52（7）： 1180-1189. |
| LONG Y J， LI H W， YIN Q， et al. Relay satellite rescheduling method based on multi-objective optimization［J］. Radio Engineering， 2022， 52（7）： 1180-1189 （in Chinese）. | |
| 35 | LIU R Z， SHENG M， XU C， et al. Antenna slewing time aware mission scheduling in space networks［J］. IEEE Communications Letters， 2017， 21（3）： 516-519. |
| 36 | 张彦， 孙占军， 李剑. 中继卫星动态调度问题研究［J］. 系统仿真学报， 2011， 23（7）： 1464-1468. |
| ZHANG Y， SUN Z J， LI J. Study of TDRS dynamic scheduling problem［J］. Journal of System Simulation， 2011， 23（7）： 1464-1468 （in Chinese）. | |
| 37 | 伍国华， 王天宇. 基于自适应模拟退火的大规模星座测控资源调度算法［J］. 航空学报， 2023， 44（12）： 327759. |
| WU G H， WANG T Y. Large-scale constellation TT & C resource scheduling algorithm based on adaptive simulated annealing［J］. Acta Aeronautica et Astronautica Sinica， 2023， 44（12）： 327759 （in Chinese）. | |
| 38 | SHANG K， ISHIBUCHI H. A new hypervolume-based evolutionary algorithm for many-objective optimization［J］. IEEE Transactions on Evolutionary Computation， 2020， 24（5）： 839-852. |
| 39 | ZITZLER E， DEB K， THIELE L. Comparison of multiobjective evolutionary algorithms： Empirical results［J］. Evolutionary Computation， 2000， 8（2）： 173-195. |
/
| 〈 |
|
〉 |
CJA