面向復(fù)雜關(guān)聯(lián)測(cè)控需求的沖突規(guī)避調(diào)度算法

辛立強(qiáng), 張 超,*, 趙靈芝, 劉建平

(1. 西安交通大學(xué)信息與通信工程學(xué)院, 陜西 西安 710048;2. 西安衛(wèi)星測(cè)控中心宇航動(dòng)力學(xué)國(guó)家重點(diǎn)實(shí)驗(yàn)室, 陜西 西安 710043)

0 引 言

在空間資源開發(fā)熱潮的推動(dòng)下,我國(guó)在軌運(yùn)行的中、低軌道衛(wèi)星越來(lái)越多,而目前測(cè)控資源卻是有限的,新建、維護(hù)測(cè)控資源設(shè)備所需成本巨大。因此,如何充分利用現(xiàn)有測(cè)控站網(wǎng)設(shè)備資源,提高測(cè)控站網(wǎng)資源使用的效率,盡可能地提高衛(wèi)星用戶測(cè)控需求的成功率成為國(guó)家迫切需要解決的問(wèn)題。

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

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

現(xiàn)有啟發(fā)式調(diào)度算法還很少考慮到任務(wù)間復(fù)雜的關(guān)聯(lián)性。本文特別針對(duì)相互關(guān)聯(lián)的測(cè)控任務(wù)的資源調(diào)度問(wèn)題進(jìn)行了研究。在對(duì)航天測(cè)控資源調(diào)度過(guò)程中所涉及的測(cè)控設(shè)備、衛(wèi)星測(cè)控任務(wù)、可見弧段信息進(jìn)行描述的基礎(chǔ)上,采用約束滿足問(wèn)題模型對(duì)衛(wèi)星測(cè)控資源調(diào)度問(wèn)題進(jìn)行了數(shù)學(xué)化建模,創(chuàng)新性地設(shè)計(jì)了一種基于任務(wù)沖突規(guī)避的啟發(fā)式調(diào)度算法。

1 衛(wèi)星測(cè)控資源調(diào)度問(wèn)題

我國(guó)現(xiàn)有測(cè)控資源調(diào)度實(shí)戰(zhàn)系統(tǒng)統(tǒng)一調(diào)度所有地面站網(wǎng)測(cè)控設(shè)備以滿足在軌衛(wèi)星的測(cè)控請(qǐng)求。目前一般采用測(cè)控資源預(yù)分配+動(dòng)態(tài)應(yīng)急響應(yīng)的方式,資源站網(wǎng)管理中心根據(jù)衛(wèi)星發(fā)出的測(cè)運(yùn)控需求申請(qǐng)生成測(cè)控計(jì)劃。在預(yù)分配過(guò)程中,需要從全局最優(yōu)角度考慮,盡可能提高任務(wù)調(diào)度成功率。資源預(yù)分配算法性能高低直接決定測(cè)控網(wǎng)的運(yùn)行效益和衛(wèi)星測(cè)控任務(wù)的滿足率。因此需要對(duì)預(yù)分配測(cè)控資源調(diào)度算法的效率和成功率進(jìn)行提高。

圖1給出了測(cè)控資源調(diào)度的系統(tǒng)框圖。

圖1 測(cè)控資源調(diào)度系統(tǒng)框圖Fig.1 Block diagram of TT & C resource scheduling system

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

雖然近些年已經(jīng)有相關(guān)學(xué)者針對(duì)我國(guó)航天測(cè)控網(wǎng)進(jìn)行了一定的分析研究,但是未曾考慮到相鄰子任務(wù)完成時(shí)間之間需要保持復(fù)雜的關(guān)聯(lián)性?？尚薪膺x取不當(dāng)容易導(dǎo)致選擇的可行解違反任務(wù)間復(fù)雜的關(guān)聯(lián)性約束,導(dǎo)致需要推倒重新選擇,影響調(diào)度算法運(yùn)行效率。本文根據(jù)衛(wèi)星測(cè)控需求,加入了測(cè)控子任務(wù)間的關(guān)聯(lián)約束,建立了目標(biāo)約束滿足模型。

