按需申請模式下的中繼衛(wèi)星任務(wù)規(guī)劃模型與算法設(shè)計

，，

1.北京空間信息中繼傳輸技術(shù)研究中心，北京 100094 2.北京衛(wèi)星導(dǎo)航中心，北京 100094

中繼衛(wèi)星任務(wù)規(guī)劃是按照各用戶提交的服務(wù)需求，在滿足特定約束的前提下，指定一定使用時長的中繼衛(wèi)星資源，以支持用戶型號完成數(shù)傳、測控等任務(wù)的活動[1-3]。結(jié)合具體應(yīng)用背景，采用高效分配模式以制定合理的資源使用計劃，這對于充分發(fā)揮中繼衛(wèi)星系統(tǒng)的服務(wù)能力至關(guān)重要[4-5]。

當(dāng)前，隨著用戶型號的不斷增加，持續(xù)的任務(wù)增長對中繼衛(wèi)星系統(tǒng)造成了較大的服務(wù)壓力。在現(xiàn)有系統(tǒng)配置條件下，采用包括改進(jìn)申請模式、調(diào)整計劃流程、提升算法性能等手段，成為進(jìn)一步挖掘系統(tǒng)服務(wù)潛力的有效途徑[6-8]。其中，申請模式對于計劃流程的設(shè)計和優(yōu)化算法的選擇都有決定性作用，其主要內(nèi)容包括確定資源申請的時機(jī)和任務(wù)需求的描述方式。

在資源申請時機(jī)方面，周申請(長期申請)和臨時申請(短期申請)是較為常見的申請方式。周申請方式要求用戶提前一周確定需求集中提交，而中繼衛(wèi)星規(guī)劃系統(tǒng)則以周為單位提前向用戶發(fā)布可用資源時段。臨時申請方式允許用戶以隨到隨占用的方式提交申請，其所面向的僅為規(guī)劃系統(tǒng)釋放的可用資源。兩種方式各有優(yōu)缺點(diǎn)，通常結(jié)合使用，即主用長期申請方式，但以短期申請方式提交補(bǔ)充需求。在實際任務(wù)中，兩種申請方式一般要求規(guī)劃系統(tǒng)以同步周期釋放各中繼星的可用時段，該模式已逐漸難以適應(yīng)任務(wù)需求的多樣性，不利于發(fā)揮不同軌位中繼星的能力優(yōu)勢。

在任務(wù)需求描述方面，“點(diǎn)殺”式申請較為常見，即用戶為每個申請指定唯一占用的中繼星和固定的捕跟時段，規(guī)劃系統(tǒng)僅依據(jù)事先擬定的優(yōu)先級準(zhǔn)則判定申請是否得到滿足。但實際上，用戶往往并不關(guān)心任務(wù)執(zhí)行的具體時段和中繼星，而僅要求任務(wù)在某個時間范圍內(nèi)得到執(zhí)行即可。因此，“點(diǎn)殺”式申請實質(zhì)上削弱了中繼衛(wèi)星資源分配的靈活性，降低了計劃調(diào)整的可行空間，制約了規(guī)劃系統(tǒng)消解任務(wù)沖突的能力。為此，對任務(wù)時限性特征的精細(xì)化描述尤為必要，它是規(guī)劃系統(tǒng)優(yōu)化資源調(diào)配的重要依據(jù)。傳統(tǒng)的任務(wù)申請在時效性描述方面，僅對捕跟時段進(jìn)行明確，而將計劃響應(yīng)時限和計劃變更時限則作為隱含

條件。例如，在周申請中，計劃響應(yīng)時限通常為計劃提交后的1天，而在臨時申請中，計劃響應(yīng)時限通常為計劃提交后的若干分鐘。

