基于改進(jìn)QPSO算法的GEO衛(wèi)星時(shí)頻資源調(diào)度

高 威，瞿連政，王 磊

(國防科技大學(xué) 信息通信學(xué)院，湖北 武漢 430014)

0 引言

靜止軌道(Geostationary Orbit,GEO)通信衛(wèi)星具有通信覆蓋區(qū)域大、通信距離遠(yuǎn)、性能穩(wěn)定、可在邊遠(yuǎn)地區(qū)部署、不依賴于地面基礎(chǔ)設(shè)施等優(yōu)點(diǎn)，在國際國內(nèi)通信、軍事通信和移動(dòng)通信等領(lǐng)域具有重要的作用[1]。隨著通信任務(wù)需求的增多，不同用戶間的通信請(qǐng)求可能存在時(shí)間窗口和頻帶沖突，對(duì)于短時(shí)間內(nèi)的大量任務(wù)請(qǐng)求，手動(dòng)計(jì)算衛(wèi)星資源的調(diào)度方案變得非常復(fù)雜[2]。在衛(wèi)星資源有限的情況下，如何設(shè)計(jì)有效的資源調(diào)度模型和算法來提高時(shí)頻資源調(diào)度效率，保障通信任務(wù)完成并最大化系統(tǒng)效能成為當(dāng)下研究的熱點(diǎn)問題。

在調(diào)度模型與算法方面，文獻(xiàn)[3]建立了基于任務(wù)資源匹配的整數(shù)規(guī)劃模型，使用蟻群算法進(jìn)行了求解；文獻(xiàn)[4]采用任務(wù)優(yōu)先級(jí)和時(shí)間靈活度加權(quán)的啟發(fā)式信息，提出了加入虛擬任務(wù)的改進(jìn)蟻群算法，具有較好的尋優(yōu)能力和穩(wěn)定性；文獻(xiàn)[5]在max-min蟻群系統(tǒng)的基礎(chǔ)上，提出了一種簡(jiǎn)化蟻群優(yōu)化算法，設(shè)計(jì)了新的信息素模型使得算法具有更平衡的探索能力和開發(fā)能力；文獻(xiàn)[6]分析了靜態(tài)調(diào)度模型和動(dòng)態(tài)調(diào)度模型的調(diào)度目標(biāo)和約束條件，采用了改進(jìn)的海洋捕食者算法求解衛(wèi)星的任務(wù)調(diào)度；文獻(xiàn)[7]將衛(wèi)星資源調(diào)度問題轉(zhuǎn)化為任務(wù)排序問題，并利用遺傳算法求解最優(yōu)任務(wù)序列。

在調(diào)度策略方面，文獻(xiàn)[3]采用基于任務(wù)和資源優(yōu)先級(jí)的“任務(wù)-資源”匹配規(guī)則；文獻(xiàn)[4]提出了時(shí)頻資源窗口更新方法，按照“低頻帶優(yōu)先，時(shí)間靠前優(yōu)先”的原則分配時(shí)頻資源，但該方法計(jì)算復(fù)雜度較高；文獻(xiàn)[7]采用時(shí)間步長(zhǎng)調(diào)整的方式進(jìn)行任務(wù)資源的匹配；文獻(xiàn)[8]采用基于任務(wù)時(shí)間窗口更新的調(diào)度策略，分析了5種不同的時(shí)間窗口沖突情況，并給出了剩余任務(wù)時(shí)間窗口的更新方法；文獻(xiàn)[9]將蟻群算法的路徑點(diǎn)設(shè)置為任務(wù)的時(shí)間片，并設(shè)計(jì)了帶偏好的衛(wèi)星時(shí)間片切割策略。

綜上所述，現(xiàn)有研究主要是將一維時(shí)間窗或二維時(shí)頻塊作為調(diào)度資源，采用以任務(wù)資源窗口更新[4,8-9]和任務(wù)資源匹配規(guī)則為核心的調(diào)度策略，建立數(shù)學(xué)規(guī)劃模型或約束滿足問題(Constraint Satisfaction Problem,CSP)模型，并利用改進(jìn)的蟻群算法[3-5,9]、海洋捕食者算法[6]和遺傳算法[7-8]等元啟發(fā)式算法(Meta-heuristic Algorithm)進(jìn)行求解。綜合來看，任務(wù)資源窗口更新方法的計(jì)算復(fù)雜度較高；離散化編碼的元啟發(fā)式算法易陷入局部最優(yōu)，而全局性能更好的連續(xù)型元啟發(fā)式算法則不能直接用于時(shí)頻資源調(diào)度問題，需要采用合適的編解碼規(guī)則。針對(duì)GEO通信衛(wèi)星的時(shí)頻資源調(diào)度問題及現(xiàn)有研究存在的不足，本文所做的工作如下：

