基于改进合同网协议的分布式卫星资源调度

靳 鹏，李 康，*

（1.合肥工业大学管理学院，安徽 合肥 230009；2.合肥工业大学过程优化与智能决策教育部重点实验室，安徽 合肥 230009）

0 引 言

遥感卫星能够快速准确地进行对地观测以获取地表信息，在国防建设、环境灾害防治等领域发挥重要作用［1-2］。卫星任务规划就是在满足相关约束的前提下，将待观测任务分配给最合适的卫星，使得规划目标最优［3］。卫星任务规划问题已经被证明为非确定性多项式难（non deterministic polynomial hard，NP-hard）问题［4］。

传统的卫星地面任务规划模式存在动态响应不及时、过分依赖地面资源、时效性差等问题，难以高效开展卫星任务规划［5］。随着卫星技术的发展，卫星已经具有一定的自主规划能力，卫星之间通过协同进行自主任务规划，能有效提高卫星任务规划的效率。在此基础上，如何进行有效的卫星资源调度和任务分配是卫星规划的重点［6-7］。

卫星任务规划问题多采用集中式架构进行处理。文献［8-10］使用蚁群算法等启发式算法进行规划，可以在短时间内获得规划方案，但算法稳定性较差。文献［11］提出了一种星地联合的运行机制进行任务规划，能有效提高卫星对非预期任务的响应能力。文献［12］采用模糊神经网络进行卫星任务规划。上述集中式架构方式虽然实现较为简单，但是存在任务响应能力差、执行效率低等诸多缺陷［13］。分布式架构以其通信分散、鲁棒性好等优点成为卫星任务规划的有效架构方式，文献［14-16］建立了分布式任务规划求解框架，并通过实验表明了分布式架构的优势。文献［17-20］采取遗传算法等启发式算法进行任务规划，但仅适用于任务规模小并且需求简单的卫星任务规划。合同网是解决分布式任务规划的一种有效方法［21-22］，因其分配效率高、适应动态环境强等特点在分布式任务规划中得到广泛应用。文献［23-24］引入合同网协议，设计相关合同网算法，有效解决了卫星任务分配问题。文献［25-26］对传统合同网进行改进，设计投标者初选策略以及诚信机制，有效降低了系统的通信负担，但每轮只对单个任务进行处理的方式效率较低，卫星之间没有建立有效的协调机制。文献［27］面向应急任务建立了基于虚拟星座的多智能体任务规划模型并设计了改进的合同网协议。文献［28］针对海洋目标的快速响应问题设计了改进的合同网算法，充分利用了卫星计算的实时特征和灵活性并且对意外任务迅速响应。文献［29］在任务聚类方法的基础上制定了合同网协议的二次分配策略，提高了分配效率以及动态响应能力。文献［30］设计了分层分布式任务框架，顶层规划将卫星和任务分解为集群，底层规划根据合同网协议进行任务分配。综上，通过对上述文献的分析发现，现阶段进行分布式卫星任务规划中主要存在以下问题：任务的处理通常是逐个进行的，在大规模下会产生较大的通信量；卫星之间没有建立良好的协作机制造成资源的浪费；没有考虑分布式任务规划中全局和局部代理目标之间的不一致性［31］。

为解决上述问题，本文设计了改进的合同网协议。首先，建立卫星任务规划的双层规划模型，上层为主星规划模型，规划目标是达到全局最优，底层为从星规划模型，规划目标是各从星达到各自局部的最优。其次，引入并发机制，包括全任务投标策略以及二次中标策略。然后，建立了可解约循环合同网，引入逼近理想解排序方法（technique for oder preference by similarity to an ideal solution，TOPSIS）完善评标策略。最后，提出一种基于自适应退火的合同网算法（contract network algorithm based on adaptive annealing，CNAA）进行任务规划。通过仿真实验证明CNAA能有效提高规划的质量，适用于分布式卫星任务规划。

1 问题描述与建模

1.1 问题描述

