分布式遙感衛(wèi)星任務(wù)分配的合同網(wǎng)絡(luò)算法

于龍江， 吳限德， 毛一嵐， 高洪濤， 郝勇

(1. 北京空間飛行器總體設(shè)計(jì)部，北京 100094；2.哈爾濱工程大學(xué) 航天與建筑工程學(xué)院，黑龍江 哈爾濱 150001； 3.哈爾濱工程大學(xué) 自動(dòng)化學(xué)院，黑龍江 哈爾濱 150001)

近年來，遙感衛(wèi)星在軌數(shù)量不斷增多、星座規(guī)模不斷擴(kuò)大，衛(wèi)星姿態(tài)敏捷機(jī)動(dòng)能力不斷提高，這些都對系統(tǒng)應(yīng)用效能的保障與提升帶來了挑戰(zhàn)。在單星層面，敏捷衛(wèi)星具備三軸聯(lián)合的姿態(tài)調(diào)整能力，并可以與成像過程相結(jié)合形成多點(diǎn)、拼幅、立體、主動(dòng)推掃等成像模式，能有效提高衛(wèi)星的工作效率；從系統(tǒng)的角度，軍、民、商界均在部署數(shù)顆甚至數(shù)十顆遙感衛(wèi)星組成的衛(wèi)星星座，以期采用多星協(xié)同的方式完成諸如目標(biāo)搜索、識別、跟蹤等復(fù)雜任務(wù)。在這一背景下，如何更好地進(jìn)行多星的任務(wù)分配、單星的任務(wù)規(guī)劃、星間的任務(wù)協(xié)同，是充分發(fā)揮系統(tǒng)能力、獲取更高收益所必須解決的關(guān)鍵問題[1]。

由于任務(wù)數(shù)量多、可選模式豐富、時(shí)效性要求高，面向多星的任務(wù)分配需要依靠良好的機(jī)器算法予以實(shí)現(xiàn)；同時(shí)也可以發(fā)揮系統(tǒng)運(yùn)行的自主能力、降低人力負(fù)擔(dān)。目前國內(nèi)外針對分布式星群的任務(wù)分配問題，主要采用集中式和分布式2種基本模式。在研究和實(shí)際應(yīng)用中多采用集中式任務(wù)分配方法，法國的Lemaitre等[2-3]針對敏捷衛(wèi)星任務(wù)規(guī)劃問題，提出了約束規(guī)劃模型。

Potter等[4]對啟發(fā)式算法在任務(wù)分配中的應(yīng)用很好地解決了不同任務(wù)需求對分配方式的要求。這種集中式任務(wù)規(guī)劃的方法靈活性較低，且難以適應(yīng)衛(wèi)星在軌的實(shí)時(shí)狀態(tài)變化。因此，分布式衛(wèi)星的任務(wù)分配問題對規(guī)劃算法提出了新的要求，即更高的靈活性、更低的計(jì)算消耗以及更快的星上響應(yīng)速度。這使得分布式任務(wù)規(guī)劃方法在解決這類星上任務(wù)規(guī)劃問題中更具優(yōu)勢。

國外的分布式任務(wù)規(guī)劃系統(tǒng)相對成熟，其中NASA的Richards等，針對分布式衛(wèi)星星座的在軌自主運(yùn)行問題，研發(fā)了星上自主規(guī)劃系統(tǒng)(distributed spacecraft coordination planning and scheduling，D-SpaCPlanS)，該系統(tǒng)采用靈活的層次化組織結(jié)構(gòu)，能夠很好地適應(yīng)資源或任務(wù)的變化[4]。國內(nèi)很多學(xué)者也對分布式任務(wù)規(guī)劃方法進(jìn)行了研究。王沖等[5]提出基于“分治-合作”策略的多衛(wèi)星中心協(xié)同規(guī)劃方法，在分析各衛(wèi)星中心遙感資源能力和中心之間關(guān)系的基礎(chǔ)上建立了多衛(wèi)星中心協(xié)同規(guī)劃問題模型，并提出了多中心合作協(xié)同進(jìn)化規(guī)劃算法，將集中式優(yōu)化問題轉(zhuǎn)化為分布式優(yōu)化問題，使得多顆衛(wèi)星之間能夠獨(dú)立地進(jìn)行決策。向仍湘[6]研究了敏捷衛(wèi)星任務(wù)調(diào)度問題，并且針對不同的任務(wù)規(guī)模，設(shè)計(jì)了不同的求解算法。陳愷建[7]立了基于多智能體系統(tǒng)(multi-agent system，MAS)的遙感衛(wèi)星分布式框架模型，并參考合同網(wǎng)協(xié)議，設(shè)計(jì)對地觀測任務(wù)的投標(biāo)模式，以此來實(shí)現(xiàn)遙感衛(wèi)星的任務(wù)分配。

