薛乃陽,丁 丹,王紅敏,劉步花

(1.航天工程大學(xué)電子與光學(xué)工程系,北京 101416;2.航天工程大學(xué)研究生院,北京 101416)

0 引 言

衛(wèi)星測(cè)控資源調(diào)度(satellite telemetry,track and command resource scheduling,STRS)需要協(xié)調(diào)多種測(cè)控資源,多類任務(wù)并且還要考慮多種約束的組合優(yōu)化問題[1]。由于其需要應(yīng)用于問題實(shí)際,STRS具有領(lǐng)域知識(shí)繁多,可行解數(shù)量龐大的特點(diǎn),這給該問題的分析與解決帶來很大的困難[2]。多類測(cè)控資源主要是指國家測(cè)控網(wǎng)和商業(yè)測(cè)控網(wǎng)等不同類別的測(cè)控資源。國家測(cè)控資源主要由政府和軍隊(duì)的測(cè)控網(wǎng)構(gòu)成,商業(yè)測(cè)控資源由商業(yè)航天公司等民間資本投資建設(shè)的測(cè)控網(wǎng)絡(luò)組成?，F(xiàn)階段國內(nèi)外的研究主要集中在單個(gè)測(cè)控網(wǎng)內(nèi)測(cè)控資源調(diào)度,對(duì)多類測(cè)控網(wǎng)聯(lián)合調(diào)度的研究較少。國外的研究主要圍繞美國空軍衛(wèi)星測(cè)控網(wǎng)[3-4]、歐空局地面測(cè)控站網(wǎng)絡(luò)[5-6]的背景展開。例如,文獻(xiàn)[7-8]采用遺傳算法對(duì)問題進(jìn)行了研究;文獻(xiàn)[9]在總結(jié)測(cè)控資源調(diào)度問題復(fù)雜性的基礎(chǔ)上,提出了基于啟發(fā)式和元啟發(fā)式方法的解決方案;文獻(xiàn)[10]利用禁忌搜索算法來提高算法效率;此外,還有學(xué)者對(duì)測(cè)控資源多目標(biāo)優(yōu)化方法[11]、資源解沖突方法[2,12]進(jìn)行了研究。國內(nèi)的研究也主要立足于國家測(cè)控基礎(chǔ)設(shè)施,通過系統(tǒng)分析多星多站問題中的各種約束和調(diào)度目標(biāo),建立測(cè)控資源一體化調(diào)度問題模型[13],以成功被調(diào)度的任務(wù)數(shù)量、被調(diào)度任務(wù)滿足測(cè)控需求的優(yōu)先級(jí)等作為目標(biāo)函數(shù)采用啟發(fā)算法,遺傳算法、拉格朗日松弛算法等以及改進(jìn)的相關(guān)算法[14]進(jìn)行求解,明顯提高了國有測(cè)控網(wǎng)測(cè)控資源調(diào)度的效率和質(zhì)量。

從當(dāng)前國內(nèi)外的發(fā)展現(xiàn)狀來看,國有和商用航天測(cè)控等多元化測(cè)控模式并存協(xié)調(diào)發(fā)展是大勢(shì)所趨[15]。商業(yè)航天是指運(yùn)用商業(yè)、市場(chǎng)規(guī)模發(fā)展、運(yùn)營航天項(xiàng)目,并遵循市場(chǎng)規(guī)律開展的航天活動(dòng)[16-17]?，F(xiàn)階段采用的是國有和商用分開的測(cè)控管理體制。但是,隨著星座網(wǎng)絡(luò)的快速發(fā)展[18]與衛(wèi)星應(yīng)用領(lǐng)域的擴(kuò)大[19-20],入軌的航天器數(shù)量急劇增長,使有限的測(cè)控資源面臨越來越嚴(yán)重的資源沖突和爭(zhēng)用的情況。如果將隸屬于多類測(cè)控資源的測(cè)控網(wǎng)進(jìn)行聯(lián)合調(diào)度,可以有效提高測(cè)控資源的利用效率,緩解資源沖突。但是,由于這兩類測(cè)控管理體制的不同,在測(cè)控任務(wù)調(diào)度時(shí)需要考慮的約束上也有一定的差異。如何在盡可能保障原來需要國有航天測(cè)控資源執(zhí)行的任務(wù)高效可靠執(zhí)行的同時(shí),也兼顧到商用測(cè)控追求的高效率與低成本等多類測(cè)控資源調(diào)度約束上的差異性,實(shí)現(xiàn)兩種資源的聯(lián)合優(yōu)化調(diào)度,是一個(gè)亟待解決并且很有意義的問題。

本文在借鑒單個(gè)測(cè)控網(wǎng)下測(cè)控資源優(yōu)化調(diào)度成果的基礎(chǔ)上,研究了多類測(cè)控資源聯(lián)合優(yōu)化調(diào)度問題?，F(xiàn)階段對(duì)多個(gè)測(cè)控網(wǎng)的測(cè)控站網(wǎng)資源任務(wù)分配調(diào)度還處在互相分離的階段,測(cè)控網(wǎng)利用效率較低,本文對(duì)多類測(cè)控資源的聯(lián)合調(diào)度進(jìn)行了研究。首先，對(duì)不同管理體制下影響測(cè)控資源任務(wù)分配調(diào)度的因素進(jìn)行分析。其次，建立了多類測(cè)控資源分配調(diào)度模型,把總調(diào)度時(shí)間內(nèi)獲得最高的任務(wù)調(diào)度總優(yōu)先級(jí)作為適應(yīng)度函數(shù),對(duì)遺傳算法進(jìn)行改進(jìn),使之適應(yīng)多類測(cè)控資源聯(lián)合調(diào)度的求解需求。最后，采用此算法對(duì)測(cè)控調(diào)度問題進(jìn)行了優(yōu)化求解；并且通過仿真實(shí)例,對(duì)比引入聯(lián)合調(diào)度方法前后的求解質(zhì)量,證明了提出算法的有效性和現(xiàn)實(shí)意義。

