遥感卫星组网观测资源调度中的数学建模与优化问题

刘永信, 王玲琳, 张 晖, 王朝霞, 杨 治

(1.内蒙古大学 电子信息工程学院,内蒙古 呼和浩特 010021;2.内蒙古师范大学 应用数学中心,内蒙古 呼和浩特 010022)

将多颗遥感卫星组网可实现对地球表面特定区域的任意时段、全天候、多要素连续监测,可以满足应对突发应急事件监测的需要。遥感卫星组网观测可以利用现有的卫星资源,结合不同轨道卫星的优化部署和小卫星快速发射补网等手段实现。卫星组网观测通过分析常规或应急观测任务需求,优化设计资源分配调度模型和实现算法,可为感兴趣区域的连续观测提供技术支持。遥感卫星组网观测的技术路线如图1所示。对于常规观测任务,根据现有卫星资源构建常规分配调度模型,设计算法进行优化求解; 针对突发应急事件,以观测任务对模式手段、时空分辨率等的具体技术指标为依据,设计卫星资源应急分配模型和算法,从空间系统的鲁棒性出发,优化在轨卫星和载荷的分配调度策略,优先满足应急任务的要求; 如果卫星和载荷数无法达到任务要求,视情启动卫星轨道优化部署机制或发射待命小卫星重新构建网络,通过多颗卫星组网协同观测,实现对目标任务的快速应急响应。

图1 遥感卫星组网观测的技术路线Fig.1 The technology roadmaping of remote sensing satellite network observation

如何实现快速准确高效的遥感卫星资源组织,最大限度利用卫星资源、扩大观测范围是目前遥感卫星组网观测的难点。构建资源分配调度数学模型,设计问题的优化求解、分配调度策略是解决该类问题的关键。本文建立了遥感卫星组网观测资源调度需解决的资源调度数学建模,并讨论了模型优化求解的相关数学问题。

1 常规观测任务的数学建模

针对遥感卫星组网的常规观测,国内外专家发展了多种数学模型。法国Gabrel等[1]基于图论思想构建了卫星调度问题的加权有向无环图模型,利用有向无环图的成像路径表示卫星在多个任务间转换方式,采用最短路径算法对问题进行求解。该模型具有简单直观的优势,不足之处在于未考虑载荷开关机时间约束对有向图拓扑结构的影响。法国国家空间研究中心Lematre[2]提出卫星观测地球任务指的是根据客户观测需求获取地球表面特定图像,并且把敏捷卫星观测地球问题(AEOS)简化为地球轨道选择和卫星资源调度问题,根据任务请求的权重、决策变量、可视性以及角度约束建立最大质量准测模型,利用动态规划算法求解,可以在短时间内获得良好的解决方案。

美国加利福尼亚州宇航局艾姆斯研究中心Frank[3]在多颗卫星调度问题中考虑任务优先级、观测时间窗以及卫星星上存储等约束条件,提出了一种基于约束描述模型,鉴于问题复杂度较高,设计启发式随机搜索算法来解决该问题,并且开发了EUROPA调度系统。2003年5月美国分析成像公司(AGI)推出一款卫星调度软件STK/Scheduler,该软件模块基本集成了卫星观测和数传过程中的约束,不仅给出了Neural Network、Random等求解算法,并且具备用户编写算法的功能接口,以消除约束的方式获取任务最大完成度并且给出分配方案甘特图。

贺仁杰[4]针对成像卫星调度问题建立了混合整数规划模型和约束满足模型,使用禁忌搜索算法和Solver求解器结合的方式来求解模型,得到令人满意的结果。韩传奇[5]针对卫星组网调度问题建立最长观测时间简单规划模型和复杂规划函数,在模型中考虑了用户观测时间约束,卫星时间窗口约束以及卫星存储约束,简单目标函数下的卫星整数规划模型分别使用遗传算法和贪心算法进行求解,讨论了两种算法在不同任务规模场景下对求解质量和速度方面的适用性。针对复杂目标函数下的规划模型,使用模拟退火算法改进后的遗传算法对其求解,提高了求解效率并且优化了解的质量。蔡德荣[6]根据卫星是否观测任务(决策变量)和任务收益建立最大任务优先级调度模型,模型中考虑的约束比较全面,不仅包括卫星观测动作约束,而且考虑了卫星星载存储器上限约束、数据下传动作等约束条件。针对模型和车辆路线问题求解的相似性,使用蚁群算法求解模型。王凌峰[7]为实现对热点目标区域持续性观测和周期性获取目标态势需求,根据卫星观测任务开始观测和结束观测时间窗口、任务优先级以及调度周期建立了最小超时程度目标函数,模型中考虑了卫星两次开机最短间隔约束、单次开机约束、单圈最长开机时间约束以及单天最大开机次数约束。使用贪心搜索算法求解模型,给出了算法的具体求解思路。实验结果表明,贪婪搜索算法能够有效求解卫星组网周期性持续观测任务问题。

