谷宏志

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

0 引言

隨著我國航天事業的發展，在軌的衛星種類越來越多，衛星數量不斷增加，對衛星任務規劃調度系統提出更高的要求。作為衛星運行控制中的核心環節，各航天大國均相繼研發自己的衛星任務規劃調度系統［1］。

商用的衛星任務規劃軟件系統有美國Veridian公司開發的GREAS(Generic Resource Event and Activity Scheduler)通用問題調度系統［2］和美國Analytical Graphics Inc推出的 STK(Satellite Tool Kit)衛星任務規劃套件［3］。但由于衛星能力與應用特點差別較大，為了更好地與衛星載荷能力相匹配，通常需要研制面向某系列衛星的專有衛星任務規劃系統。針對具體衛星的專用調度系統有Potter W等設計的 Landsat 7 調度系統［4］、Muraoka．H 等設計的ASTER調度系統等［5］。隨著衛星載荷種類和能力的不斷提升，參與衛星任務規劃的資源也不斷增加，原有單一流程的任務規劃系統的弊端也逐漸顯現，主要表現在軟件普適性較差，且系統可擴展性、可伸縮性均較低。

本文通過在任務規劃系統設計中引入有限狀態自動機(FSA)模型，利用有限狀態自動機的狀態遷移特性，將原有單一流程的任務規劃系統變成可定制流程的任務規劃平臺，通過面向不同任務匹配不同的規劃流程和算法來有效地解決這些問題。

1 衛星任務規劃流程建模

衛星任務規劃流程可定制平臺要求其能夠與衛星任務規劃業務流程緊密結合，且具有良好的可擴展性、靈活性和流程可定制性。

1．1 衛星任務規劃流程特點分析

衛星任務規劃過程一般可分為衛星載荷任務規劃、地面測控接收資源規劃、規劃方案的人工編輯和地面測控接收資源更新等多個業務節點［6］，且上述多個節點之間可相互轉化。針對不同衛星應用任務有不同的規劃流程，如受到地面測控資源的使用約束，可先進行地面測控接收資源規劃再進行衛星載荷動作規劃，也可能由于受到衛星載荷使用約束的要求，需要先進行衛星載荷任務規劃，然后再進行地面測控跟蹤資源規劃，并根據地面資源規劃結果對衛星載荷動作規劃結果進行調整，還可能按照上述方式迭代優化多次。常規的任務規劃流程如圖1所示。

圖1 衛星任務規劃流程

各節點的主要任務描述如下:

載荷任務規劃節點:根據任務需求，依據載荷任務規劃的約束條件和規劃目標，選擇合適的規劃算法，對分配到衛星相關載荷上的任務進行規劃，確定各載荷任務的執行時間和參數等。

地面資源規劃節點:根據地面接收和測控的任務要求，依據地面接收和測控資源的使用約束和規劃目標，選擇合適的規劃算法，對地面接收和測控資源的任務進行規劃，確定地面各資源的任務執行時間和參數。

地面資源更新節點:由于受到地面資源動態變化的影響，在任務規劃過程中，對資源發生的變化進行及時更新，確保衛星任務規劃所使用到的地面資源的可用性。

方案人工編輯節點:根據按照相關算法完成的任務規劃方案，由用戶確定規劃方案是否滿足任務要求，對不滿足任務要求的部分通過人機交互的方式進行修改，以確定最終的執行方案。

按照傳統的衛星任務規劃系統設計方式，一旦任務規劃系統設計完畢，則任務規劃流程就難以更改。在某個節點后增加一個業務節點或調整規劃順序，將付出較大的修改代價。鑒于此，通過引入有限狀態自動機的概念設計衛星任務規劃平臺，使其能夠搭載遺傳算法［7］、貪婪算法［8］和禁忌搜索算法等算法服務，并可以靈活定制規劃流程，從而適應多種載荷的衛星任務規劃需求。

1．2 衛星任務規劃有限狀態自動機

有限狀態自動機(Finite State Automaton，FSA)［9］是為研究有限內存的計算過程和計算流程提出的一種計算模型。有限狀態自動機擁有有限數量的狀態，每個狀態可以遷移到零個或多個狀態，輸入字串決定執行哪個狀態的遷移。有限狀態自動機可以表示為一個有向圖。

