靜止軌道通信衛(wèi)星資源調(diào)度模型與算法研究

劉文文，熊 偉，韓 馳，駱 驍

(1.航天工程大學(xué) 信息學(xué)院，北京 101416；2.中國(guó)人民解放軍32039部隊(duì)，北京 102300)

0 引言

靜止軌道通信衛(wèi)星具有覆蓋面大、性能穩(wěn)定可靠、機(jī)動(dòng)靈活、不受地理?xiàng)l件限制和遠(yuǎn)距離通信成本低等優(yōu)點(diǎn)，在國(guó)際通信、國(guó)內(nèi)通信、軍事通信、移動(dòng)通信和廣播電視等領(lǐng)域發(fā)揮了重要的作用。

近年來(lái)，國(guó)家出臺(tái)多項(xiàng)政策措施鼓勵(lì)推動(dòng)衛(wèi)星在各行業(yè)的規(guī)模化應(yīng)用、商業(yè)化服務(wù)及國(guó)際化拓展，行業(yè)面臨重大的發(fā)展機(jī)遇及挑戰(zhàn)。面對(duì)多網(wǎng)系、多任務(wù)，且衛(wèi)星通信資源有限的現(xiàn)實(shí)情況，采用衛(wèi)星資源調(diào)度方法來(lái)分配資源成為解決任務(wù)與資源之間矛盾的主要方式[1-2]。

在靜止軌道通信衛(wèi)星調(diào)度研究的過(guò)程中，常用的調(diào)度模型包括數(shù)學(xué)規(guī)劃模型、約束滿(mǎn)足模型、圖論模型和車(chē)輛調(diào)度模型等[3-6]。數(shù)學(xué)規(guī)劃模型求解通信衛(wèi)星資源調(diào)度問(wèn)題時(shí)，會(huì)簡(jiǎn)化變量之間的關(guān)系，忽略問(wèn)題的非線(xiàn)性約束，采用的精確求解算法只適用于小規(guī)模的調(diào)度。圖論模型形式簡(jiǎn)單，理論基礎(chǔ)完善，可以在合理的時(shí)間內(nèi)求得衛(wèi)星資源調(diào)度問(wèn)題的解，但由于衛(wèi)星系統(tǒng)約束繁多，如何將所有約束恰當(dāng)?shù)乇碚鞯綀D中還是一個(gè)較難的問(wèn)題，其使用具有較大的局限性。約束滿(mǎn)足模型結(jié)構(gòu)層次清晰，能夠從變量值域、決策變量和約束條件為切入點(diǎn)對(duì)衛(wèi)星資源調(diào)度問(wèn)題展開(kāi)描述，能夠?qū)σ恍╇y以用數(shù)學(xué)語(yǔ)言描述的約束進(jìn)行描述，適用于較大規(guī)模調(diào)度問(wèn)題，應(yīng)用廣泛。

目前的研究在求解靜止軌道衛(wèi)星資源調(diào)度問(wèn)題時(shí)，為方便調(diào)度模型建立，會(huì)簡(jiǎn)化調(diào)度場(chǎng)景，有傾向性地建立約束條件，不同文章考慮的模型目標(biāo)和約束存在差異，且不全面。根據(jù)已有的模型，結(jié)合靜止軌道衛(wèi)星資源調(diào)度的特點(diǎn)，建立資源調(diào)度基礎(chǔ)框架，系統(tǒng)全面地梳理調(diào)度問(wèn)題存在的目標(biāo)和約束條件，構(gòu)建一種靜止軌道衛(wèi)星資源調(diào)度基礎(chǔ)模型，為該問(wèn)題的研究提供統(tǒng)一的范式，在為研究新的調(diào)度場(chǎng)景提供支撐的同時(shí)，提供問(wèn)題求解性能橫向比較的可能。

本文從靜止軌道衛(wèi)星資源調(diào)度問(wèn)題的根本出發(fā)，綜合考慮調(diào)度過(guò)程中涉及的各項(xiàng)因素，建立靜止軌道通信衛(wèi)星資源調(diào)度的基礎(chǔ)模型，形成問(wèn)題求解的完整框架，并結(jié)合智能優(yōu)化算法提高框架的求解效果。

