班亞明，馬 寧，王玉清，孫文宇*，王寶寶，劉秀芳，賈慧燕

(1.中國電科網(wǎng)絡通信研究院，河北 石家莊 050081；2.航天系統(tǒng)部裝備部軍事代表局駐石家莊軍事代表室，河北 石家莊 050081)

0 引言

在衛(wèi)星資源有限的前提下,如何實現(xiàn)衛(wèi)星通信任務的快速高效調度,最大限度滿足地面通信任務對星上資源的需求是天基網(wǎng)絡面臨的關鍵問題之一[1-3]。而隨著衛(wèi)星通信任務需求量的增長,特殊情況下有限衛(wèi)星資源無法滿足所有用戶需求,此時需要通過任務調度方法盡量提高滿足率。

在當前的衛(wèi)星通信任務調度問題研究中,一是大多數(shù)研究使用運籌學模型和啟發(fā)式算法進行衛(wèi)星通信任務調度,但是當實際中調度問題的約束較多時,會導致對需要求解的變量與復雜度的激增,而過多的求解變量使得上述算法和模型難以高效收斂至較優(yōu)的局部最優(yōu)解;二是隨著強化學習技術的發(fā)展[4-6]以及衛(wèi)星通信系統(tǒng)感知能力的提升,越來越多的經(jīng)驗數(shù)據(jù)被保存,而深度強化學習由于自身特性可以有效利用這些數(shù)據(jù)從中發(fā)現(xiàn)規(guī)律、學習策略,因此基于強化學習的方法在任務與資源調度中被更多地研究[7-8],并適用于衛(wèi)星通信中的任務調度問題。

基于上述背景,本文基于深度強化學習網(wǎng)絡的任務調度方法,針對衛(wèi)星通信系統(tǒng)的場景提出了一種多分支深度Q網(wǎng)絡模型,主要研究內容和貢獻如下:

首先,提出了一種基于深度強化學習模型的任務調度方法,該模型通過引入了任務列表分支網(wǎng)絡(TL分支)和資源池分支網(wǎng)絡(RP分支),多分支深度Q網(wǎng)絡能夠同時對衛(wèi)星資源池狀態(tài)和衛(wèi)星任務狀態(tài)提取特征。隨后拼接特征嵌入,并將其輸入價值分支網(wǎng)絡(Value分支)計算動作價值函數(shù),并依據(jù)最優(yōu)動作價值函數(shù)進行任務選擇動作和優(yōu)先級選擇動作。多分支深度Q網(wǎng)絡具有很多優(yōu)秀的特性。其次,基于深度強化學習的解決方案在決策過程相比啟發(fā)式算法非常高效。雖然強化學習策略的訓練非常耗時,但是這些訓練工作可以離線進行,實際中只需要利用訓練好的模型進行推理,因而在絕大部分情況下可以做到近似實時決策。最后,使用強化學習的方法并不需要顯式地對未來進行預測,模型可以從交互經(jīng)驗、海量數(shù)據(jù)中發(fā)現(xiàn)規(guī)律、學習策略,從而幫助作出合適的決策。

1 衛(wèi)星通信任務調度問題

任務調度過程在基于透明轉發(fā)器的衛(wèi)星通信系統(tǒng)中被廣泛應用,尤其是頻率和時間資源的調度中,基于透明衛(wèi)星轉發(fā)器的任務調度過程如圖1所示。一般情況下,使用衛(wèi)星通信網(wǎng)絡的用戶需要提前對任務需求進行提報,將其使用的帶寬資源與時間一起提交至寬帶通信衛(wèi)星的運行控制中心。運行控制中心為衛(wèi)星的每個轉發(fā)器維護一個分配的資源表,轉發(fā)器中每個資源段的任務時間記錄在該表中,并在多個星地綜合網(wǎng)絡之間共享。隨后,運行控制中心將在表中找到滿足需求提報者任務的空閑資源段,更新相應的任務時間段,并將分配結果通知需求提報者。最后,需求提報者利用分配的衛(wèi)星轉發(fā)器資源建立衛(wèi)星通信網(wǎng)絡。