分布式卫星任务规划可以描述为m个具有自治能力的卫星在一定时间内通过协同对n个任务进行观测，使得目标函数最优。合同网协议是解决分布式任务规划的一种有效方法，通过模仿市场机制中的“招标-投标-评标”过程完成对任务的规划。在使用合同网协议解决分布式卫星任务规划问题时，将卫星分为主星和从星，分别充当招投标过程中的招标方和投标方。规划过程如图1所示。首先，主星将任务信息作为招标信息广播至从星进行招标；然后，各从星在收到招标信息后根据信息进行自主规划生成投标方案，并决定是否投标；最后，主星对返回的所有投标方案进行评价，确定中标方案，并将中标信息广播至从星。整个规划过程需要进行多次招投标，最终输出一个完整的任务分配方案。由于卫星任务规划的复杂性，本文做出以下基本假设：①待观测任务为点目标任务，任务有一定的持续时间；②携带的传感器类型唯一，观测过程中数据实时下传；③各个卫星之间存在实时通讯；④不考虑云层等因素对观测的影响。

图1 合同网协商协议Fig.1 Contract network negotiation agreement

1.2 数学模型

1.2.1 模型符号

S′：表示主星；

S＝｛S1，S2，…，Si，…，Sm｝：表示从星序列；

T＝｛t1，t2，…，t j，…，tn｝：表示待观测任务集合，共有n个任务；

t j＝〈P j，durj，dtj〉：表示任务的相关信息，其中P j表示任务t j的观测收益，durj表示任务t j的观测持续时间，dtj表示任务t j的任务最迟完成时间；

OTWij＝〈OTSij，OTEij〉：表示任务t j在卫星S i上的实际观测时间窗，OTSij和OTEij分别表示该观测时间窗的开始时间和结束时间；

PTE：任务规划的截止时间；

cij：卫星Si观测任务t j消耗的存储量；

Ci：卫星Si的最大存储限制。

1.2.2 模型变量

T q：表示第q次进行招投标的任务集合；

CTi：表示卫星Si规划方案中任务的总数；

ETi：表示卫星Si上规划方案的观测结束时间，ETi＝OTEi（lsti），其中lsti表示卫星S i上最后一个任务的观测结束时间；

rdij：表示卫星Si对任务t j进行观测时所产生的扰动，本文考虑3种形式的扰动：①任务安排到原任务序列的空闲时间片内，此时rdij＝1；②任务安排导致原任务序列上的任务被替换，此时rdij＝1；③任务安排导致原任务序列上的任务不能观测，此时rdij＝2。

1.2.3 数学模型

（1）从星模型

其中，式（1）表示从星进行任务规划时的最大化收益以及最小化扰动的目标，w p和w r分别表示收益和扰动的权重；式（2）表示唯一性约束，即一个任务最多被观测一次；式（3）表示任务进行观测时必须要满足时间窗要求，即任务的执行时间窗必须在可见时间窗内，且都早于任务的最迟完成时间；式（4）表示任务的实际观测结束时间和任务观测持续时间的关系，即实际观测结束时间等于实际观测开始时间和任务观测持续时间的和；式（5）表示存储约束。

（2）主星模型

其中，式（6）表示目标函数，由最大化观测收益、最大化完成时间差以及最大化负载均衡3个部分组成。规划总目标是这3个目标的加权和，w1、w2、w3分别表示3个目标的权重；式（7）表示负载均衡值，计算方式为规划方案中各卫星完成任务数量的标准差大小；式（8）表示任务数量之间在招投标过程中的约束，每轮投标的任务数等于总任务数减去已安排观测的任务数；式（9）表示方案的观测结束时间小于任务规划截止时间。

2 改进合同网设计

本文对传统合同网进行改进，设计多属性评标机制以及基于并发机制的可解约循环合同网。

2.1 多属性评标

本文设计多属性评标机制以完善评标过程。首先，针对各投标方案，采用向量规范化的方式进行归一化处理；然后，采用TOPSIS得到每个卫星方案的最终指标值；最后，将综合指标值最高的方案作为中标方案。

（1）构建规范决策矩阵

