黃雙臨，馬冬青，方冬梅，崔 濤

（1.北京衛(wèi)星導航中心，北京 100094；2.華北計算技術(shù)研究所，北京 100083）

基于改進蟻群算法的衛(wèi)星數(shù)傳調(diào)度

黃雙臨1，馬冬青2，方冬梅2，崔 濤2

（1.北京衛(wèi)星導航中心，北京 100094；2.華北計算技術(shù)研究所，北京 100083）

衛(wèi)星數(shù)傳調(diào)度的目標是利用有限的資源合理地安排衛(wèi)星數(shù)傳任務。由于衛(wèi)星數(shù)傳任務眾多而資源有限，且衛(wèi)星數(shù)傳受星地可見性條件以及任務、資源等多方面約束，導致調(diào)度問題十分復雜。針對衛(wèi)星數(shù)傳任務的特點，建立了衛(wèi)星數(shù)傳調(diào)度問題模型，以最大化的加權(quán)調(diào)度任務成功率作為調(diào)度的優(yōu)化目標，提出了基于改進蟻群系統(tǒng)的衛(wèi)星數(shù)傳調(diào)度算法。算法采用任務直接排列的編碼方式，以蟻群系統(tǒng)為基礎，提出自適應的偏向探索概率，動態(tài)地調(diào)整螞蟻探索比率。實驗結(jié)果表明，該算法有效提高了衛(wèi)星數(shù)傳調(diào)度任務的加權(quán)調(diào)度任務成功率。

衛(wèi)星數(shù)傳調(diào)度；蟻群算法；自適應

0 引言

衛(wèi)星數(shù)傳調(diào)度的目標是利用有限的天線、信道、記錄設備和傳輸鏈路等資源，盡可能地安排衛(wèi)星數(shù)據(jù)接收和傳輸任務。其核心是解決多星、多站條件下的數(shù)據(jù)接收任務與天線資源的沖突問題。

衛(wèi)星數(shù)傳調(diào)度涉及多顆衛(wèi)星，這些衛(wèi)星按照各自的軌道運行，它們經(jīng)過各地面站的時間長度和進入時刻不同，而各地面站的天線設備的能力不同，如仰角限制不同，因而各天線設備對各衛(wèi)星有不同的可見時間窗。要完成數(shù)據(jù)接收任務，必須滿足衛(wèi)星可見和天線空閑2個基本條件。另外，衛(wèi)星數(shù)傳調(diào)度還要滿足指定的規(guī)則和約束條件。在多星、多站、多設備和多任務條件下，衛(wèi)星數(shù)傳調(diào)度存在以下2種情況：①任務沖突，即一個資源，要完成多個任務。在同一時間，有多個任務要使用同一天線設備。②資源沖突：也稱作競爭，即一個任務可由多個資源之一完成。在同一時間，有多個任務天線設備都可以完成某個任務。概括起來，數(shù)傳任務調(diào)度是有時間約束的資源調(diào)度，是一個有約束的組合優(yōu)化問題。

國外對衛(wèi)星任務調(diào)度展開了許多研究。Gooley采用混合整數(shù)規(guī)劃算法解決美國空軍衛(wèi)星控制網(wǎng)的低、中高軌衛(wèi)星調(diào)度問題［1］。Pemberton提出了貪婪算法和分支定界法相結(jié)合的優(yōu)先級分割算法［2］。Frank提出了基于約束的衛(wèi)星觀測調(diào)度算法。Parish提出了采用遺傳算法解決多星測控調(diào)度問題的方法［3］。國內(nèi)在建模方面對多種衛(wèi)星調(diào)度問題模型進行細分，融入多種約束，針對各種不同限制及優(yōu)化目標的衛(wèi)星任務調(diào)度問題提出了多種解決方案［4－8］。

本文針對衛(wèi)星數(shù)傳任務的特點，建立了衛(wèi)星數(shù)傳調(diào)度問題模型，以最大化的加權(quán)調(diào)度任務成功率作為調(diào)度的優(yōu)化目標，提出了基于改進蟻群系統(tǒng)的衛(wèi)星數(shù)傳調(diào)度算法。算法采用任務直接排列的編碼方式，以蟻群系統(tǒng)為基礎，提出自適應的偏向探索概率，動態(tài)地調(diào)整螞蟻探索比率。

