面向密集多波束組網的衛星通信系統資源調度算法

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

（1.軍事科學院系統工程研究院，北京 100141；2.空軍工程大學信息與導航學院，陜西 西安 710077；3.北京理工大學通信與網絡實驗室，北京 100081）

1 引言

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

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

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

基于上述考慮，本文分析了密集多波束組網場景下衛星通信系統資源調度的約束條件，建立了多目標資源調度模型，綜合考慮了現有蟻群優化算法的優缺點，并針對存在的缺點，提出了以初始解集構造和額外信息素沉積為核心的改進蟻群優化算法，最后設計了仿真場景對模型和算法進行了仿真驗證。

2 衛星通信系統資源調度問題建模

在衛星通信系統中，隨著衛星在軌移動，其覆蓋范圍將發生變化，對應的業務負載以及優先級也會隨之變化。為了滿足不斷變化的地面任務需求，需要對衛星資源、信道資源以及時隙資源進行合理調度，資源調度問題主要受到時間窗口約束、衛星功耗約束、信道數量約束、地面用戶優先級以及突發性等條件影響，其目標是在滿足這些約束條件的前提下，保證系統的功耗盡可能小，調度完成的高優先級的任務盡可能多。

2.1 系統模型

衛星通信系統的資源調度場景如圖1 所示。衛星通信系統由M顆多波束通信衛星組成，對地面用戶進行動態覆蓋，不同衛星波束的覆蓋區域之間存在一定的重疊。將系統所能覆蓋的區域范圍劃分為N個地面區域，通信任務根據其發起用戶所在位置分別歸屬于不同的地面區域。

圖1 衛星通信系統的資源調度場景示意

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

在時間窗口TWi中，來自第n個地面區域的通信任務可以表示為一個五元數組，即

2.2 資源調度模型

基于以上對系統模型的分析，以地面任務服務質量以及衛星通信系統的總功耗為目標，本文建立了如式(1)所示的衛星通信資源調度模型。

上述模型中，目標函數 O1表示在2 個時間窗口內衛星通信系統盡可能完成多個高優先級任務的傳輸，即調度完成的高優先級業務總和的倒數最小；目標函數 O2代表2 個時間窗口內系統總功耗最小，總功耗主要由2 個部分組成，第一部分為任務傳輸功耗，第二部分為切換功耗。其中，Pms為單位時間切換的功率大小，Tms為連續執行資源調度需要最大切換時間，只有當=1時，不需要進行衛星切換，即。

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

在整個資源調度過程中，進行如下假設。

1) 2 個時間窗口的任務傳輸與資源調度相互獨立，任務傳輸具有連續性，并且只在時間窗口內進行，如果任務傳輸的終止時間超過了時間窗口的終止時間，則判定任務傳輸失敗。

2) 第一個時間窗口結束后，需要對任務集合進行更新，下一個時間窗口不同區域的突發性大小主要影響任務傳輸所需要的時隙數，“熱點”性強弱主要影響任務的優先級。

3) 信道分配取決于任務需求，前提是不能超過信道總數，在進行任務傳輸的時候，忽略信道損耗對功耗的影響。

2.3 資源調度問題分析

通過觀察上述資源優化問題的數學模型，2 個優化目標函數雖然在求解參數上并不強相關，但由于優先級加權和與功耗同處于N個地面區域和M個衛星提供服務的約束之下，使約束條件空間的參數下標之間存在相關性，導致使數學模型中2 個優化目標之間具有強耦合特性，因此，2 個優化目標不能拆解為單獨的優化目標函數求解。

實際上，上述問題的關鍵在于目標函數 O1中的優先級權重，若只考慮目標函數 O2，其最小值的解集空間為考慮優先級權重，在業務量大于系統可調度資源時，可能導致為了節約功耗放棄部分高優先級業務調度的問題，即最低功耗解不一定是最高優先級加權和任務完成度的解。因此，上述優化函數的數學含義是尋找優先級加權和任務完成度和功耗之間的折中。但由于2 個優化問題的參數空間的強耦合特性，無法通過簡單的參數代入推導獲得解析解，也無法通過參數空間合并轉化為單目標優化問題再通過凸優化方法求解。針對這類問題，數學上通常通過遍歷搜索的方法來求解。

然而，遍歷搜索的方式由于要窮舉解集空間，其算法復雜度與解集空間的大小強相關。首先，分析目標函數 O1，其中，任務傳輸完成標識具備2個狀態0 和1，即對于x個該類標識的組合，組合可能為2x個，那么，O1解空間大小為

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