卫星调度模型方面主要有图模型、背包问题模型、整数规划模型以及约束满足模型。其中图模型利用有向无环图观测任务路径表示卫星在多个任务间的转换方式,采用最短路径算法求解模型,不足之处在于有向无环图本身条件限制无法加入太多约束条件,因此无法准确描述卫星调度问题。背包问题模型表示卫星调度问题时具有形式简单等优点[8],可以使用水平约束对多个维度的卫星资源进行约束,其主要缺点是无法表示一些复杂实际约束条件。整数规划模型可以描述卫星调度问题中的线性约束条件,但是整数规划问题求解较难,问题规模增大时,需要设计有效的分支定界策略提高求解效率。此时通常借助一些复杂问题分解方法,比如使用列生成算法找到问题最优解的紧凑上界对寻优化过程进行指导,主要缺点为无法处理一些复杂的非线性约束条件。约束满足模型可以描述非线性约束条件和非线性目标,主要描述若干目标必须满足多个约束条件,该模型能够简单直观表示变量和约束,可选择成熟的约束规划软件工具对该问题进行求解。虽然模型有较强的描述能力,但模型求解时需要考虑约束传播,通用约束传播算法由于缺乏有效分支定界策略导致求解效率较低。

2 突发应急事件观测任务的数学建模

2.1 卫星轨道优化观测的数学建模

遥感卫星组网在实现对地球表面全天时多方位常态化观测的同时还要满足重点地区的特殊观测。在应对突发应急事件时,需要第一时间获取事发地点的实时状态,这对遥感卫星轨道重构和优化部署的计算时间要求很高。针对重点地区的突发应急事件,主要由事件发生的时间、地点、事件类型等因素来决定何种传感器可获取所需数据,从而确定哪些卫星可执行该任务。在此过程中,可能出现现有卫星无法监测到的情况,对于这种状况就要考虑卫星轨道重构的方法。

在遥感卫星轨道重构方面,主要由卫星轨道高度以及所使用传感器工作方式决定,以星载合成孔径雷达为例[9-10],低轨道遥感卫星由于轨道高度低,入射角和斜视角受到约束大则波束的有效覆盖范围较小,与高轨道卫星相比,探测范围受到极大的影响。理想状态下,卫星轨道主要由开普勒定律的6个轨道参数所决定,但在实际运行过程中还会受到各种摄动力和地球扁平所影响,对于卫星轨道的重构也必须考虑卫星的运行状态。在轨道预测方面,主要采用SGP4模型对卫星轨迹进行预测[11-12],模型主要表现为除去计算六根数,还需考虑地球非球形引力、大气阻力、月球引力和太阳潮汐等多种摄动力对卫星运行的影响,该模型可较为准确地对卫星轨道进行计算。此外,遥感卫星所携带的传感器观测覆盖范围也是必须要考虑的因素之一。孟少飞[13]提出了一种基于二维图理论的模型可快速解决卫星覆盖统计问题,先通过卫星与观测点的几何关系,建立二维图的解析数学模型,再对照传感器覆盖范围模型计算其覆盖性能,从而减少计算量,并建立对于整个任务的执行性能评估体系,二维图理论在针对覆盖性能的卫星轨道评估中得到广泛应用[14]。在对遥感卫星的轨道进行重构后,针对卫星运行速度及轨道避障规划等性能还可进一步优化。

在轨道优化方面,主要分为两种模式,一种是针对具体卫星运动模型,从模型中各参数着手,进行参数修正以达到运动轨迹最优的效果[15]。此类方法主要应用于特殊卫星和飞船,不具有普适性,且依赖于运动模型,需进行精确建模,适用小卫星和飞船,计算精度高,速度较快。但缺点也很明显,对于大多数卫星来说,运动模型无法做到精确的建模,因此方法的准确性降低。第二种是运用神经网络优化各个参数,从而达到校正卫星运动轨道误差的目的,这种方法针对一些不确定性的规律现象十分适用,因此也得到了更为广泛的应用。遗传算法以及通过遗传算法优化的神经网络方法效果比较明显[16-19],通过迭代优化的算法优化各个参数,将其代入轨道模型中,以达到修正轨道的目的,但相比上一种模式,这类优化过程通常需要大量计算,以及一定量的数据积累,因此计算速度较慢,对于一些对实时性要求比较严格的对象来说,该方法不太适用。两类优化模式各有优缺点,需从实际需求出发选择适合的方法。

