1. 上海交通大學(xué) 區(qū)域光纖通信網(wǎng)與新型光通信系統(tǒng)國家重點(diǎn)實(shí)驗(yàn)室，上海 200240 2. 上海衛(wèi)星工程研究所，上海 200240

全球新一輪的月球探索正在拉開序幕，探月范圍正在逐步由月球正面向背面和兩極拓展，探月活動也日趨復(fù)雜[1-4]。由于月球的自轉(zhuǎn)周期和公轉(zhuǎn)周期相同，地球地面站無法與月球背面直接通信，而借助地月中繼衛(wèi)星的中繼通信方式可以解決這個(gè)問題，并滿足面向月球的全時(shí)域、全空域覆蓋的通信要求[3]。

地月中繼衛(wèi)星是指為月球表面的探測器、著陸器、環(huán)月衛(wèi)星等提供數(shù)據(jù)中繼和測控服務(wù)的通信衛(wèi)星。地月中繼衛(wèi)星任務(wù)調(diào)度是指地面任務(wù)管理中心根據(jù)用戶提出的服務(wù)申請，合理地分配地月中繼衛(wèi)星資源及執(zhí)行時(shí)間，以盡可能地滿足用戶服務(wù)需求，提高地月中繼衛(wèi)星資源的利用率。隨著人類對月球的探測不斷深入[5]，未來十幾年各國發(fā)射的月面探測器也將不斷增多。地月中繼衛(wèi)星數(shù)據(jù)傳輸未來也將呈現(xiàn)大容量、多用戶以及多任務(wù)的特點(diǎn)。但是地月中繼衛(wèi)星的資源是極其有限的，如何利用有限的地月中繼衛(wèi)星資源，完成更多的任務(wù)并獲得更好的收益將顯得越來越重要。

近年來，近地的中繼衛(wèi)星任務(wù)調(diào)度問題已經(jīng)有很多人研究[6-9]。Rojanasoonthon等[10]采用并行機(jī)調(diào)度理論研究了美國TDRSS系統(tǒng)調(diào)度問題，考慮了任務(wù)的優(yōu)先級，建立了混合整數(shù)規(guī)劃模型，以最大化任務(wù)完成數(shù)量為目標(biāo)，采用貪婪隨機(jī)搜索算法對其求解。文獻(xiàn)[11]考慮到了數(shù)據(jù)中繼衛(wèi)星激光和微波混合鏈路系統(tǒng)的資源和任務(wù)的約束，建立了混合鏈路資源調(diào)度模型，以最大化完成任務(wù)優(yōu)先級之和為目標(biāo)，提出了一種基于改進(jìn)的遺傳算法。文獻(xiàn)[12]提出了中繼衛(wèi)星日常任務(wù)的調(diào)度模型，也是以最大化完成任務(wù)優(yōu)先級之和為目標(biāo)，采用人工蜂群算法求解。文獻(xiàn)[13]針對中繼衛(wèi)星任務(wù)的動態(tài)性，以最大化完成任務(wù)優(yōu)先級之和以及最小化任務(wù)重調(diào)度數(shù)量為目標(biāo)提出了一種兩階段任務(wù)調(diào)度算法。

上述基于近地中繼衛(wèi)星的任務(wù)調(diào)度研究通常都是以最大化完成任務(wù)數(shù)量和最大完成任務(wù)優(yōu)先級之和作為其優(yōu)化目標(biāo)，一般考慮任務(wù)的優(yōu)先級、用戶衛(wèi)星與中繼衛(wèi)星的可見時(shí)間窗口約束以及衛(wèi)星天線資源的約束。這些研究對于數(shù)傳任務(wù)很少考慮用戶的存儲限制，數(shù)傳任務(wù)在規(guī)定截止時(shí)間內(nèi)傳輸完成，一般就認(rèn)為任務(wù)完成。但是在現(xiàn)實(shí)情況下，用戶由于與地月中繼衛(wèi)星不可見或者中繼衛(wèi)星資源被占用等原因，產(chǎn)生的數(shù)據(jù)不能馬上進(jìn)行傳輸，需要放入存儲器中等待一定時(shí)間。在等待與中繼衛(wèi)星進(jìn)行數(shù)據(jù)傳輸?shù)臅r(shí)間內(nèi)，用戶也將不斷產(chǎn)生數(shù)據(jù)，新產(chǎn)生的數(shù)據(jù)也將會放入存儲器中，等待傳輸。那么如果用戶的剩余存儲容量不足以支撐用戶的下一次任務(wù)所需存儲容量，那么下一次任務(wù)數(shù)據(jù)將丟失(或者新產(chǎn)生的數(shù)據(jù)覆蓋原來的舊數(shù)據(jù)，還未傳輸?shù)呐f數(shù)據(jù)丟失)。而在月球探測過程中的數(shù)據(jù)和圖像是非常珍貴的，在完成任務(wù)收集到數(shù)據(jù)時(shí)，期望這些數(shù)據(jù)能盡可能多的傳輸?shù)降孛?，盡可能減少數(shù)據(jù)的丟失量。

