基于多目標(biāo)優(yōu)化的中繼衛(wèi)星重調(diào)度方法

龍運(yùn)軍，李恒偉，尹 謙，郭 磊

(1.北京空間信息中繼傳輸技術(shù)研究中心，北京 100094；2.中南大學(xué) 交通運(yùn)輸工程學(xué)院，湖南 長(zhǎng)沙 410075)

0 引言

隨著衛(wèi)星數(shù)量增多，航天器之間的數(shù)據(jù)交流需求越來(lái)越大，對(duì)中繼衛(wèi)星的需求也變大。中繼衛(wèi)星的運(yùn)行軌道在地面36 000 km之上，軌道高度高，覆蓋面廣。3顆中繼衛(wèi)星組成的衛(wèi)星網(wǎng)絡(luò)，能全部覆蓋300～2 000 km軌道上的衛(wèi)星，實(shí)現(xiàn)數(shù)據(jù)中繼和對(duì)衛(wèi)星的連續(xù)跟蹤，使得衛(wèi)星數(shù)據(jù)傳輸對(duì)地面測(cè)控站的依賴(lài)減小，節(jié)省衛(wèi)星數(shù)據(jù)傳輸?shù)某杀尽?/p>

隨著對(duì)中繼衛(wèi)星的需求增大，如何合理地調(diào)配中繼衛(wèi)星資源，滿足用戶的需求，成為提高整個(gè)系統(tǒng)利用效率的關(guān)鍵。當(dāng)前，對(duì)中繼衛(wèi)星的調(diào)度方法研究大多是在特定的理想情況下，對(duì)于單目標(biāo)需求進(jìn)行優(yōu)化。

現(xiàn)有中繼衛(wèi)星系統(tǒng)調(diào)度研究主要分為對(duì)應(yīng)用模式的研究和對(duì)算法的研究。在應(yīng)用模式方面，Hajghassem[1]對(duì)NASA的中繼衛(wèi)星系統(tǒng)在航天網(wǎng)絡(luò)的應(yīng)用模式進(jìn)行了分析。Reddy[2]針對(duì)單窗口和單根天線的約束調(diào)度問(wèn)題進(jìn)行了求解，提出的動(dòng)態(tài)算法能夠在約束條件下獲得優(yōu)化結(jié)果。Rojanasoonthon[3]針對(duì)多時(shí)間窗口和多址鏈路約束調(diào)度進(jìn)行求解，采用了分支定界法來(lái)進(jìn)行最優(yōu)解的求解。

在算法方面，顧中舜[4]將蟻群算法運(yùn)用到調(diào)度問(wèn)題中，與經(jīng)典的遺傳算法和模擬退火算法進(jìn)行比較，發(fā)現(xiàn)蟻群算法更適合中繼衛(wèi)星調(diào)度問(wèn)題，無(wú)論是時(shí)間還是精度都更優(yōu)。Liu等[5]利用時(shí)間窗口的靈活范圍和數(shù)學(xué)特征，提出了一種調(diào)度算法，與其他經(jīng)典算法對(duì)比，提高了約11%的任務(wù)完成率。He等[6]基于中繼衛(wèi)星動(dòng)態(tài)調(diào)度中的多址問(wèn)題，構(gòu)建了一種基于隨機(jī)優(yōu)化的數(shù)學(xué)架構(gòu)，將問(wèn)題轉(zhuǎn)化為一個(gè)天線內(nèi)嵌多個(gè)的形式，并利用了2種算法進(jìn)行求解。張彥等[7]主要針對(duì)新增任務(wù)和任務(wù)時(shí)間變化等動(dòng)態(tài)擾動(dòng)建立了中繼衛(wèi)星動(dòng)態(tài)調(diào)度模型，并提出了動(dòng)態(tài)擴(kuò)展/刪除樹(shù)搜索算法，以刪除任務(wù)和調(diào)整任務(wù)之比作為指導(dǎo)，提高了算法效率，并證明了其能夠在實(shí)際中運(yùn)用。

