InSAR双星编队测绘卫星任务规划方法研究

李鹏宇, 崔家山, 孙 然

(1.上海电子信息职业技术学院 中德工程学院,上海 201411; 2.西安电子科技大学 空间科学与技术学院,陕西 西安 710126;3.上海理工大学 光电信息与计算机工程学院,上海 200093)

干涉合成孔径雷达(Interferometric Synthetic Aperture Radar,InSAR)对地测绘任务规划[1-3]是结合卫星编队和优化技术的一种对地观测任务应用,由于卫星编队技术载荷约束的复杂性,相应地对地观测任务约束也更加复杂,任务求解难度更高,因此为了使卫星使用效能达到最优,有必要研究InSAR编队任务规划建模和优化方法。评价卫星任务规划的优劣需要考虑目标及重要目标的覆盖率、任务规划总时间[4-6]等。由于编队卫星独特的工作特点,存在测绘基线和开关机等多种约束条件,卫星轨道为双星绕飞或者跟飞轨道模式,双星联合对地成像,所以雷达卫星对地面目标的测绘为一个个观测条带,任务规划就是从多种观测条带任务组合中选优的问题,即NP-hard问题[7-8]。

关于卫星任务规划算法研究方面,主要有整数规划模型、启发式算法和遗传优化算法等。国外的Deb等[9]建立整数规划模型,以最大化任务收益为优化目标,运用优先搜索和动态规划对卫星成像调度问题求解;Li等[10]研究了卫星对区域目标的测绘调度问题,建立了约束满足模型,比较了贪婪、整数规划和遗传算法,实验证明,虽然遗传算法性能较好,但对于大规模约束问题建模比较困难。Bianchessi等[11]提出了二进制整数模型,采用基于拉格朗日松弛和梯度的启发式算法[11]。以上研究是以单颗卫星最大化任务收益为优化目标,在双星编队能源利用平衡方面研究比较少,对遗传优化算法只是理论上的研究和证明,没有建立完备的关于双星编队任务的规划模型。

针对双星编队测绘任务的多目标多约束任务规划需求,提出了一种基于优先级的遗传优化算法,并建立模型仿真求解任务规划的最优解集。对编队测绘任务进行数据预处理,给出问题的形式化描述,分析各项约束条件,提出了满足双星编队任务规划的约束模型;以最小化测绘任务总时间和平衡双星资源调度为优化目标,提出了一种基于优先级的遗传优化算法,结合双星编队载荷特点求解问题,通过实验仿真验证算法有效性和可行性。

1 双星编队建模

由于卫星编队在重访周期轨道的空间运行,所有测绘任务同一时刻只能选择在特定雷达波位覆盖范围内进行,不可能对所有雷达波位范围的测绘任务进行成像。为了实现对卫星资源合理使用,需要对不同卫星、不同时段和不同波位测绘任务实施优化调度,选择合适的任务条带进行成像。图1为主从星相对运动轨迹,假设编队为绕飞构型,一个卫星为主星,另一个星为从星,两星之间的相对运动轨迹为椭圆,投影到XY轴轨迹为圆形。图2所示的是测绘模式为双星交替发射雷达波束、两星同时接收的工作方式。两星间距变化为几公里至十几公里,其垂直有效基线和沿航迹基线需要满足测绘需求[12-14]。

图1 主从星相对运动轨迹

图2 双星绕飞编队InSAR测绘

假定设计双星编队的雷达载荷约束描述如表1所示。

表1 卫星任务规划约束

规划元任务定义为不可分割的最小卫星测绘条带,图3所示的条带1、条带2分别可以作为2个不同的规划元任务。其中越南北部区域的条带分割图,由于卫星工作的特点,每次卫星航过越南北部区域的时候只有一个条带可以被选中执行,因此如何选取合适的条带组合,就是一个典型凸优化问题[15-17],优化目标为选取最少的条带,卫星使用的资源最少即用最少卫星圈次进行测绘,同时能够完成区域的最大化覆盖。这个优化问题既要考虑单颗卫星平台的载荷约束条件,还要考虑如何调配组合双星开关机策略,从而达到卫星的资源使用最优,同时达到任务收益最大化。

图3 不同的规划任务条带组成卫星任务最小单元

2 任务规划问题建模

