基于人工蜂群算法的中繼衛(wèi)星任務(wù)調(diào)度研究

開彩紅 肖 瑤 方 青

?

基于人工蜂群算法的中繼衛(wèi)星任務(wù)調(diào)度研究

開彩紅*①肖 瑤①方 青②

①(合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院 合肥 230009)②(中國(guó)電子科技集團(tuán)公司第三十八研究所 合肥 230031)

研究中繼衛(wèi)星任務(wù)調(diào)度問(wèn)題可以為跟蹤與數(shù)據(jù)中繼衛(wèi)星系統(tǒng)(TDRSS)的任務(wù)計(jì)劃編排提供科學(xué)合理的決策方法，任務(wù)調(diào)度模型的建立與調(diào)度算法的設(shè)計(jì)是中繼衛(wèi)星任務(wù)調(diào)度的兩個(gè)關(guān)鍵問(wèn)題。該文針對(duì)中繼衛(wèi)星任務(wù)調(diào)度問(wèn)題特點(diǎn)，綜合考慮中繼衛(wèi)星與用戶航天器之間具有可見時(shí)間窗、用戶提交的任務(wù)屬性、中繼衛(wèi)星前向資源受限等約束條件，建立了中繼衛(wèi)星任務(wù)調(diào)度約束規(guī)劃模型并提出基于人工蜂群(ABC)算法的中繼衛(wèi)星任務(wù)調(diào)度算法。最后，通過(guò)仿真數(shù)據(jù)分析，表明基于人工蜂群算法的中繼衛(wèi)星任務(wù)調(diào)度算法是一種有效的、合理的調(diào)度方法。

中繼衛(wèi)星任務(wù)調(diào)度；可見時(shí)間窗；任務(wù)屬性；約束規(guī)劃模型；人工蜂群算法

1 引言

跟蹤與數(shù)據(jù)中繼衛(wèi)星系統(tǒng)(Tracking and Data Relay Satellite System, TDRSS)是指通過(guò)位于地球同步軌道的中繼衛(wèi)星，為中、低軌道的航天器與航天器之間、航天器與地面站之間提供數(shù)據(jù)中繼、連續(xù)跟蹤與軌道測(cè)控服務(wù)的系統(tǒng)。中繼衛(wèi)星任務(wù)調(diào)度是指系統(tǒng)管理中心根據(jù)用戶提出的服務(wù)申請(qǐng)，合理地分配中繼衛(wèi)星系統(tǒng)資源，并在資源沖突時(shí)進(jìn)行優(yōu)化調(diào)度，以完成盡可能多的任務(wù)。隨著航空航天領(lǐng)域中對(duì)地觀測(cè)、軍事偵察以及深空探測(cè)等技術(shù)的不斷發(fā)展，中繼衛(wèi)星數(shù)據(jù)傳輸呈現(xiàn)大容量、高速率以及多樣化中繼任務(wù)的特點(diǎn)，TDRSS資源優(yōu)化調(diào)度問(wèn)題愈凸顯得非常重要。

中繼衛(wèi)星任務(wù)調(diào)度問(wèn)題是一個(gè)多約束的組合優(yōu)化問(wèn)題，需要考慮衛(wèi)星間可見時(shí)間窗口、任務(wù)屬性、衛(wèi)星資源等方面的約束。中繼衛(wèi)星任務(wù)調(diào)度的目標(biāo)是在滿足可見時(shí)間窗口約束、任務(wù)屬性約束、衛(wèi)星資源有限的前提下，通過(guò)合理的安排任務(wù)執(zhí)行順序，以使得盡可能多的任務(wù)可以被成功執(zhí)行，從而提高中繼衛(wèi)星通信資源的使用效率。近年來(lái)，出現(xiàn)了不少針對(duì)中繼衛(wèi)星任務(wù)調(diào)度模型和調(diào)度算法的研究。文獻(xiàn)[3]是針對(duì)美國(guó)的中繼衛(wèi)星系統(tǒng)，采用并行機(jī)調(diào)度算法對(duì)中繼衛(wèi)星調(diào)度問(wèn)題進(jìn)行研究，其數(shù)學(xué)模型僅考慮中繼衛(wèi)星與用戶航天器之間存在不多于兩個(gè)可見時(shí)間窗口的情況。文獻(xiàn)[4]是通過(guò)建立滿足中繼衛(wèi)星約束問(wèn)題(CSP)的模型，并對(duì)該模型進(jìn)行求解得到調(diào)度方案。文獻(xiàn)[5]提出一種基于任務(wù)時(shí)間靈活度的調(diào)度算法，其主要的思想是動(dòng)態(tài)地調(diào)節(jié)已調(diào)度任務(wù)在時(shí)間窗口的位置，從而實(shí)現(xiàn)更多任務(wù)的調(diào)度。文獻(xiàn)[6]是基于有效基因路徑表示的改進(jìn)遺傳算法，通過(guò)定義合適的交叉與變異算子，來(lái)求解最優(yōu)的調(diào)度方案。文獻(xiàn)[7]是針對(duì)微波與激光混合鏈路中繼衛(wèi)星動(dòng)態(tài)調(diào)度問(wèn)題，采用啟發(fā)式算法來(lái)求解最優(yōu)調(diào)度方案。

