基于LSTM和启发式方法的遥感卫星地面站天线智能调度*
2022-07-06孙文军马广彬田妙苗林友明黄鹏
孙文军，马广彬，田妙苗，林友明，黄鹏
(1 中国科学院空天信息创新研究院， 北京 100094； 2 中国科学院大学， 北京 100049)
遥感卫星获取数据后，需要将数据传输到遥感卫星地面站(以下简称“地面站”)。地面站资源调度是在卫星与地面资源的几何可见时间窗口内确定数据接收时间窗口的起止时间，并为数据接收任务分配满足约束的地面站资源[1-3]。随着遥感数据在防灾减灾、城镇规划、科学研究以及军事侦察等领域的广泛应用，遥感卫星数据接收任务也日益增多，而相对有限的地面站接收资源难以满足接收需求。因此，需要对地面站接收资源进行合理调度，以最大程度地提高资源使用效率。
地面站资源调度问题涉及多颗卫星、多个地面站、多个时间窗和多个调度约束条件，在研究中通常把该问题看作是一个具有NP-Hard性质的组合优化问题。目前，国内外对于该问题在模型和算法方面均有研究。调度模型有数学规划模型[4-8]、约束满足模型[9-11]，此外，还有Petri网模型[12-15]、Agent模型和基于图论的模型[16-17]等其他模型。调度算法有确定性算法、一般启发式算法[1-2,18-19]、一般搜索算法[20]和智能搜索算法[21-22]。随着卫星数据接收任务持续增多，地面站资源调度模型和算法也越来越复杂，而传统的建模方法在建模时需对实际复杂调度问题进行简化并附加较多的假设条件，这些人为的假设降低了实际复杂度，造成模型获得的调度方案可靠性较低[23-24]。以中国遥感卫星地面站的站网调度系统为例，目前采用的模型为约束满足模型，寻优算法采用的是结合启发式规则的遗传算法(后文简称为“原算法”)，调度系统给出的调度结果还需要后期人工干预加以完善。同时，随着地面站卫星数据接收任务的不断增多、应用的不断深入，中国遥感卫星地面站已积累了大量的地面站资源调度数据，这些数据中隐含了反映实际调度环境特点及调度知识的大量有效信息。因此，可以使用数据驱动的方法来解决遥感卫星地面接收天线资源调度问题。
数据驱动的调度问题建模方法主要是基于历史数据、实时数据及相关调度仿真数据[23]，采用数据挖掘、机器学习、深度学习等技术建立相关调度模型，挖掘数据中隐含在实际调度环境和调度规则的大量有效信息，从而制定更优的调度方案。近年来，国内外在基于数据的调度问题上均取得了一定的研究进展。在解决工作车间调度问题时，先使用遗传算法、蚁群算法、禁忌搜索算法得到一个已知的基准问题的较优解作为训练数据，再使用属性规约、C4/5、决策树分类、多层感知机等方法挖掘方案中的操作顺序与其属性及一系列规则之间的关系，取得了比传统智能优化方法更好的结果，并且在大规模的调度问题上具有更好的可扩展性[25-31]；王成龙等[32]和王振江[33]分别使用树和人工神经网络挖掘作业车间调度规则；丁建立和王曼[34]使用Apriori算法，从大量的航班协同保障数据中发现航班保障各环节之间的关联关系，进而借助其优化航班保障流程，提升航班放行正常率；Vinyals等[35]、Bello等[36]使用一种类似于序列到序列模型(sequence-to-sequence)[37]的指针网络(pointer net)解决平面旅行商问题和背包问题；滴滴AILabs[38]提出基于强化学习的网约车派单解决方案。目前，数据驱动的调度方法在解决地面资源调度上的研究比较少。Zhang等[11]使用SVM和NSGA-Ⅱ相结合的方法来解决地面站资源调度问题，该算法首先使用SVM分类器为没有时间冲突的任务分配地面站资源，在此基础上使用NSGA-Ⅱ算法处理有时间冲突的任务。
使用数据驱动的调度方法一则避免了构建复杂的数学模型，二则能够挖掘隐含在数据里的约束规则。因此，基于中国遥感卫星地面站积累的大量历史地面资源调度数据，提出一种长短期记忆神经网络和启发式规则相结合的智能调度方法来解决地面站资源调度问题。实验结果表明，该方法相比于原算法在资源利用率和时间效率上均有一定的提升。
1 地面站天线调度问题描述
地面站接收资源主要包括天线、信道、记录器，通常卫星数据经天线接收后，经过信道的变频和解调，最后由记录器记录，具体流程如图1所示。地面站接收资源调度也主要是对天线、信道和记录器的调度，即为每一条卫星数据接收任务分配合理的接收时间窗口和地面接收资源，从而使每一条数据尽可能地被接收，也使地面站资源充分利用。由于信道和记录器资源相对充足，天线资源相对不足，本文的研究内容只针对地面站天线的调度。
图1 地面站接收记录卫星数据示意图
地面站天线的资源约束为：1)同一时间段内，一部天线只能接收一个卫星任务，且一个卫星任务仅需一部天线来接收；2)任务在执行期间不可被抢占；3)同一部天线在2个任务之间的状态切换需要时间。
2个遥感卫星数据接收任务之间的关系，本文在时间上把它划分为3种，即相离关系、部分重叠关系和包含关系。如图2所示，任务1和任务2处于包含关系，任务1和任务3处于部分重叠关系，任务2和任务3处于相离关系。当2个任务在时间上处于相离关系且时间差大于天线的切换时间时，则地面接收资源使用互不影响；当处于部分重叠或者包含关系，可能会引起数据联合接收、接收资源抢占的情况。
图2 接收任务时间关系
数据联合接收 当卫星在同一时间发射的信号位于多个地面站接收范围间的重叠区域时，每个地面站均可接收到该卫星数据，这时就会出现部分数据联合接收的情况。如图2所示，如果任务1～3属于同一颗卫星在不同地面站的数据接收任务，则任务1和任务2、任务1和任务3均属于联合接收。数据联合接收的时间越长，则接收资源不必要的浪费越严重，相应地会加剧各个地面站资源选择冲突。因此，在接收任务调度中要尽量避免联合接收的情况。
资源选择冲突 指多个卫星同时经过同一地面站时，接收任务的接收时间属于部分重叠关系或者包含关系，则在分配接收天线时，由于该地面站资源紧缺，可能会出现资源抢占，即资源选择冲突。这时，就需要从接收天线性能、接收任务优先级等角度来消解冲突，使数据完整接收。
地面站天线调度在为每一个接收任务分配接收天线的同时，需要避免数据联合接收和资源选择冲突这两种情况。因此，本文在解决地面站天线调度问题主要围绕接收天线分配、处理联合接收情况以及资源选择冲突情况展开。
2 地面站天线调度算法设计
将数据接收任务按时间从早到晚排序，并将其看成是一个时间序列，因此本文以专门用来处理时间序列的长短期记忆网络(long short-term memory network,LSTM)[39]为核心，制定如图3所示的遥感卫星地面站天线调度算法流程。首先，输入历史调度数据，并对数据进行整数编码、词嵌入等预处理；其次，把处理后的数据分成训练集和验证集，其中训练集用来调整LSTM模型参数，提取天线使用优先级规则，验证集用来选择泛化能力较好的模型，使用该模型为任务冲突集中的每个数据接收任务分配接收天线，得到初始调度方案；最后，使用启发式方法处理初始方案中数据联合接收和资源选择冲突这两种情况，得到切实可行的方案。
图3 整体技术路线
2.1 LSTM获得初始调度方案
LSTM是在普通循环神经网络基础上，在隐藏层各神经单元中增加“遗忘门”、“输入门”、“输出门”3个门控单元，控制之前信息和当前信息的记忆和遗忘程度，从而使普通循环神经网络具备长期记忆的功能，并且有效地改进其在时间序列过长时的梯度消失和梯度爆炸等问题。目前，LSTM已经广泛应用在语音识别、图片描述、自然语言处理等许多领域。
地面站天线调度是一个多任务、多天线的问题，因此可以把该问题看成是一个多分类问题，即在保证方案整体效益最大时，为每个接收任务分配一个合理的接收天线。每一个冲突任务集的长度即为其所对应的时间序列的长度。每个任务集的任务个数不同，所以选择多对多的变长LSTM框架。图4描述了含有T个任务的任务集模型架构。其中，任务输入层的每个时间步输入一个数据接收任务，并使用词嵌入技术把每个接收任务嵌入到特定的向量空间，再经过LSTM的2个隐藏层、线性(Linear)层以及归一化指数函数(Softmax)层得到天线概率分布。概率值越大则天线使用优先级越高，概率值越小则天线使用优先级越低，概率值为0则说明该天线不是此数据接收任务的候选天线。选择概率最大的天线作为该任务最优选天线，得到初始调度方案，并保留概率较大的前几个候选天线，作为修正初始方案的备选天线。
图4 LSTM模型结构图
图5为LSTM模型结构中2个隐藏层中的LSTM神经元结构图。当前神经元接收前一时刻数据接收任务隐藏层的输出ht-1和当前时刻数据接收任务的输入xt，LSTM第1步决定上一时刻学到的信息通过或部分通过神经元，这一步通过下式所表示的“遗忘门”ft来控制。
图5 LSTM神经元结构
ft=σ(Wf·[ht-1,xt]+bf).
(1)
第2步产生该神经元需要更新的新信息，
it=σ(Wi·[ht-1,xt]+bi),
(2)
(3)
(4)
最后一步决定模型的输出，
ot=σ(Wo·[ht-1,xt]+bo),
(5)
ht=ot*tanh(Ct),
(6)
其中：Wf和bf为“遗忘门”的网络参数，σ代表sigmoid激活函数；Wi和bi为“输入门”的网络参数，Wc和bc为生成候选细胞状态的参数，Ct为当前时刻细胞状态。Wo和bo为“输出门”的网络参数。ht为当前时刻细胞隐藏层输出。通过式(5)表示的“输出门”ot决定哪些部分的细胞状态需要输出，式(6)把细胞状态通过tanh函数处理，得到一个(-1,1)范围的值，再与ot逐对相乘，得到当前时刻隐藏层的输出。由于LSTM在整个时间序列中参数共享，这大大减少了网络所要学习的参数。
LSTM模型训练过程采用的是与经典的反向传播算法原理类似的BPTT算法，大致可以分为4个步骤：1)在时间序列上正向计算每个时间步的输出值；2)反向计算每个时间步的误差项，包括时间和网络层级2个反向传播方向；3)根据相应的误差项，计算每个权重的梯度；4)应用基于梯度的优化算法更新权重。
2.2 启发式搜索修正初始方案
如果初始调度方案满足数据接收任务对资源的要求，并且任务间没有联合接收和资源选择冲突的情况，则是一个可行方案，不需对初始方案加以调整，否则需要结合LSTM提取的天线使用优先级规则(Softmax层输出的概率分布)，进一步对初始方案进行调整。本文选择启发式方法用来解决初始调度方案中数据联合接收和资源选择冲突两个问题。对于数据联合接收的情况，为提高接收天线的利用率，对处于联合接收的时间段的任务做时间裁剪；对于资源选择冲突的情况，为保证数据尽可能地被完全接收，使用基于集束搜索思想的启发式搜索进行冲突消解。以下是方案修正中所用到的启发式信息：
启发信息1 任务集T的冲突度，优先调度冲突度大的冲突集。结合接收任务数量和可用接收天线数量，本文提出一种地面站天线使用冲突程度评价指标，即每个地面站可能任务冲突个数与地面接收天线个数的比值之和，如下所示
(7)
其中：ng为地面站的个数，nt为任务冲突集T中任务的个数，Agk为地面站gk的天线集合，pc
启发信息2 优先调度任务优先级高的数据接收任务。
启发信息3 优先调度任务持续时间长的任务。
启发信息4 优先调度任务开始时间早的任务。
2.2.1 数据联合接收
数据联合接收会造成地面站接收资源的浪费，加剧资源选择冲突。因此，当2个任务属于联合接收时，考虑到地面站接收资源的切换成本和利用效率，对于任务时间完全重叠的任务，取消被包含的任务；对任务时间部分重叠任务，根据启发式信息决定任务裁剪，具体见算法1。为保证数据接收的完整性，任务时间裁剪时需要保留一定时间的重叠时间，视地面站要求而定。处理联合接收的过程也是为数据接收选择唯一接收站的过程。
------------------------------------------
算法1 Algorithm 1
------------------------------------------
Step1:找出任务集T中数据联合接收的任务集合UT，若UT=∅，转Step4；否则，转Step2；
Step2:选择UT中开始时间最早的一组联合接收任务UTest，若UTest属于包含关系，取消被包含任务，转Step1；否则，转Step4；
Step3:若UTest属于部分重叠关系的任务，根据启发式信息1，优先选择引起冲突度小的裁剪方式对任务进行裁剪；如果引起的冲突度相同，则根据启发式信息3，优先裁剪持续时间短的任务；如果任务持续时间相同，根据启发式信息4，优先裁剪开始时间较晚的任务，转Step1；
Step4:输出调度方案。
------------------------------------------
2.2.2 资源选择冲突
在初始调度方案中虽然每个接收任务都分配了一个接收天线，但是如果同一地面站的2个任务在时间上处于包含或部分重叠关系，所分配的接收天线相同，则会出现资源选择冲突的情况，资源约束1)中明确要求同一时刻一部天线只能接收一个任务，此时会导致某些任务不能成功接收。因此，在解决不同的地面站数据联合接收情况后，再使用算法2解决各地面站天线选择冲突的情况，得到最终可用的地面站天线调度方案。算法2使用基于集束搜索(beam search)思想的启发式搜索方法，集束搜索是一种启发式图搜索算法，通常用在图的解空间比较大的情况下，为了减少搜索所占用的空间和时间，在每一步深度扩展的时候，剪掉一些质量比较差的结点，保留下一些质量较高的结点。如果集束宽设置得太小的话，解的范围太窄，难以寻求到较优的解，如果集束宽设置得太大，将会使解空间太大，内存占用和计算量都很大，影响计算效率，并且越靠后的解的质量也越差。因此，在算法2中需要综合解的质量和时间效率选择集束宽的大小，即LSTM为一个任务集中每个任务分配天线时，并不是输出可能性最大的天线，而是可能性较大的前几种情况，再使用算法2得到没有冲突且效果较好的调度方案。
------------------------------------------
算法2 Algorithm 2
------------------------------------------
Step1:找出任务集T中每个任务的可能冲突任务集合，根据式(7)计算每个任务的冲突度,把冲突度大于0的冲突集组成新的集合CT；
Step2:若CT=∅,转Step5；否则，转Step3；
Step3:选择集合CT中冲突度最大的冲突集CTm；
Step4:对于CTm，使用集束搜索，按照启发信息2、启发信息3、启发信息4的先后顺序为CTm冲突集中的任务重新分配天线，返回Step1；
Step5:输出调度方案。
------------------------------------------
3 实验结果与分析
3.1 实验数据
利用中国遥感卫星地面站积累的约16万条遥感卫星地面站资源调度数据，初始调度方案由原算法给出，后期经过地面站工作人员根据当天的接收资源实际可用情况进行调整，因此这些数据中隐含着资源分配的约束规则和地面站工作人员的日常习惯。每条调度数据包含卫星名称、地面站、任务优先级、任务紧急程度、接收开始时间、接收结束时间6个属性，还包含已经分配的天线，因此在网络设计时，把接收任务的属性数据作为网络的输入，所选天线作为网络的输出。
其中，中国遥感卫星地面站历史上累计服务的卫星超过70颗，因此，输入数据中卫星属性值有70多个；由于卫星按照设计的轨道在太空中运行，因此只有在卫星进入地面站接收圈后(即地面站与卫星是可见的)，地面站天线才可进行卫星数据接收工作，数据接收时间为卫星与地面站的可见时间段，对不同卫星，数据接收时间不同；地面站属性值是中国遥感卫星地面站所属的密云站、喀什站和三亚站；任务优先级与不同卫星下传数据的重要程度相关，分为5个等级，等级越高，优先级数值也越大；任务的紧急程度分为“紧急”和“一般”2种。
在数据预处理时，统计数据接收任务中所有不重复出现的属性值，作为训练数据集的词库，并使用词嵌入技术，把每个词映射为实数域特定维度的词向量，相应的每条数据接收任务映射成特定维度的向量，作为LSTM网络每个时间步的输入。天线作为网络的输出，有多种可选天线，因此在使用LSTM得到初始调度方案时，把该问题视为一个多分类问题。
3.2 评价函数
本文使用准确率来评价LSTM模型的优劣，使用F1分数选择最佳模型，使用接收方案成本函数评价数据接收方案优劣。
1)准确率(Accuracy)：准确率是评价模型正确分类的能力，准确率越高，则模型越好。Top1准确率如下所示
(8)
当LSTM分类模型在Softmax层输出概率值最大的天线和实际使用天线相同时视为正确分类，TP1代表正确分类的个数，P代表样本的总个数。Top5准确率为
(9)
当LSTM分类模型在Softmax层输出概率值较大的前5部天线中任意一部与实际使用天线相同均视为正确分类，TP5代表正确分类的个数，P代表样本总个数。
2)F1分数(F1score)：为精确率(precision)与召回率(recall)的调和均值，两者都高的情况下，F1分数也会很高，F1分数越高，说明模型越稳健，本文使用F1分数来选择模型训练中的最佳模型，其计算公式为
(10)
针对本文的LSTM模型，精确率代表预测为使用某部天线的所有接收任务中，实际上也使用这部天线所占的比率；召回率代表实际上使用某部天线的所有接收任务中，预测结果也使用这部天线所占的比率。
3)接收方案成本：在地面站资源调度领域，对调度方案的优劣尚没有统一的评价标准，因此，本文从天线使用成本、任务因天线资源选择冲突不完整接收的惩罚两个角度制定了如下所示的调度方案成本函数。
(11)
式中:W(i,j)表示任务i使用天线j来接收时的成本；ant(i,j)表示天线的使用情况，如果天线j被用来接收任务i，则其值为1，否则为0；P(i)表示任务i的重要程度，接收任务的重要程度与任务优先级成正比；pnc(i)表示任务i因为接收资源选择冲突未接收的任务时长。Cost的值越低，说明接收方案越优。
3.3 分类模型训练与选择
LSTM分类模型运行环境为python3.6，深度学习框架Pytorch0.4。训练模型时使用交叉熵损失函数，并使用带动量的随机梯度下降法优化网络参数。随机梯度下降法的初始学习率为0.01，动量参数为0.9。除此之外，训练模型时使用dropout[40]正则化技术避免过拟合，且dropout的概率设为0.2。使用固定的迭代次数训练模型，并在每次迭代中使用验证集监视模型性能。训练结束后，选择验证集上F1分数最高的模型作为最终模型。模型训练过程中损失函数变化如图6所示，细线代表训练损失，粗线代表验证损失，模型在第3次迭代时就已经收敛，随着训练迭代次数的增加，模型在训练集上的损失函数值继续减少，在验证集上的损失函数值趋于平稳。在训练过程中，模型在训练集上的准确率最高为89.6%，Top5准确率为98.5%，在验证集上的准确率最高为77.7%。模型在验证集上F1分数最高为77.7%，保留此模型作为测试的分类模型。
图6 损失函数变化曲线图
3.4 结果分析
3.4.1 案例规模
为验证算法的有效性和实用性，本文从遥感卫星地面站实际运行业务中选取15组不同规模的案例，表1显示每个案例中接收任务数量和接收任务总时长。本文考虑密云站、喀什站、三亚站3个地面站，各地面站的天线资源情况如表2所示。
表1 案例规模
表2 地面站天线资源
3.4.2 LSTM模型准确率
表3反映使用LSTM模型得到初始调度方案时，每个案例的Top1准确率和Top5准确率。在对每个案例的初始调度方案修正时，根据Top5准确率的大小调整集束搜索的束宽，避免束宽设置过大或者过小。从表3来看每个案例的Top5基本接近于1，LSTM可以输出每个接收任务可能性较大的前5个候选天线，在对初始调度方案修正时设置束宽大小为5。
表3 LSTM模型准确率
3.4.3 求解时间和接收成本
本文从算法求解时间和公式(11)给出的方案接收成本两个角度来比较本文算法、原算法和原算法+人工调整这3种方式调度方案的优劣。本文选取的15个案例每个案例的接收成本和求解时间如表4所示，本文算法接收成本和求解时间的平均值分别是原算法的96.4%和59.9%，所以整体来看本文算法优于原算法；本文算法接收成本的平均值是原算法+人工调整的99.5%，说明两者效果相当。
表4 结果对比
图7 案例接收成本折线图和求解时间折线图
3.4.4 案例分析
表5和表6分别为案例1中任务1～9(日期：2019年9月13日)和案例14中任务1～16(日期：2019年9月15日)的调度结果。从接收时长和调度结果两个方面，对LSTM、本文算法、原算法和原算法+人工调整进行对比分析，其中“计划接收时长”为任务时间窗口的长度、“实际接收时长”为调度结果中任务的实际接收时长；任务优先级分为5级，由高到低依次用P1～P5来表示；本实验中卫星有74个，依次用S1～S74来表示。
本文算法为LSTM结合启发式搜索的方法，即使用启发式搜索协助处理LSTM给出的初始调度方案中资源选择冲突和数据联合接收两种情况。表5中，LSTM调度结果为任务2和任务3均选择KS4天线接收。由于这2个任务时间重叠，属于资源选择冲突。本文算法加入启发式搜索调整后，任务2使用KS5天线接收，任务3使用KS4天线接收，避免了资源选择冲突。表6中，LSTM调度结果为任务5和任务6均选择KS3天线，存在资源选择冲突；本文算法结果为任务5使用KS3天线接收，任务6使用KS4天线接收，避免了资源选择冲突。任务8、任务9和任务13，均为卫星S5任务，分别下发到密云站、喀什站和三亚站，且这3个数据接收任务在接收任务时间上有重叠，属于数据联合接收情况。其中任务8和任务13接收时间部分重叠，且任务8和任务13包含任务9。本文算法使用启发式搜索处理后，取消任务9，并截掉任务13前半部分115 s的接收时长，避免了接收资源浪费。可见，启发式搜索可有效处理资源选择冲突和数据联合接收，比仅依靠LSTM得到的调度方案更优。
表5 案例1:任务1～9调度结果
表6 案例14:任务1～16调度结果
从表5可以看出，本文算法和原算法相比，任务1～3、任务5～9实际接收时长相同，任务4的实际接收时长不同，本文算法完整接收任务4，而原算法因任务时间冲突取消任务4，导致任务4的数据未能成功接收；原算法给出的调度方案经人工调整后，任务4被成功安排接收天线。从表6可以看出，本文算法和原算法相比，任务1～6、任务8、任务10、任务12、任务14～16实际接收时长相同，而任务7、任务9、任务11、任务13实际接收时长不同。其中，任务7和任务11属于数据联合接收，本文算法对任务11做了时间截取，且截掉153 s的接收时长，原算法对任务7做了时间截取，也截掉153 s的接收时长，但任务7和任务11分别属于密云站和三亚站，由表2可知，密云站的天线资源多于三亚站，因此本文算法中对任务11进行截取更加合理；任务8、任务9、任务13也属于联合接收，原算法没有对此接收任务做处理，而本文算法取消了任务9，并截掉了任务13的115 s的接收时长，考虑到地面资源相对于接收任务量的紧缺性，本文算法处理结果更合理。
4 结束语
总体来看，与中国遥感卫星地面站使用的结合启发式规则的遗传算法相比，本文提出的LSTM结合启发式搜索的智能调度方法的优势主要体现在两个方面。其一，在任务调度精度方面，本文算法给出接收方案的接收成本为遗传算法的96.4%，因此，本文算法的调度结果与遗传算法相比略好，并且本文算法从大量历史数据中学习调度规则和经验，结合启发式算法，能够得到相对稳定的任务调度结果。而遗传算法虽然也能获得比较好的任务调度结果，但是，遗传算法具有一定的随机性和不确定性，需要人工复核调度结果。其二，在计算效率方面，本文算法避免构造复杂的数学模型，运算简单，计算所需时间仅为遗传算法的59.9%。本文算法仍然有其不足之处，当地面站新增接收资源或者接收资源约束规则发生变化时，本算法缺乏灵活性。
