遙感衛星地面站資源調度的混合分解算法

劉靜怡, 田妙苗, 黃 鵬, 林友明, 馬廣彬

(1.中國科學院 遙感與數字地球研究所, 北京 100094；2.中國科學院大學 電子電氣與通信工程學院, 北京 100049)

衛星獲取遙感數據后, 需將這些數據傳輸到地面系統, 由地面站完成數據的接收與記錄.遙感衛星地面站(下稱地面站)資源調度是指考慮時間窗口和資源性能等約束, 合理分配地面站資源, 以完成遙感衛星數據接收任務的過程.隨著遙感在各領域中的廣泛應用[1], 數據接收任務日益增多, 調度場景更復雜, 導致資源調度規模增大, 求解難度上升, 對求解地面站資源調度問題提出了更高的要求, 因此, 快速、高效地調度地面站資源, 最優化接收衛星數據, 成為一個亟待解決的問題[2].

地面站資源調度問題是一個復雜的組合優化問題[3], 求解算法包括確定性算法、智能搜索算法、啟發式算法及混合算法[4-8].近年來, 針對地面站的資源調度效率、資源使用率、任務完成率等問題已提出了許多求解算法.文獻[9]針對伽利略系統嚴格的分發要求提出了一種新的上行調度算法, 有效提高了資源利用率; 文獻[10-11]研究了蟻群算法在地面站資源調度問題中的應用, 并對算法進行了改進, 提高了算法的搜索能力; 為進一步提高求解的效率和精度, 文獻[12-13]使用混合求解算法對組合優化問題進行求解, 通過對問題分解, 獲得了良好的求解效果.中國遙感衛星地面站采用遺傳算法求解該問題時, 為加快求解速度, 基于分治法思想先將待解問題按沖突任務集分解為多個小任務量的子問題.但隨著數據接收任務數量和任務間沖突的增加, 沖突任務集規模增大, 這種分解的作用會越來越有限.因此, 本文基于中國遙感衛星地面站運行管理的現實需求, 以提高地面站資源調度時效性為目標, 對多地面站資源調度問題進行研究.考慮衛星數據接收任務優先級、時間窗口和地面站資源性能等約束條件, 建立基于連續時間的混合整數線性規劃(mixed integer linear programming, MILP)模型.為加快求解速度, 將地面站資源調度問題分為地面站選擇和單地面站資源調度兩層, 提出一種基于啟發式規則和設備分解的混合分解算法.該算法首先利用先驗信息, 對地面站資源使用的沖突程度進行評價, 根據評價值選擇接收任務的地面站, 將地面站資源調度問題分解為多個單地面站資源調度問題； 然后使用Lagrange分解算法, 松弛站內天線與記錄器關聯約束, 按設備進行分解, 進一步縮小問題規模, 對天線調度與記錄器調度子問題分別求解, 得到問題的可行解.

1 地面站資源調度問題

衛星數據接收設備主要包括天線、信道、記錄器等, 接收過程如圖1(A)所示.數據由天線接收后, 經過信道的變頻和解調, 最后由記錄器記錄.當遙感衛星進入地面站接收范圍時, 地面站可對衛星數據進行接收, 地面站能接收衛星數據的時間范圍稱為時間窗口.由于地面站的信道資源相對充足, 因此本文只考慮天線和記錄器的調度問題.

在地面站接收衛星數據過程中, 存在接收任務重疊和接收資源沖突兩個問題.

1.1 接收任務重疊

對于采用廣播方式發送信號的衛星, 當其位于多個地面站接收范圍間的重疊區域時, 每個地面站均可接收到該衛星的數據.對部分任務數據重復接收的情形稱為接收任務重疊, 如圖1(B)所示.由圖1(B)可見, 任務a,b,c分別表示地面站1,2,3對同一衛星的數據接收任務.任務a和b稱為一組重疊任務,t2～t3為其重疊時間； 任務b和c為一組存在包含關系的重疊任務,t3～t4為其重疊時間.對于重疊任務, 為減少或避免重復接收、浪費地面站資源, 需選擇盡可能少的接收地面站承擔任務, 同時為了保證數據接收質量, 在實際運行中, 兩重疊任務之間需保證一定長度的重疊時間.

圖1 衛星數據接收過程Fig.1 Receiving process of satellite data

1.2 接收資源沖突