① 將衛(wèi)星轉(zhuǎn)發(fā)器的二維時(shí)頻資源進(jìn)行量化處理，建立了基于CSP的衛(wèi)星時(shí)頻資源調(diào)度模型，并設(shè)計(jì)了以任務(wù)序列生成和任務(wù)資源匹配為主要步驟的調(diào)度流程；

② 針對(duì)任務(wù)資源窗口更新方法計(jì)算復(fù)雜度高的問題，提出了基于資源矩陣更新的調(diào)度策略，將任務(wù)資源匹配過程轉(zhuǎn)化為矩陣的Hadamard乘積計(jì)算，有效降低了任務(wù)資源匹配的計(jì)算復(fù)雜度，縮短了算法的執(zhí)行時(shí)間；

③ 針對(duì)常用的蟻群算法和遺傳算法易陷入局部最優(yōu)的問題，提出了改進(jìn)的量子粒子群算法，采用了實(shí)數(shù)編碼、最小位置值解碼和初始解優(yōu)化方法，提升了算法的全局優(yōu)化性能；

④ 對(duì)所提調(diào)度策略和改進(jìn)算法進(jìn)行了仿真實(shí)驗(yàn)，分析了不同量化帶寬和調(diào)度策略對(duì)執(zhí)行時(shí)間、調(diào)度結(jié)果的影響，對(duì)比分析了本文所提算法與當(dāng)前幾種典型的時(shí)頻資源調(diào)度算法的性能差異。

1 GEO通信衛(wèi)星資源調(diào)度模型

1.1 問題背景

從用戶的角度，當(dāng)用戶組網(wǎng)通信時(shí)，首先需要向衛(wèi)星資源管理中心提交任務(wù)申請(qǐng)，提交信息包括用戶位置、用網(wǎng)時(shí)間、申請(qǐng)帶寬、業(yè)務(wù)類型及終端信息等，然后等待衛(wèi)星資源管理中心分配資源并使用分配的資源開展通信業(yè)務(wù)；從衛(wèi)星資源管理中心的角度，調(diào)度系統(tǒng)需要管理資源池和任務(wù)池，接收多個(gè)用戶的任務(wù)資源申請(qǐng)，并根據(jù)資源池和任務(wù)池狀態(tài)，選擇合適的調(diào)度模型和調(diào)度算法進(jìn)行資源調(diào)度，生成優(yōu)化調(diào)度方案[6]。因此，決定資源調(diào)度性能的關(guān)鍵是調(diào)度模型和調(diào)度算法。通信衛(wèi)星資源調(diào)度的架構(gòu)如圖1所示。

圖1 通信衛(wèi)星資源調(diào)度架構(gòu)

將調(diào)度問題按調(diào)度周期進(jìn)行劃分，并對(duì)調(diào)度資源采用量化處理，其中調(diào)度周期的長(zhǎng)度和通信資源劃分的粒度可以靈活調(diào)整，以適用于不同的問題場(chǎng)景。從資源管理和分配的角度，衛(wèi)星管理中心的資源調(diào)度系統(tǒng)主要進(jìn)行的操作有：

① 執(zhí)行上一周期結(jié)束時(shí)生成的調(diào)度方案。

② 監(jiān)控資源池中資源的狀態(tài)，將執(zhí)行完任務(wù)后被釋放的資源更新到資源池，對(duì)資源的狀態(tài)進(jìn)行標(biāo)記。資源狀態(tài)分為占用、已分配待使用、空閑和不可用等。

③ 監(jiān)控任務(wù)池中任務(wù)的狀態(tài)，刪除無法執(zhí)行的任務(wù)，接收新任務(wù)申請(qǐng)并更新到任務(wù)池。對(duì)任務(wù)的狀態(tài)進(jìn)行標(biāo)記，分為執(zhí)行結(jié)束、執(zhí)行中、已分配資源待執(zhí)行、拒絕執(zhí)行和新接收待分配資源等。

④ 在調(diào)度周期結(jié)束時(shí)依據(jù)任務(wù)池、資源池狀態(tài)，選擇調(diào)度模型和調(diào)度算法進(jìn)行資源調(diào)度，生成下一個(gè)周期的調(diào)度方案。

