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

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

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

文章編號(hào)：１００３－３１１４（２０２４）０３－０５４８－０７

０ 引言

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

衛(wèi)星任務(wù)規(guī)劃問題作為非確定性問題之一，若采用傳統(tǒng)的全排列算法進(jìn)行問題求解，在大規(guī)模的任務(wù)規(guī)劃過程中，會(huì)導(dǎo)致組合數(shù)量指數(shù)級(jí)增長，特別是低軌衛(wèi)星星座中由于任務(wù)需求數(shù)量的大幅增長，進(jìn)而導(dǎo)致時(shí)間復(fù)雜度和空間復(fù)雜度的驟增，不具備實(shí)際應(yīng)用價(jià)值。由于可以把衛(wèi)星通信任務(wù)規(guī)劃問題作為一種組合優(yōu)化問題，其目標(biāo)是在一定的約束條件下求解目標(biāo)的局部最優(yōu)值［４－６］，而當(dāng)前的組合優(yōu)化問題的研究中，裝箱問題、加工調(diào)度問題、聚類問題、旅行商問題以及圖著色問題等都是典型的應(yīng)用場(chǎ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)變。同時(shí)，相比高軌衛(wèi)星中的任務(wù)規(guī)劃需求，低軌衛(wèi)星中的任務(wù)規(guī)劃需求對(duì)規(guī)劃方法的運(yùn)行效率要求更高。因此，無論在任務(wù)規(guī)劃方法的創(chuàng)新角度還是實(shí)際工程應(yīng)用角度，設(shè)計(jì)出更加高效適用的方法是解決低軌衛(wèi)星星座場(chǎng)景下任務(wù)規(guī)劃問題所必須實(shí)現(xiàn)的。為解決上述問題，本文通過研究ＰＳＯ 算法在低軌星座任務(wù)規(guī)劃問題下的參數(shù)優(yōu)化，設(shè)計(jì)了慣性權(quán)值、社會(huì)和自我學(xué)習(xí)因子的優(yōu)化方式，引入了最優(yōu)近鄰搜索，通過最優(yōu)粒子間的差分值來促進(jìn)局部搜索，獲得最優(yōu)鄰域搜索ＰＳＯ 算法，以高效求解低軌衛(wèi)星通信系統(tǒng)中多個(gè)衛(wèi)星轉(zhuǎn)發(fā)器資源池與多個(gè)任務(wù)規(guī)劃的組合優(yōu)化問題，并通過將實(shí)現(xiàn)的算法與其他相關(guān)算法進(jìn)行比較，驗(yàn)證了本文方法的有效性。

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

１． １ 問題分析和建模

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

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

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

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