假设有f个投标方案，其中f≤m，第h个卫星的投标方案可以用一个三元组〈BPTh，ETGh，CTh〉进行表示，其中BPTh表示卫星S h投标方案中的任务集合、ETGh表示卫星S h投标方案的观测结束时间与规划截至时间的差值、CTh表示卫星Sh规划方案中包含的任务总数。主星在获得各个投标方案后通过计算各决策指标的值将各投标方案转化为可比较的新投标方案NCh，h＝｛1，2，…，f｝，其中NCh＝（FPh，ETGh，LDh）T。FPh＝，表示投标方案的任务观测收益和；ETGh＝PTE-ETh，表示最终观测完成时间差；LDh＝，表示投标方案的负载均衡率，其中对决策矩阵中的值进行预归一化处理得到规范决策矩阵，这里采取向量规范化的方式得到决策矩阵［z hg］f×3，计算方式为

（2）计算方案综合指标，确定中标方案

在得到规范决策矩阵后，首先计算理想解和负理想解

然后，计算各个方案到理想解和负理想解之间的加权距离和：

最后，计算各个方案的综合评标指标CEh，将综合评价指标最大的方案作为中标方案。

2.2 基于并发机制的可解约循环合同网

传统合同网“单任务投标，单代理中标”的模式在大规模任务规划下会造成较大的通信量。本文设计并发机制来减少协商次数，包括全任务招标和二次中标策略。首先，在每一轮招投标时，主星都会获取当前未进行安排观测的任务，将其作为招标信息进行招标，各从星根据招标信息生成规划方案并进行投标方案的筛选来决定是否投标，投标方案的筛选如图2所示。其次，为了充分利用卫星资源，当存在多个投标方案时，采取二次中标策略选择两个中标方案。最后，引入可解约机制，允许上轮中标卫星在下轮投标过程中对已签约的任务进行解约处理。综上，本文设计了基于并发机制的可解约循环合同网，主要步骤如下：

图2 投标方案筛选Fig.2 Selection of bidding scheme

步骤1主星获得待观测任务序列T，进入循环招投标过程，令q＝1，设定循环终止次数N te；

步骤2主星开始第q次招投标，获取当前所有未安排观测的任务组成任务序列T q，若T q为空，转步骤7，否则，转步骤3；

步骤3主星将Tq作为招标任务广播给从星，各从星根据Tq生成当前规划方案集合｛Fiq，i＝1，2，…，m｝。同时，筛选投标方案集合｛TFiq，i＝1，2，…，m｝，其中TFiq＝｛Fiq∩Tq｝。若各从星投标方案都为空，转步骤7，否则，转步骤4；

步骤4主星获取投标方案集合，采用多属性评标策略进行评标，选择首次中标方案TFiq，中标卫星将规划方案更新为F iq。更新当前未安排观测的任务序列T q。若T q为空，转步骤7；否则，转步骤5；

步骤5进行二次评标过程，筛选出针对T q的投标方案集合｛，i＝1，2…，m｝，其中＝｛F iq∩T q｝，若各从星投标方案都为空，转步骤7，否则，转步骤6；

步骤6进行多属性评标，选择二次中标方案TF′iq，中标卫星将方案更新为F′iq。更新当前未安排观测的任务序列T q。两次都未中标的从星规划方案不进行更新；

步骤7若所有任务都被安排观测或目标函数值连续N te相同，则规划结束，否则，令q＝q＋1，转步骤2。

3 CNAA设计

为了快速且有效的完成任务规划，本文设计了CNAA解决分布式卫星任务规划问题。

3.1 自适应退火

各从星在收到任务序列后，如何生成规划方案是规划的重点，本文设计了自适应模拟退火算法以生成投标方案。首先，构造3种领域算子以增强解的多样性；其次，设计自适应策略解决模拟退火算法参数敏感性强的问题，包括自适应升温策略以及动态等温步长。

3.1.1 领域生成算子设计

本文设计3种邻域生成算子，每次生成邻域解的过程会随机选择一种算子生成邻域解。3种算子分别为插入、删除以及移位算子，如图3～图5所示。

图3 插入算子Fig.3 Insertion operator

图4 删除算子Fig.4 Delete operator

图5 移位算子Fig.5 Shifted operator

