航天測控網調度的混合構造啟發式算法

劉建平, 李　晶, 張天驕

(西安衛星測控中心宇航動力學國家重點實驗室, 陜西 西安 710043)

?

航天測控網調度的混合構造啟發式算法

劉建平, 李晶, 張天驕

(西安衛星測控中心宇航動力學國家重點實驗室, 陜西 西安 710043)

摘要：針對航天測控網調度問題,提出一種基于混合啟發式的解構造算法。與其他構造啟發式算法不同的是,本啟發式算法充分利用了我國航天測控網調度需求的特點,包括優先級、任務之間時間間隔要求和一個需求包括多個相同任務要求等,綜合考慮了任務局部和需求全局,融合最大可用窗口價值規則和最早可用窗口集規則。其優勢在于通過動態選擇構造啟發式規則來提高求解質量。最后,通過仿真實驗分析比較,該算法可以在不明顯增加計算時間的基礎上得到更高的初始解質量。

關鍵詞：構造啟發式; 航天測控網調度問題; 測控需求; 約束優化問題; 時間間隔

0引言

隨著各航天大國對空間領域的高度重視,在軌衛星的日益增加造成測控資源的高度緊張,航天測控網調度問題研究成為航天工業領域運籌學研究熱點之一[1]。航天測控網調度是航天測控網管理的核心任務,主要負責協調測控設備與在軌衛星(或即將發射衛星)之間的通信分配。航天測控網調度問題是指在測控資源有限的情況下,如何為測控任務分配合理的測控資源和時間,以最大化地滿足所有測控需求[2]。在實際的航天測控網調度中,最終調度方案的形成一般分為3個階段:第一階段是初始解生成階段,就是利用某種或多種構造啟發式規則快速生成滿足所有約束的無沖突初始分配結果;第二階段是優化解生成階段,就是利用某種局部搜索算法或迭代修復規則在初始解的基礎上進行改進,通常是以一定計算代價來獲得高質量的解;第三階段是沖突消解階段,主要采用與用戶協商的機制進行沖突任務約束松弛,也最大化地滿足各方需求的調度方案[3]。其中前兩個階段通常不需要人參與求解,因而往往合并為計算機自動調度階段[4]。本文的研究主要針對計算機自動調度階段的初始解生成。

航天測控網調度問題初始解生成算法一般包括兩個決策問題,即任務的選擇和可用窗口的選擇。任務的選擇一般都是基于任務優先級規則(如果任務具有事先確定的優先級)。而可用窗口的選擇目前主要有4種規則:一種是可用窗口開始時間最早最先分配規則,稱為“先到先服務”(first coming first serving,FCFS)或“先進先出”(first in first out,FIFO)策略,將基于測控需求和可見信息生成的測控任務所對應的時間窗口開始時間作為排序的標準,進行可用窗口的選擇[5];一種是可用窗口沖突最少最先分配規則,稱為“瓶頸避免”(bottleneck avoidance, BA),以沖突度來衡量每個可用的時間窗口,并以沖突度作為排序的標準,進行可用窗口的選擇[6];一種是可用窗口靈活度最小最先分配規則,以某種靈活度指標來衡量每個可用的時間窗口,并以靈活度為排序的標準,進行可用窗口選擇[7-8]。一種是可用窗口價值最大最先分配規則,以某種價值指標來綜合衡量每個可用的時間窗口,并以價值為排序的標準,進行可用窗口選擇[9-10]。

考慮到我國航天測控網調度需求特點,以上構造啟發式算法很難適應單個測控需求多時間關聯任務的表現形式,本文提出一種基于混合構造啟發式規則的求解算法。該算法綜合考慮任務局部和測控需求整體,能夠在不明顯增加計算時間的基礎上得到更高質量初始解。本文結構如下:首先介紹當前常用的4種構造啟發式算法,給出統一的算法流程;接著分析我國航天測控網的調度需求;基于我國航天測控網調度特點,給出了基于COP的問題表示,并對4種構造啟發式算法進行適應性調整;然后提出基于混合構造啟發式的多星測控資源調度求解算法;最后給出仿真試驗。

14種構造啟發式算法