1 多類測(cè)控資源的不同特點(diǎn)

國有和商業(yè)測(cè)控網(wǎng)由于各自建立的背景和主要服務(wù)對(duì)象的不同,在運(yùn)行管理等方面存在一定的差異。國有測(cè)控網(wǎng)是航天測(cè)控網(wǎng)的重要基礎(chǔ)設(shè)施,隨著重大航天工程不斷進(jìn)步,已發(fā)展成為天地空一體化協(xié)調(diào)發(fā)展、系統(tǒng)高效可靠運(yùn)行、可按需提供各種天地測(cè)控能力的大測(cè)控系統(tǒng)。而商業(yè)航天測(cè)控隨著國家政策的放開剛起步不久,正處在發(fā)展壯大的階段。商業(yè)測(cè)控公司在給客戶提供可靠的測(cè)控服務(wù)的同時(shí),也要考慮其服務(wù)的成本和效益,從而提高公司的市場(chǎng)競(jìng)爭(zhēng)力。因此,準(zhǔn)確分析兩種測(cè)控管理體制的特點(diǎn)是建立合理模型的基礎(chǔ)。

1.1 測(cè)控網(wǎng)絡(luò)架構(gòu)不同

據(jù)了解[21],國有測(cè)控網(wǎng)的架構(gòu)是基于S/C模式的服務(wù)器/客戶端模式架構(gòu),這是傳統(tǒng)的航天測(cè)控網(wǎng)架構(gòu)。即在功能上,將分布于各地的測(cè)控站和控制中心分別比作客戶端、服務(wù)器,進(jìn)行數(shù)據(jù)交換,而各個(gè)節(jié)點(diǎn)之間采用專線相連接。商業(yè)測(cè)控公司為了更好的適應(yīng)市場(chǎng)需求,沒有采用封閉的服務(wù)器架構(gòu),而是采用了開放的軟件即服務(wù)(software-as-a-service,SaaS)架構(gòu)。即一體化測(cè)控技術(shù),把整體架構(gòu)構(gòu)建在云服務(wù)之上。測(cè)控站通過通用的電信網(wǎng)絡(luò)運(yùn)營商的交換機(jī)和服務(wù)器,連接到測(cè)控云,云數(shù)據(jù)庫將所有數(shù)據(jù)進(jìn)行集中處理和分發(fā)。同時(shí),測(cè)控大廳里顯示的測(cè)控軟件也是運(yùn)行在云服務(wù)之上,這樣衛(wèi)星任務(wù)中心就能夠支持對(duì)外聯(lián)網(wǎng),客戶用筆記本電腦等移動(dòng)設(shè)備通過公用網(wǎng)絡(luò)連接到云服務(wù)器上,在任何時(shí)間和地點(diǎn)都能夠看到商業(yè)衛(wèi)星的健康狀態(tài),實(shí)現(xiàn)了衛(wèi)星測(cè)控中心任務(wù)的透明化。由于采用SaaS架構(gòu),具有良好的可擴(kuò)展性,便于實(shí)現(xiàn)自動(dòng)化測(cè)控,運(yùn)營成本低,給多類測(cè)控資源的聯(lián)合調(diào)度創(chuàng)造了便利的條件;但是需要借助互聯(lián)網(wǎng)實(shí)現(xiàn)互聯(lián),網(wǎng)絡(luò)節(jié)點(diǎn)多,與專線連接的傳統(tǒng)測(cè)控網(wǎng)相比,響應(yīng)時(shí)間較長,安全性較低。

1.2 建立測(cè)站的位置范圍和方式不同

國有測(cè)控站主要依靠自建,由國境內(nèi)的固定站、機(jī)動(dòng)站、遠(yuǎn)望號(hào)測(cè)量船和測(cè)控中心4部分組成。大部分測(cè)站集中在國境內(nèi),覆蓋圈次和范圍有限,雖然有遠(yuǎn)望號(hào)測(cè)量船可以作為海外機(jī)動(dòng)站,但成本和費(fèi)用較高。而商業(yè)測(cè)控網(wǎng)建站位置范圍和建站方式可以有更多更靈活的選擇,既可以在境內(nèi)自行建站,也可以在境外自建或者開展國際合作租站。以開展商業(yè)航天測(cè)控業(yè)務(wù)的天鏈公司為例,該公司在帕勞共和國境內(nèi)建立了南太站,彌補(bǔ)了測(cè)控網(wǎng)在南太區(qū)域無固定測(cè)控資源的空白,同時(shí)還在歐洲,南美洲和大洋洲以及東南亞地區(qū)通過合作和自建,擁有了10余個(gè)測(cè)控站,已經(jīng)能夠提供全球性的衛(wèi)星測(cè)控服務(wù)。