1.1 衛(wèi)星測(cè)控任務(wù)模型

現(xiàn)有測(cè)控資源調(diào)度系統(tǒng)采取預(yù)分配的調(diào)度策略,資源調(diào)度系統(tǒng)同時(shí)對(duì)衛(wèi)星一周內(nèi)的所有任務(wù)進(jìn)行調(diào)度。假設(shè)一共有個(gè)衛(wèi)星測(cè)控任務(wù)需求,表示所有衛(wèi)星用戶的測(cè)控任務(wù)集合,表達(dá)式為

={,,…,,…,}

(1)

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

表1 任務(wù)需求屬性表

cd,,可表示為

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

(2)

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

1.2 地面測(cè)控設(shè)備模型

我國(guó)衛(wèi)星測(cè)控站主要分布于國(guó)土境內(nèi),各個(gè)地面站的設(shè)備屬性均不相同,為規(guī)范化統(tǒng)一描述其屬性,我們給出了衛(wèi)星測(cè)控設(shè)備的基本屬性,如表2所示。

表2 衛(wèi)星測(cè)控站設(shè)備屬性

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

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

(3)

1.3 可見弧段模型

由于只有當(dāng)衛(wèi)星與地面測(cè)控站可見時(shí)才可進(jìn)行測(cè)控任務(wù)。因此,通過(guò)仿真軟件,結(jié)合衛(wèi)星的軌道信息和測(cè)控資源的位置信息生成衛(wèi)星的可見弧段預(yù)報(bào)。表3給出了衛(wèi)星可見弧段的基本屬性。

表3 衛(wèi)星可見弧段預(yù)報(bào)屬性

對(duì)地面測(cè)控設(shè)備和衛(wèi)星相對(duì)應(yīng)的可見弧段特征可描述為

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

(4)

式中:表示某衛(wèi)星相對(duì)于一個(gè)地面設(shè)備的一個(gè)可見弧段;表示地面設(shè)備編號(hào);表示衛(wèi)星編號(hào);RF表示該弧段的升降軌屬性;rev表示該衛(wèi)星的總?cè)μ?hào);Idrev表示此弧段為該衛(wèi)星此次過(guò)境的相對(duì)圈數(shù);conrev表示該衛(wèi)星此次過(guò)境的連續(xù)可見圈數(shù);tr表示該弧段開始時(shí)間;tr表示該弧段結(jié)束時(shí)間;Ang表示該可見弧段中點(diǎn)的俯仰角。

1.4 測(cè)控資源調(diào)度目標(biāo)約束模型

為建立目標(biāo)約束模型,引入決策變量,,。當(dāng),,=1時(shí),表示任務(wù)的第天的第個(gè)子任務(wù)調(diào)度成功;當(dāng),,=0時(shí),表示任務(wù)的第天的第個(gè)子任務(wù)調(diào)度失敗。完成一個(gè)測(cè)控子任務(wù)的資源利用情況可以表示為,,={cd,,,,rev,,},任務(wù)cd,,在衛(wèi)星的第rev圈完成,和分別表示cd,,使用設(shè)備測(cè)控的開始時(shí)間和結(jié)束時(shí)間。當(dāng)子任務(wù)未被完成時(shí),,,=?。我們將目標(biāo)函數(shù)設(shè)計(jì)為衛(wèi)星測(cè)控子任務(wù)的加權(quán)完成率最大,如下所示:

(5)

測(cè)控資源調(diào)度問(wèn)題的約束條件可以分為3大類:第一類是基于測(cè)控子任務(wù)的需求約束;第二類是子任務(wù)間的關(guān)聯(lián)約束;第三類是根據(jù)設(shè)備可用時(shí)間、衛(wèi)星可見弧段所確定的設(shè)備物理約束。表4詳細(xì)列舉了各項(xiàng)約束。

