衛星與浮空器協同偵察任務規劃方法

胡笑旋， 朱外明， 馬華偉

(1. 合肥工業大學管理學院， 安徽 合肥 230009；

2. 合肥工業大學飛行器網絡系統研究所， 安徽 合肥 230009)

?

衛星與浮空器協同偵察任務規劃方法

胡笑旋1,2， 朱外明1,2， 馬華偉1,2

(1. 合肥工業大學管理學院， 安徽 合肥 230009；

2. 合肥工業大學飛行器網絡系統研究所， 安徽 合肥 230009)

摘要：針對衛星和浮空器協同對地偵察任務規劃問題，提出了一種分階段任務規劃方法，將衛星與浮空器協同任務規劃分為任務聚類、任務組分配和任務排程3個相繼的階段。使用層次聚類算法進行任務聚類，通過聚類形成多個任務組；給出了任務組分配的規劃模型，將任務組與平臺資源進行匹配；建立了任務排程的混合整數規劃模型，并使用粒子群算法進行求解，將任務最終分配到相應的平臺上。仿真結果表明，所提出的方法可行且有效。

關鍵詞：衛星; 浮空平臺; 協同偵察; 聚類; 任務規劃

0引言

成像偵察衛星能夠利用星載遙感設備，從空間軌道對指定的可覆蓋的目標實施偵察。由于衛星資源的有限性、載荷的多樣性和偵察任務的不確定性等因素，使得衛星任務規劃成為重要的研究領域。近年來，國內外學者針對單星任務規劃、多星協同規劃等方面進行了研究。對于單星任務規劃，整數規劃和圖論是經典的處理方法。文獻[1]介紹了成像衛星任務規劃的0-1整數規劃模型，使用二進制變量表示傳感器對目標的選擇與否，將偵察目標間的時間互斥性轉化為約束。文獻[2]采用圖論的方法，將偵察目標看作節點，沿衛星前進方向連接無時間互斥的節點，組成時間序、有向、無圈連通圖，衛星偵察目標的選擇為連通圖中總權重最大的一條路徑。對于多星任務規劃，文獻[3]采用預先分配的方式先將任務分配到各單衛星，然后各單星分別進行任務規劃。文獻[4]使用0-1型整數變量表示任務對衛星的選擇，使用連續型變量表示時間，建立起LTAP問題的混合整數線性規劃模型。其他還有合同網協議[5]、多維背包[6]等模型。衛星任務規劃的求解算法多樣，有遺傳算法[7]、禁忌搜索[8]、粒子群算法[9]等。

臨近空間浮空器具有與衛星所不同的特點[10-11]，它能夠在指定的空域中定點懸停，具有駐留時間長，效費比高等優點。隨著通信技術的發展，平臺間的通信鏈路日益完善，衛星與浮空器協同偵察已逐漸走向應用。將衛星和浮空器組成協同系統，共同完成對地偵察任務，能夠實現不同類型平臺能力互補，擴大同一時刻覆蓋范圍，縮短目標重訪時間，降低總體偵察成本等。

衛星與浮空器協同偵察對任務規劃技術提出了更高的要求，其問題的復雜性主要體現在如下幾點：①平臺的運動方式不同，衛星平臺在空間軌道中高速運動，而浮空器在空域中定點懸停，如何基于不同的運行方式建立統一的規劃模型是一個難點；②任務有時間要求，需要在規定的時間內完成，任務對平臺的選擇要顧及其時間特性；③任務之間存在復雜的耦合關系，耦合關系的存在增加了規劃問題的復雜度。

本文研究了一種衛星與浮空器協同偵察任務規劃方法，將整個任務規劃過程分解為任務聚類、任務組分配和任務排程3個相繼的階段，使用層次聚類算法進行任務聚類，給出了任務組分配模型和任務排程模型，使用粒子群算法進行求解，最后基于Matlab和衛星工具箱(satellite tool kit, STK)進行了仿真實驗。

1問題描述

本文所研究的任務規劃問題可概括為：在滿足偵察任務需求約束(主要包括任務傳感器類型約束、任務時間約束、任務耦合關系約束等)和衛星、浮空器資源約束的條件下，以最大化任務收益為目標，制定目標集合T在資源集合R上的計劃安排，即為每一個平臺指定任務和任務的執行時間。本文假設如下：①一個平臺只搭載一個偵察傳感器；②具有耦合關系的任務具有一致的傳感器類型要求，且處于同一時段內；③浮空器按照一定的順序對其所能覆蓋的目標進行偵察。