當多個衛星同時經過同一地面站的接收范圍時, 如果同一時刻的衛星任務數量大于接收站天線數量, 或下傳數據量超出記錄器能力范圍, 就會導致部分任務數據無法被接收, 即接收資源沖突.這種情形下, 地面站資源調度需考慮天線、記錄器的性能及任務的重要性等因素.

2 問題模型及求解算法

圖2 求解算法流程Fig.2 Flow chart of solution algorithm

對于重疊任務, 需綜合考慮重疊時間內多個地面站中資源的使用情形； 對已確定接收地面站的任務, 需對該地面站的站內資源進行調度.針對上述問題, 本文將求解地面站的資源調度問題分為兩個階段.第一階段, 為重疊任務分配地面站, 將多地面站調度問題轉化為多個單地面站調度問題.第二階段, 對單個地面站的站內資源進行調度, 為任務分配具體設備資源.求解流程如圖2所示.

2.1 地面站選擇

地面站選擇的目標是確定重疊任務的接收地面站, 盡量多地接收衛星數據.考慮到地面站接收衛星數據時的設備切換成本, 在實際操作中通常不接收被包含的任務(如圖1(B)中任務c被任務b包含, 取消地面站3對任務c的接收).本文提出一種考慮地面站資源數的地面站資源使用沖突程度評價指標(簡稱評價指標), 并根據該指標獲得地面站選擇的近似最優方案.該評價指標為重疊時間內地面站接收任務數量與地面站資源數量的比值, 公式為

(1)

其中：i為衛星數據接收任務序號;s為地面站; clushnum(i,s)表示在任務i的重疊時間內地面站s接收衛星任務的數量; resource(s)表示地面站s的資源數量;Io為重疊任務的集合;S為地面站集合.cd(i,s)值越小, 重疊時間內地面站資源使用沖突程度越低.

引入評價指標后, 地面站的選擇可通過比較評價指標值得到.通過以下啟發式規則完成對地面站的調度：

規則1) 調度的目標為最小化地面站資源沖突程度和地面站切換次數, 即

(2)

其中： station(i,s)為二值變量, 任務i由地面站s接收時為1, 否則為0; over(i,s)為地面站s接收任務i時設備的切換次數;cd(i,s)為地面站s接收任務i時的評價指標.

規則2) 一個任務最多選擇一個地面站進行接收, 表示為

(3)

規則3) 一組重疊任務在重疊時間內至少需要選擇一個地面站接收, 表示為

(4)

其中Ic(i)為任務i所在的重疊任務組.

算法步驟如下：

1) 對任務集I中的n個任務, 按任務開始時間從小到大的順序排序；

2) 將任務集中的每個任務i依次與其后的每個任務比較, 如果存在與其衛星名相同、接收時間有重疊的任務i′, 則i與i′組成一組重疊任務；

3) 比較重疊任務組中任務的接收時間, 如果存在包含關系, 則刪除被包含的任務, 轉步驟6); 否則, 轉步驟4)；

4) 根據式(1)計算評價指標；

5) 選擇評價指標最大的地面站, 減少對應任務的接收時間；

6) 判斷任務集I是否已經遍歷結束, 若判斷結果為是, 則返回地面站的選擇方案； 否則轉步驟2).

2.2 單地面站資源調度模型

單地面站資源調度問題的優化目標為最小化任務的接收成本.這里成本包括4部分： 天線使用成本、記錄器使用成本、任務不完整接收的懲罰和記錄器共用的懲罰.目標函數為

該問題的約束條件可分為以下4類： 天線分配約束、記錄器分配約束、天線記錄器關聯約束和任務接收時間約束.

1) 天線分配約束.對每個任務, 最多分配一個天線， 表示為

(6)

其中I和J分別表示可接收任務和單地面站中天線資源的集合.

在前一個任務接收結束后一段時間τ內, 同一天線不能接收其他任務， 表示為

其中: 參數M是一個極大值; 參數τ為設備切換時間, 在該問題中τ=270 s; 變量b(i)表示任務i的接收開始時間; 變量c(i)表示接收任務結束時間;X(i,i′)為二值變量, 當其值為1時表示任務i′順序在任務i后, 默認將任務列表按計劃任務開始時間進行排序, 則X(i,i′)可表示為

當任務接收時間不為0時, 必須分配天線, 表示為

(8)

其中變量b(i)和c(i)分別是實際接收的開始時間和結束時間.

2) 記錄器約束.對每個任務最多分配一個記錄器, 表示為

(9)

不存在記錄器共用的兩個任務, 在前一個任務接收結束后一段時間τ內, 同一記錄器不能接收其他任務, 表示為

