面向复杂关联测控需求的冲突规避调度算法

doi:10.12305/j.issn.1001-506X.2022.05.19

摘要/Abstract

摘要：

对卫星测控资源调度问题的现状进行了分析, 根据现有场景、需求和任务建立了目标约束满足模型。在系统阐述测控资源、可见弧段、任务需求的基础上, 考虑到测控任务需求间复杂的相互关联关系, 提出了一种基于任务冲突规避的测控资源调度算法。相比其他传统方法, 该算法考虑了全局任务对资源的需求和任务间复杂的关联性, 引入了可行解接受度函数, 避免了传统启发式算法过分贪婪的缺点。实验结果表明, 该算法应用于大规模测控任务资源调度时, 能有效提高任务调度的成功率。

关键词: 卫星测控, 资源调度, 约束优化问题, 启发式算法

Abstract:

This paper analyzes the current situation of satellite trace, telemetry, control (TT & C) resource scheduling problem. Based on the existing scenarios, requirements and tasks, we establish the objective constraint satisfaction model. After the systematic description of TT & C resources, visible arcs and task requirements, considering the complex relationship between TT & C task requirements, a TT & C resources scheduling algorithm based on task conflict avoidance is proposed. Compared with other traditional methods, this algorithm has considered the resource requirements of global tasks and the complex correlation between tasks. We introduce the acceptance function of the feasible solution, which avoids the greedy drawbacks of the traditional heuristic algorithm. Experimental results show that the algorithm can raise the scheduling success rate of tasks effectively when applied to a large-scale TT & C task resource scheduling.

Key words: satellite trace, telemetry, control (TT & C), resource scheduling, constraint optimization problem, heuristic algorithm

中图分类号:

TP18

辛立强, 张超, 赵灵芝, 刘建平. 面向复杂关联测控需求的冲突规避调度算法[J]. 系统工程与电子技术, 2022, 44(5): 1581-1588.

Liqiang XIN, Chao ZHANG, Lingzhi ZHAO, Jianping LIU. Conflict avoidance scheduling algorithm for complex associated TT & C requirements[J]. Systems Engineering and Electronics, 2022, 44(5): 1581-1588.

图/表 11

图1

表1

表2

表3

表4

图2

图3

表5

图4

图5

图6

参考文献 24

1	LI Z L, MENG X, LIU S Q, et al. Genetic algorithm for TDRS communication scheduling with resource constraints[C]//Proc. of the International Symposium on Intelligent Information Technology Application Workshops, 2009: 74-77.
2	PARISH D A. A genetic algorithm approach to automating satellite range scheduling[D]. Dayton: Air Force Institute of Technology, 1994.
3	DU Y H, XING L N, CHEN Y G, et al. An evolvable real-time system of integrated satellite scheduling based on cooperative neuro evolution of augmenting topologies[C]//Proc. of the IEEE Congress on Evolutionary Computation, 2019: 1322-1329.
4	陈峰, 武小悦. 天地测控资源调度的两阶段递进遗传算法[J]. 国防科技大学学报, 2010, 32 (2): 17- 22. doi: 10.3969/j.issn.1001-2486.2010.02.004
	CHEN F , WU X Y . Two-stage successive genetic algorithm for space and ground TT&C scheduling[J]. Journal of National University of Defense Technology, 2010, 32 (2): 17- 22. doi: 10.3969/j.issn.1001-2486.2010.02.004
5	薛乃阳, 丁丹, 王红敏, 等. 引入微元法思想的混合测控资源联合调度方法[EB/OL]. [2021-03-06]. http://kns.cnki.net/kcms/detail/11.3092.V.20210130.1110.002.html.
	XUE N Y, DING D, WANG H M, et al. Joint scheduling method of hybrid TT&C resources introducing the idea of infinitesimal method[EB/OL]. [2021-03-06]. http://kns.cnki.net/kcms/detail/11.3092.V.20210130.1110.002.html.
6	薛乃阳, 丁丹, 王红敏, 等. 基于改进遗传算法的多类测控资源调度方法[J]. 系统工程与电子技术, 2021, 43 (9): 2535- 2543.
	XUE N Y , DING D , WANG H M , et al. Multi-type TT&C resource scheduling method based on improved genetic algorithm[J]. Systems Engineering and Electronics, 2021, 43 (9): 2535- 2543.
7	GOOLEY T D . Automating air force satellite control network scheduling[J]. Mathematical and Computer Modelling, 1996, 24 (2): 91- 101. doi: 10.1016/0895-7177(96)00093-3
8	陈理江, 武小悦, 李云峰. 基于时间灵活度的中继卫星调度算法[J]. 航空计算技术, 2006, 36 (4): 48- 51. doi: 10.3969/j.issn.1671-654X.2006.04.013
	CHEN L J , WU X Y , LI Y F . Scheduling algorithm for rlaying satellite based on temporal flexibility, aeronautical computing technique[J]. Aeronautical Computing Technique, 2006, 36 (4): 48- 51. doi: 10.3969/j.issn.1671-654X.2006.04.013