1 靜止軌道通信衛(wèi)星資源調(diào)度分析

靜止軌道通信衛(wèi)星資源調(diào)度，從用戶(hù)的角度，是用戶(hù)需要組網(wǎng)通信時(shí)，向衛(wèi)星資源管理中心提交任務(wù)申請(qǐng)，衛(wèi)星資源管理中心根據(jù)任務(wù)需求為其分配符合要求的衛(wèi)星資源；從衛(wèi)星資源管理中心的角度，資源調(diào)度首先要梳理現(xiàn)有系統(tǒng)的資源池，整理可用資源列表，其次面對(duì)多任務(wù)申請(qǐng)，需要對(duì)所有任務(wù)需求進(jìn)行統(tǒng)一梳理、系統(tǒng)的分析，最后選擇合適的調(diào)度模型和算法進(jìn)行求解，形成調(diào)度方案，合理地為任務(wù)分配資源，同時(shí)保證衛(wèi)星資源使用的高效性和可沿用性。具體的調(diào)度流程如圖1所示。

圖1 通信衛(wèi)星資源調(diào)度流程Fig.1 Communication satellite resource scheduling process

隨著通信衛(wèi)星業(yè)務(wù)應(yīng)用不斷拓展，任務(wù)數(shù)量及任務(wù)對(duì)資源的需求量隨之增加，出現(xiàn)衛(wèi)星資源緊張甚至不足的情況，增加衛(wèi)星資源管理中心資源分配的難度和復(fù)雜度，形成了靜止軌道通信衛(wèi)星資源調(diào)度問(wèn)題。但無(wú)論調(diào)度場(chǎng)景如何變化，任務(wù)需求如何多樣，靜止軌道通信衛(wèi)星資源調(diào)度最根本的問(wèn)題是任務(wù)之間的沖突及任務(wù)與衛(wèi)星資源之間的矛盾。因此，求解靜止軌道通信衛(wèi)星資源調(diào)度問(wèn)題從這個(gè)根本問(wèn)題出發(fā)，系統(tǒng)梳理衛(wèi)星資源、任務(wù)需求及調(diào)度過(guò)程中的約束，通過(guò)建立規(guī)范化、科學(xué)的基礎(chǔ)框架結(jié)構(gòu)，可以應(yīng)對(duì)未來(lái)日趨復(fù)雜的調(diào)度場(chǎng)景，為衛(wèi)星資源管理中心提供通用求解的手段。

2 通信衛(wèi)星資源調(diào)度框架的構(gòu)建

根據(jù)靜止軌道通信衛(wèi)星資源調(diào)度的過(guò)程，形成通信衛(wèi)星資源調(diào)度架構(gòu)，如圖2所示，架構(gòu)主要包括資源管理、任務(wù)管理、資源調(diào)度和應(yīng)用4個(gè)部分。

圖2 通信衛(wèi)星資源調(diào)度架構(gòu)Fig.2 Communication satellite resource scheduling architecture

2.1 資源管理

通信衛(wèi)星資源是調(diào)度的對(duì)象，是系統(tǒng)分配的基礎(chǔ)。通信衛(wèi)星資源主要分為硬件資源和軟資源。硬件資源是衛(wèi)星的載荷資源，主要包括衛(wèi)星、天線(xiàn)和轉(zhuǎn)發(fā)器等；軟資源為衛(wèi)星的時(shí)間、頻率和功率等，如圖3所示。

圖3 通信衛(wèi)星載荷Fig.3 Communication satellite payloads

