基于改進QPSO算法的GEO衛星時頻資源調度

高 威，瞿連政，王 磊

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

0 引言

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

在調度模型與算法方面，文獻[3]建立了基于任務資源匹配的整數規劃模型，使用蟻群算法進行了求解；文獻[4]采用任務優先級和時間靈活度加權的啟發式信息，提出了加入虛擬任務的改進蟻群算法，具有較好的尋優能力和穩定性；文獻[5]在max-min蟻群系統的基礎上，提出了一種簡化蟻群優化算法，設計了新的信息素模型使得算法具有更平衡的探索能力和開發能力；文獻[6]分析了靜態調度模型和動態調度模型的調度目標和約束條件，采用了改進的海洋捕食者算法求解衛星的任務調度；文獻[7]將衛星資源調度問題轉化為任務排序問題，并利用遺傳算法求解最優任務序列。

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

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

① 將衛星轉發器的二維時頻資源進行量化處理，建立了基于CSP的衛星時頻資源調度模型，并設計了以任務序列生成和任務資源匹配為主要步驟的調度流程；

② 針對任務資源窗口更新方法計算復雜度高的問題，提出了基于資源矩陣更新的調度策略，將任務資源匹配過程轉化為矩陣的Hadamard乘積計算，有效降低了任務資源匹配的計算復雜度，縮短了算法的執行時間；

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

④ 對所提調度策略和改進算法進行了仿真實驗，分析了不同量化帶寬和調度策略對執行時間、調度結果的影響，對比分析了本文所提算法與當前幾種典型的時頻資源調度算法的性能差異。

1 GEO通信衛星資源調度模型

1.1 問題背景

從用戶的角度，當用戶組網通信時，首先需要向衛星資源管理中心提交任務申請，提交信息包括用戶位置、用網時間、申請帶寬、業務類型及終端信息等，然后等待衛星資源管理中心分配資源并使用分配的資源開展通信業務；從衛星資源管理中心的角度，調度系統需要管理資源池和任務池，接收多個用戶的任務資源申請，并根據資源池和任務池狀態，選擇合適的調度模型和調度算法進行資源調度，生成優化調度方案[6]。因此，決定資源調度性能的關鍵是調度模型和調度算法。通信衛星資源調度的架構如圖1所示。

圖1 通信衛星資源調度架構

將調度問題按調度周期進行劃分，并對調度資源采用量化處理，其中調度周期的長度和通信資源劃分的粒度可以靈活調整，以適用于不同的問題場景。從資源管理和分配的角度，衛星管理中心的資源調度系統主要進行的操作有：

① 執行上一周期結束時生成的調度方案。

② 監控資源池中資源的狀態，將執行完任務后被釋放的資源更新到資源池，對資源的狀態進行標記。資源狀態分為占用、已分配待使用、空閑和不可用等。

③ 監控任務池中任務的狀態，刪除無法執行的任務，接收新任務申請并更新到任務池。對任務的狀態進行標記，分為執行結束、執行中、已分配資源待執行、拒絕執行和新接收待分配資源等。

④ 在調度周期結束時依據任務池、資源池狀態，選擇調度模型和調度算法進行資源調度，生成下一個周期的調度方案。

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

1.2 時頻資源量化

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

設定任務集合T與衛星轉發器資源集合S是嚴格對應的。可將單波束覆蓋范圍內同頻段用戶終端的任務請求整合為任務集，而將該波束內的單個或多個轉發器的可用時頻資源整合為資源集。要求任務提交的資源申請以資源最小量化分辨率為單位，并表示為時頻區間的集合。轉發器的時頻資源如圖2所示，以1 MHz和1 h進行量化時，資源集可表示為{[0,4],[0,5]}，其中任務4占用的資源塊可表示為{[1,3],[1,2]}。因此，可將時頻資源調度問題抽象為數學上的二維裝箱問題，該問題已被證明為是一個NP-Hard問題[13]。

圖2 轉發器的時頻資源

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

1.3 基于CSP的調度模型

CSP可以描述為：給定一組變量及它們的值域，找到一個滿足所有約束的變量的解，并盡可能使解的質量更優[14]。基于CSP的調度模型所使用的符號如下：

S={B,TE}表示轉發器的時頻資源總量；

B=[Bstr,Bend]表示轉發器的頻率資源；

TE=[TEstr,TEend]表示轉發器的時間資源；

RS={BS,DS}表示任務所需的帶寬資源和時間資源，BS和DS分別表示未經過量化處理的帶寬大小和時間長度；