1 衛(wèi)星數(shù)傳調(diào)度模型分析

衛(wèi)星數(shù)傳系統(tǒng)是一個多星、多站、多設備、多任務和多環(huán)節(jié)的復雜系統(tǒng)。地面網(wǎng)資源由多個接收站、多個接收天線、多個信道、多套記錄設備、多條光纖傳輸鏈路以及其他相關(guān)系統(tǒng)及設備構(gòu)成。各接收站數(shù)據(jù)接收系統(tǒng)內(nèi)接收天線、信道、記錄設備的連接相對固定，通過人工設置可對信道和記錄設備進行調(diào)配。衛(wèi)星數(shù)傳調(diào)度主要是根據(jù)衛(wèi)星觀測預報、任務要求、資源情況和系統(tǒng)狀態(tài)等條件，合理安排地面資源，制定作業(yè)任務。衛(wèi)星數(shù)傳調(diào)度的核心是解決多星、多站條件下的數(shù)據(jù)接收任務與天線資源的沖突問題。如何利用有限的天線資源盡可能地安排數(shù)據(jù)接收任務，是衛(wèi)星數(shù)傳調(diào)度要解決的關(guān)鍵問題。

一項數(shù)據(jù)接收任務對應單個天線的一次跟蹤。需要多個接收站針對某一軌道的衛(wèi)星接力跟蹤時，衛(wèi)星數(shù)傳調(diào)度將任務轉(zhuǎn)換為多項任務。一項數(shù)據(jù)接收任務包含如下要素：

①衛(wèi)星：表示對哪顆衛(wèi)星的數(shù)據(jù)接收任務；

②地面站：表示系統(tǒng)中的地面站；

③天線：表示部署在各地面站的天線；

④可見區(qū)間：表示天線對衛(wèi)星的可見時間窗口；

⑤天線設置的時間限制：表示天線執(zhí)行操作所需的準備時間；

⑥優(yōu)先級：用戶在接收計劃中指定的衛(wèi)星數(shù)據(jù)時效性與重要性要求，分為重要、加急和常規(guī)；

⑦任務執(zhí)行的最少時間長度。

由于任務涉及諸多因素，經(jīng)過預處理和分析整理，可以對任務進行如下歸納：

①根據(jù)資源條件和約束，將地面站和天線、信道、記錄器等資源歸納為可完成任務的實體，即天線設備；將用戶在接收計劃中指定的地面站和任務調(diào)配原則作為實體限制；

②將設備對衛(wèi)星的可見區(qū)間、設備限制以及用戶在接收計劃中指定的開始時間和接收結(jié)束時間，任務執(zhí)行的時間范圍，任務執(zhí)行的最少時間長度歸納為可行時間窗口。

這樣，天線設備及其可行時間窗口就構(gòu)成了任務安排的一個備選項，任務可以選擇安排在任意一個備選項。

在任務集合中，如果一個任務有多個備選項，則發(fā)生競爭；如果多個任務之間的備選項重疊（同一設備，可行時間窗口重疊），則發(fā)生沖突。為了盡可能地安排任務，采取最大化加權(quán)調(diào)度任務成功率作為調(diào)度目標，如式（1）所示。

式中，wi為實際安排任務權(quán)值；maxwi為任務i的最大可能權(quán)值。本文采用優(yōu)先級和接收時間長度作為權(quán)值的設置因素。

2 基于改進蟻群系統(tǒng)的衛(wèi)星數(shù)傳調(diào)度

2.1 蟻群算法

蟻群算法是模擬自然屆螞蟻覓食過程的一種隨機搜索算法。螞蟻在覓食過程中釋放一種特殊的信息素，螞蟻感知信息素濃度信息，傾向于往信息素濃度高的方向行進。在較短路徑上，螞蟻往返時間短，經(jīng)過的螞蟻數(shù)量多，信息素積累快，使得后續(xù)螞蟻傾向于選擇較短路徑。這種正反饋機制，使得螞蟻個體之間相互協(xié)作，尋找到從蟻穴到食物源的最短路徑［9］。

