基于LGN-VNS的多卫星区域目标覆盖算法

伍 艺，余晓刚，夏 维

(1.合肥工业大学 管理学院，安徽 合肥 230009；2.北京市遥感信息研究所，北京 100192；3.过程优化与智能决策教育部重点实验室，安徽 合肥 230009；4.智能互联系统安徽省实验室，安徽 合肥 230009)

0 引言

使用卫星进行大面积区域目标观测是现代卫星的常见应用形式之一，随着城市规划和建设、大规模海洋搜索、区域搜救和农林变化监测等应用场景的增加被逐渐广泛应用于各种领域[1-4]。一般来说，大多数应用场景中的覆盖需求有时间限制，对区域目标的覆盖往往很难由一颗卫星单独完成。在这种情况下，必须对多颗卫星进行协同规划以提供区域覆盖方案[5]。

多卫星区域目标覆盖(Multi-satellite Regional Target Coverage，MSRTC)问题是一个与计算几何高度耦合的NP-Hard卫星资源调度问题[6]。解决MSRTC问题需要根据目标区域信息和卫星的参数来规划卫星在运行到达目标区域上空时的覆盖姿态、单次覆盖的起始时间以及结束时间。每颗卫星的单次覆盖范围是一个覆盖部分目标的条带状区域，多星协同覆盖的结果由单次覆盖结果组合而成。MSRTC作为一个与计算几何高度耦合的问题，需要进行离散化处理。在对单个卫星的覆盖问题的研究中，Walton[7]将目标区域划分为几个紧密排列的平行条带。但由于不同卫星的运行轨道不平行，该方法仅适用于单颗卫星覆盖问题，不适合多颗卫星覆盖。在对多卫星区域覆盖问题的处理中，网格离散化方法是目前区域处理的常用手段[8]，Zhu等[9]甚至提出了基于网格的条带构造方法。然而，网格离散法在实际使用中很难直接确定最佳网格粒度，在大多数应用中是凭借经验确定网格粒度的[10-11]。值得注意的是，Hu等[12]提出了一种父子网格结构，在父子网格结构中，大粒度的父网格可以经过划分得到粒度较小的子网格。基于这些研究，本文拓展了父子网格结构，提出了一种局部划分的网格嵌套(Local Grid Nesting，LGN)策略，有效降低冗余计算。

对于解决MSRTC问题中覆盖方案的优化方法，已有不少学者进行了相关研究。贺仁杰[13]建立了2种调度模型，并设计了禁忌搜索和列生成2种算法。Wu等[14]将问题划归为生成任务集和任务规划2个阶段，提出了融合蚁群算法和局部搜索算法的方法。孙凯等[15]采取了学习型遗传算法来解决该问题。尽管已有很多元启发式方法被用于解决MSRTC问题，但该问题的NP-Hard特性及复杂性决定了对适用算法的研究仍有很大的发展空间。

变邻域搜索(Variable Neighborhood Search，VNS)算法是一种局部搜索的启发式算法。基于一个邻域结构的局部最优解不一定是另一个邻域结构的局部最优解的认知，VNS的特点在于邻域的设计和变换规则。VNS通过多个不同的邻域动作生成不同规模的邻域，然后在多种邻域内交替搜索从而交替实现搜索到当前解的局部范围内的最优解和跳出局部最优解。李志亮等[16]将离散差分进化(Discrete Differential Evolution，DDE)与VNS算法相结合，提出了一种用于敏捷卫星任务调度的算法。本文所提出的LGN策略能够逐步细化对局部区域的离散，从而扩展备选条带集合，为VNS构造新的搜索邻域提供更大的变换空间。结合LGN策略，VNS的局部搜索特性能够随着搜索范围的扩展发挥出更大的效用。

本文提出了LGN策略，能够对卫星覆盖问题中的区域目标进行局部的离散，并结合VNS算法框架，设计了解决MSRTC问题的基于局部嵌套的变邻域搜索(Variable Neighborhood Search Algorithm Based on Local Grid Nesting，LGN-VNS)算法，提供了解决MSRTC问题的有效算法。

1 问题描述与建模

1.1 MSRTC问题描述

