加权负载均衡合同网大规模星座任务分配方法

王朝辉,徐 瑞,李朝玉,王 棒

1.北京理工大学宇航学院,北京 100081 2.深空自主导航与控制工业和信息化部重点实验室,北京 100081

0 引言

随着航天运载能力的进步和小卫星批量化生产测试技术的成熟,使用分布式小卫星星座替代传统大型卫星逐渐成为主要发展方向。低轨道大规模星座卫星密度大,对地覆盖率高,通信时延低,重访周期短,相比传统高轨道卫星在遥感和通信领域具有巨大优势。在商业航天市场上,由多达数百颗甚至上万颗运行在低轨道的卫星组成的大规模星座是当前各航天大国的竞争热点。但随着星座在轨卫星数量的增加和卫星载荷灵活性的提升,星座调度与任务规划的求解复杂度也急剧增加[1-2]。传统的地面站集中式卫星任务规划模式无法适应高灵活、快响应的大规模星座任务规划需求[3]。采用星上自主分布式任务分配可以显著提高星座的快速响应能力和系统自主性。

在通信领域,美国SpaceX公司建设的“Starlink”星座已完成4200颗卫星部署,拥有超过100万活跃用户;英国OneWeb公司建设的“OneWeb”星座已完成618颗卫星的发射,初步完成一期组网目标,即将形成全球服务能力。在遥感领域,美国Planet公司建设的“Dove”星座已发射超过450颗卫星,并保持200颗以上的卫星在轨运行,每天可以获取超过3亿平方公里的地面遥感图像;我国长光卫星公司建设的“吉林一号”星座现有72颗卫星在轨运行,可实现全球任意地点单日重访23～25次,最快可在15 min内完成一次全流程应急观测。在军用领域,美国国防部太空发展局于2019年提出了国防太空架构(NDSA),计划由数百颗小型卫星组成灵活、弹性、敏捷的系统,执行数据通信、预警、战斗管理、导航、地面支持和太空威慑等任务[4]。

随着星座在轨卫星数量的增加和遥感卫星观测灵活性的提升,分配问题求解空间大幅增大,问题约束进一步复杂化,导致星座对地观测任务分配的求解复杂度也急剧增加[2]。传统卫星调度模式中,卫星对地面目标观测任务首先需要在地面控制中心解算并生成指令,通过测控站将指令上注至卫星,卫星接收指令后按指令进行观测并下传观测数据。在该模式下,卫星只能在通过地面测控站的通信窗口内接收指令上注,并在下一次经过任务目标时进行观测,任务执行灵活性差,响应时间长。随着低轨星座中星间链路的普及以及星上计算处理能力的提升,采用星上自主分布式任务规划可以实现系统对任务的实时响应,自主计算并分配观测窗口,减轻地面测控站和系统中各星的计算负载,减少部分卫星失效对整个系统的影响,有效提升星座的快速响应能力和资源利用率。

卫星自主任务规划问题已经受到了广泛关注,并已在部分任务中实际应用。2000年NASA发射的地球观测-1号卫星(EO-1)使用自主规划软件,大幅度提高了卫星的响应速度,并随后与陆地卫星-7号(Landsat-7)首次进行了卫星分布式协同的相关验证[5-6]。张正强等建立了分层分布式多Agent结构,设计了优先级任务选择策略和动态插入方法[7]。高黎等对分布式卫星系统(DSS)任务优化分配问题进行了分析,将其转化为集覆盖问题,设计了基于合同网的严格启发式优化算法[8]。王冲等采用松耦合异步业务总线和基于自治的协同任务规划算法,实现了系统可扩展性,在此基础上设计了基于多智能体合作协同进化的多星协同任务规划方法[9-11]。庞中华针对移动目标、高低轨协同观测等问题设计了高轨卫星离线任务规划算法和低轨分布式在线规划算法[12]。Jiang等针对协同观测任务建立了网络化协同任务规划模型,并设计了改进遗传算法,提高了收敛性能[13]。薛志家等建立了综合考虑平台和载荷约束的模型,并针对突发任务设计了启发式自主任务规划算法[14]。Li等针对通信受限情况下的DSS系统对突发目标进行观测,设计了单颗卫星的在线调度算法和基于合同网的协调算法[15-16]。Wang等将深度强化学习方法引入观测调度问题求解,通过训练神经网络来执行调度任务[17]。Du等设计了任务聚类方法对集群目标进行预处理,并通过合同网方法进行二次分配,对失败任务进行重新插入,改善了集中式多Agent系统的灵活性问题[18]。甘岚等针对机动星座对多个区域目标的观测任务规划问题,设计了卫星变轨策略、并给出了观测策略,优化了观测总面积[19]。刘立昊设计了博弈协商机制求解都行分布式任务规划,较好地解决了较大规模情况下求解时间长,收敛慢的问题[20]。王俊等基于多Agent方法提出了一种基于时间窗适应的自主任务规划启发式算法[21]。高天旸等提出了一种分布式星座协同迭代优化策略,在此基础上设计了一种分布式协同进化算法[22]。靳鹏等设计了一种可解约循环合同网,减少了规划过程的协商次数,提出了一种自适应退火算法求解分布式卫星资源调度问题[23]。彭晨远等针对多星飞越巡察任务提出了一种窗口筛选计算模型和多约束任务规划算法[24]。

