面向復雜關聯測控需求的沖突規避調度算法

辛立強, 張 超,*, 趙靈芝, 劉建平

(1. 西安交通大學信息與通信工程學院, 陜西 西安 710048;2. 西安衛星測控中心宇航動力學國家重點實驗室, 陜西 西安 710043)

0 引 言

在空間資源開發熱潮的推動下,我國在軌運行的中、低軌道衛星越來越多,而目前測控資源卻是有限的,新建、維護測控資源設備所需成本巨大。因此,如何充分利用現有測控站網設備資源,提高測控站網資源使用的效率,盡可能地提高衛星用戶測控需求的成功率成為國家迫切需要解決的問題。

由于在軌衛星分布于不同軌道,而測控資源位于地面固定位置,因此衛星與測控設備的可見時間不連續,所以測控任務的可行解是離散的。同時,航天器的測控需求也日趨復雜化,任務之間存在復雜的邏輯及時序關系約束。關聯約束關系使得任務的解空間大小會受到相鄰任務可行解的選取而發生非線性變化,這大大提高了計算復雜度,所以很難在有限的時間內快速找到全局最優解。國內外不少機構和學者采用遺傳算法對測控資源調度問題進行了研究,文獻[4]將衛星過境弧段按時間先后劃分為兩部分,運用遺傳算法在對第一部分優化調度完成的基礎上,將最優解和第二部分整合并進一步優化得到最優調度解。薛乃陽等人引入微元法將可見弧段進行離散化,并采用改進的遺傳算法對小規模混合衛星資源調度問題進行驗證,使用3個測控設備對24顆衛星的125個任務進行測控,將測控任務滿足率由85.6%提高到92.8%。文獻[6]將商業測控資源和國有測控資源結合起來共同為國家級測控任務和商用衛星提供測控服務,使用3個國有測控資源和3個商業測站對16顆國有衛星和8顆商用衛星進行聯合測控,將測控調度收益值提升了13.12%。遺傳算法雖然可以解決測控資源調度問題,但無法避免其計算復雜度高、算法運行時間長的特點，只適用于解決少量測控站、小規模衛星需求的資源調度問題。

隨著測控設備數量和衛星任務數量的增多,遺傳算法并不能在有限的時間內解決大規模測控資源調度問題,而啟發式調度算法卻可很好地應用于大規模調度問題中。Gooley綜合采用混合整數規劃與插入試探的啟發式算法對美國衛星控制網的資源調度問題進行了詳細研究。Babulescu等針對航天測控調度問題分別嘗試使用了局部搜索、遺傳算法和啟發式調度算法對該問題進行求解,并對比分析了其調度結果。Li等采用先進先出調度算法對巨型星座測控業務進行了仿真,針對地面資源負載率、任務滿意度等指標進行了量化分析。文獻[13]在分析測控資源調度問題復雜性的基礎上提出了元啟發式的解決方案。文獻[14]引入了可視窗口擁擠度、匹配度和衛星偏好偏差3個啟發式因子,建立了基于特征信息的測控資源調度算法。文獻[15]按照任務需求時間由短到長的啟發式順序安排任務能夠獲得較高的任務成功率。凌曉東等設計了基于任務優先級的面向需求的測控資源調度算法。然而使用優先級來確定任務的初始調度順序無法客觀反映測控資源的稀缺性,不能從全局角度考慮資源競爭所產生的沖突。

現有啟發式調度算法還很少考慮到任務間復雜的關聯性。本文特別針對相互關聯的測控任務的資源調度問題進行了研究。在對航天測控資源調度過程中所涉及的測控設備、衛星測控任務、可見弧段信息進行描述的基礎上,采用約束滿足問題模型對衛星測控資源調度問題進行了數學化建模,創新性地設計了一種基于任務沖突規避的啟發式調度算法。

1 衛星測控資源調度問題

我國現有測控資源調度實戰系統統一調度所有地面站網測控設備以滿足在軌衛星的測控請求。目前一般采用測控資源預分配+動態應急響應的方式,資源站網管理中心根據衛星發出的測運控需求申請生成測控計劃。在預分配過程中,需要從全局最優角度考慮,盡可能提高任務調度成功率。資源預分配算法性能高低直接決定測控網的運行效益和衛星測控任務的滿足率。因此需要對預分配測控資源調度算法的效率和成功率進行提高。

