基于深度神經網絡的多星測控調度方法

李長德，徐偉，徐梁，王燕

航天恒星科技有限公司，北京 100086

1 引言

隨著各國對空間領域應用的重視，空間技術迅猛發展，在軌衛星的數量不斷增加，對測控資源的需求越來越大[1]，多星測控資源調度成為衛星應用領域的重要挑戰。多星測控調度(multi-satellite TT&C scheduling，MSTCS)問題是指在多星測控需求和測控資源一定的背景下，研究如何對眾多衛星的各類測控需求進行管理和調度，通過合理地分配測控資源，更好地滿足衛星的測控需求，使得衛星發揮最大的應用效能，并對航天頂層設計提供指導。MSTCS問題是一個高復雜、強沖突、多關聯約束的NP問題。傳統測控資源調度算法在針對大量不同種類衛星進行測控調度時面臨運算時間較長、效率低下、復雜度高且適應性差等問題。

面對MSTCS問題的現狀，國內外涌現出許多相關研究，如數學規劃、CSP模型、禁忌搜索及人工智能等求解方法。其中，文獻[2]提出CSP模型方法，文獻[3-4]提出約束規劃方法。這些方法可以精確的描述問題，但是考慮的約束過多且復雜，難以求解，文獻[5-6]提出使用遺傳算法，文獻[7]提出蟻群算法解決測控調度問題，這些禁忌搜索方法設計靈活，求解效率較高，但是領域知識依賴性較強。文獻[8-10]提出基于神經網絡解決測控資源調度，由于網絡結構較為簡單，只有一層隱含層，結果精度較差。

為了解決以上問題，本文提出了基于深度神經網絡(deep neural networks,DNN)的多星測控調度方法。深度神經網絡層級較多，結構穩定，具有強大的計算能力，學習能力強且能學到深的特征。當前DNN算法已在推薦算法[11-12]、航天器容錯控制[13]、空間目標識別[14]等方面解決了很多問題。該方法抽取調度過程中對調度結果有重要影響力的屬性作為DNN的特征值構建DNN模型，并通過預處理將測控任務與測控資源間的全匹配縮減為有效匹配，降低DNN的特征維度及訓練難度。最后根據真實的衛星和測站參數，使用STK模擬真實場景，驗證了本文提出方法的有效性和高效性。

2 多星測控調度特性分析與建模

使用DNN算法解決MSTCS問題，首先需要確定DNN的輸入，即特征值的選擇與抽取。為選擇出合適的屬性作為DNN算法的特征值，對調度過程中涉及的實體進行建模，明確各個實體的屬性；然后分析調度過程中的各種約束，進行目標約束建模。將實體模型與約束模型結合，選擇對調度結果有影響的因子，數值離散處理后作為DNN算法的特征值。

2.1 實體模型

測控資源調度問題涉及的實體主要有衛星、測控設備、測控任務、用戶偏好、可見時間弧段[15-16]。

(1)衛星

其屬性定義為：Satellite={Satellite1,Satellite2,…,Satellitem},Satellitei∈Satellite，指的是第i個衛星，i=1,2,…,m。Satellitei={SIDi,SNamei,STatusi,STypei,SPi,SCati,SFi,SLifei,SDSi}，屬性的含義分別為：SID為衛星標識符，SName為名稱，STatus為狀態，SType為衛星軌道類型，SP為衛星優先級，SCat為衛星屬性(飛船、軍用、民用等)，SF為測控頻段，SLife為衛星運行階段，SDS為設備偏好集合。

(2)測控設備

屬性定義為：Equipment={Equipment1,Equipment2,…,Equipmentn}，Equipmenti∈Equipment,指的是第i個設備，i=1,2,3,…,n。Equipmenti={EqIDi,EqNamei,EqDFi,EqUri,EqStatusi,EqStarttimei,EqEndtimei,EqPri,EqSti,EqServcei}，屬性的含義分別為：EqID為設備標識符，EqName為名稱，EqDF為設備頻段，EqUr為設備利用率，EqStatus為設備狀態，EqStarttime為設備可用開始時間，EqEndtime為設備可用結束時間，EqPr為根據設備的運行參數以及歷史故障率等得到的設備優先級，EqSt為設備切換時間、EqServce服務能力(遙測、遙控、測軌、全能型等)。

(3)測控任務