在描述MSRTC问题之前，需要介绍一些相关概念。地面轨道为从卫星运行轨道到地球中心的直线与地球表面相交形成的曲线；覆盖时间窗为卫星飞越或接近目标区域并能有效进行目标覆盖的时间段，一个覆盖时间窗的起止时间点分别被称为最早覆盖开始时间和最晚覆盖结束时间；侧摆角为卫星在垂直于其轨道的平面上具有一定的侧摆范围，最大侧摆角表示卫星向一侧摆动到极限位置的角度；视场角为卫星所携带的覆盖传感器的固定覆盖角度，由传感器配置决定，与卫星的侧摆角度无关；最大覆盖区域为在机会的最早覆盖开始时间和最晚覆盖结束时间内，当卫星在2个方向上摆动到最大侧摆角时，卫星可以覆盖到的最大地面范围；条带为卫星进行一次扫描的覆盖范围，可表示为一个条带，由可见区域平面上的一个矩形表示。由于卫星可以在侧摆的姿态下进行覆盖，因此条带的位置可能被相应的地面轨道穿过中心，也可能不与之相交，但始终与相应的地面轨道平行。一个条带的长度取决于覆盖的开始和结束时间，宽度则由视场角、侧摆角和卫星高度共同决定。MSRTC问题的示意如图1所示。

图1 MSRTC问题示意Fig.1 MSRTC problem diagram

MSRTC问题的解由多个条带构成的覆盖方案构成。给出方案的过程就是确定各个卫星到达每个覆盖时间窗的覆盖侧摆角度，以及覆盖的开始和结束时间。在本文中，MSRTC问题的目标是利用相对不足的卫星资源来尽可能地充分覆盖目标区域。因此，本文以目标区域的有效覆盖率最大为优化目标。有效覆盖率是所有条带的并集位于目标区域内的面积与目标区域面积的比值。下文将针对该目标进行算法设计。

1.2 问题假设与转化

在实际应用中，卫星在执行覆盖任务时会受到存储容量、能量供应、姿态调整和数据传输等多种因素的限制，本文进行一些假设来简化问题：

假设1：虽然卫星地面轨道是弯曲的，但它们可以在较短的覆盖时间内近似为切向直线。这些近似的直线称为地面轨道投影直线。

假设2：将一个覆盖时间窗看作一个机会。每个机会都有其对应的地面轨道投影直线、最早覆盖开始时间和最晚覆盖结束时间。

任何条带的覆盖开始时间、结束时间和侧摆角度须满足以下限制条件：

① 覆盖开始时间和结束时间必须位于最早覆盖开始时间和最晚覆盖结束时间之内；

② 覆盖开始时间和结束时间的间隔不能超过卫星的最长连续覆盖时间；

③ 覆盖侧摆角不能超过卫星的最大侧摆角。

于是，对于同一个机会，不同的开始时间、结束时间和侧摆角度的组合可以形成多个不同覆盖范围的备选条带。来自同一个机会的一组条带簇称为备选条带集合。同一个备选条带集合中的条带之间存在互斥关系：一旦确定一个条带，将占用相应的机会，同一机会的其他备选条带将无法被选择。

基于以上假设和简化，MSRTC问题可以转化为：根据目标区域信息及卫星参数，为所提供的卫星覆盖机会构造备选条带集合，并从每个机会的备选条带集合中各选择一个条带，最终形成覆盖方案。

1.3 问题建模

MSRTC问题建模涉及的符号及含义如表1所示。

表1 相关符号定义Tab.1 Definition of related symbols

决策变量：

目标函数：

∀i∈{1,2,…,|F|},∀j∈{1,2,…,|Ci|},

∀k∈{1,2,…,|Sij|}。

(1)

约束条件：

btijk≥Bij，

∀i∈{1,2,…,|F|},∀j∈{1,2,…,|Ci|},

∀k∈{1,2,…,|Sij|}，

(2)

etijk≤Eij，

∀i∈{1,2,…,|F|},∀j∈{1,2,…,|Ci|},

∀k∈{1,2,…,|Sij|}，

(3)

0≤etijk-btijk≤Tij，

∀i∈{1,2,…,|F|},∀j∈{1,2,…,|Ci|},

∀k∈{1,2,…,|Sij|}，

(4)

lijk‖lij，

∀i∈{1,2,…,|F|},∀j∈{1,2,…,|Ci|},

∀k∈{1,2,…,|Sij|}，

(5)

|ωijk|≤|Wij|，

∀i∈{1,2,…,|F|},∀j∈{1,2,…,|Ci|},

∀k∈{1,2,…,|Sij|}，

(6)

∀i∈{1,2,…,|F|},∀j∈{1,2,…,|Ci|},

∀k∈{1,2,…,|Sij|}。

(7)

式(1)表示目标函数为每个选定条带覆盖区域的最大并集；式(2)表示覆盖条带的开始时间不得早于最早覆盖开始时间Bij；式(3)表示覆盖条带的结束时间不得晚于最晚覆盖结束时间Eij；式(4)表示覆盖条带的开始时间到结束时间的间隔不能超过最长覆盖时间Tij；式(5)表示条带的左边界应平行于相应的地面轨道lij；式(6)表示条带的侧摆角不能超过相应卫星的最大侧摆角Wi；式(7)表示每个机会选择条带的数量不多于1个。