本文所研究的GEO通信衛(wèi)星時(shí)頻資源調(diào)度模型、算法及策略，主要適用于2種場(chǎng)景：① 在使用大張角波束的傳統(tǒng)寬帶通信衛(wèi)星場(chǎng)景中，對(duì)固定的組網(wǎng)通信業(yè)務(wù)進(jìn)行任務(wù)規(guī)劃和資源調(diào)度；② 在使用多波束技術(shù)的高通量衛(wèi)星場(chǎng)景中，可根據(jù)波束覆蓋用戶的情況，將多波束的資源調(diào)度問題分解為各個(gè)單波束內(nèi)的資源調(diào)度子問題，實(shí)現(xiàn)對(duì)時(shí)隙和帶寬資源的聯(lián)合調(diào)度。主要聚焦于對(duì)第1個(gè)場(chǎng)景進(jìn)行研究，但二維資源量化的框架與元啟發(fā)式算法的應(yīng)用模式，可以應(yīng)用于第2種問題場(chǎng)景；在調(diào)度資源上，聚焦于時(shí)頻資源調(diào)度，即時(shí)隙-帶寬資源塊與任務(wù)的匹配，而簡(jiǎn)化中心頻率設(shè)置、載波分配或信道劃分等情況。

1.2 時(shí)頻資源量化

衛(wèi)星轉(zhuǎn)發(fā)器的資源存在時(shí)間、頻率、功率等多個(gè)調(diào)度要素，本文以經(jīng)過量化的二維時(shí)頻資源作為調(diào)度資源。時(shí)頻資源的量化處理方式[4,7-8,10-12]可適用于多種技術(shù)體制，如頻分多址、時(shí)分多址和多頻時(shí)分多址(Multi-frequency Time Division Multiple Access,MF-TDMA)等。

設(shè)定任務(wù)集合T與衛(wèi)星轉(zhuǎn)發(fā)器資源集合S是嚴(yán)格對(duì)應(yīng)的?？蓪尾ㄊ采w范圍內(nèi)同頻段用戶終端的任務(wù)請(qǐng)求整合為任務(wù)集，而將該波束內(nèi)的單個(gè)或多個(gè)轉(zhuǎn)發(fā)器的可用時(shí)頻資源整合為資源集。要求任務(wù)提交的資源申請(qǐng)以資源最小量化分辨率為單位，并表示為時(shí)頻區(qū)間的集合。轉(zhuǎn)發(fā)器的時(shí)頻資源如圖2所示，以1 MHz和1 h進(jìn)行量化時(shí)，資源集可表示為{[0,4],[0,5]}，其中任務(wù)4占用的資源塊可表示為{[1,3],[1,2]}。因此，可將時(shí)頻資源調(diào)度問題抽象為數(shù)學(xué)上的二維裝箱問題，該問題已被證明為是一個(gè)NP-Hard問題[13]。

圖2 轉(zhuǎn)發(fā)器的時(shí)頻資源

本文主要研究無突發(fā)情況的靜止調(diào)度場(chǎng)景，即不考慮衛(wèi)星故障、任務(wù)插入和任務(wù)取消等突發(fā)情況。問題場(chǎng)景的基本假設(shè)為：① 調(diào)度期間所有待調(diào)度任務(wù)的用戶均在轉(zhuǎn)發(fā)器所屬波束的覆蓋范圍內(nèi)，且通信質(zhì)量良好，不考慮用戶終端的移動(dòng)性；② 任務(wù)申請(qǐng)的時(shí)頻資源塊個(gè)數(shù)必須為整數(shù)，任務(wù)不能被分割執(zhí)行；③ 任務(wù)經(jīng)過調(diào)度嘗試后的狀態(tài)分為調(diào)度成功和調(diào)度失敗2種，將調(diào)度成功的任務(wù)優(yōu)先級(jí)之和作為調(diào)度效能指標(biāo)，即調(diào)度收益；④ 當(dāng)任務(wù)分配的時(shí)頻資源不存在沖突時(shí)，轉(zhuǎn)發(fā)器可同時(shí)執(zhí)行多個(gè)任務(wù)。

1.3 基于CSP的調(diào)度模型

CSP可以描述為：給定一組變量及它們的值域，找到一個(gè)滿足所有約束的變量的解，并盡可能使解的質(zhì)量更優(yōu)[14]?；贑SP的調(diào)度模型所使用的符號(hào)如下：

S={B,TE}表示轉(zhuǎn)發(fā)器的時(shí)頻資源總量；

B=[Bstr,Bend]表示轉(zhuǎn)發(fā)器的頻率資源；

TE=[TEstr,TEend]表示轉(zhuǎn)發(fā)器的時(shí)間資源；

RS={BS,DS}表示任務(wù)所需的帶寬資源和時(shí)間資源，BS和DS分別表示未經(jīng)過量化處理的帶寬大小和時(shí)間長(zhǎng)度；

Nb=(Bend-Bstr)/δB表示轉(zhuǎn)發(fā)器資源進(jìn)行量化后的頻帶個(gè)數(shù)，δB表示量化頻帶的帶寬；