以目前最為常用的衛星任務規劃節點為例，設計中將各節點看成FSA中的不同狀態，則在衛星規劃過程中，上一個狀態可以根據不同的條件轉化為多個可能的后續狀態。所以，將衛星任務規劃流程映射為一個非確定有限狀態自動機，由以下5元組組成:

Q表示有窮狀態集合，針對衛星規劃流程可定制平臺特點，所設計的自動機運行狀態包括:“伺服懸停”、“載荷任務規劃”、“地面資源規劃”、“編輯方案”和“地面資源更新”等。

“伺服懸停”狀態(Halting State)是指當前沒有新的任務需要規劃，所以系統處于伺服等待狀態。在這個狀態下，系統將按時間周期檢測是否有任務到達，如發現有任務到達，則向其他規劃狀態進行轉化。

“載荷任務規劃”狀態(Satellite Scheduling State)表示正在調用載荷任務規劃算法，面向地面目標，優化生成衛星載荷動作序列，且載荷任務規劃算法尚未計算完畢。一旦載荷任務規劃算法計算結果生成，則向其他規劃狀態進行轉化。

“地面資源規劃”狀態(Resource Scheduling State)表示系統正在運行資源規劃算法優化安排地面站跟蹤接收資源、測控資源、中繼星資源和傳輸資源等，保證觀測數據能夠盡早地傳送到衛星數據處理中心，且地面資源規劃算法尚未計算完畢。一旦地面資源規劃算法計算結果生成，則向其他規劃狀態進行轉化。

“編輯方案”狀態(Plan Editing State)是人工發起的。該狀態表示操作員需要暫停規劃流程，開始對已經生成的衛星觀測方案和地面資源工作方案進行手工編輯。在“載荷任務規劃”、“地面資源規劃”或“伺服懸停”狀態，操作員可設置進入“編輯方案”狀態，對自動化算法規劃出的方案進行微調，使之更加符合操作員期望。進入到“編輯方案”狀態后，所有自動化計算流程停止，直至操作員退出“編輯方案”狀態。一旦操作員退出“編輯方案”狀態，系統將自動進入方案編輯前正在運行的狀態。

“地面資源更新”(Resource Updating State)是指系統更新可用的地面站跟蹤接收資源、測控資源、中繼星資源和傳輸資源等信息，是一種需要系統定期進入的狀態，以更新隨時間變化的各種可用地面資源信息。一旦資源更新完畢，系統將自動進入方案編輯前正在運行的狀態。

Σ是有窮輸入字母表。FSA根據接收到的字母確定其下一步轉換的狀態，該字母必須屬于Σ。在衛星規劃流程可定制平臺中，Σ包括:“伺服懸停”、“衛星任務規劃”、“地面資源規劃”、“編輯方案”和“地面資源更新”等。一旦自動機接收相應的狀態信息，則轉化到對應的自動機運行狀態上。

δ是狀態轉移函數，可表示為Q×Σ→2Q。其定義了有限狀態自動機根據當前狀態和接收到的狀態信息確定下一步需要轉換到什么狀態。

q0表示自動機初始狀態。在衛星任務規劃流程可定制平臺中，系統初始狀態設定為“伺服懸停”狀態。

F表示終結狀態集合，F包含于Q。在衛星規劃流程可定制平臺中，終結狀態集合只包括“伺服懸停”狀態。系統完成正常規劃后，將進入“伺服懸停”狀態，等待下一批規劃任務到達。如果最終自動機進入“伺服懸停”狀態，代表輸入狀態信息是合法的。這也是檢驗定制流程是否合法的唯一標準。

在平臺中定義一個3元組來描述狀態關系的合法轉換:

State_Change=(StateNow，Msg，StateNext)。其中:StateNow表示有限自動機當前處于的狀態，StateNow∈Q;Msg表示當前自動機讀入的新狀態信息，Msg∈Σ;StateNext表示當前有限狀態自動機讀入新狀態信息后將轉換到的目標狀態，StateNext∈Q。

基于上述有效狀態轉換關系描述，在衛星規劃流程可定制平臺中，設計狀態轉移函數圖，如圖2所示。

圖2 衛星規劃流程可定制平臺狀態轉移

2 基于消息的衛星任務規劃流程轉換方法