3 衛星通信資源調度算法設計

基于對蟻群優化算法優缺點的綜合考慮，本文以提高算法初期搜索速度和局部搜索能力目標，提出一種改進的蟻群優化算法來解決多約束條件下的衛星通信系統資源調度問題，算法流程如圖2所示。

3.1 初始解集構造以及信息素的更新

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

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

我州每年會有大量農村初中畢業生直接進入勞動力市場，既降低了勞動者素質，又影響了經濟發展質量。據調查，我州近幾年專業技能人才缺口上萬人，而職業教育輸送的人才數量遠不能滿足經濟社會發展需要。因此，高素質技能型人才短缺依然是產業發展的瓶頸。

圖2 衛星通信系統資源調度算法流程

3.2 狀態轉移概率的確定

對于時間窗口TWi，假設τm,n,w為第m顆衛星通過信道w完成對區域n中的調度任務的信息素濃度，則轉移概率式為

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

3.3 信息素上下界的確定

在實際的優化場景中，為了在有限次數的迭代之后找到最優解，需要確定信息素值的上下界。在每次迭代的過程中，解集的更新必定會導致信息素值的更新，假設τ0為初始的信息素值，LF和UF分別為質量函數的下界和上界，在N次迭代后可以計算出τi的上界為Uτ。

式(8)右側的第一項為揮發速率對信息素濃度的影響。式(9)為歸一化權重，其中，ηv和ηu表示與揮發速率成比例的權重值。同理，本文可以得到信息素下邊界為Lτ。當迭代次數較大時，(1 ?ρ)N(τ0?ηUF)→0，因此信息素上下界可以表示為ηu LF≤(τi)N≤ηUF。

3.4 適應函數確定

對于資源調度的多目標函數，采用線性加權的方式作為其適應函數，如式(12)所示。

其中，χ1+χ2=1。在計算適應度值之前將優先級目標函數和功耗目標函數進行歸一化，根據2 個目標函數的重要程度來確定相應的權值大小，在偏好關系上，f1的重要程度遠比f2重要，因此對應的權值關系為χ1?χ2。

3.5 額外信息素沉積

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

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

3.6 算法復雜度分析

對于螞蟻種群規模為G，迭代次數為Φ的資源調度問題，每個螞蟻個體是由二進制變量集合所決定的。假設第N個區域的任務總數為YN，第i個時間窗口的任務調度窗口的個數為Xi，則算法的復雜度

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

4 仿真以及結果分析

4.1 仿真過程實現

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

表1 衛星軌道參數

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

圖3 衛星對地面區域覆蓋情況

表2 各個地面任務區域對應的可視衛星以及相應優先級的任務數

為了分析所提算法的性能，本文首先選取調度完成的任務數以及調度完成的任務總優先級作為評價指標，將所提算法與傳統蟻群優化算法進行比較來分析算法的斂散性能，然后與智能蜂群算法[20]進行對比，分析了所提算法在資源調度效率和功耗方面的優化性能。智能蜂群算法作為一種群智能優化算法，將求解優化問題的過程轉化為蜂群尋找優良蜜源的過程，通過智能調整轉移因子與狀態轉移變量來進行優化求解，能夠克服早熟現象，收斂速度快，相比于傳統蟻群優化算法具有一定優勢。

4.2 仿真結果分析

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

1) 算法斂散性能分析

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

圖4 剩余任務數量和調度完成任務優先級隨時間變化

圖5 剩余任務數量和調度完成任務優先級隨迭代次數變化

2) 算法優化性能分析

圖6 為3 種算法的未調度成功任務數量隨總任務數量變化關系。從圖6 中可以看出，隨著總任務數量的增加，未調度成功的任務數量也增加，這是由于系統資源有限，當任務負載較重時，調度失敗的概率會大大增加，在相同的總任務數量條件下，所提算法未調度成功的任務數量明顯低于其他2 種算法。

圖6 未調度成功任務數量隨總任務數量變化關系

圖7 為3 種算法的功耗隨總任務數量變化關系，在一定的功率約束下，系統總功耗隨著任務數量增加而增加，其中，所提算法在功耗性能方面表現最優，分別減少了約29.13%和16.82%。

圖7 總功耗隨總任務數量變化關系

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

圖8 任務完成時間隨總任務數量變化關系

5 結束語

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