按需申請模式采用異步資源釋放周期方式，可將應(yīng)急任務(wù)需求的稀缺資源時段采用短期申請方式發(fā)布，而其余資源時段采用長期申請方式發(fā)布。在任務(wù)申請描述上，按需申請模式僅要求用戶填寫必要的需求要素，而諸如確定具體執(zhí)行時段和選擇服務(wù)資源等工作則全部交由規(guī)劃系統(tǒng)完成。對于用戶而言，按需申請是一種更為友好的申請方式。

本文以按需申請模式為研究背景，探討從任務(wù)特征分析到規(guī)劃模型構(gòu)建，再到調(diào)度算法設(shè)計的具體實現(xiàn)方法。從現(xiàn)實用戶申請中提取能夠表述任務(wù)共性需求的特征要素，并對其中的復(fù)雜需求進(jìn)行轉(zhuǎn)換，形成可供規(guī)劃系統(tǒng)集中處理的簡單任務(wù)。在問題建模中，考慮異步資源釋放周期對任務(wù)申請的影響，歸納出任務(wù)規(guī)劃所需考慮的主要約束。在算法設(shè)計中，基于沖突風(fēng)險規(guī)避策略進(jìn)行資源時段選擇，根據(jù)待規(guī)劃對象的需求時段分布，為用戶需求指派低沖突風(fēng)險的執(zhí)行時段。

1 任務(wù)需求的特征描述

為便于后續(xù)闡述，對文中出現(xiàn)的常用符號進(jìn)行定義，如表1所示。

表1 相關(guān)符號定義Table 1 Definition of main notations

續(xù)表1

1.1 特征要素分類

在描述相同需求時，可能存在多種描述方式，其需求描述的非唯一性可概括為描述特征組合方式的多樣性。一般而言，這些特征之間可能存在相互換算關(guān)系，并非完全獨(dú)立。為實現(xiàn)用戶需求的快速輸入和集中規(guī)劃，從眾多描述特征中提取簡單、獨(dú)立，而又能最大程度涵蓋用戶原始需求信息的特征要素就顯得極為必要[9-11]。

定義1：將獨(dú)立的不可再分的任務(wù)稱為簡單任務(wù)(或元任務(wù))，將非獨(dú)立或需要通過分解轉(zhuǎn)化的任務(wù)稱為復(fù)雜任務(wù)。

將簡單任務(wù)的描述特征稱為基本特征要素，復(fù)雜任務(wù)可由基本特征要素和附加特征要素組合的形式描述。為實現(xiàn)統(tǒng)一建模，應(yīng)保證任務(wù)描述的統(tǒng)一性，這就要求對復(fù)雜任務(wù)進(jìn)行預(yù)處理，使其分解為簡單任務(wù)。

1.2 基本特征要素

在按需申請模式下，描述簡單任務(wù)的基本特征要素主要包括：

(1)提交時刻

用戶向中繼衛(wèi)星規(guī)劃系統(tǒng)提交任務(wù)申請的時刻。在周申請模式下，任務(wù)申請通常在約定時段內(nèi)按批到達(dá)，往往具有相同提交時刻。在高動態(tài)應(yīng)急任務(wù)場景下，任務(wù)申請以流的形式逐個到達(dá)，提交時刻具有隨機(jī)性。

(2)用戶中心/用戶型號

中繼衛(wèi)星提供數(shù)據(jù)傳輸?shù)姆?wù)對象，一個用戶中心可能擁有多個用戶型號，相同用戶型號的不同業(yè)務(wù)也可能隸屬多個用戶中心。

(3)任務(wù)類型/優(yōu)先級

任務(wù)類型是對任務(wù)性質(zhì)的直接描述，能夠直觀體現(xiàn)任務(wù)執(zhí)行價值和保障緊迫程度等。通常情況下，任務(wù)優(yōu)先級與任務(wù)類型密切相關(guān)，其量化方法已有大量研究成果，本文不再贅述。

(4)需求時段

用戶期望任務(wù)執(zhí)行的時間范圍，以滑動窗口的形式表示：

(5)捕跟時長/數(shù)據(jù)量