硬件資源是軟資源的支撐，也是軟資源的約束。通信天線(xiàn)發(fā)射的電磁波在地球表面形成波束，形成了衛(wèi)星的覆蓋范圍，也約束了使用該天線(xiàn)的轉(zhuǎn)發(fā)器內(nèi)頻率資源的使用范圍，只有在波束的覆蓋區(qū)域內(nèi)才能使用其頻率進(jìn)行通信。根據(jù)移動(dòng)性，波束可以分為固定波束和可移動(dòng)波束，固定波束的覆蓋范圍固定不變，可移動(dòng)波束在其移動(dòng)范圍內(nèi)可以根據(jù)任務(wù)需要調(diào)整覆蓋區(qū)域，更加靈活。轉(zhuǎn)發(fā)器或者通道是衛(wèi)星頻率劃分的最小單元，約束了頻率可連續(xù)帶寬及功率大小，其頻段及帶寬與任務(wù)所需頻段及帶寬的匹配，也是任務(wù)是否被執(zhí)行的關(guān)鍵。轉(zhuǎn)發(fā)器可以分為透明轉(zhuǎn)發(fā)器和處理轉(zhuǎn)發(fā)器，透明轉(zhuǎn)發(fā)器主要實(shí)現(xiàn)對(duì)信號(hào)的放大功能，處理轉(zhuǎn)發(fā)器可以對(duì)信號(hào)進(jìn)行調(diào)制解調(diào)或者多址方式再處理。目前，對(duì)通信衛(wèi)星資源調(diào)度的研究中，衛(wèi)星的資源模型較為簡(jiǎn)單，波束以固定波束為主，轉(zhuǎn)發(fā)器主要以透明轉(zhuǎn)發(fā)器為主。

資源管理主要維護(hù)資源池，一是將衛(wèi)星資源規(guī)范化存儲(chǔ)；二是對(duì)資源進(jìn)行監(jiān)視更新，任務(wù)結(jié)束后，將其使用資源收回，及時(shí)發(fā)現(xiàn)干擾或者載荷故障，更新資源池，確保衛(wèi)星資源的可用性。

2.2 任務(wù)管理

任務(wù)申請(qǐng)來(lái)自用戶(hù)對(duì)于組網(wǎng)通信的需求，用戶(hù)根據(jù)自己的任務(wù)場(chǎng)景提出的主要需求包括任務(wù)基本信息和資源需求信息兩方面。

① 任務(wù)基本信息：主要用于任務(wù)識(shí)別，即任務(wù)的身份證，包括任務(wù)名稱(chēng)、任務(wù)發(fā)起者和任務(wù)類(lèi)型等信息。

② 資源需求信息：最基礎(chǔ)的內(nèi)容包括任務(wù)時(shí)間、任務(wù)范圍、需求頻段及帶寬，是實(shí)現(xiàn)任務(wù)資源匹配的基本條件。任務(wù)時(shí)間為任務(wù)開(kāi)始時(shí)間和結(jié)束時(shí)間；任務(wù)范圍是任務(wù)過(guò)程中任務(wù)活動(dòng)區(qū)域；需求頻率資源包括頻段和帶寬2部分，且?guī)捫枰B續(xù)。

任務(wù)管理主要是對(duì)任務(wù)需求信息處理及更新。將任務(wù)的需求申請(qǐng)?zhí)幚頌橘Y源調(diào)度模塊的輸入格式，出現(xiàn)新的任務(wù)申請(qǐng)或任務(wù)需求變動(dòng)時(shí)，對(duì)任務(wù)集進(jìn)行更新，還可以根據(jù)任務(wù)的重要程度設(shè)置任務(wù)優(yōu)先級(jí)，用于輔助資源調(diào)度的決策。

2.3 資源調(diào)度

資源調(diào)度主要包括調(diào)度模型和調(diào)度算法2個(gè)模塊。調(diào)度模型是資源調(diào)度的重要基礎(chǔ)，決定了場(chǎng)景的描述方式、問(wèn)題的復(fù)雜程度，以及影響調(diào)度算法的選擇。調(diào)度算法是求解優(yōu)化調(diào)度模型結(jié)果的方法，實(shí)現(xiàn)調(diào)度問(wèn)題的求解，形成調(diào)度方案。

2.3.1 資源調(diào)度模型

通信衛(wèi)星資源調(diào)度求解過(guò)程中，問(wèn)題建模是首要步驟，也是關(guān)鍵步驟。建立衛(wèi)星通信調(diào)度模型主要考慮衛(wèi)星資源調(diào)度的場(chǎng)景，根據(jù)場(chǎng)景設(shè)置調(diào)度目標(biāo)，構(gòu)建約束條件。從調(diào)度場(chǎng)景角度出發(fā)可以分為靜態(tài)調(diào)度模型和動(dòng)態(tài)調(diào)度模型。

