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

段超凡，王 銳,2

（1.國(guó)防科技大學(xué)氣象海洋學(xué)院，長(zhǎng)沙 410073；2.國(guó)防科技大學(xué)信息通信學(xué)院，武漢 430019）

0 引言

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

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

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

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

1 問題描述及建模

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

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

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

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

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

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

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

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

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

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

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

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

2.1 初始化階段

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

2.2 路徑選擇階段

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

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

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

2.3 局部泥土量更新階段

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

路徑中的泥土量變化為：

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

同時(shí)，水滴攜帶的泥土量更新為：

該值的計(jì)算由水滴的運(yùn)動(dòng)速度和運(yùn)動(dòng)時(shí)間共同決定，表示如下：

2.4 全局泥土量更新階段

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

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

3 仿真實(shí)驗(yàn)及結(jié)果分析

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

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

圖1 未完成任務(wù)權(quán)值圖

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

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

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

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

4 結(jié)語(yǔ)

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