對于測控類任務(wù)，捕跟時長主要取決于用戶期望的連續(xù)跟蹤時長；對于數(shù)傳類任務(wù)，捕跟時長主要依賴于任務(wù)傳輸數(shù)據(jù)量和中繼衛(wèi)星系統(tǒng)的數(shù)據(jù)傳輸速率。

定義2：捕跟時長加上預(yù)置任務(wù)模板的額定保護(hù)時長(狀態(tài)準(zhǔn)備時長和狀態(tài)恢復(fù)時長)，即為實際占用資源時間，稱為任務(wù)申請的服務(wù)時長。

在規(guī)劃過程中，資源占用量往往換算成服務(wù)時長的形式。對于同一個任務(wù)申請，在不同中繼資源上執(zhí)行所采用的任務(wù)模板可能不同，因此服務(wù)時長也存在差異。

若指派taski在TDRSk上執(zhí)行，所需的持續(xù)服務(wù)時長為：

式中：RPTi,k為系統(tǒng)準(zhǔn)備時長；DTLengthi,k為持續(xù)捕跟時長；CPTi,k為狀態(tài)恢復(fù)時長。

(6)資源偏好

在按需申請模式下，用戶可以不指定任務(wù)占用的中繼星，規(guī)劃系統(tǒng)默認(rèn)將所有符合約束條件的中繼資源參與分配。但實際應(yīng)用中，考慮到中繼星能力的差異，用戶對期望占用的中繼資源存在偏好。為便于算法設(shè)計，將任務(wù)的資源偏好與需求時段綁定，即在提交滑動窗口時，區(qū)分為在各中繼星上的可滑動窗口。

(7)計劃響應(yīng)截止期

無論任務(wù)需求是否得到滿足，都應(yīng)及時將計劃結(jié)果反饋至用戶。計劃響應(yīng)截止期是規(guī)劃系統(tǒng)向用戶發(fā)送計劃結(jié)果的時限，也是確定中繼資源規(guī)劃時刻點(diǎn)的重要依據(jù)。

(8)計劃變更截止期

用戶能夠接受的計劃變更時限，對任務(wù)執(zhí)行方案的調(diào)整應(yīng)在該時限內(nèi)完成，可作為重調(diào)度時，選擇任務(wù)對象的依據(jù)。

在上述基本特征中，提交時刻、計劃響應(yīng)截止期、計劃變更截止期、滑動窗口、可視窗口、捕跟時長等屬于時效性特征，如圖1所示。

令MFPTi=PBDi-ATi，稱為taski的容忍計劃反應(yīng)時長。若MFPTi≤24 h，taski為短期任務(wù)，否者為長期任務(wù)。令MFDTi=DTEndi-ATi，稱為taski的容忍任務(wù)反應(yīng)時長。若MFDTi≤1 h，taski為快響任務(wù)，否則為常規(guī)任務(wù)。

1.3 附加特征要素

對于復(fù)雜任務(wù)需求的描述，除了要使用簡單需求描述特征外，還需要利用諸如關(guān)聯(lián)性、可分性、周期性等附加特征要素。

(1)關(guān)聯(lián)性

任務(wù)的執(zhí)行情況受其他任務(wù)影響，主要包括狀態(tài)關(guān)聯(lián)和時序關(guān)聯(lián)兩種類型。狀態(tài)關(guān)聯(lián)是指任務(wù)間的執(zhí)行狀態(tài)存在相互制約，可分為共生關(guān)聯(lián)和獨(dú)占關(guān)聯(lián)。時序關(guān)聯(lián)是指任務(wù)間的執(zhí)行弧段存在相互制約，可分為間隔關(guān)聯(lián)或順序關(guān)聯(lián)。

(2)可分性