Nb=(Bend-Bstr)/δB表示轉發器資源進行量化后的頻帶個數，δB表示量化頻帶的帶寬；

Nt=(TEend-TEstr)/δt表示轉發器資源量化后的時間區間個數，δt表示量化時間的間隔；

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

則基于CSP的衛星時頻資源調度問題可以描述為一個變量、值域和約束的三元組：

SCH=〈X,D,C〉，

(1)

基于CSP的GEO通信衛星時頻資源調度模型可以描述如下：

(2)

(3)

模型的目標函數設為最大化任務優先級之和，即調度成功的任務優先級之和越大，該調度方案的收益越高。其中，約束Cb表示頻帶資源限制約束，即分配給任務的起始頻帶必須在轉發器的頻帶資源之內，同時必須留有任務執行所需帶寬的余量；約束Ct表示時間約束，即分配給任務的時間區間必須在任務申請執行的時間范圍之內；約束Ce表示資源沖突約束，即不同任務占用的資源塊不能重疊。

2 基于資源矩陣更新的調度策略

針對傳統的基于任務資源窗口更新[4,8]的調度策略計算復雜度高的問題，本文提出一種基于資源矩陣更新的調度策略，采用矩陣形式表示轉發器的時頻資源、調度方案和任務時頻窗口，而將任務資源匹配過程轉化為矩陣的乘積計算。

2.1 資源矩陣表示

將可用時頻資源表示為一個m×n的0-1矩陣：

(4)

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

(5)

(6)

式中，ikjk為任務k在第ik個頻帶上的第jk個時頻窗口矩陣。則任務k的時頻窗口矩陣集可以表示為：

(7)

圖3 任務的時頻窗口矩陣集

2.2 資源矩陣更新

(1)當對任務k進行調度時，首先根據資源矩陣狀態和任務需求特性判斷任務k在第ik個量化頻帶的調度可能性：

(8)

(2)逐個取出任務k的時頻窗口矩陣集中頻帶編號為ik的窗口矩陣，并將窗口矩陣與資源矩陣R做Hadamard乘積(即矩陣對應位置相乘)，并根據乘積矩陣E進行調度狀態判斷：

(9)

(10)

(3)每成功調度一個任務，則對該任務所在任務序列的資源矩陣和方案矩陣進行更新：

(11)

例如，有任務序列{5,2,1,4,…}，其中任務4的屬性為{3,2,2,1,4}。假設已成功調度任務5,2,1，當任務4調度成功后，資源矩陣和方案矩陣更新方法如圖4所示。

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

基于資源矩陣更新策略的調度流程為：

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

② 按任務序列的順序依次選擇任務，計算該任務的時頻窗口矩陣集；

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

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

⑤ 所有任務遍歷完畢后，輸出該任務序列的調度方案，并計算調度收益和任務完成情況。

2.3 計算復雜度分析

(12)

對于單個任務序列T=[Ti]1×M，調度完M個任務所做的資源窗口更新操作次數的最大值為：

(13)

(14)

(15)

對于單個任務序列T=[Ti]1×M，調度完M個任務所做的調度判斷次數和嘗試次數的最大值為：

(16)

3 GEO通信衛星資源調度算法

量子粒子群算法是由文獻[16]提出的一種優化算法，與標準PSO算法相比，該算法的優點是參數少便于控制、尋優能力較強，缺點是不適用于離散組合優化問題、初始解質量不高。在該算法的基礎上，本文提出一種改進的量子粒子群優化(Improved Quantum-behaved Particle Swarm Optimization，IQPSO)算法，用于求解通信衛星時頻資源調度問題。

3.1 改進的QPSO算法

3.1.1 編解碼方式

為使QPSO算法能夠解決離散組合優化問題，在粒子編解碼上分別采用實數編碼和最小位置值規則[17]解碼。設粒子長度D等于任務數量M，對粒子進行實數編碼，并利用連續域的粒子群進化方法進行種群更新；解碼時，粒子第k個位置的值對應任務k的排序優先值，按優先值由小到大對任務進行排序，生成任務序列。

設粒子i的位置向量Xi=(xi1,xi2,…,xiM)，對應的解碼向量即任務序列πi=(πi1,πi2,…,πiM)，利用粒子位置更新式進行位置更新后，粒子位置向量為：

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

(17)

則對應的解碼向量為：

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

(18)

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

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

3.1.2 初始解優化

(19)

設任務k的加權優先級為：

(20)

即任務的優先級越高，則加權優先級越高；任務優先級相同時，占用資源越少則加權優先級越高。初始種群中，粒子i的初始位置Xi的生成方法為：

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

