基于智能水滴算法的衛(wèi)星信道資源調度研究

段超凡，王 銳,2

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

0 引言

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

通信衛(wèi)星作為空間衛(wèi)星通信系統(tǒng)的重要組成部分，可以為地面用戶提供良好的信息傳輸服務功能。單顆部署于地球同步軌道的衛(wèi)星可以覆蓋40%的地球面積，3顆衛(wèi)星即可實現(xiàn)全球覆蓋，使覆蓋區(qū)域內處于任何位置的用戶可以通過衛(wèi)星實現(xiàn)實時通信，特別是對于基站難以覆蓋的海上及偏遠地區(qū)，衛(wèi)星通信可以為這部分用戶提供良好的通信服務。然而，由于衛(wèi)星的星上資源有限，當?shù)孛嬗脩舻男畔鬏斝枨筝^大、超出衛(wèi)星可最大服務用戶的能力時，需要制定相應的策略，優(yōu)先傳輸重要的信息。特別是針對多波束衛(wèi)星，如何分配有限的衛(wèi)星資源和衛(wèi)星天線給完成不同優(yōu)先級的信息傳輸任務，是衛(wèi)星信道資源調度問題研究的重點。

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

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

1 問題描述及建模

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

記S為衛(wèi)星節(jié)點，對于所有衛(wèi)星節(jié)點，可表示為：

其中，表示可用的衛(wèi)星數(shù)目。同時對于單顆衛(wèi)星，根據(jù)衛(wèi)星星上性能，構造其狀態(tài)信息：

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

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

其中，代表需要完成的數(shù)據(jù)傳輸任務數(shù)目。對于每個需要完成的數(shù)據(jù)任務，根據(jù)任務需求，構造其任務狀態(tài)信息：

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

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

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

2 基于智能水滴算法的衛(wèi)星信道資源調度

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

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

2.1 初始化階段

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

2.2 路徑選擇階段

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

其中，為非負數(shù)，為防止該值為0。

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

2.3 局部泥土量更新階段

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

路徑中的泥土量變化為：

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

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

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

2.4 全局泥土量更新階段

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

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

3 仿真實驗及結果分析

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

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

圖1 未完成任務權值圖

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

圖2 任務執(zhí)行時間圖

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

圖3 任務執(zhí)行甘特圖

4 結語

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