基于貪婪算法的衛(wèi)星地面站資源調度方法

張紅旗

(中國電子科技集團公司第五十四研究所,河北石家莊050081)

0 引言

隨著航天科技的發(fā)展,通過衛(wèi)星獲取的信息已經越來越廣泛地應用于人類生產、生活的方方面面。但由于地面站應用系統(tǒng)的地面設備能力的限制,在一定條件下能為衛(wèi)星提供的服務是有限的。在衛(wèi)星數量較少的情況下,資源沖突率并不高,而當衛(wèi)星數量較多時,資源有限的矛盾變得非常突出,這意味著大量的通過衛(wèi)星獲取的數據我們無法得到。鑒于地面站資源的高成本,如何充分、合理地對地面站內的各種資源進行分配,充分發(fā)揮其使用效益,最大限度地滿足衛(wèi)星任務需求,是一個亟待需要解決的問題[1]。

衛(wèi)星地面站系統(tǒng)資源調度問題是一個基于約束的資源優(yōu)化問題[2],即將有限資源分配到不同的任務時間段上,其目標是為了滿足更多衛(wèi)星的數據傳輸請求,以獲得盡量多的觀測數據。衛(wèi)星地面站系統(tǒng)在執(zhí)行數據接收任務時首先要滿足與進行數據傳輸的衛(wèi)星之間的數傳任務時間應在地面站與衛(wèi)星的可見時間窗口之內。涉及的地面站資源包括天線、信道和記錄設備等,各類資源之間的連接約束關系必須滿足。

1 星地面站調度問題模型

衛(wèi)星地面站調度模型的建立主要考慮3個方面的問題:①決策變量。決策變量是模型中的變量子集,如果決策變量中的變量取值已知就可以推導出整個問題的最終解;②時間約束。任務的時間約束要求任務必須在規(guī)定的時間段內完成;③資源約束。資源相容性約束表示一個時間窗口不能同時分配給2個以上衛(wèi)星任務使用,資源容量約束表示表示的是一旦任務被規(guī)劃,則必須分配給一定的資源,包括地面站的各種資源及可視時間窗口,并且分配的數量不能超過地面站資源的能力。

實際運用中,在為衛(wèi)星與地面站之間的數據傳輸任務分配資源時必須滿足2個基本條件:①數傳任務必須在衛(wèi)星與地面站之間的可見時間窗口內執(zhí)行;②所需的天線、信道和記錄設備等資源在該時間段內可用。另外,模型中還考慮了天線的轉換時間約束以及任務對于各種資源數量上的要求。

1.1 參數定義

對于一個地面站,假設存在 n個要完成的任務,共有m個時間窗口,用集合 TW={tw1,tw2,…twm}表示,對于第r個窗口的開始時間和結束時間分別為twsr和twer;任務i的開始時間為sti,結束時間為 eti,任務的持續(xù)時間 DT={dt1,dt2,…dtn};天線資源集合A={a1,a2,…},相應的天線轉換時間表示為tr1,tr2,…,信道資源集合 C={c1,c2,…},記錄器資源集合R={r1,r2,…};定義布爾變量Xi,僅當任務i能夠完成時取值1,否則取值0;布爾變量axij,僅當任務j由天線ai完成時取值1,否則取值0;布爾變量cxij,僅當任務 j由信道ci完成時取值1,否則取值0;布爾變量rxij,僅當任務j由記錄設備ri完成時取值1,否則取值0。

1.2 調度模型

模型說明:

式(1)為目標函數,表示所有已安排任務的優(yōu)先級與任務時間的乘積之和,其中 pk為任務的優(yōu)先級;式(2)表示任務必須在選定的可用時間窗之內進行;式(3)表示任意時間窗口內安排的任務的執(zhí)行時間與天線轉換時間總和不能超過該時間窗口的長度,其中Ai表示時間窗口i安排的任務集合;式(4)說明任一天線任意時刻最多只能執(zhí)行一個任務;式(5)說明任一信道任意時刻最多只能執(zhí)行一個任務;式(6)說明任一記錄設備任意時刻最多只能執(zhí)行一個任務。

2 貪婪算法的引入

2.1 貪婪算法基本思想

貪婪算法(Greedy Algorithm)是一種解決最優(yōu)化問題的近似方法。采用貪婪算法對前述模型進行求解,在貪婪算法中采用逐步構造最優(yōu)解的方法,即在每個階段,都做出一個看上去最優(yōu)的決策(在一定的標準下)。決策一旦做出,就不可再更改。做出貪婪決策的依據稱為貪婪準則(Greedy Criterion),也稱貪婪因子。貪婪準則事實上就是決策的依據和標準,即在求解的每一步,依據何種標準對變量進行賦值。貪婪算法的關鍵就在于貪婪準則的設定,貪婪搜索算法的成功絕大部分決定于貪婪因子的制定,即在明確求解目標問題的前提下制定使得每一步都得到最優(yōu)的解的準則。這種貪婪準則是啟發(fā)式選擇下一個變量并且給予這個變量賦值的依據[5]。

假設有n項活動和一種資源,資源在每一個時間點上能由一項活動使用。設活動集為T={1,2,…,n}。任意一活動 i都有開始時間sti和結束時間eti,sti＜eti。如果活動 i和j的時間段[sti,eti]和[stj,etj]不重疊,那么活動i和j就是相容的。通過貪婪算法能夠求得在給定時間段內,最大的相容活動集合(即貪婪準則為:max length[S],最大化解集中的活動數,其中S?T,表示在某時間段內的規(guī)劃結果集)。算法過程如下[2]:

