面向密集多波束組網(wǎng)的衛(wèi)星通信系統(tǒng)資源調(diào)度算法

何元智，彭聰,2，于季弘，劉韻

（1.軍事科學(xué)院系統(tǒng)工程研究院，北京 100141；2.空軍工程大學(xué)信息與導(dǎo)航學(xué)院，陜西 西安 710077；3.北京理工大學(xué)通信與網(wǎng)絡(luò)實(shí)驗(yàn)室，北京 100081）

1 引言

隨著空間信息技術(shù)的快速發(fā)展，近年來國內(nèi)外衛(wèi)星互聯(lián)網(wǎng)紛紛展開部署。國外代表性系統(tǒng)主要包括全球星系統(tǒng)、銥星系統(tǒng)、星鏈系統(tǒng)等[1-3]；我國把衛(wèi)星互聯(lián)網(wǎng)建設(shè)納入“新基建”范疇，并且將其定位為國家戰(zhàn)略性工程[4]，代表性系統(tǒng)包括鴻雁星座、行云工程、虹云工程、天象星座等[5-7]。作為未來空天地一體互聯(lián)網(wǎng)絡(luò)的重要組成部分，衛(wèi)星通信系統(tǒng)具有廣覆蓋、低時(shí)延、大寬帶、小終端等特點(diǎn)，正在朝著空天地密集多波束組網(wǎng)的方向發(fā)展。然而，空間軌位與頻譜資源的競(jìng)爭(zhēng)愈演愈烈，并伴隨空間業(yè)務(wù)量的爆發(fā)式增長，導(dǎo)致衛(wèi)星通信系統(tǒng)面臨的壓力巨大，因此需要在滿足用戶需求時(shí)，對(duì)有限的衛(wèi)星資源進(jìn)行合理調(diào)度，這對(duì)于實(shí)現(xiàn)星地之間高效協(xié)同、統(tǒng)籌組網(wǎng)具有十分重要的現(xiàn)實(shí)意義。

在密集多波束星地一體化組網(wǎng)條件下進(jìn)行衛(wèi)星資源調(diào)度會(huì)面臨星地動(dòng)態(tài)變化、多波束負(fù)載差異、星上資源受限等挑戰(zhàn)，需要在一定的時(shí)間窗口內(nèi)對(duì)有限的星上資源進(jìn)行全局規(guī)劃和多目標(biāo)化。文獻(xiàn)[8]對(duì)觀測(cè)能力有限的多衛(wèi)星資源調(diào)度問題進(jìn)行了研究，并將其轉(zhuǎn)化為組合優(yōu)化問題，同時(shí)提出了一種二階啟發(fā)式方法，在合理的計(jì)算時(shí)間內(nèi)獲得高質(zhì)量的解。文獻(xiàn)[9]提出了一種基于分治原則的新型衛(wèi)星調(diào)度框架，在此框架下，采用蟻群優(yōu)化算法將觀測(cè)任務(wù)分配到不同的衛(wèi)星軌道，并設(shè)計(jì)了一種自適應(yīng)模擬退火算法來解決每個(gè)軌道的衛(wèi)星觀測(cè)問題。文獻(xiàn)[10]提出了一種分層調(diào)度方法來解決衛(wèi)星實(shí)時(shí)調(diào)度問題，將調(diào)度過程分為3 個(gè)步驟，即預(yù)調(diào)、粗調(diào)度、精調(diào)度，在此基礎(chǔ)上提出了一種基于蟻群優(yōu)化的分層調(diào)度算法。文獻(xiàn)[11]首先分析了衛(wèi)星距離調(diào)度問題，并建立了數(shù)學(xué)模型和約束條件，然后提出了一種將改進(jìn)遺傳算法和局部搜索方法相結(jié)合的高效算法，利用改進(jìn)的遺傳算法快速提高規(guī)劃方案的質(zhì)量，并利用鄰域搜索進(jìn)行后續(xù)的小規(guī)模優(yōu)化。文獻(xiàn)[12]提出了一種基于深度神經(jīng)網(wǎng)絡(luò)的多衛(wèi)星資源調(diào)度方法，通過將多個(gè)約束和相關(guān)屬性轉(zhuǎn)換為不同的標(biāo)志，并使用數(shù)據(jù)的一些二進(jìn)制位來反映約束關(guān)系，提高了資源的利用效率。文獻(xiàn)[13]提出了一種結(jié)合軟件定義網(wǎng)絡(luò)（SDN,software defined network）模型的三層網(wǎng)絡(luò)體系結(jié)構(gòu)，用于指導(dǎo)衛(wèi)星間鏈路（ISL,inter-satellite link）連接和衛(wèi)星邊緣計(jì)算的資源調(diào)度，并提出了先進(jìn)的k 均值算法和基于廣度優(yōu)先搜索的生成樹算法，分別實(shí)現(xiàn)了衛(wèi)星邊緣計(jì)算資源劃分和ISL 構(gòu)建。上述研究都從具體的約束出發(fā)，基于不同的應(yīng)用場(chǎng)景建立資源調(diào)度模型，并提出優(yōu)化算法求解資源調(diào)度問題，但是這些算法僅適用于特定網(wǎng)絡(luò)場(chǎng)景，不能很好地適用于密集多波束衛(wèi)星通信網(wǎng)絡(luò)的資源調(diào)度，且算法復(fù)雜度較高。