2.2 发射快速响应小卫星补网模式的数学建模

发射快速响应(以下简称“快响”)小卫星补网模式是指,当现有卫星观测网络中的资源不能满足观测任务要求,且观测任务持续周期相对较长,不便或不能通过在轨卫星优化部署的方式完成观测任务时,采用发射提前储备的小卫星,通过快速部署卫星网络资源,以满足观测任务需要的卫星组网应急观测资源分配调度方式。基于军事、应急救援等应用的需要,国内外已对发射快响卫星以满足监测任务的方法进行了一定的研究。David等[20]提出发射快响卫星的理念,并从体系结构的角度进行了阐述。Wertz等[21]针对重点地区观测的需要,提出如何根据需求设计快响卫星的发射方式。陈盈果等[22]以快响卫星为对象,研究面向任务的快响系统卫星部署优化问题及求解方法。高璐等[23]探讨了快响卫星的轨道设计问题。

发射快响小卫星补网的本质是一个轨道设计与资源预估问题,应用此模式时需要重点解决两个方面的关键内容：如何根据需要合理选择小卫星在空间运行时的轨道及参数; 对于多目标多任务的需求,如何确定该卫星应该携带的传感设备及技术参数。解决问题的核心方法就是建模及求解,下面围绕以上两方面内容中涉及的数学问题进行探讨。

卫星的轨道形状和在轨道中位置通常采用星轨道六根数确定。其中,轨道半长轴和偏心率决定卫星轨道的大小和形状,轨道倾角和升交点赤经决定卫星轨道在空间中的平面方位,近地点幅角决定卫星相对于近地点的方向。对于快响小卫星轨道的选择,需要考虑其传感器覆盖范围、应急能力、分辨率、发射成本等问题,如何在满足观测任务的要求下,设计合理的卫星轨道或给出几种卫星轨道的设计方案是数学建模时需要重点考虑的问题。

对于分辨率要求较高的观测地域,要限制轨道高度,最好采用低轨轨道; 而对于覆盖能力要求较高,分辨率要求相对较低的任务,则可考虑采用中高轨道; 对于响应时间较短的应急任务,应选择倾斜轨道,根据观测目标的分布特性确定倾角大小,确保能够全覆盖; 对观测频率有严格要求,或者要求连续观测不间断的任务,设计轨道时必须严格遵循回归条件,能够与现有卫星资源在观测时间上实现无缝对接。

卫星对地观测,最终要依靠SAR、可见光相机、多光谱扫描仪、波谱仪、散射计、高度计、盐度计等星载传感器来实现,卫星对具体目标的具体空间和时间覆盖属性也是基于传感器实现的。针对观测任务的需要,如何计算出快响小卫星需要携带的具体传感器及传感器完成观测任务应具备的技术参数也是数学建模及求解需要重点考虑的问题。

如果观测任务需要成像,需要根据成像要求选择使用SAR、可见光相机或红外成像仪等传感设备,并根据分辨率等细节要求计算设备的技术参数; 对单次观测的持续时间有明确要求的任务,选取卫星传感器的波束大小及最小覆盖范围需要准确计算; 对于观测有优先级的任务,建模及计算传感设备技术参数时,首先要满足高优先级的任务; 对于需持续观测的循环性任务,要结合观测频率(或重访周期)考虑重复完成观测任务所需的传感设备数量; 基于任务的最大完成率,确定发射小卫星的数量及不同小卫星需要携带的不同传感器数量。

