徐明明，王俊峰

(1.四川大學計算機學院，成都 610065； 2. 四川大學空天科學與工程學院，成都 610065)

1 引 言

對地觀測是衛(wèi)星一個非常重要的應(yīng)用，據(jù)聯(lián)合國外太空事務(wù)局(UNOOSA)記錄，截至2018年底，有601顆對地觀測衛(wèi)星仍在軌運行，約占全球在軌衛(wèi)星總數(shù)的33%[1].衛(wèi)星成像主要采用光學成像方式，其中小部分通過雷達等方法成像.當衛(wèi)星經(jīng)過目標上方時，稱之為“過頂”，此時衛(wèi)星與目標之間可見，衛(wèi)星才能對目標進行成像.衛(wèi)星的數(shù)量和傳感器的分辨率都在逐年上升，但衛(wèi)星的瞬時視野依然受限，對地觀測需求不斷增大，且發(fā)射衛(wèi)星的費用非常高昂，衛(wèi)星的工作壽命也很短暫，衛(wèi)星資源仍然緊缺，為了緩解這一問題，大量研究者針對對地觀測任務(wù)調(diào)度模型和算法進行不斷優(yōu)化和改進，力爭在滿足任務(wù)和資源約束的條件下為每個任務(wù)更加合理地分配衛(wèi)星資源和決定任務(wù)的執(zhí)行時間段.

對地觀測任務(wù)調(diào)度可分為單星調(diào)度和多星調(diào)度.早期的研究大多針對單顆衛(wèi)星資源進行調(diào)度，隨著觀測任務(wù)日益繁重，衛(wèi)星數(shù)量也不斷上升，如果采用單星調(diào)度，調(diào)度系統(tǒng)內(nèi)缺乏通用性，衛(wèi)星的觀測能力得不到充分利用.如何綜合利用衛(wèi)星網(wǎng)絡(luò)，高效的整合衛(wèi)星資源，全面地發(fā)揮多衛(wèi)星系統(tǒng)的觀測能力成為各國研究的重點.衛(wèi)星調(diào)度問題是一個NP難問題[2]，無法在多項式時間內(nèi)找到該類問題的最優(yōu)解，只能通過離散化和次優(yōu)化，在可接受的時間內(nèi)找到較優(yōu)解，主要的研究方法可分為確定性算法，搜索算法或啟發(fā)式算法：① 確定性算法中采用較多的是分支定界法[3-5]，該算法需要消耗大量的空間來存儲葉節(jié)點的邊界.當界定方法不適合時，分支定界法的性能退化至接近窮舉法;② 搜索算法在多星調(diào)度問題上廣泛使用，包括蟻群優(yōu)化算法[6]、遺傳算法[7]、爬山算法[8]、禁忌搜索算法[9-10]和模擬退火算法(Simulated Annealing,SA)[11]等，這種方法得到的解質(zhì)量較高，但搜索空間較大時，計算時間較長，并且有陷入局部最優(yōu)的風險;③ 啟發(fā)式算法基于先驗信息制定任務(wù)調(diào)度規(guī)則，Chen等人[12]提出了幾種基于優(yōu)先級和沖突避免的啟發(fā)式策略，并開發(fā)了基于時間的貪婪方法，基于權(quán)重的貪婪方法，以及改進的差分進化算法.Cho等人[13]重新定義多星調(diào)度問題為旅行商問題的變體，并結(jié)合一種典型的基于鄰域搜索的路徑改進算法——Lin-Kernighan-Helsgaun啟發(fā)式算法來解決該問題.王慧林等人[14]針對異構(gòu)地球觀測資源網(wǎng)提出了兩種算法用以協(xié)調(diào)和分配觀測任務(wù)，包括最高權(quán)重優(yōu)先分配算法和禁忌列表模擬退火算法.該類算法規(guī)則較為復(fù)雜，設(shè)計思路的偏離將造成性能與最優(yōu)解相去甚大.