在现有研究中,对星座的的分布式规划问题进行了部分讨论,但是大规模星座在满足任务完成率的前提下,需要进一步提高系统响应速度,改善规划求解效果,现有文献缺少对大规模星座自主任务分配问题的讨论。本文针对大规模星座对地面固定点目标观测任务分配问题,建立了基于合同网协议的分布式任务分配模型;给出了适应大规模星座的参与投标卫星筛选策略,提出了一种综合考虑任务延迟时间和观测窗口质量的任务收益评估方法;使用基于加权负载均衡的合同网算法进行任务分配。最后通过仿真验证了该算法对于大规模星座分布式观测任务分配的高效性。

1 问题提出与描述

1.1 问题提出

以低轨对地遥感卫星星座为例,描述星座自主任务分配问题。假设所有的卫星都具有基本的自主定轨与轨道递推能力;所有的卫星都可以和星座内的其他卫星通过星间通信链路保持通信;卫星搭载对地观测载荷,在任务期间卫星不进行轨道机动,但可以通过姿态机动观测星下点周围一定区域范围内的目标;卫星具有一定的星载计算能力,可以根据当前位置计算相应目标的观测窗口,并评估窗口收益,同时可以对收到的其他卫星的投标信息进行评估。

卫星执行任务的流程如下:首先由地面用户向星座内的任意一颗可通信的卫星上传任务目标坐标,卫星收到目标坐标后向星座内其他卫星发送任务目标信息。在所有卫星接收到任务目标信息后,每颗卫星根据当前轨道数据计算轨道递推和目标观测窗口。得到窗口后,星座开始任务招投标流程,选定任意一颗卫星作为招标卫星,用来负责收集所有卫星的投标值,并选定最终中标卫星。所有卫星筛选自身计算所得的目标观测窗口,剔除不符合要求的窗口,对符合要求的窗口进行任务收益计算,并向招标卫星发送自身的任务收益值进行投标。在收到所有卫星的投标后,招标卫星排序接收到的任务投标,选取收益值最高的卫星作为中标卫星。在所有任务完成分配后,对所有任务的中标收益值进行排序,将收益较低的任务取消当前中标结果,并重新进行招投标流程,直到系统收益值稳定不再发生变动或达到迭代次数上限。

为方便问题求解,对问题做如下假设:1)星座内所有卫星存在稳定的星间通信链路,且可以忽略通信延迟;2)在整个任务期间,卫星不进行轨道机动。

1.2 问题描述

T={t1,t2,…,tNT}:表示任务集合;

S={s1,s2,…sNS}:表示卫星集合;

tij={lij,dij,cij}:表示任务相关信息。

其中:lij为卫星sj对任务ti进行观测的时间窗口开始前的等待时间;dij为卫星sj对任务ti进行观测的时间窗口的持续时间;cij是卫星是否参与任务投标的控制位。默认为1,表示卫星sj可以参与任务ti的投标,若该控制位为0,则不参与。

任务分配的原则是所有卫星执行任务的收益之和最大化,目标函数如下:

(1)

式中:tv为星座执行所有任务的收益值之和,xij表示任务ti是否被卫星sj执行的变量。当任务ti被卫星sj执行时,xij=1,否则xij=0;al为任务窗口开始前的等待时间的收益权重;ad为观测窗口质量的收益权重;ab为负载均衡系数。

任务约束条件如下:

(2)

xuj·xvj·(luj+duj-lvj)(lvj+dvj-luj)≤0,

u,v∈T,j∈S

(3)

其中:式(2)表示每个任务最多只由1颗卫星执行1次;式(3)表示任意1颗卫星执行2个不同任务时窗口不能互相重叠。