令活動按照結束時間的先后順序排序為:

貪婪算法的運算流程為:

式中,集合S為每一次選擇的活動的集合。運算結束時表示一個規(guī)劃結果,S中的元素表示所有規(guī)劃的任務;j為最新加入集合S的活動。

2.2 貪婪算法在地面站資源調度中的應用

貪婪算法的特點體現在最大可能地利用每一次機會,在規(guī)劃的每一步,都對地面站的資源給予最充分的利用。其基本思路是:首先按照優(yōu)先級高低對任務排序,然后從中依次選取任務嘗試為其安排資源,對于每一個滿足與地面站之間可視時間窗口約束的任務,在為其選擇資源時,為了能夠最大化目標函數的增量,在優(yōu)先級已定的前提下,就需要使得安排任務的時間盡量長。策略首先是將天線按照對于該任務可用時間的長度由長到短進行排序,也就是說可用時間較長的天線將被優(yōu)先選擇,然后從天線序列中依次選取作為備選天線,之后依次選擇與之滿足匹配關系的可用時間盡量長的信道及記錄設備并調整任務的執(zhí)行時間,當選出的天線、信道和記錄設備數達到了任務要求的數量時,記下該組資源下任務的執(zhí)行時間,計算目標函數值,當所有天線均比較完畢后,鎖定使得目標函數最大的那組資源,并將其安排給該任務。具體過程如下:

步驟1:對于 n個任務按照任務優(yōu)先級由高到低的規(guī)則對其排序;

步驟2:從待規(guī)劃任務序列中依次選取任務 i作為待規(guī)劃任務,并從滿足時間窗口約束的天線、信道和記錄器集中選取滿足連接關系的資源組合,計算目標函數的值;

步驟3:對于當前待規(guī)劃任務搜索能夠最大限度提高目標函數值的滿足約束的資源組合,假設選定的天線為a1,信道c1,c2,c3,記錄器 r1,則令ax1i,cx1i,cx2i,cx3i,rx1i均等于1,即將這組資源安排給該任務;

步驟4:判斷任務序列是否已遍歷結束,判斷結果為是,則返回已安排任務及為其安排的資源情況,即所得解;否則轉步驟2。

3 實驗仿真和結果分析

假設有5個任務,2個地面站S1、S2,地面站內的資源如表1所示,并且假設各資源之間均滿足可連接關系。任務時間及與地面站可見時間如表2和表3所示。

表1 地面站資源描述

表2 任務時間

表3 可視時間段

為了驗證算法的有效性,設計和實現了一個基于貪婪算法的衛(wèi)星資源調度原型系統(tǒng),最終實驗結果如表4所示。

表4 規(guī)劃結果

在以上實驗中每個任務需安排的天線數為1、信道數為2、記錄設備數為2,從任務時間與各站可視時間來看,地面站S1滿足全部5個任務的時間窗口約束,而地面站S2對于任務3和任務4不能完整接收,其他3個任務的時間則均在可視時間窗口之內。又發(fā)現每個任務均需要2個信道,而2個地面站內的信道數分別為3和4,這就意味著5個任務無法全部安排,必然存在某些任務沒有資源可用。分析計算結果也可以看出,信道資源沖突最嚴重,天線和記錄設備則相對充足;按照貪婪規(guī)則,優(yōu)先級高的任務2、3均被安排了可用資源,對于具有同一優(yōu)先級的任務4與任務5,前者任務時間較長,安排任務4可以使得目標函數值更大,于是選擇了任務4,并將其由兩站聯(lián)合接收,即為聯(lián)合接收任務;從任務4規(guī)劃的時間段可以看出聯(lián)合接收任務在時間上要有一定的重疊時間。

4 結束語

衛(wèi)星地面站系統(tǒng)任務規(guī)劃問題是一個非常復雜的優(yōu)化問題,針對衛(wèi)星地面站系統(tǒng)資源規(guī)劃問題提出了一種貪婪算法。仿真結果表明該算法為問題的解決提供了一種有效的求解思路和方法。實際應用中的衛(wèi)星地面站系統(tǒng)的資源規(guī)劃包含的約束條件更為復雜,如衛(wèi)星與各種資源的匹配約束、任務對資源特殊性能的要求約束等,這些都有待于更加深入地探索和研究。

[1]劉 洋,陳英武,譚躍進.衛(wèi)星地面站系統(tǒng)任務調度的動態(tài)規(guī)劃方法[J].中國空間科學技術,2005,25(1):47-50.

[2]劉 洋,陳英武,譚躍進.基于貪婪算法的衛(wèi)星地面站系統(tǒng)任務規(guī)劃方法[J].系統(tǒng)工程與電子技術,2003,25(10):1239-1241.

[3]邢文訓,謝金星.現代優(yōu)化計算方法[M].北京:清華大學出版社,2005.

[4]R OPKE S,PISINGER D.An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problemwith Time Windows[J].Transportation Science,2006(40):455-472.

[5]盧 盼,徐培德.基于貪婪算法成像偵察衛(wèi)星調度方法研究[J].計算機仿真,2008,2(25):37-40.