1.4 基于网格的条带构造

基于上文对MSRTC问题的建模分析表明，解决该问题首先需要进行有效的条带构造。理论上，覆盖的开始和结束时间、卫星偏转角度等都是取值连续的量，会因此产生由连续的条带簇组成的无限大的备选条带集合。为了实现方案的可操作性，区域目标需要进行离散，常用的离散方法是网格离散法。基于网格的条带构造法示意如图2所示，目标区域被离散成网格，网格中的每个正方形单元称为一个单元格。

图2 基于网格的条带构造法示意Fig.2 Diagram of strip construction algorithm based on grid

本文在网格化离散的基础上，根据Zhu等[9]提出的基于网格的条带构造法构造有限数量的条带集合。基于网格的条带构造法通过在网格中选择3个锚定单元格t，g和u，分别确定每个可行条带的左边界、上边界和下边界，再从覆盖条带反向确定观测起止时间和侧摆角度。无论是同一条带还是不同条带，锚定单元格可以被重复使用。图2展示了一条斜率为负的条带(形如“”)和一条斜率为正的条带(形如“/”)。以前者为例说明一个条带的构造方法，后者的构造方法与之类似：

已知机会cij和相应的地面轨道投影直线lij，首先通过在每个单元格的左下顶点外形成一条平行于lij的直线来筛选出不违反最大侧摆角约束的单元格。如果不违反约束，将这条线记为l1，并作为条带的左边界。一旦确定了条带的左边界l1，就可以根据式(8)计算出相应的条带宽度w(t)：

(8)

式中，dt为直线l1到lij的距离；hi为卫星Fi所在的高度。

条带的左边界l1和条带宽度w(t)已经确定，可以相应地确定条带右边界l2的位置。在lij上分别找到Bij和Eij时刻的对应位置投影点PijB和PijE，并分别过PijB和PijE点做与lij垂直的直线lijB和lijE。最后，从直线lijB，lijE，l1和l2围成的封闭区域内选择一对满足以下条件的单元格g和u，经过单元格g的左上顶点绘制一条垂直于lij的线并记为l3，经过单元格u的右下顶点绘制一条垂直于lij的线并记为l4，卫星到达l3和l4的时间间隔不得超过Tij。l3和l4分别形成条带的上边界和下边界，卫星相继到达线l3，l4与lij的交叉点位置的时间，就是所构造条带的开始时间和结束时间。

基于网格的条带构造法就是在划分的网格中找出所有符合上述条件的单元格组合，同时按照上述方法确定条带的边界及覆盖范围。构造出的条带之间允许重叠，但每个新生成的条带应与现有条带进行比较，以消除条带集中的冗余。当一条带的覆盖区域是另一条带的子集时，需要删除被包含的条带。最终的覆盖方案是从不同机会的条带集合中分别选择一个条带作为对应机会的实际覆盖范围。此外，本研究采用Vatti[17]提出的多边形布尔运算法计算所选条带的并集，确定解的覆盖范围。

2 局部网格嵌套策略

根据条带构造方法可知，网格离散化的粒度是影响条带数量的直接因素。在MSRTC问题中，当网格划分的粒度较大时，在此基础上构造出的条带比较稀疏，不利于方案的组合。但是，当网格划分的粒度较小时，会产生数量较大的网格，随之产生的条带不仅数量较大，在位置上的排列也非常密集，还会在条带构造环节产生较大的计算负担和搜索负担。因此，本文提出了通过局部处理区域网格离散，控制网格数量减少冗余计算的LGN策略。

在Hu等[12]提出的父子网格中，一个区域可以先被划分成粒度较大的网格作为父网格，通过对父网格的嵌套形成新的子网格。如果一次嵌套操作将一个单元格的边长缩短到原来大小的1/2，父单元格将被分成4个子单元格；如果长度缩短到1/3，一个父单元格将产生9个子单元格。由此得到的子单元格也可以按照同样的规则分裂下去。

这种父子网格结构具有2个重要特性：第1，父单元格完全包含子单元格。这确保了不同层级的网格以及根据不同层级的网格构造出的条带可以共存。第2，在父网格中构造的备选条带在子网格中仍然是可行的。这意味着在给定的区域中，子单元格构建的条带集合完全包含父单元格构建的条带集合。嵌套网格意味着原始条带集合的扩展。根据这样的性质，本文将父子网格的嵌套应用到局部网格区域，提出了LGN策略。

