，，

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

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

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

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

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

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

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

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

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

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

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

續(xù)表1

1.1 特征要素分類

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

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

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

1.2 基本特征要素

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

(1)提交時(shí)刻

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

(2)用戶中心/用戶型號(hào)

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

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

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

(4)需求時(shí)段

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

(5)捕跟時(shí)長(zhǎng)/數(shù)據(jù)量

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

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

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

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

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

(6)資源偏好

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

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

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

(8)計(jì)劃變更截止期

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

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

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

1.3 附加特征要素

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

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

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

(2)可分性

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

(3)周期性

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

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

2 問(wèn)題描述與建模

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

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

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

在slnow開(kāi)始后，對(duì)已到達(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)前暫時(shí)未被滿足且未喪失執(zhí)行可能性的任務(wù)集合，表示為DTaskSetnow={taski|(PSi=0)∧(VSi=1)}。

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

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

WPlanSetnow=WTaskSetnow∪DTaskSetnow∪

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

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

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

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

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

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

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

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

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

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

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

DTWi∩DTWi′=?,

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

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

[STBegini,STBEndi]∩VRTWnow≠?,

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

3 沖突風(fēng)險(xiǎn)評(píng)估與規(guī)避

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

3.1 沖突任務(wù)檢測(cè)

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

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

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

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

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

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

3.2 損失機(jī)會(huì)評(píng)估

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

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

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

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

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

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

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

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

對(duì)t時(shí)刻TDRSk的需求重疊度為：

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

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

完成損失機(jī)會(huì)評(píng)估的關(guān)鍵在于構(gòu)造出需求重疊系度分布函數(shù)。由于其為階梯函數(shù)，因此可采用兩個(gè)離散序列，即分布函數(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對(duì)離散序列KNi,k和CIi,k進(jìn)行初始化；Line 2檢測(cè)存在需求沖突的任務(wù)；Line 3～5完成需求沖突任務(wù)集的構(gòu)造；Line 6～7識(shí)別CNFi,k(t)的拐點(diǎn)；Line 8～15統(tǒng)計(jì)相鄰拐點(diǎn)間的重疊度。

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

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

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

根據(jù)上述結(jié)論，可采用算法遍歷需求重疊系度分布函數(shù)的拐點(diǎn)，以獲取etwi,k在最小損失機(jī)會(huì)原則下的最優(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檢測(cè)至少有一個(gè)端點(diǎn)包含于KNi,k的可用服務(wù)時(shí)段OSTW；Line 16～20從OSTW中選出損失服務(wù)機(jī)會(huì)時(shí)長(zhǎng)最小的時(shí)段指派給etwi,k，若不存在可用服務(wù)時(shí)段，則etwi,k為空。

4 結(jié)束語(yǔ)

采用按需申請(qǐng)模式可有效提升規(guī)劃系統(tǒng)資源協(xié)調(diào)的靈活性，增加任務(wù)申請(qǐng)滿足概率。本文針對(duì)新模式下的中繼衛(wèi)星任務(wù)規(guī)劃模型與優(yōu)化算法展開(kāi)研究，提出了用戶需求的基本描述要素，歸納了資源分配中所需考慮的主要約束，從使用者和管理者的角度分別提出了優(yōu)化目標(biāo)。在此基礎(chǔ)上，基于沖突風(fēng)險(xiǎn)規(guī)避策略設(shè)計(jì)出問(wèn)題的優(yōu)化算法，給出了算法中采用的沖突檢測(cè)模型和損失機(jī)會(huì)評(píng)估模型。所采用的啟發(fā)式算法具有低時(shí)間復(fù)雜度，有利于計(jì)劃方案的快速生成。但需要指出的是，本文雖然構(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]. 中國(guó)空間科學(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]. 中國(guó)空間科學(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)化-模擬退火的天地測(cè)控資源聯(lián)合調(diào)度[J]. 宇航學(xué)報(bào), 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)星測(cè)控資源調(diào)度模型及其求解算法[J].宇航學(xué)報(bào), 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í)行時(shí)段滑動(dòng)調(diào)整策略的中繼衛(wèi)星任務(wù)規(guī)劃算法設(shè)計(jì)[J]. 飛行器測(cè)控學(xué)報(bào), 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).