2任務規劃流程設計

協同偵察的平臺資源具有不同的時空行為，偵察衛星是高速移動的天基平臺，具有嚴格的軌道限制，而浮空器沒有高速移動的特點，是一種定點平臺。因此，衛星和浮空器協同偵察任務規劃的過程較為復雜，要考慮不同平臺在對地覆蓋的范圍和時間窗上的差異。本文將任務規劃過程分解成3個相繼的階段，分別為任務聚類、任務組分配和任務排程，如圖1所示。通過這3個階段的依次執行，完成衛星和浮空器的協同偵察任務規劃。

圖1　任務規劃流程

其中任務聚類是將用戶提交的任務基于時間、地理位置、傳感器需求等屬性進行聚合，形成不同的任務組的過程。屬于同一個任務組中的任務可以由相似的平臺執行。任務組分配是將平臺某一時段的工作時間劃分給某一任務組的過程，實現任務組到平臺的預分配。任務排程是對各任務組內的任務進行詳細規劃，確定每個任務執行的平臺和時間。

3任務聚類

通過任務聚類形成任務組，任務組是一個任務子集，組內的任務具有相同或相近的特性。任務聚類時要綜合考慮任務所要求的傳感器類型、任務區域、任務時間等多個屬性。層次聚類算法[11-12]具有簡單、快速的特點，有自頂向下和自底向上2種策略。本文選取層次聚類算法實現聚類，采用自底向上的策略，首先將每個任務各自作為一個任務組，然后逐步的合并成為越來越大的任務組，直到全部都聚成一個任務組或某個終止條件得到滿足。

3.1時間距離計算

(1)

3.2空間距離計算

步驟 1將經緯度轉換成空間坐標。如圖2所示，設ti對應點A，tj對應點B。α為A的緯度，β為A的經度，R為地球半徑，則A點的三維坐標由式(2)計算獲得:

(2)

圖2　經緯度與直角坐標轉換示意圖

步驟 2計算兩點之間的空間直線距離D,直接由空間距離公式(3)計算獲得:

(3)

步驟 3根據立體幾何計算出其球面距離。如圖2所示，A、B兩點的直線距離D已由步驟2計算得到，根據立體幾何，A,B之間的球面距離由式(4)計算得到:

(4)

3.3傳感器類型距離計算

(5)

式中，M為給定的足夠大的整數。

3.4任務合成距離計算

任務ti與tj之間的距離dij是綜合時間距離、空間距離、傳感器類型距離得到，其計算公式如式(6)所示(其中，L為給定的參數)。

(6)

式(6)表明，當任務ti與tj的時間距離超過一定數值L時，或ti與tj所要求傳感器的類型不一致時，將ti與tj之間的距離dij計為M，以使2個任務聚到不同的任務組中。其他情況下，dij定義為ti與tj的空間距離。

令G= {gl|l= 1, 2, …,NG}表示聚成的任務組，其中NG表示任務組的數量。令Dlm(l,m=1, 2,…,NG)表示任務組之間的距離，其計算公式為

(7)

Dlm的更新采用最小距離方法，即新聚成的任務組與其他任務組之間的距離使用該任務組中的任務與其他任務組中的任務之間的最小距離代替。

輸入：任務集合T，聚成的任務組數NG。

輸出：任務組G= {gl|l= 1, 2, …,NG}。

4任務組分配

(8)

(10)

5任務排程

通過任務聚類將大量廣布的任務劃分成NG個任務組，又通過任務組分配建立了任務組與資源之間的分配關系，使得特定的任務組合可以交由特定平臺的特定時段去執行。任務排程是在各平臺組合內進行任務執行詳細計劃的制定，即確定具體的任務由哪個平臺在何時執行。

5.1數學模型

(11)

5.2求解算法

任務排程的數學模型為混合整數規劃模型，當任務增多時，選擇組合成指數增長，適合采用智能求解算法進行求解。粒子群算法具有易實現、精度高、收斂快等優點，在求解組合優化問題表現出較大優勢。

粒子群算法是從鳥類捕食的行為中得到啟發而產生，文獻[13-14]提出，屬于進化算法的一種。粒子群算法通過更新各個粒子的位置、飛行的速度和適應度，使得搜索不斷地向前迭代，最終尋找到優良的解，其速度和位置更新公式分別見式(21)和式(22)。

