張紅旗

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

0 引言

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

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

1 星地面站調(diào)度問(wèn)題模型

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

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

1.1 參數(shù)定義

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

1.2 調(diào)度模型

模型說(shuō)明:

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

2 貪婪算法的引入

2.1 貪婪算法基本思想

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

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

令活動(dòng)按照結(jié)束時(shí)間的先后順序排序?yàn)?

貪婪算法的運(yùn)算流程為:

式中,集合S為每一次選擇的活動(dòng)的集合。運(yùn)算結(jié)束時(shí)表示一個(gè)規(guī)劃結(jié)果,S中的元素表示所有規(guī)劃的任務(wù);j為最新加入集合S的活動(dòng)。

2.2 貪婪算法在地面站資源調(diào)度中的應(yīng)用

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

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

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

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

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

3 實(shí)驗(yàn)仿真和結(jié)果分析

假設(shè)有5個(gè)任務(wù),2個(gè)地面站S1、S2,地面站內(nèi)的資源如表1所示,并且假設(shè)各資源之間均滿足可連接關(guān)系。任務(wù)時(shí)間及與地面站可見(jiàn)時(shí)間如表2和表3所示。

表1 地面站資源描述

表2 任務(wù)時(shí)間

表3 可視時(shí)間段

為了驗(yàn)證算法的有效性,設(shè)計(jì)和實(shí)現(xiàn)了一個(gè)基于貪婪算法的衛(wèi)星資源調(diào)度原型系統(tǒng),最終實(shí)驗(yàn)結(jié)果如表4所示。

表4 規(guī)劃結(jié)果

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

4 結(jié)束語(yǔ)

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

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

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

[3]邢文訓(xùn),謝金星.現(xiàn)代優(yōu)化計(jì)算方法[M].北京:清華大學(xué)出版社,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)星調(diào)度方法研究[J].計(jì)算機(jī)仿真,2008,2(25):37-40.