在多目标多约束优化问题中,各目标通常相互冲突且不可同时兼顾,对其中的某一个目标进行优化就必须以牺牲其他目标作为代价,各目标约束条件的单位又往往不一致,因此很难客观地评价多目标问题解的优劣性。与单目标优化问题相比,多目标优化问题的解并不是唯一的,而是存在一个最优解集合,集合中元素称为 Pareto 最优或非劣最优。其中最优解往往有无穷多个,如何在最优解集合中求出一组分布均匀且数量充足的候选解供给决策者进行选择就显得十分重要。经典的方法很好地解决了部分单目标优化问题,然而现实世界中的许多优化问题都涉及多个目标的优化,而且这些目标并不是独立存在的,它们往往是耦合在一起且处于相互竞争的状态,它们的竞争和复杂度使优化变得十分困难[18-19]。一般地,多目标优化问题可以用函数f来定义,该函数把决策向量X映射到目标向量Y,可得:

(1)

式中:X=(x1,x2,…,xm)由m个决策变量xi构成;Y为n个须同时优化的目标fi(X)构成;约束g(X)为r个等式和不等式构成。制定InSAR编队卫星优化目标准则主要包含以下几个方面。

① 双星总计目标元任务数量最大。

② 双星总计成像重点目标元任务数量最大。

③ 双星总计需要规划圈次最小。

④ 单圈总时长满足小于等于TD_SS。

⑤ 单次成像时长小于等于MD_SI。

⑥ 双星开关机最小间隔大于等于MITI。

⑦ 单轨双星最大成像次数小于等于SC_SS。

其中,在互相冲突的情况下第②目标要高于第①目标,双星编队测绘任务规划设计的数学模型为

(2)

式中:i为卫星工作圈号;j为单圈内成像序号;m为圈号i内总计成像次数;n为指定时间范围内卫星工作的总计圈次;TN为元任务时长;IN为重点区域元任务时长;countof(circle)为本次优化卫星工作的总圈次。

3 规划算法设计

3.1 算法设计流程

多目标遗传算法主要步骤包括参数编码、设定初始种群、设置适应值函数、复制、选择、交叉、变异操作以及问题解码,具有全局优化、鲁棒性好、搜索效率高和本质并行性等特点。本研究运用基于优先级的遗传算法解决多目标优化问题,首先,根据轨道动力学理论计算卫星雷达载荷对地覆盖的条带区域;然后,对不同重点区域设置不同优先级别,通过多目标遗传算法生成基因和染色体,并根据条带优先级进行变异优化以求取最优解;最后,根据其他约束生成卫星成像任务调度计划。任务规划基于优先级的遗传算法如图4所示。

图4 任务规划基于优先级的遗传算法

3.2 规划算法详细设计

3.2.1 编码

卫星元任务定义为相同雷达波位覆盖的一段卫星测绘条带,图3中越南部分区域是被卫星测绘条带覆盖的。如图5所示,可以把每个元任务作为一个基础的规划单元,也即一个基因,多个基因组合为一个单圈次规划的染色体,其中,黄色基因为重点测绘区域的元任务,每个染色体包含重点区域元任务的数量决定当前染色体的优先级,优先级越高的染色体被选择的概率越高。

图5 染色体编码设计

图6 交叉优先级流程

染色体定义为具有相同轨道圈次编号的卫星任务基因的组合,也即一个轨道圈次内满足载荷约束要求的卫星任务基因组合。卫星任务规划时间与任务基因数量、染色体数量成正比,因此,合理规划卫星任务基因数量以及合理规划各个染色体执行顺序可以提高卫星任务执行效能。

基因属性描述如表2所示。

表2 基因属性描述

染色体属性描述如表3所示。

表3 染色体属性描述

3.2.2 初始染色体生成

对步骤1产生的基因数组按照优先级由高到低排序,生成第1个优先级数组level_list。基因优先级计算式为

GeneLevel=import_weight×ITN+time_weight×TTN+base_weight×BASE_N

(3)

式中:import_weight为重点区域任务时长权值;ITN为重点区域任务总时长;time_weight为基因内任务总时长权值;TTN为基因任务总时长;base_weight为基因内基线的权值;BASE_N为基因的基线的满足度。基于level_list优先级数组,生成其他9个newlevel_list,共计10个优先级数据,详细算法如下。

Input:level_list //初始基因优先级数组N//优先级个数output: newlevel_list //基因优先级数组1.for i=1 to 10 do2.for j=1 to 5 do3.k=random(ticks)//生成随机数k4.m=random(ticks)//生成随机数m5.newlevel=swap(level_listk,level_listm)//交换序号为k,m基因的优先级6.end for7.newlevel_listi=newlevel//生成一个新的优先级数组8.end for9.return newlevel_list//返回基因优先级数组

在生成newlevel_list优先级数组后,按照每组优先级排列生成对应初始染色体。详细算法如下。