上述研究主要側(cè)重于中繼衛(wèi)星系統(tǒng)靜態(tài)任務(wù)調(diào)度。隨著中繼衛(wèi)星的運(yùn)用范圍越來(lái)越大，各類(lèi)型用戶目標(biāo)對(duì)中繼衛(wèi)星系統(tǒng)資源需求動(dòng)態(tài)性越來(lái)越高，而且在未來(lái)戰(zhàn)爭(zhēng)中，中繼衛(wèi)星系統(tǒng)作為重要戰(zhàn)略資源是敵人破壞摧毀的目標(biāo)。面對(duì)海量應(yīng)急中繼使用需求或資源受損時(shí)，如何快速重新進(jìn)行資源分配調(diào)整計(jì)劃，成為發(fā)揮或保持整個(gè)中繼衛(wèi)星系統(tǒng)效能的關(guān)鍵。當(dāng)前研究對(duì)中繼衛(wèi)星的調(diào)度方法大多是針對(duì)單目標(biāo)需求進(jìn)行優(yōu)化，如最大化任務(wù)完成度，對(duì)于多目標(biāo)情況的研究鮮有涉及。

因此，本文針對(duì)中繼衛(wèi)星系統(tǒng)接收海量臨時(shí)申請(qǐng)或者中繼資源故障時(shí)如何快速進(jìn)行重調(diào)度問(wèn)題進(jìn)行研究，以滿足最大化任務(wù)完成率和最小化動(dòng)態(tài)擾動(dòng)測(cè)度2個(gè)互相沖突的需求為優(yōu)化目標(biāo)，建立了調(diào)度過(guò)程中突發(fā)新增任務(wù)的動(dòng)態(tài)調(diào)度的模型，基于NSGA-Ⅱ多目標(biāo)優(yōu)化算法，對(duì)中繼衛(wèi)星進(jìn)行動(dòng)態(tài)重調(diào)度。

1 中繼衛(wèi)星應(yīng)用模式

1.1 系統(tǒng)工作原理和流程

中繼衛(wèi)星系統(tǒng)是指將中繼衛(wèi)星發(fā)射至地球的靜止軌道，并將地面站作為終端，對(duì)中低軌道衛(wèi)星進(jìn)行大面積覆蓋，提供測(cè)控通信和數(shù)據(jù)中繼的系統(tǒng)。

中繼衛(wèi)星系統(tǒng)概貌如圖1所示，可以將整個(gè)中繼衛(wèi)星系統(tǒng)分為3個(gè)部分：第1部分是中繼衛(wèi)星；第2部分是用戶層，由多種用戶航天器構(gòu)成；第3部分為地面設(shè)施，主要包含用戶航天器及中繼衛(wèi)星的管理中心和地面網(wǎng)絡(luò)終端。

圖1 中繼衛(wèi)星系統(tǒng)概貌Fig.1 Overview of relay satellite system

由于用戶層與地面可見(jiàn)時(shí)間較短，需要利用中繼衛(wèi)星進(jìn)行數(shù)據(jù)中轉(zhuǎn)，在用戶航天器與中繼衛(wèi)星的可見(jiàn)時(shí)間窗口內(nèi)，將需要傳給地面的數(shù)據(jù)信息傳給中繼衛(wèi)星。用戶航天器管理部門(mén)需要根據(jù)中繼衛(wèi)星管理部門(mén)對(duì)外發(fā)布的下一周期衛(wèi)星資源，以及自身的任務(wù)需求，向中繼衛(wèi)星的管理部門(mén)提交任務(wù)申請(qǐng)，中繼衛(wèi)星管理部門(mén)對(duì)用戶需求進(jìn)行整理，科學(xué)合理地分配有限的衛(wèi)星資源，并生成調(diào)度方案。對(duì)于突發(fā)情況，中繼衛(wèi)星管理部門(mén)會(huì)及時(shí)啟用相應(yīng)的動(dòng)態(tài)調(diào)度算法進(jìn)行調(diào)整，保證中繼衛(wèi)星服務(wù)的正常運(yùn)行，并獲得動(dòng)態(tài)調(diào)度方案。最后，各部門(mén)依據(jù)最終方案，完成地面站和用戶航天器之間的數(shù)據(jù)傳輸任務(wù)。

1.2 系統(tǒng)應(yīng)用模式分析

本文的中繼衛(wèi)星系統(tǒng)應(yīng)用模式采用傳統(tǒng)的通用模式，可歸納如下[8-10]：

① 用戶管理部門(mén)提交的任務(wù)申請(qǐng)信息包括其任務(wù)的緊急程度、需求的服務(wù)時(shí)間和窗口等。提交的每一項(xiàng)任務(wù)只能所屬一個(gè)用戶航天器，通常對(duì)應(yīng)一個(gè)或多個(gè)中繼衛(wèi)星服務(wù)時(shí)間窗口，任務(wù)必須一次性完成。