圖1給出了測控資源調度的系統框圖。

圖1 測控資源調度系統框圖Fig.1 Block diagram of TT & C resource scheduling system

測控資源調度問題是一種必須同時滿足衛星處于測控設備可見弧段、任務需求約束的規劃問題。衛星的可見弧段由其運行軌道和地面站所處位置決定。使用STK仿真軟件根據衛星軌道信息和測控設備的地理位置生成衛星與測控設備的可見預報。測控資源調度中心根據具體任務需求、衛星可見預報、測控資源屬性給出資源調度方案,將資源調度計劃反饋回衛星和測控資源設備。

雖然近些年已經有相關學者針對我國航天測控網進行了一定的分析研究,但是未曾考慮到相鄰子任務完成時間之間需要保持復雜的關聯性。可行解選取不當容易導致選擇的可行解違反任務間復雜的關聯性約束,導致需要推倒重新選擇,影響調度算法運行效率。本文根據衛星測控需求,加入了測控子任務間的關聯約束,建立了目標約束滿足模型。

1.1 衛星測控任務模型

現有測控資源調度系統采取預分配的調度策略,資源調度系統同時對衛星一周內的所有任務進行調度。假設一共有個衛星測控任務需求,表示所有衛星用戶的測控任務集合,表達式為

={,,…,,…,}

(1)

式中:=[,,type,pri]為某一衛星的測控任務需求,為提出測控申請的衛星,為測控事件,type為星座類型,pri為該任務的優先級。={cd,1,cd,2,cd,3,cd,4,cd,5,cd,6,cd,7},中包括了一周7天的測控任務需求。假設第個任務的第天一共有(,)個子測控任務需求,那么cd, ={cd,,1,cd,,2,…,cd,,,…,cd,,(,)}。cd,,是不可分割的最小子任務需求。每個子測控任務需求cd,,有表1中的11個屬性。

表1 任務需求屬性表

cd,,可表示為

cd,,={RT,MME,MTL,RPC,Favdecset,function, Frereq,Sigstru,Intertype,Inter,Inter}

(2)

表1給出了衛星測控任務需求的基本屬性。RT表示升降軌要求,指定完成該測控子任務需要衛星處在升軌弧段或降軌弧段;MME表示測控弧段所需的最小仰角;MTL表示完成該測控子任務所需的最短測控時間;RPC表示測控所屬相對圈號約束,PRC?{1,2,…,},為衛星過境連續可見圈數,完成該測控子任務的相對圈號僅能是PRC集合中的一個;Favdevset表示該任務偏好的地面設備集;function表示該子任務需要實現的功能;Frereq表示該任務所需的頻段,常用的頻段有VHF/UHF、L、S、C、X、Ku、Ka、激光,只有測控設備具備該頻段的通信條件時,才可完成該任務的測控;Sigstru表示該任務所需的功能信號體制;Intertype表示相鄰子任務的關聯模式,Intertype=0表示相鄰兩子任務完成圈號需滿足最大最小約束,Intertype=1表示相鄰兩子任務的測控時間間隔需滿足最大最小約束;Inter表示該子任務測控的開始時刻與上一子任務測控結束時刻的最短時間間隔或最小間隔圈號;Inter表示完成該子任務測控需求的開始時刻與完成上一子任務測控結束時刻的最長時間間隔或最大間隔圈號。

1.2 地面測控設備模型

我國衛星測控站主要分布于國土境內,各個地面站的設備屬性均不相同,為規范化統一描述其屬性,我們給出了衛星測控設備的基本屬性,如表2所示。

表2 衛星測控站設備屬性

假設有個測控設備,用集合{,,…,}表示。每個測控設備的屬性可以表示為

={buildtime,diamatletime,function, Fresus,Sigsus,〈forbiddentime〉}

(3)

1.3 可見弧段模型

由于只有當衛星與地面測控站可見時才可進行測控任務。因此,通過仿真軟件,結合衛星的軌道信息和測控資源的位置信息生成衛星的可見弧段預報。表3給出了衛星可見弧段的基本屬性。