資源調(diào)度的核心是資源調(diào)度算法，常用的有遺傳算法、蟻群優(yōu)化算法、粒子群算法以及它們的組合[11,14-18]，這些算法對(duì)于一般規(guī)模網(wǎng)絡(luò)的資源調(diào)度能夠達(dá)到很好的優(yōu)化效果，但在密集多波束組網(wǎng)的條件下，算法的復(fù)雜度會(huì)急劇上升，因此需要在算法的優(yōu)化性能和復(fù)雜度之間進(jìn)行折中。對(duì)于衛(wèi)星資源調(diào)度來說，還需要考慮實(shí)現(xiàn)的難易程度，蟻群優(yōu)化（ACO,ant colony optimization）算法作為一種啟發(fā)式尋優(yōu)搜索算法，常用于求解路由最短路徑以及多目標(biāo)資源優(yōu)化問題，具有控制簡(jiǎn)單、兼容性強(qiáng)、對(duì)硬件要求不高以及易于編程實(shí)現(xiàn)等特點(diǎn)，對(duì)于解決密集多波束、高動(dòng)態(tài)的衛(wèi)星資源調(diào)度問題具有一定優(yōu)勢(shì)。然而，初始階段信息素匱乏導(dǎo)致的搜索速度過慢以及局部搜索能力較弱等特點(diǎn)嚴(yán)重制約該算法在實(shí)時(shí)性、高效性需求較強(qiáng)的衛(wèi)星調(diào)度過程中的應(yīng)用，需要對(duì)其進(jìn)行改進(jìn)。

基于上述考慮，本文分析了密集多波束組網(wǎng)場(chǎng)景下衛(wèi)星通信系統(tǒng)資源調(diào)度的約束條件，建立了多目標(biāo)資源調(diào)度模型，綜合考慮了現(xiàn)有蟻群優(yōu)化算法的優(yōu)缺點(diǎn)，并針對(duì)存在的缺點(diǎn)，提出了以初始解集構(gòu)造和額外信息素沉積為核心的改進(jìn)蟻群優(yōu)化算法，最后設(shè)計(jì)了仿真場(chǎng)景對(duì)模型和算法進(jìn)行了仿真驗(yàn)證。

2 衛(wèi)星通信系統(tǒng)資源調(diào)度問題建模

在衛(wèi)星通信系統(tǒng)中，隨著衛(wèi)星在軌移動(dòng)，其覆蓋范圍將發(fā)生變化，對(duì)應(yīng)的業(yè)務(wù)負(fù)載以及優(yōu)先級(jí)也會(huì)隨之變化。為了滿足不斷變化的地面任務(wù)需求，需要對(duì)衛(wèi)星資源、信道資源以及時(shí)隙資源進(jìn)行合理調(diào)度，資源調(diào)度問題主要受到時(shí)間窗口約束、衛(wèi)星功耗約束、信道數(shù)量約束、地面用戶優(yōu)先級(jí)以及突發(fā)性等條件影響，其目標(biāo)是在滿足這些約束條件的前提下，保證系統(tǒng)的功耗盡可能小，調(diào)度完成的高優(yōu)先級(jí)的任務(wù)盡可能多。

2.1 系統(tǒng)模型

衛(wèi)星通信系統(tǒng)的資源調(diào)度場(chǎng)景如圖1 所示。衛(wèi)星通信系統(tǒng)由M顆多波束通信衛(wèi)星組成，對(duì)地面用戶進(jìn)行動(dòng)態(tài)覆蓋，不同衛(wèi)星波束的覆蓋區(qū)域之間存在一定的重疊。將系統(tǒng)所能覆蓋的區(qū)域范圍劃分為N個(gè)地面區(qū)域，通信任務(wù)根據(jù)其發(fā)起用戶所在位置分別歸屬于不同的地面區(qū)域。

