加權(quán)負(fù)載均衡合同網(wǎng)大規(guī)模星座任務(wù)分配方法

王朝輝,徐 瑞,李朝玉,王 棒

1.北京理工大學(xué)宇航學(xué)院,北京 100081 2.深空自主導(dǎo)航與控制工業(yè)和信息化部重點(diǎn)實(shí)驗(yàn)室,北京 100081

0 引言

隨著航天運(yùn)載能力的進(jìn)步和小衛(wèi)星批量化生產(chǎn)測試技術(shù)的成熟,使用分布式小衛(wèi)星星座替代傳統(tǒng)大型衛(wèi)星逐漸成為主要發(fā)展方向。低軌道大規(guī)模星座衛(wèi)星密度大,對地覆蓋率高,通信時(shí)延低,重訪周期短,相比傳統(tǒng)高軌道衛(wèi)星在遙感和通信領(lǐng)域具有巨大優(yōu)勢。在商業(yè)航天市場上,由多達(dá)數(shù)百顆甚至上萬顆運(yùn)行在低軌道的衛(wèi)星組成的大規(guī)模星座是當(dāng)前各航天大國的競爭熱點(diǎn)。但隨著星座在軌衛(wèi)星數(shù)量的增加和衛(wèi)星載荷靈活性的提升,星座調(diào)度與任務(wù)規(guī)劃的求解復(fù)雜度也急劇增加[1-2]。傳統(tǒng)的地面站集中式衛(wèi)星任務(wù)規(guī)劃模式無法適應(yīng)高靈活、快響應(yīng)的大規(guī)模星座任務(wù)規(guī)劃需求[3]。采用星上自主分布式任務(wù)分配可以顯著提高星座的快速響應(yīng)能力和系統(tǒng)自主性。

在通信領(lǐng)域,美國SpaceX公司建設(shè)的“Starlink”星座已完成4200顆衛(wèi)星部署,擁有超過100萬活躍用戶;英國OneWeb公司建設(shè)的“OneWeb”星座已完成618顆衛(wèi)星的發(fā)射,初步完成一期組網(wǎng)目標(biāo),即將形成全球服務(wù)能力。在遙感領(lǐng)域,美國Planet公司建設(shè)的“Dove”星座已發(fā)射超過450顆衛(wèi)星,并保持200顆以上的衛(wèi)星在軌運(yùn)行,每天可以獲取超過3億平方公里的地面遙感圖像;我國長光衛(wèi)星公司建設(shè)的“吉林一號(hào)”星座現(xiàn)有72顆衛(wèi)星在軌運(yùn)行,可實(shí)現(xiàn)全球任意地點(diǎn)單日重訪23～25次,最快可在15 min內(nèi)完成一次全流程應(yīng)急觀測。在軍用領(lǐng)域,美國國防部太空發(fā)展局于2019年提出了國防太空架構(gòu)(NDSA),計(jì)劃由數(shù)百顆小型衛(wèi)星組成靈活、彈性、敏捷的系統(tǒng),執(zhí)行數(shù)據(jù)通信、預(yù)警、戰(zhàn)斗管理、導(dǎo)航、地面支持和太空威懾等任務(wù)[4]。

隨著星座在軌衛(wèi)星數(shù)量的增加和遙感衛(wèi)星觀測靈活性的提升,分配問題求解空間大幅增大,問題約束進(jìn)一步復(fù)雜化,導(dǎo)致星座對地觀測任務(wù)分配的求解復(fù)雜度也急劇增加[2]。傳統(tǒng)衛(wèi)星調(diào)度模式中,衛(wèi)星對地面目標(biāo)觀測任務(wù)首先需要在地面控制中心解算并生成指令,通過測控站將指令上注至衛(wèi)星,衛(wèi)星接收指令后按指令進(jìn)行觀測并下傳觀測數(shù)據(jù)。在該模式下,衛(wèi)星只能在通過地面測控站的通信窗口內(nèi)接收指令上注,并在下一次經(jīng)過任務(wù)目標(biāo)時(shí)進(jìn)行觀測,任務(wù)執(zhí)行靈活性差,響應(yīng)時(shí)間長。隨著低軌星座中星間鏈路的普及以及星上計(jì)算處理能力的提升,采用星上自主分布式任務(wù)規(guī)劃可以實(shí)現(xiàn)系統(tǒng)對任務(wù)的實(shí)時(shí)響應(yīng),自主計(jì)算并分配觀測窗口,減輕地面測控站和系統(tǒng)中各星的計(jì)算負(fù)載,減少部分衛(wèi)星失效對整個(gè)系統(tǒng)的影響,有效提升星座的快速響應(yīng)能力和資源利用率。