屬性定義為：Task={Task1,Task2, …,Taskn}，Taski∈Task，指的是第i個測控任務，i=1,2,3,…,n。Taski={TaIDi,TaNamei,Tasi,Taei,TaSati,TaTyi,Tapli, TaProi,Tacyi,TaDi,TaPi,TaTwi,TaSpliti,TaMinci,TaMaxci,TaMindi,TaMaxdi,TaMinsi,TaMaxsi,UIDi,TaStatusi}。屬性對應的含義分別為：TaID為任務ID，TaName為名稱，Tas為開始時間，Tae為結束時間，TaSat為所屬衛星，TaTy為任務類型(遙測、遙控、注入、測軌)，Tapl為任務性質(正常、應急)，TaPro為任務類別(實戰、聯調)，Tacy為周期性，TaD為任務時長，TaP為任務優先級，TaTw為任務執行階段(長管、應急等)，TaSplit為是否可拆分，TaMinc為最小分解段數，TaMaxc為最大分解段數，TaMind為最小分解弧段時長，TaMaxd為最大分解弧段時長，TaMins為最小分段間隔，TaMaxs為最大分段間隔，UID為用戶偏好ID，TaStatus為執行狀態。

(4)用戶偏好

屬性定義為：UP={UP1,UP2,…,UPn}，UP為用戶偏好集合，UPi∈UP，指的是第i個用戶偏好，i=1,2,3,…,n。UPi={UIDi,Utpi,Ucti}。屬性對應的含義分別為：UID為用戶偏好標識符，Utp為用戶偏好類型(時間偏好、設備偏好等)，Uct為偏好內容。

(5)測站對衛星的可見時間窗口

屬性定義為：Trace={Trace1,Trace2,…,Tracen}，Trace為可見時間窗口集合，Tracei∈Trace，指的是第i個可見時間窗口，i=1,2,3,…,n。Tracei={TIDi,Tsi,Tei,Tqi,Tdi,Tepi,TraSati,Prioi,TSi,Tyi,TeqUri}。屬性對應的含義分別為：TID為可見時間窗口的ID，Ts為窗口開始時間，Te為窗口結束時間，Tq為所屬圈號，Td為持續時長，Tep為所屬設備，TraSat為所屬衛星ID，Prio為優先級(根據設備與衛星的屬性獲得)，TS為使用狀態(未分配、已分配)，Ty為圈次類型(升圈、降圈)，TeqUr為當前設備的利用率。

2.2 約束模型

在多星測控資源調度過程中要考慮的約束具體如下：

1)設備一旦跟蹤一顆衛星，即要跟蹤到設備對該衛星的本段可見時間窗口結束。

2)設備同一時間只能跟蹤一顆衛星。

3)每個測控任務(可拆分任務根據約束完成拆分)只能選擇一個可見時間弧段執行。

4)遙測任務與遙控任務可并行執行。

5)測控設備需與被測控的衛星頻段相符。

6)同一衛星上不同任務執行需有一定的時間間隔，間隔時間由衛星自己的特性決定。

7)設備執行不同衛星的測控任務時，其間隔時間大于或等于測控設備切換時間。

多星測控資源調度的目標為充分利用有限的測控資源滿足衛星測控需求，使得衛星、地面站都發揮最大的應用效能?；谏鲜黾s束和假定，該問題目標用公式描述如下：

max[αTaskR+(1-α)EquipR]

(1)

(2)

(3)

(4)

Taskl∈Satellitep-Taskl+1∈Satellitep≥β

(5)

TaTyi∩EqServcek≠?

(6)

SFp∩DFk≠?

(7)

[Tasi,Taei]∩[Tsj,Tej]≥TaDi+EqStk

(8)

3 基于DNN的測控資源調度算法實現

DNN也叫多層感知機，其經典結構如圖1所示，按層的類型劃分為3類，即輸入層、隱含層及輸出層。其中第一層為輸入層，神經元的個數即為提取的特征值的個數；最后一層為輸出層，神經元的個數為輸出的結果個數，可以為一個，也可以是多個；除此之外均為隱含層，隱含層的層數和隱含層神經元的個數可調，由結果的精度決定。

圖1 DNN結構Fig.1 DNN structure

本節主要描述基于DNN的多星測控調度算法，其核心是對多星測控調度問題的DNN建模。首先根據對多星測控調度問題的實體建模與約束建模，選擇出對調度結果有重大影響的特征值，使用合適的抽取方法對特征值進行離散化處理，即為DNN的輸入。通過對DNN結構的分析可知，DNN的輸入節點是相互獨立的；對抽取的特征進一步分析可知，部分特征可以通過基于簡單規則的預處理進行匹配性判定，因此提出了特征降維算法，對DNN模型進一步優化，縮減其輸入節點數和求解空間，降低訓練難度，提高算法精度。最后完成DNN模型的建立并對該模型進行訓練，以得到可以精確預測調度結果的DNN模型。

