基于粒子群算法的衛(wèi)星任務地面站資源調度方法*

樊慧晶，章文毅，田妙苗，馬廣彬，程博

(1 中國科學院空天信息創(chuàng)新研究院，北京 100094；2 中國科學院大學，北京 100049)

衛(wèi)星地面站資源調度問題是指根據衛(wèi)星的任務應用需求，在有限的時間范圍和特定的約束條件下，為衛(wèi)星的數傳、測控等任務配置相應的地面站資源(如天線、記錄器等)，得到滿足衛(wèi)星任務需求的資源分配調度方案。隨著航天技術的發(fā)展，衛(wèi)星任務數量也在急劇增多。巨大的任務量需要相應規(guī)模的衛(wèi)星數傳和測控運行體系，還需要合理地分配與調度地面站的設備資源，這樣才能更好地完成衛(wèi)星任務。其中任務運行設備的增加和改進受到經費、投入周期、工業(yè)技術等實際因素的制約，因此科學地安排和配置地面資源設備，對于地面站資源調度問題具有重要意義。

衛(wèi)星任務的資源調度問題具有資源類型多、約束復雜、規(guī)模龐大、求解計算量大、評價體系復雜等特點[1]，國內外許多學者對該問題進行過研究。經典的模型主要有約束滿足模型(constraint satisfaction problem，CSP)[2]、 0-1規(guī)劃模型[3]、Petri網[4]、基于規(guī)則的調度模型[5]、混合整數規(guī)劃模型[6]等；常用的調度方法主要有遺傳算法及其改進算法[7]、啟發(fā)式算法[6]等。目前已有的研究大多是根據不同衛(wèi)星任務類型(如數傳任務、測控任務)分別進行規(guī)劃，隨著運行體系的升級和發(fā)展，地面站資源(如天線)也不再是具有單一測控能力或單一數傳能力的設備，而是逐漸升級為同時具有測控能力和數傳能力的設備[8-9]，因此可以考慮將不同類型的任務進行一體化規(guī)劃，避免不同類型任務之間的資源沖突，統籌規(guī)劃，共用資源，提高任務的完成率。

從運籌學的角度來講，衛(wèi)星地面站資源調度問題是一個具有優(yōu)化目標、約束條件的優(yōu)化問題。粒子群算法通過追蹤粒子的個體最優(yōu)和全局最優(yōu)來搜索最優(yōu)解[10]，是一種參數簡單、功能強大的群智能算法，目前已經廣泛應用于優(yōu)化問題[11-12]。最初粒子群算法用于解決連續(xù)的非整數問題，但是現實世界有很多問題是離散的整數問題，因此Kennedy和Eberhart[13]提出一種適用于離散問題的粒子群算法，可用于解決組合優(yōu)化問題。如果將地面站的資源配置看作一個組合問題，則對于一般規(guī)模的調度場景，若使用窮舉法，其產生的調度方案的數量規(guī)模是極其龐大的。粒子群算法的尋優(yōu)機制可以使大規(guī)模的問題更快收斂至令人滿意的解，因此本文利用粒子群算法對衛(wèi)星任務的地面站資源調度問題進行求解。

1 地面站資源一體化調度場景

當衛(wèi)星進入地面站接收圈時，稱衛(wèi)星在對于地面站的可視弧段內，此時衛(wèi)星與地面站相互可見，可以相互通信。衛(wèi)星將獲取到的數據下傳到地面站的過程是數傳[14]，數傳過程中，地面站天線接收衛(wèi)星數據，并由記錄器記錄；衛(wèi)星測控是指通過測控設備對衛(wèi)星飛行的軌道、姿態(tài)及衛(wèi)星載荷進行測量、跟蹤和控制[15]，以保障衛(wèi)星任務的完成，這一過程需要地面站天線向衛(wèi)星發(fā)射信號，對衛(wèi)星的有效載荷提出指令。圖1描述了衛(wèi)星數傳任務和測控任務的過程。

圖1 數傳、測控過程及資源示意圖