圖1 衛(wèi)星通信系統(tǒng)的資源調(diào)度場(chǎng)景示意

考慮到隨著衛(wèi)星的在軌移動(dòng)，即圖1 中SAT1和SAT2由左側(cè)位置沿軌道移動(dòng)至右側(cè)位置時(shí)，各波束所覆蓋的地面區(qū)域隨之發(fā)生變化，設(shè)置時(shí)間窗口為TWi,i=1,2，以時(shí)間窗口長度為粒度對(duì)衛(wèi)星通信資源進(jìn)行優(yōu)化，其中，T W1表示當(dāng)前時(shí)間窗口，TW2表示下一個(gè)時(shí)間窗口，時(shí)間窗口的起止時(shí)間為[S Ti,ETi]。時(shí)間窗口可劃分為Nk個(gè)資源調(diào)度窗口，為任務(wù)的最大分配單元，當(dāng)任務(wù)的起止時(shí)刻包含于資源調(diào)度窗口內(nèi)時(shí)，才能有效地執(zhí)行任務(wù)的傳輸。每個(gè)資源調(diào)度窗口持續(xù)K個(gè)時(shí)隙，第k個(gè)資源調(diào)度窗口的開始時(shí)刻和結(jié)束時(shí)刻分別為和。

在時(shí)間窗口TWi中，來自第n個(gè)地面區(qū)域的通信任務(wù)可以表示為一個(gè)五元數(shù)組，即

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

基于以上對(duì)系統(tǒng)模型的分析，以地面任務(wù)服務(wù)質(zhì)量以及衛(wèi)星通信系統(tǒng)的總功耗為目標(biāo)，本文建立了如式(1)所示的衛(wèi)星通信資源調(diào)度模型。

上述模型中，目標(biāo)函數(shù) O1表示在2 個(gè)時(shí)間窗口內(nèi)衛(wèi)星通信系統(tǒng)盡可能完成多個(gè)高優(yōu)先級(jí)任務(wù)的傳輸，即調(diào)度完成的高優(yōu)先級(jí)業(yè)務(wù)總和的倒數(shù)最小；目標(biāo)函數(shù) O2代表2 個(gè)時(shí)間窗口內(nèi)系統(tǒng)總功耗最小，總功耗主要由2 個(gè)部分組成，第一部分為任務(wù)傳輸功耗，第二部分為切換功耗。其中，Pms為單位時(shí)間切換的功率大小，Tms為連續(xù)執(zhí)行資源調(diào)度需要最大切換時(shí)間，只有當(dāng)=1時(shí)，不需要進(jìn)行衛(wèi)星切換，即。

在約束條件中，C1為時(shí)間窗口起始時(shí)刻約束，目的是確保2 個(gè)時(shí)間窗口不發(fā)生重疊，且各資源調(diào)度窗口均完整地位于時(shí)間窗口內(nèi)部。C2表示任務(wù)有效執(zhí)行時(shí)間約束，即只有當(dāng)任務(wù)的起止時(shí)刻包含于時(shí)間調(diào)度窗口內(nèi)時(shí)，才能有效地執(zhí)行任務(wù)的傳輸。C3為信道數(shù)量約束，即為每個(gè)區(qū)域分配的信道數(shù)量總和應(yīng)該小于總的信道數(shù)量。C4為任務(wù)狀態(tài)更新方程，考慮到任務(wù)隨時(shí)間的連續(xù)變化性，下一個(gè)時(shí)間窗口有可能出現(xiàn)優(yōu)先級(jí)較高的“熱點(diǎn)”任務(wù)或突發(fā)性較強(qiáng)的重負(fù)載任務(wù)，即任務(wù)突發(fā)情況，或者出現(xiàn)大量低優(yōu)先級(jí)、輕負(fù)載的任務(wù)，即任務(wù)減少情況，這時(shí)需要對(duì)網(wǎng)絡(luò)資源的調(diào)度進(jìn)行調(diào)整。通過定義時(shí)隙數(shù)調(diào)整量θb，描述地面區(qū)域在前后2 個(gè)時(shí)間窗口中占用時(shí)隙數(shù)的彈性變化，通過定義優(yōu)先級(jí)調(diào)整量Ah，描述地面區(qū)域在前后2 個(gè)時(shí)間窗口中的優(yōu)先級(jí)變化。C5為衛(wèi)星與地面任務(wù)的功耗關(guān)系，對(duì)于每一顆衛(wèi)星而言，它所提供的功率等于其覆蓋區(qū)域內(nèi)所有任務(wù)功率的總和，且必須小于衛(wèi)星所能提供的最大功率。C6為功耗約束，即覆蓋區(qū)域內(nèi)所有任務(wù)的傳輸功耗與衛(wèi)星的切換功耗之和不超過衛(wèi)星在這2 個(gè)時(shí)間窗口內(nèi)所能提供的功耗總和。約束條件C1和C2是確保資源調(diào)度成功的時(shí)間窗口約束，即保證任務(wù)的起止時(shí)間要落在資源調(diào)度窗口內(nèi)；C3、C5和C6分別是信道約束、功率約束和功耗約束，對(duì)應(yīng)衛(wèi)星的通信資源；C4是時(shí)隙調(diào)整和優(yōu)先級(jí)調(diào)整，用于刻畫地面通信任務(wù)的連續(xù)動(dòng)態(tài)變化特性。