為了提高衛(wèi)星調(diào)度系統(tǒng)的靈活性和魯棒性，Morris等人[15]提出了一種分布式的調(diào)度模型思路：將多星調(diào)度分解為兩個子問題，預(yù)調(diào)度和單星自主調(diào)度.首先，為每個任務(wù)分配衛(wèi)星資源，然后每個衛(wèi)星執(zhí)行自主單星調(diào)度算法.但他們只描述了框架的模型，并沒有針對上述框架提出具體的策略.已有一些研究者采用基于分解的分布式模型來進行多星觀測調(diào)度：李菊芳等人[16]采用自適應(yīng)蟻群優(yōu)化算法搜索最優(yōu)的任務(wù)分配方案，在單星自主調(diào)度階段采用非?？焖倌M退火算法.實驗結(jié)果表明，對比于禁忌搜索算法，性能提升并不明顯(<8%).孫凱等人[17]提出了一種新的學習型遺傳算法來解決任務(wù)資源匹配問題，并采用后移滑動策略及最優(yōu)插入位置搜索策略解決單星任務(wù)調(diào)度子問題.Sinha等[18]提出了一種基于多代理的衛(wèi)星系統(tǒng)建模方法，并利用最大增益消息算法處理衛(wèi)星中的任務(wù)分配問題.當搜索算法應(yīng)用于多星預(yù)調(diào)度階段時存在缺陷：根據(jù)后續(xù)的單星調(diào)度階段的結(jié)果更新解的適應(yīng)度，完成反饋，導(dǎo)致預(yù)調(diào)度算法和單星自主調(diào)度算法的耦合.此外，搜索算法的終止條件和初始值的設(shè)定也會影響性能，設(shè)置不當會導(dǎo)致分配方案不合理.

針對以上問題，本文提出了一種基于規(guī)則的啟發(fā)式算法，適用于分布式的衛(wèi)星任務(wù)規(guī)劃系統(tǒng)，其目標是在預(yù)調(diào)度階段，考慮能量約束，化解任務(wù)之間的沖突，完成優(yōu)化目標，并且通過將計算負載從單個節(jié)點分散到多個來減少計算時間，從而提高系統(tǒng)的效率和穩(wěn)定性.該預(yù)調(diào)度算法實現(xiàn)簡單，通用性強，只需衛(wèi)星和任務(wù)的先驗信息，后續(xù)的單星自主調(diào)度階段的算法可以結(jié)合實際情況自由選擇，無需編寫反饋接口.

2 多星成像任務(wù)調(diào)度模型

2.1 多星成像任務(wù)調(diào)度模型輸入與數(shù)據(jù)的預(yù)處理

根據(jù)圖像衛(wèi)星的特點，作如下假設(shè).

① 用戶提交任務(wù)后，無法撤回或更改；

② 用戶無法在任務(wù)規(guī)劃期間提交任務(wù)；

③ 一個任務(wù)可能有幾顆衛(wèi)星可以執(zhí)行它，但最終只能由其中一顆衛(wèi)星執(zhí)行；

④ 衛(wèi)星在一個運行周期內(nèi)對一個任務(wù)目標點最多只能有一次觀測機會；

⑤ 衛(wèi)星觀測具有原子性，一旦觀測任務(wù)開始執(zhí)行就無法被中斷；

⑥ 在一個時間點，衛(wèi)星只能對一個任務(wù)目標點進行觀測.

基于上述前提假設(shè)，本文對多星問題的輸入進行公式化表達，衛(wèi)星和任務(wù)的主要參數(shù)如表1.

表1 衛(wèi)星和任務(wù)的主要參數(shù)Tab.1 Main parameters of satellites and missions

得到輸入后，系統(tǒng)進行預(yù)處理，通過仿真得到目標點對衛(wèi)星可見的時間范圍，再計算該時間范圍與任務(wù)的指定觀察時間范圍重疊的部分，稱之為可用時間窗口，表示為

TW={twij|1≤i≤NSC,1≤j≤NT}

(1)

其中，(tw_startij,tw_endij)為衛(wèi)星i可完成任務(wù)j的時間段;mpcij為衛(wèi)星i完成任務(wù)j的最小電量消耗;mmcij為衛(wèi)星i完成任務(wù)j的最小內(nèi)存消耗.

2.2 多星成像任務(wù)調(diào)度模型的輸出與優(yōu)化目標

完成預(yù)調(diào)度后，得到分配矩陣O.

O={oij|1≤i≤Ns+1,1≤j≤NT}

(2)