資源調度問題中，衛(wèi)星的數傳任務主要涉及的地面站資源有：地面站天線、信道與記錄器。其中，信道是指數據傳輸與轉換過程中的變頻設備與解調設備，信道與天線和記錄器之間通過開關矩陣連接。一般情況下，信道以共享網絡化的方式管理，從理論上說，一個數傳任務只要安排了天線，就一定有相應的信道配合安排，因此本文數傳任務只考慮天線與記錄器的調度情況。而測控任務中基帶、頻點等約束都體現在天線能力上，因此測控任務的資源調度問題只考慮天線這一種地面站資源。

衛(wèi)星的數傳任務和測控任務的資源調度有一定的區(qū)別，也有一定的共性，即任務類型與設備能力相匹配。數傳和測控任務需要不同能力的天線來完成，一般來說，衛(wèi)星的任務類型有以下3種：單一數傳、單一測控、數傳與測控任務。相應地，按照能力劃分，天線也有3種：數傳天線、測控天線、數傳與測控天線。其中，數傳與測控天線既可以執(zhí)行數傳與測控任務，也可以執(zhí)行單一數傳、單一測控任務；數傳天線可以執(zhí)行單一的數傳任務；測控天線可以執(zhí)行單一的測控任務。另外，數傳與測控任務也可同時用一部數傳天線和一部測控天線來完成，但這不符合一體化規(guī)劃中資源設備的合理使用，因此一般情況下不考慮這種調度方式。

2 地面站資源調度問題建模

為衛(wèi)星任務的地面站資源調度問題建立約束滿足模型，首先應對該問題的變量進行描述，再分析該問題的優(yōu)化目標、約束條件。

地面站資源調度問題涉及的變量有以下5種：

1)衛(wèi)星任務集合J={j1,j2,j3,…,ji,…,jn}；

2)地面站集合G={g1,g2,g3,…,gq,…,gm}；

3)衛(wèi)星集合S={s1,s2,s3,…,sp,…,sz}，任務ji的衛(wèi)星用Sji表示；

4)天線集合A={a1,a2,a3,…,ak,…,ax}，任務ji所用天線用Aji表示；

5)記錄器集合R={r1,r2,r3,…,rl,…,ry}，任務ji所用記錄器用Rji表示。

2.1 優(yōu)化目標

衛(wèi)星任務的地面站資源調度主要是為衛(wèi)星任務安排地面站設備，根據實際調度場景，該問題往往是一個多目標的優(yōu)化問題。針對衛(wèi)星任務的資源調度問題主要設計如下優(yōu)化目標：

1)任務執(zhí)行率最大

用Cji表示任務ji是否執(zhí)行，若任務ji安排了符合約束的設備，那么Cji=1，否則Cji=0。

(1)

2)調度方案中所有任務的總弧長最大

STji=min (FSSji,FCSji).

(2)

ETji=max (FSEji,FCEji).

(3)

(4)

式(2)～式(4) 中：FSSji、 FCSji、 FSEji、 FCEji分別表示任務的實際數傳開始時間、實際測控開始時間、實際數傳結束時間、實際測控結束時間，f2表示調度方案的總任務弧長。

3)盡量為任務安排其優(yōu)選設備

(FSEji-FSSji)×( 1/SR(Sji,Rji))).

(5)

f3表示調度方案每個任務的實際時長與其設備首選程度的乘積，其值越大，代表調度方案的設備越優(yōu)選。其中，SA(Sji,Aji)表示任務ji的衛(wèi)星對其天線的首選性值，SR(Sji,Rji)表示任務ji的衛(wèi)星對其記錄器的首選性值。由于設備首選性數值與其首選程度呈負相關，因此，對設備首選性數值取倒數表示設備的首選程度。

2.2 約束條件

2.2.1 任務重要性約束

按照優(yōu)先級由高到低地執(zhí)行衛(wèi)星數傳與測控任務：根據任務的緊急程度和重要程度，任務具有不同的優(yōu)先級，在資源調度過程中，應先安排緊急、重要的任務。

2.2.2 地面站資源約束

本文考慮天線和記錄器兩種設備資源，以下按照設備的能力約束、時間占用約束及天線記錄器關聯約束分別進行敘述。

1)設備能力約束

①天線對衛(wèi)星可用

SA(Sji,Aji)≠-1.