綜合來看，傳統(tǒng)的集中式任務(wù)分配方法對于任務(wù)規(guī)模和需求都不變的靜態(tài)情況效果較好。而對于實(shí)際的系統(tǒng)而言，新任務(wù)的不斷加入是一種常態(tài)，這就需要一種適用于動(dòng)態(tài)情況下任務(wù)分配的規(guī)劃方法。分布式算法能夠比較好地解決這一問題，在時(shí)間維度內(nèi)實(shí)現(xiàn)多星的協(xié)同、交互，以在系統(tǒng)層面更好地利用資源。本文采用基于合同網(wǎng)絡(luò)算法的分布式任務(wù)分配方法，將遙感衛(wèi)星星座/星群中的每個(gè)成員看成合同網(wǎng)中的一個(gè)獨(dú)立的個(gè)體，既可以進(jìn)行任務(wù)拍賣，也可以進(jìn)行任務(wù)投標(biāo)。深入結(jié)合敏捷衛(wèi)星特點(diǎn)，以完成任務(wù)需求的總收益最高為目標(biāo)，綜合采用買賣、交換和置換3種合同類型，研究提出了一種適用于動(dòng)態(tài)情況的分布式任務(wù)協(xié)同分配方法。

1 分布式任務(wù)模型構(gòu)建

1.1 問題描述

多星多任務(wù)分配和協(xié)同應(yīng)用如圖1所示，由于分布式衛(wèi)星規(guī)模龐大、種類繁多，因此面向這類分布式衛(wèi)星的多星多任務(wù)規(guī)劃屬于NP難問題。多星多任務(wù)分配即通過構(gòu)建分布式衛(wèi)星模型(用于描述衛(wèi)星在軌運(yùn)行狀態(tài)及執(zhí)行任務(wù)的相關(guān)約束條件)，構(gòu)建任務(wù)模型(用于描述任務(wù)的相關(guān)需求)，設(shè)計(jì)算法和策略，建立衛(wèi)星空間和任務(wù)空間兩者之間的映射關(guān)系，最終使得分布式衛(wèi)星的系統(tǒng)任務(wù)規(guī)劃問題得到解決得一個(gè)過程。

圖1 多星多任務(wù)分配和協(xié)同應(yīng)用場景Fig.1 Scenario of tasks allocation and collaboration of multi-satellites

為便于規(guī)劃，通常衛(wèi)星對任務(wù)的開始執(zhí)行之間取可見窗的最左側(cè)。但當(dāng)同一衛(wèi)星同時(shí)對2個(gè)任務(wù)可見，且可見窗有重疊部分時(shí)，則不能直接取左側(cè)可見窗左側(cè)為任務(wù)的開始執(zhí)行時(shí)間。圖2給出了當(dāng)可見窗發(fā)生沖突時(shí)的解決方案，這種情況下，在可見窗滿足要求的情況下，考慮任務(wù)間的轉(zhuǎn)換時(shí)間，將下一任務(wù)順序后移即可。

圖2 可見窗沖突解決方案示意Fig.2 Solution to solve conflict of tow visible windows

1.2 任務(wù)收益計(jì)算

由于任務(wù)的優(yōu)先級不同，收益的大小也不同，傳統(tǒng)的收益函數(shù)只考慮收益總和，即：

(1)

(2)

圖3 收益懲罰函數(shù)示意Fig.3 The gain and punishment function

應(yīng)用收益懲罰函數(shù)后的任務(wù)收益函數(shù)為：

(3)

2 基于合同網(wǎng)的分布式任務(wù)規(guī)劃與調(diào)度

傳統(tǒng)的集中式任務(wù)分配對于靜態(tài)任務(wù)集合，也就是任務(wù)規(guī)模和范圍都不變的情況下，效果較好。而真實(shí)的衛(wèi)星星座/星群任務(wù)調(diào)度過程中，經(jīng)常會(huì)有新任務(wù)的加入。這就需要一種新型的任務(wù)規(guī)劃模式，既能對靜態(tài)任務(wù)集合進(jìn)行分配，也能在任務(wù)集合動(dòng)態(tài)變化情況下進(jìn)行分配。因此本文引進(jìn)合同網(wǎng)的方法，將其應(yīng)用到分布式任務(wù)分配中，綜合采用買賣合同、交換合同、置換合同這3種合同處理方式，來建立任務(wù)優(yōu)化分配算法[9-10]。