表4 測(cè)控任務(wù)約束條件表

2 測(cè)控資源調(diào)度算法

2.1 任務(wù)占用資源的概率分布

(6)

(7)

2.2 基于任務(wù)需求度的關(guān)鍵任務(wù)選取策略

基于啟發(fā)式的航天測(cè)控網(wǎng)調(diào)度問(wèn)題初始解生成一般包括兩個(gè)步驟,即確定任務(wù)處理的順序和任務(wù)可行解的選取策略。獲得一個(gè)好的任務(wù)處理順序是建立一個(gè)接近最優(yōu)的單輪序貫調(diào)度算法的關(guān)鍵。

圖2給出了4個(gè)設(shè)備不同時(shí)刻被任務(wù)占用概率累積和的示意圖,從圖中可以看出,設(shè)備3的圓圈處取值最大,即設(shè)備被任務(wù)占用概率累積和最大,說(shuō)明此時(shí)該設(shè)備最可能產(chǎn)生任務(wù)沖突,因此為關(guān)鍵資源位置。

圖2 關(guān)鍵位置示意圖Fig.2 Schematic diagram of bottleneck location

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

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

(8)

2.4 算法流程圖

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

3 實(shí)驗(yàn)驗(yàn)證

為了驗(yàn)證本文提出的基于沖突的站網(wǎng)資源調(diào)度啟發(fā)式算法的性能,本文給出位于9個(gè)地面站的16臺(tái)測(cè)控設(shè)備對(duì)50顆、100顆、150顆低軌衛(wèi)星兩周14天測(cè)控任務(wù)需求進(jìn)行測(cè)控的實(shí)例,分別代表小規(guī)模、中規(guī)模、大規(guī)模情況下的衛(wèi)星測(cè)控任務(wù)需求。測(cè)控設(shè)備和任務(wù)需求的基本情況參見表5。

表5 測(cè)控場(chǎng)景的基本情況

實(shí)驗(yàn)驗(yàn)證環(huán)境為Win10 64位系統(tǒng),CPU為Core i7-8700,3.20 GHz六核,16GBRAM,實(shí)驗(yàn)工具為Eclipse。

實(shí)驗(yàn)分析任務(wù)調(diào)度成功率。本文選取7組對(duì)照算法進(jìn)行實(shí)驗(yàn)。單層調(diào)度算法采取隨機(jī)選取任務(wù)的可行解進(jìn)行調(diào)度和測(cè)控任務(wù)的可行解先到先服務(wù)(first in first out, FIFO)的策略。雙層調(diào)度算法將對(duì)選取調(diào)度任務(wù)和可行解這兩個(gè)步驟分步進(jìn)行,設(shè)置基于任務(wù)優(yōu)先級(jí)的FIFO算法、基于任務(wù)優(yōu)先級(jí)的可行解接受度最大的調(diào)度算法、基于關(guān)鍵任務(wù)的FIFO算法、基于關(guān)鍵任務(wù)的隨機(jī)可行解選取算法作為對(duì)照組。為了對(duì)比觀察各個(gè)算法的性能,這里以衛(wèi)星測(cè)控任務(wù)需求滿足率來(lái)衡量算法的求解質(zhì)量。根據(jù)上述場(chǎng)景實(shí)驗(yàn)得到不同任務(wù)規(guī)模下測(cè)控任務(wù)調(diào)度成功率如圖4所示。

圖4 不同任務(wù)規(guī)模下任務(wù)調(diào)度成功率Fig.4 Task scheduling success rate under different task sizes