前面提到了,4種構造啟發式算法包括:基于可用窗口開始時間最早最先分配規則(FIFO)的構造啟發式算法、基于可用窗口沖突最少最先分配規則(Min-Conflict)的構造啟發式算法、基于可用窗口靈活度最小最先分配規則(Min-Flexibility)的構造啟發式算法和基于可用窗口價值最大最先分配規則(Max-Value)的構造啟發式算法。這4種構造啟發式算法的一個共同特點就是利用可用窗口的排序準則來覺得任務和可用窗口的選擇。其中前3種沒有考慮任務優先級,第4種將任務優先級融入到可用窗口的價值指標中。圖1給出了4種構造啟發式算法統一的算法流程。

圖1　4種構造啟發式算法統一算法流程

首先根據測控需求和可見窗口信息生成可調度的可用窗口集合,并按照相應的構造啟發式規則對所有可用窗口集中的所有元素進行排序;然后按照順序先后對任務分配資源,將先分配資源的任務所確定的資源及占用時間作為后續任務調度時必須遵守的硬約束,更新可用窗口集中合中受影響任務的可用時間信息,同時更新被調度任務對應需求的滿足程度;重復分配資源的步驟,當所有任務都已被操作(成功調度或由于沖突等原因調度失敗)或所有衛星需求得到滿足時算法終止。

2我國航天測控網調度需求分析

雖然已經有部分文獻比較明確地描述了我國航天測控網調度需求[11-13],但是本文首次從與幾個具有代表性的航天測控網調度需求對比的角度,來分析我國航天測控網調度需求的特點。有代表性的航天測控網調度需求分別是美國AFSCN[2]、ESA ESTRACK系統[14]、ESA GALILEO系統[15]和歐洲共享航天測控網絡(academic ground station network , AGSN)[16]。各國航天測控網調度需求的不同主要體現在任務需求和優化目標的不同形式,本文這里主要從任務形式的不同來進行比較。

表1主要從7個方面進行比較,包括任務提交形式、任務執行時間、任務優先級、關聯任務、任務間隔時間、任務可用窗口的升/降軌要求和任務冗余。從表1中可以清楚地看到我國航天測控網調度需求所具有的特點。這些特點大多數是因為我國航天測控網的幾何布局造成的,主要是中國大陸境內測控站。

3基于COP的問題表示

將航天測控網調度問題描述為四元組,表示為

P=

(1)

式中，Reg表示所有衛星用戶向測控網管中心提出的測控需求集合,包括具體的測控需求(指明了所用的設備和時間區間)、一般測控需求(日常管理的周期性需求),即Reg={r1,r2,…,rn}(ri表示第i個需求,n表示需求的數量)。參考文獻[9],測控需求r可以表示為

r={No,Sat,p,deviceset,Orbit,

(Rn,Fn)/N,Last,Min,Max}

(2)

其中,No表示需求編號;Sat表示需求對應的衛星編號;p表示需求的優先級;deviceset表示可供完成此需求的測控設備集合,包括中繼測控設備、設備偏好次序、最少設備次數等;Orbit表示軌道類型,包括低/中/高軌;(Rn,Fn)是針對低軌類型衛星來說,表示升軌次數和降軌次數;N是針對中高軌衛星來說,表示測控次數;Last表示一次測控最短持續時間要求;Min表示兩次測控之間的最短測控間隔時間要求;Max表示兩次測控之間的最長測控間隔時間要求。

Sce表示航天測控網資源調度場景,主要由一個調度周期內所有用于調度的可用時間窗口構成,該時間窗口是衛星與測控資源的可見弧段;即Sce=Sce1∨Sce2∨…∨Scen (Scei表示第i個測控需求率的所有可用弧段集合)。

表1　典型的航天測控網調度需求比較

C表示航天測控網資源調度問題所有約束集合,如衛星約束、資源約束、時間窗口約束、關系約束等。約束的具體形式可以參考文獻[11],本文這里不再贅述。

由于zi=r(i,:)Xl,s+Ni (l{1,2,…,Nt}，s S)，Ni為QHN的第i個元素，此時βi(l,x)= ui(l,x)+ Ni，其中，ui(l,x)=r(i,:)Xl,s-r(i,:)X.在某一時刻，接收端信道狀態信息已知時，信道傳輸矩陣H已知，發射向量固定，接收端檢測時假設發端發射向量也是已知的，因此ui(l,x)可以近似看成一個常量.由于N服從高斯分布，可以推導出βi(l,x)也服從高斯分布，歸一化為：