(1) 靜態(tài)調(diào)度模型

靜態(tài)調(diào)度是指在資源調(diào)度時(shí)，衛(wèi)星資源和用戶(hù)任務(wù)需求是確定的，調(diào)度過(guò)程中無(wú)已規(guī)劃任務(wù)或新的資源調(diào)度，不影響已有規(guī)劃任務(wù)的調(diào)度，此時(shí)可建立靜態(tài)調(diào)度模型。在通信衛(wèi)星靜態(tài)調(diào)度問(wèn)題中，主要研究如何分配通信衛(wèi)星處理任務(wù)的時(shí)間資源和頻率資源，最大化地滿(mǎn)足用戶(hù)的任務(wù)請(qǐng)求，不考慮任何擾動(dòng)因素。

建立常見(jiàn)靜態(tài)調(diào)度的基本數(shù)學(xué)模型如下:

調(diào)度目標(biāo)

(1)

約束條件

TDi∈D,

(2)

Tb≤tbi,tei≤Te,

(3)

TFi∈F,

(4)

bi≤B,

(5)

(6)

(7)

·調(diào)度目標(biāo)

常見(jiàn)調(diào)度目標(biāo)還有以下幾種：

① 任務(wù)調(diào)度數(shù)量最大化f2：當(dāng)任務(wù)需求總資源超過(guò)衛(wèi)星資源數(shù)量，或任務(wù)之間沖突較大時(shí)，導(dǎo)致部分任務(wù)無(wú)法獲取資源，需以最大化任務(wù)調(diào)度數(shù)量為目標(biāo)，進(jìn)行舍取。

② 衛(wèi)星資源利用率最大化f3：衛(wèi)星資源緊張的情況下，優(yōu)先考慮資源的分配，充分提高資源的利用率。

③ 資源使用均衡度f(wàn)4：任務(wù)集中分配在某段資源上，增加了該段資源故障擾動(dòng)帶來(lái)的風(fēng)險(xiǎn)。將任務(wù)均衡地分配到各個(gè)衛(wèi)星資源段中，可以降低故障造成的影響，減輕衛(wèi)星載荷的負(fù)載壓力。

④ 資源破碎度最小化f5：在任務(wù)與任務(wù)之間會(huì)產(chǎn)生空余的頻率資源段，如果空余的頻段較寬，會(huì)造成資源的浪費(fèi)，所以在調(diào)度的過(guò)程中要盡量減小空閑的數(shù)量，在避免不了時(shí)減小其帶寬，使資源段相對(duì)完整，減少資源的浪費(fèi)，有利于后續(xù)任務(wù)的調(diào)度。

該數(shù)學(xué)模型中，設(shè)置了一個(gè)調(diào)度目標(biāo)，可以根據(jù)實(shí)際需要增加目標(biāo)數(shù)量，建立多目標(biāo)優(yōu)化模型。

·約束條件

式(2)是覆蓋范圍約束：TDi為任務(wù)i的活動(dòng)范圍；D為衛(wèi)星資源的覆蓋范圍，要求任務(wù)區(qū)域必須在轉(zhuǎn)發(fā)器覆蓋范圍內(nèi)。

式(3)是時(shí)間約束：tbi,tei分別為任務(wù)i的開(kāi)始和結(jié)束時(shí)間；Tb，Te分別為資源的可用開(kāi)始時(shí)間和結(jié)束時(shí)間，要求任務(wù)的執(zhí)行時(shí)間必須在資源可用時(shí)間范圍內(nèi)。

式(4)是頻段約束：TFi為任務(wù)i的申請(qǐng)頻段；F為資源頻段，要求任務(wù)所需頻段必須與轉(zhuǎn)發(fā)器頻段一致。

式(5)是帶寬約束：bi為任務(wù)i的需求帶寬;B為資源提供帶寬，要求衛(wèi)星資源的可用帶寬大于或者等于任務(wù)需求帶寬，才能提供服務(wù)。