表3 衛星可見弧段預報屬性

對地面測控設備和衛星相對應的可見弧段特征可描述為

={,,RF,rev,Idrev,conrev,tr,tr,Ang}

(4)

式中:表示某衛星相對于一個地面設備的一個可見弧段;表示地面設備編號;表示衛星編號;RF表示該弧段的升降軌屬性;rev表示該衛星的總圈號;Idrev表示此弧段為該衛星此次過境的相對圈數;conrev表示該衛星此次過境的連續可見圈數;tr表示該弧段開始時間;tr表示該弧段結束時間;Ang表示該可見弧段中點的俯仰角。

1.4 測控資源調度目標約束模型

為建立目標約束模型,引入決策變量,,。當,,=1時,表示任務的第天的第個子任務調度成功;當,,=0時,表示任務的第天的第個子任務調度失敗。完成一個測控子任務的資源利用情況可以表示為,,={cd,,,,rev,,},任務cd,,在衛星的第rev圈完成,和分別表示cd,,使用設備測控的開始時間和結束時間。當子任務未被完成時,,,=?。我們將目標函數設計為衛星測控子任務的加權完成率最大,如下所示:

(5)

測控資源調度問題的約束條件可以分為3大類:第一類是基于測控子任務的需求約束;第二類是子任務間的關聯約束;第三類是根據設備可用時間、衛星可見弧段所確定的設備物理約束。表4詳細列舉了各項約束。

表4 測控任務約束條件表

2 測控資源調度算法

2.1 任務占用資源的概率分布

(6)

(7)

2.2 基于任務需求度的關鍵任務選取策略

基于啟發式的航天測控網調度問題初始解生成一般包括兩個步驟,即確定任務處理的順序和任務可行解的選取策略。獲得一個好的任務處理順序是建立一個接近最優的單輪序貫調度算法的關鍵。

圖2給出了4個設備不同時刻被任務占用概率累積和的示意圖,從圖中可以看出,設備3的圓圈處取值最大,即設備被任務占用概率累積和最大,說明此時該設備最可能產生任務沖突,因此為關鍵資源位置。

圖2 關鍵位置示意圖Fig.2 Schematic diagram of bottleneck location

2.3 基于沖突代價最小的可行解選取策略

啟發式調度算法第二步是根據可行解選取策略確定關鍵任務的調度解。需要綜合考慮成功調度收益和導致其他任務調度失敗代價,為關鍵任務選定最佳可行解。為方便表述,將子任務cd,,記為連續數字編號。假設通過第22節方法找到該時刻關鍵任務為,那么關鍵任務的可行解空間為。由于選擇同一子任務可行解空間內的任何一個解都能夠完成測控任務需求,所以該任務成功調度的收益相同。但當選擇某一可行解時將導致其他待調度任務可行解空間減小情況不同,因此根據該可行解對其他待調度任務可行解空間的影響情況構造出該可行解的接受度函數()。依次遍歷關鍵任務的所有可行解,找出其中接受度最高的解作為調度解。接受度函數()的表達式為

(8)

2.4 算法流程圖

圖3 算法流程圖Fig.3 Algorithm flow chart

3 實驗驗證

為了驗證本文提出的基于沖突的站網資源調度啟發式算法的性能,本文給出位于9個地面站的16臺測控設備對50顆、100顆、150顆低軌衛星兩周14天測控任務需求進行測控的實例,分別代表小規模、中規模、大規模情況下的衛星測控任務需求。測控設備和任務需求的基本情況參見表5。

表5 測控場景的基本情況

實驗驗證環境為Win10 64位系統,CPU為Core i7-8700,3.20 GHz六核,16GBRAM,實驗工具為Eclipse。

實驗分析任務調度成功率。本文選取7組對照算法進行實驗。單層調度算法采取隨機選取任務的可行解進行調度和測控任務的可行解先到先服務(first in first out, FIFO)的策略。雙層調度算法將對選取調度任務和可行解這兩個步驟分步進行,設置基于任務優先級的FIFO算法、基于任務優先級的可行解接受度最大的調度算法、基于關鍵任務的FIFO算法、基于關鍵任務的隨機可行解選取算法作為對照組。為了對比觀察各個算法的性能,這里以衛星測控任務需求滿足率來衡量算法的求解質量。根據上述場景實驗得到不同任務規模下測控任務調度成功率如圖4所示。