衛(wèi)星自主任務(wù)規(guī)劃問題已經(jīng)受到了廣泛關(guān)注,并已在部分任務(wù)中實(shí)際應(yīng)用。2000年NASA發(fā)射的地球觀測-1號(hào)衛(wèi)星(EO-1)使用自主規(guī)劃軟件,大幅度提高了衛(wèi)星的響應(yīng)速度,并隨后與陸地衛(wèi)星-7號(hào)(Landsat-7)首次進(jìn)行了衛(wèi)星分布式協(xié)同的相關(guān)驗(yàn)證[5-6]。張正強(qiáng)等建立了分層分布式多Agent結(jié)構(gòu),設(shè)計(jì)了優(yōu)先級任務(wù)選擇策略和動(dòng)態(tài)插入方法[7]。高黎等對分布式衛(wèi)星系統(tǒng)(DSS)任務(wù)優(yōu)化分配問題進(jìn)行了分析,將其轉(zhuǎn)化為集覆蓋問題,設(shè)計(jì)了基于合同網(wǎng)的嚴(yán)格啟發(fā)式優(yōu)化算法[8]。王沖等采用松耦合異步業(yè)務(wù)總線和基于自治的協(xié)同任務(wù)規(guī)劃算法,實(shí)現(xiàn)了系統(tǒng)可擴(kuò)展性,在此基礎(chǔ)上設(shè)計(jì)了基于多智能體合作協(xié)同進(jìn)化的多星協(xié)同任務(wù)規(guī)劃方法[9-11]。龐中華針對移動(dòng)目標(biāo)、高低軌協(xié)同觀測等問題設(shè)計(jì)了高軌衛(wèi)星離線任務(wù)規(guī)劃算法和低軌分布式在線規(guī)劃算法[12]。Jiang等針對協(xié)同觀測任務(wù)建立了網(wǎng)絡(luò)化協(xié)同任務(wù)規(guī)劃模型,并設(shè)計(jì)了改進(jìn)遺傳算法,提高了收斂性能[13]。薛志家等建立了綜合考慮平臺(tái)和載荷約束的模型,并針對突發(fā)任務(wù)設(shè)計(jì)了啟發(fā)式自主任務(wù)規(guī)劃算法[14]。Li等針對通信受限情況下的DSS系統(tǒng)對突發(fā)目標(biāo)進(jìn)行觀測,設(shè)計(jì)了單顆衛(wèi)星的在線調(diào)度算法和基于合同網(wǎng)的協(xié)調(diào)算法[15-16]。Wang等將深度強(qiáng)化學(xué)習(xí)方法引入觀測調(diào)度問題求解,通過訓(xùn)練神經(jīng)網(wǎng)絡(luò)來執(zhí)行調(diào)度任務(wù)[17]。Du等設(shè)計(jì)了任務(wù)聚類方法對集群目標(biāo)進(jìn)行預(yù)處理,并通過合同網(wǎng)方法進(jìn)行二次分配,對失敗任務(wù)進(jìn)行重新插入,改善了集中式多Agent系統(tǒng)的靈活性問題[18]。甘嵐等針對機(jī)動(dòng)星座對多個(gè)區(qū)域目標(biāo)的觀測任務(wù)規(guī)劃問題,設(shè)計(jì)了衛(wèi)星變軌策略、并給出了觀測策略,優(yōu)化了觀測總面積[19]。劉立昊設(shè)計(jì)了博弈協(xié)商機(jī)制求解都行分布式任務(wù)規(guī)劃,較好地解決了較大規(guī)模情況下求解時(shí)間長,收斂慢的問題[20]。王俊等基于多Agent方法提出了一種基于時(shí)間窗適應(yīng)的自主任務(wù)規(guī)劃啟發(fā)式算法[21]。高天旸等提出了一種分布式星座協(xié)同迭代優(yōu)化策略,在此基礎(chǔ)上設(shè)計(jì)了一種分布式協(xié)同進(jìn)化算法[22]。靳鵬等設(shè)計(jì)了一種可解約循環(huán)合同網(wǎng),減少了規(guī)劃過程的協(xié)商次數(shù),提出了一種自適應(yīng)退火算法求解分布式衛(wèi)星資源調(diào)度問題[23]。彭晨遠(yuǎn)等針對多星飛越巡察任務(wù)提出了一種窗口篩選計(jì)算模型和多約束任務(wù)規(guī)劃算法[24]。

