加權負載均衡合同網大規模星座任務分配方法

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

1.北京理工大學宇航學院,北京 100081 2.深空自主導航與控制工業和信息化部重點實驗室,北京 100081

0 引言

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

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

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

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

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

1 問題提出與描述

1.1 問題提出

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

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

為方便問題求解,對問題做如下假設:1)星座內所有衛星存在穩定的星間通信鏈路,且可以忽略通信延遲;2)在整個任務期間,衛星不進行軌道機動。

1.2 問題描述

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

S={s1,s2,…sNS}:表示衛星集合;

tij={lij,dij,cij}:表示任務相關信息。

其中:lij為衛星sj對任務ti進行觀測的時間窗口開始前的等待時間;dij為衛星sj對任務ti進行觀測的時間窗口的持續時間;cij是衛星是否參與任務投標的控制位。默認為1,表示衛星sj可以參與任務ti的投標,若該控制位為0,則不參與。

任務分配的原則是所有衛星執行任務的收益之和最大化,目標函數如下:

(1)

式中:tv為星座執行所有任務的收益值之和,xij表示任務ti是否被衛星sj執行的變量。當任務ti被衛星sj執行時,xij=1,否則xij=0;al為任務窗口開始前的等待時間的收益權重;ad為觀測窗口質量的收益權重;ab為負載均衡系數。

任務約束條件如下:

(2)

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

u,v∈T,j∈S

(3)

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

任務分配問題的特點是衛星數量與任務數增加后,解空間大小會大幅增加,采用傳統方法進行求解時計算量過大,難以實現衛星在軌求解。同時,現有分布式衛星系統規模較小,任務分配時較少考慮到系統負載均衡性問題,在大規模星座中應用時,可能導致衛星負載不均衡,影響系統性能。針對上述問題,設計了一種考慮負載均衡的合同網目標分配算法。

2 加權負載均衡合同網任務分配

合同網算法用于分布式問題求解的高級通訊和控制協議,是分布式多智能體系統中采用最為廣泛的控制結構[25]。合同網算法機制簡單,不依賴個體間大量迭代交互,適用于解決大規模分布式問題。現有的衛星任務分配方法由于問題規模較小,較少考慮任務分配過程中導致的負載不均衡問題,在大規模星座的分配問題中可能導致星座中部分衛星任務過飽和。為了求解大規模星座任務分配問題,在分析問題特點的基礎上,設計了添加負載均衡系數的合同網分配方法,采用窗口篩選策略減小問題的解空間,并在合同網算法中加入負載均衡系數,改進了傳統算法在大規模星座和大規模任務情況下的分配效率和分配效果。

2.1 窗口篩選策略

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

衛星sj對任務ti進行觀測的時間窗口開始前的等待時間lij是對地觀測任務分配的重要指標。受衛星攜帶推進劑的數量和軌道運動規律限制,衛星在執行絕大多數觀測任務時,不會進行軌道機動。在完成任務規劃后,需要等待衛星運行至可見觀測窗口時進行觀測。等待時間越長,衛星所獲得的觀測數據時效性越差。

在衛星觀測窗口篩選過程中,設置閾值lt進行過濾。將lij過大的任務窗口的控制變量cij置0,剔除延遲時間較長的觀測窗口,衛星將不會參與后續的收益計算與招投標程序,表示如下:

(4)

在進行篩選后,可以有效減少參與后續步驟的衛星數量,同時縮短衛星軌道遞推和窗口計算需要前推的時長,節省星上計算資源和星間通信資源。

如圖1所示,衛星在對地觀測過程中相機可見范圍為以當前時刻星下點為圓心的圓,隨著衛星的移動,相機的可見范圍為以星下點軌跡為中心線的條帶狀區域。因此,對于地面固定點目標,衛星可見目標的星下點范圍是以目標為圓心的圓,衛星的星下點軌跡在目標附近可近似為圓的割線。由于衛星在圓軌道上勻速運行時星下點沿星下點軌跡勻速運動,由幾何關系可知,當衛星星下點軌跡穿過目標時,衛星從目標正上方飛過,觀測角度垂直于地面,觀測清晰度最高,觀測窗口持續時間最長,衛星所需要進行的姿態機動幅度最小,可視為最優觀測窗口。因此,衛星對目標的觀測窗口持續時間越長,窗口質量越好。