Input:level_list //基因优先级数组N//优先级个数output: chrom_list//返回染色体数组1.for i=1 to N do2.Sort(level_listi)//所有基因优先级排序3.gene1=level_listi0//选取最高优先级的基因为第1个选择的元任务4.chrom_listi.Add(gene1)//第1个基因加入到染色体i中5.While(TT_N

3.2.3 交叉

交叉是把初始优先级染色体数组chrom_list中随机选择2个染色体的优先级数组,采用部分一致交叉算法(PMX),交换2个优先级数组中的部分片段,生成2个新的优先级数组,然后根据新生成的优先级数据采用类似于第3.2.2节的方法生成新的染色体数组chromlist_intersect。具体步骤如下。

① 随机选择优先级片段;

② 交换优先级片段;

③ 子代优先级合法化;

④ 子代染色体生成。

交叉优先级流程如图5所示。

3.2.4 变异

变异步骤首先在优先级数组矩阵level_list中随机选择1个染色体的优先级数组,随机生成2个位置v1和v2,并交换优先级数组的位置v1和v2的优先级数值,如此重复2次,获得2个子代染色体的优先级数组,并采用类似于第3.2.2节的方法生成染色体数组。

3.2.5 适值计算

合并第3.2.2节～第3.2.4节中生成的染色体数组,并计算各自的适值。计算方法为

evaluate=timval×timweight+importval×importweight

(4)

式中:evaluate为对应染色体数组的适应值;timval为染色体任务总计规划时长;timweight为总计规划时长的权值;importval为重点区域染色体任务的时长;importweight为重点区域染色体任务时长权值。经过仿真实验m_timweight为0.7,m_importweight为0.3效果最好。

3.2.6 选择(轮盘赌算法)

从父代染色体和子代染色体中根据适应值大小排序,最多可以取得8个新一代染色体。新一代染色体数目和波位数量一致,这样优化更合理。具体方法如下:首先,计算各染色体的选择概率pk和累计概率qk为

(5)

式中:evaluatek为第k个染色体的适应值;第k个染色体的累计概率为第1个染色体的选择概率到第k个染色体的选择概率之和。这样就得到k个染色体的累计概率数组,然后随机生成[0,1]之间的随机数rk,选择符合条件qi-1

3.2.7 优化结果输出

重复第3.2.3节～第3.2.6节的步骤各100次,选择适应值最高的染色体为结果输出,即为单圈次卫星任务的规划输出结果。

4 仿真分析

对中国陆地区域内范围包括大陆、台湾和海南岛等相关岛屿进行无差别的InSAR卫星任务规划,通过对比贪婪式优化算法和基于优先级的遗传优化算法的规划效率来验证不同优化算法之间的差异。设计任务规划约束条件,如表4所示。设置单轨最大成像时长为240 s,单轨双星最大成像4次,垂直有效基线范围200～800 m,沿航迹基线最大值600 m,单次最大成像时间为200 s。

表4 仿真约束条件

如果对中国陆地区域包括周边岛屿的范围内进行无缝隙的条带覆盖,采用基于优先级的遗传优化算法,设置AB星的各自波位数量为12个,总计条带24个,经过规划计算,相邻开机时间、单轨开机总时长、开机次数都在约束范围内,满足仿真预设条件,如图7所示。

图7 约束情况检查

本研究对比了2种优化算法的覆盖效能。采用基于优先级的遗传优化算法的面积覆盖率,如图8所示。从图8可以看出,总计规划时间为266 d,面积覆盖率为99.013%。采用基于贪婪优化算法的面积覆盖率,如图9所示。从图9可以看出,总计规划时间为399 d,面积覆盖率为99.013%。采用贪婪优化算法比采用基于优先级的遗传优化多花费133 d,从曲线图分析可知,在覆盖率不足80%时两种算法的效率差别不大,而剩下20%面积覆盖的时间中两种算法相差很大,这是因为在卫星任务充足情况下对任务选取的效能是没有大的差别的,而在任务不充足的情况下,遗传优化算法优先选取高优先级别侯选解的优势就体现出来了,通过遗传优化算法可以对单圈次内的任务的筛选更合理,相比贪婪算法对任务调度重访周期更短。

图8 基于优先级遗传优化算法规划效能分析

图9 贪婪优化算法规划效能分析

5 结束语

详细介绍了InSAR双星编队任务规划方法,充分分析了双星编队规划、卫星工作方式和负载约束的特点,设计了一种基于优先级的卫星任务遗传优化算法,给出了基因和染色体在卫星任务规划中的具体实现方法,并对优化算法进行了仿真。与贪婪算法仿真结果对比表明,基于优先级的遗传算法适用于InSAR双星编队任务规划优化,本研究采用的算法模型为双星编队和多星星座等卫星资源调度决策支持系统的设计提供了有效的参考。