任务分配问题的特点是卫星数量与任务数增加后,解空间大小会大幅增加,采用传统方法进行求解时计算量过大,难以实现卫星在轨求解。同时,现有分布式卫星系统规模较小,任务分配时较少考虑到系统负载均衡性问题,在大规模星座中应用时,可能导致卫星负载不均衡,影响系统性能。针对上述问题,设计了一种考虑负载均衡的合同网目标分配算法。

2 加权负载均衡合同网任务分配

合同网算法用于分布式问题求解的高级通讯和控制协议,是分布式多智能体系统中采用最为广泛的控制结构[25]。合同网算法机制简单,不依赖个体间大量迭代交互,适用于解决大规模分布式问题。现有的卫星任务分配方法由于问题规模较小,较少考虑任务分配过程中导致的负载不均衡问题,在大规模星座的分配问题中可能导致星座中部分卫星任务过饱和。为了求解大规模星座任务分配问题,在分析问题特点的基础上,设计了添加负载均衡系数的合同网分配方法,采用窗口筛选策略减小问题的解空间,并在合同网算法中加入负载均衡系数,改进了传统算法在大规模星座和大规模任务情况下的分配效率和分配效果。

2.1 窗口筛选策略

相比现有的卫星星座,大规模星座卫星数量大幅提升,可用对地观测资源大幅增加,观测覆盖率也随着增加,因此大规模星座可以大幅减少等待目标观测窗口所需的时间。但资源的丰富导致任务分配问题的解空间增加,增加了求解所需的算力和时间。在使用合同网方法进行任务分配前,利用任务窗口延迟和任务窗口时长对可用窗口进行筛选,可以在保证任务分配效果的情况下,减少分配求解的计算量,提高系统任务分配的效率。

卫星sj对任务ti进行观测的时间窗口开始前的等待时间lij是对地观测任务分配的重要指标。受卫星携带推进剂的数量和轨道运动规律限制,卫星在执行绝大多数观测任务时,不会进行轨道机动。在完成任务规划后,需要等待卫星运行至可见观测窗口时进行观测。等待时间越长,卫星所获得的观测数据时效性越差。

在卫星观测窗口筛选过程中,设置阈值lt进行过滤。将lij过大的任务窗口的控制变量cij置0,剔除延迟时间较长的观测窗口,卫星将不会参与后续的收益计算与招投标程序,表示如下:

(4)

在进行筛选后,可以有效减少参与后续步骤的卫星数量,同时缩短卫星轨道递推和窗口计算需要前推的时长,节省星上计算资源和星间通信资源。

如图1所示,卫星在对地观测过程中相机可见范围为以当前时刻星下点为圆心的圆,随着卫星的移动,相机的可见范围为以星下点轨迹为中心线的条带状区域。因此,对于地面固定点目标,卫星可见目标的星下点范围是以目标为圆心的圆,卫星的星下点轨迹在目标附近可近似为圆的割线。由于卫星在圆轨道上匀速运行时星下点沿星下点轨迹匀速运动,由几何关系可知,当卫星星下点轨迹穿过目标时,卫星从目标正上方飞过,观测角度垂直于地面,观测清晰度最高,观测窗口持续时间最长,卫星所需要进行的姿态机动幅度最小,可视为最优观测窗口。因此,卫星对目标的观测窗口持续时间越长,窗口质量越好。

图1 卫星观测可见范围示意图

在卫星观测窗口筛选过程中,设置阈值dt进行过滤,剔除窗口持续时间较短的观测窗口:

(5)

采用阈值筛选方法可以在任务中根据实际需要灵活调整阈值lt和dt,以便适应系统运行过程中不同的需求。筛选可以有效减少参与后续步骤的卫星数量,同时保证任务快速响应和任务执行质量,减少卫星姿态调整角度,节省星上资源和星间通信资源。

2.2 加权负载均衡合同网任务分配

合同网算法适用于分布式多智能体任务分配问题,通过招标-投标-中标的市场机制实现任务分配,具有分布性、自主性[8]。加权负载均衡合同网任务分配方法在传统合同网的分配机制的投标基础上,加入负载均衡系数,在招投标过程中对中标有多个任务的卫星进行任务收益惩罚,倾向于将任务分配给目前中标任务数量较少的卫星,避免单个卫星中标任务数量过多,导致系统负载过于集中。相比传统合同网算法,可以在不增加系统迭代次数的情况下,改善分配结果的负载均衡性。使用加权负载均衡合同网分配算法进行自主任务分配,流程如图2所示:

图2 合同网任务分配流程图

分配过程主要分为以下3个步骤:

1) 在任务预处理过程中进行窗口计算和窗口筛选后,若某卫星对某任务拥有符合筛选条件的观测窗口,则计算卫星执行当前任务的收益值,得到的收益值作为投标值,参与该任务的投标。

在卫星观测收益评估过程中,采用负权重系数与任务窗口等待时间相乘,计入任务收益;采用正权重系数与任务窗口持续时间相乘,计入任务收益为:

(6)

此外,考虑到部分卫星可能在分配过程中被分配到过多任务,而部分卫星没有被分配到任务,导致系统中不同卫星任务负载不均衡,影响系统性能。在合同网算法的投标值计算过程中,加入负载均衡加权系数,对已经中标有任务的卫星,在进行新的任务投标值计算时,按照负载均衡系数进行收益惩罚,扣除部分收益值,减少卫星重复中标,收益计算方式为:

(7)

2) 在所有拥有符合要求的观测窗口的卫星执行投标后,各卫星对收到的每个任务的投标值分别进行排序,每个任务由投标值最高的卫星作为中标卫星。遍历所有的任务后,得到任务分配初始的结果。

3) 若满足迭代优化条件,将分配结果输入迭代优化模块,使用贪婪算法迭代优化分配结果。在每轮迭代优化过程中,对分配完成的任务重新进行带有负载均衡惩罚的收益计算,筛选收益值较低的任务,清除其分配结果,重新进行招投标过程,得到新的分配结果。判断是否满足迭代优化条件,若满足迭代优化条件,进入下一轮迭代;若不满足迭代优化条件,输出最终分配结果。

3 仿真实验与分析

3.1 实验参数

本节通过仿真实验验证所提方法。实验计算机配置为Intel(R) Core(TM) i7-10700 CPU @2.90 GHz。星座包括400颗低轨遥感卫星,轨道高度为350 km,轨道倾角为75°,400颗卫星分别部署在20个均匀分布的轨道面上,每个轨道面包含的20颗卫星均匀分布。卫星可以对以星地连线为中心,摆动30°以内的范围进行观测。在地表随机生成1000个固定点目标,如图3所示。在仿真中,分别选取100、200、300、400、500、600、700、800、900和1000个目标,使用本文所提方法与传统任务分配的经典方法混合整数规划算法、匈牙利算法进行对比,表1列举了仿真中的参数信息。

表1 仿真参数信息

3.2 实验结果与对比

针对10组测试算例,分别采用本文提出的方法、混合整数规划算法和匈牙利算法进行求解,分别比较任务收益、规划耗时和负载均衡效果,验证本文所提出方法的有效性与合理性。

从图4可以看出,由于对地观测资源较为充足,所有的任务都可以较快地得到卫星分配并达到较好的执行效果,因此3种算法的收益基本相当。本文提出的加权负载均衡合同网分配算法的分配结果在所有情况下都略优于混合整数规划算法,并且随着任务规模的增加,任务平均收益差距有扩大的趋势。

图4 任务平均收益对比

从图5可以看出,采用窗口筛选方式对任务进行预处理后,可以显著减少每个任务参与投标的卫星总数,有效减少在轨计算资源与通信资源消耗。

图5 窗口筛选前后参与投标卫星数对比

如图6所示,通过算法重复运行100次并求运行时间平均值可知,相比混合整数规划和匈牙利算法的集中计算求解方式,合同网算法采用分布式计算,可以充分利用分布在各个卫星上的计算资源,大幅度提高计算效率。加权负载均衡合同网算法比混合整数规划算法可以减少94%以上的运行时间,同时随着任务规模增大,差距有进一步扩大的趋势;比匈牙利算法可以减少99%以上的运行时间。

图6 任务观测分配消耗时间对比

如表2和图7所示,通过对比任务分配结果中中标任务数量最多的卫星和卫星执行任务数量的标准差,可以看出,2种集中式分配算法的分配结果基本相同。合同网算法通过卫星之间的信息交互与迭代优化,可以得到更均衡的分配方案。随着任务规模的进一步增加,加权负载均衡合同网算法与其他2种算法的差距有进一步扩大的趋势。

图7 卫星执行任务数量的标准差对比

4 结论

研究了大规模星座的任务分配问题。根据问题相关特点,提出了一种加权负载均衡合同网观测任务分配方法,设计了适用于大规模星座和大规模任务的任务收益评估与观测窗口筛选方法,并在多星合同网分配中考虑加权负载均衡。仿真表明,加权负载均衡合同网任务分配算法可以高效解决大规模星座的任务分配问题,任务收益与传统算法基本相当,并达到良好的负载均衡效果。