任務(wù)可切割為多個子任務(wù)執(zhí)行，子任務(wù)間可完全獨(dú)立，也可具有關(guān)聯(lián)性。任務(wù)分割需明確兩項參數(shù)，即切割的粒度下限和數(shù)量上限。粒度下限是指切割后子任務(wù)應(yīng)具有的最小捕跟時長/數(shù)據(jù)量，而數(shù)量上限是指最多允許的切割份數(shù)(子任務(wù)數(shù)量)。

(3)周期性

在一定時限內(nèi)的重復(fù)需求可作為周期性任務(wù)，既適用于描述常態(tài)化任務(wù)申請，也適用于描述臨時性的應(yīng)急需求。

在以上附加特征要素中，關(guān)聯(lián)性約束可在規(guī)劃模型中直接體現(xiàn)；具有可分性特征的任務(wù)采用特定分解算法，分解為多個簡單子任務(wù)，各子任務(wù)間具有關(guān)聯(lián)性；具有周期性特征的任務(wù)，也可按照其需求頻率，復(fù)制為多個非周期性的簡單子任務(wù)。因此，具備上述需求特征的復(fù)雜任務(wù)均可通過預(yù)處理轉(zhuǎn)換為簡單任務(wù)。在后續(xù)問題建模和算法設(shè)計中，本文僅針對簡單任務(wù)的情況進(jìn)行研究。

2 問題描述與建模

在整個任務(wù)周期內(nèi)，各用戶中心提交的新申請不斷到達(dá)，匯聚至等待處理任務(wù)隊列中。中繼衛(wèi)星任務(wù)規(guī)劃系統(tǒng)根據(jù)申請?zhí)卣?、資源狀態(tài)、調(diào)度規(guī)則等信息安排調(diào)度事件序列，完成對所有任務(wù)申請的處理。在每次調(diào)度觸發(fā)前，系統(tǒng)計算本輪調(diào)度追加釋放的可用資源時段，并選擇參與調(diào)度的任務(wù)對象，而調(diào)度事件本身也需耗用一定的時間。調(diào)度的結(jié)果是明確用戶申請的滿足情況，制定中繼資源的使用計劃[12-13]。每次調(diào)度后，均以新的任務(wù)狀態(tài)更新之前任務(wù)狀態(tài)。

如圖2所示，設(shè)調(diào)度事件序列為SL={Sl1,Sl2,…,SlPNum}，對于第i次調(diào)度事件sli，所需占用的時段為SLWi=[SLBegini,SLEndi]，其中SLBegini和SLEndi分別為開始調(diào)度時刻和完成調(diào)度并反饋計劃時刻。在sli中，向用戶追加釋放TDRSk的可用時段FTWi,k=[FTBegini,k,FTEndi,k]，其中FTBegini,k,FTEndi,k分別為FTWi,k開始時刻和結(jié)束時刻。通常情況下，規(guī)劃系統(tǒng)完成一次調(diào)度所需時長較為恒定，不妨設(shè)為SLT=SLEndi-SLBegini，i=1,2,…,PNum。

設(shè)當(dāng)前調(diào)度事件為slnow，向用戶累計釋放的TDRSk可用時段為：

在slnow開始后，對已到達(dá)任務(wù)依據(jù)其規(guī)劃狀態(tài)和執(zhí)行狀態(tài)進(jìn)行分類。

1)完成服務(wù)任務(wù)集：當(dāng)前已執(zhí)行完畢的任務(wù)集合，表示為FTaskSetnow={taski|(VSi=0)∨(ASi=1∧ETEndi≤SLBegini)}。

2)當(dāng)前服務(wù)任務(wù)集：當(dāng)前已進(jìn)入執(zhí)行狀態(tài)，但尚未執(zhí)行完畢的任務(wù)集合，表示為ETaskSetnow= {taski|(PSi=1)∧(ETWi∩SLWnow≠?)}。

3)等待服務(wù)任務(wù)集：當(dāng)前已分配資源，但尚待執(zhí)行的任務(wù)集合，表示為WTaskSetnow={taski|(PSi=1)∧(ETBegini>SLBeginnow)}。