除以上建模及优化求解时需要考虑的问题外,实际发射快响小卫星时,还需要考虑如下问题：卫星及传感器运行时的能量限制,如传感器最大开机时间; 卫星自身的信息存储能力、卫星之间以及卫星与地面站之间的信息传输能力; 观测目标的建模问题,如点、面等; 卫星的工作寿命及发射成本; 发射及运行过程中的外部因素干扰,如电离层、云层等大气条件。为使有限的卫星资源能够被最大限度地利用,以满足应急情况下的观测需要,同时兼顾常态化观测任务,需要在合理的假设条件下,建立一个包含未知需求解因素的多类卫星资源多复杂观测任务的数学模型,并进行实时优化求解,得到发射快响小卫星的数量、轨道参数及所携带传感器的数量及技术参数,设计出能够取得最大调度收益的资源分配调度方案,在较短时间内取得符合客户需求的结果。而且,数学模型越接近实际、实用性越强,则要求建模时考虑的问题越复杂、越精准,模型的参数、约束条件越多、相互关系越复杂,则建模和优化求解的难度越大。

为解决这类问题,国内外学者大多构建多目标优化模型,先后提出了多目标进化、多目标差分进化等算法寻求优化解的方案。也有学者提出将快速发射小卫星轨道机动模型的机动过程描述为Lambert轨道转移问题[22],进而基于决策者参与的多目标差分进化算法进行求解。然而,在现有的发射快响小卫星补网乃至常态化多任务多目标卫星资源组网观测数学建模过程中,大多假设观测目标可近似为点目标,一颗卫星只携带一个传感器,忽略了区域覆盖与点覆盖的差别,将卫星协同与传感器协调近似等同,也忽略了能量、成本、寿命、外界条件等因素的限制[20-25],构建出的数学模型相对较为理想化,与实际应用相差较远,这正是需要重点改进的方向。

3 遥感卫星组网观测资源调度的优化求解问题

面对常规和应急观测需求,建立不同的遥感卫星组网模型,需要设计相应的算法进行求解,主要用到的算法包括智能优化算法、贪婪算法、动态规划算法以及树搜索算法。

智能优化算法在卫星调度问题中应用广泛,它是一种迭代改进的非精确搜索算法,求解结果的最优性往往取决于耗费的时间长度,并且该算法可在任何迭代的过程返回一个可行解[26],设计时需要一定技巧,为了获取更好的实验结果需要对算法的某些参数进行多次实验。智能优化算法没有固定形式,在资源分配、调度等领域应用性较强,典型的智能优化算法有遗传算法、粒子群算法、模拟退火算法以及蚁群算法等。

贪婪算法按照提前设计好的启发式规则对可行解进行逐步构造,在整个计算过程中不需要迭代。主要缺点为不能保证最终求解结果最优性,不能给出可行解和最优解之间差异[27]。当其它算法在有限时间内无法求出最优解时,可以选择贪婪算法对可行解逐步构造。在卫星调度问题中,设计合理的贪婪启发式规则是求解关键因素,一般启发式规则设计方式有两种: 第一种按照卫星与任务之间可见时间窗口的先后顺序对任务进行逐个安排; 第二种按照任务优先级的高低顺序对规划任务进行逐个安排。可以在算法搜索过程中引入随机机制对贪婪算法进行改进。

动态规划算法主要将卫星调度问题分解为若干个子问题进行求解,动态规划算法通常按照卫星星下点轨迹与地面目标的地理位置关系确定观测任务的执行顺序[2],主要从卫星调度时间、星载存储容量、卫星载荷能力等方面对问题进行求解,该问题的求解时间较长,可通过在每一步保存最优解的方式降低时间复杂度。该算法缺陷在于当待规划任务具有多个卫星观测时间窗口时,即任务分配的时间窗口有多个,则不能很好确定全局最优解。

树搜索算法分为深度优先搜索和最佳优先搜索两种,深度优先搜索可以较快生成初始解,并且算法占用的内存空间较小,可以从多个点出发搜索,该算法对初始搜索节点的选择依赖性较强,导致解的性能不够理想[28]。最佳优先搜索是广度搜索算法的改进,使用启发函数对将要遍历的点进行估价,并且以最小代价为准则,直到遍历完成所有的点。该算法解的性能较优,需要存储空间较大,生成解的时间较长。

4 结语

卫星组网调度问题主要包括建立卫星调度模型和设计相应算法求解模型两部分内容。在遥感卫星组网观测建模过程中还有许多问题有待解决,如何准确建立卫星覆盖的资源模型仍是最主要的议题,理论与实际干扰因素相结合的精确建模目前还没有出现,是未来急需解决的问题。除此之外,如何处理传感器工作模式与卫星运动状态的关系也十分重要,这关系着是否可以最大程度利用传感器获取有效信息,希望可以从数学关系中找到对应的解决办法,以达到最高的利用率和最大的观测范围。