3.1.2 自适应升温策略

在模拟退火算法中，一般来说，初始温度应该设置的足够大从而保证搜索质量，但是过高的温度会增加算法的运行时间。本文采取自适应升温策略确定初始温度，具体步骤如下：

步骤1设定初始温度为TE*，等温步长设定为当前任务数，获得满足约束的初始解；

步骤2基于3种算子生成邻域解，获得当前温度下的邻域解集合。检验所有邻域解，若所有邻域解都被接受，转步骤4；否则，转步骤3；

步骤3更新初始温度。更新的方法为：TE*＝TE*＋10；同时，返回步骤1；

步骤4重复步骤1～步骤3共10次，取10次初始温度的平均值作为最终初始温度。

3.1.3 动态等温步长

等温步长的值对模拟退火算法的影响也很大。较大的等温步长可以生成更多的邻域解，以便于找到更优的解，但同时也会导致计算的时间大大增加。针对这一特点，设计了与温度有关的动态等温步长，第v次迭代下的动态等温步长N v计算公式为

式中：λv表示第v次进行等温步长调节的系数，λv的计算公式为

式中：t v表示第v次迭代下的温度；α为降温速率；n为任务数量；n v表示在温度t v下最优解的完成任务的数量。

3.1.4 自适应退火算法

本文自适应退火算法用于各从星生成规划方案，算法的输入为任务序列T′以及从星S i，i∈｛1，2，…，m｝，算法的输出为规划方案F iq。算法最开始的初始解和最优解都设定为卫星Si未进行退火的原规划方案，算法流程如下：

步骤1执行自适应温度策略获得初始温度TE*，设定终止温度TEmin，降温速率f c，设定初始等温步长N c，令c＝0，v＝0；

步骤2进行判断，若TE*＞TEmin，转步骤7。否则，转步骤3；

步骤3进行判断，若c＞N c，转步骤6。否则，转步骤4；

步骤4随机选择生成算子生成领域解，以Metropolis准则判断是否接受领域解；

步骤5更新当前解和最优解，c＝c＋1，转步骤3；

步骤6v＝v＋1，根据式（16）和式（17）更新等温步长N c；同时，进行降温操作，TE*＝f c·TE*，令c＝0，转步骤2；

步骤7退火结束，输出Si的规划方案。

3.2 CNAA

本文设计CNAA进行分布式卫星任务规划。算法的输入为任务集合T，卫星集合｛S1，S2，…，Sm｝，算法输出为最终规划方案，主要算法流程如下：

步骤1算法初始化，对任务集合T按照收益从大到小进行重排序，若存在多个收益相同的任务，按照任务观测持续时间由小到大进行二次排序；

步骤2进入循环合同网，主星获取所有未观测任务信息。若所有任务都被观测，转步骤7。否则，基于全任务投标策略进行投标，转步骤3；

步骤3各从星基于自适应退火算法生成规划方案；

步骤4筛选投标方案，若各从星投标方案都为空，转步骤7。否则，基于多属性评标策略进行评标，更新中标卫星的规划方案和未观测任务序列，转步骤5；

步骤5若当前未观测任务序列为空，转步骤7。否则，执行二次评标策略，更新二次中标卫星的规划方案和未观测任务序列，转步骤6；

步骤6若最优收益连续N te次保持不变，转步骤7。否则，循环步骤2～步骤5进行方案迭代更新；

步骤7停止循环，输出方案。

4 仿真算例

本节通过实验验证本文所提出的方法的合理性和有效性。实验计算机配置为Intel（R）Xeon（R）W-2255，CPU＠3.70 GHz，编程语言为java，基于IDEA 2021开发环境实现。本文利用仿真软件生成3颗、4颗、5颗卫星的数据。任务规划时域为2017年4月23日00：00：00～2017年4月23日24：00：00。随机生成50、100、150、200、250、300、350、400、450、500个任务集合的10组算例，实验过程中每组算例运行50次，取50次的平均值作为最终结果，部分任务信息如表1所示。由于卫星任务规划问题的复杂性，目前没有该领域公认的实验测试集。本文首先在3颗卫星资源下使用CNAA的求解结果与CPLEX求解器的求解结果进行对比以表明本文算法的有效性；其次，在3颗卫星资源下，与基于二次分配策略的合同网算法［29］（contract network algorithm based on secondary allocation strategy，CNSA）以及集中式算法（centralized algorithm，CA）对比以表明本文算法的合理性；最后，将3颗卫星的规划结果和4颗以及5颗卫星的规划结果进行对比，分析资源增加后对规划的影响情况。

