1. 上海交通大學(xué) 區(qū)域光纖通信網(wǎng)與新型光通信系統(tǒng)國家重點(diǎn)實(shí)驗(yàn)室,上海 200240 2. 上海衛(wèi)星工程研究所,上海 200240
全球新一輪的月球探索正在拉開序幕,探月范圍正在逐步由月球正面向背面和兩極拓展,探月活動(dòng)也日趨復(fù)雜[1-4]。由于月球的自轉(zhuǎn)周期和公轉(zhuǎn)周期相同,地球地面站無法與月球背面直接通信,而借助地月中繼衛(wèi)星的中繼通信方式可以解決這個(gè)問題,并滿足面向月球的全時(shí)域、全空域覆蓋的通信要求[3]。
地月中繼衛(wèi)星是指為月球表面的探測(cè)器、著陸器、環(huán)月衛(wèi)星等提供數(shù)據(jù)中繼和測(cè)控服務(wù)的通信衛(wèi)星。地月中繼衛(wèi)星任務(wù)調(diào)度是指地面任務(wù)管理中心根據(jù)用戶提出的服務(wù)申請(qǐng),合理地分配地月中繼衛(wèi)星資源及執(zhí)行時(shí)間,以盡可能地滿足用戶服務(wù)需求,提高地月中繼衛(wèi)星資源的利用率。隨著人類對(duì)月球的探測(cè)不斷深入[5],未來十幾年各國發(fā)射的月面探測(cè)器也將不斷增多。地月中繼衛(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)先級(jí),建立了混合整數(shù)規(guī)劃模型,以最大化任務(wù)完成數(shù)量為目標(biāo),采用貪婪隨機(jī)搜索算法對(duì)其求解。文獻(xiàn)[11]考慮到了數(shù)據(jù)中繼衛(wèi)星激光和微波混合鏈路系統(tǒng)的資源和任務(wù)的約束,建立了混合鏈路資源調(diào)度模型,以最大化完成任務(wù)優(yōu)先級(jí)之和為目標(biāo),提出了一種基于改進(jìn)的遺傳算法。文獻(xiàn)[12]提出了中繼衛(wèi)星日常任務(wù)的調(diào)度模型,也是以最大化完成任務(wù)優(yōu)先級(jí)之和為目標(biāo),采用人工蜂群算法求解。文獻(xiàn)[13]針對(duì)中繼衛(wèi)星任務(wù)的動(dòng)態(tài)性,以最大化完成任務(wù)優(yōu)先級(jí)之和以及最小化任務(wù)重調(diào)度數(shù)量為目標(biāo)提出了一種兩階段任務(wù)調(diào)度算法。
上述基于近地中繼衛(wèi)星的任務(wù)調(diào)度研究通常都是以最大化完成任務(wù)數(shù)量和最大完成任務(wù)優(yōu)先級(jí)之和作為其優(yōu)化目標(biāo),一般考慮任務(wù)的優(yōu)先級(jí)、用戶衛(wèi)星與中繼衛(wèi)星的可見時(shí)間窗口約束以及衛(wèi)星天線資源的約束。這些研究對(duì)于數(shù)傳任務(wù)很少考慮用戶的存儲(chǔ)限制,數(shù)傳任務(wù)在規(guī)定截止時(shí)間內(nèi)傳輸完成,一般就認(rèn)為任務(wù)完成。但是在現(xiàn)實(shí)情況下,用戶由于與地月中繼衛(wèi)星不可見或者中繼衛(wèi)星資源被占用等原因,產(chǎn)生的數(shù)據(jù)不能馬上進(jìn)行傳輸,需要放入存儲(chǔ)器中等待一定時(shí)間。在等待與中繼衛(wèi)星進(jìn)行數(shù)據(jù)傳輸?shù)臅r(shí)間內(nèi),用戶也將不斷產(chǎn)生數(shù)據(jù),新產(chǎn)生的數(shù)據(jù)也將會(huì)放入存儲(chǔ)器中,等待傳輸。那么如果用戶的剩余存儲(chǔ)容量不足以支撐用戶的下一次任務(wù)所需存儲(chǔ)容量,那么下一次任務(wù)數(shù)據(jù)將丟失(或者新產(chǎn)生的數(shù)據(jù)覆蓋原來的舊數(shù)據(jù),還未傳輸?shù)呐f數(shù)據(jù)丟失)。而在月球探測(cè)過程中的數(shù)據(jù)和圖像是非常珍貴的,在完成任務(wù)收集到數(shù)據(jù)時(shí),期望這些數(shù)據(jù)能盡可能多的傳輸?shù)降孛?,盡可能減少數(shù)據(jù)的丟失量。
地月中繼衛(wèi)星的任務(wù)包括實(shí)時(shí)性任務(wù)(如遙控遙測(cè)類任務(wù))和延遲容忍類任務(wù)(如數(shù)傳類任務(wù))。本文針對(duì)地月中繼衛(wèi)星的延遲容忍類任務(wù),即數(shù)傳任務(wù)展開研究,研究目標(biāo)是盡可能使數(shù)傳任務(wù)的數(shù)據(jù)丟失量最小,從而提高地月中繼衛(wèi)星資源的利用率。
地月中繼系統(tǒng)如圖1所示,地月中繼系統(tǒng)由地月中繼衛(wèi)星、用戶和地面站3部分組成。未來地月中繼衛(wèi)星將有以下幾類用戶:環(huán)月衛(wèi)星、月球探測(cè)車、著陸器、月表?xiàng)⒌亍⒂詈絾T等。未來地月中繼衛(wèi)星系統(tǒng)中傳輸?shù)娜蝿?wù)將包括遙控、遙測(cè)、數(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ù)將會(huì)不斷增多,任務(wù)將會(huì)隨之增多。但是地月中繼衛(wèi)星在同一時(shí)間能服務(wù)的用戶數(shù)量是有限的,并不能滿足所有用戶的要求。所以本文的目的是在滿足地月中繼衛(wèi)星任務(wù)調(diào)度約束的前提下,找到一種合適地月中繼衛(wèi)星資源調(diào)度策略,使得數(shù)傳任務(wù)的數(shù)據(jù)丟失量最小。
為了簡(jiǎn)化研究問題,假設(shè):
1)由于實(shí)時(shí)性任務(wù)的優(yōu)先級(jí)相對(duì)于數(shù)傳任務(wù)的優(yōu)先級(jí)較高,所以在本文中對(duì)于數(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í)較長(zhǎng)的搜索算法來尋求優(yōu)化解。數(shù)傳任務(wù)的結(jié)束時(shí)間是仿真結(jié)束時(shí)間,任務(wù)在仿真結(jié)束時(shí)間之前回傳即可,存儲(chǔ)溢出就算任務(wù)調(diào)度失敗。
3)不考慮數(shù)據(jù)采集階段的消耗時(shí)間。假設(shè)數(shù)據(jù)在數(shù)傳任務(wù)開始時(shí)存儲(chǔ)到用戶中。數(shù)傳任務(wù)執(zhí)行結(jié)束后,會(huì)釋放數(shù)傳任務(wù)的存儲(chǔ)空間。
4)不考慮中繼衛(wèi)星從一個(gè)用戶切換到另一個(gè)用戶所需要的時(shí)間。
地月中繼衛(wèi)星任務(wù)調(diào)度的約束包括以下幾點(diǎn)。
(1)地月中繼衛(wèi)星用戶屬性約束
地月中繼衛(wèi)星用戶屬性約束包括可見時(shí)間窗約束和用戶存儲(chǔ)約束。
可見時(shí)間窗約束:用戶與地月中繼衛(wèi)星并非時(shí)時(shí)可見,只有當(dāng)他們位于彼此可見的范圍內(nèi),才能建立通信鏈路,所以任務(wù)的執(zhí)行時(shí)間必須在中繼衛(wèi)星與用戶的可見時(shí)間窗口內(nèi)。
用戶存儲(chǔ)約束:針對(duì)于數(shù)傳任務(wù)來說,用戶的剩余存儲(chǔ)容量必須大于任務(wù)所需存儲(chǔ)量,任務(wù)才能正常執(zhí)行,否則直接判定任務(wù)調(diào)度失敗。用戶的剩余存儲(chǔ)容量對(duì)于每一個(gè)任務(wù)來說可能都是不一樣的,需要根據(jù)這個(gè)任務(wù)之前開始的任務(wù)的調(diào)度狀態(tài)來確定。
(2)任務(wù)屬性約束
用戶提交任務(wù)申請(qǐng)時(shí),會(huì)提交任務(wù)的優(yōu)先級(jí)、任務(wù)的持續(xù)時(shí)間、任務(wù)最早開始時(shí)間以及任務(wù)最晚結(jié)束時(shí)間。對(duì)于數(shù)據(jù)傳輸類任務(wù)除了上述要求外,還需要知道任務(wù)的數(shù)據(jù)量大小,及用戶的剩余存儲(chǔ)量。
進(jìn)行任務(wù)調(diào)度時(shí)必須考慮以下內(nèi)容:1)任務(wù)的執(zhí)行時(shí)間必須在任務(wù)的有效時(shí)間內(nèi);2)任務(wù)一次傳輸完成,不考慮任務(wù)拆分;3)對(duì)于新產(chǎn)生的數(shù)據(jù)傳輸類任務(wù)要考慮用戶剩余存儲(chǔ)容量是否超出任務(wù)的數(shù)據(jù)量。若任務(wù)的數(shù)據(jù)量超出用戶的剩余存儲(chǔ)容量,則該任務(wù)數(shù)據(jù)被丟棄。
(3)中繼衛(wèi)星資源約束
地月中繼衛(wèi)星資源在本文中指地月中繼衛(wèi)星數(shù)目以及一顆地月中繼衛(wèi)星在同一時(shí)刻能連接的用戶數(shù)量。
數(shù)學(xué)模型中出現(xiàn)的相關(guān)符號(hào)說明如下。
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í)的剩余存儲(chǔ)容量。
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í)間。
基于上述的問題描述與分析,地月中繼衛(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之前,必須確保用戶的剩余存儲(chǔ)容量大于任務(wù)i的數(shù)據(jù)量,否則任務(wù)i無法執(zhí)行,這里的用戶剩余存儲(chǔ)容量是隨著任務(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í)間求解。而通常求解這類問題會(huì)采用啟發(fā)式算法和智能搜索算法。由于在本文中討論的是靜態(tài)業(yè)務(wù)調(diào)度,對(duì)于計(jì)算時(shí)間要求相對(duì)較小,所以為了得到更好的調(diào)度方案,采用智能搜索算法。
而煙花算法是一種新型的智能搜索算法,目前在很多領(lǐng)域取得比較好的應(yīng)用。煙花算法通過爆炸的操作實(shí)現(xiàn)了局部搜索和全局搜索的平衡,相比于遺傳算法,不容易陷入局部最優(yōu)解,能找到更好的解。所以本文采用了基于離散煙花算法進(jìn)行地月中繼衛(wèi)星任務(wù)調(diào)度的算法設(shè)計(jì)。
煙花算法(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)度問題中。針對(duì)求解地月中繼衛(wèi)星任務(wù)調(diào)度問題,本文設(shè)計(jì)了一種求解地月中繼衛(wèi)星任務(wù)調(diào)度問題的離散煙花算法。該算法包含編碼、任務(wù)調(diào)度算子、爆炸算子、變異算子和選擇策略幾部分。
本文的離散煙花算法采用整數(shù)編碼,一個(gè)煙花的位置定義為任務(wù)調(diào)度順序的序列X={x1,x2,x3,…,xNtotal},其中xi是0~Ntotal中的一個(gè)整數(shù),是任務(wù)的序號(hào),其中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)度。
任務(wù)調(diào)度算子的功能是通過請(qǐng)求的任務(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)度算子包含以下幾部分:用戶剩余存儲(chǔ)資源計(jì)算,任務(wù)安排,時(shí)間窗口更新。該算子的具體操作如圖2所示。該算子根據(jù)任務(wù)序列X依次調(diào)度每一個(gè)任務(wù)xi,對(duì)于每一個(gè)任務(wù)xi執(zhí)行下列操作:首先判斷該任務(wù)是否滿足用戶的存儲(chǔ)約束,若是不滿足,則判定任務(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)用戶剩余存儲(chǔ)資源計(jì)算
每個(gè)用戶在開始執(zhí)行每一個(gè)數(shù)據(jù)傳輸任務(wù)之前,會(huì)把產(chǎn)生的任務(wù)數(shù)據(jù)存放到用戶的存儲(chǔ)器上,然后等待傳輸,在數(shù)據(jù)產(chǎn)生到數(shù)據(jù)傳輸完成之前必須占用用戶的存儲(chǔ)資源,在傳輸完成后釋放存儲(chǔ)空間。所以在任務(wù)調(diào)度安排之前必須確保用戶有剩余的存儲(chǔ)空間來存儲(chǔ)這個(gè)任務(wù)的數(shù)據(jù),這樣才能使數(shù)據(jù)順利地下傳到地面站。即任務(wù)調(diào)度必須滿足約束公式(4)。
所以在安排任務(wù)i的執(zhí)行時(shí)間窗口之前,應(yīng)該遍歷任務(wù)i所在用戶l產(chǎn)生的所有數(shù)傳任務(wù)。對(duì)該用戶上的每個(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)從用戶剩余存儲(chǔ)中減去任務(wù)j的數(shù)據(jù)量大小。
最終輸出對(duì)于任務(wù)i的用戶剩余存儲(chǔ)容量。
(2)任務(wù)安排
這一步操作主要遵循約束公式(2)和約束公式(3)。本文按照任務(wù)序列X中任務(wù)的調(diào)度順序依次安排任務(wù)。對(duì)于每一個(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
對(duì)于煙花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)生的爆炸火花過多或者過少,通過如下公式來對(duì)控制每個(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所示為該爆炸算子的操作方法(以編號(hào)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′)
對(duì)于煙花X,隨機(jī)選取其中的兩位,然后進(jìn)行位置交換,若交換后的適應(yīng)度f(X′)
從煙花、爆炸火花、變異火花一起組成候選集,選出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)入下一代中。
基于離散煙花算法的地月中繼衛(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
本文試驗(yàn)參考鵲橋號(hào)中繼衛(wèi)星為月球背面的嫦娥四號(hào)與玉兔二號(hào)探測(cè)器提供中繼服務(wù)的場(chǎng)景。仿真時(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è)用戶是月球背面探測(cè)器。用戶與地球中繼衛(wèi)星的可見時(shí)間窗口由STK導(dǎo)出。本文在MatlabR2016b平臺(tái)上進(jìn)行仿真試驗(yàn)。
表1 環(huán)月衛(wèi)星的軌道參數(shù)
在仿真試驗(yàn)時(shí),首先對(duì)60個(gè)實(shí)時(shí)任務(wù)進(jìn)行調(diào)度,然后獲得地月中繼衛(wèi)星的剩余可用時(shí)間窗。再利用離散煙花算法對(duì)數(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è)用戶的剩余存儲(chǔ)空間在200~800 Gbit之間隨機(jī)選擇。
為了驗(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í)間長(zhǎng)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ù)量。遺傳算法的子代依賴于遺傳和變異的概率,相對(duì)于煙花算法來說產(chǎn)生的子代數(shù)量較少,所以遺傳算法的復(fù)雜度相對(duì)要低一些。但是煙花算法由于其爆炸和變異的特性,在搜索最優(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)用戶使用手冊(cè):中繼系統(tǒng)以一周為周期,對(duì)業(yè)務(wù)進(jìn)行資源分配。所以對(duì)于靜態(tài)業(yè)務(wù)調(diào)度問題來說,算法的運(yùn)行時(shí)間長(zhǎng)短影響并不是很大。
為了進(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ù)屬性的不同對(duì)算法造成影響,試驗(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ī)模下的算法對(duì)比Fig.8 Comparison of algorithms under different task sizes
本文首次根據(jù)地月中繼衛(wèi)星任務(wù)調(diào)度問題的特點(diǎn),綜合考慮了中繼衛(wèi)星資源約束,任務(wù)屬性約束和用戶的存儲(chǔ)約束,以最小化數(shù)據(jù)丟失量為目標(biāo),建立了地月中繼衛(wèi)星任務(wù)調(diào)度的約束滿足模型,并基于該模型提出了一種基于離散煙花算法的地月中繼衛(wèi)星任務(wù)調(diào)度算法。根據(jù)仿真結(jié)果可知,相比于遺傳算法,該算法能有效減少數(shù)據(jù)的丟失。日后隨著探月的不斷發(fā)展,任務(wù)類型也將趨向于多元化,任務(wù)的動(dòng)態(tài)性也將會(huì)增加,而且地月中繼衛(wèi)星也將可能會(huì)形成一個(gè)衛(wèi)星網(wǎng)絡(luò),這將是未來研究的重點(diǎn)。另外,本篇文章為了簡(jiǎn)化問題做了較多假設(shè),對(duì)于地月中繼衛(wèi)星資源調(diào)度模型還有很多不足,未來可以根據(jù)實(shí)際的情況對(duì)模型和仿真參數(shù)進(jìn)行更具體的細(xì)化和研究。