Nt=(TEend-TEstr)/δt表示轉(zhuǎn)發(fā)器資源量化后的時(shí)間區(qū)間個(gè)數(shù)，δt表示量化時(shí)間的間隔；

T={T1,T2,…,Tj,…,TM}表示任務(wù)的集合，M為任務(wù)數(shù)量；

則基于CSP的衛(wèi)星時(shí)頻資源調(diào)度問題可以描述為一個(gè)變量、值域和約束的三元組：

SCH=〈X,D,C〉，

(1)

基于CSP的GEO通信衛(wèi)星時(shí)頻資源調(diào)度模型可以描述如下：

(2)

(3)

模型的目標(biāo)函數(shù)設(shè)為最大化任務(wù)優(yōu)先級(jí)之和，即調(diào)度成功的任務(wù)優(yōu)先級(jí)之和越大，該調(diào)度方案的收益越高。其中，約束Cb表示頻帶資源限制約束，即分配給任務(wù)的起始頻帶必須在轉(zhuǎn)發(fā)器的頻帶資源之內(nèi)，同時(shí)必須留有任務(wù)執(zhí)行所需帶寬的余量；約束Ct表示時(shí)間約束，即分配給任務(wù)的時(shí)間區(qū)間必須在任務(wù)申請(qǐng)執(zhí)行的時(shí)間范圍之內(nèi)；約束Ce表示資源沖突約束，即不同任務(wù)占用的資源塊不能重疊。

2 基于資源矩陣更新的調(diào)度策略

針對(duì)傳統(tǒng)的基于任務(wù)資源窗口更新[4,8]的調(diào)度策略計(jì)算復(fù)雜度高的問題，本文提出一種基于資源矩陣更新的調(diào)度策略，采用矩陣形式表示轉(zhuǎn)發(fā)器的時(shí)頻資源、調(diào)度方案和任務(wù)時(shí)頻窗口，而將任務(wù)資源匹配過程轉(zhuǎn)化為矩陣的乘積計(jì)算。

2.1 資源矩陣表示

將可用時(shí)頻資源表示為一個(gè)m×n的0-1矩陣：

(4)

式中，m=Nb為量化頻帶的數(shù)目；n=Nt為量化時(shí)間的數(shù)目。rij=1表示資源塊{[i-1,i],[j-1,j]}已被占用，為0則表示資源塊空閑。將調(diào)度方案也表示為一個(gè)矩陣：

(5)

(6)

式中，ikjk為任務(wù)k在第ik個(gè)頻帶上的第jk個(gè)時(shí)頻窗口矩陣。則任務(wù)k的時(shí)頻窗口矩陣集可以表示為：

(7)

圖3 任務(wù)的時(shí)頻窗口矩陣集

2.2 資源矩陣更新

(1)當(dāng)對(duì)任務(wù)k進(jìn)行調(diào)度時(shí)，首先根據(jù)資源矩陣狀態(tài)和任務(wù)需求特性判斷任務(wù)k在第ik個(gè)量化頻帶的調(diào)度可能性：

(8)

(2)逐個(gè)取出任務(wù)k的時(shí)頻窗口矩陣集中頻帶編號(hào)為ik的窗口矩陣，并將窗口矩陣與資源矩陣R做Hadamard乘積(即矩陣對(duì)應(yīng)位置相乘)，并根據(jù)乘積矩陣E進(jìn)行調(diào)度狀態(tài)判斷：

(9)

(10)

(3)每成功調(diào)度一個(gè)任務(wù)，則對(duì)該任務(wù)所在任務(wù)序列的資源矩陣和方案矩陣進(jìn)行更新：

(11)

例如，有任務(wù)序列{5,2,1,4,…}，其中任務(wù)4的屬性為{3,2,2,1,4}。假設(shè)已成功調(diào)度任務(wù)5,2,1，當(dāng)任務(wù)4調(diào)度成功后，資源矩陣和方案矩陣更新方法如圖4所示。

圖4 資源矩陣和方案矩陣的更新

基于資源矩陣更新策略的調(diào)度流程為：

① 由元啟發(fā)式算法生成任務(wù)序列，初始化該任務(wù)序列的資源矩陣和方案矩陣；

② 按任務(wù)序列的順序依次選擇任務(wù)，計(jì)算該任務(wù)的時(shí)頻窗口矩陣集；

③ 按照式(8)判斷任務(wù)的調(diào)度可能性，若不具備調(diào)度的可能性，則返回②；