1.3 任務(wù)調(diào)度規(guī)劃優(yōu)先級(jí)不同

兩種測(cè)控管理體制對(duì)航天器的測(cè)控任務(wù)規(guī)劃調(diào)度優(yōu)先級(jí)不同。比如,國家測(cè)控任務(wù)對(duì)時(shí)效性和可靠性要求較高,應(yīng)當(dāng)優(yōu)先選擇符合條件的國有測(cè)站執(zhí)行,如果相應(yīng)的國有測(cè)站出現(xiàn)任務(wù)沖突或沒有可見弧段,則可以考慮使用商業(yè)測(cè)站來執(zhí)行測(cè)控任務(wù)。而在商業(yè)測(cè)控公司看來,國有衛(wèi)星的測(cè)控請(qǐng)求作為一個(gè)客戶需求,也需要在日常的商業(yè)測(cè)控任務(wù)列表中按一定的優(yōu)先級(jí)規(guī)則進(jìn)行規(guī)劃調(diào)度。但由于其市場(chǎng)化的特點(diǎn),在場(chǎng)景總測(cè)控調(diào)度時(shí)間段內(nèi)可能有一段時(shí)間需要優(yōu)先滿足某些重要客戶的測(cè)控請(qǐng)求,在此時(shí)間段內(nèi)商業(yè)測(cè)控網(wǎng)只執(zhí)行重要客戶的測(cè)控任務(wù)。因此,多類測(cè)控資源可能對(duì)同一個(gè)測(cè)控任務(wù)定義的調(diào)度優(yōu)先級(jí)不同,需要在所建立模型的約束條件和改進(jìn)遺傳算法的適應(yīng)度函數(shù)中有所體現(xiàn)。

1.4 上行頻段范圍不同

國有和商業(yè)測(cè)站在使用的上行頻段范圍有一定差異。S頻段上行權(quán)限由國家掌握并控制,主要用于國防或政府主導(dǎo)的航天器測(cè)控。而商業(yè)測(cè)控公司只有權(quán)限發(fā)送X頻段的上行指令,所以商業(yè)測(cè)控公司所屬測(cè)站不能在無政府授權(quán)的情況下向衛(wèi)星發(fā)射S頻段上行信號(hào)[17]。