地月中繼衛(wèi)星的任務(wù)包括實(shí)時(shí)性任務(wù)(如遙控遙測類任務(wù))和延遲容忍類任務(wù)(如數(shù)傳類任務(wù))。本文針對地月中繼衛(wèi)星的延遲容忍類任務(wù)，即數(shù)傳任務(wù)展開研究，研究目標(biāo)是盡可能使數(shù)傳任務(wù)的數(shù)據(jù)丟失量最小，從而提高地月中繼衛(wèi)星資源的利用率。

1 地月中繼衛(wèi)星任務(wù)調(diào)度模型

1.1 問題描述

地月中繼系統(tǒng)如圖1所示，地月中繼系統(tǒng)由地月中繼衛(wèi)星、用戶和地面站3部分組成。未來地月中繼衛(wèi)星將有以下幾類用戶：環(huán)月衛(wèi)星、月球探測車、著陸器、月表?xiàng)⒌?、宇航員等。未來地月中繼衛(wèi)星系統(tǒng)中傳輸?shù)娜蝿?wù)將包括遙控、遙測、數(shù)傳、話音、視頻、導(dǎo)航等類型[3],其中只有數(shù)傳任務(wù)是延遲容忍類業(yè)務(wù),其余為實(shí)時(shí)性任務(wù)。本文的研究問題是如何合理的安排這些數(shù)傳任務(wù)的執(zhí)行時(shí)間，減少數(shù)據(jù)的丟失，提高中繼衛(wèi)星的資源利用率。

圖1 地月中繼系統(tǒng)模型Fig.1 Model of Earth-Moon relay system

隨著探月的深入，月球上的用戶數(shù)將會不斷增多，任務(wù)將會隨之增多。但是地月中繼衛(wèi)星在同一時(shí)間能服務(wù)的用戶數(shù)量是有限的，并不能滿足所有用戶的要求。所以本文的目的是在滿足地月中繼衛(wèi)星任務(wù)調(diào)度約束的前提下，找到一種合適地月中繼衛(wèi)星資源調(diào)度策略，使得數(shù)傳任務(wù)的數(shù)據(jù)丟失量最小。

為了簡化研究問題，假設(shè)：

1)由于實(shí)時(shí)性任務(wù)的優(yōu)先級相對于數(shù)傳任務(wù)的優(yōu)先級較高，所以在本文中對于數(shù)傳任務(wù)的研究是在實(shí)時(shí)任務(wù)調(diào)度完成之后，所用的時(shí)間窗是地月中繼衛(wèi)星的剩余時(shí)間窗口資源。

2)所有數(shù)傳任務(wù)的任務(wù)開始時(shí)間是已知的，是靜態(tài)的任務(wù)調(diào)度研究。靜態(tài)業(yè)務(wù)是指任務(wù)提前可預(yù)知，在任務(wù)開始之前有足夠的時(shí)間進(jìn)行任務(wù)規(guī)劃，可以采用耗時(shí)較長的搜索算法來尋求優(yōu)化解。數(shù)傳任務(wù)的結(jié)束時(shí)間是仿真結(jié)束時(shí)間，任務(wù)在仿真結(jié)束時(shí)間之前回傳即可，存儲溢出就算任務(wù)調(diào)度失敗。

3)不考慮數(shù)據(jù)采集階段的消耗時(shí)間。假設(shè)數(shù)據(jù)在數(shù)傳任務(wù)開始時(shí)存儲到用戶中。數(shù)傳任務(wù)執(zhí)行結(jié)束后，會釋放數(shù)傳任務(wù)的存儲空間。

4)不考慮中繼衛(wèi)星從一個(gè)用戶切換到另一個(gè)用戶所需要的時(shí)間。

地月中繼衛(wèi)星任務(wù)調(diào)度的約束包括以下幾點(diǎn)。

(1)地月中繼衛(wèi)星用戶屬性約束