圖2表示了基于有限狀態自動機的衛星規劃流程可定制平臺狀態轉換關系。通過消息隊列(Message Queue)中間件［10］來實現上述狀態轉換機制。即當平臺收到Message Queue發送來的消息時，根據消息內容決定將要進行轉換的狀態。消息內容包括要求自動機轉換到“伺服懸停”狀態、“載荷任務規劃”狀態、“地面資源規劃”狀態、“編輯方案”狀態和“地面資源更新”狀態等狀態信息。

當有限狀態自動機處于“伺服懸停”狀態時，任務規劃平臺檢測到有新的對地觀測任務到達，則可向消息隊列隊尾添加“衛星載荷任務規劃”消息，要求有限狀態自動機由當前狀態轉換到“載荷任務規劃”狀態。同時任務規劃平臺對消息隊列進行監測，如果發現消息隊列不為空，則從消息隊隊列頭取出消息進行解析。如果消息解析結果是“衛星載荷任務規劃”，則自動機將當前狀態由“伺服懸停”轉換到“載荷任務規劃”狀態。同理，如果載荷任務規劃完畢，需要啟動地面資源規劃流程，則可向消息隊列隊尾添加“地面資源規劃”消息。當規劃平臺檢測到消息隊列隊頭消息為“地面資源規劃”時，則自動機可將當前狀態轉換到“地面資源規劃”狀態。其余的狀態轉換方式以此類推。

但自動機是否可以轉換到指定狀態，需要根據有限狀態自動機合法轉換集合來進行驗證。

如果自動機由當前狀態轉換到消息隊列中指定的目標狀態的情況在有限狀態自動機合法轉換集合中沒有描述，則稱為自動機狀態轉換異常。自動機狀態轉換異常是以消息隊列方式實現有限狀態自動機不可避免的問題。產生自動機狀態轉換異常的原因可分為以下2種:

①消息生成渠道多源化導致的自動機狀態轉換異常。如假定當前自動機的狀態為“載荷任務規劃”狀態，且消息隊列為空。而這時地面資源更新事件發生，于是“地面資源更新”狀態消息被添加到消息隊列。任務規劃平臺檢測到消息隊列不為空，于是取出消息，解析為“地面資源更新”，要求自動機轉換到“地面資源更新”狀態。由有限狀態自動機合法轉換集合可知，自動機無法從“載荷任務規劃”狀態直接轉換到“地面資源更新”狀態，從而產生自動機狀態轉換異常。

②程序異常導致的自動機狀態轉換異常。如消息隊列異常，導致消息隊列內各消息次序錯亂或錯誤消息出現，使得自動機無法由當前狀態轉換到消息指定的目標狀態，從而產生自動機狀態轉換異常。

針對第1種情況，在設計中采用消息轉發機制來進行異常處理，即如果自動機可由當前狀態轉換到消息要求的目標狀態，則進行轉換;否則將消息重新添加到消息隊列隊尾，自動機狀態保持不變。如上例中，自動機當前狀態為“載荷任務規劃”狀態，但消息為“地面資源更新”，導致了自動機狀態轉換異常。由于“地面資源更新”消息無法被處理，于是將其添加到消息隊列隊尾，從而繼續開始處理消息隊列中消息。當載荷任務規劃完畢后，任務規劃平臺向消息隊列添加“地面資源規劃”消息，從而自動機可轉換到“地面資源規劃”狀態，當地面資源規劃完畢后，任務規劃平臺向消息隊列添加“伺服懸停”消息，從而自動機轉化為“伺服懸停”狀態。這時，“地面資源更新”消息可被處理，于是自動機狀態轉換異常被消除。

而針對第2種情況，即程序異常導致的自動機狀態轉換異常，可采用消息丟棄的方式進行處理。自動機將丟棄非合法轉換的消息，并上報該異常，從而保證自動機總是處于合法的狀態中。

3 衛星任務規劃可定制流程設計

衛星任務規劃可定制流程設計中的難點在于判定流程是否合法，主要包括:自動機狀態轉換流程是否可達、是否存在死鎖或活鎖、是否能夠正確完成等幾個方面。

規劃流程中每一個節點都代表了一個需要完成的動作，為了完成特定功能，要求每一個節點都能夠被順利地激活。可達性分析主要就是為了判定用戶定制流程內的每一個節點是否均能夠被激活。如果某個節點不可達，則可分為3種情況:① 無輸入遷移，也無輸出遷移，即活動是一個單獨的單元;② 無輸入遷移，有輸出遷移，即活動只有輸出沒有輸入;③有輸入遷移，沒有輸出遷移，即活動只有輸入沒有輸出。如果對上述3種情況進行排除，即可完成可達性分析。

