基于貪婪算法的遙感地面站任務(wù)調(diào)度技術(shù)

張 超

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

0 引言

隨著航天技術(shù)的發(fā)展,對地遙感觀測衛(wèi)星已越來越廣泛地滲透到人類生產(chǎn)和生活的各個領(lǐng)域,并發(fā)揮著重要的作用。在衛(wèi)星整個觀測過程中,衛(wèi)星只有將所偵察的信息數(shù)據(jù)遞交至用戶手中,才能最終實現(xiàn)信息價值。遙感地面接收站任務(wù)調(diào)度問題的目標(biāo)就是依據(jù)分布在多處的有限的遙感地面接收站資源及其能力特點,最大限度地規(guī)劃安排完成最多數(shù)量的數(shù)據(jù)接收任務(wù),以獲得最大效果的數(shù)據(jù)應(yīng)用目標(biāo)。但是由于衛(wèi)星數(shù)量和地面站接收系統(tǒng)的位置、數(shù)量對應(yīng)關(guān)系是多對多的關(guān)系,單套接收系統(tǒng)在同一時間只能接收單一衛(wèi)星的遙感數(shù)據(jù)下傳,在衛(wèi)星數(shù)量不斷增加、接收系統(tǒng)數(shù)量有限的情況下,就出現(xiàn)所謂“接收任務(wù)沖突”。因此如何高效、高速地制訂衛(wèi)星數(shù)據(jù)接收計劃,就成為一個待解決的問題。

1 數(shù)據(jù)接收任務(wù)調(diào)度模型

衛(wèi)星與地面站之間進行數(shù)據(jù)傳輸必須滿足2個基本條件:一是衛(wèi)星與地面站之間存在可見時間窗口;二是衛(wèi)星數(shù)據(jù)傳輸?shù)念l段、通道數(shù)量、調(diào)制方式、碼速率、信號功率與地面站的跟蹤接收系統(tǒng)相匹配。所以調(diào)度模型轉(zhuǎn)化為綜合考慮時間窗口約束、地面站天線轉(zhuǎn)換時間以及接收設(shè)備資源約束的條件下,使得完成任務(wù)的接收時間之和最大。

1.1 數(shù)據(jù)接收參數(shù)定義

假設(shè)一個遙感地面站,對于 n個要完成的任務(wù),定義場景時間:SchSpans表示調(diào)度開始時間,SchSpane表示調(diào)度結(jié)束時間,SchSpan=[SchSpans,SchSpane]也稱為調(diào)度時間區(qū)間?？梢姇r間窗口:twi=[twsi,twei]表示任務(wù)與遙感地面站之間在場景時間內(nèi)的第i個可見時間窗口,0≤i≤n,開始時間和結(jié)束時間分別為twsr和twer;任務(wù)完成需要的持續(xù)時間DT={dt1,dt2,…dtn},任務(wù)i的開始時間為si,結(jié)束時間為 ei,所以 dti=ei-si;遙感地面站天線轉(zhuǎn)換時間表示為tr;任務(wù)的最小數(shù)據(jù)接收限制時間為Limtime。

1.2 數(shù)據(jù)接收調(diào)度目標(biāo)

遙感數(shù)據(jù)接收調(diào)度就是在滿足一定的約束條件下,對衛(wèi)星數(shù)據(jù)接收任務(wù)集中進行調(diào)度,以實現(xiàn)一定的調(diào)度目標(biāo)[2]。通過遙感數(shù)據(jù)接收任務(wù)調(diào)度背景分析,確定了接收任務(wù)目標(biāo)安排的時間滿足度盡可能大是調(diào)度的主要目標(biāo)。

1.3 數(shù)據(jù)接收約束條件

考慮基本資源和時間約束:衛(wèi)星數(shù)據(jù)下傳的頻段、通道數(shù)量、調(diào)制方式、碼速率、信號功率與遙感地面站的跟蹤接收系統(tǒng)必須相匹配;地面站與衛(wèi)星必須相互可見,地面站天線才能對衛(wèi)星進行捕獲和跟蹤;單數(shù)據(jù)接收任務(wù)成功調(diào)度必須大于最小接收時間;衛(wèi)星數(shù)據(jù)接收必須在可用時間窗口內(nèi)進行。

1.4 遙感數(shù)據(jù)接收調(diào)度數(shù)學(xué)模型

模型說明:式(1)為目標(biāo)函數(shù)表示完成任務(wù)的優(yōu)先級之和;約束條件(2)表示天線轉(zhuǎn)換時間與任務(wù)的接收執(zhí)行時間總和不能超過時間窗口的總長度;約束條件(3)表示任務(wù)的接收執(zhí)行時間總和不能小于最小數(shù)據(jù)接收限制時間;約束條件(4)表示任務(wù)必須在可用時間窗之內(nèi)進行數(shù)據(jù)接收:約束條件(5)說明任務(wù)的開始和結(jié)束時間必須在規(guī)劃時間段范圍之內(nèi)。

2 數(shù)據(jù)接收任務(wù)調(diào)度算法