3.1 特征值選擇與抽取

DNN的輸入神經元是相互獨立的離散值，為適應其輸入要求，將多星測控調度過程中約束進行抽取并進行離散化處理。結合第二部分的實體模型以及調度過程中的各種約束，提取出7個特征值，具體如下：

1)根據弧段有效時長是否大于或等于任務時長定義時間長度約束標記位D，弧段有效時長大于或等于任務時長時D為1，小于時為0。

2)根據任務所屬衛星和弧段所屬衛星是否匹配，定義衛星匹配標記位S，匹配為1，不匹配為0。

3)根據任務可選設備和弧段所屬設備是否匹配，定義任務可選設備與弧段所屬設備匹配標記位E，匹配為1，不匹配為0。

4)根據任務的類型(遙測、遙控、注入、測軌)和設備服務能力是否匹配，定義任務需求與設備服務能力匹配標記位C，匹配為1，不匹配為0。

5)根據任務、弧段、衛星優先級約束，定義優先級標記位P，取值為衛星、測控設備、任務的優先級之和。

6)根據可見時間弧段所在設備的利用率是否不小于等于80%，定義設備利用率標記位R，大于或等于80%時為1，小于為0。

7)根據資源調度的過程中是否出現沖突，定義沖突標記位U，沖突為1，不沖突為0。

3.2 特征降維算法

通過對上述DNN的描述與特征值的抽取可知，使用DNN解決多星測控調度問題的求解空間非常大，為測控任務與測控資源的全匹配。對抽取的特征值進行了深入的分析，發現其中有些特征值，如時間長度標記位、衛星匹配標記位、設備匹配標記位等，相互獨立，特征符合性可以通過簡單的計算、比較或者匹配完成，無需通過大量數據對DNN訓練，進而學習規則解決。通過該預處理為測控任務初步匹配可能的測控資源，可以去掉無效的測控資源，大大縮減求解空間。同時，可將算法的特征值從7個縮減為3個，即：優先級標記位、沖突標記位、可見時間窗口所在設備的利用率。特征降維后，DNN的節點減少，學習難度減低，算法精度將隨之提高。DNN特征降維算法(DNN feature dimensionality reduction algorithm，DNNFDRA)的具體過程如下：

Input: 衛星集合Satellite, 設備集合Equipment，可見時間窗口集合Trace，任務集合Task，用戶偏好UP

Output: 任務與滿足任務約束的所有可能的可見時間窗口的二元組集合DS〈Taski,Tracej〉

Begin

For每個測控任務Taskido

根據任務所屬衛星TaSat獲取衛星的頻段SF，以及衛星的設備偏好SDS；

該任務的有效設備VaEqi=SDS∩UID∩Equipment；

過濾掉VaEqi中與SF頻段不匹配的設備；

過濾掉與服務能力與任務類型TaTy不匹配的設備，獲取有效設備集合EQ；

獲取EQ中在[Tas,Tae]中的可見時間窗口Tracei；

ForTracei中的每個可見時間窗口TCj

任務所屬衛星TaSat與可見時間窗口的衛星滿足：TraSat: TaSat∩TraSat≠?；

比較任務時長與弧段有效時長滿足:TaD≤[Tas,Tae]∩[Ts,Te]；

將滿足上述比較條件的弧段與Taski組成二元組存入DS；

EndFor

EndFor

Return (DS)

End

DNNFDRA算法將不符合條件的可見時間窗口過濾掉，包括與任務所屬衛星不匹配、不滿足任務時長、不在有效設備集合中、任務類型與設備不匹配及任務所屬衛星頻段不滿足的時間窗口。將過濾后符合條件的可見時間窗口與測控任務組成二元組集合。

根據DNN的輸入特性，對獲取的二元組集合進行處理，抽取優先級標記位、沖突標記位、測控設備資源利用率這3個特征值作為DNN模型的輸入，降低了輸入神經元的緯度，縮小求解空間，同時降低了DNN模型的訓練難度。

3.3 DNN建模及訓練過程

本文采用DNN經典的5層結構模型解決多星測控資源調度問題，包括輸入層，3層隱含層以及輸出層。輸入層神經元即為抽取的特征值，輸出層神經元為DNN計算結果。