表1 部分任务信息Table 1 Partial task information

4.1 算法有效性实验

为了验证CNAA的有效性，将上述10组算例在分别使用CNAA以及CPLEX求解器进行任务规划，规划结果对比如表2所示。

表2 CNAA和CPLEX结果Table 2 CNAA and CPLEX results

从表2可以看出，CNAA相较于CPLEX求解器能够以较短的时间完成任务规划。当任务规模较小的时候，CNAA的观测收益率和CPLEX求解器的观测收益率基本保持一致。当任务规模增大至150时，CNAA的观测收益率和CPLEX求解器的观测收益率之间的差距约为2%。当任务规模增大至250时，CPLEX就无法对其进行求解，而CNAA仍能在较短的时间内完成任务规划，综上，说明了CNAA的有效性。

4.2 算法合理性实验

为了验证CNAA和改进合同网协议的合理性，将上述10组算例分别使用CNAA、CNSA以及CA进行任务规划，通过对比表明CNAA 和改进合同网协议的合理性。

（1）为了说明CNAA在观测收益率、任务完成率以及规划耗时的合理性，将10组算例分别使用CNAA、CNSA、CA进行规划。实验结果如表3以及图6～图8所示。

表3 收益率和完成率以及规划耗时对比结果Table 3 Yield and completion rate and planning time comparison

图6 观测收益率对比Fig.6 Comparison of observed yield

图7 任务完成率对比Fig.7 Task completion rate comparison

图8 规划耗时对比Fig.8 Comparison of planning time

从表3以及图6～图8可以看出，在本文进行试验的10组算例下，CNAA在任务规划的观测收益率以及任务完成率上都明显高于CNSA，在观测收益率方面，CNAA的观测收益率比CNSA平均提高约11.5%，与CA相比，差距不超过2.5%。在任务完成率方面，CNAA的任务完成率比CNSA平均提高约16.3%，与CA相比，差距不超过3%。随着任务规模的增加，3种算法在观测收益率以及任务完成率之间的差距趋于稳定。

在规划耗时方面，CNAA的规划耗时优于CNSA 和CA的规划耗时。当任务规模较少时，3种算法的规划耗时都比较短，但当任务规模增大时，CNSA和CA的规划耗时迅速增加。尤其是集中式规划CA在任务规模超过300后，其规划耗时呈现指数型的快速增长趋势，而CNAA随着任务规模的增加，其规划耗时的增长趋势较为平缓，且保持在一个相对较短的水平。综上，CNAA在观测收益率、任务完成率两个方面均优于CNSA，且与CA之间的差距较低。在规划耗时方面，CNAA不管是在小规模还是大规模算例中均能以较短的规划时长获得较好的规划方案。

（2）为了说明改进合同网协议的合理性，将上述10组算例分别使用CNAA、CNSA、CA进行任务规划，通过平均完成时间差以及负载均衡值以及协商次数以表明改进合同网协议的合理性。其中，完成时间差是任务规划截至时间和最终任务完成时间的差值，差值越大，说明任务完成的越早。负载均衡值是各卫星完成任务数量的标准差，负载均衡值越小，说明任务在各卫星上的数量分布越均衡。平均完成时间差、负载均衡值以及协商次数的结果分别如表4以及图9～图11所示。

表4 平均完成时间差和负载均衡值以及协商次数对比结果Table 4 Comparison results of average completion time difference，load balancing value，and negotiation times

图9 时间差对比Fig.9 Time difference comparison

图10 负载对比Fig.10 Load comparison

图11 协商次数对比Fig.11 Negotiation times comparison