多星觀測調(diào)度本質(zhì)上是一個滿足約束的調(diào)度機問題，約束條件對于調(diào)度過程的制約非常大，從而影響調(diào)度結(jié)果.本文采用的是超額訂購方式，即在給定的松弛程度下，分配到衛(wèi)星的任務(wù)量可以超出衛(wèi)星的執(zhí)行能力，σi代表系統(tǒng)的超額分配率.

(3)

(4)

(5)

(6)

其中，SNs+1是一顆虛擬衛(wèi)星，所有不能被衛(wèi)星資源調(diào)度的任務(wù)將分配到該衛(wèi)星上;式(3)是任務(wù)的單一執(zhí)行約束，即每個任務(wù)只能被調(diào)度一次；式(4)～(6)是衛(wèi)星的載荷能力約束，即每個衛(wèi)星完成分配到的任務(wù)數(shù)量、所需的總耗電量和存儲容量不能超過給定松弛程度下衛(wèi)星的載荷能力.

預(yù)調(diào)度是多星調(diào)度的第一階段，因此其優(yōu)化目標和整個多星調(diào)度的相同.當單星調(diào)度階段完成時，分配矩陣O將被更新，主要是因為某些任務(wù)在單星調(diào)度階段未能成功調(diào)度，只能分配到虛擬衛(wèi)星上.最終的優(yōu)化目標是最大化執(zhí)行完單星自主調(diào)度算法后可以成功調(diào)度的任務(wù)的總優(yōu)先級，可以表示為

S.t. (3)～(6)

(7)

3 基于沖突概率的調(diào)度算法

3.1 算法描述

本節(jié)提出CIPBS算法來處理多星預(yù)調(diào)度問題.該算法的基本思路是在任務(wù)分配的過程中，根據(jù)當前分配情況計算任務(wù)在每個衛(wèi)星上成功執(zhí)行的概率，將任務(wù)分配給成像可能性最大的衛(wèi)星.Cho等人[13]提出影響成像概率的因素為當前任務(wù)可用時間窗口與同一衛(wèi)星上其它任務(wù)的可用時間窗口的重合程度，但只考慮這一因素是較為片面的，因為在多衛(wèi)星場景下，時間窗口沖突的多個任務(wù)被分配到不同的衛(wèi)星資源上，相互的影響不一定存在.如圖1所示，為了更充分利用多星調(diào)度問題的啟發(fā)式信息，本文將任務(wù)分為沖突任務(wù)和非沖突任務(wù)，沖突任務(wù)的沖突成像概率由潛在沖突系數(shù)、實際沖突系數(shù)和能量系數(shù)構(gòu)成，而非沖突任務(wù)只需要考慮能量的約束即能量系數(shù)，最終得到預(yù)分配結(jié)果.

圖1 求解策略Fig.1 Solving stategy

預(yù)調(diào)度階段的第一步是根據(jù)任務(wù)間可用時間窗口的重合度,將任務(wù)劃分為沖突任務(wù)和非沖突任務(wù)，以簡化后期沖突成像概率的求解.如圖2所示，mcitij是任務(wù)j在衛(wèi)星i上的可用時間窗口的最長連續(xù)無碰撞時長.如果

?i∈{1,2,…,Ns},mcitij>mdj

(8)

即在衛(wèi)星i上，任務(wù)j的最長連續(xù)可用無碰撞時長超過該任務(wù)的最小執(zhí)行時長，則稱任務(wù)j在衛(wèi)星i上無沖突.若某一任務(wù)在任一衛(wèi)星上無沖突，就是非沖突任務(wù)，否則，該任務(wù)是沖突任務(wù).

圖2 任務(wù)最長連續(xù)可用無碰撞時長示意圖Fig.2 Maximum continuous idle time of the task

如圖2所示，沖突成像概率由pij、rij和eij三部分構(gòu)成，其中，δ為無窮小量如下式.

(9)

其中，pij是潛在沖突系數(shù)，反映的是任務(wù)間的潛在影響，即尚未分配到衛(wèi)星i的任務(wù)在衛(wèi)星i上有可用時間窗口，可能在后續(xù)的調(diào)度中被分配到衛(wèi)星i上，和任務(wù)j爭搶時間窗.任務(wù)j的潛在沖突系數(shù)的計算方法為：找出所有未分配但在衛(wèi)星i上有可用時間窗口的任務(wù)，計算(tw_startij,tw_endij).