(21)

(22)

5.2.1編碼方式

職業教育是我國教育領域的主要構成部分，對推動經濟增長有著十分重要的作用。學?；鶎有姓ぷ髡呤枪芾斫逃闹饕獦嫵刹糠?，在培育人才的過程中承擔著十分關鍵的責任。不過，在職業教育發展中，高校始終傾向于教師文化素養與教育能力的提升，普遍忽略了行政工作者的職業特征與心理活動，進而導致學校的行政管理者出現普遍性的職業倦怠現象。

使用整數編碼方式對二進制決策變量進行編碼。任務對資源的選擇具有唯一性，即一個任務最多選擇一個資源。因此任務的選擇有2種情況：一是任務得以執行，并選擇一個平臺資源執行；二是得不到執行，不選擇任何平臺資源。采用以下編碼方式確定任務對資源的選擇：

(1) 使用整數對資源進行編號，增加虛擬資源編號0；

(2) 使用一維整數變量表示任務選擇的資源編號，當變量選擇資源0時表示任務不執行。

例如一維變量X取值如表1所示。

表1　一維變量X取值

表1說明，任務1、2、3、5分別由資源1、3、3、2執行，任務4不執行。

5.2.2更新方式

(1) 慣性權重。慣性權重w衡量粒子對以前的學習狀況，在標準粒子群算法后期的迭代過程中，種群容易陷入局部最優。為使算法的運行更加穩健，設置慣性權重w的值隨著迭代次數的增加而線性遞減。

(2) 收縮因子。收縮因子是文獻[15]提出的對標準粒子群算法的一種改進，旨在促進算法的收斂。改進后的速度更新公式見式(23)。

(23)

式中，χ為收縮因子，其計算公式為

6仿真實驗

根據本文所介紹的相關技術，進行了任務聚類、任務組分配和任務排程的仿真實驗。實驗平臺：CPU為Intel Core i5 3.10 GHz，內存為4 GB。實驗基于Matlab編程實現，其中平臺資源對目標覆蓋的時間窗采用STK 9.0軟件計算。

6.1任務聚類與任務組分配實驗

6.1.1方法可行性驗證

按照均勻分布的原則，選取不同時段、不同經緯度、不同傳感器要求的偵察任務共100個，如圖3所示。選取4顆衛星平臺和3個定點浮空器平臺進行實驗，其中衛星的時段使用其軌道圈次計算，即衛星一個軌道圈次計為衛星的一個可用時段。浮空器為部署好的定點平臺,各平臺數據如表2所示。

圖3　任務目標分布圖

資源類型傳感器類型可用時段個數r1衛星114r2衛星115r3衛星214r4衛星214r5浮空器210r6浮空器110r7浮空器110

實驗中的傳感器類型有2類,任務的時間要求從某日的0點到24點之間。首先進行任務聚類實驗，根據任務的傳感器類型要求、區域位置、時段的不同，要求聚為8類。然后使用表1中平臺數據，結合任務聚類的結果進行任務組分配實驗，使用STK計算出平臺對任務的覆蓋數據，并據此計算各平臺時段資源分配給各任務組的收益，使用Matlab線性規劃工具箱求解。任務聚類與任務組分配的實驗結果見表3。

表3　任務聚類與任務組分配的實驗結果

分析實驗結果，各任務組內的任務均具有傳感器類型要求相同、時段相同、區域位置集中的特點。各任務組之間具有明顯不同的任務特性。從任務組的分配結果可以看出，當任務組內包含的任務數較多時，對應分配的時段個數也就越多，這是因為在較多任務的任務組內，資源覆蓋的任務數較多，則平臺時段資源分配給該任務組的收益越大，導致資源越向該任務組集中。但由于時段、傳感器類型等限制，沒有產生過度集中的現象。

6.1.2方法效率分析

為了分析算法和模型的效率，分別使用不同數量的任務進行任務聚類和任務組分配實驗，表4記錄了任務數在100~1 000的實驗的耗時數據。

表4　任務聚類和任務組分配實驗效率統計　s

由表4可知，隨著任務數的增多，任務聚類和任務組分配的耗時在不斷增加。但對應任務數的增加，耗時的增長呈現近似線性形式，在規劃過程中是可以接受的。

6.2任務排程實驗