1991年意大利的Dorigo等人提出蟻群算法，用來解決TSP問題［10］。蟻群算法模擬蟻群協(xié)作，根據(jù)信息素濃度采用隨機比例規(guī)則構(gòu)建路徑，并對所有路徑進行全局信息素更新，通過正反饋機制多次迭代，得到問題的滿意解。在基本蟻群算法的基礎上，提出了多種改進方法，包括：精華螞蟻系統(tǒng)、最大最小螞蟻系統(tǒng)和基于排列的螞蟻系統(tǒng)，這些方法在搜索控制方面進行改進，調(diào)整信息素更新方式。1997年Dorigo提出新的蟻群系統(tǒng)，采用偽隨機比例規(guī)則構(gòu)建路徑，調(diào)整信息素全局更新規(guī)則，新增局部更新規(guī)則。這些改進使蟻群算法收斂性能得到改善［11－13］。

本文基于改進蟻群系統(tǒng)的衛(wèi)星數(shù)傳調(diào)度算法，采用任務直接排列的編碼方式，以蟻群系統(tǒng)為基礎，提出自適應的偏向探索概率，動態(tài)地調(diào)整螞蟻探索比率，避免算法收斂過快或算法停滯。

本文采用改進蟻群算法求解衛(wèi)星數(shù)傳調(diào)度問題，算法步驟如下：

①初始化信息素；

②初始化蟻群，用隨機法為蟻群中各螞蟻確定初始任務；

③采用偽隨機比例規(guī)則進行狀態(tài)轉(zhuǎn)移，生成任務序列，即每只螞蟻根據(jù)當前任務依據(jù)信息素濃度確定下一任務，直到確定所有任務；

④按照信息素局部更新規(guī)則，對每只螞蟻的任務序列更新信息素；

⑤按照信息素全局更新規(guī)則，令當前最優(yōu)螞蟻釋放信息素；

⑥轉(zhuǎn)到步驟②進行逐步迭代。當任務序列滿足優(yōu)化準則或達到迭代次數(shù)時，結(jié)束迭代。將蟻群中的最優(yōu)任務序列作為近似最優(yōu)解。

2.2 編碼與解碼

利用蟻群算法解決衛(wèi)星數(shù)傳調(diào)度問題時，首先要確定解的表示形式［14］。衛(wèi)星數(shù)傳調(diào)度需要確定出各任務分配的資源及任務的開始和結(jié)束時間。本算法采用任務號直接排列的表示方法構(gòu)成螞蟻路徑的編碼，采用1～N（N是任務數(shù)）的不重復的自然數(shù)編碼形式，表示調(diào)度序列。在這種編碼中，1，2，…，N表示各衛(wèi)星數(shù)傳任務，安照編碼順序逐一安排各任務。

解碼過程根據(jù)編碼序列所表示的任務順序轉(zhuǎn)換生成實際的調(diào)度方案。解碼時，逐一對任務分配資源和執(zhí)行時間。資源分配策略是：根據(jù)已安排任務情況和剩余可用資源情況安排支持最大任務時間的資源執(zhí)行。解碼過程中，沖突消解是一個重要的環(huán)節(jié)，編碼序列中的各項任務必須滿足星地可見約束及任務資源約束，資源分配時進行約束檢查及裁剪處理，滿足條件的任務納入數(shù)傳調(diào)度表。具體包括：

①在資源與任務弧段不對應的情況下，解碼消除該任務；

②在任務弧段與該星的已分配任務有重疊的情況下，將任務弧段進行裁剪，不重疊部分作為剩余弧段，當剩余弧段有多個時間段時，選擇時間最長部分作為任務項；

③在資源與已分配時間有重疊的情況下，裁剪任務弧段；

④當剩余任務弧段大于任務執(zhí)行的最少時間時，將其納入數(shù)傳調(diào)度表，并記錄資源分配時間。資源分配時間包括執(zhí)行任務的時間和資源設置時間。

在本文研究的衛(wèi)星數(shù)傳調(diào)度問題中，采用數(shù)傳調(diào)度表的加權(quán)調(diào)度任務成功率作為數(shù)傳調(diào)度的目標函數(shù)值，用于評判解的優(yōu)劣。加權(quán)調(diào)度任務成功率高的數(shù)傳調(diào)度優(yōu)于加權(quán)調(diào)度任務成功率低的數(shù)傳調(diào)度。