研究中繼衛(wèi)星任務(wù)調(diào)度問(wèn)題的關(guān)鍵在于建立有效的調(diào)度約束模型進(jìn)而設(shè)計(jì)調(diào)度算法，從而能夠在短時(shí)間內(nèi)形成一種較優(yōu)的任務(wù)編排方案，以滿足工程應(yīng)用需求。本文首先針對(duì)中繼衛(wèi)星與用戶航天器之間可見時(shí)間窗約束、用戶提交的任務(wù)屬性和中繼衛(wèi)星資源的約束，建立了任務(wù)調(diào)度約束規(guī)劃模型。通過(guò)合理地設(shè)計(jì)目標(biāo)函數(shù)，使得規(guī)劃模型以盡可能成功調(diào)度更多任務(wù)，并優(yōu)先調(diào)度優(yōu)先級(jí)高的任務(wù)為目標(biāo)。基于所建立的中繼衛(wèi)星任務(wù)調(diào)度規(guī)劃模型，本文提出了一種基于人工蜂群(Artificial Bees Colony, ABC)算法的中繼衛(wèi)星任務(wù)編排算法。通過(guò)在算法的迭代過(guò)程中對(duì)每個(gè)可行調(diào)度方案進(jìn)行評(píng)估、鄰域操作尋找局部最優(yōu)調(diào)度方案，從而獲得全局最優(yōu)調(diào)度方案。最后通過(guò)仿真實(shí)驗(yàn)分析，表明所提算法在調(diào)度效率方面具有優(yōu)勢(shì)，能夠有效地提高中繼衛(wèi)星的使用效率，且算法本身具有低復(fù)雜度的特點(diǎn)，因而適用于工程實(shí)踐。

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

2.1 中繼衛(wèi)星任務(wù)調(diào)度問(wèn)題描述

中繼衛(wèi)星任務(wù)調(diào)度是指在滿足任務(wù)調(diào)度約束的前提下，在相對(duì)較短時(shí)間內(nèi)得到一種最優(yōu)的調(diào)度方案。中繼衛(wèi)星任務(wù)調(diào)度的約束包括以下幾點(diǎn)：(1)中繼衛(wèi)星與用戶航天器之間具有可見時(shí)間窗約束。中繼衛(wèi)星與用戶航天器并非時(shí)時(shí)可見，只有當(dāng)它們位于彼此的可見范圍內(nèi)，才能建立通信鏈路，即任務(wù)的執(zhí)行時(shí)間必須在中繼衛(wèi)星與用戶航天器之間的可見時(shí)間窗內(nèi)。如圖1所示，表示可見時(shí)間窗的開始時(shí)刻，表示可見時(shí)間窗的結(jié)束時(shí)刻，表示任務(wù)執(zhí)行的持續(xù)時(shí)間(不包括服務(wù)準(zhǔn)備和終止所需要的時(shí)間)。(2)任務(wù)屬性約束。用戶提交任務(wù)申請(qǐng)時(shí)，會(huì)提交任務(wù)的優(yōu)先級(jí)、任務(wù)的持續(xù)時(shí)間、任務(wù)最早開始執(zhí)行時(shí)間及任務(wù)最晚結(jié)束時(shí)間。進(jìn)行任務(wù)調(diào)度時(shí)須考慮：執(zhí)行任務(wù)的開始時(shí)間不小于任務(wù)最早開始時(shí)間；執(zhí)行任務(wù)的結(jié)束時(shí)間不大于任務(wù)的最晚結(jié)束時(shí)間；當(dāng)某個(gè)可見時(shí)間窗的時(shí)間長(zhǎng)度小于任務(wù)的持續(xù)時(shí)間，由于本文所討論的任務(wù)持續(xù)時(shí)間不允許拆分成多個(gè)子時(shí)間段，所以進(jìn)行任務(wù)調(diào)度時(shí)必須選擇其他時(shí)間長(zhǎng)度比此任務(wù)持續(xù)時(shí)間長(zhǎng)的可見時(shí)間窗(如圖2所示，表示第個(gè)可見時(shí)間窗)。(3)對(duì)于中繼衛(wèi)星與用戶航天器之間的某一條鏈路而言，同一時(shí)間最多只能有一個(gè)任務(wù)由該鏈路完成數(shù)據(jù)傳輸；與此同時(shí)考慮到衛(wèi)星單址鏈路沖突的情況，在同一時(shí)刻任一顆用戶航天器上最多只能有一條鏈路進(jìn)行數(shù)據(jù)傳輸。