O表示優化目標,最大限度地滿足航天測控網的測控需求。即

(3)

式中,p表示測控需求的優先級;d表示單個測控需求的任務滿足率,例如某測控需求一天需要完成m個測控任務,則d∈{0,1/m,2/m,…,(m-1)/m,1};優化目標O表示整個航天測控網的測控需求滿足率。

4構造啟發式算法的適應性調整

為了使4種常用的構造啟發式算法能夠適應我國航天測控網調度需求,需要對這4種算法進行適應性調整。圖2給出了調整后的統一算法流程,其中虛線框為適應性調整的部分。可以看到,整個流程在兩個地方進行了適應性調整:一處是在構造啟發式規則應用可用窗口之前,增加了基于優先級的任務選擇模塊,這主要是為了適應任務優先級的需求;另一處是在構造啟發式規則應用可用窗口之后,增加了可用窗口的升/降軌和時間間隔要求的判斷,這主要是為了適應任務的升/降軌需求和任務間隔時間要求。

另外,由于以上4種常用構造啟發式規則都是從單任務角度進行逐個求解,而沒有從任務所屬的測控需求整體考慮。因此,為了適應以測控需求為表現形式的相同多任務提交形式,也就是一個測控需求時段內往往具有多個帶有時間間隔要求的相同任務,本文提出了面向同一測控需求的最早可用窗口集優先分配規則(First-Set)。First-Set定義如下:假設一個測控需求具有m個具有時間間隔要求的相同任務,最短/最長時間間隔為Δmin/Δmax,其可見窗口集合為W。若存在同時滿足這m個任務的可用時間窗口集合為AWm(AWm?W),則First-Set就是AWm中具有第一個任務可見窗口開始時間最早的集合;若AWm為空集,可以繼續搜索同時滿足m-1個任務的可用時間窗口集合AWm-1,依次類推。

圖2　4種構造啟發式算法調整后的統一算法流程

5基于混合構造啟發式的求解算法

針對我國航天測控網調度需求特點,使構造啟發式規則既能適應傳統單任務提交形式又能適應單個測控需求多任務的表現形式,綜合考慮任務局部和測控需求整體,本文這里提出了混合First-Set規則和Max-Value規則的構造啟發式規則,縮寫為First-Set & Max-Value。其中First-Set規則側重于單個測控需求整體,而Max-Value側重于單個任務。圖3給出了求解算法流程。

與4種常見構造啟發式算法的單一任務尺度不同,本算法混合了測控需求和任務兩種不同尺度,且一個測控需求包括多個優先級相同或不同的任務。首先以優先級為準則依次選擇測控需求,再以該測控需求內所包含的任務優先級為準則依次選擇任務。Max-Value規則運行一次僅得到一個調度任務,而First-Set規則運行一次可以得到多個調度任務。當完成一個測控需求分配時,通過比較兩者該測控需求滿足率,以較大者產生的調度任務作為本測控需求的已調度任務。這樣設計的優勢在于,通過每一輪以測控需求滿足率為指標動態選擇構造啟發式規則,以融合First-Set規則和Max-Value規則的優勢,提高整個求解質量。當然,從算法復雜性來看,由于混合了兩者規則,相對單一規則來說增加了計算成本,運行時間上應該是兩個單一規則算法運行時間之和。

圖3　混合構造啟發式算法流程

6仿真實例與結果分析

6.1仿真場景

假設航天測控網具有5個地面站9套設備,分別位于喀什(2套)、佳木斯(2套)、三亞(2套)、渭南(2套)和青島(1套),75顆在軌衛星(包括4顆中高軌衛星),其編號為1~75,每個衛星測控任務需求如表2所示。

表2　每個衛星測控任務需求

不失一般性,對于低軌衛星來說,可見時間窗口一般為滿足任務最短持續時間要求的整個弧段;對于中高軌衛星來說,由于可見弧段時間一般較長,為了提高弧段利用率,對每個長可見弧段進行子弧段離散化處理,即每個子弧段時長為最短持續時間,時間間隔取1 min。仿真場景設計了3種不同規模的場景,分別是大、中和小規模場景,場景配置如表3所示。

6.2比較算法的設計

