基于沖突成像概率的多星任務預調(diào)度算法

徐明明，王俊峰

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

1 引 言

對地觀測是衛(wèi)星一個非常重要的應用，據(jù)聯(lián)合國外太空事務局(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)星資源仍然緊缺，為了緩解這一問題，大量研究者針對對地觀測任務調(diào)度模型和算法進行不斷優(yōu)化和改進，力爭在滿足任務和資源約束的條件下為每個任務更加合理地分配衛(wèi)星資源和決定任務的執(zhí)行時間段.

對地觀測任務調(diào)度可分為單星調(diào)度和多星調(diào)度.早期的研究大多針對單顆衛(wèi)星資源進行調(diào)度，隨著觀測任務日益繁重，衛(wèi)星數(shù)量也不斷上升，如果采用單星調(diào)度，調(diào)度系統(tǒng)內(nèi)缺乏通用性，衛(wèi)星的觀測能力得不到充分利用.如何綜合利用衛(wèi)星網(wǎng)絡，高效的整合衛(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ā)式算法基于先驗信息制定任務調(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)和分配觀測任務，包括最高權(quán)重優(yōu)先分配算法和禁忌列表模擬退火算法.該類算法規(guī)則較為復雜，設計思路的偏離將造成性能與最優(yōu)解相去甚大.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

完成預調(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èi)星的執(zhí)行能力，σi代表系統(tǒng)的超額分配率.

(3)

(4)

(5)

(6)

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

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

S.t. (3)～(6)

(7)

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

3.1 算法描述

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

圖1 求解策略Fig.1 Solving stategy

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

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

(8)

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

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

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

(9)

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

(10)

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

rij=Gi_longestpath+pj-Gi'_longestpath

(11)

為了系統(tǒng)負載均衡和滿足能量約束，要考慮完成衛(wèi)星分配到的總?cè)蝿盏哪芰肯模识x能量系數(shù)的計算如下.

(12)

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

Algorithm1 Collision Probability-Based Schedule(CIPBS)

1) 生成場景(S,T)

2) 初始化參數(shù)

3) 預處理，計算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) 隨機選擇任務Tj∈Λ*

14) fori←1toNSCdo

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

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

18) 將任務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) 依次選擇任務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

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

3.2 算法分析

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

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

4 實驗與仿真

4.1 實驗設置

本文實驗運行在4 GB內(nèi)存的Inter Core i5 3.20 GHz 單核CPU上，衛(wèi)星和任務目標點之間的可見時間窗口通過Satellite Tool Kit 11.0軟件獲取，算法實現(xiàn)語言為Matlab.由于在多星觀測調(diào)度領域，尚無公開的標準數(shù)據(jù)集[19].為了全面的分析CIBPS的性能，本文設計了三組任務場景，分別對應不同的任務分布情況，任務的具體生成規(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算法的終止條件設定為最優(yōu)解在100次迭代中未曾更新.對于每個實驗用例，CIBPS與SA都運行了20次.表3給出了3種分布下15個實驗用例的計算結(jié)果和CPU運行時間.

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

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

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

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

從CPU運行時間的角度來看，當任務規(guī)模較小時，CIBPS的計算時間明顯短于SA.隨著任務數(shù)量的增加，CIBPS的計算時間以三次量級增加，這驗證了算法分析中對于算法復雜度的推算.綜上所述，CIBPS能夠完成在多項式時間內(nèi)高效解決多星預調(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)解，但是隨著任務數(shù)量的增長，CIBPS和SA在每次運行后的解可能有所區(qū)別，而即使CIBPS算法的最差解也比SA的最佳解提升5%以上，SA算法解的四分位數(shù)范圍和總范圍都是CIPBS的2倍以上，說明CIPBS算法的解更加集中，即CIBPS算法可以獲得更有效的穩(wěn)定解決方案.在場景b(用例4～6)中，即使解空間相比于場景a更小，即使此時的SA的解范圍更加集中，CIBPS的性能提升反而更加明顯，原因是此時任務目標點的分布更加集中，任務時間窗口間的沖突更大，CIBPS通過計算成像概率進行預測，化解任務間的沖突，可以取得更好的效果.在場景c(用例7～15)中，CIBPS和SA的解分布接近場景a，CIBPS的解非常穩(wěn)定，四分位數(shù)范圍和總范圍都明顯小于SA.

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

5 結(jié) 論

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