上述國有和商業(yè)測(cè)控資源的測(cè)控特點(diǎn)表明,在進(jìn)行多類測(cè)控資源聯(lián)合調(diào)度時(shí),需要根據(jù)用戶衛(wèi)星和測(cè)控資源的屬性不同,建立適當(dāng)?shù)恼{(diào)度收益函數(shù),體現(xiàn)不同的調(diào)度優(yōu)先級(jí)。而某類特殊的S頻段上行測(cè)控任務(wù),則需要在國有測(cè)站的可見弧段的時(shí)間內(nèi)完成指令上注。因此,以實(shí)際測(cè)控作業(yè)規(guī)程為依據(jù)的多類測(cè)控資源聯(lián)合調(diào)度也必然要體現(xiàn)上述測(cè)控約束。

2 多類測(cè)控資源聯(lián)合調(diào)度模型

多類測(cè)控資源聯(lián)合調(diào)度問題建模的關(guān)鍵是尋找出影響國有和商業(yè)測(cè)控網(wǎng)實(shí)際能力的因素并使用約束條件進(jìn)行有效描述。本文將兩種管理體制下的測(cè)控資源按照國有和商用屬性分類,在分析多類測(cè)控資源特點(diǎn)的基礎(chǔ)上,根據(jù)對(duì)象的具體屬性來添加國有和商業(yè)測(cè)控資源的約束條件,接著進(jìn)行規(guī)范化的描述和科學(xué)的抽象。為了研究問題的方便,假設(shè)國有和商業(yè)測(cè)控站只考慮陸基固定站,且都為全功能站,不考慮移動(dòng)測(cè)站。

2.1 變量及符號(hào)定義

為了精確描述模型建立的過程和約束條件,首先對(duì)模型中涉及到的關(guān)鍵點(diǎn)進(jìn)行符號(hào)定義。

(2)測(cè)控資源集合R={R1,R2,…,Rg,…,Rr}。其中,國有測(cè)控站數(shù)量為g,其余為商用測(cè)控站。?Rk∈R可以表示為Rk=(RTk,RFk)。其中,RTk為測(cè)控資源屬性種類,有RTk∈{1,2}={國有測(cè)控站,商用測(cè)控站};RFk是測(cè)控頻段,與用戶衛(wèi)星測(cè)控頻段對(duì)應(yīng)。

(4)設(shè)用戶衛(wèi)星Si提出的任務(wù)集合為Reqi={ReSi,SAi,RJk,RAk}。測(cè)控任務(wù)類型定義為ReSi∈{0,1}={非S頻段上行任務(wù)，S頻段上行任務(wù)};Si與所有測(cè)控資源形成的過境窗口弧段集合為SAi；測(cè)控資源Rk所有可以提供測(cè)控服務(wù)的任務(wù)集合為RJk,Rk與所有用戶衛(wèi)星的可用測(cè)控弧段集合為RAk。

(5)測(cè)控任務(wù)集J={J1,J2,…,Jm},?Ji∈J,Ji={JNui,JSi,JAi,JCi,JYi,JSai,JFi,JFei}。其中,JNui為任務(wù)標(biāo)識(shí);JSi為提出任務(wù)請(qǐng)求的衛(wèi)星;JAi為可執(zhí)行該任務(wù)的測(cè)控弧段集合;JCi表示該任務(wù)測(cè)控需求中的測(cè)控站最短設(shè)備切換時(shí)間;JYi∈{0,1}={常規(guī)任務(wù),應(yīng)急測(cè)控任務(wù)};JSai={1,2}={一級(jí)安全性,二級(jí)安全性},表示此測(cè)控任務(wù)要求的安全性等級(jí),規(guī)定一級(jí)安全性只能有國有測(cè)控網(wǎng)執(zhí)行測(cè)控任務(wù),二級(jí)安全性對(duì)執(zhí)行任務(wù)的測(cè)控網(wǎng)沒有特殊要求;JFi={1,2}={國有測(cè)控網(wǎng),商業(yè)測(cè)控網(wǎng)},為資源特點(diǎn)約束,表明由于測(cè)控能力或者測(cè)控成本等約束條件的限制,只能由相應(yīng)屬性的測(cè)控網(wǎng)完成此測(cè)控任務(wù)。JFei主要與商業(yè)衛(wèi)星測(cè)控任務(wù)有關(guān),為衛(wèi)星用戶所能接受的最高測(cè)控費(fèi)用。

定義 1測(cè)控任務(wù)綜合優(yōu)先級(jí)。綜合考慮不同管理體制下的測(cè)控資源對(duì)用戶衛(wèi)星屬性、時(shí)間窗口的偏好程度和用戶衛(wèi)星優(yōu)先級(jí),定義衛(wèi)星i在測(cè)控弧段Al下的測(cè)控任務(wù)綜合屬性優(yōu)先級(jí)JPk(測(cè)控調(diào)度收益):

JPk=SPi+APrl(Jk∈Reqi,Al∈JAi)

(1)

2.2 約束條件

根據(jù)任務(wù)需求及多類測(cè)控資源聯(lián)合調(diào)度的特點(diǎn),借鑒國有測(cè)控資源的約束描述方式[1,13],將所有約束分為多類測(cè)控資源的特有約束和測(cè)控問題的一般約束。多類測(cè)控資源聯(lián)合調(diào)度過程的主要約束條件如下。

(1)多類測(cè)控資源聯(lián)合調(diào)度的特有約束

(2)

(3)

成本約束,在其他條件相同的情況下,滿足同一個(gè)測(cè)控任務(wù)需求,商業(yè)測(cè)控網(wǎng)的成本要小于國有測(cè)控網(wǎng)的成本。假設(shè)商業(yè)測(cè)控網(wǎng)進(jìn)行一次測(cè)控任務(wù)的成本是price1,而國有測(cè)控網(wǎng)的成本為price2,則price1

C2={?Jk∈J,RTk=2，price1

(4)

安全性約束,由于國有測(cè)控網(wǎng)采用專線互聯(lián)的封閉架構(gòu),節(jié)點(diǎn)少,網(wǎng)絡(luò)簡單,并且設(shè)備專用性較強(qiáng),可以盡最大可能的保障測(cè)控任務(wù)的安全性。而某些對(duì)安全性要求極高的國家級(jí)測(cè)控任務(wù),即(JSak<2)時(shí),只能由國有測(cè)控資源執(zhí)行測(cè)控任務(wù),精確表述如下所示：

C3={?Jk∈J,JSak<2:JFk=1}

(5)

站點(diǎn)空間分布約束,在測(cè)控資源調(diào)度方面,由于商業(yè)測(cè)站可以全球布網(wǎng),部署方便快捷,所以商業(yè)測(cè)控站的可用圈次數(shù)量更多。根據(jù)變量定義,國有測(cè)控站的編號(hào)為R1～Rg,商業(yè)測(cè)控站的編號(hào)為Rg+1～Rr。不同測(cè)控資源的可用弧段數(shù)量關(guān)系需要遵循約束：

(6)

測(cè)控能力約束,對(duì)于某些國有衛(wèi)星某圈次需要發(fā)送S頻段上行信號(hào)的任務(wù)來說,在規(guī)定的測(cè)控時(shí)間窗口中只能使用國有測(cè)控資源來完成。

C5={?Jm∈J,?Al∈JAi,SFk=1，Reqi=1,JFk=1}

(7)

測(cè)控資源服務(wù)偏好約束,由于每套測(cè)控網(wǎng)主要的服務(wù)對(duì)象不一樣,則歸屬于不同測(cè)控網(wǎng)的測(cè)控資源服務(wù)偏好不同。在不同類型的測(cè)控網(wǎng)下,對(duì)同一個(gè)衛(wèi)星的測(cè)控任務(wù)需求,測(cè)控收益值主要由定義的優(yōu)先級(jí)決定,優(yōu)先級(jí)的定義要遵循：C6={?Ak∈A，RTk=STk時(shí),其優(yōu)先級(jí)為APrk;RTk≠STk時(shí),優(yōu)先級(jí)為

APrl;APrk>APrl}

(8)

(2)測(cè)控資源調(diào)度的一般約束

時(shí)間窗有效性約束,所有測(cè)控任務(wù)只能在衛(wèi)星和測(cè)控站存在可見時(shí)間窗口內(nèi)的條件下進(jìn)行。假設(shè),要在測(cè)控弧段Ai所包含的時(shí)間窗口內(nèi)執(zhí)行測(cè)控任務(wù)JAk,則需滿足約束條件:

(9)

在同一測(cè)控資源執(zhí)行完一個(gè)測(cè)控任務(wù)后,執(zhí)行下一個(gè)測(cè)控任務(wù)之前,需要設(shè)置一定的設(shè)備復(fù)位與準(zhǔn)備時(shí)間,即測(cè)控站前后相鄰任務(wù)之間的轉(zhuǎn)換時(shí)間:

(10)

測(cè)控能力約束,對(duì)用戶衛(wèi)星需要執(zhí)行的測(cè)控任務(wù)與測(cè)控資源的頻段相匹配才能建立測(cè)控任務(wù)的通信鏈路:

C9={?Ai∈A,Ai∈SAk,Ai∈RAl,SFk∈RFl}

(11)

測(cè)控設(shè)備獨(dú)占性約束,對(duì)于同一個(gè)測(cè)控設(shè)備,在同一時(shí)刻只能為一顆衛(wèi)星提供測(cè)控服務(wù)。

(12)

衛(wèi)星任務(wù)獨(dú)占性約束,同一顆用戶衛(wèi)星不能有兩個(gè)及兩個(gè)以上的任務(wù)同時(shí)測(cè)控。

(13)

測(cè)控任務(wù)執(zhí)行次數(shù)約束,每個(gè)測(cè)控任務(wù)最多只能被完成一次,不能再被后續(xù)任務(wù)調(diào)度。

(14)

測(cè)控窗口可用性約束,每個(gè)測(cè)控任務(wù)的執(zhí)行時(shí)間必須不短于測(cè)控最短支持時(shí)間,最長也不能超過最長測(cè)控支持時(shí)間。

(15)

2.3 測(cè)控調(diào)度方案評(píng)價(jià)指標(biāo)

在多類測(cè)控資源聯(lián)合調(diào)度問題中,由于測(cè)控資源的有限性,在測(cè)控任務(wù)過多時(shí)可能不可避免的存在任務(wù)沖突,所以對(duì)綜合收益值的計(jì)算方法進(jìn)行了改進(jìn)。在同一個(gè)測(cè)控站中,如果調(diào)度計(jì)劃中的任務(wù)與上一個(gè)任務(wù)時(shí)間沖突(即約束C8和C10),則此任務(wù)的收益值取負(fù)號(hào)加入總收益函數(shù),并在生成最終方案時(shí)將此任務(wù)刪去,這樣就可以用算法的尋優(yōu)特性來盡量減少?zèng)_突造成的損失。測(cè)控調(diào)度計(jì)劃的優(yōu)劣程度采用改進(jìn)后的綜合收益值進(jìn)行評(píng)價(jià),設(shè)調(diào)度方案中有n個(gè)測(cè)控弧段與測(cè)站的前面的任務(wù)存在沖突,目標(biāo)函數(shù)如下:

(16)

3 改進(jìn)遺傳算法的求解策略

根據(jù)建立的模型,多類測(cè)控資源調(diào)度的直接對(duì)象是測(cè)控可用弧段。遺傳算法是模仿生命進(jìn)化發(fā)展而來的一類算法,具有通用性強(qiáng)、不依賴于問題背景、尋優(yōu)能力強(qiáng)、適合大規(guī)模問題等特點(diǎn)[13],不僅在類似問題中取得了較好的求解效果[22-24],而且還有許多學(xué)者用遺傳算法與其他優(yōu)化方法結(jié)合生成新算法[25-30]。因此,通過遺傳算法能夠較好的解決聯(lián)合調(diào)度的尋優(yōu)問題。算法主要分為可見弧段預(yù)處理、染色體基因編碼、遺傳組件設(shè)計(jì)和將測(cè)控任務(wù)弧段序列號(hào)依次分配給用戶衛(wèi)星需求4部分?？梢栽谧裱瓋煞N測(cè)控管理體制資源各自特點(diǎn)和運(yùn)行規(guī)律下發(fā)揮多類測(cè)控資源的整合優(yōu)勢(shì),從而實(shí)現(xiàn)尋找調(diào)度收益最高方案的目標(biāo)。其中，可見弧段的計(jì)算主要依賴衛(wèi)星工具包(satellite tool kit,STK)軟件。

3.1 基于STK與Matlab互聯(lián)的可見弧段預(yù)處理

通過可見弧段預(yù)處理產(chǎn)生的星站可見窗口弧段是進(jìn)行測(cè)控任務(wù)調(diào)度的對(duì)象。其目標(biāo)是將調(diào)度場(chǎng)景中每個(gè)衛(wèi)星的測(cè)控需求、測(cè)控總調(diào)度時(shí)間段、每次測(cè)控最短時(shí)間和測(cè)站最短轉(zhuǎn)換時(shí)間等約束條件通過STK軟件建模求得的衛(wèi)星與測(cè)站可見窗口信息相結(jié)合,得到每個(gè)衛(wèi)星需求才測(cè)控總時(shí)間段內(nèi)可用測(cè)控弧段集合。文獻(xiàn)[31]利用STK仿真計(jì)算地面站調(diào)度信息,并將這些數(shù)據(jù)用XML格式儲(chǔ)存。為了方便快捷的獲取可見弧段信息,本文采用基于Matlab與STK互聯(lián)的可見弧段獲取方式,兩款軟件的具體版本為Matlab 2014b和STK 11.4。在Matlab程序中調(diào)用STK中IAgStkObjectRoot函數(shù)集和相應(yīng)的接口函數(shù)。通過編寫Matlab程序,實(shí)現(xiàn)了場(chǎng)景中所有衛(wèi)星和測(cè)站的可見弧段信息的自動(dòng)化獲取。接著,把其包含的衛(wèi)星、測(cè)站、弧段始末時(shí)間以及窗口持續(xù)時(shí)間按照滿足C1～C3、C5和C13約束進(jìn)行初步篩選,儲(chǔ)存在特定的表格中,得到每個(gè)衛(wèi)星需求的可用測(cè)控弧段集合。

3.2 改進(jìn)遺傳算法求解框架

基于改進(jìn)遺傳算法的多類測(cè)控資源聯(lián)合調(diào)度的具體求解框架如圖1所示。算法的主要改進(jìn)是對(duì)基因型發(fā)生變化的染色體進(jìn)行約束條件檢驗(yàn),使之適應(yīng)問題求解的需要。經(jīng)過可見弧段預(yù)處理之后,首先要進(jìn)行種群初始化,并進(jìn)行約束條件檢驗(yàn),確保種群中的每一條染色體代表的測(cè)控調(diào)度方案都可以滿足任務(wù)需求。其次,依次進(jìn)行適應(yīng)度計(jì)算、選擇、交叉和變異操作,在有新染色體產(chǎn)生的交叉和變異階段,需要對(duì)每個(gè)染色體進(jìn)行約束條件檢驗(yàn)。對(duì)于同一個(gè)測(cè)站的測(cè)控可用弧段的沖突約束,采用將其適應(yīng)度值設(shè)置為負(fù)數(shù)的方法進(jìn)行處理。最后,根據(jù)場(chǎng)景規(guī)模大小設(shè)置相應(yīng)的進(jìn)化代數(shù)作為算法終止條件,若在調(diào)度表中存在沖突的情況,就刪去收益值為負(fù)數(shù)的測(cè)控窗口,得到最終的優(yōu)化調(diào)度方案。

圖1 改進(jìn)遺傳算法優(yōu)化框架Fig.1 Optimization framework of improved genetic algorithm

3.3 編碼

染色體上的基因編碼奠定了遺傳算法求解的基礎(chǔ),編碼方法設(shè)計(jì)的優(yōu)劣程度直接影響到了算法的求解效率和性能。因此,染色體采用整數(shù)編碼方式,將預(yù)處理之后得到的測(cè)控弧段按照時(shí)間先后順序排列序號(hào)作為弧段序列號(hào)。并將此序列號(hào)作為染色體上的基因型,分別儲(chǔ)存在JAk集合中,隨機(jī)在集合中選取衛(wèi)星k的調(diào)度窗口,排列在染色體上的相鄰位置,編碼和基因排列情況如圖2所示。圖2中展示了由3顆衛(wèi)星(每顆衛(wèi)星的測(cè)控需求為4次)組成的調(diào)度方案。其中每條染色體長度即為衛(wèi)星提出的總?cè)蝿?wù)需求數(shù)量。