在現(xiàn)有研究中,對星座的的分布式規(guī)劃問題進(jìn)行了部分討論,但是大規(guī)模星座在滿足任務(wù)完成率的前提下,需要進(jìn)一步提高系統(tǒng)響應(yīng)速度,改善規(guī)劃求解效果,現(xiàn)有文獻(xiàn)缺少對大規(guī)模星座自主任務(wù)分配問題的討論。本文針對大規(guī)模星座對地面固定點(diǎn)目標(biāo)觀測任務(wù)分配問題,建立了基于合同網(wǎng)協(xié)議的分布式任務(wù)分配模型;給出了適應(yīng)大規(guī)模星座的參與投標(biāo)衛(wèi)星篩選策略,提出了一種綜合考慮任務(wù)延遲時(shí)間和觀測窗口質(zhì)量的任務(wù)收益評估方法;使用基于加權(quán)負(fù)載均衡的合同網(wǎng)算法進(jìn)行任務(wù)分配。最后通過仿真驗(yàn)證了該算法對于大規(guī)模星座分布式觀測任務(wù)分配的高效性。

1 問題提出與描述

1.1 問題提出

以低軌對地遙感衛(wèi)星星座為例,描述星座自主任務(wù)分配問題。假設(shè)所有的衛(wèi)星都具有基本的自主定軌與軌道遞推能力;所有的衛(wèi)星都可以和星座內(nèi)的其他衛(wèi)星通過星間通信鏈路保持通信;衛(wèi)星搭載對地觀測載荷,在任務(wù)期間衛(wèi)星不進(jìn)行軌道機(jī)動(dòng),但可以通過姿態(tài)機(jī)動(dòng)觀測星下點(diǎn)周圍一定區(qū)域范圍內(nèi)的目標(biāo);衛(wèi)星具有一定的星載計(jì)算能力,可以根據(jù)當(dāng)前位置計(jì)算相應(yīng)目標(biāo)的觀測窗口,并評估窗口收益,同時(shí)可以對收到的其他衛(wèi)星的投標(biāo)信息進(jìn)行評估。

衛(wèi)星執(zhí)行任務(wù)的流程如下:首先由地面用戶向星座內(nèi)的任意一顆可通信的衛(wèi)星上傳任務(wù)目標(biāo)坐標(biāo),衛(wèi)星收到目標(biāo)坐標(biāo)后向星座內(nèi)其他衛(wèi)星發(fā)送任務(wù)目標(biāo)信息。在所有衛(wèi)星接收到任務(wù)目標(biāo)信息后,每顆衛(wèi)星根據(jù)當(dāng)前軌道數(shù)據(jù)計(jì)算軌道遞推和目標(biāo)觀測窗口。得到窗口后,星座開始任務(wù)招投標(biāo)流程,選定任意一顆衛(wèi)星作為招標(biāo)衛(wèi)星,用來負(fù)責(zé)收集所有衛(wèi)星的投標(biāo)值,并選定最終中標(biāo)衛(wèi)星。所有衛(wèi)星篩選自身計(jì)算所得的目標(biāo)觀測窗口,剔除不符合要求的窗口,對符合要求的窗口進(jìn)行任務(wù)收益計(jì)算,并向招標(biāo)衛(wèi)星發(fā)送自身的任務(wù)收益值進(jìn)行投標(biāo)。在收到所有衛(wèi)星的投標(biāo)后,招標(biāo)衛(wèi)星排序接收到的任務(wù)投標(biāo),選取收益值最高的衛(wèi)星作為中標(biāo)衛(wèi)星。在所有任務(wù)完成分配后,對所有任務(wù)的中標(biāo)收益值進(jìn)行排序,將收益較低的任務(wù)取消當(dāng)前中標(biāo)結(jié)果,并重新進(jìn)行招投標(biāo)流程,直到系統(tǒng)收益值穩(wěn)定不再發(fā)生變動(dòng)或達(dá)到迭代次數(shù)上限。

為方便問題求解,對問題做如下假設(shè):1)星座內(nèi)所有衛(wèi)星存在穩(wěn)定的星間通信鏈路,且可以忽略通信延遲;2)在整個(gè)任務(wù)期間,衛(wèi)星不進(jìn)行軌道機(jī)動(dòng)。