其中: 參數pt(i)為計劃任務進行時間;y(i,i′)為一個二值變量, 當任務i與i′存在記錄器共用時其值為1, 否則為0.當每個記錄器在同一時間記錄任務所需的通道數不得超過記錄器本身具有的邏輯記錄器數目時， 表示為

其中: 參數chanl(i)表示任務i數據下行通道數量； 參數logicnum(k)表示記錄器k邏輯記錄器數量.

3) 天線記錄器關聯約束.每個任務天線與記錄器或者都分配或者都不分配, 表示為

(12)

4) 任務接收時間約束.任務的未接收時間表示為

pnc(i)=pt(i)-c(i)+b(i), ?i∈I.

(13)

接收任務開始時間和結束時間必須在時間窗口內, 表示為

c(i)≤te(i), ?i∈I,

(14)

b(i)≥st(i), ?i∈I,

(15)

其中: 參數te(i)表示時間窗口的結束時間; 參數st(i)表示時間窗口的開始時間.接收任務開始時間小于等于接收任務結束時間表示為

b(i)≤c(i), ?i∈I.

(16)

2.3 Lagrange分解算法

Lagrange分解基本思想是在求解有約束的數學規劃模型時, 通過引入Lagrange乘子松弛部分約束, 從而將原問題分解為多個規模較小、易求解的對偶子問題.各子問題之間利用Lagrange乘子關聯, 通過不斷調整Lagrange乘子及求解子問題可得到原問題的近似最優解.

2.3.1 分解方案 單地面站調度模型中, 考慮對天線和記錄器兩類資源進行調度.由于天線和記錄器的調度關系相對獨立, 因此本文設計了基于設備分解的Lagrange分解方法, 通過松弛天線與記錄器之間的關聯約束(12), 將該問題分解成天線調度P1和記錄器調度P2兩個子問題.為保證所有子問題中相同任務對應的開始時間和結束時間相同, 需添加如下約束：

c1(i)=c2(i), ?i∈I,

(17)

b1(i)=b2(i), ?i∈I,

(18)

其中,b1(i)和c1(i)及b2(i)和c2(i)分別為子問題P1和P2的接收開始時間和結束時間.

給定非負Lagrange乘子λ1松弛約束(12)、λ2松弛約束(17)、λ3松弛約束(18), 可得如下天線調度子問題P1的數學模型：

其中: pnc1(i)為P1中任務因沖突未接收的時間; 式(19)為P1的目標函數; 式(6), 式(20)～(25)為其約束條件.記錄器調度子問題P2的數學模型為

其中: pnc2(i)為P2中任務因沖突未接收的時間; 式(26)為P2的目標函數; 式(9),(11),(27)～(32)為其約束條件.

2.3.2 Lagrange乘子的更新 在單地面站資源分配問題中, Lagrange乘子λ1,λ2,λ3表示天線調度方案中任務i的天線分配數、接收開始時間、接收結束時間和記錄器調度方案不一致時所帶來的懲罰.因此, 當天線調度方案中任務i天線分配數、接收開始時間和接收結束時間大于記錄器調度方案中對應項時,λ1,λ2,λ3增大, 反之減小.次梯度算法因其形式簡單且能保證收斂的穩定性而得到廣泛應用, 其表達式為

λk+1=λk+[tk/(‖Sk‖2+γ)]Sk,

(33)

其中:k表示算法的迭代次數；t為步長；S表示由子問題的解計算得到的次梯度.本文算法中, 在次梯度公式中添加了一個給定的極小值γ, 其作用是為了避免分母為0.本文算法中γ=10-5,λ1,λ2,λ3的初始值為0.

2.3.3 可行化方案 由于子問題中松弛了部分約束, 得到的解可能不是原問題的可行解.同時對于好的Lagrange乘子, 子問題解中的二值變量, 即ant(i,j)和rec(i,k)的取值接近最優解, 因此可利用一種啟發式算法將不可行解轉換成可行解.在啟發式算法中, 如果子問題的解不滿足天線記錄器關聯約束(12), 則將為任務分配資源較少的子問題的解作為已知量, 代入單站資源調度模型進行計算, 得到單站資源調度問題的可行解及對應的目標函數值costP.

2.3.4 停止準則 對偶間隙是衡量松弛問題和原問題解接近程度的一個指標.通常以對偶間隙的大小作為停止準則, 當對偶間隙小于給定值時停止迭代, 即