圖2 調(diào)度方案在染色體上的編碼方式示意圖Fig.2 Schematic representation of coding mode of scheduling scheme on chromosome

3.4 初始種群的生成

一般來說,遺傳算法的搜索性能與生成初始種群的基因多樣性密切相關(guān),因此本文采用隨機(jī)方法產(chǎn)生初始種群中每一個(gè)染色體的基因型。

3.5 適應(yīng)度數(shù)值計(jì)算

由于多類測(cè)控資源聯(lián)合調(diào)度的目的,是在盡可能考慮滿足不同測(cè)控資源約束和測(cè)控需求的條件下,使獲得的總優(yōu)先級(jí)之和最大。因此,將目標(biāo)函數(shù)作為適應(yīng)度函數(shù),如式(16)所示。

3.6 遺傳算子設(shè)計(jì)

(1)改進(jìn)的保留選擇算子。由于本文中采用隨機(jī)方式產(chǎn)生初始種群,并且輸入規(guī)模較大,所以單一的選擇方式不能保證適應(yīng)度值較大的個(gè)體有更大的可能性進(jìn)行交叉和變異。因此,對(duì)選擇策略進(jìn)行了改進(jìn):首先按從大到小的順序?qū)ΨN群中的個(gè)體進(jìn)行排序,然后結(jié)合排序和輪盤賭法選擇法的結(jié)果,按比例選擇優(yōu)秀個(gè)體進(jìn)入配偶池。這樣既提高了算法的收斂速度,又在一定程度上減少了算法求解陷入局部最優(yōu)的可能性。