加權(quán)調(diào)度任務成功率可表示為：

式中，psum為加權(quán)調(diào)度任務成功率；n為任務數(shù)；ti為任務i的安排時間長度；Ti為任務i的最大可能安排時間長度；ai為任務i的優(yōu)先級系數(shù)［15］。

2.3 狀態(tài)轉(zhuǎn)移規(guī)則

算法中每只螞蟻隨機選擇一個任務作為開始任務，隨后按照特定規(guī)律選擇下一任務。在本算法中，執(zhí)行某任務i的螞蟻k，根據(jù)式（3）所示的偽隨機比例規(guī)則選擇下一個任務j。

式中，Jk（i）為螞蟻k尚未執(zhí)行的任務集合；τ（i，j）為從任務i轉(zhuǎn)到任務j的信息素量；η( i，j)為啟發(fā)式信息，η（i，j）＝1／（tc＋tij），tc為任務執(zhí)行時間下限，tij為在執(zhí)行i任務后執(zhí)行j任務的損失時間；α為信息素濃度權(quán)重；β為啟發(fā)式信息權(quán)重；q0為自適應參數(shù)，如式（5）所示，0≤q0≤1；q為在［0，1］區(qū)間均勻分布的隨機數(shù)。當q≤q0時，螞蟻直接執(zhí)行信息素濃度高和損失時間小的最優(yōu)任務，這種情況下，螞蟻根據(jù)當前已知的狀態(tài)確定地選擇任務。當q＞q0時，采用輪盤賭選擇策略來選擇螞蟻的下一任務，這種情況下，選擇任務j的概率為：

2.4 信息素更新規(guī)則

在基于改進蟻群系統(tǒng)的衛(wèi)星數(shù)傳調(diào)度算法中，用信息素來表示某任務作為另一任務后續(xù)任務的優(yōu)劣程度。算法初始化時，所有任務相對另一任務的信息素都被初始化為τ0，τ0＝1／（mTsum），m為螞蟻數(shù)量，Tsum為數(shù)傳任務時間最大可能調(diào)度時間。

2.4.1 信息素全局更新規(guī)則

信息素全局更新規(guī)則是指最優(yōu)螞蟻按全局更新規(guī)則來更新信息素。當螞蟻完成所有任務后，算法對各任務進行信息素更新。在全局更新規(guī)則中，只有至今最優(yōu)的螞蟻才被允許釋放信息素，其他螞蟻不釋放信息素。這個策略以及偽隨機比例規(guī)則的使用，使搜索過程具有更強的指導性。在每次迭代中，在螞蟻完成所有任務后，對最優(yōu)任務調(diào)度序列中的任務更新信息素，信息素全局更新公式為：

式中，ρ為信息素揮發(fā)參數(shù)，代表信息素揮發(fā)速率；Δ τb（i，j）為新增加的信息素，Δ τb（i，j）＝1／（Tsum－Tb）；Mb為最優(yōu)任務調(diào)度序列；Tb為最優(yōu)任務調(diào)度時間。

2.4.2 信息素局部更新規(guī)則

信息素局部更新規(guī)則是指完成任務的每一只螞蟻均釋放信息素。信息素局部更新公式為：

式中，ξ為信息素局部揮發(fā)參數(shù)，0＜ξ＜1；τ0為信息素初始值，τ0＝1／（mTsum）。

3 算法改進

基于改進蟻群系統(tǒng)的衛(wèi)星數(shù)傳調(diào)度算法的改進，主要體現(xiàn)在以下兩方面：

①提出任務直接排列的編碼方式，采用任務直接排列的表示方法構(gòu)成螞蟻路徑的編碼。這種改進有效地避免了采用組合編碼的大量非法解，從而提高了算法的搜索效率。