圖1 中繼衛(wèi)星與用戶航天器之間的可見時(shí)間窗

圖2 可見時(shí)間窗長(zhǎng)度小于任務(wù)持續(xù)時(shí)間

2.2中繼衛(wèi)星任務(wù)調(diào)度問(wèn)題的約束規(guī)劃模型

2.2.3任務(wù)調(diào)度模型 中繼衛(wèi)星任務(wù)調(diào)度約束規(guī)劃模型如下：

其中，適應(yīng)度函數(shù)式(1)表明了調(diào)度的目標(biāo)是確保更高優(yōu)先級(jí)的、更多的任務(wù)能夠調(diào)度成功，式中,分別代表任務(wù)的優(yōu)先級(jí)和任務(wù)在該任務(wù)編排中執(zhí)行時(shí)間的先后次序?qū)m應(yīng)度函數(shù)的貢獻(xiàn)值，它們的乘積表明了優(yōu)先級(jí)高的任務(wù)能夠優(yōu)先調(diào)度。約束條件式(2)表明若一個(gè)任務(wù)調(diào)度成功則該任務(wù)只能在一條鏈路上執(zhí)行，否則該任務(wù)調(diào)度失敗。約束條件式(3)指明在同一條鏈路上的所有調(diào)度成功的任務(wù)中，且表現(xiàn)為在這條鏈路上執(zhí)行完任務(wù)之后執(zhí)行任務(wù)，那滿足這樣的任務(wù)最多只能有一個(gè)，即表明了在一條鏈路上在同一時(shí)間最多只能為一個(gè)任務(wù)服務(wù)。約束條件式(4)確保了在同一條鏈路上執(zhí)行的任務(wù)它們必須排成一個(gè)有序序列，也說(shuō)明了一條鏈路在同一時(shí)刻最多只能執(zhí)行一個(gè)任務(wù)。約束條件式(5)表明了調(diào)度成功的任務(wù)執(zhí)行時(shí)僅能在一個(gè)可用時(shí)間窗口內(nèi)進(jìn)行。約束條件式(6)表明了若兩個(gè)任務(wù),(在之后執(zhí)行) 在同一鏈路上執(zhí)行時(shí)，任務(wù)的開始執(zhí)行時(shí)間在任務(wù)執(zhí)行完之后，進(jìn)一步強(qiáng)調(diào)鏈路在同一時(shí)刻只能執(zhí)行一個(gè)任務(wù)；若任務(wù)沒(méi)有這層關(guān)系，由于恒成立，所以不等式式(6)仍然成立。約束條件式(7)表示兩條鏈路,發(fā)生資源沖突時(shí)，分別在同一顆衛(wèi)星的兩條鏈路上任何兩個(gè)任務(wù)均調(diào)度成功時(shí)，任務(wù)的執(zhí)行時(shí)間是不能有重疊的，要么任務(wù)在任務(wù)之前執(zhí)行即，或任務(wù)在任務(wù)之前執(zhí)行即，表明了一顆衛(wèi)星在同一時(shí)刻只能有一條鏈路為任務(wù)服務(wù)。約束條件式(8)和式(9)表明了調(diào)度成功任務(wù)的執(zhí)行必須在一個(gè)可用時(shí)間窗內(nèi)進(jìn)行，其中約束條件式(8)表明任務(wù)的執(zhí)行時(shí)間必須不小于該可用時(shí)間窗的開始時(shí)間即；約束條件式(9)表明任務(wù)的結(jié)束時(shí)間必須不大于該可用時(shí)間窗的結(jié)束時(shí)間。約束條件式(10)中表明任務(wù)的可執(zhí)行時(shí)間必須在中繼衛(wèi)星與用戶航天器之間的可見時(shí)間窗內(nèi)，也只有在可見時(shí)間窗內(nèi)才能執(zhí)行任務(wù)，即進(jìn)一步約束任務(wù)可執(zhí)行時(shí)間。

3 基于人工蜂群(ABC)算法的中繼衛(wèi)星任務(wù)調(diào)度算法

3.1 人工蜂群算法概述

ABC算法是模擬蜜蜂行為提出的一種優(yōu)化方法，它通過(guò)各人工蜂個(gè)體的局部尋優(yōu)行為，最終在群體中使全局最優(yōu)值凸顯出來(lái)。該算法是一種迭代算法，算法中種群的各個(gè)個(gè)體尋找的蜜源代表一個(gè)可行解，采用適應(yīng)度值來(lái)衡量該蜜源的蜂蜜含量及遠(yuǎn)近程度。通過(guò)在迭代過(guò)程中對(duì)每個(gè)解的質(zhì)量進(jìn)行適應(yīng)度評(píng)估和鄰域操作，從而得到局部的最優(yōu)解，最終得到優(yōu)化問(wèn)題的全局最優(yōu)解。ABC算法在許多優(yōu)化問(wèn)題中取得了成功的應(yīng)用。接下來(lái)探索如何將ABC算法運(yùn)用于解決中繼衛(wèi)星任務(wù)調(diào)度問(wèn)題，并評(píng)估其調(diào)度決策的效率。