4)未規(guī)劃任務(wù)集：當(dāng)前尚未參與規(guī)劃且未喪失執(zhí)行可能性的任務(wù)集合，表示為NPlanSetnow={taski|(ASi=0)∧(VSi=1)}。

5)拒絕服務(wù)任務(wù)集：當(dāng)前暫時未被滿足且未喪失執(zhí)行可能性的任務(wù)集合，表示為DTaskSetnow={taski|(PSi=0)∧(VSi=1)}。

其中，判斷taski規(guī)劃價值的方法如下：

在上述集合中，對ETaskSetnow中任務(wù)計劃的調(diào)整可能需要崗位人員手動干預(yù)完成，該過程具有較高的誤操作風(fēng)險，且耗時較長，因此本文不考慮搶占服務(wù)的情況。對待規(guī)劃任務(wù)集WPlanSetnow的構(gòu)造方法如下：

WPlanSetnow=WTaskSetnow∪DTaskSetnow∪

從中繼資源使用者的角度考慮，所需優(yōu)化的目標(biāo)應(yīng)為各用戶中心的任務(wù)滿足率，記為：

式中：Q為決策矩陣X的可行域。

定義3：構(gòu)造區(qū)間長度度量函數(shù)dim()，對于任意時段tsi=[tbi,tei]，記dim(tsi)=tei-tbi。特別地，若tsi=?，令dim(tsi)=0。

從中繼資源管理者的角度考慮，優(yōu)化目標(biāo)為各中繼星的資源使用率，記為：

調(diào)度過程中需考慮的主要約束包括：

約束1：對于本輪調(diào)度選取的任務(wù)對象，應(yīng)保證在其計劃響應(yīng)截止期/調(diào)整截止期內(nèi)，完成規(guī)劃：

約束2：每個任務(wù)最多被執(zhí)行一次，且只能選擇由一顆中繼星執(zhí)行：

約束3：資源具有獨(dú)占性，在某顆中繼星上，同一時刻最多執(zhí)行一圈任務(wù)：

約束4：對于被執(zhí)行的任務(wù)，占用資源的時間不低于所需持續(xù)服務(wù)時長：

約束5：任務(wù)的捕跟時段應(yīng)處于其滑動可視窗口內(nèi)：

約束6：同一用戶型號不能同時占用多顆中繼衛(wèi)星：

DTWi∩DTWi′=?,

約束7：在計劃方案制定過程中，非獨(dú)立任務(wù)的關(guān)聯(lián)性應(yīng)得到滿足：

約束8：僅將本輪調(diào)度前已累計釋放的中繼資源分配給任務(wù)：

[STBegini,STBEndi]∩VRTWnow≠?,

每一輪調(diào)度，均為在滿足以上約束的可行解域中尋找優(yōu)化解的過程。調(diào)度完成后，更新任務(wù)的可執(zhí)行狀態(tài)、執(zhí)行資源、執(zhí)行時段等，從而形成新的計劃方案。

3 沖突風(fēng)險評估與規(guī)避

由于中繼衛(wèi)星資源的稀缺性，任務(wù)沖突在規(guī)劃過程中廣泛存在，沖突消解一直是計劃制定與資源調(diào)配的難點(diǎn)[14-15]。在資源分配前，評估可能出現(xiàn)的沖突風(fēng)險，可作為資源時段選擇的重要依據(jù)。

3.1 沖突任務(wù)檢測