9	NICOLAS Z . Graph colouring approaches for a satellite range scheduling problem[J]. Journal of Scheduling, 2008, 11, 263- 277. doi: 10.1007/s10951-008-0066-8
10	GOOLEY T. Automating the satellite range scheduling process[D]. Dayton: Air Force Institute of Technology, 1993.
11	BARBULESCU L , HOWE A , WHITLEY D . AFSCN scheduling: how the problem and solution have evolved[J]. Mathematical and Computer Modelling, 2006, 43 (9/10): 1023- 1037.
12	LI Z Y, MING W, LIU J P, et al. Analysis of ground station network resources for giant constellation TT&C service[C]//Proc. of the IEEE 3rd International Conference on Electronic Information and Communication Technology, 2020: 6-11.
13	XHAFA F , IP A W H . Optimisation problems and resolution methods in satellite scheduling and space-craft operation: a survey[J]. Enterprise Information Systems, 2019, 15 (1): 1- 24. doi: 10.4018/IJEIS.2019010101
14	REN B, LIU J P, LI Z Y, et al. Satellite requirement preference driven TT&C resources scheduling algorithm for time sensitive missions[C]//Proc. of the IEEE 3rd International Conference on Electronic Information and Communication Technology, 2020: 15-19.
15	SONG Y J, MA X, SONG B Y, et al. A heuristic algorithm for satellite transmission scheduling problem[C]//Proc. of the IEEE 3rd Advanced Information Technology, Electronic and Automation Control Conference, 2018: 147-151.
16	凌晓冬, 武小悦, 刘琦. 面向需求的航天测控资源调度算法[J]. 系统工程与电子技术, 2009, 31 (7): 1661- 1666. doi: 10.3321/j.issn:1001-506X.2009.07.030
	LING X D , WU X Y , LIU Q . Requirement-oriented TT&C scheduling algorithm[J]. Systems Engineering and Electronics, 2009, 31 (7): 1661- 1666. doi: 10.3321/j.issn:1001-506X.2009.07.030
17	凌晓冬, 武小悦, 刘琦. 基于HLA的测控资源调度仿真系统设计[J]. 系统仿真学报, 2010, 22 (2): 362- 365.
	LING X D , WU X Y , LIU Q . TT&C resource scheduling simulation system design based on HLA[J]. Journal of System Simulation, 2010, 22 (2): 362- 365.
18	刘建平, 李晶, 张天骄. 航天测控网调度的混合构造启发式算法[J]. 系统工程与电子技术, 2015, 37 (7): 1569- 1574.
	LIU J P , LI J , ZHANG T J . Hybrid constructive heuristics of space measurement and control network scheduling problem[J]. Systems Engineering and Electronics, 2015, 37 (7): 1569- 1574.
19	LIU J P, LI J, BAI J, et al. A heuristic algorithm of space born TT&C resources scheduling[C]//Proc. of the IEEE International Conference on Intelligent Computing and Intelligent Systems, 2010: 180-182.
20	WU J , ZHANG J W , YANG J H , et al. Research on task priority model and algorithm for satellite scheduling problem[J]. IEEE Access, 2019, 7, 103031- 103046. doi: 10.1109/ACCESS.2019.2928992
21	LI J, YU P J, LIU J P. The TT&C resource scheduling method based on multi-satellite[C]//Proc. of the IEEE International Conference on Intelligent Computing and Intelligent Systems, 2010: 431-435.
22	LI J, BAI J, LIU J P, et al. The TT&C task planning algorithm based on multi-satellite[C]//Proc. of the International Conference on Artificial Intelligence and Computational Intelligence, 2010: 556-559.
23	金光. 卫星地面站测控资源调度CSP模型[J]. 系统工程与电子技术, 2007, 29 (7): 1117- 1120. doi: 10.3321/j.issn:1001-506X.2007.07.024
	JIN G . CSP model for satellite and ground station TT&C resource scheduling problems[J]. Systems Engineering and Electronics, 2007, 29 (7): 1117- 1120. doi: 10.3321/j.issn:1001-506X.2007.07.024
24	姚智海, 刘建平, 王建平, 等. 地面测控资源调度效能评估指标体系[J]. 系统工程与电子技术, 2020, 42 (8): 1751- 1758.
	YAO Z H , LIU J P , WANG J P , et al. Evaluation index system of ground-based TT&C resource scheduling[J]. Systems Engineering and Electronics, 2020, 42 (8): 1751- 1758.