(2)帶有禁忌搜索策略的交叉算子和變異算子。為了較好地平衡算法的收斂性與種群的多樣性,避免局部最優(yōu)。本文采用單點(diǎn)交叉方法,雜交的個(gè)體從選擇后的新種群中隨機(jī)選取,對(duì)雜交后產(chǎn)生的新染色體進(jìn)行約束條件檢驗(yàn)。為了更快的找到最優(yōu)解,在此步驟引入了禁忌搜索策略,將不符合約束條件的基因型放到禁忌列表中,防止程序陷入死循環(huán),提高求解速度和方案可行性。同理,采用隨機(jī)選取變異位置的單點(diǎn)變異算子,為了使變異后的個(gè)體滿足約束條件,將不符合約束條件的變異點(diǎn)基因型列入禁忌表中,提高求解質(zhì)量和速度。

3.7 終止條件

在遺傳算法中,通常將最大迭代次數(shù)設(shè)置為終止條件,當(dāng)算法的進(jìn)化代數(shù)滿足此終止條件的要求時(shí),算法停止,同時(shí)輸出結(jié)果。本文根據(jù)調(diào)度場(chǎng)景規(guī)模設(shè)置最大遺傳代數(shù)Gen,當(dāng)遺傳代數(shù)達(dá)到Gen時(shí)算法停止。