1.2 問題描述

T={t1,t2,…,tNT}:表示任務(wù)集合;

S={s1,s2,…sNS}:表示衛(wèi)星集合;

tij={lij,dij,cij}:表示任務(wù)相關(guān)信息。

其中:lij為衛(wèi)星sj對任務(wù)ti進(jìn)行觀測的時(shí)間窗口開始前的等待時(shí)間;dij為衛(wèi)星sj對任務(wù)ti進(jìn)行觀測的時(shí)間窗口的持續(xù)時(shí)間;cij是衛(wèi)星是否參與任務(wù)投標(biāo)的控制位。默認(rèn)為1,表示衛(wèi)星sj可以參與任務(wù)ti的投標(biāo),若該控制位為0,則不參與。

任務(wù)分配的原則是所有衛(wèi)星執(zhí)行任務(wù)的收益之和最大化,目標(biāo)函數(shù)如下:

(1)

式中:tv為星座執(zhí)行所有任務(wù)的收益值之和,xij表示任務(wù)ti是否被衛(wèi)星sj執(zhí)行的變量。當(dāng)任務(wù)ti被衛(wèi)星sj執(zhí)行時(shí),xij=1,否則xij=0;al為任務(wù)窗口開始前的等待時(shí)間的收益權(quán)重;ad為觀測窗口質(zhì)量的收益權(quán)重;ab為負(fù)載均衡系數(shù)。

任務(wù)約束條件如下:

(2)

xuj·xvj·(luj+duj-lvj)(lvj+dvj-luj)≤0,

u,v∈T,j∈S

(3)

其中:式(2)表示每個(gè)任務(wù)最多只由1顆衛(wèi)星執(zhí)行1次;式(3)表示任意1顆衛(wèi)星執(zhí)行2個(gè)不同任務(wù)時(shí)窗口不能互相重疊。

任務(wù)分配問題的特點(diǎn)是衛(wèi)星數(shù)量與任務(wù)數(shù)增加后,解空間大小會(huì)大幅增加,采用傳統(tǒng)方法進(jìn)行求解時(shí)計(jì)算量過大,難以實(shí)現(xiàn)衛(wèi)星在軌求解。同時(shí),現(xiàn)有分布式衛(wèi)星系統(tǒng)規(guī)模較小,任務(wù)分配時(shí)較少考慮到系統(tǒng)負(fù)載均衡性問題,在大規(guī)模星座中應(yīng)用時(shí),可能導(dǎo)致衛(wèi)星負(fù)載不均衡,影響系統(tǒng)性能。針對上述問題,設(shè)計(jì)了一種考慮負(fù)載均衡的合同網(wǎng)目標(biāo)分配算法。

2 加權(quán)負(fù)載均衡合同網(wǎng)任務(wù)分配

合同網(wǎng)算法用于分布式問題求解的高級通訊和控制協(xié)議,是分布式多智能體系統(tǒng)中采用最為廣泛的控制結(jié)構(gòu)[25]。合同網(wǎng)算法機(jī)制簡單,不依賴個(gè)體間大量迭代交互,適用于解決大規(guī)模分布式問題?，F(xiàn)有的衛(wèi)星任務(wù)分配方法由于問題規(guī)模較小,較少考慮任務(wù)分配過程中導(dǎo)致的負(fù)載不均衡問題,在大規(guī)模星座的分配問題中可能導(dǎo)致星座中部分衛(wèi)星任務(wù)過飽和。為了求解大規(guī)模星座任務(wù)分配問題,在分析問題特點(diǎn)的基礎(chǔ)上,設(shè)計(jì)了添加負(fù)載均衡系數(shù)的合同網(wǎng)分配方法,采用窗口篩選策略減小問題的解空間,并在合同網(wǎng)算法中加入負(fù)載均衡系數(shù),改進(jìn)了傳統(tǒng)算法在大規(guī)模星座和大規(guī)模任務(wù)情況下的分配效率和分配效果。

2.1 窗口篩選策略