gap≤ε.

(34)

對偶間隙可表示為

gap=(costP-cost_1p-cost_2p)/costP,

(35)

其中： costP表示問題P可行解對應的目標函數值； cost_1p和cost_2p分別表示子問題P1和P2所得解對應的目標函數值.本文算法中ε=0.3.

圖3 Lagrange分解算法流程Fig.3 Flow chart of Lagrangean decomposition algorithm

為保證計算效率, 得到滿意解時能快速輸出結果, 本文算法在子問題的解滿足被松弛的約束(12)、步長t→0或循環次數達到給定值時, 停止迭代.

2.3.5 算法流程 Lagrange分解算法的求解流程如圖3所示, 步驟如下：

1) 初始化Lagrange乘子；

2) 求解子問題, 獲得子問題的目標函數值cost_1p和cost_2p；

3) 利用啟發式算法可行化子問題的解, 得到可行解對應的目標函數值costP；

4) 計算對偶間隙, 如果對偶間隙小于給定值, 或子問題的解滿足被松弛的約束(12), 說明資源分配非常接近最優解, 則轉步驟6)；

5) 更新Lagrange乘子, 如果步長趨于0, 或循環次數達到給定最大循環次數, 則說明資源分配不能進一步進行有效調整, 轉步驟6)；

6) 輸出地面站資源調度方案, 算法終止.

3 實驗結果與分析

3.1 規模及參數

為驗證算法的有效性和實用性, 本文選取15組不同規模的案例, 表1列出了不同實例的任務數量和任務總時長.本文考慮了3個地面站, 地面站資源列于表2, 包括天線資源和記錄器資源.

表1 案例規模

表2 地面站資源

3.2 求解時間和目標函數值

在實際運行中, 中國遙感衛星地面站采用結合啟發式規則的遺傳算法(下稱原算法)對地面站資源進行調度.本文算法與原算法的計算結果列于表3.

表3 本文算法與原算法的計算結果對比

表3中原算法所列結果為5次計算所得結果的平均值.由表3可見, 相比原算法, 本文算法在求解時間上提高了81%～94%； 在目標函數上, 本文算法的目標函數值均小于原算法.求解時間的減少, 說明本文算法能有效提高多地面站資源調度問題的求解效率； 目標函數的減少, 說明本文算法的資源調度方案更合理, 降低了接收成本.

3.3 典型案例分析

表4和表5分別為案例7中任務1～11及案例13中任務1～14的調度結果.包括計劃接收時長、實際接收時長、天線分配和記錄器分配.其中計劃接收時長為任務時間窗口的長度； 實際接收時長為調度結果中任務的實際接收時長； 任務的優先級分為5級, 由高到低分別用P1～P5表示.

表4 案例7調度結果

由表4可見, 本文算法與原算法的調度結果中, 任務1～6、任務8～9和任務11的實際接收時長相同.對任務7和任務10, 本文算法未完整接收任務7, 未接收時間為211 s； 原算法未完整接收任務10, 未接收時間為211 s.從接收時長的角度分析, 本文算法和原算法的實際接收時長相同, 未接收任務的時長均為211 s.從任務優先級的角度分析, 任務10的優先級高于任務7, 原算法選擇完整接收任務7, 本文算法選擇完整接收任務10, 保證了高優先級任務的接收.因此, 兩種算法的任務接收時長相同, 但考慮任務優先級, 本文算法更優.

表5 案例13調度結果

由表5可見, 對比本文算法與原算法的結果, 任務1、任務3～7、任務9～10和任務12～14的實際接收時長相同.對任務2,8和11, 本文算法未完整接收任務2, 未接收時間為19 s； 原算法未完整接收任務8且未接收任務11, 未接收時間分別為32 s和549 s.從接收時長的角度分析, 本文算法實際接收時長減少19 s, 原算法減少581 s, 本文算法的實際接收時長更長, 保證了更多衛星數據的接收.從任務優先級的角度分析, 任務11的優先級高于任務2和任務8, 本文算法的調度結果完整接收任務11, 保證了高優先級任務的接收.因此, 從接收時長和任務優先級兩方面評價, 本文算法結果更優.

綜上所述, 針對中國遙感衛星地面站實際運行中的地面站資源調度問題變量多、規模大、難以快速求解等問題, 本文提出了一種混合分解算法.實驗結果表明, 該算法提高了任務的求解效率, 在任務接收時長和高優先級任務的接收上優化效果較好.