透明衛(wèi)星轉發(fā)器任務調度過程如果依賴于人工,只有在任務需求量較少的情況下才可行。隨著任務需求的強度不斷加大與任務資源需求的靈活變化和多樣性提升,任務調度過程造成的衛(wèi)星轉發(fā)器頻率碎片化的現(xiàn)象日益嚴重,對人工搜索空閑資源段進行任務需求調度和維護帶來了相當大的挑戰(zhàn)。這些挑戰(zhàn)增加了任務的復雜性和對運行控制中心的技術要求以及衛(wèi)星系統(tǒng)的運營成本,并且由于其經(jīng)驗性質,手動搜索很難保證資源的最佳利用。此外,當高優(yōu)先級任務的需求無法立即得到滿足而需要搶占低優(yōu)先級任務的現(xiàn)有資源時,如何選擇搶占對象以保證影響最小也是決策過程需要考慮的問題。

通過對任務和資源進行合理快速調度,衛(wèi)星通信任務調度方法能夠在多約束的條件下提高衛(wèi)星轉發(fā)器資源(頻率和占用時間)的使用率,通過多分支深度Q網(wǎng)絡(Deep Q Network,DQN)提高衛(wèi)星資源占用率的示意如圖1所示。多約束條件下任務調度問題已經(jīng)被證明是NP問題[9-10],一些傳統(tǒng)運籌學算法[11-12]、貪心算法[13]和啟發(fā)式算法[14-16]已經(jīng)被應用在了衛(wèi)星通信任務調度領域和其他任務調度領域中。

圖1 通過多分支DQN提高衛(wèi)星資源占用率Fig.1 Multi-branch DQN is used to improve satellite resource occupancy

2 基于多分支DQN的調度方法

2.1 強化學習問題定義

用于衛(wèi)星通信的基于多分支DQN的任務調度方法可以定義如下:在固定的衛(wèi)星通信系統(tǒng)條件下,將衛(wèi)星通信系統(tǒng)的衛(wèi)星任務需求和資源池生成定義為強化學習的環(huán)境。在該環(huán)境中,狀態(tài)包括資源池狀態(tài)srp和任務列表狀態(tài)stl,t時刻的狀態(tài)被定義為st,以及一系列用于決策的有效動作集A(s)。多分支DQN控制的智能體會在動作集合A(s)中選擇一個有效的動作at∈A(s),并于時間t時在環(huán)境中執(zhí)行動作at以獲得獎勵rt,之后環(huán)境的狀態(tài)發(fā)生轉移至st+1。在該方法中,將執(zhí)行迭代直到環(huán)境達到終止條件,即所有分配完成并且資源池沒有更多資源可供分配時終止。

2.2 多分支DQN模型建模

使用多分支DQN模型解決衛(wèi)星通信任務調度問題實質上是找到了比使用啟發(fā)式算法更好的排序序列,其最終目標是最小化分配結果的資源占用率,縮短衛(wèi)星任務分配總時間。多分支深度Q網(wǎng)絡是一種基于DQN[6]的離線策略(Off-policy)方法,是一種典型的價值優(yōu)化強化學習算法,詳細的網(wǎng)絡結構在2.3節(jié)進行闡述。

多分支DQN將衛(wèi)星運控中心建模為智能體(Agent),將任務需求和衛(wèi)星通信資源建模為環(huán)境(Environment)。此外,還將討論用于衛(wèi)星通信任務調度問題的多分支DQN模型中定義的強化學習的主要元素,包括狀態(tài)空間、動作空間和獎勵。同時,模型訓練階段的經(jīng)驗回放、目標網(wǎng)絡和損失函數(shù)的定義也會得到詳細介紹。

圖2 基于多分支深度Q網(wǎng)絡的任務調度方法整體圖Fig.2 Overview of the proposed multi-branch DQN based task scheduling method

①狀態(tài)空間

t時刻下的衛(wèi)星任務需求和資源池狀態(tài)st=(srp,stl)t是對該時刻下資源池狀態(tài)srp和任務列表狀態(tài)stl的觀測。當有新的任務需求時,需要對任務列表狀態(tài)stl進行格式化并更新任務列表stl的狀態(tài),stl可以表示為:

stl={[o1,φ1(t1),φ2(f1)],…,[om,φ1(tm),φ2(fm)], (1)

式中:om表示衛(wèi)星資源池中第m個任務的分配狀態(tài),tm和fm分別表示任務占用的衛(wèi)星時間和頻率資源,φ1(tm)=N×tm/Δt和φ2(fm)=N×fm/Δf為tm和fm的狀態(tài)重構,使它們符合模型輸入的張量大小,tm和fm均在[1,N]內重新表述,Δf和Δt分別表示衛(wèi)星資源池中的時間資源和頻率資源范圍。

通過將頻率資源和時間資源在各自維度上分別劃分N-1次,可以將衛(wèi)星資源池劃分為N×N個資源塊。狀態(tài)矩陣srp用于表示資源池中每個資源塊的占用情況。srp的表示如下:

(2)

式中:p(n,n)為(n,n)資源塊中衛(wèi)星資源池的占用指示。

②動作空間

在衛(wèi)星通信任務調度問題中,可用動作空間A(s)是衛(wèi)星控制系統(tǒng)的決策空間,根據(jù)t時刻的當前狀態(tài)st從A(s)中選擇動作at?？捎玫牟僮骺臻g取決于分配的資源的類型和資源的限制,包括優(yōu)先動作空間Ap和選擇動作空間Ac。形式上,A(s)可以定義為:

A(s)={(Ac(i),Ap(j))|1≤i≤m,j=0,1},

(3)

式中:ac=Ac(i)為任務選擇動作,表示本輪在列表中選擇的任務號;ap=Ap(j)是資源搜索優(yōu)先級的動作,表示分配時頻率搜索或時間搜索的優(yōu)先級。

動作選擇的探索機制直接影響采樣性能。因此,在訓練階段,動作選擇采用-貪婪策略。多分支DQN以概率從A(s)中隨機采樣,可以表示為:

(4)

在測試階段,多分支DQN會選擇概率分布Q*(st,at)中概率最高的at。

③獎勵

以資源占用率作為算法的優(yōu)化目標,即網(wǎng)絡的獎勵值rt,代表對狀態(tài)st下所選動作at的評價。任務分配后,資源占用率越高,獎勵值越高。對于相同資源塊大小的任務分配,資源占用率越接近上限,獎勵值應該越大。基于上述原則,獎勵設計如下式所示:

(5)

式中:非負乘數(shù)ε用于避免無窮值。

④經(jīng)驗回放

在訓練階段,同一般DQN方法采用了經(jīng)驗回放(Reply Memory)技巧來消除衛(wèi)星任務分配系統(tǒng)中與環(huán)境交互產(chǎn)生的樣本數(shù)據(jù)的相關性。原因在于深度神經(jīng)網(wǎng)絡要求輸入樣本不相關,但是對于衛(wèi)星任務分配系統(tǒng),任務分配順序與最終資源占用率之間存在顯著的相關性。而且,經(jīng)驗回放保證了一個樣本可以多次參與訓練,從而提高學習效率。每個訓練步驟中生成的四元組et=〈st,at,st+1,rt〉保存在經(jīng)驗回放池中。

⑤目標網(wǎng)絡

在訓練階段,本文使用目標網(wǎng)絡來計算TD目標,SGD只更新DQN的參數(shù),而不更新目標網(wǎng)絡的參數(shù)。原因在于,即便衛(wèi)星任務分配問題中分配動作并非最優(yōu),但其獎勵通常是正值,并且會出現(xiàn)類似于DQN的高估問題,這會導致每次使用二元組〈st,at〉更新多分支DQN參數(shù)ω時,該模型往往會高估〈st,at〉的Q值。TD目標計算如下:

(6)

式中:γ為折扣因子獎勵。目標網(wǎng)絡的參數(shù)ω-定期更新,多分支DQN中目標更新間隔T根據(jù)經(jīng)驗設置為100。目標網(wǎng)絡的參數(shù)通過計算ω和ω-的加權平均值來更新,然后再將值分配給ω-。

⑥損失函數(shù)

考慮到Q函數(shù)的自洽性,按照最小化Q(st,at;ω)和TD目標yt估計誤差的原則更新動作價值函數(shù)。在一個訓練輪次中,通過模型推理獲得狀態(tài)st和st+1之間的獎勵值rt后,可以得到本次狀態(tài)轉移的四元組〈st,at,st+1,rt〉,隨后損失函數(shù)L(ω)由以下等式計算:

L(ω)=E[(yt-Q(st,at;ω))2],

(7)

式中:yt通過式(6)計算。

2.3 網(wǎng)絡結構

本節(jié)描述所提出的多分支DQN的網(wǎng)絡結構,包括其RP分支、TL分支和Value分支,以及其詳細網(wǎng)絡結構,如圖3所示。

圖3 多分支DQN的模型結構示意Fig.3 Structure of the proposed multi-branch DQN model

RP分支是卷積神經(jīng)網(wǎng)絡(CNN),由卷積模塊組成,每個模塊由卷積層、BN層和ReLU激活組成。衛(wèi)星資源池狀態(tài)矩陣srp(根據(jù)式(2)計算)的輸入大小為N×N,類似于2D圖像,因此,RP分支使用CNN的結構更有利于提取衛(wèi)星資源池狀態(tài)的判別特征frp。RP分支的作用是從輸入srp中提取特征,并將其作為推導動作價值函數(shù)的判決條件。TL分支是一個全連接(Fully Connected,FC)神經(jīng)網(wǎng)絡,其輸入序列為衛(wèi)星任務列表stl(由式(1)計算得到)經(jīng)序列化后通過FC層從中提取特征,輸入大小為3×M。TL分支的目標是從輸入stl中提取特征,這些特征與frp一起用于估計動作價值函數(shù)。RP分支和TL分支是并行的,它們的輸出通過Concat層連接起來。然后,將frp和ftl連接起來,生成用于動作價值函數(shù)估計的全局特征f,隨后將其用作Value分支的輸入來計算Q(st,at;ω)。與TL分支類似,Value分支也是基于FC層的神經(jīng)網(wǎng)絡。

TL分支、RP分支和Value分支共同構成了多分支DQN的整體結構,如表1所示。與一般的強化學習模型相比,該模型結合了多種衛(wèi)星資源類型的特點,更適合不同類型的狀態(tài)輸入,更加關注衛(wèi)星通信系統(tǒng)的資源狀態(tài)。特別是,根據(jù)要解決的衛(wèi)星分配問題的復雜性(例如任務數(shù)量、資源池塊劃分的大小),可以利用更深、更復雜的網(wǎng)絡作為該模型的骨干。然而,主干結構的選擇超出了本文的范圍。為了簡化,多分支DQN僅采用相對較淺的網(wǎng)絡進行調查。

RP分支輸入的高度和寬度均為N。在第三個卷積層使用了擴展特征圖的技巧(表1中的Conv3)。再改模型中還采用批量歸一化和Dropout來緩解ICS與過度擬合問題。在模型訓練完成后,進行去BN操作,以提高模型的推理速度,進一步減少衛(wèi)星通信任務調度時間。

3 實驗設置與結果分析

3.1 數(shù)據(jù)集和實驗設置

由于當前缺少公開衛(wèi)星通信任務調度數(shù)據(jù)集,本文使用了2種隨機生成方法來生成衛(wèi)星任務列表數(shù)據(jù)集,并進行深度強化學習模型的訓練。第一種方法是零浪費衛(wèi)星任務列表數(shù)據(jù)集生成方法[17],可以用于比較不同分配方法之間的性能。第二種是非零浪費數(shù)據(jù)集生成方法,這種方法更符合衛(wèi)星任務列表的實際情況。

在所有實驗中,批量大小固定為32,使用SGD優(yōu)化器,針對不同的episode,動量為0.9,權重衰減為0.000 5。在所有卷積和全連接層后添加BN和ReLU層,并通過Kaiming初始化[18]來初始化參數(shù)。為了消除隨機因素,在訓練模型時手動固定隨機種子,以確保模型的初始化參數(shù)在不同實驗運行中保持一致,避免影響對比實驗的有效性和合理性。TL分支、Value分支和RL分支的初始學習率分別設置為0.001、0.001和0.01。經(jīng)驗回放池的緩沖區(qū)大小設置為1×105,經(jīng)驗回放的超參數(shù)設置如下:分別為α=0.3、β=0.5和η=0.000 005。梯度裁剪設置為20,折扣因子獎勵γ設置為0.95。目標網(wǎng)絡解決了訓練階段的高估問題,目標更新間隔為100。非負乘數(shù)ε根據(jù)經(jīng)驗設置為0.1。

3.2 實驗結果與分析

基于3.1節(jié)中生成的零浪費和非零浪費數(shù)據(jù)集,本文對任務調度性能和運行時間性能進行了對比實驗,證明了所提出的多分支DQN模型的有效性。具體來說,本文的對比實驗如表2所示,主要比較了本文方法與傳統(tǒng)貪婪算法和啟發(fā)式算法的性能。此外,還分析了實驗結果以及基于強化學習的多分支DQN模型如何影響衛(wèi)星通信任務調度算法。

表2 本文方法與其他算法在零浪費數(shù)據(jù)集的對比Tab.2 Comparisons of the proposed multi-branch DQN with existing methods on the zero-waste dataset

由表2可以看出,與貪心算法和啟發(fā)式算法相比,在零浪費數(shù)據(jù)集上進行測試時,多分支DQN在平均資源占用性能(AOP)和運行時開銷(RO)方面都有顯著改善。本文方法與貪心算法(Bottom Left[13])相比,可以在時限允許范圍內大幅提高AOP指標,并且隨著衛(wèi)星任務數(shù)量的增加,本文方法的性能提升更加明顯。例如,當M=40時,本文方法的性能(95.1%)明顯高于GA-PSO[15](93.9%)。這是由于多分支Q網(wǎng)絡模型能夠從先前的經(jīng)驗中學習,不同的分支可以準確地學習和提取多狀態(tài)特征,而不是對每個預測進行啟發(fā)式探索。特別是對時間復雜度而言,本文方法(1.47 s)可以顯著降低完整任務調度過程的運行時開銷(32.54 s)。原因在于與GA-PSO等啟發(fā)式算法相比,基于強化學習的方法消除了迭代過程時間,而多分支Q網(wǎng)絡模型的訓練過程雖長但可以離線進行,實際中僅使用訓練好的模型進行推理。

本文還在非零浪費數(shù)據(jù)集中進行了對比實驗,來更廣泛的評估多分支Q網(wǎng)絡模型的性能,模型的訓練和測試的參數(shù)設置相同。實驗結果如表3所示,與零浪費數(shù)據(jù)集上的實驗結果相似。由于非零浪費,無法知道該數(shù)據(jù)集上的最優(yōu)分配結果,但仍然可以使用AOP來比較每種方法的性能。與GA-PSO相比,本文方法在M=40時,AOP(89.6%)和運行時開銷(1.52 s)方面也取得了更好的性能。

表3 本文方法與其他算法在非零浪費數(shù)據(jù)集的對比Tab.3 Comparisons of the proposed multi-branch DQN with existing methods on the non-zero waste dataset

從表2和表3可以得出結論:① 本文所提出的多分支Q網(wǎng)絡模型與Bottom Left和GA-PSO相比,在非零浪費和零浪費數(shù)據(jù)集均取得更好的AOP,并且隨著任務數(shù)量的增加,性能的提升變得更加明顯。② 與GA-PSO等啟發(fā)式算法相比,本文模型具有分配運行時間更短的優(yōu)點,這是由于多分支Q網(wǎng)絡模型在推理階段不需要啟發(fā)式算法的迭代過程,而大部分時間僅消耗在模型的訓練過程上。以上結果證明,訓練后的基于多分支的DQN模型能夠有效解決衛(wèi)星通信任務調度問題,TL分支和RP分支能夠準確提取衛(wèi)星資源池狀態(tài)和衛(wèi)星任務狀態(tài)的判別特征。實驗結果驗證了強化學習算法在衛(wèi)星通信任務調度問題上的應用效果。

4 結束語

本文提出多分支Q網(wǎng)絡模型是一個基于透明轉發(fā)器的衛(wèi)星通信任務調度問題的強化學習解決方案。通過在網(wǎng)絡中引入TL分支和RP分支,準確提取資源池和任務列表的判別特征?；贒QN的結構,通過Value分支選擇包括優(yōu)先級和任務索引號在內的多種動作價值函數(shù),大大提高了平均占用率和時間消耗的性能。綜合實驗表明,提出的模型在生成的零浪費任務數(shù)據(jù)集和非零浪費任務數(shù)據(jù)集上為比傳統(tǒng)的貪婪方法和啟發(fā)式方法表現(xiàn)得更好。這些實驗結果表明了本文方法在解決衛(wèi)星通信任務調度問題方面的有效性和可靠性。