在LGN策略中，对一个局部区域LRcij的嵌套仅仅意味着机会cij具备了在新网格构造条带的条件。尽管局部区域间存在重叠，也不会影响到其他任何机会的条带集合，以及其他机会对应条带的位置和覆盖范围。例如，如果2个机会c1和c2的局部区域LRc1和LRc2存在部分重叠，在对LRc1进行局部嵌套时也会将重叠部分进行分割。但是机会c2的网格层级并不因此发生变动，也不会生成新的条带，除非对LRc2单独执行嵌套。

根据本文所提出的LGN策略，对目标区域进行离散时不需要在起始阶段就将整个区域完全划分成众多的小单元格，从而带来过大的计算压力；而是以一个较粗粒度的网格作为初级网格，在初级网格上构造出可行的初始解，再以此为基础根据需要对局部区域进行细化。这个选择局部区域进行嵌套细化的操作可以自然地融合到局部搜索的过程中，根据搜索需要进行局部嵌套，找到较优的覆盖方案。

3 基于局部网格嵌套的变邻域搜索算法

3.1 变邻域搜索算法

Hansen等[18]针对旅行商问题首次提出了变邻域搜索算法，该算法是一种改进的局部搜索算法，在求解大规模的组合优化和全局优化问题中性能良好。变邻域搜索算法的思想基于以下基本事实：不同邻域结构之间的局部最优解之间没有必然联系，全局最优解是所有可能邻域的局部最优解。

① 构造初始解X0，令最优解Xb=X0。

② 若满足终止条件，转⑤；否则，随机地从Xb的某一邻域中选取解X作为变邻域深度搜索的当前解。

③ 令m=1，开始进行变邻域深度搜索。在X的Nm邻域中进行局部搜索，得到局部最优解X′。

④ 如果X′优于Xb，则更新Xb=X′，令m=1；否则，令m=m+1。

⑤ 若m<2，转②；否则，输出最优解Xb。

3.2 LGN-VNS算法

根据LGN策略和VNS算法的特点，将二者进行结合，提出了LGN-VNS算法。在LGN-VNS算法中，设计了2个邻域结构N1和N2，同时这些邻域也在抖动过程中使用。

3.2.1 邻域结构N1

3.2.2 邻域结构N2

与邻域结构N1相比，邻域结构N2替换的条带更多，对当前覆盖方案的扰动更大，增强了解的多样性。

3.2.3 LGN-VNS算法步骤

③ 若满足终止条件，则输出最优解；否则，从Xb的某一邻域Nm中选取1个解X作为变邻域深度搜索的当前解。

④ 令m=1，Nm为当前的邻域结构，在Nm中对X执行局部搜索，直到得到局部最优解X′。

⑤ 如果X′优于Xb，则更新Xb=X′，令m=1；否则，令m=m+1。

⑥ 若m<2，转③；否则，输出最优解Xb。

4 实验测试与结果

由于目前没有MSRTC问题的公认数据集，本文使用随机生成的10个算例进行实验测试。本节不仅验证了本文所提出的LGN-VNS算法对不同规模的算例的可行性；还通过与普通的VNS算法进行对比，验证了LGN策略的有效性，最后通过与遗传算法进行对比，验证了LGN-VNS算法的有效性和高效性。

算例参数如表2所示。算例的区域规模有50 km×50 km，100 km×100 km，150 km×150 km，200 km×200 km和250 km×250 km 五种，所有算例的一个初始单元格均表示10 km×10 km的区域面积。随着目标区域面积的增加，相应的机会数量也从5个逐渐增加到50个。为避免偶然因素，本文对以下实验都进行了10次独立重复。实验结果以覆盖方案对目标区域的有效覆盖率为评价依据。所选条带的并集和覆盖方案的覆盖率由多边形布尔运算法计算所得。本实验的测试平台为具有24 GB RAM和运行3.60 GHz 64位Windows10操作系统的IntelCorei7-7700处理器的PC，编程语言为C#。

表2 算例参数Tab.2 Parameters of instances

4.1 LGN-VNS算法求解MSRTC问题

首先，使用LGN-VNS算法进行覆盖方案规划测试。图3展示了LGN-VNS算法10次重复实验得到的最优覆盖方案，以及与最优覆盖方案相对应的初始覆盖方案。如图3(b)表示LGN-VNS算法在算例1上寻找出的最优覆盖方案，图3(a)表示该最优覆盖方案对应的初始覆盖方案。从图3中不难看出，对于不同规模的算例，随机生成的初始覆盖方案经过LGN-VNS算法的寻优都得到了明显提升。