② 在用戶申請(qǐng)完畢后，由中繼衛(wèi)星管理部門(mén)進(jìn)行統(tǒng)計(jì)，并通過(guò)靜態(tài)調(diào)度算法，根據(jù)用戶需求生成合理的衛(wèi)星調(diào)度方案，依據(jù)調(diào)度方案完成任務(wù)。

③ 對(duì)于在中繼衛(wèi)星執(zhí)行任務(wù)過(guò)程中可能出現(xiàn)的動(dòng)態(tài)擾動(dòng)，如緊急新增任務(wù)、資源失效等任務(wù)變化，導(dǎo)致靜態(tài)調(diào)度方案中部分任務(wù)可能無(wú)法按原有方案進(jìn)行執(zhí)行時(shí)，需要緊急啟用動(dòng)態(tài)調(diào)度算法，進(jìn)行動(dòng)態(tài)調(diào)度，來(lái)滿足任務(wù)需求；失效資源上已安排的任務(wù)均作為新增任務(wù)申請(qǐng)進(jìn)行重新分配。

④ 在靜態(tài)調(diào)度方案和動(dòng)態(tài)方案生成完畢后，獲得一個(gè)新的方案，中繼衛(wèi)星將按新的方案執(zhí)行任務(wù)。同時(shí)，中繼衛(wèi)星管理部門(mén)需要將任務(wù)執(zhí)行情況下達(dá)至各個(gè)用戶及所對(duì)應(yīng)的地面站。

2 考慮任務(wù)擾動(dòng)的中繼衛(wèi)星重調(diào)度模型

中繼衛(wèi)星系統(tǒng)調(diào)度問(wèn)題復(fù)雜，涉及變量眾多，約束條件繁雜，因此本文在構(gòu)建模型時(shí)做了適當(dāng)簡(jiǎn)化，降低求解難度。

2.1 問(wèn)題假設(shè)

為降低問(wèn)題建模與求解難度，對(duì)中繼衛(wèi)星任務(wù)調(diào)度問(wèn)題做了簡(jiǎn)化，做如下基本假設(shè)[11-13]：

① 不考慮不同任務(wù)間可能存在的相關(guān)性；

② 所有任務(wù)被執(zhí)行時(shí)必須一次性完成；

③ 用戶申請(qǐng)的服務(wù)時(shí)間窗口為固定的時(shí)間窗口，不具備彈性。

2.2 變量符號(hào)說(shuō)明

本文構(gòu)建的中繼衛(wèi)星重調(diào)度模型將要用到的變量定義如表1所示。

表1 符號(hào)定義Tab.1 Symbol definition

2.3 模型決策變量和優(yōu)化目標(biāo)

2.3.1 決策變量

在本文選定的應(yīng)用模式下，整個(gè)問(wèn)題實(shí)際上就是對(duì)用戶申請(qǐng)的任務(wù)確定6個(gè)要素的信息：任務(wù)的執(zhí)行緊急程度、任務(wù)執(zhí)行的最早開(kāi)始時(shí)間和最晚結(jié)束時(shí)間、任務(wù)的執(zhí)行所需時(shí)間、任務(wù)能被執(zhí)行的天線和任務(wù)對(duì)應(yīng)用戶航天器。故模型的決策變量為xtrj,actstrj和acdtrj。

決策變量xtrj的值只有0或1兩種，用來(lái)表示任務(wù)是否被成功執(zhí)行，成功其值為1，不成功則為0。決策變量actstrj表示在可見(jiàn)窗口j內(nèi)，任務(wù)t在被資源r執(zhí)行的開(kāi)始時(shí)間，為一個(gè)連續(xù)變量。決策變量acdtrj，表示在可見(jiàn)窗口j內(nèi)，任務(wù)t在被資源r執(zhí)行的實(shí)際持續(xù)時(shí)間，為一個(gè)連續(xù)變量。

2.3.2 優(yōu)化目標(biāo)

在中繼衛(wèi)星重調(diào)度模型中，選取最大化任務(wù)執(zhí)行率和最小化動(dòng)態(tài)擾動(dòng)測(cè)度為目標(biāo)函數(shù)。最大化任務(wù)完成率是指算法求解時(shí)，在滿足約束條件的情況下，向任務(wù)完成率最大的解靠近。