圖1 衛星觀測可見范圍示意圖

在衛星觀測窗口篩選過程中,設置閾值dt進行過濾,剔除窗口持續時間較短的觀測窗口:

(5)

采用閾值篩選方法可以在任務中根據實際需要靈活調整閾值lt和dt,以便適應系統運行過程中不同的需求。篩選可以有效減少參與后續步驟的衛星數量,同時保證任務快速響應和任務執行質量,減少衛星姿態調整角度,節省星上資源和星間通信資源。

2.2 加權負載均衡合同網任務分配

合同網算法適用于分布式多智能體任務分配問題,通過招標-投標-中標的市場機制實現任務分配,具有分布性、自主性[8]。加權負載均衡合同網任務分配方法在傳統合同網的分配機制的投標基礎上,加入負載均衡系數,在招投標過程中對中標有多個任務的衛星進行任務收益懲罰,傾向于將任務分配給目前中標任務數量較少的衛星,避免單個衛星中標任務數量過多,導致系統負載過于集中。相比傳統合同網算法,可以在不增加系統迭代次數的情況下,改善分配結果的負載均衡性。使用加權負載均衡合同網分配算法進行自主任務分配,流程如圖2所示:

圖2 合同網任務分配流程圖

分配過程主要分為以下3個步驟:

1) 在任務預處理過程中進行窗口計算和窗口篩選后,若某衛星對某任務擁有符合篩選條件的觀測窗口,則計算衛星執行當前任務的收益值,得到的收益值作為投標值,參與該任務的投標。

在衛星觀測收益評估過程中,采用負權重系數與任務窗口等待時間相乘,計入任務收益;采用正權重系數與任務窗口持續時間相乘,計入任務收益為:

(6)

此外,考慮到部分衛星可能在分配過程中被分配到過多任務,而部分衛星沒有被分配到任務,導致系統中不同衛星任務負載不均衡,影響系統性能。在合同網算法的投標值計算過程中,加入負載均衡加權系數,對已經中標有任務的衛星,在進行新的任務投標值計算時,按照負載均衡系數進行收益懲罰,扣除部分收益值,減少衛星重復中標,收益計算方式為:

(7)

2) 在所有擁有符合要求的觀測窗口的衛星執行投標后,各衛星對收到的每個任務的投標值分別進行排序,每個任務由投標值最高的衛星作為中標衛星。遍歷所有的任務后,得到任務分配初始的結果。

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

3 仿真實驗與分析

3.1 實驗參數

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

表1 仿真參數信息

3.2 實驗結果與對比

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

從圖4可以看出,由于對地觀測資源較為充足,所有的任務都可以較快地得到衛星分配并達到較好的執行效果,因此3種算法的收益基本相當。本文提出的加權負載均衡合同網分配算法的分配結果在所有情況下都略優于混合整數規劃算法,并且隨著任務規模的增加,任務平均收益差距有擴大的趨勢。

圖4 任務平均收益對比

從圖5可以看出,采用窗口篩選方式對任務進行預處理后,可以顯著減少每個任務參與投標的衛星總數,有效減少在軌計算資源與通信資源消耗。

圖5 窗口篩選前后參與投標衛星數對比

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

圖6 任務觀測分配消耗時間對比

如表2和圖7所示,通過對比任務分配結果中中標任務數量最多的衛星和衛星執行任務數量的標準差,可以看出,2種集中式分配算法的分配結果基本相同。合同網算法通過衛星之間的信息交互與迭代優化,可以得到更均衡的分配方案。隨著任務規模的進一步增加,加權負載均衡合同網算法與其他2種算法的差距有進一步擴大的趨勢。

圖7 衛星執行任務數量的標準差對比

4 結論

研究了大規模星座的任務分配問題。根據問題相關特點,提出了一種加權負載均衡合同網觀測任務分配方法,設計了適用于大規模星座和大規模任務的任務收益評估與觀測窗口篩選方法,并在多星合同網分配中考慮加權負載均衡。仿真表明,加權負載均衡合同網任務分配算法可以高效解決大規模星座的任務分配問題,任務收益與傳統算法基本相當,并達到良好的負載均衡效果。