為了驗證本文提出的混合構造啟發式算法的有效性,這里考慮了本文第4節給出的基于FIFO規則啟發式算法、基于Max-Value規則啟發式算法和基于First-Set規則啟發式算法。其中基于Max-Value規則啟發式算法采用文獻[10]的CHBR算法的弧段價值計算方法。這3種算法的選擇具有一定的代表性:FIFO啟發式反映在單個任務的可能開始時間上;Max-Value啟發式反映在涵蓋相鄰任務時間間隔要求的單任務價值上;First-Set啟發式則反映在具有多個時間關聯任務的測控需求上。

表3　3種場景配置

6.3仿真結果比較分析

為了更加客觀地反映各個算法的性能,這里以測控需求滿足度來衡量算法求解質量,以計算時間來衡量算法計算成本。每個場景以需求優先級的不同生成200個算例,每個算例在1~10間隨機生成所包含測控需求的優先級。而且,每個場景設計了兩種時間間隔:一個最長時間間隔為8 h,一個最長時間間隔為10 h。表4是各算法在不同場景下的平均測控需求滿足度,表5是各算法在不同場景下的平均計算時間。

從求解質量來看,First-Set & Max-Value啟發式最好,Max-Value次之,其次First-Set,FIFO最差。隨著最長時間間隔由10 h縮短為8 h,測控需求的時間間隔約束加強,雖然4個算法的求解質量都有所下降,但是相比較次優的Max-Value啟發式,有兩點發現:一是First-Set & Max-Value啟發式的求解質量從2%提高到6%;二是First-Set啟發式的求解質量逐步逼近Max-Value啟發式。這兩點發現實際上也反映了First-Set & Max-Value啟發式綜合考慮任務局部和測控需求整體的優勢所在。

表4　各算法在不同場景下的平均測控需求滿足度

表5　各算法在不同場景下的平均計算時間　s

從計算成本來看,由于本文所給出的算法都是調度問題初始解構造的貪婪算法,每一步任務的選擇和可用弧段的選擇都是根據啟發式規則確定的,直至所剩任務沒有可以弧段為止。因此在算法運行過程中,未調度集合隨時間變化都應是線性遞減,直至算法結束。不同的是,各個算法進行每一步可用弧段選擇時進行的計算復雜度是不同的,從仿真結果來看,FIFO由于僅僅進行簡單排序,因而計算量最少;First-Set由于要先確定AW窗口集,再排序,因而次之;Max-Value由于需要先確定每個可用弧段的價值而需要更多計算量;First-Set & Max-Value即要先確定AW窗口集又要確定每個可用弧段的價值,因此計算量最大。

7結論

針對我國航天測控網調度需求特點,提出一種混合構造啟發式的測控網調度問題求解算法。算法綜合考慮任務局部和測控需求整體,融合了First-Set規則和Max-Value規則的構造啟發式規則,通過以測控需求滿足率為指標動態選擇構造啟發式規則來提高求解質量。通過仿真實驗分析比較驗證了該算法可以在不明顯增加計算時間的基礎上得到更高的初始解質量。本文雖然對航天測控網調度的混合構造啟發式算法進行了一個很好的嘗試,但是由于混合的方式還比較簡單而造成計算代價較大。下一步將繼續深入研究這種混合構造啟發式算法,提高兩者構造啟發式規則的耦合程度,如在可用窗口集的選擇依據上引入Max-Value規則等,進一步改善計算成本。

參考文獻：

[1] Jorg F, Konstantinos K, Banafsheh K. Operations research in the space industry[J].EuropeanJournalofOperationalResearch, 2012, 217(2): 233-240.

[2] Barbulescu L, Howe A, Whitley D. AFSCN scheduling: how the problem and solution have evolved[J].MathematicalandComputerModelling, 2006, 43(9/10):1023-1037.

[3] Stottler D. Satellite communication scheduling, optimization, and deconfliction using artificial intelligence techniques[C]∥Proc.oftheInfotech@Aerospace,2010.

[4] Schalck S M. Automating satellite range scheduling[D]. Dayton: Air Force Institute of Technology, 1993.

[5] Barbulescu L, Watson J P, Whitley L D, et al. Scheduling space-ground communications for the air force satellite control network[J].JournalofScheduling, 2004, 7(1): 7-34.

[6] Stottler R, Mahan K, Jensen R. Bottleneck avoidance techniques for automated satellite communication scheduling[C]∥Proc.oftheInfotech@Aerospace, 2011.