動(dòng)態(tài)擾動(dòng)測(cè)度(DDM)是指當(dāng)動(dòng)態(tài)擾度發(fā)生后，經(jīng)過(guò)算法產(chǎn)生的動(dòng)態(tài)調(diào)度方案與之前靜態(tài)調(diào)度的方案的差異程度[14]：

ψ(s0,snew)=λdelndel+λcnc，

(1)

式中，s0表示靜態(tài)調(diào)度的方案；snew表示動(dòng)態(tài)調(diào)度后產(chǎn)生的新方案；ndel表示從靜態(tài)至動(dòng)態(tài)調(diào)度刪除的任務(wù)與除新增任務(wù)外另增加的任務(wù)數(shù)量之和；nc表示從靜態(tài)調(diào)度到動(dòng)態(tài)調(diào)度的任務(wù)調(diào)整數(shù)量(比如任務(wù)從第1個(gè)衛(wèi)星調(diào)整到第2個(gè)衛(wèi)星執(zhí)行)數(shù)量；λ表示任務(wù)的權(quán)重。重調(diào)度的目標(biāo)函數(shù)為：

(2)

minf2=λdelndel+λcnc。

(3)

本文建立的中繼衛(wèi)星重調(diào)度模型中，將最大化任務(wù)完成率作為本文的優(yōu)化目標(biāo)，即希望通過(guò)算法求解時(shí)，在滿足約束條件的情況下，向任務(wù)完成率最大的解靠近。

2.4 約束條件

在中繼衛(wèi)星系統(tǒng)調(diào)度問(wèn)題中，主要涉及兩方面約束：一方面為資源約束；另一方面為任務(wù)需求約束。

2.4.1 資源約束

資源約束包括可見(jiàn)時(shí)間窗口約束和資源的使用約束。

① 可見(jiàn)時(shí)間窗口約束

中繼衛(wèi)星與用戶航天器之間可以傳輸數(shù)據(jù)的時(shí)間稱(chēng)為可見(jiàn)時(shí)間窗口，要求在任務(wù)被執(zhí)行的過(guò)程中，必須與其所屬的用戶航天器對(duì)應(yīng)的與中繼衛(wèi)星的可見(jiàn)時(shí)間窗口匹配。由此可得約束條件C1,C2：

(4)

(5)

C1表示任務(wù)執(zhí)行的開(kāi)始時(shí)間不能小于其所屬的用戶航天器與中繼衛(wèi)星的可見(jiàn)時(shí)間窗口的開(kāi)始時(shí)間。C2表示任務(wù)執(zhí)行的結(jié)束時(shí)間不能大于其所屬的用戶航天器與中繼衛(wèi)星的可見(jiàn)時(shí)間窗口的結(jié)束時(shí)間。

② 天線資源約束

在中繼衛(wèi)星重調(diào)度問(wèn)題中，一個(gè)天線資源在任意時(shí)刻只能執(zhí)行一個(gè)任務(wù)，得到約束C3：

C3:(adjust+Dmr+rec)∩(adjust+Dnr+rec)=φ,

?t∈T,r∈R,m∈T。

(6)

2.4.2 任務(wù)需求約束

任務(wù)方面的約束包括任務(wù)執(zhí)行時(shí)間約束和任務(wù)執(zhí)行約束。

① 任務(wù)服務(wù)時(shí)長(zhǎng)約束

在中繼衛(wèi)星重調(diào)度問(wèn)題中，任務(wù)在被調(diào)度時(shí)，分配的任務(wù)時(shí)長(zhǎng)必須等于任務(wù)需求的服務(wù)時(shí)長(zhǎng)，可得約束C4：

(7)

② 任務(wù)時(shí)間窗口約束

與可見(jiàn)時(shí)間窗口相似，任務(wù)不是時(shí)時(shí)都能夠被執(zhí)行，每個(gè)任務(wù)都有一個(gè)能被執(zhí)行的窗口，稱(chēng)為服務(wù)時(shí)間窗口，因此任務(wù)的執(zhí)行時(shí)間都應(yīng)在任務(wù)服務(wù)時(shí)間窗口內(nèi)。可得約束C5,C6：

(8)

(9)

C5表示任務(wù)的執(zhí)行時(shí)刻應(yīng)遲于其對(duì)應(yīng)的服務(wù)時(shí)間窗口的開(kāi)始時(shí)間。C6表示任務(wù)的執(zhí)行結(jié)束時(shí)刻應(yīng)早于其對(duì)應(yīng)的服務(wù)時(shí)間窗口的結(jié)束時(shí)刻。

③ 任務(wù)執(zhí)行約束