2.1 貪婪算法

貪婪算法是一種解決最優(yōu)化問題的近似方法。在貪婪算法中采用逐步構(gòu)造最優(yōu)解的方法,即在每個階段都做出一個看上去最優(yōu)的決策(在一定的標(biāo)準(zhǔn)下)。決策一旦做出,就不可再更改。做出貪婪決策的依據(jù)稱為貪婪準(zhǔn)則,是決策的標(biāo)準(zhǔn),在求解的每一步,依據(jù)此標(biāo)準(zhǔn)對變量進行賦值。貪婪算法的關(guān)鍵就在于貪婪準(zhǔn)則的設(shè)定[4]。

貪婪算法的優(yōu)點在于簡單易行,不包括復(fù)雜的控制機制,因此搜索速度比較快,但算法容易很快終止于一個局部最小解[1,4]。

2.2 貪婪隨機插入算法設(shè)計

為了降低衛(wèi)星數(shù)據(jù)接收調(diào)度算法復(fù)雜性,采用了分治法思想。按照時間映射關(guān)系與接收時段相關(guān)性(接收時段重疊,單站多星跟蹤時段間隔時間小于天線切換時間等)將所有的接收任務(wù)與接收時段分組,分為多組可能沖突任務(wù)組。問題分解后減小了算法搜索的問題規(guī)模,大大減少了對非可行解的搜索,并且方便進行分布式并行處理。

為了解決貪婪算法容易陷入局部最小解的缺點,通過加入隨機策略來彌補貪婪算法的不足,可增加解的搜索空間以優(yōu)化搜索結(jié)果。同時采用隨機化后,可以幫助改善資源使用的情況,相對達到資源均衡使用狀態(tài),可以生成不同的任務(wù)安排方案,供用戶選擇。

最終采用分治法思想,基于貪婪算法加入隨機化,提出了貪婪隨機插入法,貪婪隨機插入法流程如圖1所示。

圖1 貪婪隨機插入法流程

2.3 實驗仿真及結(jié)果分析

設(shè)計場景規(guī)模為8顆衛(wèi)星3個地面站,數(shù)據(jù)接收任務(wù)81個,其中10個為緊急任務(wù)。衛(wèi)星軌道和地面站數(shù)據(jù)依據(jù)AGI公司在2005年6月發(fā)布的衛(wèi)星軌道和地面站數(shù)據(jù)庫,所有場景均利用STK 7.0進行設(shè)計。為了驗證算法的有效性,設(shè)計和實現(xiàn)了一個基于貪婪隨機插入算法的遙感數(shù)據(jù)接收調(diào)度原型系統(tǒng),最終實驗結(jié)果如表1所示。

表1 實驗結(jié)果數(shù)據(jù)

算法運行結(jié)果對比顯示,對于貪婪隨機插入法保證了盡可能多的緊急任務(wù)被安排,提高了近6.7%。并且第2次、第4次和第6次試驗都產(chǎn)生了優(yōu)于貪婪算法的結(jié)果。說明加入隨機化以后,避免了貪婪算法過早地陷入局部最小解的吸引域,改善了算法性能,產(chǎn)生更好的規(guī)劃方案。同時對于貪婪隨機插入法因為加入了隨機性,也增加了實驗結(jié)果的不穩(wěn)定性,起伏波動較大,所以還需智能搜索算法的進一步優(yōu)化。

3 結(jié)束語

遙感地面接收站任務(wù)規(guī)劃問題是一個十分復(fù)雜的組合優(yōu)化問題。通過分析問題實際約束和問題調(diào)度目標(biāo),建立了遙感地面站任務(wù)調(diào)度問題模型。在此基礎(chǔ)上根據(jù)貪婪算法思想,基于貪婪算法采用分治法思想和隨機化思想,編程實現(xiàn)了基本的應(yīng)用模型,并將其應(yīng)用于遙感數(shù)據(jù)接收方案的制定,其所得結(jié)果滿足遙感數(shù)據(jù)接收多目標(biāo)規(guī)劃需求,能使地面接收資源得到充分的利用,很好地解決了遙感數(shù)據(jù)接收方案的優(yōu)化問題。

[1]郭玉華,李 軍,趙 珂,等.多星聯(lián)合任務(wù)規(guī)劃中的啟發(fā)式求解方法研究[J].宇航學(xué)報,2009,30(2):652-658.

[2]李 軍,王 鈞,陳 健.基于多目標(biāo)遺傳算法的衛(wèi)星成像任務(wù)調(diào)度技術(shù)[J].系統(tǒng)工程與電子技術(shù),2007,29(7):1164-1168.

[3]金 光,武小悅,高衛(wèi)斌.衛(wèi)星地面站資源優(yōu)化調(diào)度模型及其啟發(fā)式算法[J].系統(tǒng)工程和電子技術(shù),2004,26(12):1839-1843.

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

[5]趙靜文.遙感衛(wèi)星地面接收系統(tǒng)總體設(shè)計探討[J].現(xiàn)代雷達,2004,26(7):14-16.