从表4以及图9可以看出，当任务规模为50时，CNAA的平均完成时间差小于CA的平均完成时间差，这是因为集中式规划会充分利用卫星的能力，当任务规模较小时，会出现只需要部分卫星就完成任务观测的情况，无观测任务的卫星的完成时间差就为规划时域的大小，从而造成较大的平均完成时间差。随着任务规模增大，当任务规模达到100后，CNAA的平均完成时间差均大于CNSA和CA的平均完成时间差，CNAA的完成时间比CNSA 完成时间平均早12.3 min，比CA的完成时间平均早6.2 min左右，能够更早地完成任务观测。随着任务规模的进一步增加，各算法的平均完成时间差都逐渐减小，这是因为随着安排观测任务数的增加，会导致观测时间窗后移，最终观测任务的观测时间窗也会渐渐靠近规划截止时间，造成完成时间差的降低，从而出现完成时间差随着任务规模增大而减小的情况。

从表4以及图10可以看出，在任务规划的负载均衡方面，当任务规模为50时，CNAA的负载均衡值大于CNAA的负载均衡值，这是因为传统合同网算法采取单任务投标形式，所以在任务规模较少的时候，多次投标会使任务有更大概率分散到各个卫星上，从而使得负载更均衡。但随着任务规模增大，CNAA的负载均衡值差均大于CNSA和CA的平负载均衡值，说明在大规模下CNAA更能保证规划的负载均衡。

对于通信协商成本使用协商次数进行衡量，从表4以及图11可以看出，CNAA的协商次数显然小于CNSA协商次数。在不同规模下，CNAA所需要的协商次数平均只有CNSA的22.7%，大大减小了通信成本。随着任务规模的增加，规划的复杂性也大大增加，从而导致协商的次数也会增加。传统合同网采用单任务招投标，所以其协商次数就等同于任务数，CNSA采用了二次分配策略，所以协商次数高于任务数。不管是传统合同网算法还是CNSA，CNAA所需的协商次数都有很大的优势。综上，CNAA在平均完成时间差、负载均衡以及协商次数3个方面均优于CNSA和CA，表明了CNAA的合理性。

4.3 卫星资源影响分析

为了分析不同规模的卫星资源下对规划的影响程度，将卫星个数增加至4颗和5颗，并且对10组算例进行规划，从观测收益率、协商次数、规划耗时3个指标进行分析，规划结果如表5以及图12～图14所示。

表5 不同资源下规划结果对比Table 5 Comparison of planning results under different resources

图12 收益率对比Fig.12 Yield ratio comparison

图13 协商对比Fig.13 Negotiating comparison

图14 耗时对比Fig.14 Time consuming compared

从表5以及图12可以看出，随着卫星资源的增多，观测收益率随之增加。当任务规模达到200之后，观测收益率的差距得到进一步体现，从规划结果可以看出，4星相较于3星观测收益率平均提高了约4.8%，5星相较于3星观测收益率提高了约6.5%。

另一方面，规划耗时和协商次数随着卫星资源的增多而减少。4星相较于3星规划耗时平均减少了约3.1 s，5星相较于3星规划耗时平均减少了约4.5 s。4星相较于3星协商次数平均减少了约19.3次，5星相较于3星协商次数减少了32.3次。在任务规模不变的情况下，随着卫星资源的增加，规划能力得到提高，能够以更少的协商次数完成对任务的规划，协商次数的减少就会降低规划的时长。不同卫星资源下的规划对比实验揭示了任务规划和卫星资源之间的影响关系。

5 结束语

本文针对分布式卫星任务规划问题，提出了可解约循环合同网进行任务规划。设计全任务投标策略以及二次评标策略解决传统合同网协商次数多的问题，有效降低了卫星的通信成本。建立多属性评标策略，弥补了评标属性单一的问题。提出了CNAA进行分布式任务规划，通过对比实验证明了算法的有效性和合理性。在本文的基础上，下一步的研究主要考虑：①当应急任务到达时，如何及时响应且快速完成任务规划；②当卫星发生通信故障或成像不能完成情况时，如何合理优化调整现有规划方案。