基于最優鄰域搜索粒子群的低軌衛星通信任務規劃方法

摘 要：針對低軌衛星通信中的任務規劃問題，提出了一種基于最優鄰域搜索粒子群優化（Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ，ＰＳＯ）群算法的任務規劃方法。引入最優近鄰搜索，通過最優粒子間的差分值來促進局部搜索，設計了慣性權值、社會和自我學習因子的優化方式，最終能夠高效求解低軌衛星通信星座中多轉發器與多任務的組合優化問題，用以應對低軌衛星過境時間限制和鏈路切換導致的時間段離散問題，并使得算法前期具有更強探索全局最優和后期快速收斂的能力。實驗驗證結果表明，該方法能夠在低軌衛星中的約束條件下，有效提高衛星平均資源占用率（Ａｖｅｒａｇｅ ＯｃｃｕｐａｎｃｙＰｅｒｃｅｎｔａｇｅ，ＡＯＰ）的同時減少算法收斂的迭代次數，顯著降低運行時間開銷。

關鍵詞：任務規劃；粒子群優化；啟發式算法；最優鄰域搜索；低軌衛星通信

中圖分類號：ＴＮ９２７ 文獻標志碼：Ａ 開放科學（資源服務）標識碼（ＯＳＩＤ）：

文章編號：１００３－３１１４（２０２４）０３－０５４８－０７

０ 引言

衛星通信任務規劃技術是指在通信衛星用戶保障任務與管控需求的驅動下，通過對任務與衛星資源的建模，消除多衛星任務執行過程中的資源沖突，最大化任務與資源效率的一種優化技術。衛星通信中的任務規劃問題是一種典型的非確定性問題，即該問題沒有確定的公式可以在確定的時間內求得最優解，而低軌衛星通信系統相比一般高軌衛星的“一星一系統”，可以通過星間組網的方式跨星使用轉發器資源。低軌衛星通信系統還需要應對過境時間限制和鏈路切換導致的時間段離散問題，因此低軌衛星的任務規劃問題相比高軌衛星任務規劃更加復雜［１－３］。

衛星任務規劃問題作為非確定性問題之一，若采用傳統的全排列算法進行問題求解，在大規模的任務規劃過程中，會導致組合數量指數級增長，特別是低軌衛星星座中由于任務需求數量的大幅增長，進而導致時間復雜度和空間復雜度的驟增，不具備實際應用價值。由于可以把衛星通信任務規劃問題作為一種組合優化問題，其目標是在一定的約束條件下求解目標的局部最優值［４－６］，而當前的組合優化問題的研究中，裝箱問題、加工調度問題、聚類問題、旅行商問題以及圖著色問題等都是典型的應用場景［７－８］，其求解組合優化問題的思路同樣適用于抽象建模后的低軌衛星通信任務規劃問題。目前研究衛星任務規劃問題的方法一般利用啟發式算法，如遺傳算法（Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ，ＧＡ）［９－１０］、粒子群優化（Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ，ＰＳＯ）算法［１０－１１］、模擬退火算法［１２］等。

隨著天地一體化信息網絡的發展，特別是低軌衛星星座的發展［１３－１４］，衛星通信的任務規劃問題由單星任務規劃向多星任務規劃轉變。同時，相比高軌衛星中的任務規劃需求，低軌衛星中的任務規劃需求對規劃方法的運行效率要求更高。因此，無論在任務規劃方法的創新角度還是實際工程應用角度，設計出更加高效適用的方法是解決低軌衛星星座場景下任務規劃問題所必須實現的。為解決上述問題，本文通過研究ＰＳＯ 算法在低軌星座任務規劃問題下的參數優化，設計了慣性權值、社會和自我學習因子的優化方式，引入了最優近鄰搜索，通過最優粒子間的差分值來促進局部搜索，獲得最優鄰域搜索ＰＳＯ 算法，以高效求解低軌衛星通信系統中多個衛星轉發器資源池與多個任務規劃的組合優化問題，并通過將實現的算法與其他相關算法進行比較，驗證了本文方法的有效性。

１ 最優鄰域搜索ＰＳＯ 的衛星任務規劃方法

１． １ 問題分析和建模

衛星通信系統中由于任務列表中各用戶提報上的任務需求不同，不同規劃方法下在有限的時間、帶寬和空間范圍內所占用的衛星轉發器資源不同，資源利用率也就不同。因此衛星任務規劃的目標是通過合理資源規劃方法，計算出一組最佳通信任務資源的排列方式，最大化資源利用率，同時盡可能的縮短任務規劃過程所需的時間。

隨著衛星通信任務需求規模的快速增長，傳統的按需分配與優先級分配已經不能滿足業務規模增長的需求，基于動態規劃的衛星任務規劃逐漸成為衛星通信資源規劃研究的重點。通信衛星資源動態規劃是指在不同衛星的不同時隙和帶寬資源條件下，為滿足用戶對資源的不同需求，對一定數量的通信衛星資源進行分配［４，１５］。時間和帶寬需求是通信系統任務具有的基本元素。其中，規劃算法的優劣取決于任務規劃規則的設計和優化算法的性能，合理的規劃規則有助于提高衛星資源利用率，降低整體的衛星通信任務完成時間。啟發式算法和傳統的運籌學算法是常用的資源規劃算法，在衛星任務規劃領域得到了諸多應用，并且以往的研究表明啟發式算法通常具有獨特的性能優勢。本文所研究的衛星任務規劃問題屬于組合優化問題，具備路徑規劃、資源規劃等基本特征，如“任務－資源”之間存在組合優化的關系、設有一定的約束條件、有明確的優化目標、不存在多項式時間解法等［９，１６］。

低軌衛星通信中的任務規劃過程如圖１ 所示。根據低軌衛星通信任務需求的特點，可以分析出其基本約束包括衛星轉發器約束、頻率約束和時間約束。面向任務的低軌衛星透明轉發器資源的動態規劃在一定的時間范圍和頻率范圍內通過有效地安排通信任務而實現［１７－１８］。其中，衛星轉發器約束為：① 同一任務需求不可同時分配至多個衛星轉發器；② 不同衛星的轉發器帶寬可以不同。時間約束為：① 任務需求的時間是固定的；② 任務所需時間范圍連續且不中斷；③ 任務存在最小起止時間和最晚結束時間；④ 低軌衛星星座中不同衛星轉發器的可用時間段不相同；⑤ 最晚結束時間與最小開始時間之差，必須大于或等于任務所需時間長度。頻率約束為：① 任務所需帶寬固定不變；② 任務所需的頻率范圍連續。

進一步根據上述描述，任務規劃中的任務列表可表征如下：衛星的單個任務描述可以表示為一個二維向量，不同維度分別代表單個任務所需的帶寬大小以及任務時長，任務規劃與調度中的任務列表是由多個任務構成的集合。多通信任務的排列方式可以通過二維坐標系的方法進行表征，在低軌衛星星座中的資源池中占用情況如圖２ 所示。