基于智能水滴算法的衛星信道資源調度研究

段超凡，王 銳,2

（1.國防科技大學氣象海洋學院，長沙 410073；2.國防科技大學信息通信學院，武漢 430019）

0 引言

隨著航天技術、材料技術、微電子和通信技術的不斷發展，衛星作為空間信息獲取的主要載體已經受到了業界的廣泛關注，從功能角度可以分為通信衛星、遙感衛星、環境探測衛星和導航衛星等。自1957 年蘇聯發射了第一顆人造衛星斯普特尼克1號起，世界各國在爭奪衛星空間資源上各展其能，發射了各式各樣的衛星。

通信衛星作為空間衛星通信系統的重要組成部分，可以為地面用戶提供良好的信息傳輸服務功能。單顆部署于地球同步軌道的衛星可以覆蓋40%的地球面積，3顆衛星即可實現全球覆蓋，使覆蓋區域內處于任何位置的用戶可以通過衛星實現實時通信，特別是對于基站難以覆蓋的海上及偏遠地區，衛星通信可以為這部分用戶提供良好的通信服務。然而，由于衛星的星上資源有限，當地面用戶的信息傳輸需求較大、超出衛星可最大服務用戶的能力時，需要制定相應的策略，優先傳輸重要的信息。特別是針對多波束衛星，如何分配有限的衛星資源和衛星天線給完成不同優先級的信息傳輸任務，是衛星信道資源調度問題研究的重點。

研究人員針對上述問題提出了一系列的解決方法，通過地面指控中心集合各類信息傳輸需求提高衛星面對突發情況的快速響應能力，通過指控中心與衛星間的配合最大化完成信息傳輸任務。趙靜等利用改進的NSGA 算法對微波/激光混合鏈路的多目標資源調度進行了研究，實驗證明了該方法的有效性；田志新等提出利用有向圖模型在線生成任務指令；賀川等利用最小時間窗口約束，將不同任務分配至不同的時間窗口。其他研究人員將信道資源調度問題抽象成整數規劃模型、被曝模型和其他模型進行求解，均取得了較好的實驗結果。

本文針對衛星信道資源調度問題，構建了多目標約束規劃模型，利用智能水滴算法對該問題進行求解。在建模過程中考慮了不同用戶的優先級和數據傳輸任務的特點，并對所提出的算法進行了實驗驗證。仿真結果表明，該算法能夠為衛星分配合適的數據傳輸任務，有效解決衛星信道資源調度問題。

1 問題描述及建模

衛星信道資源調度問題受到信息傳輸任務的數量、優先級及任務時間窗等因素的約束，同時還需考慮到可用的衛星集合和有限的衛星天線及信道資源約束，可以抽象成多目標約束問題。解決該問題的主要思想是盡可能完成任務優先級較高的信息傳輸任務，并在此基礎上盡可能多地完成信息傳輸任務，為了方便模型建立，作出如下定義：

記S為衛星節點，對于所有衛星節點，可表示為：

其中，表示可用的衛星數目。同時對于單顆衛星，根據衛星星上性能，構造其狀態信息：

其中，為該衛星所分配的數據傳輸任務，為衛星天線資源集合，包含天線數目和數據傳輸速率，為衛星存儲能量，每執行完一次數據傳輸任務需要消耗一定的星上能量。

記M為需要完成的數據傳輸任務，對于所有需要完成的任務，可以表示為：

其中，代表需要完成的數據傳輸任務數目。對于每個需要完成的數據任務，根據任務需求，構造其任務狀態信息：

對于每個需要完成的傳輸任務，T,T分別為任務開始時間和任務結束時間，衛星需要在任務開始后，在任務結束前完成信息傳輸任務；t為執行該任務的任務開始時間；d為任務傳輸時間；p代表任務的優先級；E代表傳輸該任務所需要花費的星上能量；x表示該任務是否被執行，若任務被執行則x= 0，否則x= 1。

基于上述定義，建立衛星資源調度的多目標約束模型：

在本文中，優化的目標是優先完成優先級高的數據傳輸任務，也就是最小化不能完成任務的總共的優先級，共有三個約束條件。其中，約束條件1 代表每個數據傳輸任務只被完成一次；約束條件2代表衛星在執行數據傳輸任務前需要滿足剩余能量約束；約束條件3代表每個任務的開始執行時間和完成時間需要在任務時間窗的范圍之內。

2 基于智能水滴算法的衛星信道資源調度

智能水滴算法（intelligent water drops algorithm，IWD）是由Hamed Shah-Hosseini 于2007年提出的一種群體智能算法，該算法的設計思想來源于自然界中水流的運動。若只考慮重力對水流的影響，水滴將會從高處流向低處，水滴的運動軌跡是一條從起始點到終點的直線路徑。然而在水滴的運動過程中會受到阻力和障礙物的影響，改變路徑軌跡。在前人的研究工作中，智能水滴算法已經被應用于工程科學領域等眾多問題的求解中，顯示出巨大的優勢。