對于待規(guī)劃任務(wù)，可能存在的沖突對象包括當(dāng)前服務(wù)任務(wù)、等待服務(wù)任務(wù)和其他待規(guī)劃任務(wù)。在非搶占規(guī)則下，當(dāng)前服務(wù)任務(wù)的狀態(tài)不受待規(guī)劃任務(wù)的影響，其占用的資源對于待規(guī)劃任務(wù)完全不可用；對于等待服務(wù)任務(wù)，其預(yù)先分配的資源具備更改可能；而對于其他待規(guī)劃任務(wù)，其需求僅作為當(dāng)前待規(guī)劃任務(wù)優(yōu)選執(zhí)行時段的考慮因素。因此，將與當(dāng)前服務(wù)任務(wù)、等待服務(wù)任務(wù)和其他待規(guī)劃任務(wù)形成的沖突，分別稱為強(qiáng)沖突、弱沖突和需求沖突。

定義3：對于?taski∈WPlanSetnow，在TDRSk上的強(qiáng)沖突任務(wù)集為：

CETaskSeti,k={taskj|VTWSi,k∩STWSi,k∩

定義4：對于?taski∈WPlanSetnow，在TDRSk上的弱沖突任務(wù)集為：

CWTaskSeti,k={taskj|STWSi,k∩ETWj≠?,

定義5：對于?taski∈WPlanSetnow，在TDRSk上的需求沖突任務(wù)集為：

3.2 損失機(jī)會評估

在不變更WTaskSetnow中任務(wù)計劃方案的前提下，計算taski在TDRSk上的可用時段為：

當(dāng)不存在滿足taski最小捕跟時長要求的可用時段時，可調(diào)整WTaskSetnow中任務(wù)的原方案。下面計算taski在TDRSk上的可協(xié)調(diào)時段：

若安排taski在TDRSk上執(zhí)行，其可選的資源時段集合VCTWi,k為：

如果TDRSk在t∈VCTWi,k時刻被taski占用，則對于其他任務(wù)taskj∈WPlanSetnow，該時刻資源呈現(xiàn)不可用狀態(tài)，即taskj損失在t時刻被TDRSk執(zhí)行的機(jī)會。

定義6：在將WPlanSetnow中對TDRSk在t時刻存在服務(wù)需求的任務(wù)數(shù)量，稱為對t時刻TDRSk的需求重疊度。

通常情況下，安排某個任務(wù)在具有較高需求重疊度的時段執(zhí)行，將導(dǎo)致后續(xù)任務(wù)損失較多的潛在執(zhí)行機(jī)會，進(jìn)而降低后續(xù)任務(wù)的可執(zhí)行性。因此，在選擇執(zhí)行時段時，應(yīng)優(yōu)先選擇覆蓋需求重疊度低的時段。

設(shè)taski為當(dāng)前待調(diào)度任務(wù)，此時對t∈VCTWi,k存在服務(wù)需求的待規(guī)劃任務(wù)集合為：

CReqSeti,k(t)={taskjt∈VCTWi,k∩STWSj

對t時刻TDRSk的需求重疊度為：

式中：‖·‖用于度量集合中的元素個數(shù)。

若安排taski在tsi=[tbi,tei]內(nèi)由TDRSk執(zhí)行，由此造成其他待規(guī)劃任務(wù)損失的潛在執(zhí)行機(jī)會為：

完成損失機(jī)會評估的關(guān)鍵在于構(gòu)造出需求重疊系度分布函數(shù)。由于其為階梯函數(shù)，因此可采用兩個離散序列，即分布函數(shù)上的拐點(diǎn)和拐點(diǎn)間的重疊度描述。

構(gòu)建序列KNi,k和CIi,k的基本步驟如下：

1:Let set CW←VCTWi,k,KNi,k←?,CNi,k←?;

2:Construct set CQTaskSeti,kby Eq.(17);

3:for each taskjfrom set CQTaskSeti,kdo

4:Let a=VCTWi,k∩STWSj,kand insert a to set CW;

5:endfor

6: Remove all time points from CW to KNi,k,and delete

the same one;

7: Sort all point in set KNi,kby increasing order, and

8:forj←1 tom-1 do

10:for each taskjfrom set CQTaskSeti,kdo

11:if Var∩STWSj,k≠? then

13:endif

14:endfor

16:endfor

算法中，Line 1對離散序列KNi,k和CIi,k進(jìn)行初始化；Line 2檢測存在需求沖突的任務(wù)；Line 3～5完成需求沖突任務(wù)集的構(gòu)造；Line 6～7識別CNFi,k(t)的拐點(diǎn)；Line 8～15統(tǒng)計相鄰拐點(diǎn)間的重疊度。

3.3 執(zhí)行時段優(yōu)選

在可選時段集合中，基于最小損失機(jī)會原則為taski指派執(zhí)行時段，計算方法如下：

定理4：基于沖突風(fēng)險規(guī)避策略獲取taski在TDRSk上服務(wù)時段的最優(yōu)解集合，其中必然存在某個解Etwi,k=[Etbi,k,Etei,k]，滿足(Etbi,k∈KNi,k)∨(Etei,k∈KNi,k)。

根據(jù)上述結(jié)論，可采用算法遍歷需求重疊系度分布函數(shù)的拐點(diǎn)，以獲取etwi,k在最小損失機(jī)會原則下的最優(yōu)解，基本步驟如下：

1:Let OSTW←?,OSTL←?,CTWNum←0;

4:CTWNum←CTWNum+1;

6: Calculate OStlCTWNum←LTLi,k(OStwCTWNum) by Eq.

(20);

7: Insert OStwCTWNumto OSTW, and add OStlCTWNumto

OSTL;

8:end if

10:CTWNum←CTWNum+1;

12: Calculate OStlCTWNum←LTLi,k(OStwCTWNum) by Eq.

(20);

13: Insert OStwCTWNumto OSTW, and add OStlCTWNum

to OSTL;

14:endif

15:endfor

16:if OSTW≠? then

17: Asumme OStlh=min {OSTL}, and let etwi,k←

OStwh;

18:else

19:etwi,k←?;

20:end

算法中，Line 2～15檢測至少有一個端點(diǎn)包含于KNi,k的可用服務(wù)時段OSTW；Line 16～20從OSTW中選出損失服務(wù)機(jī)會時長最小的時段指派給etwi,k，若不存在可用服務(wù)時段，則etwi,k為空。

4 結(jié)束語

采用按需申請模式可有效提升規(guī)劃系統(tǒng)資源協(xié)調(diào)的靈活性，增加任務(wù)申請滿足概率。本文針對新模式下的中繼衛(wèi)星任務(wù)規(guī)劃模型與優(yōu)化算法展開研究，提出了用戶需求的基本描述要素，歸納了資源分配中所需考慮的主要約束，從使用者和管理者的角度分別提出了優(yōu)化目標(biāo)。在此基礎(chǔ)上，基于沖突風(fēng)險規(guī)避策略設(shè)計出問題的優(yōu)化算法，給出了算法中采用的沖突檢測模型和損失機(jī)會評估模型。所采用的啟發(fā)式算法具有低時間復(fù)雜度，有利于計劃方案的快速生成。但需要指出的是，本文雖然構(gòu)建了異步資源釋放周期條件下的任務(wù)規(guī)劃模型，但并未給出資源釋放周期的確定方法，該部分內(nèi)容將在后續(xù)研究中作進(jìn)一步探討。

References)

[1] WANG J S, QI X. China′s data relay satellite system served for manned spaceflight[J]. Science China Technological Sciences, 2014, 44(3):235-242.

[2] ZHANG S J, CAO X B. Coordinated attitude control for a tracking and data relay satellite with mobile antennas[J]. Aircraft Engineering and Aerospace Technology, 2004, 76(4): 414-419.

[3] 李于衡, 黃惠明, 鄭軍. 中繼衛(wèi)星系統(tǒng)應(yīng)用效能提升技術(shù)[J]. 中國空間科學(xué)技術(shù), 2014, 34(1): 71-76.

LI Y H，HUANG H M，ZHENG J. Efficiency improvement technologies for tracking and data relay satellite system[J]. Chinese Space Science and Technology, 2014, 34(1): 71-76(in Chinese).

[4] MARCO A. Heuristic scheduling of the DRS communication system[J]. Engineering Applications of Artificial Intelligence, 1995, 8(2): 147-156.

[5] 陳英武, 方炎申, 顧中舜. 中繼衛(wèi)星單址鏈路調(diào)度模型與算法研究[J]. 中國空間科學(xué)技術(shù), 2007, 27(2): 52-58.

CHEN Y W, FANG Y S, GU Z S. Algorithms for the single access link scheduling model of tracking and data relay satellite system[J]. Chinese Space Science And Technology, 2007, 27(2): 52-58(in Chinese).

[6] 王海波, 徐敏強(qiáng), 王日新, 等. 基于蟻群優(yōu)化-模擬退火的天地測控資源聯(lián)合調(diào)度[J]. 宇航學(xué)報, 2012, 33(11): 1636-1645.

WANG H B, XU M Q, WANG R X, et.al. Solvingspace and ground TT&C resources integrated scheduling problem with ant colony optimization-simulated annealing algorithm[J]. Journal of Astronautics, 2012, 33(11): 1636-1645(in Chinese).

[7] WU B, LI Y X, HUANG Y X. Optimal scheduling of TT&C network resources based on genetic algorithm[J]. Journal of Astronautics, 2006, 27(6): 1132-1136.

[8] 張娜,柯良軍,馮祖仁. 一種新的衛(wèi)星測控資源調(diào)度模型及其求解算法[J].宇航學(xué)報, 2009, 30(5):1636-1645.

ZHANG N,KE L J,FENG Z R. A new model for satellite TT&C resource scheduling and its solution algorithm[J]. Journal of Astronautics, 2009, 30(5):1636-1645(in Chinese).

[9] 賀川, 孟憲貴, 祝轉(zhuǎn)民, 等. 基于執(zhí)行時段滑動調(diào)整策略的中繼衛(wèi)星任務(wù)規(guī)劃算法設(shè)計[J]. 飛行器測控學(xué)報, 2015, 34(3): 246-253.

HE C, MENG X G, ZHU Z M, et al.Research on the tasks programming algorithm for tdrs based on the slide adjustment strategy of execution time[J]. Journal of Spacecraft TT&C Technology, 2015, 34(3): 246-253(in Chinese).

[10] TOSCO G, CRONE G, ROEDERER A G.. Analysis of the S-band communication link between the automated transfer vehicle and the data relay satellites in the presence of the space station[J]. IEEE Antennas and Propagation Magazine, 2002, 44(6): 12-23.

[11] VAZQUEZ A J , ERWIN R S. On the tractability of satellite range scheduling[J]. Optimization Letters, 2014, 9(2):311-327.

[12] LIU X L, BAI B C, CHEN Y W. Multi satellites scheduling algorithm based on task merging mechanism[J]. Applied Mathematics and Computation, 2014, 230(2): 687-700.

[13] WU G H, LIU J,MA M H. A two-phase scheduling method with the consideration of task clustering for earth observing satellites[J]. Computers & Operations Research, 2013, 40(7): 1884-1894.

[14] KOLICI V, HERRERO X, XHAFA F. Local search and genetic algorithms for satellite scheduling problems[C]∥Proceedings of the 8th IEEE International Conference on Broadband, Wireless Computing, Communication and Applications. Compiegne, 2013: 328-335.

[15] 劉洋, 賀仁杰, 譚躍進(jìn). 基于約束滿足的多衛(wèi)星調(diào)度模型研究[J]. 系統(tǒng)工程與電子技術(shù), 2004, 26(8): 1076-1079.

LIU Y, HE R J, TAN Y J. Modeling the scheduling problem of multi-satellites based on the constraint satisfaction[J]. Systems Engineering and Electronics, 2004, 26(8): 1076-1079(in Chinese).