(a) R1初始覆盖方案 (b) R1最优覆盖方案

(c) R2初始覆盖方案 (d) R2最优覆盖方案

(e) R3初始覆盖方案 (f) R3最优覆盖方案

(g) R4初始覆盖方案 (h) R4最优覆盖方案

(i) R5初始覆盖方案 (j) R5最优覆盖方案

(k) R6初始覆盖方案 (l) R6最优覆盖方案

(m) R7初始覆盖方案 (n) R7最优覆盖方案

(o) R8初始覆盖方案 (p) R8最优覆盖方案

(q) R9初始覆盖方案 (r) R9最优覆盖方案

(s) R10初始覆盖方案 (t) R10最优覆盖方案图3 LGN-VNS算法所得最优覆盖方案Fig.3 Optimal coverage schemes obtained by LGN-VNS algorithm

表3记录了LGN-VNS算法所得的最优方案覆盖率、对应的初始方案覆盖率、提升覆盖率以及相对提升率。其中，相对提升率为最优方案与对应初始方案之间覆盖率的差值与初始方案覆盖率的比值。由表3可以看出，相较于初始方案，LGN-VNS算法的提升效果十分明显，平均提升覆盖率为29.87%，在其中的3个算例中甚至出现了40%以上的提升。平均相对提升率高达64.83%，其中的2个方案相对于其初始方案得到了100%以上的相对提升。

表3 LGN-VNS算法所得最优方案及其提升率Tab.3 Optimal solution obtained by LGN-VNS algorithm and their lifting rate 单位：%

4.2 LGN-VNS与VNS算法比较分析

LGN-VNS与VNS算法所得解的平均覆盖率及差值如表4所示。由表4可以看出，LGN-VNS所得方案的平均覆盖率远高于VNS算法。总体平均覆盖率之差为14.27%，在其中的4个算例中达到了20%以上的差距。

表4 VNS，LGN-VNS平均覆盖率及差值Tab.4 Average solution results of VNS algorithm，LGN-VNS algorithm and the difference 单位：%

LGN-VNS与VNS的平均提升覆盖率对比如表5所示。由表5可以看出，LGN-VNS的平均提升率均值达29.73%，同样远高于VNS算法的16.38%，提升覆盖率的平均差值为13.34%。对于算例3，两算法的平均提升率之差甚至达到了33.72%。充分证明了LGN-VNS的搜索能力优于VNS，验证了LGN策略的有效性。

表5 VNS，LGN-VNS提升覆盖率均值及差值Tab.5 Average lift rate of VNS algorithm， LGN-VNS algorithm and the difference 单位：%

4.3 LGN-VNS与遗传算法的比较分析

为了验证LGN-VNS算法的有效性，将其与遗传算法(GA)进行了求解效果和求解时间上的比较。在GA中采用同样方式获得初始解。GA的种群规模设置为10，最大迭代次数设置为100，当连续20代的种群最优解不发生改变时，迭代自动结束。

LGN-VNS算法与GA的平均覆盖率及求解时间对比如表6所示。由表6可以看出，LGN-VNS算法在所有算例中得到的覆盖方案，不仅结果都明显好于GA，而且所用时间也明显短于GA。LGN-VNS算法的求解均值整体高于GA14.40%，但整体求解时间仅为GA的36.44%。这表明LGN-VNS算法能够较快地得到质量较高的解，充分体现了LGN-VNS算法的有效性和高效性。

表6 LGN-VNS，GA平均覆盖率及求解时间Tab.6 Average coverage rate and solution time of LGN-VNS algorithm and GA algorithm

5 结束语

本文分析了MSRTC问题中区域目标的离散精度对覆盖方案的最优性和获得方案的复杂程度的影响，在网格离散法和基于网格的条带生成法的基础上，改进了父子网格嵌套机制，提出了一种局部网格嵌套的LGN策略；并结合VNS搜索算法，提出了LGN-VNS算法。

对10个规模不同的随机算例进行的测试实验表明，LGN-VNS算法对MSRTC问题的搜索性能提升非常明显，对随机生成的测试算例表现出平均提升覆盖率为29.73%的提升效果，远远高于普通VNS算法的16.38%。另外，在对10个随机算例的实验中，LGN-VNS算法的求解结果全部高于普通VNS算法，平均高出14.27%。不仅如此，LGN-VNS算法在求解效果和求解效率方面都好于GA，表现出了明显的优越性。

经实验验证，本文提出的LGN-VNS算法在求解MSRTC问题方面具有明显的优势，能够在较短的时间内得到相对不充足的卫星覆盖资源下高覆盖率的区域目标覆盖方案。