為驗證任務排程的混合整數規劃模型，選取一定數量的任務，目標分布見圖4，使用表1中的平臺進行實驗(此時假設平臺具有相同特性的傳感器)。衛星偵察時間窗采用STK計算，浮空器按照一定的順序對其所能覆蓋的目標進行偵察。規劃周期從某日的0點到12點，各平臺資源在各時段內對各目標無重訪現象。同時，在任務周期內隨機設置任務的時間要求，隨機給定任務的優先級，實驗所用其他數據使用計算機隨機生成?；贛atlab采用粒子群算法進行求解。

圖4　任務排程的目標分布

6.2.1任務排程的協同程度分析

在滿約束下使用不同任務數進行實驗，分別記錄浮空器執行任務數、衛星平臺執行任務數，分析浮空器和衛星平臺協同執行任務的情況，相關的數據見表5。由表5可知，隨著任務數目的增多，執行的總任務數在逐漸減少。算例不同，所獲取數據存在差異，但浮空器執行的任務占總執行任務的比重相對穩定，未出現過度偏離的現象。協同效果的好壞與任務的耦合關系的設置不無影響。

表5　衛星與浮空器協同程度分析

6.2.2任務排程的效率分析

在不同任務數下，隨機的設置捆綁關系和緊前關系，分別進行無捆綁且無緊前約束、只附帶捆綁約束、只附帶緊前約束和滿約束實驗，分別記錄每種情況下的時耗和規劃成功任務占總任務的比重，見圖5和圖6。由圖5可知，在沒有捆綁或緊前約束的情況下，任務規劃求解的效率較高。但是，提供高質量的信息服務，任務之間的耦合關系必須考慮。隨著任務數目的增多，描述任務耦合關系的矩陣也越來越大，進行處理所要消耗的時間也越來越大。由圖6可知，在資源相對充足的條件下，任務的耦合關系約束成為影響任務完成率的主要因素。任務的耦合關系越多，平臺就越難以按照要求執行可選的任務，使得耦合的任務均得不到執行。但任務的耦合關系必須考慮，此時可以通過增加資源種類，利用各種平臺協同而作，提升任務的完成率。在其他條件不變的情況下，使用不同數量的平臺進行實驗，資源越充足，總體任務的完成程度越大，但規劃消耗的時間也相應地增大。

圖5　不同約束下規劃的效率分析

圖6　不同約束下規劃成功任務占總任務的比重

7結論

任務規劃是成像偵察衛星與浮空器應用中的關鍵技術之一。本文以成像偵察衛星和浮空器為對象，分析了衛星與浮空器協同偵察的優勢，結合實際需求，設計了一種分階段的衛星與浮空器協同偵察任務規劃方法，將整個規劃過程分解為任務聚類、任務組分配和任務排程3個相繼的階段。通過分解，降低了任務規劃問題的求解難度。隨后，使用層次聚類算法進行任務聚類，給出了任務組分配和任務排程的數學規劃模型，并使用粒子群優化算法進行求解。根據所提出的模型和算法，基于STK和Matlab進行了仿真實驗。實驗結果驗證了所提出的方法的可行性和有效性。

參考文獻：

[1] Gabrel V. Strengthened 0-1 linear formulation for the daily satellite mission planning[J].JournalofCombinatorialOptimization, 2006, 11(3): 341-346.

[2] Chen H, Li J, Jing N, et al. Scheduling model and algorithms for autonomous electromagnetic detection satellites[J].ActaAeronauticaetAstronauticaSinica, 2010, 31(5): 1045-1053. (陳浩, 李軍, 景寧, 等. 電磁探測衛星星上自主規劃模型及優化算法[J]. 航空學報, 2010, 31(5): 1045-1053.)

[3] Wang Z Y, Wang Y Q, Wang J, et al. New multi-satellite scheduling method[J].ChineseSpaceScienceandTechnology, 2012(1): 8-14. (王智勇, 王永強, 王鈞, 等. 多星聯合任務規劃方法[J]. 中國空間科學技術, 2012(1): 8-14.)

[4] Wang H B, Xu M Q, Wang R X, et al. Long-term acquisition plan method for small satellites constellation[J].SystemsEngineeringandElectronics, 2011, 33(6): 1293-1298. (王海波, 徐敏強, 王日新, 等. 對地觀測小衛星星座長期任務規劃求解技術[J]. 系統工程與電子技術, 2011, 33(6): 1293-1298.)