流程的死鎖是指流程總是在一部分活動中運轉而不能執行其他活動，即流程中存在不能激活的活動，從而不能完成整個預定流程。

流程的活鎖是指某個活動由于輸入遷移條件不斷得到滿足而陷入無限循環的執行導致整個流程不能結束。

對于死鎖、活鎖的分析可以借鑒數據庫事務處理中的分析思路，通過分析節點之間是否有多余回路，以及通過仿真模擬的方式，分析死鎖與活鎖發生的可能性。

流程正確性分析主要是判斷流程執行完畢時是否合乎最初設計的目標，是否能夠順利完成既定任務。通常這個過程需要規劃人員的參與。針對模擬的規劃數據進行計算，再與預期結果相比，從而調整規劃流程，使之更加符合規劃人員預期。

4 任務規劃流程定制演示

模擬運行結果如圖3所示。

圖3 衛星任務規劃流程可定制平臺實驗演示

采用SOA技術構建了系統框架［11］，設計并實現的衛星任務規劃流程可定制平臺實驗系統。系統中流程定義及狀態轉移采用XML文件描述［12］。

仿真演示中定制的衛星任務規劃流程為“伺服懸停”—“資源更新”—“載荷任務規劃10”—“地面資源規劃3”—“伺服懸停”。其中，流程中數字代表該節點運行次數，即自環路運行。該過程模擬了一般衛星任務規劃的主要流程。首先，系統處于“伺服懸停”狀態，當接收到新的對地觀測任務時，系統進行資源更新，然后啟動載荷任務規劃10次，地面資源規劃3次，以進行迭代尋優，最終進入“伺服懸停”狀態，完成一次自動規劃過程。

通過平臺運行流程演示可以看到，實驗系統按照設定的流程完成了衛星任務規劃過程，驗證了利用FSA模型設計的衛星任務規劃系統的可行性，為后續實際工程應用奠定了技術基礎。

5 結束語

通過對衛星任務規劃系統的業務流程特點以及有限狀態自動機模型的分析研究，提出了基于有限狀態自動機模型的衛星任務規劃系統的設計思路，并通過衛星任務規劃流程可定制平臺實驗系統的設計實現，驗證了在應用該模型的衛星任務規劃系統上，通過靈活有效的定制任務規劃流程，可以有效地提高系統的可擴展性和可重用性。

［1］ 陳 浩．地表電磁環境探測衛星的資源規劃調度方法［D］．國防科學技術大學，2009．

［2］ Veridian Inc．GREAS for STK User’s Manualand Tutorial［M］．USA:Veridian Inc，2002．

［3］ Analytical Graphics Inc．STK User’s Manual［M］．USA:Analytical Graphics Inc，2003．

［4］ 郭玉華，靳肖閃，李 軍，等．一類對地觀測衛星成像調度系統的設計與實現［J］．系統仿真學報，2009，21(9):2 737－2 741．

［5］ 李 靜，傅碧宏．ASTER項目簡介［J］．遙感技術與應用，1997，12(1):68 －70．

［6］ 賀仁杰，高 鵬，白保存，等．成像衛星任務規劃模型、算法及其應用［J］．系統工程理論與實踐，2011，31(3):411－422．

［7］ 張 旺，王黎莉，伍 洋．基于遺傳算法的陣列天線綜合及分析［J］．無線電通信技術，2011，37(4):28 －30．

［8］ 張 超．基于貪婪算法的遙感地面站任務調度技術［J］．無線電工程，2011，41(1):58 －60．

［9］ 陳火旺，劉春林，譚慶平．程序設計編譯原理［M］．北京:國防工業出版社，2003．

［10］楊 超，徐如志，楊 峰．基于消息隊列的多進程數據處理系統［J］．計算機工程與設計，2010(13):3 128－3 131．

［11］汪 濤．基于SOA架構的中間件應用集成技術［J］．無線電通信技術，2009，35(4):14 －16

［12］高 鵬，李菊芳，譚躍進．XML文檔在衛星任務規劃系統中的應用研究［J］．計算機仿真，2008，25(7):12－15．