在整個(gè)資源調(diào)度過程中，進(jìn)行如下假設(shè)。

1) 2 個(gè)時(shí)間窗口的任務(wù)傳輸與資源調(diào)度相互獨(dú)立，任務(wù)傳輸具有連續(xù)性，并且只在時(shí)間窗口內(nèi)進(jìn)行，如果任務(wù)傳輸?shù)慕K止時(shí)間超過了時(shí)間窗口的終止時(shí)間，則判定任務(wù)傳輸失敗。

2) 第一個(gè)時(shí)間窗口結(jié)束后，需要對(duì)任務(wù)集合進(jìn)行更新，下一個(gè)時(shí)間窗口不同區(qū)域的突發(fā)性大小主要影響任務(wù)傳輸所需要的時(shí)隙數(shù)，“熱點(diǎn)”性強(qiáng)弱主要影響任務(wù)的優(yōu)先級(jí)。

3) 信道分配取決于任務(wù)需求，前提是不能超過信道總數(shù)，在進(jìn)行任務(wù)傳輸?shù)臅r(shí)候，忽略信道損耗對(duì)功耗的影響。

2.3 資源調(diào)度問題分析

通過觀察上述資源優(yōu)化問題的數(shù)學(xué)模型，2 個(gè)優(yōu)化目標(biāo)函數(shù)雖然在求解參數(shù)上并不強(qiáng)相關(guān)，但由于優(yōu)先級(jí)加權(quán)和與功耗同處于N個(gè)地面區(qū)域和M個(gè)衛(wèi)星提供服務(wù)的約束之下，使約束條件空間的參數(shù)下標(biāo)之間存在相關(guān)性，導(dǎo)致使數(shù)學(xué)模型中2 個(gè)優(yōu)化目標(biāo)之間具有強(qiáng)耦合特性，因此，2 個(gè)優(yōu)化目標(biāo)不能拆解為單獨(dú)的優(yōu)化目標(biāo)函數(shù)求解。

實(shí)際上，上述問題的關(guān)鍵在于目標(biāo)函數(shù) O1中的優(yōu)先級(jí)權(quán)重，若只考慮目標(biāo)函數(shù) O2，其最小值的解集空間為考慮優(yōu)先級(jí)權(quán)重，在業(yè)務(wù)量大于系統(tǒng)可調(diào)度資源時(shí)，可能導(dǎo)致為了節(jié)約功耗放棄部分高優(yōu)先級(jí)業(yè)務(wù)調(diào)度的問題，即最低功耗解不一定是最高優(yōu)先級(jí)加權(quán)和任務(wù)完成度的解。因此，上述優(yōu)化函數(shù)的數(shù)學(xué)含義是尋找優(yōu)先級(jí)加權(quán)和任務(wù)完成度和功耗之間的折中。但由于2 個(gè)優(yōu)化問題的參數(shù)空間的強(qiáng)耦合特性，無法通過簡(jiǎn)單的參數(shù)代入推導(dǎo)獲得解析解，也無法通過參數(shù)空間合并轉(zhuǎn)化為單目標(biāo)優(yōu)化問題再通過凸優(yōu)化方法求解。針對(duì)這類問題，數(shù)學(xué)上通常通過遍歷搜索的方法來求解。