地月中繼衛(wèi)星用戶屬性約束包括可見時(shí)間窗約束和用戶存儲約束。

可見時(shí)間窗約束：用戶與地月中繼衛(wèi)星并非時(shí)時(shí)可見，只有當(dāng)他們位于彼此可見的范圍內(nèi)，才能建立通信鏈路，所以任務(wù)的執(zhí)行時(shí)間必須在中繼衛(wèi)星與用戶的可見時(shí)間窗口內(nèi)。

用戶存儲約束：針對于數(shù)傳任務(wù)來說，用戶的剩余存儲容量必須大于任務(wù)所需存儲量，任務(wù)才能正常執(zhí)行，否則直接判定任務(wù)調(diào)度失敗。用戶的剩余存儲容量對于每一個(gè)任務(wù)來說可能都是不一樣的，需要根據(jù)這個(gè)任務(wù)之前開始的任務(wù)的調(diào)度狀態(tài)來確定。

(2)任務(wù)屬性約束

用戶提交任務(wù)申請時(shí)，會提交任務(wù)的優(yōu)先級、任務(wù)的持續(xù)時(shí)間、任務(wù)最早開始時(shí)間以及任務(wù)最晚結(jié)束時(shí)間。對于數(shù)據(jù)傳輸類任務(wù)除了上述要求外，還需要知道任務(wù)的數(shù)據(jù)量大小，及用戶的剩余存儲量。

進(jìn)行任務(wù)調(diào)度時(shí)必須考慮以下內(nèi)容：1)任務(wù)的執(zhí)行時(shí)間必須在任務(wù)的有效時(shí)間內(nèi);2)任務(wù)一次傳輸完成，不考慮任務(wù)拆分;3)對于新產(chǎn)生的數(shù)據(jù)傳輸類任務(wù)要考慮用戶剩余存儲容量是否超出任務(wù)的數(shù)據(jù)量。若任務(wù)的數(shù)據(jù)量超出用戶的剩余存儲容量，則該任務(wù)數(shù)據(jù)被丟棄。

(3)中繼衛(wèi)星資源約束

地月中繼衛(wèi)星資源在本文中指地月中繼衛(wèi)星數(shù)目以及一顆地月中繼衛(wèi)星在同一時(shí)刻能連接的用戶數(shù)量。

1.2 符號說明

數(shù)學(xué)模型中出現(xiàn)的相關(guān)符號說明如下。

U：用戶集合，用戶數(shù)目為Nu。

Tu：用戶u的任務(wù)集，任務(wù)總數(shù)是Nt。

qi：任務(wù)i的數(shù)據(jù)量大小，i∈Tu。

[tsi,tei]：任務(wù)i的有效時(shí)間，tsi為任務(wù)i的最早開始時(shí)間，tei為任務(wù)i的最晚截止時(shí)間。

di：任務(wù)i的持續(xù)時(shí)間，i∈Tu。

Si：用戶u在將要開始執(zhí)行任務(wù)i時(shí)的剩余存儲容量。

M：地月中繼衛(wèi)星的鏈路集合，數(shù)量為Nm。

Vj：表示鏈路j的數(shù)據(jù)傳輸速率，所以任務(wù)i在鏈路j的持續(xù)時(shí)間di=qi/Vj。

Wij：任務(wù)i在鏈路j上的時(shí)間窗口集合，時(shí)間窗口數(shù)量為Nw。

Wsij(k)：任務(wù)i在鏈路j上的第k個(gè)時(shí)間窗口的開始時(shí)間。

Weij(k)：任務(wù)i在鏈路j上的第k個(gè)時(shí)間窗口的結(jié)束時(shí)間。

yij(k)：表示任務(wù)i在鏈路j上的第k個(gè)時(shí)間窗口上的調(diào)度情況，yij(k)∈{0,1}，yij(k)=0，則表示任務(wù)i在鏈路j上的第k個(gè)時(shí)間窗口上調(diào)度成功，反之，則任務(wù)失敗。

τsij：任務(wù)i在鏈路j的開始執(zhí)行時(shí)間。

τeij：任務(wù)i在鏈路j的執(zhí)行結(jié)束時(shí)間。

1.3 數(shù)學(xué)模型的建立

基于上述的問題描述與分析，地月中繼衛(wèi)星任務(wù)調(diào)度問題的數(shù)學(xué)模型如下：

(1)

s.t.

τeij(k)=τsij(k)+di,ifyij(k)=0

(2)

(3)

qi≤Si,ifyij(k)=0