3.2基于人工蜂群算法的中繼衛(wèi)星任務(wù)調(diào)度

3.2.1解的描述 運(yùn)用ABC算法進(jìn)行中繼衛(wèi)星任務(wù)調(diào)度時(shí)，一個(gè)解代表了所有待執(zhí)行任務(wù)的一個(gè)有序排列，比如，待執(zhí)行的任務(wù)共有個(gè)，則調(diào)度問(wèn)題的一個(gè)解就代表了這個(gè)任務(wù)的一個(gè)有序排列(,表示任務(wù)編號(hào)，)。對(duì)解所確定的任務(wù)排列，我們進(jìn)行任務(wù)編排(具體的任務(wù)編排方法見第3.2.3節(jié))，從而確定按照解所確定的任務(wù)排序中，有哪些任務(wù)可以被成功調(diào)度，每個(gè)成功調(diào)度任務(wù)的開始執(zhí)行時(shí)間等。進(jìn)而，可以計(jì)算得出解所對(duì)應(yīng)的適應(yīng)度函數(shù)值(具體的計(jì)算方法見第3.2.2節(jié))。ABC算法的最優(yōu)解就是使得適應(yīng)度函數(shù)最大的解，其對(duì)應(yīng)的任務(wù)編排即為最優(yōu)調(diào)度方案。

3.2.3對(duì)解()的任務(wù)編排及解的初始化 在應(yīng)用ABC算法進(jìn)行中繼衛(wèi)星任務(wù)調(diào)度時(shí)，對(duì)解進(jìn)行任務(wù)編排的過(guò)程就是對(duì)全體任務(wù)的有序排列(,表示任務(wù)編號(hào))中每個(gè)任務(wù)順次進(jìn)行是否可成功調(diào)度判定、計(jì)算任務(wù)執(zhí)行時(shí)間的過(guò)程。按照解()確定的任務(wù)順序，從第1個(gè)任務(wù)開始，我們執(zhí)行下述調(diào)度判定和任務(wù)執(zhí)行時(shí)間計(jì)算步驟，直至第個(gè)任務(wù)。其中任務(wù)就是任務(wù)序列中第個(gè)任務(wù)，為便于描述，下面用代表任務(wù)。則對(duì)任務(wù)進(jìn)行執(zhí)行時(shí)間編排的步驟如下：

(5)在選擇可用時(shí)間窗的過(guò)程中，若出現(xiàn)多個(gè)可用時(shí)間窗的開始時(shí)間相同則隨機(jī)選擇一個(gè)可用時(shí)間窗進(jìn)行進(jìn)一步判斷；若遍歷完該任務(wù)所有的可用時(shí)間窗也沒(méi)有找到一個(gè)可用時(shí)間窗為其服務(wù)，則標(biāo)記該任務(wù)調(diào)度失敗。

3.2.4解的鄰域操作 在ABC算法搜索過(guò)程中，為了判斷一個(gè)解的附近是否存在一個(gè)比當(dāng)前解更優(yōu)的解，需要通過(guò)某種方法獲取該解，該方法稱為鄰域操作方法，得到的解稱為鄰域解。ABC算法中解的鄰域操作(包括3.2.5節(jié)介紹的二次鄰域操作)是一個(gè)局部尋優(yōu)的過(guò)程，所以選擇一個(gè)較好的鄰域操作對(duì)于提高算法性能具有積極意義。通過(guò)數(shù)據(jù)仿真測(cè)試，本文采用選擇一個(gè)任務(wù)隨機(jī)插入的鄰域操作方法。具體操作如下：從當(dāng)前解中抽取一個(gè)任務(wù)，然后隨機(jī)插入一個(gè)位置，這樣得到的解即為當(dāng)前解的鄰域解，圖3表示了該鄰域操作方法(以編號(hào)為09的10個(gè)任務(wù)為例)。對(duì)于鄰域操作產(chǎn)生的新解，我們可以按照第3.2.3節(jié)中介紹的任務(wù)編排方法，對(duì)從任務(wù)插入位置開始的所有任務(wù)重新進(jìn)行任務(wù)編排。圖4和圖5表示其它兩種常見的操作方法(選擇兩個(gè)任務(wù)交換位置法和選擇個(gè)任務(wù)隨機(jī)插入法)。