然而，遍歷搜索的方式由于要窮舉解集空間，其算法復(fù)雜度與解集空間的大小強(qiáng)相關(guān)。首先，分析目標(biāo)函數(shù) O1，其中，任務(wù)傳輸完成標(biāo)識(shí)具備2個(gè)狀態(tài)0 和1，即對(duì)于x個(gè)該類標(biāo)識(shí)的組合，組合可能為2x個(gè)，那么，O1解空間大小為

通過上述分析，解空間大小為指數(shù)函數(shù)，意味著遍歷求解方式的計(jì)算復(fù)雜度隨著參數(shù)下標(biāo)的大小呈指數(shù)增長。實(shí)際上，優(yōu)化問題根據(jù)其是否可以在多項(xiàng)式時(shí)間內(nèi)求解，通常可以分類為多項(xiàng)式（P,polynomial）問題和非多項(xiàng)式（NP,non-deterministic polynomial）問題，上述問題的計(jì)算復(fù)雜度為非多項(xiàng)式函數(shù)，是典型的NP 問題。為了求解該問題，需要通過多輪次迭代尋找求解搜索方向，以避免無方向的遍歷帶來的指數(shù)級(jí)復(fù)雜度。蟻群優(yōu)化算法作為一種模擬進(jìn)化算法，是一種用來在圖中尋找優(yōu)化路徑的隨機(jī)算法，可用于本文的優(yōu)化問題求解。

3 衛(wèi)星通信資源調(diào)度算法設(shè)計(jì)

基于對(duì)蟻群優(yōu)化算法優(yōu)缺點(diǎn)的綜合考慮，本文以提高算法初期搜索速度和局部搜索能力目標(biāo)，提出一種改進(jìn)的蟻群優(yōu)化算法來解決多約束條件下的衛(wèi)星通信系統(tǒng)資源調(diào)度問題，算法流程如圖2所示。

3.1 初始解集構(gòu)造以及信息素的更新

在蟻群優(yōu)化算法中，對(duì)于每一個(gè)解元素Γi=(α,β,γ)來說，都有一個(gè)信息素濃度τi與之對(duì)應(yīng)。信息素濃度的更新為

其中，ρ為揮發(fā)速率，ωΓ為解元素Γi的權(quán)重因子。首先，通過蒙特卡羅仿真產(chǎn)生初始解集空間，然后將解集與任務(wù)集合進(jìn)行映射。為了提高算法初期的搜索速度，本文定義了質(zhì)量函數(shù)F(Γ)=f1，其目標(biāo)是確保調(diào)度完成的任務(wù)的優(yōu)先級(jí)盡可能高。任務(wù)按照優(yōu)先級(jí)的大小依次傳輸，如果任務(wù)的傳輸時(shí)間不能滿足時(shí)間窗口約束，則視為無法傳輸，可以把這些任務(wù)所對(duì)應(yīng)的解元素從解集空間中刪掉，最后確定初始的解集范圍。

我州每年會(huì)有大量農(nóng)村初中畢業(yè)生直接進(jìn)入勞動(dòng)力市場(chǎng)，既降低了勞動(dòng)者素質(zhì)，又影響了經(jīng)濟(jì)發(fā)展質(zhì)量。據(jù)調(diào)查，我州近幾年專業(yè)技能人才缺口上萬人，而職業(yè)教育輸送的人才數(shù)量遠(yuǎn)不能滿足經(jīng)濟(jì)社會(huì)發(fā)展需要。因此，高素質(zhì)技能型人才短缺依然是產(chǎn)業(yè)發(fā)展的瓶頸。

圖2 衛(wèi)星通信系統(tǒng)資源調(diào)度算法流程

3.2 狀態(tài)轉(zhuǎn)移概率的確定

對(duì)于時(shí)間窗口TWi，假設(shè)τm,n,w為第m顆衛(wèi)星通過信道w完成對(duì)區(qū)域n中的調(diào)度任務(wù)的信息素濃度，則轉(zhuǎn)移概率式為

其中，a為信息素啟發(fā)值權(quán)重，用來描述信息素濃度對(duì)于調(diào)度任務(wù)的影響程度，其值越大，螞蟻對(duì)走過的路徑選擇的概率越大；κm,n,w(TWi)為第m顆衛(wèi)星通過信道w完成對(duì)區(qū)域n中的調(diào)度任務(wù)的啟發(fā)程度；καm,n,w(TWi)為衛(wèi)星調(diào)度的啟發(fā)值；b為相應(yīng)的啟發(fā)值權(quán)重；κβm,n,w(TWi)為信道分配的啟發(fā)值；c為對(duì)應(yīng)的啟發(fā)值權(quán)重；κγm,n,w(TWi)為任務(wù)調(diào)度的啟發(fā)值；d為對(duì)應(yīng)的啟發(fā)值權(quán)重。b、c、d值的選取決定了算法的局部搜索能力。