在中繼衛(wèi)星重調(diào)度問(wèn)題中，中繼衛(wèi)星執(zhí)行的任務(wù)只能被一個(gè)天線選擇執(zhí)行，同時(shí)也只能選擇一個(gè)可見(jiàn)時(shí)間窗口被執(zhí)行，可得約束C7,C8：

(10)

(11)

2.5 重調(diào)度數(shù)學(xué)模型

本文所構(gòu)建的中繼衛(wèi)星多目標(biāo)重調(diào)度模型以任務(wù)完成率最大化和動(dòng)態(tài)擾動(dòng)測(cè)度最小化為目標(biāo)，以資源和任務(wù)需求為約束，構(gòu)建的具體數(shù)學(xué)模型如下：

minf2=λdelndel+λcnc，

3 基于多目標(biāo)優(yōu)化的重調(diào)度算法

本文研究的內(nèi)容為多目標(biāo)優(yōu)化下的中繼衛(wèi)星的重調(diào)度。基于多目標(biāo)優(yōu)化，選取NSGA-Ⅱ這一多目標(biāo)優(yōu)化領(lǐng)域內(nèi)的流行算法作為本文動(dòng)態(tài)調(diào)度問(wèn)題的優(yōu)化算法，探究其對(duì)中繼衛(wèi)星動(dòng)態(tài)調(diào)度的優(yōu)化效果。

3.1 算法簡(jiǎn)介

NSGA-Ⅱ作為優(yōu)化算法的一種，基于遺傳算法改進(jìn)而來(lái)。遺傳算法作為經(jīng)典的智能優(yōu)化算法，是以達(dá)爾文生物學(xué)中“優(yōu)勝劣汰”為背景，以自然選擇和遺傳作為原理，模擬生物進(jìn)化的一種算法。NSGA-Ⅱ算法繼承了遺傳算法優(yōu)勝劣汰的思想，同時(shí)引進(jìn)了Pareto支配關(guān)系和非支配排序、種群擁擠度和精英保留策略等思想[15]。Pareto支配關(guān)系和非支配排序主要是為多目標(biāo)優(yōu)化服務(wù)，種群擁擠度的提出是為了得到最優(yōu)解在空間中形成均勻的分布，精英保留策略則是為了更方便地選擇出更為優(yōu)秀的個(gè)體，遺傳至下一代。

3.2 流程設(shè)計(jì)

① 生成靜態(tài)調(diào)度方案

首先，根據(jù)用戶提交的任務(wù)信息和中繼衛(wèi)星資源信息，利用靜態(tài)調(diào)度算法生成初始的靜態(tài)調(diào)度方案。主要是通過(guò)任務(wù)的服務(wù)窗口和中繼衛(wèi)星與用戶航天器的可見(jiàn)時(shí)間窗口的交集生成任務(wù)的可用時(shí)間，運(yùn)用算法進(jìn)行初步的任務(wù)調(diào)度，得到靜態(tài)調(diào)度方案，方便后續(xù)動(dòng)態(tài)擾度測(cè)定計(jì)算。

② 對(duì)第一代種群進(jìn)行非支配排序

靜態(tài)調(diào)度后進(jìn)行動(dòng)態(tài)調(diào)度初始方案的生成。在動(dòng)態(tài)調(diào)度中，要保證新增任務(wù)必須執(zhí)行，然后考慮執(zhí)行新增任務(wù)后，資源和任務(wù)的匹配生成動(dòng)態(tài)調(diào)度的初始解，即整個(gè)進(jìn)化算法的初始種群。然后計(jì)算種群中每個(gè)個(gè)體的目標(biāo)函數(shù)值，本文考慮的多目標(biāo)為最大化任務(wù)完成率和最小化動(dòng)態(tài)擾動(dòng)測(cè)度，依據(jù)多目標(biāo)函數(shù)值，對(duì)每個(gè)個(gè)體進(jìn)行非支配排序。

③ 選擇、交叉、變異

選擇是指從父代中選出優(yōu)秀的個(gè)體，進(jìn)行交配產(chǎn)生下一代。在遺傳算法中選擇的方式有很多，如輪盤(pán)賭和錦標(biāo)賽選擇法等。NSGA-Ⅱ中運(yùn)用的錦標(biāo)賽選擇法，即從種群N個(gè)個(gè)體中，選出k個(gè)個(gè)體，一般取N的一半，然后根據(jù)個(gè)體的適應(yīng)度(Pareto等級(jí)和擁擠度)，將表現(xiàn)最好的個(gè)體放入交配集。

