開彩紅 肖 瑤 方 青

?

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

開彩紅*①肖 瑤①方 青②

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

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

3.1 人工蜂群算法概述

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

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

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

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

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

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

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

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

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

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

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

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

4.1仿真場景

考慮中繼衛(wèi)星的單址天線的任務(wù)調(diào)度問題，通信鏈路為前向鏈路，仿真時間為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ù)，可以計算出中繼衛(wèi)星與各用戶航天器之間的可見時間窗[16]。表2列出了中繼衛(wèi)星TDRS-1與用戶航天器ALOS之間可見時間窗，其它用戶航天器與中繼衛(wèi)星之間的可見時間窗就不再一一列出。假設(shè)有20個任務(wù)申請服務(wù)，各個任務(wù)的申請服務(wù)請求的約束條件如表3所示，任務(wù)編號記為Task1,Task2,,Task20。根據(jù)用戶提交的任務(wù)約束、中繼衛(wèi)星和用戶航天器之間的可見時間窗，可以得到任務(wù)的可用時間窗。表4顯示了任務(wù)(Task1)的可用時間窗，其它的任務(wù)可用時間窗就不再一一列出。

4.2結(jié)果分析

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

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

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

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

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

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

時間窗口開始時間結(jié)束時間持續(xù)時間 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各個任務(wù)的參數(shù)

任務(wù)優(yōu)先級持續(xù)時間(s)最早開始時間最晚結(jié)束時間服務(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)的可用時間窗

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

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

任務(wù)優(yōu)先級執(zhí)行任務(wù)的開始時刻持續(xù)時間(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時間沖突 Task13資源沖突 Task17資源沖突 Task19資源沖突

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

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

5 結(jié)束語

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

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

[2] 王家勝. 中國數(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)度問題的CSP模型[J]. 國防科技大學(xué)學(xué)報, 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] 陳理江, 武小悅, 李云峰. 基于時間靈活度的中繼衛(wèi)星調(diào)度算法[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)星動態(tài)調(diào)度快速啟發(fā)式算法[J]. 中國激光, 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é)報(自然科學(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

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

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

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

肖 瑤： 男，1990年生，碩士生，研究方向為無線通信與網(wǎng)絡(luò)通信.

方 青： 男，1972年生，研究員級高級工程師，研究方向為衛(wèi)星通信系統(tǒng).

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

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