3.3 信息素上下界的確定

在實(shí)際的優(yōu)化場(chǎng)景中，為了在有限次數(shù)的迭代之后找到最優(yōu)解，需要確定信息素值的上下界。在每次迭代的過程中，解集的更新必定會(huì)導(dǎo)致信息素值的更新，假設(shè)τ0為初始的信息素值，LF和UF分別為質(zhì)量函數(shù)的下界和上界，在N次迭代后可以計(jì)算出τi的上界為Uτ。

式(8)右側(cè)的第一項(xiàng)為揮發(fā)速率對(duì)信息素濃度的影響。式(9)為歸一化權(quán)重，其中，ηv和ηu表示與揮發(fā)速率成比例的權(quán)重值。同理，本文可以得到信息素下邊界為Lτ。當(dāng)?shù)螖?shù)較大時(shí)，(1 ?ρ)N(τ0?ηUF)→0，因此信息素上下界可以表示為ηu LF≤(τi)N≤ηUF。

3.4 適應(yīng)函數(shù)確定

對(duì)于資源調(diào)度的多目標(biāo)函數(shù)，采用線性加權(quán)的方式作為其適應(yīng)函數(shù)，如式(12)所示。

其中，χ1+χ2=1。在計(jì)算適應(yīng)度值之前將優(yōu)先級(jí)目標(biāo)函數(shù)和功耗目標(biāo)函數(shù)進(jìn)行歸一化，根據(jù)2 個(gè)目標(biāo)函數(shù)的重要程度來確定相應(yīng)的權(quán)值大小，在偏好關(guān)系上，f1的重要程度遠(yuǎn)比f2重要，因此對(duì)應(yīng)的權(quán)值關(guān)系為χ1?χ2。

3.5 額外信息素沉積

為了進(jìn)一步提高收斂速度，本文在每次迭代中將更新擴(kuò)展到有限元素，以便更多的解元素能夠更新它們的信息素值。本文提出了自適應(yīng)信息素更新方法，在所有選中的解集方案中，選擇部分解元素進(jìn)行額外的信息素沉積，主要思想是構(gòu)建一個(gè)質(zhì)量域BQ，如式(13)所示。

如果在質(zhì)量域中存在多于一個(gè)優(yōu)化解，則選取一個(gè)質(zhì)量值最大的作為chv{Γi}。最終，可以進(jìn)行一次額外的信息素值更新，如式(15)所示。

3.6 算法復(fù)雜度分析

對(duì)于螞蟻種群規(guī)模為G，迭代次數(shù)為Φ的資源調(diào)度問題，每個(gè)螞蟻個(gè)體是由二進(jìn)制變量集合所決定的。假設(shè)第N個(gè)區(qū)域的任務(wù)總數(shù)為YN，第i個(gè)時(shí)間窗口的任務(wù)調(diào)度窗口的個(gè)數(shù)為Xi，則算法的復(fù)雜度

由此可知，算法的時(shí)間復(fù)雜度與蟻群規(guī)模、迭代次數(shù)、地面任務(wù)負(fù)載輕重以及總的信道數(shù)目有關(guān)。在密集多波束組網(wǎng)時(shí)，地面任務(wù)負(fù)載較重，并且信道數(shù)目以及時(shí)間窗口不變，為了降低算法的時(shí)間復(fù)雜度，本文通過初始解集的構(gòu)造以及額外信息素的沉積加快了算法收斂速度，減少了迭代次數(shù)，因此大大降低了時(shí)間復(fù)雜度。

4 仿真以及結(jié)果分析

4.1 仿真過程實(shí)現(xiàn)

仿真分析基于5 顆衛(wèi)星（SAT1～SAT5）和7 個(gè)地面區(qū)域（Z1～Z7），衛(wèi)星的軌道高度和傾角如表1所示，仿真的時(shí)間段為00:00:00—06:00:00，地面任務(wù)區(qū)域彼此不重疊地分布于300 km×200 km的方格內(nèi)，利用STK 軟件對(duì)地面任務(wù)區(qū)域進(jìn)行可見性分析，可以獲得地面區(qū)域的任務(wù)調(diào)度窗口。資源調(diào)度過程仿真實(shí)現(xiàn)基于MATLAB R2019，在2 個(gè)時(shí)間窗口內(nèi)，衛(wèi)星對(duì)地面區(qū)域的覆蓋情況如圖3 所示，單個(gè)地面區(qū)域可能同時(shí)被多個(gè)衛(wèi)星所覆蓋，因此需要綜合考慮任務(wù)需求和衛(wèi)星現(xiàn)有的資源狀況來選擇合適的衛(wèi)星進(jìn)行資源調(diào)度，各個(gè)地面任務(wù)區(qū)域?qū)?yīng)的可視衛(wèi)星以及相應(yīng)優(yōu)先級(jí)的任務(wù)數(shù)如表2 所示，其中，Am(n)代表第m種優(yōu)先級(jí)對(duì)應(yīng)的任務(wù)數(shù)量為n。