(21)

(22)

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

3.1.3 種群進化

算法的種群進化方法[16]如下：

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

(23)

(24)

(25)

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

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

(26)

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

3.2 基于IQPSO算法的調度流程

基于IQPSO算法的時頻資源調度流程如圖6所示。

圖6 基于IQPSO算法的時頻資源調度流程

基于IQPSO算法的時頻資源調度流程為：

① 輸入調度場景參數和算法參數，按照初始解優化方法生成初始粒子種群；

② 按照最小位置值解碼規則對粒子進行解碼，生成任務序列矩陣；

③ 逐個對任務序列進行調度，生成各粒子的調度方案并計算各調度方案的收益，即為對應的粒子的適應度值；

④ 更新種群中粒子的個體最優位置和全局最優位置；

⑤ 按照式(23)和式(24)計算粒子的吸引子位置和個體平均最優位置；

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

⑦ 判斷算法的迭代終止條件，若不符合則轉向②；若符合則結束算法的執行；

⑧ 輸出資源調度結果。

4 仿真實驗

4.1 仿真場景和參數設置

仿真場景選擇GEO通信衛星Ku頻段轉發器,帶寬資源總量為48 MHz，調度時間周期為24 h，最小量化帶寬為1 MHz，最小量化時間區間為1 h，則最小量化時頻資源塊的總量為1 152個。任務集的生成方法參照了文獻[4]，以任務集中任務k為例描述如下：

② 任務的申請帶寬(單位MHz)在取值范圍內隨機生成，但需要做向上取整的處理，即不足1 MHz的部分按1 MHz處理，并假設任務的最大可申請帶寬為16 MHz，則申請帶寬的值域為：{1,2,…,16}。申請時間區間的長度也相同方法進行處理，申請時間區間的值域為{1,2,3,4}。

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

表1 算例的特征

4.2 計算復雜度對比分析

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

① 基礎蟻群算法ACO[18]；

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

③ 由文獻[8]提出的改進遺傳算法GA；

④ 標準粒子群算法PSO[19]；

⑤ 本文提出的使用RMU的改進算法IQPSO。當使用TRWU方法時，記為QPSO(TRWU)。

每種算法分別使用TRWU和RMU方法進行實驗，各算法的參數如表2所示。

表2 算法的參數

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

表3 不同算法的平均執行時間

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

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

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

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

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

③ 不同的量化帶寬對執行時間也有較大影響。當量化帶寬由8 MHz變為1 MHz時，算法使用TRWU的執行時間增加5.6～9倍，使用RMU的執行時間增加2～-6.7倍。這是由于提高量化帶寬分辨率后，任務間沖突加劇，導致算法的執行時間大幅增加。

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

4.3 算法優化性能分析

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

表4 算法的優化結果(量化帶寬8 MHz)

由表4可以看出：

① 本文所提IQPSO算法在4種任務規模下，調度收益的平均值和最優值均為最優；

② IQPSO在任務數量30，50和GA算法在任務數量為80，100時，完成任務數量指標最優，推測GA算法更善于處理占用資源塊較少的任務，因此能夠實現更多任務的調度；

③ 執行時間指標上，PSO和IQPSO在所有任務規模情況下為最優。當任務規模增大時，PSO由于陷入局部最優，因此迭代次數和執行時間均低于IQPSO，但調度收益和完成任務數量也更差。在相同任務規模情況下，IQPSO的平均執行時間為ACOTB的12%～14%，GA的20%～22%。

綜上，IQPSO算法對比現有幾種算法，可以在更短的執行時間內，在調度收益指標上取得更優的結果，同時完成任務數量也較好。

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

圖9 最佳執行的收斂曲線

由圖9可以看出：① 在相同量化帶寬情況下，PSO算法由于缺乏針對性的優化機制，易陷入局部最優解，ACO-TB和GA算法持續優化能力較強，本文所提IQPSO算法的全局優化能力則相對更優，能夠不斷跳出局部收斂；② 對同一任務集生成的算例100_1和100_6，當量化帶寬由8 MHz變為1 MHz時，各算法的調度收益均得到有效提升，可見較小的量化尺度能夠發現更多的資源碎片加以利用，但結合表4可知，提升量化帶寬分辨率也會帶來執行時間的增加。

量化帶寬為1 MHz和8 MHz時，算法調度完成的任務數量如圖10和圖11所示。

圖10 算法調度完成的任務數量(量化帶寬1 MHz)

圖11 算法調度完成的任務數量(量化帶寬8 MHz)

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

5 結束語

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