式(6)是任務(wù)執(zhí)行次數(shù)的約束:yi,j=1表示第i個(gè)任務(wù)使用第j個(gè)資源;yi,j=0表示第i個(gè)任務(wù)不使用第j個(gè)資源;m為資源的數(shù)量。式(6)表示每個(gè)任務(wù)在其可用資源中僅選取一個(gè)資源，只執(zhí)行一次，且執(zhí)行過(guò)程不能中斷。

式(7)是資源使用次數(shù)的約束：hj,i=1表示第j個(gè)資源被第i個(gè)任務(wù)使用；yi,j=0表示第j個(gè)資源未被第i個(gè)任務(wù)使用，n為任務(wù)數(shù)量。式(7)表示同一資源在同一時(shí)刻不可以被多任務(wù)共同使用。

以上約束為靜止軌道通信衛(wèi)星資源分配的基礎(chǔ)約束，在具體場(chǎng)景的運(yùn)用中，可以根據(jù)實(shí)際情況添加約束。

靜態(tài)調(diào)度的優(yōu)點(diǎn)是調(diào)度過(guò)程、算法簡(jiǎn)單，但是靜態(tài)調(diào)度靈活性不強(qiáng)，對(duì)于需要提前長(zhǎng)時(shí)間進(jìn)行部署的任務(wù)不友好，對(duì)用戶(hù)來(lái)講增加了資源調(diào)度的不確定性。

(2) 動(dòng)態(tài)調(diào)度模型

動(dòng)態(tài)調(diào)度是指在調(diào)度方案的執(zhí)行過(guò)程中，出現(xiàn)突發(fā)情況影響任務(wù)的執(zhí)行，需要即刻在原有調(diào)度方案的基礎(chǔ)上進(jìn)行資源分配的調(diào)整，此時(shí)需根據(jù)擾動(dòng)因素建立動(dòng)態(tài)調(diào)度模型，應(yīng)對(duì)系統(tǒng)突發(fā)擾動(dòng)事件。動(dòng)態(tài)擾動(dòng)主要包括衛(wèi)星設(shè)備損壞或者干擾所導(dǎo)致的衛(wèi)星資源變化、任務(wù)的突然撤銷(xiāo)或者新任務(wù)的增加所導(dǎo)致的任務(wù)數(shù)量的變化、任務(wù)持續(xù)時(shí)間變動(dòng)等[7-11]。

建立動(dòng)態(tài)調(diào)度數(shù)學(xué)模型如下：

調(diào)度目標(biāo)

(8)

max(αnd+βnc)。

(9)

約束條件

TDi∈D，

(10)

Tb≤tbi,tei≤Te，

(11)

TFi∈F，

(12)

bi≤B，

(13)

(14)

(15)

·動(dòng)態(tài)調(diào)度目標(biāo)

根據(jù)動(dòng)態(tài)擾動(dòng)因素規(guī)劃新的調(diào)度方案時(shí)，常考慮與原有初始調(diào)度方案的變更情況，即在最大化地滿(mǎn)足用戶(hù)的任務(wù)請(qǐng)求等性能目標(biāo)的同時(shí)，要保證新方案與初始方案之間變化最小，即新方案與初始方案之間相似性最大。故增加了目標(biāo)式(9)：nd表示初始方案到新方案任務(wù)分配資源不變的任務(wù)總數(shù)；nc表示初始方案到新方案任務(wù)分配資源變動(dòng)的任務(wù)總數(shù)；α表示分配資源不變?nèi)蝿?wù)的權(quán)重；β表示資源調(diào)整任務(wù)的權(quán)重。

·約束分析

① 任務(wù)擾動(dòng)

任務(wù)時(shí)間、任務(wù)需求帶寬的改變主要是任務(wù)與轉(zhuǎn)發(fā)器之間可用資源和時(shí)間窗口約束的變化，更新約束式(11)和(13)。新增任務(wù)擾動(dòng)主要增加任務(wù)的數(shù)量，更新n的數(shù)值，增加TD,tb,te,TF,b集合內(nèi)參數(shù)值。