相比現(xiàn)有的衛(wèi)星星座,大規(guī)模星座衛(wèi)星數(shù)量大幅提升,可用對地觀測資源大幅增加,觀測覆蓋率也隨著增加,因此大規(guī)模星座可以大幅減少等待目標(biāo)觀測窗口所需的時(shí)間。但資源的豐富導(dǎo)致任務(wù)分配問題的解空間增加,增加了求解所需的算力和時(shí)間。在使用合同網(wǎng)方法進(jìn)行任務(wù)分配前,利用任務(wù)窗口延遲和任務(wù)窗口時(shí)長對可用窗口進(jìn)行篩選,可以在保證任務(wù)分配效果的情況下,減少分配求解的計(jì)算量,提高系統(tǒng)任務(wù)分配的效率。

衛(wèi)星sj對任務(wù)ti進(jìn)行觀測的時(shí)間窗口開始前的等待時(shí)間lij是對地觀測任務(wù)分配的重要指標(biāo)。受衛(wèi)星攜帶推進(jìn)劑的數(shù)量和軌道運(yùn)動(dòng)規(guī)律限制,衛(wèi)星在執(zhí)行絕大多數(shù)觀測任務(wù)時(shí),不會(huì)進(jìn)行軌道機(jī)動(dòng)。在完成任務(wù)規(guī)劃后,需要等待衛(wèi)星運(yùn)行至可見觀測窗口時(shí)進(jìn)行觀測。等待時(shí)間越長,衛(wèi)星所獲得的觀測數(shù)據(jù)時(shí)效性越差。

在衛(wèi)星觀測窗口篩選過程中,設(shè)置閾值lt進(jìn)行過濾。將lij過大的任務(wù)窗口的控制變量cij置0,剔除延遲時(shí)間較長的觀測窗口,衛(wèi)星將不會(huì)參與后續(xù)的收益計(jì)算與招投標(biāo)程序,表示如下:

(4)

在進(jìn)行篩選后,可以有效減少參與后續(xù)步驟的衛(wèi)星數(shù)量,同時(shí)縮短衛(wèi)星軌道遞推和窗口計(jì)算需要前推的時(shí)長,節(jié)省星上計(jì)算資源和星間通信資源。

如圖1所示,衛(wèi)星在對地觀測過程中相機(jī)可見范圍為以當(dāng)前時(shí)刻星下點(diǎn)為圓心的圓,隨著衛(wèi)星的移動(dòng),相機(jī)的可見范圍為以星下點(diǎn)軌跡為中心線的條帶狀區(qū)域。因此,對于地面固定點(diǎn)目標(biāo),衛(wèi)星可見目標(biāo)的星下點(diǎn)范圍是以目標(biāo)為圓心的圓,衛(wèi)星的星下點(diǎn)軌跡在目標(biāo)附近可近似為圓的割線。由于衛(wèi)星在圓軌道上勻速運(yùn)行時(shí)星下點(diǎn)沿星下點(diǎn)軌跡勻速運(yùn)動(dòng),由幾何關(guān)系可知,當(dāng)衛(wèi)星星下點(diǎn)軌跡穿過目標(biāo)時(shí),衛(wèi)星從目標(biāo)正上方飛過,觀測角度垂直于地面,觀測清晰度最高,觀測窗口持續(xù)時(shí)間最長,衛(wèi)星所需要進(jìn)行的姿態(tài)機(jī)動(dòng)幅度最小,可視為最優(yōu)觀測窗口。因此,衛(wèi)星對目標(biāo)的觀測窗口持續(xù)時(shí)間越長,窗口質(zhì)量越好。

圖1 衛(wèi)星觀測可見范圍示意圖

在衛(wèi)星觀測窗口篩選過程中,設(shè)置閾值dt進(jìn)行過濾,剔除窗口持續(xù)時(shí)間較短的觀測窗口:

(5)

采用閾值篩選方法可以在任務(wù)中根據(jù)實(shí)際需要靈活調(diào)整閾值lt和dt,以便適應(yīng)系統(tǒng)運(yùn)行過程中不同的需求。篩選可以有效減少參與后續(xù)步驟的衛(wèi)星數(shù)量,同時(shí)保證任務(wù)快速響應(yīng)和任務(wù)執(zhí)行質(zhì)量,減少衛(wèi)星姿態(tài)調(diào)整角度,節(jié)省星上資源和星間通信資源。

2.2 加權(quán)負(fù)載均衡合同網(wǎng)任務(wù)分配