(6)

②天線能力與任務類型相匹配

即任務ji的天線Aji的能力ATAji要滿足任務類型Tji。

③記錄器對任務可用

SR(Sji,Rji)≠-1.

(7)

④只對含有數傳的任務安排記錄器

即如果任務ji的類型Tji為單一測控任務，就不需要對該任務安排記錄器。

⑤記錄器的邏輯記錄器的個數LCRji滿足衛(wèi)星任務下行通道數SCji

SCji≤LCRji.

(8)

⑥記錄器的每個邏輯碼速率LVRji滿足衛(wèi)星任務每個通道的下行碼速率SVji

max(SVji)≤LVRji.

(9)

⑦記錄器物理碼速率PVRji滿足衛(wèi)星任務的最大碼速率：

sum (SVji)≤PVRji.

(10)

2)設備時間占用約束

①某一時刻，一部天線只能安排一顆衛(wèi)星的任務：即在[STji,ETji]時間段內，衛(wèi)星任務ji的天線Aji不能被其他任務所用。

②當一部天線完成一個任務，需要一定的切換時間t才能供下一任務使用：

即在[ETji,ETji+t]時間段內，衛(wèi)星任務ji的天線Aji不能被其他衛(wèi)星利用。

③在滿足負載(即邏輯記錄器個數、邏輯碼速率、物理碼速率)的情況下，記錄器可以給多個任務共用。然而多個數傳任務共用記錄器執(zhí)行任務不穩(wěn)定，因此在資源充足的情況下，多個任務不共用記錄器。當現有的記錄器資源無法滿足當前任務單獨使用時，才考慮多任務共用記錄器。

當記錄器資源充足時，[FSSji,FSEji]時間段內，衛(wèi)星任務ji的記錄器Rji不能被其他任務所用。當記錄器資源不足時，考慮[FSTji,FSEji]時間內記錄器的剩余邏輯記錄器個數、邏輯碼速率、剩余物理碼速率情況，如能滿足當前任務需要，則可安排該記錄器。

④當一個記錄器完成一個任務，需要一定的切換時間t1，才能供下一任務使用：

即在[FSEji,FSEji+t1]時間段內，衛(wèi)星任務ji的記錄器Rji正在占用的通道不可被其他衛(wèi)星利用。

3)天線記錄器關聯約束

單一測控任務只需要安排天線資源。對于含有數傳的任務，只安排天線或只安排記錄器的任務無效。

3 結合啟發(fā)式規(guī)則的改進粒子群算法

3.1 生成初始種群

衛(wèi)星任務的地面站資源調度問題具有約束復雜、規(guī)模較大等特點，因此利用分治思想對問題進行分解，即將任務按照設備、時間分成互不關聯的多個集合，可以有效避免計算過程中對無關部分的遍歷，減少問題的時間復雜度。衛(wèi)星任務的地面站資源調度問題是一個多目標的優(yōu)化問題，對于優(yōu)化目標1)任務執(zhí)行率最大和優(yōu)化目標2)任務總時長最大來說，其進化范圍是很有限的。如果通過算法進行進化或搜索，不僅會增加計算的時間成本，效果也并不明顯，因此考慮先隨機生成一定數量的初始解，再按照優(yōu)化目標1)和優(yōu)化目標2)對其進行篩選，用較優(yōu)的初始種群參與算法的進化與搜索。生成初始種群的流程如圖2所示。

圖2 生成初始解流程圖

在獲取要輸入的任務計劃文件后，對任務分組，同一集合的任務屬于同一地面站，任務之間存在時間沖突，不同的沖突任務集合之間資源調度互不關聯，對每一組分別進行約束和求解。

由于算法的初始解是隨機生成的，為了減少迭代過程中的計算次數，可以根據優(yōu)化目標1)和2)的目標函數值對初始解進行初步篩選，選出較優(yōu)的初始解對優(yōu)化目標3)進化。先隨機生成M個初始解，計算每個初始解的任務執(zhí)行率，選出執(zhí)行率最高的前N(N

針對每一個沖突任務集合，當組內發(fā)生不可調節(jié)的設備資源使用沖突時，還要對任務時間進行合理的弧段修剪，盡量給每個任務都安排設備。對于那些因為資源沖突未安排設備的任務，按照以下原則進行弧段修剪來消解沖突：

1)只對遙感成像衛(wèi)星的數傳任務進行修剪。對于其他任務，不完整執(zhí)行很可能導致任務失敗，因此并不是對所有任務都可以進行弧段修剪。