3.2.5解的二次鄰域操作 為了能夠進(jìn)一步提高算法找到最優(yōu)解的速度，基于最優(yōu)解以比較大的概率落在較優(yōu)解附近的特點(diǎn)，我們引入了一個(gè)基于適應(yīng)度值的二次鄰域操作過(guò)程，即從種群中選擇一些較優(yōu)解，然后判斷這些解的附近是否存在一個(gè)更優(yōu)的鄰域解。本文采用錦標(biāo)賽的選擇方式來(lái)選擇較優(yōu)的解來(lái)進(jìn)行二次領(lǐng)域操作。即從該種群中隨機(jī)抽取兩個(gè)解(,)，計(jì)算它們對(duì)應(yīng)的適應(yīng)度值(,)。如果，選擇；否則選擇。

圖3 選擇一個(gè)任務(wù)隨機(jī)插入 ???????? 圖4 選擇兩個(gè)任務(wù)交換位置 ??? ????? 圖5 選擇k(k=3)個(gè)任務(wù)隨機(jī)插入

3.2.7 ABC算法 應(yīng)用ABC算法進(jìn)行中繼衛(wèi)星任務(wù)調(diào)度的步驟如下：

(2)按照第3.2.4節(jié)所介紹的鄰域操作方式，為種群中每個(gè)解生成一個(gè)鄰域解。如果，則設(shè)置,；否則。

(4)根據(jù)(3)得到的解鄰域集合，對(duì)每個(gè)解的鄰域集合進(jìn)行判斷。若某個(gè)解()的鄰域集合是非空的，即，則從該解的鄰域解集合中選擇一個(gè)最好的鄰域解，即滿足,，然后作如下判斷：如果，則設(shè)置,；否則，并清空集合。

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

4.1仿真場(chǎng)景

考慮中繼衛(wèi)星的單址天線的任務(wù)調(diào)度問(wèn)題，通信鏈路為前向鏈路，仿真時(shí)間為00:00:0023:59:59。從衛(wèi)星工具箱(Satellite Tool Kits, STK)[15]中導(dǎo)出一顆中繼衛(wèi)星(TDRS-1)和4顆用戶航天器(ALOS,JB-3 2,NAVSTAR 58,YAOGAN 4)，它們的軌道參數(shù)如表1所示。根據(jù)中繼衛(wèi)星和各用戶航天器的軌道參數(shù)，可以計(jì)算出中繼衛(wèi)星與各用戶航天器之間的可見時(shí)間窗[16]。表2列出了中繼衛(wèi)星TDRS-1與用戶航天器ALOS之間可見時(shí)間窗，其它用戶航天器與中繼衛(wèi)星之間的可見時(shí)間窗就不再一一列出。假設(shè)有20個(gè)任務(wù)申請(qǐng)服務(wù)，各個(gè)任務(wù)的申請(qǐng)服務(wù)請(qǐng)求的約束條件如表3所示，任務(wù)編號(hào)記為Task1,Task2,,Task20。根據(jù)用戶提交的任務(wù)約束、中繼衛(wèi)星和用戶航天器之間的可見時(shí)間窗，可以得到任務(wù)的可用時(shí)間窗。表4顯示了任務(wù)(Task1)的可用時(shí)間窗，其它的任務(wù)可用時(shí)間窗就不再一一列出。

4.2結(jié)果分析

利用基于ABC算法得到的最優(yōu)調(diào)度結(jié)果如表5，表6所示(種群規(guī)模=30, 閾值=200, 迭代次數(shù)=1000，二次鄰域搜索循環(huán)次數(shù)=30，選擇一個(gè)任務(wù)隨機(jī)插入的鄰域操作方式)。其中表5是調(diào)度成功的任務(wù)情況表，表6是調(diào)度失敗的任務(wù)情況表。在表6指明的任務(wù)調(diào)度失敗的原因中，時(shí)間沖突是指中繼衛(wèi)星與用戶航天器在這段時(shí)間內(nèi)不可見，即不能進(jìn)行數(shù)據(jù)中繼；資源沖突是指該任務(wù)搶占衛(wèi)星資源(中繼衛(wèi)星、用戶航天器)失敗。

基于ABC算法的調(diào)度結(jié)果分析如下：(1)調(diào)度的目標(biāo)是完成盡可能多任務(wù)，且優(yōu)先級(jí)高的任務(wù)優(yōu)先安排調(diào)度，考慮中繼衛(wèi)星單址天線任務(wù)調(diào)度如Task19調(diào)度失敗，Task18, Task4, Task14調(diào)度成功，因?yàn)門-ask19搶占資源失敗。(2)任務(wù)的執(zhí)行必須在中繼衛(wèi)星和用戶航天器的可見時(shí)間窗內(nèi)，且也必須滿足用戶提交的時(shí)間約束，如Task16由于在該段時(shí)間內(nèi)中繼衛(wèi)星與用戶航天器不能彼此可見，所以Task16調(diào)度失敗。(3)中繼衛(wèi)星與用戶航天器之間可能具有多個(gè)可見時(shí)間窗，但任務(wù)的執(zhí)行只能在一個(gè)可見時(shí)間窗內(nèi)完成，因此當(dāng)時(shí)間窗長(zhǎng)度小于任務(wù)的持續(xù)時(shí)間長(zhǎng)度時(shí)應(yīng)考慮其它的時(shí)間窗，且同一時(shí)刻一顆衛(wèi)星最多只能為一個(gè)任務(wù)服務(wù)，Task13和Task17因?yàn)楦?jìng)爭(zhēng)資源失敗未能調(diào)度成功。