④ 若具備調(diào)度可能性，則借鑒二維裝箱問題中的BL準(zhǔn)則[15]，按照“低頻帶優(yōu)先，頻帶相同的時(shí)間靠前優(yōu)先”的原則依次取出時(shí)頻窗口矩陣，依據(jù)式(9)和式(10)檢查是否可以調(diào)度；首次出現(xiàn)滿足調(diào)度條件的時(shí)頻窗口后，記錄調(diào)度狀態(tài)，并按式(11)更新資源矩陣和方案矩陣，轉(zhuǎn)向②；

⑤ 所有任務(wù)遍歷完畢后，輸出該任務(wù)序列的調(diào)度方案，并計(jì)算調(diào)度收益和任務(wù)完成情況。

2.3 計(jì)算復(fù)雜度分析

(12)

對(duì)于單個(gè)任務(wù)序列T=[Ti]1×M，調(diào)度完M個(gè)任務(wù)所做的資源窗口更新操作次數(shù)的最大值為：

(13)

(14)

(15)

對(duì)于單個(gè)任務(wù)序列T=[Ti]1×M，調(diào)度完M個(gè)任務(wù)所做的調(diào)度判斷次數(shù)和嘗試次數(shù)的最大值為：

(16)

3 GEO通信衛(wèi)星資源調(diào)度算法

量子粒子群算法是由文獻(xiàn)[16]提出的一種優(yōu)化算法，與標(biāo)準(zhǔn)PSO算法相比，該算法的優(yōu)點(diǎn)是參數(shù)少便于控制、尋優(yōu)能力較強(qiáng)，缺點(diǎn)是不適用于離散組合優(yōu)化問題、初始解質(zhì)量不高。在該算法的基礎(chǔ)上，本文提出一種改進(jìn)的量子粒子群優(yōu)化(Improved Quantum-behaved Particle Swarm Optimization，IQPSO)算法，用于求解通信衛(wèi)星時(shí)頻資源調(diào)度問題。

3.1 改進(jìn)的QPSO算法

3.1.1 編解碼方式

為使QPSO算法能夠解決離散組合優(yōu)化問題，在粒子編解碼上分別采用實(shí)數(shù)編碼和最小位置值規(guī)則[17]解碼。設(shè)粒子長(zhǎng)度D等于任務(wù)數(shù)量M，對(duì)粒子進(jìn)行實(shí)數(shù)編碼，并利用連續(xù)域的粒子群進(jìn)化方法進(jìn)行種群更新；解碼時(shí)，粒子第k個(gè)位置的值對(duì)應(yīng)任務(wù)k的排序優(yōu)先值，按優(yōu)先值由小到大對(duì)任務(wù)進(jìn)行排序，生成任務(wù)序列。

設(shè)粒子i的位置向量Xi=(xi1,xi2,…,xiM)，對(duì)應(yīng)的解碼向量即任務(wù)序列πi=(πi1,πi2,…,πiM)，利用粒子位置更新式進(jìn)行位置更新后，粒子位置向量為：

X′i=(x′i1,x′i2,…,x′iM)，

(17)

則對(duì)應(yīng)的解碼向量為：

π′i=(π′i1,π′i2,…,π′iM)。

(18)

基于最小位置值的解碼方法如圖5所示。設(shè)種群中有粒子向量(此時(shí)M=6):(0.87,0.34,1.02,1.65,1.13,0.76)，則可生成對(duì)應(yīng)的任務(wù)序列(2,6,1,3,5,4)，此任務(wù)序列對(duì)應(yīng)的調(diào)度收益即為該粒子的適應(yīng)度值。

圖5 基于最小位置值的解碼方法

3.1.2 初始解優(yōu)化

(19)

設(shè)任務(wù)k的加權(quán)優(yōu)先級(jí)為：

(20)

即任務(wù)的優(yōu)先級(jí)越高，則加權(quán)優(yōu)先級(jí)越高；任務(wù)優(yōu)先級(jí)相同時(shí)，占用資源越少則加權(quán)優(yōu)先級(jí)越高。初始種群中，粒子i的初始位置Xi的生成方法為：

Xi=(xi1,xi2,…,xik,…,xiM)，

(21)

(22)

式中，[Xmin,Xmax]表示粒子每一維搜索空間的取值范圍。初始粒子種群中，加權(quán)優(yōu)先級(jí)越高的任務(wù)初始位置值較小的概率越高，生成任務(wù)序列時(shí)位置靠前的概率越高。由于按任務(wù)序列調(diào)度具有“先到先占”的特點(diǎn)，加權(quán)優(yōu)先級(jí)高的任務(wù)有更高概率被成功調(diào)度，因此相比于隨機(jī)法能夠生成更高質(zhì)量的初始解，有助于加快算法的收斂。