DNN的本質是多元線性回歸，可預測新輸入數據的輸出，可以將其看做是一個復雜函數，輸入集為求解空間，輸出即為預測結果，函數的系數等參數便是DNN網絡結構。為獲取預測效果較好的網絡結構，需通過大量、高質量、多特征的訓練數據有針對性的訓練。訓練數據由歷史測控調度數據處理后得到：手動去掉調度失敗的任務，使得測控任務的調度率為100%。其DNN訓練流程如圖2所示。為達到訓練目標，DNN使用損失函數度量訓練數據的輸出損失，然后對損失函數優化求極小值，最終獲得的線性系數矩陣W和偏移向量b即為DNN模型，求解過程一般使用梯度下降法迭代完成，當達到最大迭代次數或者停止迭代的閾值時停止。

圖2 DNN訓練流程Fig.2 DNN training flowchart

4 試驗及結果分析

本文結合目前空間衛星分布情況和中國陸基測控站布局情況對算法進行驗證。通過對比傳統調度方法(TA)與DNN調度方法的性能，驗證DNN的效能。其中，這里的傳統調度方法是目前應用較廣的基于資源綜合加權優先級的調度方法[17]。通過比較DNN調度方法與傳統方法(TA)的任務滿足度與資源利用率，驗證DNN算法的可行性及有效性；通過比較基于DNN的多星資源測控調度方法(MSTCS)和基于降維預處理的DNN調度方法(MSTCS_DF)的調度時間驗證MSTCS_DF的效能。

4.1 試驗場景

利用STK軟件模擬100顆真實運行中的高中低軌衛星，其中中低軌衛星由全球星系統和銥星系統中的衛星組成，高軌衛星由北斗衛星組成；模擬中國陸基測控站中喀什站、渭南站、基律納站等15套地面站測控設備，每顆衛星的測控任務為每天升圈測2圈次，降圈測2圈次，模擬未來測控網管理系統面臨的“星多站少”的供求關系。

試驗過程中準備了5組7天的任務數據，分別針對MSTCS、MSTCS_DF和TA方法進行測試。

4.2 試驗結果及分析

使用上述試驗數據，根據圖2對DNN模型進行訓練。使用DNN經典結構，即1個輸入層，3個隱含層，1個輸出層，每層具體的神經元個數以及激活函數如表1所示。

表1 DNN模型的層數、神經元數以及激活函數

對訓練好的DNN，用5組7天的測控數據對多星測控任務分配資源，通過計算測控任務的加權滿足度、資源加權平均利用率、算法運行時間3個方面對提出的算法進行結果分析，測試結果的平均值如表2和圖3所示。

從表2與圖3中可以看出，在任務滿足度與資源利用率方面，DNN算法與傳統算法TA性能都很好，且MSTCS_DF更為優越，說明使用DNN解決多星測控資源調度是可行且有效的。在調度時間方面，降維后的MSTCS_DF算法用時約縮減為MSTCS算法用時的17%，是傳統算法用時的70%，說明MSTCS_DF算法具有高效性。

表2 測控數據的測試結果

圖3 DNN測控數據的測試結果Fig.3 Test result of TT&C data

下面從優先級與資源分配的關系方面分析DNN算法(包括MSTCS算法和MSTCS_DF算法)的調度結果。圖4(a)為可見時間窗口的優先級值與資源分配的關系，可以看出，可見窗口的優先級值越高，資源被分配的幾率也越高；圖4(b)為測控任務的優先級值與資源分配的概率，可以看出，任務優先級值越高，其被分配資源的概率也越高。綜上可得，該調度結果符合一般調度的分配規律，DNN學習效果較好。

圖4 優先級與資源分配的關系Fig.4 The relationship between priority and resource allocation

綜上可以看出，DNN方法適用于解決大規模多星測控調度任務，且在性能上更優越，說明DNN方法在處理多星測控資源調度方面適應和擴展性良好。

5 結論

多星測控調度問題是復雜多約束、高沖突的NP組合優化問題，計算復雜度高，強度大，已有算法對多星測控調度適應性較差。本文分析了航天測控資源調度問題的特點和工程需求，針對問題求解中涉及的資源、測控任務以及約束，建立了DNN模型，并通過對測控任務初步資源分配，減少了算法的輸入規模和輸入特征的維度。然后通過大量歷史數據的迭代訓練獲得DNN模型參數。最后用STK模擬真實應用場景，并通過大量試驗驗證了算法的高效性。此算法提高了測控任務的資源分配速率、效率以及滿足度，且具有良好的適應性，能充分適應不同類型、規模的衛星測控任務資源分配問題。

為進一步提高多星測控調度的精度，下一步將深入分析影響多星測控調度的影響因子以及影響因子的優先級值，同時優化DNN的訓練過程，考慮使用遺傳算法或者模擬退火算法訓練神經網絡。