在現(xiàn)有算法中，多數(shù)參照解決車輛路徑問題VRP的任務與資源組合排列的方法進行編碼。這種編碼方法在應用于解決衛(wèi)星數(shù)傳調(diào)度問題時，由于星地可見要求等約束限制，使得求解過程中面臨大量無效編碼，效率較低。本算法采用任務號直接排列的表示方法構(gòu)成螞蟻路徑的編碼。解碼過程逐一對任務分配資源和執(zhí)行時間，并根據(jù)星地可見約束及任務資源約束進行沖突消解。由于本算法的編碼方式避免了大量非法解，有效地提高了算法的搜索效率。

②提出自適應的偏向探索概率，動態(tài)地調(diào)整螞蟻探索比率。這種方法在算法趨向停滯的情況下，增大了在全局范圍內(nèi)搜索比例，避免算法收斂到局部最優(yōu)解。

在螞蟻群系統(tǒng)中，狀態(tài)轉(zhuǎn)移規(guī)則中的q0是一個很重要的控制參數(shù)，螞蟻以q0為概率選擇當前最優(yōu)任務，以（1－q0）的概率進行偏向探索。本算法提出自適應的偏向探索概率，動態(tài)地調(diào)整螞蟻探索比率，避免算法停滯。算法初期，采用預設的q0，保證算法較快地收斂。在迭代多次問題解沒有改進的情況下，算法按照式（5）減小q0，從而增大偏向探索概率。這種方法在算法趨向停滯的情況下，增大了在全局范圍內(nèi)搜索比例，避免算法收斂到局部最優(yōu)解。

4 實驗驗證

為驗證本算法的調(diào)度能力，本文采用模擬生成的實驗樣本進行解算。在實驗樣本中，衛(wèi)星數(shù)傳任務涉及12顆衛(wèi)星和3個地面站。12顆衛(wèi)星分布在3個軌道面，構(gòu)成walker星座，軌道傾角56°，軌道周期為12 h，偏心率為0，近地點幅角為0°，衛(wèi)星和地面站參數(shù)如下表1和表2所示。每個站有2套設備。設備的工作仰角大于10°，設備的設置時間為2 min。衛(wèi)星數(shù)傳調(diào)度的時間范圍為2012年4月17日12時至2012年4月18日12時，根據(jù)衛(wèi)星與地面站的可見關(guān)系生成60個任務。每個任務最少執(zhí)行時間為5 min，任務優(yōu)先級均為1。

表1 實驗樣本衛(wèi)星參數(shù)

表2 實驗樣本地面站參數(shù)

本文實驗分別用先到先服務FCFS算法、貪婪算法、最短任務優(yōu)先算法和改進蟻群算法對上述實驗樣本進行解算，計算結(jié)果如表3所示。表中改進蟻群算法中螞蟻數(shù)為20，迭代次數(shù)設為100，運行20次，統(tǒng)計平均值作為統(tǒng)計數(shù)據(jù)。實驗樣本的最大可能加權(quán)任務時間為406 531 s。

表3 實驗結(jié)果

從數(shù)據(jù)中可以看出：采用改進蟻群算法得到的優(yōu)化調(diào)度的加權(quán)調(diào)度任務成功率為93．8%，優(yōu)于其他幾個算法。

改進蟻群算法由于算法相對復雜，與其他啟發(fā)式算法相比，較為耗時。算例中計算時間在3 s之內(nèi)，不算過長，可以用于實際的衛(wèi)星數(shù)傳調(diào)度。

5 結(jié)束語

通過分析和實驗驗證可知，本文的基于改進蟻群系統(tǒng)算法有效地解決了衛(wèi)星數(shù)傳調(diào)度問題，提高了加權(quán)調(diào)度任務成功率。本算法采用任務直接排列的編碼方式，有效地提高了算法的搜索效率。提出的自適應的偏向探索概率，動態(tài)地調(diào)整螞蟻探索比率，在算法趨向停滯的情況下增大了在全局范圍內(nèi)搜索比例，避免算法收斂到局部最優(yōu)解。

［1］陳祥國．衛(wèi)星數(shù)傳調(diào)度的蟻群優(yōu)化模型及算法研究［D］．長沙：國防科學技術(shù)大學博士學位論文，2010：7－16．