3.1.3 種群進(jìn)化

算法的種群進(jìn)化方法[16]如下：

atri(t)=r1·Pi(t)+(1-r1)·G(t),r1～U(0,1)，

(23)

(24)

(25)

式中，u～U(0,1)表示隨機(jī)因子；Pi(t)和G(t)分別表示個(gè)體最優(yōu)位置和全局最優(yōu)位置；atri表示粒子i的吸引子，該位置綜合了個(gè)體信息和群體信息對(duì)粒子搜索的指導(dǎo)作用；C(t)表示每代種群的平均最優(yōu)位置，該位置體現(xiàn)了算法的個(gè)體信息協(xié)作機(jī)制。

α稱為收縮-擴(kuò)張系數(shù)[16]，是算法中除種群數(shù)量、粒子維數(shù)和迭代次數(shù)以外唯一的參數(shù)。合理控制α能夠調(diào)節(jié)算法的全局搜索能力和局部搜索能力，改善算法性能。文獻(xiàn)[16]提出了固定參數(shù)和線性遞減2種控制策略，并指出當(dāng)系數(shù)維持較大的值時(shí)，算法跳出局部收斂的能力更強(qiáng)。系數(shù)遞減策略如下：

(26)

式中，α2和α1表示收縮擴(kuò)張系數(shù)的最大值和最小值；iter和Gmax表示算法的迭代次數(shù)和最大迭代次數(shù)。

3.2 基于IQPSO算法的調(diào)度流程

基于IQPSO算法的時(shí)頻資源調(diào)度流程如圖6所示。

圖6 基于IQPSO算法的時(shí)頻資源調(diào)度流程

基于IQPSO算法的時(shí)頻資源調(diào)度流程為：

① 輸入調(diào)度場(chǎng)景參數(shù)和算法參數(shù)，按照初始解優(yōu)化方法生成初始粒子種群；

② 按照最小位置值解碼規(guī)則對(duì)粒子進(jìn)行解碼，生成任務(wù)序列矩陣；

③ 逐個(gè)對(duì)任務(wù)序列進(jìn)行調(diào)度，生成各粒子的調(diào)度方案并計(jì)算各調(diào)度方案的收益，即為對(duì)應(yīng)的粒子的適應(yīng)度值；

④ 更新種群中粒子的個(gè)體最優(yōu)位置和全局最優(yōu)位置；

⑤ 按照式(23)和式(24)計(jì)算粒子的吸引子位置和個(gè)體平均最優(yōu)位置；

⑥ 按照式(25)更新粒子的位置，生成下一代種群；

⑦ 判斷算法的迭代終止條件，若不符合則轉(zhuǎn)向②；若符合則結(jié)束算法的執(zhí)行；

⑧ 輸出資源調(diào)度結(jié)果。

4 仿真實(shí)驗(yàn)

4.1 仿真場(chǎng)景和參數(shù)設(shè)置

仿真場(chǎng)景選擇GEO通信衛(wèi)星Ku頻段轉(zhuǎn)發(fā)器,帶寬資源總量為48 MHz，調(diào)度時(shí)間周期為24 h，最小量化帶寬為1 MHz，最小量化時(shí)間區(qū)間為1 h，則最小量化時(shí)頻資源塊的總量為1 152個(gè)。任務(wù)集的生成方法參照了文獻(xiàn)[4]，以任務(wù)集中任務(wù)k為例描述如下：

② 任務(wù)的申請(qǐng)帶寬(單位MHz)在取值范圍內(nèi)隨機(jī)生成，但需要做向上取整的處理，即不足1 MHz的部分按1 MHz處理，并假設(shè)任務(wù)的最大可申請(qǐng)帶寬為16 MHz，則申請(qǐng)帶寬的值域?yàn)椋簕1,2,…,16}。申請(qǐng)時(shí)間區(qū)間的長(zhǎng)度也相同方法進(jìn)行處理，申請(qǐng)時(shí)間區(qū)間的值域?yàn)閧1,2,3,4}。

⑤ 任務(wù)數(shù)量分別設(shè)置小規(guī)模(30)、中規(guī)模(50,80)和大規(guī)模(100)共4種情況，實(shí)時(shí)任務(wù)占比為20%。每種數(shù)量規(guī)模分別隨機(jī)生成5個(gè)任務(wù)集，共20個(gè)任務(wù)集，且確保每個(gè)任務(wù)集的平均優(yōu)先級(jí)均為5.5。而后按照1 MHz和8 MHz的量化帶寬分別生成20個(gè)算例，共40個(gè)算例。其中，以任務(wù)數(shù)量為100的10個(gè)算例為例，其基本特性如表1所示。

表1 算例的特征

