计算机科学 ›› 2019, Vol. 46 ›› Issue (10): 90-96.doi: 10.11896/jsjkx.180901806

• 网络与通信 • 上一篇    下一篇

基于启发式算法的卫星反应式调度

张铭1, 卫波2, 王晋东1   

  1. (解放军信息工程大学 郑州450001)1
    (北京市遥感信息研究所 北京100101)2
  • 收稿日期:2018-09-27 修回日期:2018-12-06 出版日期:2019-10-15 发布日期:2019-10-21
  • 通讯作者: 王晋东(1966-),男,教授,主要研究方向为信息安全、服务计算,E-mail:3361852202@qq.com。
  • 作者简介:张铭(1993-),男,硕士生,主要研究方向为资源调度,E-mail:2663931027@qq.com;卫波(1990-),男,硕士,工程师,主要研究方向为遥感卫星任务控制;
  • 基金资助:
    本文受十三五预研项目(30503020102),军内科研项目(TJ20172A03067)资助。

Satellite Reactive Scheduling Based on Heuristic Algorithm

ZHANG Ming1, WEI Bo2, WANG Jin-dong1   

  1. (PLA Information Engineering University,Zhengzhou 450001,China)1
    (Beijing Institute of Remote Sensing Information,Beijing 100101,China)2
  • Received:2018-09-27 Revised:2018-12-06 Online:2019-10-15 Published:2019-10-21

摘要: 面对地震、火灾等突发性事件,需要对卫星调度方案进行动态调整。文中考虑了卫星资源失效和应急任务加入等动态不确定性因素,综合任务约束、时间约束、卫星能量和存储约束条件,设计了基于触发规则的事件驱动策略,构建了以最大化调度收益和最小化扰动测度为目标函数的反应式调度多目标优化模型,提出了基于任务迫切度的选择策略、基于时间和角度的合成策略、基于冲突程度的替换策略,最后采用了一种考虑任务合并、插入、移位、替换的启发式算法。仿真结果表明,相比事件驱动和周期驱动策略,文中所设计的基于触发规则的事件驱动策略能够兼顾触发次数、任务完成率和响应时间,是一种有效的反应式驱动策略,MISR-HA(Heuristic Algorithm for Merging,Inserting,Shifting and Replcing)算法相比其他3种算法在调度收益上平均提高了14.78%,在扰动测度上平均降低了41.91%,在运行时间上平均缩短了14.63%,从而有效地证明了该算法的有效性。

关键词: 触发规则, 调度收益, 启发式, 扰动测度, 约束条件

Abstract: For the sudden events such as earthquakes and fires,it is necessary to dynamically adjust the satellite dispatching plan.Considering the dynamic uncertainty factors such as satellite resource failure and joining emergency task,combining task constraints,time constraints,satellite energy and storage constraints,this paper designed an event-driven strategy based on trigger rules,constructed a multi-objective optimazation model regarding maximized scheduling gain and minimum disturbance measure as objective function,and then proposed a heuristic algorithm considering task merging,insertion,shifting and replacement.The simulation results show that the event-driven strategy based on trigger rules can balance the number of triggers,task completion rate and response time,and it is an effective reactive driving strategy.Compared with other three algorithms,the MISR-HA algorithm improves the scheduling gain by an average of 14.78%,reduces the disturbance measurement by an average of 41.91%,and reduces the running time by an average of 14.63%,thus proving the effectiveness of the algorithm.

Key words: Constraint condition, Dispatch income, Disturbance measure, Heuristic method, Trigger rule

中图分类号: 

  • TP79