2)只修剪普通優(yōu)先級的任務，要保證重要任務和緊急任務的完整執(zhí)行。

3)弧段修剪后的剩余數傳時間不得小于t2。數傳時間過短的任務無效。

4)根據任務總時長最大的優(yōu)化目標，為了最大化整體任務時長，如有多種可以消解沖突的修剪方案，選擇修剪時間最短的方案。

5)除任務時間被其他任務幾乎完全覆蓋的任務，保證所有任務都安排了設備。

3.2 改進粒子群算法

粒子群算法是一種進化算法，從初始解出發(fā)，通過迭代尋求最優(yōu)解。本文提及的優(yōu)化目標1)、2)已經在生成初始解步驟進行了篩選，粒子群算法對優(yōu)化目標3)進行優(yōu)化。輸入為經過篩選的N個較優(yōu)初始解，進化的決策變量為天線Aji和記錄器Rji。傳統的粒子群算法流程如下：

1)輸入N個粒子組成的初始解，初始化粒子群：確定種群位置pop[i]、速度Vel[i]。

2)計算每個粒子的適應度值。

3)找到粒子的個體歷史最優(yōu)Pbest，找到粒子的全局歷史最優(yōu)Gbest。

4)按照以下公式更新粒子的位置：

Vel[i]=Vel[i]+r1×c1×(Pbest-pop[i])+

r2×c2×(Gbest-pop[i]).

pop[i]=Vel[i]+pop[i].

其中:r1、r2是0與1之間的隨機數，c1、c2是學習因子參數，通常取2。粒子通過本身的經驗和整個種群的經驗來決定下一步的進化方向。本文中，由于衛(wèi)星任務地面站資源調度問題是一個離散的整數問題，因此對速度進化公式的計算值進行取整，再更新粒子的位置。

5)判斷更新后的粒子是否滿足約束條件:如滿足，則進化成功；否則，退回原位置不動。

6)若未達到終止條件重復步驟2)～6)，否則結束，輸出全局最優(yōu)值。

傳統粒子群算法中，每次迭代進化后判斷粒子是否符合約束。只有符合約束的粒子進化了，不符合約束的沒有進化，這極大限制了粒子群算法的搜索空間，使其陷入局部最優(yōu)。因此，對于那些進化后不符合約束的粒子，利用啟發(fā)式規(guī)則對其進行修正，使其變成符合約束的粒子，這種做法可以有效擴大解空間，尋得更好的解。根據衛(wèi)星任務資源調度的約束條件，定義以下啟發(fā)式規(guī)則：

1)對于每個種群中與其他任何任務都無時間沖突的任務，直接安排其最優(yōu)選設備。

2)如進化后的任務不符合設備時間占用約束，則搜索其沖突集合中與該任務有設備占用沖突的任務，為這些沖突任務更換滿足約束的設備。

3)更換設備時，優(yōu)先更換比當前設備更優(yōu)選的設備，如不滿足約束，再考慮更換次優(yōu)選的設備。

結合啟發(fā)式規(guī)則的改進粒子群算法流程如圖3所示。

圖3 結合啟發(fā)式規(guī)則的改進粒子群算法流程圖

4 仿真實驗及分析

為了驗證算法的有效性，本文從2020年中國遙感衛(wèi)星地面站受理的任務中隨機選取真實任務案例進行資源調度算法仿真實驗。案例的任務規(guī)模與地面資源情況見表1、表2(已隱去真實信息，用代號表示)。

表1 任務規(guī)模

表2 地面站資源情況