［2］PEMBERTON Joseph C，F(xiàn)LAVIUS Galiber．A Constraint-Based Approach to Satellite Scheduling［C］∥Boston，MA，USA：Proceedings of Constraint Programming and Large Scale Discrete Optimization，2001：101－114．

［3］李云峰，武小悅．遺傳算法在衛(wèi)星數(shù)傳調(diào)度問題中的應用［J］．系統(tǒng)工程理論與實踐，2008（1）：124－131．

［4］李云峰，武小悅．基于試探性的衛(wèi)星數(shù)傳任務調(diào)度算法研究［J］．系統(tǒng)工程與電子技術(shù)，2007，29（5）：764－766．

［5］凌曉冬，武小悅．一種求解多星測控調(diào)度問題的啟發(fā)式算法［J］兵工自動化，2008（1）：71－73．

［6］孫 兵，陳祥國．混合蟻群優(yōu)化算法求解衛(wèi)星數(shù)傳調(diào)度問題［J］．計算機應用研究，2012（11）：4 065－4 068．

［7］張 超．基于貪婪算法的遙感地面站任務調(diào)度技術(shù)［J］．無線電工程，2011，41（1）：58－60．

［8］徐雪仁，宮 鵬，黃學智．資源衛(wèi)星（可見光）遙感數(shù)據(jù)獲取任務調(diào)度優(yōu)化算法研究［J］．遙感學報，2007，11（1）：109－114．

［9］趙天男，王曉紅．蟻群算法及其應用研究［J］．軟件導刊．2010（6）：34－35．

［10］COLORNIA，DORIGO M，MANIEZZO V．Distributed Op-timization by Ant Colonies［C］∥Proceedings of 1st Euro-pean conference on Artificiial Life，1991：134－142．

［11］DORIGO M，MANIEZZO V，COLONI A．The Ant System：Optimization by a Colony of Cooperating Agents［J］．IEEE Transactions on Systems，Man，and Cybemetics-Part B，1996，26（1）：29－41．

［12］胡銀厚．求解TSP算法的研究與改進［D］．鄭州：鄭州大學碩士學位論文，2012：29－44．

［13］王海波，徐敏強，王日新．基于IP-ACO算法的航天器測控資源調(diào)度技術(shù)［J］．系統(tǒng)工程與電子技術(shù)，2012（4）：719－725．

［14］BARBULESCU L，HOWE A．AFSCN Scheduling：How the Problem and Solution Have Evolved［J］．Mathematical and ComputerModeling，2006，43（9）：1 023－1 037．

［15］SOLOMON M．Algorithms for Vehicle Routing and Sched-uling Problems with Time Window Constraints［J］．Opera-tions Research，1987，35（2）：254－266．

Satellite Data Transmission Scheduling Based on Improved Ant Colony System

HUANG Shuang-lin1，MA Dong-qing2，F(xiàn)ANG Dong-mei2，CUI Tao2
（1．Beijing Satellite Navigation Centre，Beijing 100094，China；2．North China Institute of Computing Technology，Beijing 100083，China）

Satellite data transmission scheduling is to program the missions scientifically using limited resources．Because of the conflict between large task numbers and limited resources and restrictions in terms of satellite visibility，the scheduling for satellite data transmission is very complex．In this paper，a mathematical model of the satellite data transmission scheduling is established，considering the features of the missions，setting a goal to maximize the weighted scheduling success rate．And an improved ant colony optimization algorithm is presented to solve the scheduling problem，which introduces mission-straight permutation coding．Based on ant colony system，the algorithm introduces an adaptive probabilistic decision model for biased-exploration to adjust ant exploration ratio dynamically．Experimental data demonstrate that the algorithm effectively improves the weighted scheduling success rate of satellite data transmission．

satellite data transmission scheduling；ant colony system；adaptive

TP39

A

1003－3106（2015）07－0027－04

10．3969／j．issn．1003－3106．2015．07．08

黃雙臨，馬冬青，方冬梅，等．基于改進蟻群算法的衛(wèi)星數(shù)傳調(diào)度［J］．無線電工程，2015，45（7）：27－30，58．

黃雙臨女，（1975—），碩士。主要研究方向：衛(wèi)星導航。

2015-04-02

馬冬青女，（1972—），碩士。主要研究方向：衛(wèi)星應用。