[5] Gao L, Zhou L A, Sha J C. Task allocation model and algorithm for DSS cooperation mechanism[J].JournalofSystemsEngineering, 2009, 24(4): 445-450. (高黎, 周利安, 沙基昌. 分布式衛星系統協作任務分配模型及優化算法[J]. 系統工程學報, 2009, 24(4): 445-450.)

[6] Vasquez M, Hao J K. A “logic-constrained” knapsack formulation and a tabu algorithm for the daily photograph scheduling of an earth observation satellite[J].ComputationalOptimizationandApplications, 2001, 20(2): 137-157.

[7] Mansour M A A, Dessouky M M. A genetic algorithm approach for solving the daily photograph selection problem of the SPOT5 satellite[J].Computers&IndustrialEngineering, 2010, 58(3): 509-520.

[8] Bianchessi N, Cordeau J F, Desrosiers J, et al. A heuristic for the multi-satellite, multi-orbit and multi-user management of earth observation satellites[J].EuropeanJournalofOperationalResearch, 2007, 177(2): 750-762.

[9] Yin P Y, Yu S S, Wang P P, et al. A hybrid particle swarm optimization algorithm for optimal task assignment in distributed systems[J].ComputerStandards&Interfaces, 2006, 28(4): 441-450.

[10] Jing X L, Zhang J W, Huang S C. Development actuality and key technology of near space[J].AerospaceManufacturingTechnology, 2011(2): 17-21. (景曉龍, 張建偉, 黃樹彩. 臨近空間發展現狀與關鍵技術研究[J]. 航天制造技術, 2011(2): 17-21.)

[11] Jain A K, Murty M N, Flynn P J. Data clustering: a review[J].ACMComputingSurveys, 1999, 31(3): 264-323.

[12] Murtagh F. A survey of recent advances in hierarchical clustering algorithms[J].TheComputerJournal,1983,26(4):354-359.

[13] Kennedy J, Eberhart R. Particle swarm optimization[C]∥Proc.oftheIEEEInternationalConferenceonNeuralNetworks, 1995, 4(2): 1942-1948.

[14] Parsopoulos K E, Vrahatis M N.Particleswarmoptimizationandintelligence:advancesandapplications[M]. Hershey: Information Science Reference, 2010.

[15] Clerc M, Kennedy J. The particle swarm-explosion, stability, and convergence in a multidimensional complex space[J].IEEETrans.onEvolutionaryComputation, 2002, 6(1):58-73.

胡笑旋(1978-)，男，教授，博士，主要研究方向為空間信息網絡任務規劃與資源調度。

E-mail：xiaoxuanhu@hfut.edu.cn

朱外明(1988-)，男，碩士研究生，主要研究方向為空間信息網絡任務規劃與資源調度。

E-mail：zhuwaiming@hfutfxqs.com

馬華偉(1977-)，男，副教授，博士，主要研究方向為物流與供應鏈管理、管理信息系統。

E-mail：colt_mhw@126.com

網絡優先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20141019.2345.008.html

Method of satellite and aerostat cooperative reconnaissance

mission planning

HU Xiao-xuan1,2， ZHU Wai-ming1,2， MA Hua-wei1,2

(1.SchoolofManagement,HefeiUniversityofTechnology,Hefei230009,China;

2.AircraftNetworkSystemInstitute,HefeiUniversityofTechnology,Hefei230009,China)

Abstract:A staged task planning method is put forward to solve the task planning problem of satellite and aerostat cooperative reconnaissance. The satellite and aerostat cooperative task planning is divided into three stages that are task clustering, task groups allocation and task scheduling. Firstly, a hierarchical clustering algorithm is used in task clustering by which several task groups would be produced. Secondly, the planning model of task group allocation which aims to build connections between task groups and resources is introduced. At last, a mixed integer planning model used in task scheduling is modeled and a corresponding particle optimize algorithm is introduced. By task scheduling, all tasks would be finally allocated to the specific platforms. The simulation results show that the proposed method is feasible and efficient.

Keywords:satellite; aerostat; cooperative reconnaissance; clustering; mission planning

作者簡介：

中圖分類號：V 19

文獻標志碼：A

DOI:10.3969/j.issn.1001-506X.2015.07.15

基金項目：中央高?；究蒲袠I務費專項資金(2012HGZY0009)資助課題

收稿日期：2014-05-29；修回日期：2014-08-13；網絡優先出版日期：2014-10-19。