3.8 利用算法尋優(yōu)的約束沖突處理

本文將算法的尋優(yōu)特性應(yīng)用于任務(wù)弧段沖突的消解。根據(jù)適應(yīng)度函數(shù),把每條染色體上的調(diào)度方案中與前面任務(wù)存在沖突的任務(wù)的測(cè)控收益賦為負(fù)數(shù),這樣在算法的優(yōu)化迭代中就可以優(yōu)先選擇出總收益最大的調(diào)度方案。同時(shí),在本文設(shè)計(jì)的算法中,要在交叉、變異運(yùn)算之后對(duì)約束條件進(jìn)行檢查,但是這些檢查的約束中不包含代表測(cè)控弧段時(shí)間沖突的約束C8。最后,刪去評(píng)價(jià)為負(fù)值的測(cè)控弧段,得到最終的調(diào)度方案。

4 仿真實(shí)例與結(jié)果分析

4.1 場(chǎng)景設(shè)計(jì)

為了驗(yàn)證本文提出方法的適用性和有效性,如圖3所示。通過實(shí)驗(yàn),應(yīng)用相同的優(yōu)化算法求解,對(duì)多類測(cè)控資源引入聯(lián)合調(diào)度方法的前后調(diào)度結(jié)果進(jìn)行對(duì)比。在沒有對(duì)測(cè)控資源進(jìn)行聯(lián)合調(diào)度前,不同屬性的測(cè)控資源只能對(duì)相同屬性的衛(wèi)星用戶提供測(cè)控服務(wù)。而引入聯(lián)合調(diào)度的方法后,在滿足相應(yīng)約束的前提下,屬性不同的測(cè)控資源可以對(duì)不同屬性的衛(wèi)星用戶執(zhí)行測(cè)控任務(wù)。場(chǎng)景的總調(diào)度時(shí)間為2020-10-01 00:00:00至2020-10-02 00:00:00。根據(jù)實(shí)際情況,在場(chǎng)景中分別設(shè)置了一定數(shù)量的國有、商業(yè)測(cè)控資源以及在軌運(yùn)行的多顆低軌用戶衛(wèi)星,利用STK與Matlab軟件創(chuàng)建并獲取可見弧段中的各項(xiàng)數(shù)據(jù)信息。場(chǎng)景中測(cè)控資源和衛(wèi)星分布概貌如圖4所示。

圖3 實(shí)驗(yàn)方案對(duì)比設(shè)計(jì)示意圖Fig.3 Schematic diagram of experimental scheme comparison design

圖4 場(chǎng)景的測(cè)控資源和衛(wèi)星分布概貌Fig.4 Telemetry,track and command resources and satellite distribution overview of the scene

場(chǎng)景中包含呼倫貝爾站、佳木斯站、喀什站、老撾站、帕勞站和一個(gè)位于東海附近測(cè)量船組成的測(cè)控資源集合以及包含24顆低軌衛(wèi)星的用戶衛(wèi)星集合。其中,佳木斯站、海上測(cè)量船和喀什站是國有測(cè)控站,帕勞站、呼倫貝爾站和老撾站是商業(yè)測(cè)站;24顆低軌衛(wèi)星中有16顆是國有衛(wèi)星,8顆是商用衛(wèi)星,所有衛(wèi)星采用其在雙行軌道根數(shù)中的SSC號(hào)碼進(jìn)行命名,根據(jù)此號(hào)碼可以在互聯(lián)網(wǎng)上查詢到對(duì)應(yīng)衛(wèi)星的雙行軌道根數(shù)信息。其中的3顆商業(yè)衛(wèi)星有一次測(cè)控任務(wù)由于成本約束C2,不能選擇測(cè)量船(?；鶞y(cè)控站)執(zhí)行測(cè)控任務(wù)。另外,隨機(jī)選擇6顆國有衛(wèi)星,在首圈測(cè)控時(shí)需要通過國有測(cè)站上傳S波段上行信號(hào)。

表1 資源收益Table 1 Resources income

表2 衛(wèi)星基本信息Table 2 Satellite basic information

4.2 改進(jìn)遺傳算法的計(jì)算結(jié)果

實(shí)驗(yàn)系統(tǒng)配置為:Inter Core(TM)i7-9750H CPU @2.60 GHz,DDR4 8 G RAM,Windows10;算法采用Matlab 2019a編程實(shí)現(xiàn)。改進(jìn)遺傳算法的具體參數(shù)設(shè)置如表3所示。通過可見性分析軟件,計(jì)算出799條可用弧段信息,將其作為輸入信息代入求解優(yōu)化算法中。

表3 改進(jìn)遺傳算法參數(shù)設(shè)置Table 3 Parameter setting of improved genetic algorithm