参数符号	参数名称	备注
RT	升降轨属性	0:无要求; 1:升轨; 2:降轨
MME	最小仰角	单位为度
MTL	最小测控时间	单位为秒
PRC	相对圈号约束	-
Favdevset	该任务偏好的地面设备集	-
function	设备支持功能需求	遥测接收、测距、测速、测角、上行遥控、普通数传、高速数传
Frereq	工作频段要求	VHF/UHF、L、S、C、X、Ku、Ka、激光
Sigstru	功能信号体制
Intertype	子任务关联模式	0:无需求; 1:时间差; 2:圈号差
Inter₁	最短间隔	与上一子任务最短时间间隔或最小间隔圈号
Inter₂	最长间隔	与上一子任务最长时间间隔或最大间隔圈号

参数符号	参数名称
buildtime	建链准备时间
diamatletime	拆链时间
function	设备可完成的功能
Fresus	工作频段
Sigsus	功能信号体制
〈forbiddentime〉	禁用时间段

参数符号	参数名称
D_m	设备编号
s_i	卫星编号
RF	升降轨属性
rev	卫星总圈号
Idrev	过境的相对圈数
conrev	过境的连续可见圈数
tr_s	弧段开始时间
tr_e	弧段结束时间
Ang	弧段中点的俯仰角

类别	约束条件	符号表达
子任务约束	升降轨约束	cd_{i, j, k}.RT=R.RT(W_{i, j, k}.t_s≥R.tr_s, W_{i, j, k}.t_e≤R.tr_e)
	最短测控时长约束	cd_{i, j, k}.MTL≤W_{i, j, k}.t_e－W_{i, j, k}.t_s
	最小仰角约束	R.Ang≥cd_{i, j, k}.MME(W_{i, j, k}.t_s≥R.tr_s, W_{i, j, k}.t_e≤R.tr_e)
	相对圈号约束	R.Idrev∈cd_{i, j, k}.RPC(W_{i, j, k}.t_s≥R.tr_s, W_{i, j, k}.t_e≤R.tr_e)
	任务功能约束	cd_{i, j, k}.function⊆D_m.function(W_{i, j, k}.t_s≥R.tr_s, W_{i, j, k}.t_e≤R.tr_e)
	任务频段约束	cd_{i, j, k}.Frereq∈D_m.Fresus(W_{i, j, k}.t_s≥R.tr_s, W_{i, j, k}.t_e≤R.tr_e)
	任务功能信号体制约束	cd_{i, j, k}.Sigstru∈D_m.Sigsus(W_{i, j, k}.t_s≥R.tr_s, W_{i, j, k}.t_e≤R.tr_e)
子任务关联约束	任务间最大最小圈号约束	cd_{i, j, k}.Inter₁≤W_{i, j, k}.rov－W_{i, j, (k－1)}.rov≤cd_{i, j, k}.Inter₂ (1≤j≤7, 1＜k≤K(i, j), Intertype=0) cd_{i, j, 1}.Inter₁≤W_{i, j, 1}.rov－W_{i, (j－1), K(i, j－1)}.rov≤cd_{i, j, 1}.Inter₂ (1＜j≤7, Intertype=0)
子任务关联约束	任务间最大最小测控时间间隔约束	cd_{i, j, k}.Inter₁≤W_{i, j, k}.t_s－W_{i, j, (k－1)}.t_e≤cd_{i, j, k}.Inter₂ (1≤j≤7, 1＜k≤K(i, j), Intertype=1) cd_{i, j, 1}.Inter₁≤W_{i, j, 1}.t_s－W_{i, (j－1), K(i, j－1)}.t_e≤cd_{i, j, 1}.Inter₂ (1＜j≤7, Intertype=1)
设备物理约束	可见时间窗口约束	R.tr_s≤W_{i, j, k}.t_s＜W_{i, j, k}.t_e＜R.tr_e
	设备禁用时段约束	∀l∈L(m), [W_{i, j, k}.t_s－W_{i, j, k}.D_m.buildtime, W_{i, j, k}.t_e+W_{i, j, k}.D_m.diamatletime]∩[W_{i, j, k}.D_m.forbiddentime_l^s, W_{i, j, k}.D_m.forbiddentime_l^e]=∅
	测控设备测控任务个数约束	∀(W_{i, j, k}, W_{i′, j′, k′}), [W_{i, j, k}.t_s, W_{i, j, k}.t_e]∩[W_{i′, j′, k′}.t_s, W_{i′, j′, k′}.t_e]=∅ (W_{i, j, k}.D_m=W_{i′, j′, k′}.D_m)

场景	子任务功能	子任务个数	测控设备	测控频段要求
小规模(50颗卫星)	测距、测速、测角	77	南宁(1套)、甘肃(2套)、喀什(4套)、佳木斯(3套)、渭南(2套)、厦门(1套)、沈阳(1套)、青岛(1套)、漠河(1套)	S
	上行遥控	1 571
	普通数传	44
中规模(100颗卫星)	测距、测速、测角	77
	上行遥控	3 222
	普通数传	115
大规模(150颗卫星)	测距、测速、测角	77
	上行遥控	4 664
	普通数传	297