[1]WANG J,ZHU X,YANG L T,et al.Towards dynamic real-time scheduling for multiple earth observation satellites[J].Journal of Computer and System Sciences,2015,81(1):110-124.
[2]GRASSET-BOURDEL R,VERFAILLIE G,FLIPO A.Planning and replanning for a constellation of agile Earth observing satellites[J].Proceedings of International Conference on Automated Planning and Scheduling,2011,26(2):68-86.
[3]HAO H C,JIANG W,LI Y J.Dynamic Task Planning Problem Based on Multi-Agent Agile Satellite[J].Journal of National University of Defense Technology,2013,35(1):53-59.(in Chinese)
郝会成,姜维,李一军.基于Multi-Agent敏捷卫星动态任务规划问题[J].国防科技大学学报,2013,35(1):53-59.
[4]WANG J M,LI J F,TAN Y J.Study on multi-star dynamic scheduling model and algorithm with new task insertion[J].Journal of System Simulation,2009,21(12):3522-3527.(in Chinese)
王军民,李菊芳,谭跃进.有新任务插入的多星动态调度模型与算法研究[J].系统仿真学报,2009,21(12):3522-3527.
[5]PEMBERTON J C,GREENWALD L G.On the need for dynamic scheduling of imaging satellites.International Archives of Photogrammetry Remote Sensing and Spatial Information Sciences,2002,34(1):165-171.
[6]KRAMER L A,SMITH S F.Maximizing Flexibility:A Retraction Heuristic for Oversubscribed Sched-uling Problems[C]//Proceedings of the 18th International Joint Conference on Artificial Intelligence.Acapulco Mexico,2003.
[7]KRAMER L A,SMITH S F.Task Swapping for Schedule Improvement:A Broader Analysis[C]//Proceedings of the 14th International Conference on Automated Planning and Scheduling.Whistler,Canada,2004.
[8]KRAMER L A,SMITH S F.Task Swapping:Making Space in Schedules for Space[C]//Proceedings of the 4th International Workshop on Planning and Scheduling for Space.Darmstadt.Germany,2004.
[9]KRAMER L A,SMITH S F.Maximizing flexibility:A retrac-tion heuristic for oversubscribed scheduling problems//IJCAI. 2003:1218-1223.
[10]FOX M,GEREVINI A,LONG D,et al.Plan Stability:Replanning versus Plan Repair[C]//Proceedings of the International Conference on Automated Planning and Scheduling.2006:212-221.
[11]LI Y Q,WANG R X,XU M Q.Scheduling and Rescheduling of Imaging Satellite Based on Ant Colony Optimization[J].Journal of Computational Information Systems,2013,9(16):6503-6510.
[12]LIU Y.Research on Dynamic Rescheduling Model,Algorithm and Application of Reconnaissance Satellite [D].Changsha:National University of Defense Technology,2005.(in Chinese)
刘洋.侦察卫星动态重调度模型、算法及应用研究[D].长沙:国防科技大学,2005.
[13]ZHU J H,LIU J.Local Dynamic Collaborative Rescheduling Method for Agile Satellite Observation Scheme[J].Military Planning and Systems Engineering,2014,28(3):48-52.(in Chinese)
祝江汉,刘进.敏捷卫星观测方案局部动态协同重调度方法[J].军事运筹与系统工程,2014,28(3):48-52.
[14]WANG J,ZHU X,QIU D,et al.Dynamic scheduling for emergency tasks on distributed imaging satellites with task merging[J].IEEE Transactions on Parallel and Distributed Systems,2014,25(9):2275-2285.
[15]WANG J,ZHU X,YANG L T,et al.Towards dynamic real-time scheduling for multiple earth observation satellites[J].Journal of Computer and System Sciences,2015,81(1):110-124.
[16]BILLUPS S C.Satellite Mission Scheduling with Dynamic Tasking[R].Final Report of the UCDHSC Mathematics Clinic,2005.
[17]YANG H T,YANG L,ZHAO H L.Study on the mission planning model of space-based information acquisition[J].Journal of System Simulation,2009,21(21):6710-6715.
[18]FRANCOIS V,ARDA Y,CRAMA Y,et al.Large neighborhood search for multi-trip vehicle routing[J].European Journal of Operational Research,2016,255(2):422-441.
[19]CHURCH L K,UZSOY R.Analysis of periodic and event-driven rescheduling policies in dynamic shops[J].International Journal of Computer Integrated Manufacturing,1992,5(3):153-163.
[1] 张露萍, 徐飞.
具有突触规则的脉冲神经膜系统综述
Survey on Spiking Neural P Systems with Rules on Synapses
计算机科学, 2022, 49(8): 217-224. https://doi.org/10.11896/jsjkx.220300078
[2] 耿海军, 王威, 尹霞.
基于混合软件定义网络的单节点故障保护方法
Single Node Failure Routing Protection Algorithm Based on Hybrid Software Defined Networks
计算机科学, 2022, 49(2): 329-335. https://doi.org/10.11896/jsjkx.210100051
[3] 郭彪, 唐麒, 文智敏, 傅娟, 王玲, 魏急波.
一种面向动态部分可重构片上系统的列表式软硬件划分算法
List-based Software and Hardware Partitioning Algorithm for Dynamic Partial Reconfigurable System-on-Chip
计算机科学, 2021, 48(6): 19-25. https://doi.org/10.11896/jsjkx.200700198
[4] 刘忠慧, 赵琦, 邹璐, 闵帆.
三元概念的启发式构建及其在社会化推荐中的应用
Heuristic Construction of Triadic Concept and Its Application in Social Recommendation
计算机科学, 2021, 48(6): 234-240. https://doi.org/10.11896/jsjkx.200500136
[5] 周秋艳, 肖满生, 张龙信, 张晓丽, 杨文理.
多约束条件下生产排程智能优化技术
Intelligent Optimization Technology of Production Scheduling Under Multiple Constraints
计算机科学, 2021, 48(3): 239-245. https://doi.org/10.11896/jsjkx.200300105
[6] 郭启程, 杜晓玉, 张延宇, 周毅.
基于改进鲸鱼算法的无人机三维路径规划
Three-dimensional Path Planning of UAV Based on Improved Whale Optimization Algorithm
计算机科学, 2021, 48(12): 304-311. https://doi.org/10.11896/jsjkx.201000021
[7] 唐文君, 刘岳, 陈荣.
移动边缘计算中的动态用户分配方法
User Allocation Approach in Dynamic Mobile Edge Computing
计算机科学, 2021, 48(1): 58-64. https://doi.org/10.11896/jsjkx.200900079
[8] 郭飞雁, 唐兵.
基于用户延迟感知的移动边缘服务器放置方法
Mobile Edge Server Placement Method Based on User Latency-aware
计算机科学, 2021, 48(1): 103-110. https://doi.org/10.11896/jsjkx.200900146
[9] 冯炳超, 吴璟莉.
求解自行车共享系统静态再平衡问题的单亲遗传算法
Partheno-genetic Algorithm for Solving Static Rebalance Problem of Bicycle Sharing System
计算机科学, 2020, 47(6A): 114-118. https://doi.org/10.11896/JsJkx.190700120
[10] 张旭, 王莉莉, 杨博韬.
带有一刀切约束的二维非规则装箱算法
Heuristic Algorithms for Two-dimensional Irregular Bin Packing Problem with GuillotineConstraints
计算机科学, 2020, 47(5): 212-216. https://doi.org/10.11896/jsjkx.190400078
[11] 潘恒, 李景峰, 马君虎.
可抵御内部威胁的角色动态调整算法
Role Dynamic Adjustment Algorithm for Resisting Insider Threat
计算机科学, 2020, 47(5): 313-318. https://doi.org/10.11896/jsjkx.190800051
[12] 杨婷, 罗飞, 丁炜超, 卢海峰.
一种自适应优化松弛量的装箱算法
Bin Packing Algorithm Based on Adaptive Optimization of Slack
计算机科学, 2020, 47(4): 211-216. https://doi.org/10.11896/jsjkx.190500132
[13] 郭超, 王磊, 尹爱华.
求解一刀切式二维矩形Strip Packing问题的混合搜索算法
Hybrid Search Algorithm for Two Dimensional Guillotine Rectangular Strip Packing Problem
计算机科学, 2020, 47(11A): 119-125. https://doi.org/10.11896/jsjkx.200200016
[14] 罗飞, 任强, 丁炜超, 卢海峰.
基于最小松弛量的启发式一维装箱算法
Heuristic One-dimensional Bin Packing Algorithm Based on Minimum Slack
计算机科学, 2019, 46(9): 315-320. https://doi.org/10.11896/j.issn.1002-137X.2019.09.048
[15] 张澍裕, 宫达, 谢兵, 刘开贵.
基于实时GPS的公交短时动态调度算法
Bus Short-term Dynamic Dispatch Algorithm Based on Real-time GPS
计算机科学, 2019, 46(6A): 497-501.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!