表1 衛(wèi)星軌道參數(shù)

在仿真場(chǎng)景中，綜合考慮全球星、銥星、星鏈等實(shí)際在軌衛(wèi)星的單星參數(shù)及其平臺(tái)類型和未來密集多波束組網(wǎng)場(chǎng)景的用戶服務(wù)需求，假設(shè)5 顆衛(wèi)星的可用信道總數(shù)Ctotal為100，單個(gè)信道的功耗為20 W，每個(gè)衛(wèi)星所能提供的功耗Pm為400 W。在改進(jìn)的蟻群優(yōu)化算法中，螞蟻的數(shù)量為30，根據(jù)ACO算法參數(shù)設(shè)置[19]，信息速率的揮發(fā)速率ρ為0.03，適應(yīng)函數(shù)的權(quán)值χ1和χ2分別為0.64 和0.36，狀態(tài)轉(zhuǎn)移概率啟發(fā)權(quán)重a、b、c、d分別為2、4、2.5、0.5，額外信息素沉積的質(zhì)量域半徑δ為0.2。

圖3 衛(wèi)星對(duì)地面區(qū)域覆蓋情況

表2 各個(gè)地面任務(wù)區(qū)域?qū)?yīng)的可視衛(wèi)星以及相應(yīng)優(yōu)先級(jí)的任務(wù)數(shù)

為了分析所提算法的性能，本文首先選取調(diào)度完成的任務(wù)數(shù)以及調(diào)度完成的任務(wù)總優(yōu)先級(jí)作為評(píng)價(jià)指標(biāo)，將所提算法與傳統(tǒng)蟻群優(yōu)化算法進(jìn)行比較來分析算法的斂散性能，然后與智能蜂群算法[20]進(jìn)行對(duì)比，分析了所提算法在資源調(diào)度效率和功耗方面的優(yōu)化性能。智能蜂群算法作為一種群智能優(yōu)化算法，將求解優(yōu)化問題的過程轉(zhuǎn)化為蜂群尋找優(yōu)良蜜源的過程，通過智能調(diào)整轉(zhuǎn)移因子與狀態(tài)轉(zhuǎn)移變量來進(jìn)行優(yōu)化求解，能夠克服早熟現(xiàn)象，收斂速度快，相比于傳統(tǒng)蟻群優(yōu)化算法具有一定優(yōu)勢(shì)。

4.2 仿真結(jié)果分析

圖4(a)和圖4(b)分別給出了剩余任務(wù)數(shù)量和調(diào)度完成任務(wù)優(yōu)先級(jí)隨時(shí)間的變化，2 個(gè)時(shí)間窗口都為32 s，為了反映地面區(qū)域任務(wù)負(fù)載的變化情況，將2 個(gè)時(shí)間窗口的任務(wù)以及相應(yīng)的優(yōu)先級(jí)放在同一個(gè)坐標(biāo)系內(nèi)進(jìn)行比較，如圖4(a)所示，無論初始的任務(wù)負(fù)載有多重，剩余未完成的任務(wù)數(shù)量總能在20 s以后保持穩(wěn)定，從側(cè)面反映了在給定的約束條件下，算法的收斂時(shí)間大約為20 s。如圖4(b)所示，無論任務(wù)負(fù)載輕重，開始調(diào)度完成任務(wù)總的優(yōu)先級(jí)都相等，這是因?yàn)閯傞_始的時(shí)候系統(tǒng)資源充足，優(yōu)先級(jí)最大成為唯一約束，隨著時(shí)間的推移，系統(tǒng)資源消耗增加，此時(shí)需要與優(yōu)先級(jí)進(jìn)行綜合考慮，尋求總的效益最大化。

1) 算法斂散性能分析

