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

關(guān)鍵詞：任務(wù)規(guī)劃；粒子群優(yōu)化；啟發(fā)式算法；最優(yōu)鄰域搜索；低軌衛(wèi)星通信

中圖分類號：ＴＮ９２７ 文獻(xiàn)標(biāo)志碼：Ａ 開放科學(xué)（資源服務(wù)）標(biāo)識碼（ＯＳＩＤ）：

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

０ 引言

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

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

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

１ 最優(yōu)鄰域搜索ＰＳＯ 的衛(wèi)星任務(wù)規(guī)劃方法

１． １ 問題分析和建模

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

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

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

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