② 資源擾動(dòng)因素

在用資源受擾和衛(wèi)星設(shè)備故障造成的影響都是資源故障，其主要引起資源集的變化，從而導(dǎo)致衛(wèi)星資源的時(shí)間、可用資源集的變化，故需要更新集合Tb，Te，F(xiàn)，B。

動(dòng)態(tài)調(diào)度方法更加靈活，根據(jù)通信衛(wèi)星資源變動(dòng)和任務(wù)新增需求，在相對(duì)減小對(duì)原有方案影響的基礎(chǔ)上，近似于實(shí)時(shí)調(diào)整調(diào)度，更加符合實(shí)際需求。

2.3.2 調(diào)度算法

調(diào)度算法是求解調(diào)度問(wèn)題的關(guān)鍵，目前，精確算法、啟發(fā)式算法等一系列調(diào)度算法被應(yīng)用于通信衛(wèi)星資源調(diào)度問(wèn)題中，表現(xiàn)出較好的優(yōu)化效果。

精確算法包括線(xiàn)性規(guī)劃、動(dòng)態(tài)規(guī)劃、整數(shù)規(guī)劃和分支定界法等運(yùn)籌學(xué)中的傳統(tǒng)算法，需要遍歷所有解空間，能夠解出全局最優(yōu)解，其算法計(jì)算復(fù)雜性一般很大，只適合于求解小規(guī)模問(wèn)題，在應(yīng)用于復(fù)雜、困難的優(yōu)化問(wèn)題時(shí)有較大的局限性[12-13]。面對(duì)現(xiàn)在大規(guī)模、復(fù)雜度高的衛(wèi)星資源調(diào)度，精確算法并不適用，但是其在模型建立、目標(biāo)函數(shù)設(shè)計(jì)等方面有一定的指導(dǎo)意義。

啟發(fā)式算法是設(shè)計(jì)在解空間搜索的一類(lèi)算法，在可接受的計(jì)算成本內(nèi)去搜尋最好的解，但不能保證所得解是最優(yōu)解，甚至在多數(shù)情況下，無(wú)法闡述所得解同最優(yōu)解的近似程度。啟發(fā)式算法的求解結(jié)果可能千變?nèi)f化，選擇合適的初始參數(shù)對(duì)啟發(fā)式算法非常重要，一般需要根據(jù)問(wèn)題本身的特點(diǎn)進(jìn)行適應(yīng)性改造，如常采用的模擬退火算法(SA)、禁忌搜索、遺傳算法(GA)、蟻群算法(ACO)、粒子群算法(PSO)和人工蜂群(ABC)等，在衛(wèi)星資源調(diào)度問(wèn)題[14-16]中都有成功的應(yīng)用，但其本身也存在一些不足。例如，局部搜索能力差、存在未成熟收斂等現(xiàn)象，從而導(dǎo)致算法的收斂性能差，需要很長(zhǎng)時(shí)間才能找到最優(yōu)解。為提高算法的搜索能力和提高算法的收斂速度，產(chǎn)生了眾多改進(jìn)型算法。王海波等[17]利用蟻群優(yōu)化模擬退火算法進(jìn)行天地測(cè)控資源聯(lián)合調(diào)度。啟發(fā)式算法之間進(jìn)行適當(dāng)結(jié)合，可以針對(duì)性地改善遺傳算法自身存在的問(wèn)題，形成算法性能上的互補(bǔ)，使問(wèn)題優(yōu)化的過(guò)程快速高效。

常見(jiàn)啟發(fā)式算法的偽代碼如下。

Algorithm Framework of Heuristic algorithmInput:task set T,Satellite resources set S,Satellite and mission mat-ching set DS,population size NP,maximum generation Gen,limit the number of improvements LimitOutput: the best solution1:Initialize all parameters2:P←Initial population generation (NP,T)3:Solution0 ←Satellite and mission match4:f←Calculate the fitness value of the initial population individual(NP)5:G_best ←Update the best solution6:forgen= 1 to GEN do7: foreach operator do8: Search for new individuals9:end10: L_best ←find the best individual11: If L_best>G_best then12: G_best=L_best;13: end14:end