在衛(wèi)星任務地面站資源調度問題中，常規(guī)算法有遺傳算法等，本文將通過仿真實驗對比遺傳算法、粒子群算法和結合啟發(fā)式規(guī)則的改進粒子群算法。由于遺傳算法、粒子群算法均帶有一定隨機性，為排除實驗偶然性，分別利用遺傳算法、傳統粒子群算法(以下簡稱粒子群算法)、結合啟發(fā)式規(guī)則的改進粒子群算法(以下簡稱改進算法)對每個案例做10次實驗。實驗經驗表明，遺傳算法在經過500次迭代可以取得較滿意的解，粒子群算法在經過100次以內的迭代幾乎均可以收斂。計算每個案例10次實驗的目標函數平均值和平均差，實驗結果如表3所示。

表3 各算法實驗結果比較

為合理評價算法，本文通過算法運行時間、收斂代數、目標函數值、目標函數值的平均差來評價算法的效率、收斂速度、尋優(yōu)能力和算法穩(wěn)定性。

尋優(yōu)性能方面，通過實驗結果可以看出，通過對初始解進行篩選，可以有效保證調度方案的任務執(zhí)行率。在實驗案例中，除了有時間被包含的任務的案例(如案例3)，所有案例的任務執(zhí)行率達到100%。也就是說，絕大部分調度方案都可以合理配置資源，有效避免了不科學地舍棄任務。其中，案例1任務完整執(zhí)行，即沒有舍棄任何接收弧段；執(zhí)行任務總弧長超過計劃總時長的99%，即因資源不足而減少的任務時長很少。優(yōu)化目標3)為衛(wèi)星任務盡量安排其最佳設備，是通過遺傳算法、粒子群算法優(yōu)化得到的。實驗結果表明，相對于遺傳算法，粒子群算法得到的調度方案尋優(yōu)能力提高33.13%，改進粒子群算法的尋優(yōu)能力較遺傳算法提高42.74%，相對于傳統粒子群算法，結合啟發(fā)式規(guī)則的改進粒子群算法尋優(yōu)能力提高6.67%。

從運行時間來看，算法的運行時間受到迭代次數、約束計算次數的影響，遺傳算法主要通過交叉、變異來尋優(yōu)，它的計算約束次數較少；而粒子群算法每進化一次都要計算約束。雖然改進粒子群算法中增加了對啟發(fā)式規(guī)則的判斷，但相比傳統算法，改進粒子群算法減少了對無沖突任務的遍歷，因此改進算法并沒有增加較多的運行時間，很多案例中，改進算法甚至還加快了算法的運行速度。

從算法達到收斂時的迭代次數來看，遺傳算法的收斂代數最多，在多次實驗中，遺傳算法都表現出較慢的收斂速度。粒子群算法都是迭代100次，其中改進的粒子群算法相對于傳統粒子群算法收斂速度平均提高48.11%，即改進算法具有更快的收斂速度(如圖4所示)。

圖4 某一地面站任務各算法收斂速度對比

從各案例10次實驗的平均差來看，遺傳算法的穩(wěn)定性要優(yōu)于粒子群算法，這與遺傳算法的尋優(yōu)能力和進化程度較弱有關。經改進的粒子群算法相對于傳統粒子群算法穩(wěn)定性平均提高53.12%，相對于遺傳算法穩(wěn)定性提高43.5%。即改進算法具有更好的穩(wěn)定性(如圖5所示)。

圖5 改進算法與傳統算法穩(wěn)定性對比

5 結論

衛(wèi)星任務地面站資源調度問題具有任務規(guī)模大、資源有限、約束復雜、求解難度大等特點，本文通過分析資源調度問題的優(yōu)化目標和衛(wèi)星任務與地面資源的約束，為衛(wèi)星任務地面站資源調度問題建立約束滿足模型。先通過一定的規(guī)則對任務集合進行分解，再對初始解進行篩選，用選出的高質量初始解參與粒子群進化，通過與常規(guī)調度方法(如遺傳算法)對比，證明了粒子群算法對衛(wèi)星任務資源調度問題的可行性，并提出一種結合啟發(fā)式規(guī)則的改進粒子群算法。仿真實驗表明，結合啟發(fā)式方法的改進粒子群算法為衛(wèi)星任務的地面站資源調度問題提供了設備更優(yōu)選的方案，并有效提高了傳統粒子群算法的收斂速度和穩(wěn)定性。