從圖4可以看出隨機(jī)選取可行解的算法隨著測(cè)控任務(wù)規(guī)模的擴(kuò)大,由于其沒(méi)有考慮到任務(wù)之間的沖突關(guān)系,成功率有所下降。當(dāng)衛(wèi)星任務(wù)個(gè)數(shù)超過(guò)100后,FIFO的調(diào)度策略成功率都低于90%,是因?yàn)槠涿恳徊竭x取“過(guò)分貪婪”,沒(méi)有考慮到設(shè)備的稀缺性和任務(wù)可行解的靈活度,將測(cè)控任務(wù)大多安排在地方時(shí)早的設(shè)備上,使得這些設(shè)備的利用率過(guò)高,從而導(dǎo)致更多的任務(wù)沖突?；谌蝿?wù)優(yōu)先級(jí)的FIFO調(diào)度算法相較于全局FIFO算法成功率有所降低,因?yàn)槿蝿?wù)調(diào)度成功率對(duì)優(yōu)先級(jí)是敏感的,而優(yōu)先級(jí)的屬性較為主觀,也不能反映測(cè)控資源的稀缺情況。

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

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

圖5 設(shè)備服務(wù)時(shí)長(zhǎng)匯總Fig.5 Summary of equipment service duration

雖然在圖4中發(fā)現(xiàn):基于關(guān)鍵任務(wù)來(lái)確定任務(wù)調(diào)度順序并沒(méi)有明顯比傳統(tǒng)的通過(guò)優(yōu)先級(jí)來(lái)確定任務(wù)調(diào)度順序的方法好。但當(dāng)測(cè)控資源數(shù)量減少時(shí),測(cè)控資源更加稀缺,便能明顯體現(xiàn)出基于關(guān)鍵任務(wù)處理順序的優(yōu)勢(shì)。圖6展示了150顆衛(wèi)星的5 038個(gè)測(cè)控任務(wù)需求在7個(gè)、10個(gè)、17個(gè)測(cè)控設(shè)備時(shí)任務(wù)調(diào)度的成功率。隨著測(cè)控設(shè)備數(shù)量的減少,任務(wù)調(diào)度的成功率也隨之降低。而通過(guò)基于關(guān)鍵任務(wù)的測(cè)控資源調(diào)度算法計(jì)算得到的任務(wù)調(diào)度成功率明顯高于其他算法。

圖6 150顆衛(wèi)星測(cè)控任務(wù)調(diào)度成功率Fig.6 Success rate of TT & C task scheduling for 150 satellites

4 結(jié) 論

針對(duì)基于衛(wèi)星需求的測(cè)控資源調(diào)度問(wèn)題, 本文建立了目標(biāo)約束模型,并充分考慮到測(cè)控任務(wù)需求間復(fù)雜的關(guān)聯(lián)關(guān)系,設(shè)計(jì)了一種沖突規(guī)避的復(fù)雜關(guān)聯(lián)測(cè)控需求調(diào)度算法。該算法采用測(cè)控資源被任務(wù)占用概率的累積和作為評(píng)判指標(biāo)找到最可能產(chǎn)生沖突的測(cè)控設(shè)備和時(shí)刻,并選取該時(shí)刻對(duì)此測(cè)控設(shè)備需求度最大的任務(wù)作為關(guān)鍵任務(wù)進(jìn)行調(diào)度。為避免過(guò)分貪婪,充分考慮到測(cè)控資源占用對(duì)全局任務(wù)的影響和任務(wù)間的關(guān)聯(lián)關(guān)系,構(gòu)造了接受度函數(shù),選取接受度函數(shù)最大的可行解作為調(diào)度解。通過(guò)算例的對(duì)比實(shí)驗(yàn)分析可以看出,本算法的求解效果較好。

雖然本文提出的基于沖突規(guī)避的關(guān)鍵任務(wù)測(cè)控資源調(diào)度算法能夠獲得較為滿意的調(diào)度解,但這只是一種單輪序貫的啟發(fā)式調(diào)度算法。下一步將通過(guò)分析單輪序貫調(diào)度下資源分配失敗任務(wù)與成功任務(wù)之間的競(jìng)爭(zhēng)關(guān)系,設(shè)計(jì)合適的回溯搜索算法。