(10)

式(9中)，rij是實際沖突系數(shù)，反映的是任務(wù)間的實際影響，即在計算任務(wù)j分配到衛(wèi)星i時的沖突成像概率時，已經(jīng)有一些任務(wù)被分配到衛(wèi)星i上，如果這些任務(wù)和任務(wù)j的執(zhí)行會產(chǎn)生沖突，這種沖突必須在此時最小化.在計算過程中，每個衛(wèi)星都維護各自的有向無環(huán)圖用以計算實際沖突系數(shù).記衛(wèi)星i的圖為Gi，其最長加權(quán)路徑為Gi_longestpath，該圖的結(jié)點由所有分配到該衛(wèi)星的任務(wù)構(gòu)成，圖的有向邊表示任務(wù)的執(zhí)行序列.加入一個任務(wù)j時，將任務(wù)結(jié)點j插入圖內(nèi)構(gòu)成圖Gi'，找到該圖包含結(jié)點j的最長加權(quán)路徑Gi'_longestpath.所有因該任務(wù)無法執(zhí)行的已分配任務(wù)的總權(quán)重就是任務(wù)j在衛(wèi)星i上的實際沖突系數(shù)rij，可表示為

rij=Gi_longestpath+pj-Gi'_longestpath

(11)

為了系統(tǒng)負載均衡和滿足能量約束，要考慮完成衛(wèi)星分配到的總?cè)蝿?wù)的能量消耗，故定義能量系數(shù)的計算如下.

(12)

綜上所述，算法1給出了CIPBS算法的詳細計算過程.

Algorithm1 Collision Probability-Based Schedule(CIPBS)

1) 生成場景(S,T)

2) 初始化參數(shù)

3) 預(yù)處理，計算tw,mmp,mpc,mcit

4) forj←1toNtdo

5) fori←1toNSCdo

6) ifMCITij>MDj

7) Φ←Φ∪{Tj}

8) Γi←Γi∪{SCi}

9) end if

10) end for

11) end for

12) while Λ*≠? do

13) 隨機選擇任務(wù)Tj∈Λ*

14) fori←1toNSCdo

15) 計算Λ*中每個任務(wù)的TW_overlapijk

17) 構(gòu)建衛(wèi)星Si上分配到的任務(wù)的有向無圈圖G

18) 將任務(wù)Tj插入G構(gòu)成G'

19)rij←Gi_longestpath+pj-Gi'_longestpath

22) end for

23) ifcij是{cik|1

24)oij←1

25)G←G'

26) end if

27) Λ*←Λ*-{Tj}

28) end while

31) 依次選擇任務(wù)Tj∈Λ

32) fori←1toNSCdo

33) ifSi∈Γj

35) elseeij←

36) end if

37) end for

38) ifeij是{eik|1

39)oij←1

40) end if

41) Λ←Λ-{Tj}

42) end while

43) returnO

其中，Φ表示所有無沖突任務(wù)的集合；Γi表示所有在衛(wèi)星上Si上無沖突的任務(wù)集合；Λ*表示所有尚未分配的沖突任務(wù)構(gòu)成的集合；Λ表示所有尚未分配的無沖突任務(wù)構(gòu)成的集合.

3.2 算法分析

CIBPS算法的時間復(fù)雜度主要由三個部分構(gòu)成(N表示任務(wù)規(guī)模，K表示衛(wèi)星規(guī)模)：1) 劃分沖突任務(wù)和非沖突任務(wù)的復(fù)雜度為O(K·N2).其中，計算一個任務(wù)在一顆衛(wèi)星上的最長連續(xù)可用無碰撞時長的時間復(fù)雜度為O(N)，則計算N個任務(wù)在K顆衛(wèi)星上的最長連續(xù)可用無碰撞時長的時間復(fù)雜度為O(K·N2)； 2) 沖突任務(wù)調(diào)度的復(fù)雜度為O(K·N3).其中，對于單個任務(wù)在某一衛(wèi)星資源上計算成像概率而言，計算潛在沖突系數(shù)的復(fù)雜度為O(N)，采用Dijkstra算法構(gòu)造有向無環(huán)圖并計算其最短單源路徑得到實際沖突系數(shù)的復(fù)雜度是O(N2)，計算能量系數(shù)的復(fù)雜度為O(N)，故復(fù)雜度為O(N)+O(N2)+O(N)=O(N2)，對于任務(wù)規(guī)模為N，衛(wèi)星規(guī)模為K的沖突任務(wù)調(diào)度問題計算時間復(fù)雜度為O(K·N3)； 3) 對于無沖突任務(wù)，只需計算其能量系數(shù)，復(fù)雜度為O(K·N2).因此，CIBPS算法的總時間復(fù)雜度為O(K·N2)+O(K·N3)+O(K·N2)=O(K·N3).