2.1 合同網(wǎng)算法模型

合同網(wǎng)算法以分布式方式處理多星任務(wù)協(xié)商、認(rèn)領(lǐng)、分配和規(guī)劃等操作。合同網(wǎng)協(xié)商所需數(shù)據(jù)由星間鏈路實(shí)現(xiàn)，合同網(wǎng)協(xié)議按照招標(biāo)、投標(biāo)、評標(biāo)、交換、買賣和置換等方式，基于星間鏈路迭代完成。合同網(wǎng)算法的任務(wù)分配模型如圖4所示。

圖4 合同網(wǎng)算法的任務(wù)協(xié)商示意Fig.4 Tasks collaboration model of contract net algorithm

本文設(shè)計(jì)了遙感衛(wèi)星的合同網(wǎng)收益模型、多星合同網(wǎng)算法模型及仿真驗(yàn)證?；诤贤W(wǎng)的星群任務(wù)規(guī)劃招投標(biāo)系統(tǒng)的工作流程為：

1) 地面或主星收集用戶的任務(wù)需求，形成招標(biāo)書，并發(fā)放給作為投標(biāo)方的衛(wèi)星；

2) 用戶作為投標(biāo)方比對自身資源和任務(wù)信息，在滿足基本要求的前提下填寫標(biāo)書；

3) 地面或主星作為招標(biāo)方，收集所有標(biāo)書后，對其進(jìn)行評估，擇選最優(yōu)方案完成招標(biāo)過程。

2.2 任務(wù)優(yōu)化分配算法

1) 基于買賣合同的任務(wù)分配。

(4)

(5)

(6)

2) 基于交換合同的任務(wù)分配。

(7)

衛(wèi)星接受到標(biāo)書后，首先計(jì)算該交換實(shí)現(xiàn)后自己的效能變化：

(8)

接下來判斷交換實(shí)現(xiàn)后系統(tǒng)整體效能的變化：

(9)

3) 基于置換合同的任務(wù)分配

(10)

置換過程發(fā)生后系統(tǒng)整體效能的變化：

(11)

2.3 任務(wù)投標(biāo)流程方法

在衛(wèi)星進(jìn)行任務(wù)投標(biāo)前，首先執(zhí)行以下步驟：

1)可見時(shí)間窗的計(jì)算。

2)確定任務(wù)執(zhí)行時(shí)間。

對滿足以上時(shí)間約束的時(shí)間窗口集合，按照時(shí)間順序選擇一個(gè)時(shí)間窗口，按照以下步驟判斷是否能夠執(zhí)行任務(wù)，如不能則改換下一順位時(shí)間窗口，迭代進(jìn)行，直至得出能夠執(zhí)行任務(wù)或不能執(zhí)行任務(wù)的結(jié)論。

①準(zhǔn)備時(shí)間計(jì)算。首先根據(jù)衛(wèi)星當(dāng)前姿態(tài)，以及即將執(zhí)行任務(wù)的星體姿態(tài)角Gm,n，判斷衛(wèi)星是否需要進(jìn)行姿態(tài)機(jī)動(dòng)，計(jì)算姿態(tài)機(jī)動(dòng)所需時(shí)間tturn，即準(zhǔn)備時(shí)間。

②時(shí)間約束檢驗(yàn)。提取前一觀測任務(wù)的結(jié)束時(shí)間，判斷在前一觀測任務(wù)結(jié)束后，若要完成姿態(tài)機(jī)動(dòng)開始當(dāng)前任務(wù)，當(dāng)前任務(wù)的開始時(shí)間和結(jié)束時(shí)間是否依然滿足可見時(shí)間窗的要求。

(12)

CR=TD×β

(13)

CE

(14)

CR

(15)

式中：CE為執(zhí)行姿態(tài)機(jī)動(dòng)動(dòng)作消耗能量；λ為姿態(tài)機(jī)動(dòng)消耗能量系數(shù)；CR為執(zhí)行觀測任務(wù)占用存儲空間；β為存儲圖像占用存儲空間系數(shù)。

分布式的任務(wù)規(guī)劃流程如圖5所示。

圖5 任務(wù)規(guī)劃流程Fig.5 Flow chart of mission planning based on contract algorithm

3 仿真驗(yàn)證及結(jié)果分析

為了對本文采用的方法進(jìn)行驗(yàn)證，進(jìn)行3個(gè)算例的仿真。算例1對4顆衛(wèi)星10個(gè)任務(wù)的分配進(jìn)行規(guī)劃；算例2對7顆衛(wèi)星50個(gè)任務(wù)的分配進(jìn)行規(guī)劃；算例3對7顆衛(wèi)星500個(gè)任務(wù)的分配進(jìn)行規(guī)劃。3個(gè)算例均選用敏捷衛(wèi)星進(jìn)行驗(yàn)證，即任務(wù)的執(zhí)行窗口可以在可見窗內(nèi)進(jìn)行前后移動(dòng)。