(4)

(5)

(6)

其中，目標(biāo)函數(shù)f表示最小化數(shù)據(jù)丟失量。約束條件式(2)表示任務(wù)的結(jié)束時(shí)間是任務(wù)開始時(shí)間和任務(wù)持續(xù)時(shí)間之和。約束條件式(3)表示時(shí)間窗口的約束，任務(wù)的執(zhí)行時(shí)間必須在可見時(shí)間窗口內(nèi)，而且任務(wù)執(zhí)行時(shí)間還必須得在任務(wù)有效期限內(nèi)。約束條件式(4)表示，在開始任務(wù)i之前，必須確保用戶的剩余存儲容量大于任務(wù)i的數(shù)據(jù)量，否則任務(wù)i無法執(zhí)行，這里的用戶剩余存儲容量是隨著任務(wù)調(diào)度情況不斷變化的。約束條件式(5)表示用戶在同一時(shí)間只能通過一條鏈路執(zhí)行任務(wù)。約束條件(6)表示地月中繼衛(wèi)星的一條鏈路在同一時(shí)刻只能服務(wù)于一個(gè)用戶。

根據(jù)上述地月中繼衛(wèi)星任務(wù)調(diào)度模型，本文把任務(wù)調(diào)度轉(zhuǎn)化為任務(wù)調(diào)度次序的求解。根據(jù)任務(wù)調(diào)度的順序依次判斷任務(wù)是否符合式(2)～(6)，若是符合則任務(wù)調(diào)度成功，若是不符合則任務(wù)調(diào)度失敗。所以目標(biāo)是找到一個(gè)合適的調(diào)度順序，使得任務(wù)的數(shù)據(jù)丟失量最小。一顆近地中繼衛(wèi)星的任務(wù)調(diào)度問題在文獻(xiàn)[10]中已經(jīng)被證明為一個(gè)NP-hard問題，所以在任務(wù)數(shù)量過大時(shí)很難在多項(xiàng)式時(shí)間求解。而通常求解這類問題會采用啟發(fā)式算法和智能搜索算法。由于在本文中討論的是靜態(tài)業(yè)務(wù)調(diào)度，對于計(jì)算時(shí)間要求相對較小，所以為了得到更好的調(diào)度方案，采用智能搜索算法。

而煙花算法是一種新型的智能搜索算法，目前在很多領(lǐng)域取得比較好的應(yīng)用。煙花算法通過爆炸的操作實(shí)現(xiàn)了局部搜索和全局搜索的平衡，相比于遺傳算法，不容易陷入局部最優(yōu)解，能找到更好的解。所以本文采用了基于離散煙花算法進(jìn)行地月中繼衛(wèi)星任務(wù)調(diào)度的算法設(shè)計(jì)。

2 任務(wù)調(diào)度算法

2.1 煙花算法概述

煙花算法(Fireworks Algorithm, FWA)是根據(jù)煙花爆炸這種現(xiàn)象演變而來的一種群體智能搜索算法，自提出以來在很多領(lǐng)域得到了廣泛的應(yīng)用與研究[14-16]。

煙花算法由4部分組成：爆炸算子、高斯變異算子、映射規(guī)則和選擇策略。爆炸算子的作用是在煙花周圍產(chǎn)生火花，火花的數(shù)量和爆炸的振幅都是由爆炸算子決定的。然后通過突變算子產(chǎn)生一些火花。在經(jīng)過兩種算子后，如果新產(chǎn)生的一些火花不在可行解范圍內(nèi)，那么映射規(guī)則將這些火花映射到可行解區(qū)域內(nèi)。最后用選擇算子從火花中挑選出進(jìn)入下一代的群體。煙花算法將不斷執(zhí)行上述的過程，直到符合終止條件。

傳統(tǒng)的煙花算法是為了實(shí)參優(yōu)化而設(shè)計(jì)的，其中的爆炸算子和變異算子適合用在較大的空間中搜索，然后通過選擇算子決定下一代煙花種群。但是地月中繼衛(wèi)星任務(wù)調(diào)度問題則是一個(gè)組合優(yōu)化問題，是離散數(shù)學(xué)問題，所以不能把標(biāo)準(zhǔn)的煙花算法直接應(yīng)用到求解地月中繼衛(wèi)星任務(wù)調(diào)度問題中。針對求解地月中繼衛(wèi)星任務(wù)調(diào)度問題，本文設(shè)計(jì)了一種求解地月中繼衛(wèi)星任務(wù)調(diào)度問題的離散煙花算法。該算法包含編碼、任務(wù)調(diào)度算子、爆炸算子、變異算子和選擇策略幾部分。