合同網(wǎng)算法適用于分布式多智能體任務(wù)分配問題,通過招標(biāo)-投標(biāo)-中標(biāo)的市場機(jī)制實(shí)現(xiàn)任務(wù)分配,具有分布性、自主性[8]。加權(quán)負(fù)載均衡合同網(wǎng)任務(wù)分配方法在傳統(tǒng)合同網(wǎng)的分配機(jī)制的投標(biāo)基礎(chǔ)上,加入負(fù)載均衡系數(shù),在招投標(biāo)過程中對中標(biāo)有多個(gè)任務(wù)的衛(wèi)星進(jìn)行任務(wù)收益懲罰,傾向于將任務(wù)分配給目前中標(biāo)任務(wù)數(shù)量較少的衛(wèi)星,避免單個(gè)衛(wèi)星中標(biāo)任務(wù)數(shù)量過多,導(dǎo)致系統(tǒng)負(fù)載過于集中。相比傳統(tǒng)合同網(wǎng)算法,可以在不增加系統(tǒng)迭代次數(shù)的情況下,改善分配結(jié)果的負(fù)載均衡性。使用加權(quán)負(fù)載均衡合同網(wǎng)分配算法進(jìn)行自主任務(wù)分配,流程如圖2所示:

圖2 合同網(wǎng)任務(wù)分配流程圖

分配過程主要分為以下3個(gè)步驟:

1) 在任務(wù)預(yù)處理過程中進(jìn)行窗口計(jì)算和窗口篩選后,若某衛(wèi)星對某任務(wù)擁有符合篩選條件的觀測窗口,則計(jì)算衛(wèi)星執(zhí)行當(dāng)前任務(wù)的收益值,得到的收益值作為投標(biāo)值,參與該任務(wù)的投標(biāo)。

在衛(wèi)星觀測收益評估過程中,采用負(fù)權(quán)重系數(shù)與任務(wù)窗口等待時(shí)間相乘,計(jì)入任務(wù)收益;采用正權(quán)重系數(shù)與任務(wù)窗口持續(xù)時(shí)間相乘,計(jì)入任務(wù)收益為:

(6)

此外,考慮到部分衛(wèi)星可能在分配過程中被分配到過多任務(wù),而部分衛(wèi)星沒有被分配到任務(wù),導(dǎo)致系統(tǒng)中不同衛(wèi)星任務(wù)負(fù)載不均衡,影響系統(tǒng)性能。在合同網(wǎng)算法的投標(biāo)值計(jì)算過程中,加入負(fù)載均衡加權(quán)系數(shù),對已經(jīng)中標(biāo)有任務(wù)的衛(wèi)星,在進(jìn)行新的任務(wù)投標(biāo)值計(jì)算時(shí),按照負(fù)載均衡系數(shù)進(jìn)行收益懲罰,扣除部分收益值,減少衛(wèi)星重復(fù)中標(biāo),收益計(jì)算方式為:

(7)

2) 在所有擁有符合要求的觀測窗口的衛(wèi)星執(zhí)行投標(biāo)后,各衛(wèi)星對收到的每個(gè)任務(wù)的投標(biāo)值分別進(jìn)行排序,每個(gè)任務(wù)由投標(biāo)值最高的衛(wèi)星作為中標(biāo)衛(wèi)星。遍歷所有的任務(wù)后,得到任務(wù)分配初始的結(jié)果。

3) 若滿足迭代優(yōu)化條件,將分配結(jié)果輸入迭代優(yōu)化模塊,使用貪婪算法迭代優(yōu)化分配結(jié)果。在每輪迭代優(yōu)化過程中,對分配完成的任務(wù)重新進(jìn)行帶有負(fù)載均衡懲罰的收益計(jì)算,篩選收益值較低的任務(wù),清除其分配結(jié)果,重新進(jìn)行招投標(biāo)過程,得到新的分配結(jié)果。判斷是否滿足迭代優(yōu)化條件,若滿足迭代優(yōu)化條件,進(jìn)入下一輪迭代;若不滿足迭代優(yōu)化條件,輸出最終分配結(jié)果。

3 仿真實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)參數(shù)