算例1的衛(wèi)星軌道信息見表1。

表1 衛(wèi)星軌道信息Table 1 Satellite orbit information

為了得到收益情況，選取10個(gè)任務(wù)，分別賦予它們不同的時(shí)間屬性及優(yōu)先級屬性。時(shí)間屬性以系統(tǒng)開始運(yùn)行時(shí)間為0開始，單位為h。優(yōu)先級分為1～5級，1級最高。任務(wù)發(fā)布時(shí)間有先有后，用于模擬實(shí)際任務(wù)需求產(chǎn)生過程的動(dòng)態(tài)特征。

使用以上仿真參數(shù)，對買賣合同模式、買賣合同與交換合同結(jié)合模式以及本文提出的合同網(wǎng)任務(wù)規(guī)劃模式分別仿真，得到算例1結(jié)果如圖6所示。

圖6 4星算例仿真結(jié)果Fig.6 The simulation results of the 4-satellites case

從結(jié)果可以看出，任務(wù)作為合同在星間被交互、買賣的次數(shù)越多，任務(wù)在星間被分配的“合理程度”會(huì)越來越高，表現(xiàn)為隨著買賣次數(shù)的增加，任務(wù)分配結(jié)果總收益越來越高。相比于其他算法，本文提出算法具有顯著的收益優(yōu)勢，表明在相同的合同買賣次數(shù)下，采用本文算法能夠?qū)崿F(xiàn)任務(wù)的更合理的分配。仿真結(jié)果證實(shí)了本文提出的基于合同網(wǎng)的分布式遙感衛(wèi)星任務(wù)規(guī)劃方案是有效的。

算例2采用7顆衛(wèi)星，任務(wù)數(shù)量設(shè)定為50。軌道參數(shù)如表2所示，觀測任務(wù)位置如圖7所示。

表2 衛(wèi)星軌道信息Table 2 Satellites orbit information

圖7 50個(gè)任務(wù)位置圖Fig.7 Positions of 50 tasks

算例2的規(guī)劃結(jié)果如圖8所示。從圖中可以看出，本文提出的算法能夠?qū)⑷蝿?wù)均勻地分配給7顆衛(wèi)星，分配效果良好。

圖8 50個(gè)任務(wù)分配結(jié)果Fig.8 50 tasks allocation results among satellites

算例2在驗(yàn)證規(guī)劃算法的同時(shí)，對算法的規(guī)劃效率進(jìn)行了驗(yàn)證，對不同場景下的規(guī)劃時(shí)間進(jìn)行了統(tǒng)計(jì)，結(jié)果如圖9所示。從圖中可以看出，衛(wèi)星數(shù)目和任務(wù)數(shù)目決定了任務(wù)分配過程耗時(shí)。

圖9 時(shí)間變化曲線Fig.9 Tasks allocation results among satellites

算例3在算例2的基礎(chǔ)上，對500個(gè)任務(wù)進(jìn)行分配，測試了本文算法針對大規(guī)模任務(wù)集合的分配情況，分配結(jié)果如圖10所示。

從圖10中可以看出，本文所設(shè)計(jì)的算法在解決大規(guī)模任務(wù)分配問題時(shí)，依然能夠得到一個(gè)滿足約束條件的可行解。說明所設(shè)計(jì)的算法是可行且有效的。

圖10 500個(gè)任務(wù)分配結(jié)果Fig.10 500 tasks′ allocation results among satellites

4 結(jié)論

1) 隨著合同網(wǎng)絡(luò)中合同拍賣次數(shù)的增加，本文算法和經(jīng)典合同網(wǎng)算法的總收益指數(shù)均呈上升趨勢。本文算法較經(jīng)典合同網(wǎng)算法有5%～10%的收益增加，表現(xiàn)出了更優(yōu)的分配性能。

2) 多星多任務(wù)仿真結(jié)果可以看出，在任務(wù)位置可見的情況下，各觀測任務(wù)較均勻的分配到了衛(wèi)星上，取得了較好的任務(wù)規(guī)劃效果。

3) 任務(wù)分配算法運(yùn)行時(shí)間隨衛(wèi)星數(shù)量和任務(wù)數(shù)量增加呈線性增長趨勢，能夠適應(yīng)未來大規(guī)模星群任務(wù)分配需求。