2.2 編碼

本文的離散煙花算法采用整數(shù)編碼，一個(gè)煙花的位置定義為任務(wù)調(diào)度順序的序列X={x1,x2,x3,…,xNtotal}，其中xi是0～Ntotal中的一個(gè)整數(shù)，是任務(wù)的序號，其中Ntotal=Nt×Nu，是總?cè)蝿?wù)數(shù)量。例如，X={6,3,5,4,1,2}表示首先調(diào)度任務(wù)列表中的第6個(gè)任務(wù)，然后調(diào)度任務(wù)列表中的第3個(gè)任務(wù)，按順序依次調(diào)度。

2.3 任務(wù)調(diào)度算子

任務(wù)調(diào)度算子的功能是通過請求的任務(wù)序列X來獲得最終的任務(wù)調(diào)度結(jié)果。編碼生成調(diào)度序列，任務(wù)調(diào)度算子生成調(diào)度計(jì)劃。這個(gè)算子也是適應(yīng)度計(jì)算的基礎(chǔ)，根據(jù)任務(wù)調(diào)度結(jié)果來計(jì)算每一個(gè)煙花的適應(yīng)度。任務(wù)調(diào)度算子包含以下幾部分：用戶剩余存儲資源計(jì)算，任務(wù)安排，時(shí)間窗口更新。該算子的具體操作如圖2所示。該算子根據(jù)任務(wù)序列X依次調(diào)度每一個(gè)任務(wù)xi，對于每一個(gè)任務(wù)xi執(zhí)行下列操作：首先判斷該任務(wù)是否滿足用戶的存儲約束，若是不滿足，則判定任務(wù)調(diào)度失敗。若是滿足則遍歷時(shí)間窗口，找到一個(gè)最早可用的時(shí)間窗口，若是找到可用時(shí)間窗口，任務(wù)調(diào)度成功并更新中繼衛(wèi)星的時(shí)間窗口，若是未找到則判定任務(wù)失效。不斷重復(fù)上述步驟，知道所有任務(wù)都調(diào)度完成，得到最終調(diào)度方案。

圖2 任務(wù)調(diào)度算子流程Fig.2 Task scheduling operator flow chart

下面將具體介紹任務(wù)調(diào)度算子的各個(gè)部分。

(1)用戶剩余存儲資源計(jì)算

每個(gè)用戶在開始執(zhí)行每一個(gè)數(shù)據(jù)傳輸任務(wù)之前，會把產(chǎn)生的任務(wù)數(shù)據(jù)存放到用戶的存儲器上，然后等待傳輸，在數(shù)據(jù)產(chǎn)生到數(shù)據(jù)傳輸完成之前必須占用用戶的存儲資源，在傳輸完成后釋放存儲空間。所以在任務(wù)調(diào)度安排之前必須確保用戶有剩余的存儲空間來存儲這個(gè)任務(wù)的數(shù)據(jù)，這樣才能使數(shù)據(jù)順利地下傳到地面站。即任務(wù)調(diào)度必須滿足約束公式(4)。

所以在安排任務(wù)i的執(zhí)行時(shí)間窗口之前，應(yīng)該遍歷任務(wù)i所在用戶l產(chǎn)生的所有數(shù)傳任務(wù)。對該用戶上的每個(gè)任務(wù)j(i,j∈Tu，且i≠j)，都應(yīng)進(jìn)行如下操作：

1)判斷任務(wù)j開始時(shí)間是否在任務(wù)i開始之前，若是則繼續(xù)下面操作。

2)判斷任務(wù)j是否已經(jīng)調(diào)度完成，若未調(diào)度，則跳轉(zhuǎn)到步驟5)。若是調(diào)度完成則繼續(xù)下面操作。

3)判斷任務(wù)j是否調(diào)度失敗，若調(diào)度成功則繼續(xù)下面操作。

4)判斷任務(wù)j的調(diào)度完成時(shí)間是否在任務(wù)i開始之前，若不是則繼續(xù)下面操作。

5)從用戶剩余存儲中減去任務(wù)j的數(shù)據(jù)量大小。

最終輸出對于任務(wù)i的用戶剩余存儲容量。

(2)任務(wù)安排

