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

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

CLC Number:

TP18

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.

Figures/Tables 11

Fig.1

Table 1

Table 2

Table 3

Table 4

Fig.2

Fig.3

Table 5

Fig.4

Fig.5

Fig.6

References 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

Conflict avoidance scheduling algorithm for complex associated TT & C requirements

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 11

References 24

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	Jiawei ZHANG, Fengchen QIAN, Junqiang YANG, Qian ZHAO, Zhengrong ZHANG. Survey on routing and spectrum allocation algorithm in elastic optical networks [J]. Systems Engineering and Electronics, 2022, 44(6): 2001-2010.
[2]	Changxiao ZHAO, Ershuai LI, Feng HE, Peng WANG. Bandwidth allocation and optimization of time-sensitive traffic in TSN [J]. Systems Engineering and Electronics, 2022, 44(6): 2027-2034.
[3]	Wenge XING, Chuanrui ZHOU, Cheng ZHOU. Research on key technology of detection and communication integration for phased array radar [J]. Systems Engineering and Electronics, 2022, 44(10): 3053-3058.
[4]	Zhihai YAO, Jianping LIU, Jianping WANG, Wei LI, Bo REN. Evaluation index system of ground-based TT&C resource scheduling [J]. Systems Engineering and Electronics, 2020, 42(8): 1751-1758.
[5]	Jiayi LIU, Gang WANG, Jie ZHANG, Chuang WANG, Xituan SONG. Target optimal assignment model based on improved AGD-distributed multi-Agent system [J]. Systems Engineering and Electronics, 2020, 42(4): 863-870.
[6]	Yadong WANG, Quan SHI, Wei XIA, Cai CHEN. Structure optimization of spare parts supply network based on hyper heuristic algorithm [J]. Systems Engineering and Electronics, 2020, 42(3): 620-629.
[7]	Yi DU, Kefei LIAO, YANG Shan OU, Yijun CHEN. Two-dimensional resource adaptive scheduling algorithm for ISAR imaging system [J]. Systems Engineering and Electronics, 2020, 42(2): 339-345.
[8]	WANG Xun, YAO Peiyang, ZHANG Jieyong, WAN Lujun, JIAO Zhiqiang, CHEN Jieyu. Research on problem of Holonic-C2 organization resource scheduling [J]. Systems Engineering and Electronics, 2019, 41(3): 564-570.
[9]	LIU Xinbo, WANG Buhong, LIU Shuaiqi, YANG Zhixian, ZHAO Zhiyuan. Heuristic algorithm for secure virtual network embedding [J]. Systems Engineering and Electronics, 2018, 40(3): 676-681.
[10]	DING Ding, AI Lihua, LUO Siwei, XU Baomin. User behavior-based resource scheduling mechanism for cloud computing with feedback control [J]. Systems Engineering and Electronics, 2018, 40(1): 209-216.
[11]	CUI Feng-zhe, WANG Xiu-kun, TENG Hong-fei. Dual-system cooperative co-evolutionary algorithm for non-separable function [J]. Systems Engineering and Electronics, 2016, 38(11): 2660-2669.
[12]	LIU Jian-ping, LI Jing, ZHANG Tian-jiao. Hybrid constructive heuristics of space measurement and control network scheduling problem [J]. Systems Engineering and Electronics, 2015, 37(7): 1569-1574.
[13]	ZHAO Xin-shuang, WANG Hou-xiang, CAI Yi-chao. Resource scheduling method in antimissile early warning campaign [J]. Systems Engineering and Electronics, 2015, 37(6): 1300-1305.
[14]	QIU Dishan， WANG Jianjiang， WU Chaobo， LIU Gang. Emergency scheduling method of earth observation satellites based on task merging [J]. Journal of Systems Engineering and Electronics, 2013, 35(7): 1430-1437.
[15]	ZHANG Guang-yu, LI Qing-min, GUO Xuan. Modeling for repairable spare parts in multi-location inventory system with lateral transshipments [J]. Journal of Systems Engineering and Electronics, 2012, 34(7): 1424-1429.