算法的斂散性是衡量蟻群優(yōu)化算法的重要指標(biāo)，通過解集構(gòu)造以及額外信息素沉積將極大地提高算法的收斂速度，與傳統(tǒng)的蟻群優(yōu)化算法進(jìn)行比較，所提算法能更快地收斂到目標(biāo)值。如圖5(a)和圖5(b)所示，所提算法在經(jīng)過63 次迭代后完成收斂，而傳統(tǒng)的蟻群優(yōu)化算法需要87 次迭代，并且所提算法經(jīng)過迭代后剩余未調(diào)度完的任務(wù)數(shù)要少于傳統(tǒng)蟻群優(yōu)化算法，而調(diào)度完成任務(wù)總的優(yōu)先級(jí)要高于傳統(tǒng)蟻群優(yōu)化算法，可以看出所提算法的優(yōu)化性能也有一定程度的提高。

圖4 剩余任務(wù)數(shù)量和調(diào)度完成任務(wù)優(yōu)先級(jí)隨時(shí)間變化

圖5 剩余任務(wù)數(shù)量和調(diào)度完成任務(wù)優(yōu)先級(jí)隨迭代次數(shù)變化

2) 算法優(yōu)化性能分析

圖6 為3 種算法的未調(diào)度成功任務(wù)數(shù)量隨總?cè)蝿?wù)數(shù)量變化關(guān)系。從圖6 中可以看出，隨著總?cè)蝿?wù)數(shù)量的增加，未調(diào)度成功的任務(wù)數(shù)量也增加，這是由于系統(tǒng)資源有限，當(dāng)任務(wù)負(fù)載較重時(shí)，調(diào)度失敗的概率會(huì)大大增加，在相同的總?cè)蝿?wù)數(shù)量條件下，所提算法未調(diào)度成功的任務(wù)數(shù)量明顯低于其他2 種算法。

圖6 未調(diào)度成功任務(wù)數(shù)量隨總?cè)蝿?wù)數(shù)量變化關(guān)系

圖7 為3 種算法的功耗隨總?cè)蝿?wù)數(shù)量變化關(guān)系，在一定的功率約束下，系統(tǒng)總功耗隨著任務(wù)數(shù)量增加而增加，其中，所提算法在功耗性能方面表現(xiàn)最優(yōu)，分別減少了約29.13%和16.82%。

圖7 總功耗隨總?cè)蝿?wù)數(shù)量變化關(guān)系

圖8 為3 種算法的任務(wù)完成時(shí)間隨總?cè)蝿?wù)數(shù)量變化關(guān)系。從圖8 中可以看出，在不同的任務(wù)規(guī)模下，所提算法完成任務(wù)調(diào)度所需要的時(shí)間最短，從側(cè)面反映了所提算法的收斂速度最快?？傮w來說，無論是任務(wù)調(diào)度成功的數(shù)量、算法能耗還是任務(wù)完成時(shí)間，所提算法都優(yōu)于其他2 種算法，這主要是由于所提算法進(jìn)行了初始解集構(gòu)造、基于質(zhì)量域的精英選擇機(jī)制以及額外信息素沉積，能夠在迭代的過程中快速找出優(yōu)秀個(gè)體，并且將其保留，使算法快速收斂到最優(yōu)解。

圖8 任務(wù)完成時(shí)間隨總?cè)蝿?wù)數(shù)量變化關(guān)系

5 結(jié)束語

衛(wèi)星通信系統(tǒng)是未來空天地大規(guī)模移動(dòng)網(wǎng)絡(luò)的重要組成部分，在密集多波束組網(wǎng)過程中，需要在滿足用戶需求前提下對(duì)有限的網(wǎng)絡(luò)資源進(jìn)行調(diào)度。本文首先分析了密集多波束組網(wǎng)場(chǎng)景下衛(wèi)星通信系統(tǒng)資源調(diào)度的約束條件，建立了多目標(biāo)優(yōu)化資源調(diào)度模型，然后提出了一種以初始解集構(gòu)造和額外信息素沉積為核心的改進(jìn)蟻群優(yōu)化算法用于求解衛(wèi)星資源調(diào)度問題。仿真結(jié)果表明，所提算法在資源調(diào)度方面具有良好的斂散性能和優(yōu)化性能，能夠有效地解決密集多波束組網(wǎng)時(shí)衛(wèi)星通信系統(tǒng)的資源調(diào)度問題。當(dāng)然，衛(wèi)星通信系統(tǒng)的資源調(diào)度還會(huì)受到其他約束條件的影響，包括大氣環(huán)境影響、信道干擾等，此類問題有待進(jìn)一步研究。