交叉之前進(jìn)行編碼，將每個(gè)任務(wù)和執(zhí)行任務(wù)的衛(wèi)星都用二進(jìn)制的方式表達(dá)出來(lái)。染色體編碼示意如圖2所示。

將所有的任務(wù)編碼完畢后，一個(gè)任務(wù)及其執(zhí)行情況將會(huì)對(duì)應(yīng)一段同樣長(zhǎng)度的編碼，然后進(jìn)行交叉，產(chǎn)生新的2段不同的編碼，本文選用兩點(diǎn)交叉法，實(shí)現(xiàn)過(guò)程不復(fù)雜，也有較好的隨機(jī)性。兩點(diǎn)交叉法示意如圖3所示。

圖3 兩點(diǎn)交叉法示意Fig.3 Schematic diagram of two-point crossover method

④ 精英選擇

將輸出的子代與父代合并為同一個(gè)種群，計(jì)算種群中每個(gè)個(gè)體的目標(biāo)函數(shù)值，即最大化任務(wù)完成率和最小化動(dòng)態(tài)擾動(dòng)測(cè)度，依據(jù)多目標(biāo)函數(shù)值，對(duì)每個(gè)個(gè)體進(jìn)行非支配排序，然后對(duì)恰好無(wú)法全部放入種群的那層Pareto層級(jí)個(gè)體進(jìn)行擁擠度計(jì)算，保留擁擠度較大的個(gè)體進(jìn)入下一代。精英選擇示意如圖4所示。

圖4 精英選擇示意Fig.4 Schematic diagram of elite selection

⑤ 算法結(jié)束

將上面的4個(gè)步驟循環(huán)一次，代表整個(gè)種群進(jìn)化了一次，持續(xù)循環(huán)直到滿足輸出條件，得到最后的優(yōu)化結(jié)果，即重調(diào)度的最終結(jié)果。

4 仿真實(shí)驗(yàn)和結(jié)果分析

4.1 任務(wù)需求信息

① 任務(wù)編號(hào)

在實(shí)驗(yàn)中，為了方便，任務(wù)直接從1開(kāi)始編號(hào)。

② 任務(wù)對(duì)應(yīng)航天器

任務(wù)實(shí)際能夠被執(zhí)行的時(shí)間，實(shí)際上為任務(wù)對(duì)應(yīng)航天器和中繼衛(wèi)星的可見(jiàn)時(shí)間窗口和任務(wù)的執(zhí)行時(shí)間窗口的交集。每一個(gè)任務(wù)相應(yīng)地對(duì)應(yīng)一個(gè)航天器，在本文的實(shí)驗(yàn)中，采用均勻生成隨機(jī)數(shù)的方法，將任務(wù)與航天器一一匹配。

ust=ceil(λ*us)，

(12)

式中，ust表示任務(wù)的航天器編號(hào)；ceil表示向上取整；λ表示(0，1)的隨機(jī)數(shù)；us表示每個(gè)實(shí)驗(yàn)中用戶航天器的數(shù)量。

③ 任務(wù)服務(wù)時(shí)間

由用戶提交任務(wù)能夠被執(zhí)行的開(kāi)始時(shí)間和結(jié)束時(shí)間。在本文的仿真實(shí)驗(yàn)中，通過(guò)隨機(jī)數(shù)和正態(tài)分布來(lái)生成。

stst=λ*86 400，

(13)

stet=stst+abs(normrnd(mean,std))，

(14)

式中，stst表示開(kāi)始時(shí)間；stet表示結(jié)束時(shí)間；mean表示整個(gè)服務(wù)時(shí)間正態(tài)分布的均值；std表示整個(gè)服務(wù)時(shí)間正態(tài)分布的標(biāo)準(zhǔn)差；abs表示取絕對(duì)值。

④ 任務(wù)服務(wù)時(shí)長(zhǎng)

用戶根據(jù)其需求對(duì)任務(wù)進(jìn)行評(píng)估后提交的信息。在本文的實(shí)驗(yàn)中，根據(jù)隨機(jī)數(shù)和正態(tài)分布來(lái)生成。任務(wù)服務(wù)時(shí)長(zhǎng)為：

dt=abs(normrnd(mean,std))。

(15)

部分任務(wù)數(shù)據(jù)信息如表2所示。

表2 任務(wù)數(shù)據(jù)信息表Tab.2 Task data information