這一步操作主要遵循約束公式(2)和約束公式(3)。本文按照任務(wù)序列X中任務(wù)的調(diào)度順序依次安排任務(wù)。對于每一個(gè)任務(wù)的時(shí)間安排，本文采取貪婪啟發(fā)式規(guī)則，把每個(gè)任務(wù)安排到最早可用時(shí)間窗口。這樣安排是為了更加充分地利用有限的中繼衛(wèi)星資源，使得任務(wù)安排更加的緊湊。

這里的可用窗口要滿足下列條件：1)時(shí)間窗口是指中繼衛(wèi)星的剩余可用時(shí)間窗與用戶和中繼衛(wèi)星的可見時(shí)間窗口的交集；2)而最早可用是指選擇一個(gè)能夠滿足任務(wù)傳輸?shù)淖钤绲臅r(shí)間窗口。

(3)時(shí)間窗口更新機(jī)制

由于地月中繼衛(wèi)星的一條鏈路在同一時(shí)刻只能服務(wù)于一個(gè)用戶，為了滿足約束公式(6)，本文采用了時(shí)間窗口資源刪除更新的機(jī)制。這里的時(shí)間窗口是中繼衛(wèi)星的剩余時(shí)間資源，在每次任務(wù)成功調(diào)度后，把該任務(wù)所占用的時(shí)間窗口從中繼衛(wèi)星的可用時(shí)間窗口中刪除。根據(jù)上述的任務(wù)安排方案，地月中繼衛(wèi)星時(shí)間窗的刪除只可能是下列3種情形，具體的操作情況如圖3所示。

圖3 地月中繼衛(wèi)星可用時(shí)間窗口刪除方法Fig.3 Method for deleting available time window

2.4 爆炸算子

對于煙花X首先按照式(7)計(jì)算出火花的個(gè)數(shù)L。

(7)

式中：L為煙花產(chǎn)生的爆炸火花個(gè)數(shù)；m為一個(gè)常量代表，表示所有煙花產(chǎn)生的爆炸火花的總數(shù)；Ymax為N個(gè)煙花中適應(yīng)度最差的值；f(X)為煙花適應(yīng)度；ε為一個(gè)極小的常數(shù)，在式中的作用是防止分母為零。

為了防止產(chǎn)生的爆炸火花過多或者過少，通過如下公式來對控制每個(gè)煙花爆炸火花的數(shù)量：

(8)

式中：a,b為0～1之間的常數(shù)，且a

再通過式(7)(8)計(jì)算出煙花X的火花個(gè)數(shù)L，然后按照下面的步驟得到L個(gè)火花:

1)隨機(jī)選取序列X中的兩個(gè)節(jié)點(diǎn)，然后反轉(zhuǎn)這兩個(gè)節(jié)點(diǎn)及其中間部分的序列，得到新的調(diào)度序列X′，圖4所示為該爆炸算子的操作方法(以編號1～10的10個(gè)任務(wù)為例)。

圖4 爆炸算子操作示意Fig.4 Explosion operator operation

2)計(jì)算得到的新的調(diào)度序列X′的適應(yīng)度f(X′)，把新序列的適應(yīng)度與原序列的適應(yīng)度f(X)進(jìn)行比較，若f(X′)

2.5 變異算子

對于煙花X,隨機(jī)選取其中的兩位，然后進(jìn)行位置交換，若交換后的適應(yīng)度f(X′)

2.6 選擇策略

從煙花、爆炸火花、變異火花一起組成候選集，選出N個(gè)煙花組成下一代的煙花種群。選擇策略基于兩個(gè)準(zhǔn)則：1)采用精英保留策略保留最優(yōu)煙花的個(gè)體；2)采用輪盤賭的方法選擇剩余的N-1個(gè)煙花，煙花Xj被選擇的概率為：

(9)

式中：fmax為候選集中適應(yīng)度最差的值；f(Xj)為煙花Xj的適應(yīng)度。從式(9)可以看出，適應(yīng)度越好的煙花，越有可能進(jìn)入下一代中。

2.7 算法的總體思路

基于離散煙花算法的地月中繼衛(wèi)星任務(wù)調(diào)度的算法的總體思路如圖5所示，這個(gè)算法的主要步驟如下：

1)在初始化階段，輸入任務(wù)信息，用戶信息，中繼衛(wèi)星的可用資源信息等，確定種群規(guī)模N、爆炸火花個(gè)數(shù)Ne、變異火花個(gè)數(shù)Nm、控制劣解接受的參數(shù)θ、最大迭代次數(shù)Cmax，隨機(jī)初始化N個(gè)煙花種群，并利用任務(wù)調(diào)度算子計(jì)算每個(gè)煙花的適應(yīng)度。