在自然界中，若不存在阻力和障礙物的影響，水流的路徑將是一條理想路徑，同時該從起點到終點的直線是最短路徑，并且當水流受到障礙物的影響時，也會使改變的路徑盡可能地接近于理想路徑。每個水滴在進行路徑選擇時，將會受到路徑中障礙物的影響，在該算法中考慮的是路徑中的泥土量。路徑中的泥土量越大，路徑對水滴的阻力效果越大，水滴選擇這條路徑的概率也就越低。同時，當水滴經過路徑時將會帶走部分路徑中的泥土量，使得后續水滴在進行路徑選擇時更有可能選擇這條路徑。水滴在進行路徑選擇時將根據概率選擇下一步運動的路徑，這在一定程度上避免了算法陷入局部最優。智能水滴算法主要分為四個階段，分別是初始化階段、路徑選擇階段、局部泥土量更新階段和全局泥土量更新階段。

2.1 初始化階段

在初始化階段中，需要確定可利用進行數據傳輸的衛星集合，所需完成的數據傳輸任務集合，以及對應的相關參數；智能水滴的個數N，智能水滴的初始速度v，速度更新參數a、b、c，泥土量更新參數a、b、c，局部泥土量更新參數，全局泥土量更新參數和路徑泥土量矩陣。

2.2 路徑選擇階段

將每個衛星當做一個智能水滴，在初始狀態時，每個衛星根據其擁有的天線數量及信道資源隨機選取一個任務進行數據傳輸，并對應更新信道占用情況和任務執行情況。每個任務都被視作為路徑中的節點，節點的選擇概率計算為：

其中，為非負數，為防止該值為0。

根據每個備選節點（下一個可執行的數據傳輸任務）的選擇概率，采用輪盤賭注的方法去選擇下一個任務節點，并更新已訪問節點和未訪問節點。當前衛星的天線及信道資源被全部分配完成后，則構建生成了該衛星的任務調度方案，將剩余未執行的數據傳輸任務分配給后續各衛星直至生成所有的衛星任務分配方案，并計算各方案對應的目標函數值。

2.3 局部泥土量更新階段

完成節點選擇后，水滴將訪問該節點。節點間的泥土量、水滴速度和衛星剩余星上能量等都將發生變化。假設在時刻，水滴位于節點p，并且在+1時刻運動到節點p，水滴的速度變化計算為：

路徑中的泥土量變化為：

其中，Δ(p,p)為泥土量的變化量，ρ為局部泥土更新參數，是介于0到1的一個常數。

同時，水滴攜帶的泥土量更新為：

該值的計算由水滴的運動速度和運動時間共同決定，表示如下：

2.4 全局泥土量更新階段

在每一次迭代中，根據水滴構成的可行解，計算目標函數值，并找到目標函數值最小的解作為該次迭代過程中的最優解，并將最優解路徑中的泥土量矩陣作為下一次迭代的初始泥土量矩陣，全局泥土量更新計算為：

這樣，在每一次迭代過程中都能獲得本次迭代的最優解，并且將之與歷史最優解進行對比，若獲得的目標函數值小于全局最優解，則進行更新，當運行到最大迭代次數時，可以獲得該問題的最優解輸出。

3 仿真實驗及結果分析

利用Maltab 仿真軟件對所提出的衛星資源調度算法進行了實驗驗證，所設計的實驗場景中包含3顆衛星用于完成數據傳輸任務，三顆衛星的天線數據傳輸速率分別為200 Mb/s，300 Mb/s和500 Mb/s，總共數據傳輸任務為64 個。仿真實驗分別對每次迭代過程中未完成的任務數、任務執行時間等進行了分析。

從圖1可以看出，隨著迭代次數的增加，未完成的任務權值數逐漸減少。由于衛星天線及信道資源有限，難以做到完成所由任務，算法通過不斷迭代有效降低了未完成任務的權值，達到了預計目標。

圖1 未完成任務權值圖

由于不同衛星的信息傳輸能力有所差異，傳輸能力強的衛星可以在較短時間內完成信息傳輸任務，但是在實驗場景中仍不能通過單顆衛星完成所有的信息傳輸任務，需要通過3顆衛星共同配合減少總任務完成時間。從圖2可以看出，隨著迭代次數的增加，任務執行時間逐步降低。

圖2 任務執行時間圖

圖3為任務執行甘特圖，不同顏色色塊代表衛星的任務執行次序，可以看出算法所規劃的信息傳輸任務能夠較好地利用衛星資源，保持各任務間不發生沖突的同時，最大化地利用有限的衛星資源。

圖3 任務執行甘特圖

4 結語

本文提出了基于智能水滴算法的衛星信道資源調度算法，在可以利用的衛星資源有限的情況下，優先執行任務優先級較高的數據傳輸任務，在保證數據傳輸任務不沖突的情況下，盡可能多地完成任務。所提出的智能水滴算法分為數據初始化、路徑選擇、局部泥土量更新和全局泥土量更新四個階段，通過不斷迭代優化調度方案，最后利用實驗證明了算法的有效性。