4.2 仿真實(shí)驗(yàn)參數(shù)設(shè)定

在本文的實(shí)驗(yàn)中，選擇86 400 s作為調(diào)度周期。然后根據(jù)不同的變量構(gòu)建實(shí)驗(yàn)，觀察不同變量的變化對(duì)整個(gè)動(dòng)態(tài)調(diào)度優(yōu)化效果的影響。最大參數(shù)規(guī)模可以達(dá)到500個(gè)任務(wù)申請(qǐng)、3顆中繼衛(wèi)星、10個(gè)航天器。本次實(shí)驗(yàn)的環(huán)境參數(shù)如表3所示。

表3 環(huán)境參數(shù)Tab.3 Environmental parameters

4.3 優(yōu)化結(jié)果展示與算法性能分析

為研究NSGA-Ⅱ算法對(duì)中繼衛(wèi)星動(dòng)態(tài)調(diào)度的優(yōu)化效果以及不同中繼衛(wèi)星數(shù)量、用戶航天器數(shù)量和新增任務(wù)數(shù)量對(duì)優(yōu)化效果的影響，本文選擇300個(gè)任務(wù)規(guī)模，做新增任務(wù)和用戶航天器數(shù)量變化實(shí)驗(yàn)，在500個(gè)任務(wù)規(guī)模做中繼衛(wèi)星數(shù)量變化實(shí)驗(yàn)，并在相同條件下選取了經(jīng)典的多目標(biāo)算法SPEA-Ⅱ算法進(jìn)行優(yōu)化效果對(duì)比。

在本文中選用超體積指標(biāo)(HV)做算法性能評(píng)價(jià)[16]，在雙目標(biāo)優(yōu)化問(wèn)題中，HV的運(yùn)算方法為獲得的非支配解集的每個(gè)個(gè)體與參照點(diǎn)(最大值個(gè)體)在空間中圍成的矩形的面積之和，HV值越大，說(shuō)明算法的綜合性能越好。

(16)

4.3.1 300個(gè)任務(wù)申請(qǐng)

在300個(gè)任務(wù)規(guī)模時(shí)，將中繼衛(wèi)星數(shù)量固定為2，考慮此基礎(chǔ)上的優(yōu)化效果以及不同新增任務(wù)數(shù)量和不同用戶航天器數(shù)量對(duì)優(yōu)化效果的影響。

① 新增任務(wù)數(shù)量對(duì)算法的影響

不同新增任務(wù)優(yōu)化效果對(duì)比如圖5所示。

(a) 2個(gè)新增任務(wù)

(b) 4個(gè)新增任務(wù)

(c) 6個(gè)新增任務(wù)

(d) 8個(gè)新增任務(wù)

(e) 10個(gè)新增任務(wù)

(f) 12個(gè)新增任務(wù)

(g) 14個(gè)新增任務(wù)

(h) 16個(gè)新增任務(wù)

(i) 18個(gè)新增任務(wù)

(j) 20個(gè)新增任務(wù)圖5 優(yōu)化效果對(duì)比Fig.5 Optimization effect comparison

不同新增任務(wù)優(yōu)化數(shù)據(jù)對(duì)比如表4所示。

表4 優(yōu)化數(shù)據(jù)對(duì)比Tab.4 Optimized data comparison

圖6展現(xiàn)了在300個(gè)任務(wù)、2顆中繼衛(wèi)星、10個(gè)用戶航天器的條件下，不同新增任務(wù)的優(yōu)化效果，輸出的為在同樣迭代次數(shù)下SPEA-Ⅱ和NSGA-Ⅱ算法優(yōu)化后種群的Pareto最優(yōu)值。

圖6 HV值對(duì)比Fig.6 HV value comparison

由圖6可以看出，在新增任務(wù)數(shù)量不同時(shí)，NSGA-Ⅱ算法輸出的Pareto最優(yōu)解在空間上分布的均勻性、收斂性和廣泛性相較SPEA-Ⅱ算法都更加優(yōu)秀。

對(duì)比圖5可以看出，HV值相較SPEA-Ⅱ要更大，說(shuō)明NSGA-Ⅱ算法在中繼衛(wèi)星動(dòng)態(tài)調(diào)度優(yōu)化方面性能更好，能優(yōu)化出收斂性和多樣性更佳的非支配個(gè)體。

② 對(duì)算法的影響

不同用戶航天器數(shù)量?jī)?yōu)化效果對(duì)比如圖7所示。