在開始調(diào)度時，pij較大，rij較小，此時cij的計算主要取決于任務(wù)間的潛在沖突.隨著任務(wù)分配的進行，每一個任務(wù)被分配到衛(wèi)星資源后，該任務(wù)對其他任務(wù)的潛在沖突就會在隨后的調(diào)度計算中被剔除，同時，該任務(wù)會被添加到該衛(wèi)星資源的有向無環(huán)資源圖中，隨著衛(wèi)星資源的已分配任務(wù)信息增多，pij減小，rij增大，此時cij的計算主要取決于任務(wù)間的實際沖突.通過這種計算沖突系數(shù)分配衛(wèi)星資源的方式，可以減少多個任務(wù)在同一段時間爭用同一個衛(wèi)星資源的情況，以達到均衡合理分配資源的目的.

4 實驗與仿真

4.1 實驗設(shè)置

本文實驗運行在4 GB內(nèi)存的Inter Core i5 3.20 GHz 單核CPU上，衛(wèi)星和任務(wù)目標點之間的可見時間窗口通過Satellite Tool Kit 11.0軟件獲取，算法實現(xiàn)語言為Matlab.由于在多星觀測調(diào)度領(lǐng)域，尚無公開的標準數(shù)據(jù)集[19].為了全面的分析CIBPS的性能，本文設(shè)計了三組任務(wù)場景，分別對應(yīng)不同的任務(wù)分布情況，任務(wù)的具體生成規(guī)則如表2所示.

4.2 實驗結(jié)果

本文將CIBPS與SA算法進行對比,其中，SA算法被Globus等人在實驗中證明在各種典型的對地觀測衛(wèi)星調(diào)度算法中具有最好的性能[20].為了評估算法的性能，需要完成單星自主調(diào)度得到最終的調(diào)度結(jié)果.本實驗中單星調(diào)度算法采用了基于權(quán)重的貪婪算法[12].SA算法的終止條件設(shè)定為最優(yōu)解在100次迭代中未曾更新.對于每個實驗用例，CIBPS與SA都運行了20次.表3給出了3種分布下15個實驗用例的計算結(jié)果和CPU運行時間.

表2 任務(wù)參數(shù)生成規(guī)則Tab.2 Generation rule of tasks

表3 實驗結(jié)果Tab.3 Experimental result

可以通過對表3的分析比較CIBPS和SA之間的性能差異.從實驗結(jié)果中可以看出，隨著任務(wù)數(shù)量的增加，任務(wù)調(diào)度率逐漸下降，同時，CIBPS的任務(wù)調(diào)度率在大多數(shù)情況下都高于SA的.用例1中，SA可以和CIBPS實現(xiàn)相同的調(diào)度結(jié)果，這是因為此時的衛(wèi)星資源相對充足，但SA花費的時間是CIBPS數(shù)百倍.當任務(wù)數(shù)量增加時，衛(wèi)星資源相對稀缺，任務(wù)的可用時間窗口間競爭加劇，此時CIBPS是一種更好的資源分配算法，能夠緩解這種競爭，遏制任務(wù)完成率的急速下降.因此，隨著任務(wù)規(guī)模的增加，CIBPS的優(yōu)勢更加明顯.