4.2 計(jì)算復(fù)雜度對(duì)比分析

為了分析資源矩陣更新(Resource Matrix Update，RMU)方法對(duì)資源匹配過程的計(jì)算復(fù)雜度的影響，并與傳統(tǒng)的任務(wù)資源窗口更新方法(Task Resource Window Update，TRWU)進(jìn)行比較，使用以下算法進(jìn)行對(duì)比分析：

① 基礎(chǔ)蟻群算法ACO[18]；

② 由文獻(xiàn)[4]提出的改進(jìn)蟻群算法ACO-TB(Ant Colony Optimization based on Time and Bandwidth)；

③ 由文獻(xiàn)[8]提出的改進(jìn)遺傳算法GA；

④ 標(biāo)準(zhǔn)粒子群算法PSO[19]；

⑤ 本文提出的使用RMU的改進(jìn)算法IQPSO。當(dāng)使用TRWU方法時(shí)，記為QPSO(TRWU)。

每種算法分別使用TRWU和RMU方法進(jìn)行實(shí)驗(yàn)，各算法的參數(shù)如表2所示。

表2 算法的參數(shù)

算法的種群數(shù)量設(shè)置為與任務(wù)數(shù)量相等，迭代次數(shù)均為100次。在量化帶寬為1 MHz和8 MHz的情況下，分別對(duì)30,50,80,100個(gè)任務(wù)的5個(gè)算例運(yùn)行10次并取算法執(zhí)行時(shí)間的平均值，結(jié)果如表3、圖7和圖8所示。

表3 不同算法的平均執(zhí)行時(shí)間

圖7 不同算法的平均運(yùn)行時(shí)間(量化帶寬1 MHz)

圖8 不同算法的平均執(zhí)行時(shí)間(量化帶寬8 MHz)

由表3、圖7和圖8可以看出：

① GA，PSO和IQPSO算法的執(zhí)行時(shí)間基本相近，且均小于相同條件下的ACO和ACOTB，說明這3種算法在計(jì)算復(fù)雜度上要低于ACO和ACOTB。

② 相比于TRWU方法，算法在使用RMU方法時(shí)，執(zhí)行時(shí)間均有效降低。當(dāng)量化帶寬為8 MHz，同一算法使用RMU和TRWU方法時(shí)，所獲得的執(zhí)行時(shí)間的改善幅度為51%～84%；當(dāng)量化帶寬為1 MHz時(shí)，這一改善幅度為82%～88%，可見本文所提的RMU方法在處理大量沖突時(shí)具有更明顯的優(yōu)勢(shì)。

③ 不同的量化帶寬對(duì)執(zhí)行時(shí)間也有較大影響。當(dāng)量化帶寬由8 MHz變?yōu)? MHz時(shí)，算法使用TRWU的執(zhí)行時(shí)間增加5.6～9倍，使用RMU的執(zhí)行時(shí)間增加2～-6.7倍。這是由于提高量化帶寬分辨率后，任務(wù)間沖突加劇，導(dǎo)致算法的執(zhí)行時(shí)間大幅增加。

④ 本文提出的IQPSO(RMU)相比于主要對(duì)照算法ACO-TB(TRWU)，在1 MHz量化帶寬下，時(shí)間改善程度為88%～91%，在8 MHz量化帶寬下，時(shí)間改善程度為80%～89%，可見本文算法能夠有效降低現(xiàn)有調(diào)度算法的計(jì)算復(fù)雜度，縮短算法的執(zhí)行時(shí)間。

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

本小節(jié)設(shè)置算法終止條件為閾值條件，即設(shè)最大、最小迭代次數(shù)為200和100，當(dāng)算法的優(yōu)化解連續(xù)50次迭代沒有改善時(shí)，則終止算法執(zhí)行。ACO，ACOTB依照文獻(xiàn)[4]以及GA依照文獻(xiàn)[8]的設(shè)置均采用TRWU方法，PSO，IQPSO則采用本文提出的RMU方法。以8 MHz量化帶寬為例，使用5種算法對(duì)20個(gè)算例運(yùn)算10次并取平均值，結(jié)果如表4所示。

表4 算法的優(yōu)化結(jié)果(量化帶寬8 MHz)

由表4可以看出：

① 本文所提IQPSO算法在4種任務(wù)規(guī)模下，調(diào)度收益的平均值和最優(yōu)值均為最優(yōu)；

② IQPSO在任務(wù)數(shù)量30，50和GA算法在任務(wù)數(shù)量為80，100時(shí)，完成任務(wù)數(shù)量指標(biāo)最優(yōu)，推測(cè)GA算法更善于處理占用資源塊較少的任務(wù)，因此能夠?qū)崿F(xiàn)更多任務(wù)的調(diào)度；