(a) 2個(gè)用戶航天器

(b) 4個(gè)用戶航天器

(c) 6個(gè)用戶航天器

(d) 8個(gè)用戶航天器

(e) 10個(gè)用戶航天器

(f) 12個(gè)用戶航天器

(g) 14個(gè)用戶航天器圖7 優(yōu)化效果對(duì)比Fig.7 Optimization effect comparison

不同用戶航天器數(shù)量?jī)?yōu)化數(shù)據(jù)對(duì)比如表5所示。

表5 優(yōu)化數(shù)據(jù)對(duì)比Tab.5 Optimized data comparison

圖8展示了在300個(gè)任務(wù)、2顆中繼衛(wèi)星、10個(gè)新增任務(wù)的情況下，不同用戶航天器數(shù)量對(duì)優(yōu)化效果的影響。

由圖8可以看出，在300個(gè)任務(wù)條件下，僅用2個(gè)用戶航天器承載任務(wù)會(huì)導(dǎo)致任務(wù)的完成率減少，這是由于任務(wù)的服務(wù)時(shí)間和航天器與衛(wèi)星的可見(jiàn)時(shí)間匹配隨機(jī)概率減少。在不同的用戶航天器情況下，NSGA-Ⅱ算法展現(xiàn)了較強(qiáng)的優(yōu)化性能，得到的Pareto最優(yōu)解適應(yīng)性、均勻性和收斂性都較好。

圖8 HV值對(duì)比Fig.8 HV value comparison

4.3.2 500個(gè)任務(wù)申請(qǐng)

500個(gè)任務(wù)時(shí)，將用戶航天器數(shù)量固定為10個(gè)，考慮此基礎(chǔ)上的優(yōu)化效果及不同中繼衛(wèi)星數(shù)量對(duì)優(yōu)化效果的影響。500個(gè)任務(wù)規(guī)模也和300個(gè)形成對(duì)比，展現(xiàn)不同任務(wù)數(shù)量時(shí)，對(duì)優(yōu)化結(jié)果的影響，優(yōu)化效果對(duì)比如圖9所示，優(yōu)化數(shù)據(jù)對(duì)比如表6所示。

(a) 2顆中繼衛(wèi)星

(b) 3顆中繼衛(wèi)星

(c) 4顆中繼衛(wèi)星圖9 優(yōu)化效果對(duì)比Fig.9 Optimization effect comparison

表6 優(yōu)化數(shù)據(jù)對(duì)比Tab.6 Optimized data comparison

圖10展示了在500個(gè)任務(wù)、10個(gè)用戶航天器、10個(gè)新增任務(wù)的動(dòng)態(tài)擾動(dòng)環(huán)境下，變化中繼衛(wèi)星數(shù)量，對(duì)算法優(yōu)化效果的影響。

圖10 HV值對(duì)比Fig.10 HV value comparison

隨著資源數(shù)量的增加，任務(wù)完成率也隨之增加，且NSGA-Ⅱ算法的優(yōu)化結(jié)果分布更均勻，種群多樣性更高，同時(shí)NSGA-Ⅱ算法的性能，即HV值，要優(yōu)于SPEA-Ⅱ算法。

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

在中繼衛(wèi)星單址天線調(diào)度問(wèn)題基礎(chǔ)上，考慮調(diào)度需求多樣性，構(gòu)建了多目標(biāo)函數(shù)的中繼衛(wèi)星重調(diào)度模型，在生成初始調(diào)度方案后，運(yùn)用NSGA-Ⅱ算法對(duì)初始調(diào)度方案進(jìn)行優(yōu)化。仿真實(shí)驗(yàn)中，本文對(duì)比了在實(shí)驗(yàn)參數(shù)，如任務(wù)規(guī)模和資源數(shù)量等變化的情況下，NSGA-Ⅱ算法的優(yōu)化情況。其總能優(yōu)化得到一個(gè)收斂性、均勻性和廣泛性較好的Pareto最優(yōu)解。在對(duì)比SPEA-Ⅱ這一經(jīng)典多目標(biāo)算法時(shí)，NSGA-Ⅱ展現(xiàn)了更強(qiáng)的適用性，基于多目標(biāo)優(yōu)化的NSGA-Ⅱ算法輸出的Pareto最優(yōu)解，為調(diào)度方案提供了多樣化的選擇，為中繼衛(wèi)星管理部門(mén)和用戶建立了一個(gè)較佳的選擇空間。