接下來(lái)將基于ABC算法與基于有效基因路徑表示的改進(jìn)遺傳算法[6]調(diào)度結(jié)果作比較，有關(guān)有效基因路徑表示的改進(jìn)遺傳算法描述和操作請(qǐng)參考文獻(xiàn)[6]。表7(迭代次數(shù)為1000、種群規(guī)模為30)顯示了ABC算法與該遺傳算法相比較的結(jié)果，其中Minimuma, Maximumb, Averagec分別表示算法運(yùn)行20次得到所有最優(yōu)解中適應(yīng)度值的最小值、最大值、平均值。從數(shù)據(jù)分析中可以看出，就中繼衛(wèi)星任務(wù)調(diào)度問(wèn)題而言，ABC算法能夠以較少的運(yùn)算時(shí)間得到更高的適應(yīng)度函數(shù)值，亦即得到中繼星資源使用率更高的任務(wù)調(diào)度方案，其效果相對(duì)文獻(xiàn)[6]提出的算法較好。

表1衛(wèi)星的軌道參數(shù)

軌道參數(shù)TDRS-1ALOSJB-3 2NAVSTAR 58YAOGAN 4 軌道偏心率0.0000000.0001290.0005130.0077060.001523 軌道長(zhǎng)半軸(km)42166.3007063.7846813.44626558.5287023.275 軌道傾角0.08398.15697.02855.95197.873 近地點(diǎn)角0.000103.22198.901298.298119.840 升交點(diǎn)赤經(jīng)88.184184.813114.87825.940187.747 平均近點(diǎn)角282.837256.915261.27960.940240.434 平均運(yùn)動(dòng)(revs/d)1.003014.595715.30492.005714.7548

表2 中繼衛(wèi)星TDRS-1與用戶航天器ALOS之間的可見時(shí)間窗

時(shí)間窗口開始時(shí)間結(jié)束時(shí)間持續(xù)時(shí)間 104:01:0904:59:3400:58:25 205:38:5606:37:5100:58:55 307:15:2908:17:1801:01:49 408:48:3512:34:4603:46:11 513:03:1414:06:1801:03:04 614:43:1015:42:2600:59:16 716:21:3717:20:0100:58:24 817:59:1318:58:2900:59:16 919:35:2220:38:2801:03:06 1021:06:5523:59:5902:53:04

表3各個(gè)任務(wù)的參數(shù)

任務(wù)優(yōu)先級(jí)持續(xù)時(shí)間(s)最早開始時(shí)間最晚結(jié)束時(shí)間服務(wù)的衛(wèi)星 Task12300009:40:0013:45:00ALOS Task23200007:00:0012:44:00ALOS Task33270010:30:3014:00:00ALOS Task41240012:10:0014:00:00ALOS Task54240009:00:0013:20:00ALOS Task62180016:09:0018:30:00JB-3 2 Task75240000:40:0009:00:00JB-3 2 Task82300007:45:0017:40:00JB-3 2 Task95180017:40:0023:00:00JB-3 2 Task106210015:40:0020:30:00JB-3 2 Task117420018:00:0020:56:00NAVSTAR 58 Task127360007:40:0021:40:00NAVSTAR 58 Task138300014:30:0017:10:00NAVSTAR 58 Task143270012:10:0015:47:00NAVSTAR 58 Task155540014:30:0017:10:00NAVSTAR 58 Task166180007:00:0008:30:00YAOGAN 4 Task176300004:34:0018:00:00YAOGAN 4 Task182330010:23:0014:41:00YAOGAN 4 Task193240010:23:0014:41:00YAOGAN 4 Task203300010:00:0021:00:00YAOGAN 4

表4任務(wù)(Task1)的可用時(shí)間窗

可用時(shí)間窗開始時(shí)間結(jié)束時(shí)間服務(wù)的衛(wèi)星 109:40:0012:34:46ALOS 211:19:5512:11:42ALOS

表5基于ABC算法調(diào)度成功的任務(wù)情況

