基于多分支深度Q網絡模型的衛星通信任務調度方法

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

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

0 引言

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

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

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

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

1 衛星通信任務調度問題

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

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

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

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

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

2.1 強化學習問題定義

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

2.2 多分支DQN模型建模

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

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

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

①狀態空間

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

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

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

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

(2)

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

②動作空間

在衛星通信任務調度問題中,可用動作空間A(s)是衛星控制系統的決策空間,根據t時刻的當前狀態st從A(s)中選擇動作at。可用的操作空間取決于分配的資源的類型和資源的限制,包括優先動作空間Ap和選擇動作空間Ac。形式上,A(s)可以定義為:

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

(3)

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

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

(4)

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

③獎勵

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

(5)

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

④經驗回放

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

⑤目標網絡

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

(6)

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

⑥損失函數

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

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

(7)

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

2.3 網絡結構

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

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

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

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

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

3 實驗設置與結果分析

3.1 數據集和實驗設置

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

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

3.2 實驗結果與分析

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

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

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

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

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

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

4 結束語

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