本節(jié)通過仿真實(shí)驗(yàn)驗(yàn)證所提方法。實(shí)驗(yàn)計(jì)算機(jī)配置為Intel(R) Core(TM) i7-10700 CPU @2.90 GHz。星座包括400顆低軌遙感衛(wèi)星,軌道高度為350 km,軌道傾角為75°,400顆衛(wèi)星分別部署在20個(gè)均勻分布的軌道面上,每個(gè)軌道面包含的20顆衛(wèi)星均勻分布。衛(wèi)星可以對以星地連線為中心,擺動(dòng)30°以內(nèi)的范圍進(jìn)行觀測。在地表隨機(jī)生成1000個(gè)固定點(diǎn)目標(biāo),如圖3所示。在仿真中,分別選取100、200、300、400、500、600、700、800、900和1000個(gè)目標(biāo),使用本文所提方法與傳統(tǒng)任務(wù)分配的經(jīng)典方法混合整數(shù)規(guī)劃算法、匈牙利算法進(jìn)行對比,表1列舉了仿真中的參數(shù)信息。

表1 仿真參數(shù)信息

3.2 實(shí)驗(yàn)結(jié)果與對比

針對10組測試算例,分別采用本文提出的方法、混合整數(shù)規(guī)劃算法和匈牙利算法進(jìn)行求解,分別比較任務(wù)收益、規(guī)劃耗時(shí)和負(fù)載均衡效果,驗(yàn)證本文所提出方法的有效性與合理性。

從圖4可以看出,由于對地觀測資源較為充足,所有的任務(wù)都可以較快地得到衛(wèi)星分配并達(dá)到較好的執(zhí)行效果,因此3種算法的收益基本相當(dāng)。本文提出的加權(quán)負(fù)載均衡合同網(wǎng)分配算法的分配結(jié)果在所有情況下都略優(yōu)于混合整數(shù)規(guī)劃算法,并且隨著任務(wù)規(guī)模的增加,任務(wù)平均收益差距有擴(kuò)大的趨勢。

圖4 任務(wù)平均收益對比

從圖5可以看出,采用窗口篩選方式對任務(wù)進(jìn)行預(yù)處理后,可以顯著減少每個(gè)任務(wù)參與投標(biāo)的衛(wèi)星總數(shù),有效減少在軌計(jì)算資源與通信資源消耗。

圖5 窗口篩選前后參與投標(biāo)衛(wèi)星數(shù)對比

如圖6所示,通過算法重復(fù)運(yùn)行100次并求運(yùn)行時(shí)間平均值可知,相比混合整數(shù)規(guī)劃和匈牙利算法的集中計(jì)算求解方式,合同網(wǎng)算法采用分布式計(jì)算,可以充分利用分布在各個(gè)衛(wèi)星上的計(jì)算資源,大幅度提高計(jì)算效率。加權(quán)負(fù)載均衡合同網(wǎng)算法比混合整數(shù)規(guī)劃算法可以減少94%以上的運(yùn)行時(shí)間,同時(shí)隨著任務(wù)規(guī)模增大,差距有進(jìn)一步擴(kuò)大的趨勢;比匈牙利算法可以減少99%以上的運(yùn)行時(shí)間。

圖6 任務(wù)觀測分配消耗時(shí)間對比

如表2和圖7所示,通過對比任務(wù)分配結(jié)果中中標(biāo)任務(wù)數(shù)量最多的衛(wèi)星和衛(wèi)星執(zhí)行任務(wù)數(shù)量的標(biāo)準(zhǔn)差,可以看出,2種集中式分配算法的分配結(jié)果基本相同。合同網(wǎng)算法通過衛(wèi)星之間的信息交互與迭代優(yōu)化,可以得到更均衡的分配方案。隨著任務(wù)規(guī)模的進(jìn)一步增加,加權(quán)負(fù)載均衡合同網(wǎng)算法與其他2種算法的差距有進(jìn)一步擴(kuò)大的趨勢。

圖7 衛(wèi)星執(zhí)行任務(wù)數(shù)量的標(biāo)準(zhǔn)差對比

4 結(jié)論

研究了大規(guī)模星座的任務(wù)分配問題。根據(jù)問題相關(guān)特點(diǎn),提出了一種加權(quán)負(fù)載均衡合同網(wǎng)觀測任務(wù)分配方法,設(shè)計(jì)了適用于大規(guī)模星座和大規(guī)模任務(wù)的任務(wù)收益評估與觀測窗口篩選方法,并在多星合同網(wǎng)分配中考慮加權(quán)負(fù)載均衡。仿真表明,加權(quán)負(fù)載均衡合同網(wǎng)任務(wù)分配算法可以高效解決大規(guī)模星座的任務(wù)分配問題,任務(wù)收益與傳統(tǒng)算法基本相當(dāng),并達(dá)到良好的負(fù)載均衡效果。