基于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問題方面具有明顯的優勢，能夠在較短的時間內得到相對不充足的衛星覆蓋資源下高覆蓋率的區域目標覆蓋方案。