衛(wèi)星與浮空器協(xié)同偵察任務規(guī)劃方法

胡笑旋， 朱外明， 馬華偉

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

2. 合肥工業(yè)大學飛行器網(wǎng)絡系統(tǒng)研究所， 安徽 合肥 230009)

?

衛(wèi)星與浮空器協(xié)同偵察任務規(guī)劃方法

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

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

2. 合肥工業(yè)大學飛行器網(wǎng)絡系統(tǒng)研究所， 安徽 合肥 230009)

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

關鍵詞：衛(wèi)星; 浮空平臺; 協(xié)同偵察; 聚類; 任務規(guī)劃

0引言

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

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

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

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

1問題描述

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

2任務規(guī)劃流程設計

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

圖1　任務規(guī)劃流程

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

3任務聚類

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

3.1時間距離計算

(1)

3.2空間距離計算

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

(2)

圖2　經(jīng)緯度與直角坐標轉(zhuǎn)換示意圖

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

(3)

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

(4)

3.3傳感器類型距離計算

(5)

式中，M為給定的足夠大的整數(shù)。

3.4任務合成距離計算

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

(6)

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

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

(7)

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

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

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

4任務組分配

(8)

(10)

5任務排程

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

5.1數(shù)學模型

(11)

5.2求解算法

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

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

(21)

(22)

5.2.1編碼方式

職業(yè)教育是我國教育領域的主要構(gòu)成部分，對推動經(jīng)濟增長有著十分重要的作用。學校基層行政工作者是管理教育的主要構(gòu)成部分，在培育人才的過程中承擔著十分關鍵的責任。不過，在職業(yè)教育發(fā)展中，高校始終傾向于教師文化素養(yǎng)與教育能力的提升，普遍忽略了行政工作者的職業(yè)特征與心理活動，進而導致學校的行政管理者出現(xiàn)普遍性的職業(yè)倦怠現(xiàn)象。

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

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

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

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

表1　一維變量X取值

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

5.2.2更新方式

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

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

(23)

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

6仿真實驗

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

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

6.1.1方法可行性驗證

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

圖3　任務目標分布圖

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

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

表3　任務聚類與任務組分配的實驗結(jié)果

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

6.1.2方法效率分析

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

表4　任務聚類和任務組分配實驗效率統(tǒng)計　s

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

6.2任務排程實驗

為驗證任務排程的混合整數(shù)規(guī)劃模型，選取一定數(shù)量的任務，目標分布見圖4，使用表1中的平臺進行實驗(此時假設平臺具有相同特性的傳感器)。衛(wèi)星偵察時間窗采用STK計算，浮空器按照一定的順序?qū)ζ渌芨采w的目標進行偵察。規(guī)劃周期從某日的0點到12點，各平臺資源在各時段內(nèi)對各目標無重訪現(xiàn)象。同時，在任務周期內(nèi)隨機設置任務的時間要求，隨機給定任務的優(yōu)先級，實驗所用其他數(shù)據(jù)使用計算機隨機生成。基于Matlab采用粒子群算法進行求解。

圖4　任務排程的目標分布

6.2.1任務排程的協(xié)同程度分析

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

表5　衛(wèi)星與浮空器協(xié)同程度分析

6.2.2任務排程的效率分析

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

圖5　不同約束下規(guī)劃的效率分析

圖6　不同約束下規(guī)劃成功任務占總?cè)蝿盏谋戎?/p>

7結(jié)論

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

參考文獻：

[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. (陳浩, 李軍, 景寧, 等. 電磁探測衛(wèi)星星上自主規(guī)劃模型及優(yōu)化算法[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. (王智勇, 王永強, 王鈞, 等. 多星聯(lián)合任務規(guī)劃方法[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. (王海波, 徐敏強, 王日新, 等. 對地觀測小衛(wèi)星星座長期任務規(guī)劃求解技術[J]. 系統(tǒng)工程與電子技術, 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. (高黎, 周利安, 沙基昌. 分布式衛(wèi)星系統(tǒng)協(xié)作任務分配模型及優(yōu)化算法[J]. 系統(tǒng)工程學報, 2009, 24(4): 445-450.)

[6] Vasquez M, Hao J K. A “l(fā)ogic-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. (景曉龍, 張建偉, 黃樹彩. 臨近空間發(fā)展現(xiàn)狀與關鍵技術研究[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-)，男，教授，博士，主要研究方向為空間信息網(wǎng)絡任務規(guī)劃與資源調(diào)度。

E-mail：xiaoxuanhu@hfut.edu.cn

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

E-mail：zhuwaiming@hfutfxqs.com

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

E-mail：colt_mhw@126.com

網(wǎng)絡優(yōu)先出版地址：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

基金項目：中央高校基本科研業(yè)務費專項資金(2012HGZY0009)資助課題

收稿日期：2014-05-29；修回日期：2014-08-13；網(wǎng)絡優(yōu)先出版日期：2014-10-19。