任務(wù)優(yōu)先級(jí)執(zhí)行任務(wù)的開始時(shí)刻持續(xù)時(shí)間(s)服務(wù)的衛(wèi)星(用戶航天器和中繼衛(wèi)星)執(zhí)行任務(wù)的先后順序 Task7504:42:202400JB-3 2, TDRS-11 Task8207:50:153000JB-3 2, TDRS-12 Task2308:48:352000ALOS, TDRS-13 Task5409:21:552400ALOS, TDRS-14 Task1210:01:553000ALOS, TDRS-15 Task3310:51:553000ALOS, TDRS-16 Task18211:36:553300YAOGAN 4, TDRS-17 Task4113:03:142400ALOS, TDRS-18 Task14313:43:142700NAVSTAR 58, TDRS-19 Task20314:48:453000YAOGAN 4, TDRS-110 Task15515:38:455400NAVSTAR 58, TDRS-111 Task6217:58:421800JB-3 2, TDRS-112 Task11718:28:424200NAVSTAR 58, TDRS-113 Task10619:38:422100JB-3 2, TDRS-114 Task12720:13:423600NAVSTAR 58, TDRS-115 Task9521:13:421800JB-3 2, TDRS-116

表6調(diào)度失敗的任務(wù)情況

任務(wù)調(diào)度失敗原因 Task16時(shí)間沖突 Task13資源沖突 Task17資源沖突 Task19資源沖突

表7 ABC算法與遺傳算法[6]的比較

算法MinimumaMaximumbAveragec算法運(yùn)行平均時(shí)間(ms)調(diào)度成功的平均任務(wù)數(shù) ABC算法120812341223.727.85916 遺傳算法 99710631051.968.37212

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

根據(jù)中繼衛(wèi)星任務(wù)調(diào)度問(wèn)題的特點(diǎn)，綜合考慮中繼衛(wèi)星與用戶航天器之間具有可見時(shí)間窗、提交的任務(wù)約束、中繼衛(wèi)星前向資源受限等約束條件，建立了一個(gè)調(diào)度約束規(guī)劃模型，基于這個(gè)模型提出了一種基于ABC算法的中繼衛(wèi)星任務(wù)調(diào)度方法。仿真結(jié)果表明：ABC算法能夠有效解決中繼衛(wèi)星任務(wù)調(diào)度問(wèn)題；通過(guò)與基于有效基因路徑表示的改進(jìn)遺傳算法任務(wù)調(diào)度結(jié)果相比較，從調(diào)度成功的任務(wù)數(shù)、算法的運(yùn)行時(shí)間以及適應(yīng)度函數(shù)值3方面考慮，得之其性能比該改進(jìn)的遺傳算法較好。在將來(lái)，我們也將與其它啟發(fā)式算法作比較。

[1] Teles J, Samii M V, and Doll C E. Overview of TDRSS[J]., 1995, 16(12): 67-76.

[2] 王家勝. 中國(guó)數(shù)據(jù)中繼衛(wèi)星系統(tǒng)及其應(yīng)用拓展[J]. 航天器工程, 2013, 22(1): 1-6.

Wang Jia-sheng. China’s data relay satellite system and its application prospect[J]., 2013, 22(1): 1-6.

[3] Rojannasoonthon S, Bard J F, and Reddy S D. Algorithms for parallel machine scheduling: a case study of the tracking a-n--d data relay satellite system[J]., 2003, 54(8): 806-821.

[4] 方炎申, 陳英武, 顧中舜. 中繼衛(wèi)星調(diào)度問(wèn)題的CSP模型[J]. 國(guó)防科技大學(xué)學(xué)報(bào), 2005, 27(2): 6-10.

Fang Yan-shen, Chen Ying-wu, and Gu Zhong-shun. CSP model of the relay satellite scheduling[J]., 2005, 27(2): 6-10.

[5] 陳理江, 武小悅, 李云峰. 基于時(shí)間靈活度的中繼衛(wèi)星調(diào)度算法[J].航空計(jì)算技術(shù), 2006, 36(4): 48-51.

Chen Li-jiang, Wu Xiao-yue, and Li Yun-feng. Scheduling algorithm for relaying satellite based on temporal flexibility [J]., 2006, 36(4): 48-51.

[6] Fang Yan-shen and Chen Ying-wu. Constraint programming model of TDRSS single access link scheduling problem[C].2006 International Conference on Machine Learning and Cybernetics (ICMLC), Dalian, 2006: 948-951.

[7] 趙衛(wèi)虎, 趙靜, 趙尚弘, 等. 微波與激光混合鏈路中繼衛(wèi)星動(dòng)態(tài)調(diào)度快速啟發(fā)式算法[J]. 中國(guó)激光, 2014, 41(9): 1-7.

Zhao Wei-hu, Zhao Jing, Zhao Shang-hong,. Dynamic scheduling fast heuristic algorithm for data relay satellite with microwave and laser hybird links[J]., 2014, 41(9): 1-7.