[7] Gooley T. Automating the satellite range scheduling process[D]. Dayton: Air Force Institute of Technology, 1993.

[8] Chen L J, Wu X Y, Li Y F. Scheduling algorithm for relaying satellite based on temporal flexibility[J].AeronauticalComputingTechnique,2006,36(4):48-51.(陳理江,武小悅,李云峰.基于時間靈活度的中繼衛星調度算法[J].航空計算技術,2006,36(4):48-51.)

[9] Ling X D, Wu X Y, Liu Q. Requirement-oriented TT&C scheduling algorithm[J].SystemsEngineeringandElectronics, 2009, 31(7):1661-1666.(凌曉冬,武小悅,劉琦.面向需求的航天測控資源調度算法[J].系統工程與電子技術, 2009,31(7):1661-1666.)

[10]Chen F. Research on genetic algorithm for multi-satellite TT&C scheduling problem[D].Changsha:National University of Defense Technology,2010.(陳峰.多星測控調度問題的遺傳算法研究[D].長沙:國防科學技術大學,2010.)

[11]Ling X D, Wu X Y, Liu B, et al. Study on the CSP model of satellite TT&C resource scheduling[J].SystemsEngineeringandElectronics,2012,34(11):2275-2279.(凌曉冬,武小悅,劉冰,等.衛星測控資源調度CSP模型研究[J].2012,34(11):2275-2279.)

[12]Chen F, Wu X Y. Space and ground TT&C resource integrated scheduling model[J].JournalofAstronautics, 2010, 31(5): 1405-1412.(陳峰,武小悅.天地測控資源一體化調度模型[J].宇航學報,2010,31(5):1405-1412.)

[13]Kang N. Research on genetic algorithm for multi-satellite TT&C scheduling problem[D]. Changsha: National University of Defense Technology,2011.(康寧.航天測控優化調度模型及其拉格朗日松弛[D].長沙:國防科學技術大學,2011.)

[14]Damiani S, Dreihahn H, Noll J, et al. Automated allocation of ESA ground station network services[C]∥Proc.oftheInternationalWorkshoponPlanningandSchedulingforSpace,2006:1-10.

[15]Marinelli F, Rossi F, Nocella S, et al. A Lagrangian heuristic for satellite range scheduling with resource constraints[J].Computers&OperationsResearch,2005,38(11):1572-1583.

[16]Schmidt M, Schilling K. A scheduling system with redundant scheduling capabilities for ground station networks[C]∥Proc.oftheInternationalWorkshoponPlanningandSchedulingforSpace, 2009: 1-6.

劉建平(1975-),男,高級工程師,博士,主要研究方向為航天任務智能規劃與優化調度。

E-mail:ljpnudt@sina.com

李晶(1963-),女,研究員,博士,主要研究方向為航天任務智能規劃與優化調度。

E-mail:carol_lee_0727@sina.com

張天驕(1988-),女,工程師,博士研究生,主要研究方向為航天任務智能規劃與優化調度。

E-mail:tiantian880407@163.com

網絡優先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20141119.2227.011.html

Hybrid constructive heuristics of space measurement and

control network scheduling problem

LIU Jian-ping, LI Jing, ZHANG Tian-jiao

(StateKeyLaboratoryofAstronauticDynamics,Xi’anSatelliteControlCentre,Xi’an710043,China)

Abstract:For the space measurement and control network scheduling problem, a hybrid constructive heuristics is proposed. Different from existing constructive heuristics, this heuristics takes advantage of characteristics of space measurement and control network scheduling requirements, including priorities, temporal intervals and multiple same tasks in one requirement. Considering both local tasks and the complete requirement, it integrates the maximum valued available task window rule with the first available task window set rule. Its advantage is to improve the solution quality by means of dynamic choice of the two rules. Finally,through simulation cases and computational results analysis,it is found that this hybrid constructive heuristics can improve the solution quality and increase less computation cost.

Keywords:constructive heuristics; space measurement and control network scheduling problem; tracking, telemetry and command (TT&C) requirement; constraint optimization problem (COP); temporal interval

作者簡介：

中圖分類號：TP 18

文獻標志碼：A

DOI:10.3969/j.issn.1001-506X.2015.07.16

基金項目：青年創新基金(GFZX04060103-02)資助課題

收稿日期：2014-07-08；修回日期：2014-11-01；網絡優先出版日期：2014-11-19。