2)判斷迭代是否終止，若是沒達(dá)到終止條件則進(jìn)入搜索階段。

3)通過爆炸算子和變異算子產(chǎn)生火花，計(jì)算所有火花的適應(yīng)度，并和煙花一起放入選擇算子中，選擇進(jìn)入下一代的個(gè)體。

4)重復(fù)步驟2)和3)，直到最大迭代次數(shù)Cmax，最后輸出最終的結(jié)果。

圖5 基于離散煙花算法的地月中繼衛(wèi)星任務(wù)調(diào)度算法流程Fig.5 Lunar relay satellite task scheduling algorithm based on discrete fireworks algorithm

3 仿真結(jié)果及分析

3.1 仿真場景

本文試驗(yàn)參考鵲橋號中繼衛(wèi)星為月球背面的嫦娥四號與玉兔二號探測器提供中繼服務(wù)的場景。仿真時(shí)間為一天00:00:00-23:59:59，一顆地月中繼衛(wèi)星采用地月拉格朗日L2點(diǎn)的Halo軌道參數(shù)，這個(gè)中繼衛(wèi)星有3個(gè)信道用于數(shù)傳任務(wù)。6個(gè)數(shù)傳任務(wù)用戶其中2個(gè)是環(huán)月衛(wèi)星，其軌道參數(shù)如表1所示，另外4個(gè)用戶是月球背面探測器。用戶與地球中繼衛(wèi)星的可見時(shí)間窗口由STK導(dǎo)出。本文在MatlabR2016b平臺上進(jìn)行仿真試驗(yàn)。

表1 環(huán)月衛(wèi)星的軌道參數(shù)

在仿真試驗(yàn)時(shí)，首先對60個(gè)實(shí)時(shí)任務(wù)進(jìn)行調(diào)度，然后獲得地月中繼衛(wèi)星的剩余可用時(shí)間窗。再利用離散煙花算法對數(shù)傳任務(wù)進(jìn)行調(diào)度。

仿真中各參數(shù)設(shè)定如下：數(shù)傳任務(wù)的開始時(shí)間在一天內(nèi)隨機(jī)分布，數(shù)傳任務(wù)的結(jié)束時(shí)間沒有進(jìn)行設(shè)置，只要在數(shù)據(jù)丟失之前回傳即可；數(shù)傳任務(wù)的數(shù)據(jù)量是100～400 Gbit之間的隨機(jī)值；每條鏈路的傳輸速率為100 Mbit/s；任務(wù)的傳輸時(shí)間由任務(wù)的數(shù)據(jù)量和信道的傳輸速率所決定；6個(gè)用戶的剩余存儲空間在200～800 Gbit之間隨機(jī)選擇。

3.2 仿真結(jié)果

為了驗(yàn)證算法的性能，分別采用本文的算法(DFWA)和遺傳算法(Genetic Algorithm，GA)進(jìn)行仿真驗(yàn)證。遺傳算法的種群數(shù)量為20，遺傳概率為0.8，變異概率為0.1，迭代次數(shù)為100次。煙花算法的參數(shù)設(shè)置如表2所示。

表2 參數(shù)設(shè)置

在任務(wù)數(shù)量為42時(shí)，兩種算法的調(diào)度結(jié)果甘特圖如圖6所示。其中彩色部分是數(shù)傳任務(wù)，空白的矩形塊是中繼衛(wèi)星在進(jìn)行數(shù)傳任務(wù)調(diào)度時(shí)已經(jīng)被占用的資源。在這種情況下，基于DFWA的算法的任務(wù)安排數(shù)量為39，數(shù)據(jù)丟失量為609 Gbit。而遺傳算法的任務(wù)完成數(shù)量為35，數(shù)據(jù)丟失量為1683 Gbit?？梢钥闯?，基于DFWA的算法在求解結(jié)果上要優(yōu)于遺傳算法。圖7是兩個(gè)算法在任務(wù)數(shù)量為42的一次試驗(yàn)的搜索過程，從圖中可以看出，基于DFWA的算法的在搜索最優(yōu)解方面有更好的特性。

圖6 任務(wù)數(shù)量為42時(shí)的算法調(diào)度結(jié)果示意Fig.6 Algorithm scheduling results when the task number is 42

圖7 任務(wù)數(shù)量為42時(shí)智能算法的搜索過程Fig.7 The search process of intelligent algorithm when the task number is 42