在場景a(用例1～3)中，當任務(wù)數(shù)量較少時，SA的性能接近CIBPS，盡管搜索需要更多時間，SA仍無法找到更好的解決方案，隨著任務(wù)數(shù)量的上升，CIBPS和SA完成率均呈下降趨勢，但CIBPS相較與SA仍有10%以上的提升.場景b(用例4～6)下的結(jié)果有些不同：當任務(wù)數(shù)量較小時，CIBPS和SA之間的性能差異也較明顯，隨著任務(wù)規(guī)模的增長，SA的完成率快速下降，CIBPS的完成率緩慢下降，仍比SA提高了約20%.場景c(用例7～15)的任務(wù)目標點分布考慮實際的對地觀測任務(wù)包含定期的巡航拍攝和突發(fā)的集中觀測，結(jié)合均勻分布和集中分布的特征，增加了更多的任務(wù).該種場景下，CIBPS和SA的任務(wù)完成率介于場景a和場景b之間，性能提升比也是如此.因此，三種任務(wù)目標點分布的場景按資源短缺程度有如下排序：b>c>a，而場景b下，CIBPS的性能提升最大，由此可以得出結(jié)論，CIBPS更擅長在衛(wèi)星資源緊缺和任務(wù)可用時間窗口沖突大的情況下處理多星預(yù)調(diào)度問題.

從CPU運行時間的角度來看，當任務(wù)規(guī)模較小時，CIBPS的計算時間明顯短于SA.隨著任務(wù)數(shù)量的增加，CIBPS的計算時間以三次量級增加，這驗證了算法分析中對于算法復(fù)雜度的推算.綜上所述，CIBPS能夠完成在多項式時間內(nèi)高效解決多星預(yù)調(diào)度問題的目標.

圖3 a組實驗結(jié)果盒圖Fig.3 Box plot for Group(a)

圖4 b組實驗結(jié)果盒圖Fig.4 Box plot for Group(b)

圖5 c組實驗結(jié)果盒圖Fig.5 Box plot for Group(c)

圖3～圖5是通過箱形圖展示所有解的分布，可以看出，在場景a(用例1～3)中，在解空間較小時，CIBPS和SA每次都可以找到到最優(yōu)解，但是隨著任務(wù)數(shù)量的增長，CIBPS和SA在每次運行后的解可能有所區(qū)別，而即使CIBPS算法的最差解也比SA的最佳解提升5%以上，SA算法解的四分位數(shù)范圍和總范圍都是CIPBS的2倍以上，說明CIPBS算法的解更加集中，即CIBPS算法可以獲得更有效的穩(wěn)定解決方案.在場景b(用例4～6)中，即使解空間相比于場景a更小，即使此時的SA的解范圍更加集中，CIBPS的性能提升反而更加明顯，原因是此時任務(wù)目標點的分布更加集中，任務(wù)時間窗口間的沖突更大，CIBPS通過計算成像概率進行預(yù)測，化解任務(wù)間的沖突，可以取得更好的效果.在場景c(用例7～15)中，CIBPS和SA的解分布接近場景a，CIBPS的解非常穩(wěn)定，四分位數(shù)范圍和總范圍都明顯小于SA.

總的來說，CIBPS幾乎在每種情況下都能找到更好的任務(wù)調(diào)度解.由此可以得出結(jié)論，CIBPS算法在性能方面明顯優(yōu)于SA算法，CIBPS算法在有效性和穩(wěn)定性方面的優(yōu)勢是顯而易見的.

5 結(jié) 論

本文深入研究了多衛(wèi)星對地觀測任務(wù)調(diào)度模型和調(diào)度算法，對多星觀測調(diào)度問題進行約束性分析，確定了基本假設(shè)和約束條件，針對現(xiàn)有的確定性調(diào)度算法的性能退化、搜索算法易陷入局部最優(yōu)、其它啟發(fā)式算法規(guī)則制定不全面的問題，根據(jù)觀測衛(wèi)星的實際情況，提出了CIPBS算法，使規(guī)劃結(jié)果盡可能接近最優(yōu)解.在三種不同的任務(wù)分布下進行實驗，通過調(diào)度結(jié)過分析對比表明本文提出的算法適應(yīng)于多星預(yù)調(diào)度模型求解，能穩(wěn)定的找到更好的解.但是本文還是存在一些不足，在對地觀測任務(wù)完成后的衛(wèi)星數(shù)據(jù)下傳時間窗口分配未進行優(yōu)化，如何結(jié)合CIBPS算法的特點設(shè)計觀測衛(wèi)星數(shù)據(jù)下傳算法也是今后研究的方向.