圖4 不同任務規模下任務調度成功率Fig.4 Task scheduling success rate under different task sizes

從圖4可以看出隨機選取可行解的算法隨著測控任務規模的擴大,由于其沒有考慮到任務之間的沖突關系,成功率有所下降。當衛星任務個數超過100后,FIFO的調度策略成功率都低于90%,是因為其每一步選取“過分貪婪”,沒有考慮到設備的稀缺性和任務可行解的靈活度,將測控任務大多安排在地方時早的設備上,使得這些設備的利用率過高,從而導致更多的任務沖突。基于任務優先級的FIFO調度算法相較于全局FIFO算法成功率有所降低,因為任務調度成功率對優先級是敏感的,而優先級的屬性較為主觀,也不能反映測控資源的稀缺情況。

對于采用基于關鍵任務的調度算法,當確定關鍵任務后,考慮了3種不同的可行解選取策略。FIFO的選擇策略成功率最低。若隨機選取關鍵任務的任一可行解作為調度解,任務調度的成功率隨著任務規模的擴大呈下降趨勢。該算法由于選擇可行解時過分隨機,沒有考慮到子任務間有復雜的關聯約束,選擇不當會與未調度任務的可行解產生更多的沖突,從而降低整體任務調度的成功率。本文提出的基于接受度函數最大的測控資源調度算法由于每次選取可行解時均充分考慮到了對未調度測控任務的影響,所以該算法的調度成功率最高。隨著測控任務規模的擴大,成功率依然可以保持較高水平,當有150顆衛星的測控任務需要調度時,成功率仍能達到98%以上,因此該算法是有效的。

圖5給出了各測控設備的可服務時長和各算法情況下各設備提供測控服務時長總和。由于一階FIFO算法僅從可行解的開始時間角度出發,將大量任務安排在盡量早的時間段進行測控,從而使得位于黑龍江佳木斯的6號設備的測控服務時間較長。二階的FIFO算法中,6號設備的測控時長較長,而位于新疆喀什的15號設備的測控時長較短,未能充分利用所有的測控設備,從而降低了測控任務的調度成功率。

圖5 設備服務時長匯總Fig.5 Summary of equipment service duration

雖然在圖4中發現:基于關鍵任務來確定任務調度順序并沒有明顯比傳統的通過優先級來確定任務調度順序的方法好。但當測控資源數量減少時,測控資源更加稀缺,便能明顯體現出基于關鍵任務處理順序的優勢。圖6展示了150顆衛星的5 038個測控任務需求在7個、10個、17個測控設備時任務調度的成功率。隨著測控設備數量的減少,任務調度的成功率也隨之降低。而通過基于關鍵任務的測控資源調度算法計算得到的任務調度成功率明顯高于其他算法。

圖6 150顆衛星測控任務調度成功率Fig.6 Success rate of TT & C task scheduling for 150 satellites

4 結 論

針對基于衛星需求的測控資源調度問題, 本文建立了目標約束模型,并充分考慮到測控任務需求間復雜的關聯關系,設計了一種沖突規避的復雜關聯測控需求調度算法。該算法采用測控資源被任務占用概率的累積和作為評判指標找到最可能產生沖突的測控設備和時刻,并選取該時刻對此測控設備需求度最大的任務作為關鍵任務進行調度。為避免過分貪婪,充分考慮到測控資源占用對全局任務的影響和任務間的關聯關系,構造了接受度函數,選取接受度函數最大的可行解作為調度解。通過算例的對比實驗分析可以看出,本算法的求解效果較好。

雖然本文提出的基于沖突規避的關鍵任務測控資源調度算法能夠獲得較為滿意的調度解,但這只是一種單輪序貫的啟發式調度算法。下一步將通過分析單輪序貫調度下資源分配失敗任務與成功任務之間的競爭關系,設計合適的回溯搜索算法。