兩個(gè)算法的運(yùn)行時(shí)間上，基于離散煙花算法的運(yùn)行時(shí)間要比遺傳算法時(shí)間長0.25倍。遺傳算法的時(shí)間復(fù)雜度是O[Cmax×(N+Nc+Nm)×K]，其中Cmax是迭代次數(shù)，N是種群數(shù)量，Nc是交叉產(chǎn)生的種群數(shù)量，Nm是變異的種群數(shù)量，K是適應(yīng)度計(jì)算的時(shí)間復(fù)雜度。煙花算法的時(shí)間復(fù)雜度是O[Cmax×(N×L+Nm)×K]。其中Cmax是迭代次數(shù)，N是種群數(shù)量，L爆炸火花個(gè)數(shù)，Nm是變異的種群數(shù)量，K是適應(yīng)度計(jì)算的時(shí)間復(fù)雜度。這兩個(gè)時(shí)間復(fù)雜度的區(qū)別主要在于子代的數(shù)量。遺傳算法的子代依賴于遺傳和變異的概率，相對于煙花算法來說產(chǎn)生的子代數(shù)量較少，所以遺傳算法的復(fù)雜度相對要低一些。但是煙花算法由于其爆炸和變異的特性，在搜索最優(yōu)解的時(shí)候不容易陷入局部最優(yōu)，所以其求解效果要更好一些，能求得更好的解。所以可以說，基于煙花算法的地月中繼衛(wèi)星任務(wù)調(diào)度的算法是犧牲了部分的運(yùn)行時(shí)間來得到一個(gè)更好的解。由于本文考慮的是靜態(tài)任務(wù)調(diào)度，即業(yè)務(wù)提前一定時(shí)間到達(dá)。根據(jù)NASA 發(fā)布的中繼衛(wèi)星系統(tǒng)用戶使用手冊：中繼系統(tǒng)以一周為周期，對業(yè)務(wù)進(jìn)行資源分配。所以對于靜態(tài)業(yè)務(wù)調(diào)度問題來說，算法的運(yùn)行時(shí)間長短影響并不是很大。

為了進(jìn)一步驗(yàn)證算法的有效性，本文還比較了任務(wù)規(guī)模數(shù)量為30、60、90、120、150的情況。在這些任務(wù)規(guī)模數(shù)量下，分別采用遺傳算法和基于離散煙花算法的地月中繼衛(wèi)星任務(wù)調(diào)度算法進(jìn)行仿真計(jì)算，把算法運(yùn)行20次，最終結(jié)果取平均值。為防止任務(wù)屬性的不同對算法造成影響，試驗(yàn)時(shí)每次任務(wù)都是隨機(jī)產(chǎn)生的。兩個(gè)算法的運(yùn)算結(jié)果如圖8所示。由圖8可知，雖然在任務(wù)數(shù)量比較少的時(shí)候兩個(gè)算法求得的解沒有很大差別，這是由于任務(wù)數(shù)量較少，資源比較充足的原因。但是當(dāng)任務(wù)數(shù)量比較多的時(shí)候，基于DFWA的算法求解能力總是優(yōu)于遺傳算法。

圖8 不同任務(wù)規(guī)模下的算法對比Fig.8 Comparison of algorithms under different task sizes

4 結(jié)束語

本文首次根據(jù)地月中繼衛(wèi)星任務(wù)調(diào)度問題的特點(diǎn)，綜合考慮了中繼衛(wèi)星資源約束，任務(wù)屬性約束和用戶的存儲約束，以最小化數(shù)據(jù)丟失量為目標(biāo)，建立了地月中繼衛(wèi)星任務(wù)調(diào)度的約束滿足模型，并基于該模型提出了一種基于離散煙花算法的地月中繼衛(wèi)星任務(wù)調(diào)度算法。根據(jù)仿真結(jié)果可知，相比于遺傳算法，該算法能有效減少數(shù)據(jù)的丟失。日后隨著探月的不斷發(fā)展，任務(wù)類型也將趨向于多元化，任務(wù)的動態(tài)性也將會增加，而且地月中繼衛(wèi)星也將可能會形成一個(gè)衛(wèi)星網(wǎng)絡(luò)，這將是未來研究的重點(diǎn)。另外，本篇文章為了簡化問題做了較多假設(shè)，對于地月中繼衛(wèi)星資源調(diào)度模型還有很多不足，未來可以根據(jù)實(shí)際的情況對模型和仿真參數(shù)進(jìn)行更具體的細(xì)化和研究。