[8] Karaboga D. An idea based on honey bee swarm for numerical optimization[R]. Technical report TR06. Computer Engineer-i-ng Department, Engineering Faculty, Erciyes University, 2005.

[9] Karaboga D and Basturk B.On the performance of artificial bee colony (ABC) algorithm[J]., 2008, 8(1): 687-697.

[10] Abu-Mouti F S and El-Hawary M E. Overview of artificial bee colony (ABC) algorithm and its applications[C]. 2012 IEEE I-nternational Systems Conference(SysCon), Vancouver, 2012: 1-6.

[11] Karaboga D, Gorkemli B, Ozturk C,. A comprehensive survey: artificial bee colony (ABC) algorithm and applications[J].,2014, 42(1): 21-57.

[12] Yi Yu-jiang and He Ren-jie. A novel artificial bee colony algorithm[C]. Intelligent Human-Machine Systems and Cybernetics (IHMSC), Hangzhou, 2014: 271-274.

[13] Kojima M, Nakano H, and Miyauchi A. An artificial bee colony algorithm for solving dynamic optimization problems [C]. E-v-olutionary Computation (CEC), Cancun, 2013: 2398-2405.

[14] Liang Yun-chia, Chen A H L, and Nien Yung-hsiang. Artificial bee colony for workflow scheduling[C]. 2014 IEEE Congress o-n Evolutionary Compution(CEC), Beijing, 2014: 558-564.

[15] STK User’s Manual Version 6.0.1 for PCS[M]. USA, Analytical Graphics, Inc., 2005: 144-152.

[16] 李于衡, 孫恩昌, 易克初.中繼衛(wèi)星與用戶星雙向跟蹤關(guān)系及策略[J].西安電子科技大學(xué)學(xué)報(bào)(自然科學(xué)版), 2007, 34(1): 6-10.

Li Yu-heng, Sun En-chang, and Yi Ke-chu. On the tracking strategies and space geometrical relationship between a TDRS a-nd user satellites[J]., 2007, 34(1): 6-10.

Relay Satellite Scheduling Based on Artificial Bee Colony Algorithm

Kai Cai-hong①Xiao Yao①Fang Qing②

①(,,230009,)②(.38,,230031,)

Research on the relay-satellite scheduling problem provides scientific decision-making methods for the task planning of the Tracking and Data Relay Satellite Systems (TDRSS). How to develop a reasonable scheduling model and design the scheduling algorithm according to the model are two key issues to address. In this paper, according to the characteristics of the relay satellite scheduling problem, incorporating the constraints brought by the visible time window between the relay satellite and the user spacecraft, mission attributes submitted by users, and the limited resources of the relay satellite, a scheduling programming model is established. Furthermore, a scheduling algorithm based on the Artificial Bee Colony (ABC) algorithm is proposed. Finally, the simulation data analysis shows that the scheduling algorithm based on the ABC algorithm is an effective and reasonable scheduling method.

Relay satellite scheduling; Visible time windows; Mission attributes; Constraint programming model; Artificial Bee Colony (ABC) algorithm

TN927

A

1009-5896(2015)10-2466-09

10.11999/JEIT150144

2015-01-27；改回日期：2015-05-28；

2015-07-17

開彩紅 chkai@hfut.edu.cn

國(guó)家自然科學(xué)基金(61202459, 61571178)

The National Natural Science Foundation of China (61202459, 61571178)

開彩紅： 女，1982年生，副教授，研究方向?yàn)闊o(wú)線通信與網(wǎng)絡(luò)通信、網(wǎng)絡(luò)體系結(jié)構(gòu)和協(xié)議、網(wǎng)絡(luò)系統(tǒng)性能分析與評(píng)價(jià).

肖 瑤： 男，1990年生，碩士生，研究方向?yàn)闊o(wú)線通信與網(wǎng)絡(luò)通信.

方 青： 男，1972年生，研究員級(jí)高級(jí)工程師，研究方向?yàn)樾l(wèi)星通信系統(tǒng).

1)如在服務(wù)準(zhǔn)備階段，TDRS地面站需要建立TCP通信連接、配置數(shù)據(jù)服務(wù)器系統(tǒng)、完成星間、星地通信鏈路設(shè)備配置等；而在服務(wù)終止階段，則需要完成釋放拆除鏈路、釋放TDRS資源等工作。

2)本節(jié)仿真中只考慮單個(gè)中繼衛(wèi)星在同一時(shí)刻最多服務(wù)一個(gè)用戶的情形。如若中繼衛(wèi)星有多天線(假設(shè)天線數(shù)為)，在本文的中繼衛(wèi)星任務(wù)調(diào)度模型中，通過(guò)將其視為個(gè)中繼衛(wèi)星，可以很容易得到最優(yōu)調(diào)度方案。