面對(duì)日益復(fù)雜的大規(guī)模優(yōu)化問(wèn)題，尤其是多模態(tài)、高維、帶約束和多目標(biāo)優(yōu)化問(wèn)題，需要不斷尋找性能更高的智能算法，例如超啟發(fā)式算法、學(xué)習(xí)算法等，將其應(yīng)用在通信衛(wèi)星資源調(diào)度問(wèn)題中，以獲取更加令人滿(mǎn)意的優(yōu)化效果。

本文采用海洋捕食者算法(Marine Predators Algorithm,MPA)對(duì)資源調(diào)度問(wèn)題進(jìn)行求解。該算法是Faramarzi等[18]于2020年提出的一種新型元啟發(fā)式優(yōu)化算法，是受海洋生物中捕食者和獵物的行為啟發(fā)，通過(guò)實(shí)驗(yàn)驗(yàn)證具有很高的尋優(yōu)能力。

2.4 資源調(diào)度模式

衛(wèi)星資源管理中心的調(diào)度模式主要以日常調(diào)度和應(yīng)急調(diào)度為主。在日常調(diào)度中，用戶(hù)會(huì)根據(jù)任務(wù)的開(kāi)始時(shí)間提前較長(zhǎng)時(shí)間進(jìn)行資源申請(qǐng)，資源調(diào)度中心有足夠的時(shí)間選擇合適的時(shí)間點(diǎn)進(jìn)行資源調(diào)度，并將調(diào)度方案中規(guī)劃的任務(wù)資源按照時(shí)間節(jié)點(diǎn)下發(fā)給用戶(hù)。應(yīng)急調(diào)度常與動(dòng)態(tài)調(diào)度模型相結(jié)合，用以應(yīng)對(duì)原有調(diào)度方案執(zhí)行過(guò)程中，出現(xiàn)新的緊急任務(wù)或衛(wèi)星資源出現(xiàn)擾動(dòng)等突發(fā)事件時(shí)，進(jìn)行實(shí)時(shí)調(diào)度，需在第一時(shí)間將調(diào)度方案結(jié)果通知用戶(hù)。

3 實(shí)例驗(yàn)證

基于上述通信衛(wèi)星資源調(diào)度框架，結(jié)合MPA，進(jìn)行通信衛(wèi)星資源調(diào)度問(wèn)題的仿真求解。

3.1 仿真場(chǎng)景

應(yīng)用調(diào)度場(chǎng)景設(shè)計(jì)如下：假設(shè)有4個(gè)可用衛(wèi)星資源，具體衛(wèi)星資源信息如表1所示，在2021年7月16日00時(shí)，接收到日常任務(wù)申請(qǐng)40個(gè)，需進(jìn)行資源調(diào)度操作。經(jīng)整理，任務(wù)申請(qǐng)需求如表2所示。任務(wù)區(qū)域范圍以經(jīng)度、緯度為中心點(diǎn)，半徑為r的圓形表示。任務(wù)優(yōu)先級(jí)為1～5的隨機(jī)整數(shù)，數(shù)值越小優(yōu)先級(jí)越高。在設(shè)置任務(wù)開(kāi)始時(shí)間和需求帶寬時(shí)，增加了任務(wù)之間的沖突，以體現(xiàn)資源調(diào)度解決任務(wù)之間矛盾的有效性。

表1 衛(wèi)星通信資源Tab.1 Satellite communication resources

表2 通信任務(wù)Tab.2 Communication task

3.2 建模求解