③ 執(zhí)行時(shí)間指標(biāo)上，PSO和IQPSO在所有任務(wù)規(guī)模情況下為最優(yōu)。當(dāng)任務(wù)規(guī)模增大時(shí)，PSO由于陷入局部最優(yōu)，因此迭代次數(shù)和執(zhí)行時(shí)間均低于IQPSO，但調(diào)度收益和完成任務(wù)數(shù)量也更差。在相同任務(wù)規(guī)模情況下，IQPSO的平均執(zhí)行時(shí)間為ACOTB的12%～14%，GA的20%～22%。

綜上，IQPSO算法對(duì)比現(xiàn)有幾種算法，可以在更短的執(zhí)行時(shí)間內(nèi)，在調(diào)度收益指標(biāo)上取得更優(yōu)的結(jié)果，同時(shí)完成任務(wù)數(shù)量也較好。

以任務(wù)集100_1和100_6為例，分別采用了1 MHz和8 MHz的帶寬量化方式，5種算法分別執(zhí)行10次并取最好的一次結(jié)果，其收斂曲線如圖9所示。

圖9 最佳執(zhí)行的收斂曲線

由圖9可以看出：① 在相同量化帶寬情況下，PSO算法由于缺乏針對(duì)性的優(yōu)化機(jī)制，易陷入局部最優(yōu)解，ACO-TB和GA算法持續(xù)優(yōu)化能力較強(qiáng)，本文所提IQPSO算法的全局優(yōu)化能力則相對(duì)更優(yōu)，能夠不斷跳出局部收斂；② 對(duì)同一任務(wù)集生成的算例100_1和100_6，當(dāng)量化帶寬由8 MHz變?yōu)? MHz時(shí)，各算法的調(diào)度收益均得到有效提升，可見較小的量化尺度能夠發(fā)現(xiàn)更多的資源碎片加以利用，但結(jié)合表4可知，提升量化帶寬分辨率也會(huì)帶來執(zhí)行時(shí)間的增加。

量化帶寬為1 MHz和8 MHz時(shí)，算法調(diào)度完成的任務(wù)數(shù)量如圖10和圖11所示。

圖10 算法調(diào)度完成的任務(wù)數(shù)量(量化帶寬1 MHz)

圖11 算法調(diào)度完成的任務(wù)數(shù)量(量化帶寬8 MHz)

由圖10和圖11可以看出：① 從任務(wù)規(guī)?？?，當(dāng)任務(wù)規(guī)模較小(30)時(shí)，各算法完成任務(wù)數(shù)量基本一致，且由于資源相對(duì)充足，任務(wù)間資源沖突相對(duì)較少，任務(wù)完成率接近100%。當(dāng)任務(wù)規(guī)模增大時(shí)，隨著任務(wù)資源需求和任務(wù)間沖突增加，完成任務(wù)數(shù)量雖提升，但完成率總體在下降。② 從算法對(duì)比來看，IQPSO和GA能夠調(diào)度成功更多的任務(wù)數(shù)量，ACOTB次之，而ACO和PSO相對(duì)較差。③ 從量化帶寬看，同等任務(wù)數(shù)量情況下，量化帶寬為1 MHz時(shí)算法的調(diào)度方案能夠完成更多的任務(wù)。

5 結(jié)束語

本文針對(duì)GEO通信衛(wèi)星時(shí)頻資源調(diào)度問題，提出了以資源矩陣更新為核心的調(diào)度策略，相比于傳統(tǒng)的任務(wù)資源窗口更新方法，有效降低了計(jì)算復(fù)雜度，在同等條件下使算法執(zhí)行時(shí)間減少51%～88%。在此基礎(chǔ)上，設(shè)計(jì)了采用實(shí)數(shù)編碼、最小位置值解碼和初始解優(yōu)化的IQPSO算法，對(duì)比ACO-TB[4]和GA[8]算法，在提升優(yōu)化解質(zhì)量的同時(shí)，算法執(zhí)行時(shí)間減少78%～88%。本文所提的調(diào)度策略和改進(jìn)算法對(duì)于利用連續(xù)型元啟發(fā)式算法解決通信衛(wèi)星時(shí)頻資源調(diào)度問題具備一定的參考意義。通過本文的工作可以發(fā)現(xiàn)，單目標(biāo)優(yōu)化情況下，算法對(duì)調(diào)度收益和任務(wù)完成數(shù)量2個(gè)指標(biāo)并不能很好的兼顧，下一步將主要針對(duì)多目標(biāo)情況下的衛(wèi)星資源調(diào)度問題進(jìn)行研究。