對(duì)引入聯(lián)合調(diào)度前后的多類測(cè)控資源優(yōu)化情況都用本文提出的改進(jìn)遺傳算法進(jìn)行求解。如圖5所示,為引入聯(lián)合調(diào)度方法前后的測(cè)控調(diào)度收益隨算法迭代次數(shù)變化情況。

圖5 引入聯(lián)合調(diào)度前后算法的尋優(yōu)軌跡Fig.5 Algorithm optimization trajectory before and after the introduction of joint scheduling

在圖5中,橫坐標(biāo)為算法迭代次數(shù),縱坐標(biāo)為模型中定義的測(cè)控調(diào)度收益值。程序求解時(shí)間為18.528 s,從圖5中可以看出,如果對(duì)多類測(cè)控資源不采用聯(lián)合調(diào)度的方式,測(cè)控需求滿足率僅為88.40%,測(cè)控調(diào)度收益為1 401;而對(duì)多類測(cè)控資源引入聯(lián)合調(diào)度方法,測(cè)控需求滿足率可以提高至100%,測(cè)控調(diào)度收益為1 835。通過實(shí)驗(yàn)對(duì)比,在引入聯(lián)合調(diào)度方法前后,測(cè)控調(diào)度方案的收益值較不引入聯(lián)合調(diào)度方法增加了13.12%?？梢钥闯?在多類測(cè)控資源的應(yīng)用中引入聯(lián)合調(diào)度,不僅可以有效提高測(cè)控需求滿足率,還增加了調(diào)度方案的收益值,從而提高了整個(gè)測(cè)控資源的利用效率。

采用改進(jìn)遺傳算法對(duì)多類測(cè)控資源進(jìn)行聯(lián)合調(diào)度,根據(jù)得到的最優(yōu)化方案畫出的甘特圖如圖6所示。其中,不同顏色代表不同衛(wèi)星的測(cè)控任務(wù),每個(gè)任務(wù)的X/Y代號(hào)表示第X顆衛(wèi)星的在總測(cè)控調(diào)度計(jì)劃中排列為Y的測(cè)控任務(wù)?？v坐標(biāo)測(cè)站代號(hào)1～6依次代表海上測(cè)控站、呼倫貝爾站、佳木斯站、喀什站、老撾站和帕勞站;橫坐標(biāo)表示調(diào)度時(shí)間,為0～1 440 min。

圖6直觀的表示出了調(diào)度計(jì)劃中151個(gè)測(cè)控任務(wù)的測(cè)控弧段的時(shí)間長短和星站可見窗口等信息,可以看出調(diào)度結(jié)果是滿足所有約束要求的。綜上,從算法優(yōu)化求解的結(jié)果可知,所設(shè)計(jì)的改進(jìn)遺傳算法可以在多類測(cè)控資源聯(lián)合調(diào)度模型下求得一定質(zhì)量的調(diào)度方案。在設(shè)置的場(chǎng)景中,從算法最終求得的最優(yōu)解可以看出,對(duì)于多類測(cè)控資源來說,不采用聯(lián)合調(diào)度方法時(shí)任務(wù)收益和測(cè)控任務(wù)需求滿足情況較差。但如果在進(jìn)行多類測(cè)控資源調(diào)度時(shí)采用聯(lián)合調(diào)度方法,即使不同測(cè)控網(wǎng)之間聯(lián)合調(diào)度存在許多約束,但還是能全部滿足測(cè)控需求并取得了較高的調(diào)度收益,表明多類測(cè)控資源聯(lián)合測(cè)控資源調(diào)度方案能夠有效提高測(cè)控資源的利用效率。另外,利用改進(jìn)遺傳算法求解此類問題還存在一定的不足,在求解能力上還有進(jìn)一步提高的空間。

圖6 算法優(yōu)化求解得到的聯(lián)合調(diào)度方案甘特圖Fig.6 Gantt chart of joint scheduling scheme obtained by algorithm optimization

5 結(jié) 論

多類測(cè)控資源聯(lián)合調(diào)度問題是一個(gè)約束條件多,資源沖突強(qiáng)的復(fù)雜組合優(yōu)化問題。本文對(duì)國有和商業(yè)測(cè)控資源特點(diǎn)分別進(jìn)行分析和規(guī)范化的描述和科學(xué)的抽象。結(jié)合多類測(cè)控資源聯(lián)合調(diào)度的需求和特點(diǎn),建立了多類測(cè)控資源聯(lián)合調(diào)度模型,并根據(jù)問題求解的實(shí)際情況提出了基于改進(jìn)遺傳算法的求解策略,證明了采用多類測(cè)控資源聯(lián)合調(diào)度方法較傳統(tǒng)方法的優(yōu)越性,并為求解此類問題提出了一種可行的解決方案。應(yīng)該注意到,多類測(cè)控資源聯(lián)合調(diào)度問題具有復(fù)雜性和特殊性,不同的測(cè)控資源管理機(jī)構(gòu)會(huì)對(duì)其有更加細(xì)致的要求。此外,本文建立的模型只考慮了屬于不同測(cè)控網(wǎng)的地基測(cè)控站的資源調(diào)度問題,如果要在實(shí)際任務(wù)中真正投入使用,還需要考慮與天基等測(cè)控資源的協(xié)同,以及由于加入緊急測(cè)控任務(wù)造成動(dòng)態(tài)不確定影響的動(dòng)態(tài)測(cè)控資源調(diào)度等問題。