MPA是一種基于群體的方法，利用布朗運(yùn)動(dòng)(Brownian Motion)和萊維飛行(Lévy Flight)2種隨機(jī)游走算子來(lái)進(jìn)行搜索。萊維飛行的隨機(jī)游走以小步碎走和間歇性大跳為主，步長(zhǎng)較小，使算法能夠有效且深入地搜索附近的鄰域；間歇性大跳能使算法跳出局部，進(jìn)行其他區(qū)域的搜索，但跳步較大，不能完全覆蓋所有區(qū)域。布朗運(yùn)動(dòng)的步長(zhǎng)服從正態(tài)分布，可以追蹤和探索鄰居的較遠(yuǎn)區(qū)域，但不能像萊維飛行策略精確和深入地搜索。MPA將萊維飛行的獨(dú)特性和布朗運(yùn)動(dòng)的特性相結(jié)合，探索如何更全局/局部地探索和利用解空間。本文將MPA與靜止軌道衛(wèi)星資源調(diào)度相結(jié)合，在迭代后期，對(duì)萊維飛行和布朗運(yùn)動(dòng)的使用進(jìn)行了調(diào)整改進(jìn)，獵物種群前半部分采用布朗運(yùn)動(dòng)算子進(jìn)行搜索；后半部分采用萊維飛行算子進(jìn)行搜索，形成改進(jìn)的MPA——IMPA，用以提高算法的求解質(zhì)量，算法流程如圖4所示。

圖4 IMPA的流程Fig.4 IMPA process

采用IMPA對(duì)調(diào)度模型進(jìn)行求解，圖5為IMPA求解目標(biāo)值的搜索過(guò)程，可以看出,IMPA以相對(duì)均勻的小步碎走和間歇性大跳的方式進(jìn)行搜索，深入進(jìn)行鄰域搜索的同時(shí)避免陷入局部。

圖5 IMPA運(yùn)行結(jié)果Fig.5 IMPA operation result

采用ABC,MPA和改進(jìn)后的IMPA同時(shí)對(duì)問(wèn)題進(jìn)行求解，迭代次數(shù)均設(shè)置為NP=500，種群數(shù)量為pop=100。為消除隨機(jī)性的影響，將算法運(yùn)行10次，以均值體現(xiàn)算法的求解性能，以方差表示算法的穩(wěn)定性，對(duì)運(yùn)行數(shù)據(jù)進(jìn)行分析梳理如表3所示，將算法10次運(yùn)行的收益值繪制成圖，如圖5所示。

表3 場(chǎng)景仿真計(jì)算結(jié)果Tab.3 Scene simulation calculation results

場(chǎng)景中，任務(wù)數(shù)量為40個(gè)，總收益為36。采用ABC，10次運(yùn)行獲得平均收益為30.90，占總收益的85.83%，平均執(zhí)行任務(wù)32.2個(gè)，占總?cè)蝿?wù)數(shù)的80.5%；使用MPA，10次運(yùn)行獲得平均收益為32.32，占總收益的89.78%，平均執(zhí)行任務(wù)33.5個(gè)，占總?cè)蝿?wù)數(shù)的82.5%；使用IMPA，10次運(yùn)行獲得平均收益為33.36，占總收益的92.67%，平均執(zhí)行任務(wù)35個(gè)，占總?cè)蝿?wù)數(shù)的87.5%。IMPA的平均收益值比ABC提高了8.9%，比MPA提升2.89%，任務(wù)數(shù)量平均增加2個(gè)左右。算法運(yùn)行目標(biāo)值分布如圖6所示。由圖6及方差值可以看出，IMPA更加穩(wěn)定。

圖6 算法運(yùn)行目標(biāo)值分布Fig.6 Distribution of target values for algorithm operation

4 結(jié)束語(yǔ)

靜止軌道通信衛(wèi)星資源調(diào)度的框架和調(diào)度過(guò)程較為簡(jiǎn)單，但是隨著技術(shù)的發(fā)展，通信衛(wèi)星載荷更加復(fù)雜，簡(jiǎn)單的透明轉(zhuǎn)發(fā)器模型不能滿(mǎn)足當(dāng)前的需求；任務(wù)之間的關(guān)聯(lián)關(guān)系逐漸呈現(xiàn)，簡(jiǎn)單的約束關(guān)系不能適應(yīng)復(fù)雜的調(diào)度場(chǎng)景。因此需要根據(jù)調(diào)度框架，結(jié)合實(shí)際情況，建立更加復(fù)雜且貼近實(shí)際的調(diào)度模型，來(lái)更好地解決衛(wèi)星資源與任務(wù)之間的矛盾。