無線網絡中基于深度Q學習的傳輸調度方案

朱江，王婷婷，宋永輝，劉亞利

（重慶郵電大學移動通信技術重點實驗室，重慶 400065）

1 引言

近年來，隨著無線通信技術的不斷發展，各種新型的通信網絡越來越多，區域化的具有小覆蓋范圍的通信模型逐步興起，如應用于室內環境的毫微微網絡、無線接入點等。為保證用戶的通信質量需求，這些以小型基站和接入點為代表的調度節點需要及時處理大量的數據。因此，對其硬件和軟件的處理速度、能耗等的要求就越來越高。在中繼調度節點轉發數據的過程中，如果節點沒有足夠的緩存區空間，那么將會造成數據分組的丟失，而且較差的信道狀態也不能實現高效傳輸，造成能量的浪費。因此，無線網絡中的有效傳輸逐漸成為當前學者的研究熱點之一。

針對中繼節點的傳輸調度問題，文獻[1]考慮單個發送機，在建立馬爾可夫決策過程模型的基礎上，通過引入拉格朗日乘子法和黃金分割搜索方法構建了一種無線電網絡的傳輸調度方案，該方案可以在滿足緩存區的分組丟失率的約束下，最小化平均功率。文獻[2]在MDP模型的基礎上考慮具有中心節點的無線傳輸網絡，通過 W 學習算法來指導中繼節點為其他節點傳輸數據。文獻[3]在圖形博弈的基礎上引入了學習算法，通過次梯度迭代算法來交換多個代理之間的信息，讓單個代理來學習自己周圍的環境信息，并據此來指導節點選擇信道傳輸數據。文獻[4]同樣將無線傳輸問題描述為MDP過程，通過設定新的目標函數來實現延長終端壽命的目的。不過，該文使用策略迭代的方法來對 MDP的調度問題進行求解，該方法具有較大的求解計算量。現有文獻在解決數據傳輸的問題時，較多關注于單方面的優化目標，沒有綜合考慮這些方面。此外，在快速時變的環境下，系統在進行求解計算中有大量的信息交互，容易產生維災難，很難做到快速收斂。目前，針對此類問題的研究較少，文獻[1,2]采用狀態聚合和行動集縮減的方法來減小系統計算規模，但此種方法需要根據具體問題重新定義狀態空間和行動集。

本文在無線網絡數據傳輸問題中，綜合考慮數據分組的丟失、能耗以及系統的吞吐量。在實際的無線網絡中，合理的假設是環境信息未知，即中繼節點不能事先知道環境狀態的轉移概率。為此，在建模為MDP的系統模型中，通過Q學習的強化學習方法使中繼調度節點對周圍環境狀態的轉移信息進行學習，并對節點的行為進行指導。在狀態行為獲取中，為了考慮探索與利用的均衡，改進策略選擇方法，提出了基于行為評價值Q和Index(s,a)索引值的綜合行為評價方法，以獲取更優的狀態行為數據。另外，基于強化學習獲得的行為數據，使用深度學習方法來構造狀態和行為之間的映射關系，達到快速求解的目的。

2 系統模型

在無線網絡環境下，數據傳輸模型如圖1所示。系統中存在K個待傳輸數據的節點，每個節點對應的緩存區長度為L，存在一個中繼節點可以為K個用戶傳輸數據，并假設該節點可用的頻譜資源的個數為M，且各個節點之間和頻譜之間相互獨立。假設節點的上層數據以到達率為λ的泊松分布到達，并存儲在對應的緩存區內。每一幀內，中繼節點選擇一個信道狀態較好的信道為一個節點傳輸數據。當緩存區中的數據滿時，如果中繼節點沒有為它傳輸數據，那么當下一幀再有數據到達時會造成數據的丟失。

圖1 數據傳輸模型

2.1 信道狀態

定義時間基本單位為幀Tf，且在每一幀內信道的狀態保持不變，信道的狀態轉移發生在2個相鄰的狀態之間。將塊衰落信道狀態建模為一階的有限狀態馬爾可夫鏈（FSMC,finite state Markov chain）[5]。在FSMC信道狀態模型中，存在加性高斯白噪聲的信道接收信噪比（SNR,signal-to-noise ratio）服從瑞利分布，其概率密度函數表示為其中，ρ＞0，且表示平均接收信噪比。若信噪比門限設為那么，根據接收信噪比門限，可以將信道劃分為多個狀態信道狀態概率為

信道的狀態轉移概率為

2.2 緩存器狀態

在每一幀內，每個節點對應緩存區中的數據分組到達服從到達率為λ的泊松分布di為在每幀內到達的數據量。

定義在時刻i節點k對應的緩存區中的數據分組數為 lk,i，如果每幀到達的數據分組為 dk,i，傳輸的數據分組為 tk,i，那么，節點k對應的緩存區中的數據量為那么，系統中緩存器的狀態轉移概率為

2.3 發送功率

中繼節點在通過信道發送數據的時候采用自適應調制（AM,adaptive modulation）的方式(j-QAM)[6～8]，用 j = 1 ,2,3,4,…來表示選中的方式。通過限定傳輸方式下的誤碼率（BER,bit error ratio），可以得到在不同狀態和傳輸方式下滿足誤碼率要求時的最小功率[8]。

當 j = 1 時，有

當 j ＞ 1 時，即 j = 2 ,3,4,…時，有

其中， W N0表示噪聲功率。

3 傳輸調度的MDP問題分析

系統中存在2個狀態對象，分別是節點對應的緩存器的狀態和信道狀態。系統運行是一個狀態轉移的過程，系統在當前狀態下通過執行某個行為進入到下一個狀態。因此，傳輸調度問題可以建模為MDP[1,2,4]。

3.1 系統狀態轉移

定義系統的狀態 S為緩存器和信道的組合狀態，即S?B?C。如果緩存區的長度為L，那么，單個緩存區的狀態個數為B=L+1。信道的狀態個數為N。

中繼節點所采取的行為 A可以表示為當其值 ai,k=1時，表示在時隙i中繼節點為節點k來傳輸數據，其中，含有選擇的信道m和傳輸方式j信息。當 ai,k= 0 時，表示不采取任何行動。

在時刻 i，存在一個緩存區和一個信道的情況下，系統狀態處于 si時采取行為 ai后轉移到狀態的狀態轉移概率可以表示為那么，整個系統的狀態轉移概率為

3.2 系統收益和代價

高效傳輸是要實現在最大化吞吐量的同時最小化系統發送功率和分組丟失數。如果系統中信息的基本傳輸速率為v，那么，在使用不同的傳輸方式下的傳輸數據量為 t=v × 2j。在當前的系統狀態后，系統可以獲得的最大收益為下選擇行為

因此，定義系統的代價Co為緩存器的壓力值和傳輸功率的組合，即

定義系統的效用為O，該值與每一幀內傳輸的數據量成正比，與緩存器的壓力值和功耗成反比，可以得到該表達式

4 基于深度Q學習的最優行為獲取

在本文的MDP模型中，中繼節點通過學習來獲得系統的狀態參數。系統的狀態和行為是離散的，每執行一次行為，系統的狀態就會發生不連續的變化。因此，在求解此MDP問題時采用強化學習的方法來指導節點行為[10～12]。當系統規模較大時，往往存在較大的狀態行為空間，不宜直接對MDP進行求解。這里，使用QL算法實現對環境狀態信息的學習并獲得最優行為。在使用QL算法對此問題進行求解時，是一種逐步尋優的過程，所以很難實現行為選擇的快速收斂。由于深度神經網絡具有較好的泛化能力，幾乎可以實現任意非線性函數的逼近功能。所以，在QL算法的基礎上使用深度神經網絡的方法建立狀態和行為之間的映射關系，實現問題的加速求解[13～16]，以解決因系統狀態規模較大而導致的維災問題[17～18]。

4.1 QL算法

Q學習在與環境交互的過程中，通過不斷地試錯來找到最優的行為。該最優行為不僅關注立即收益，同時還考慮了未來n步的收益情況，用表示，即

Q學習算法中的Q值是狀態和行為的評價值，用立即收益和折扣收益來表示，即

其中， γ(0 < γ<1)是折扣系數，表示未來收益對當前行為的影響。Q學習的目標是為了最大化系統效用，用 Oi替換 ri，用來替換那么，可得

策略的探索與利用[19]是強化學習中的重要問題。尤其是當系統狀態規模較大時，如何有效地選擇行為，將直接影響算法的收斂速度以及形同的性能。本文引入基于行為評價值Q和Index(s,a)索引值的綜合行為評價方法，以獲取更優的狀態行為數據。

當系統處于狀態 si時，依據式(14)來選擇行為 ai。

其中，Q表示狀態和行為評價值。在Q值的基礎上，增加行為索引值來選擇可以最大化收益所對應的行為，表示為

其中，?是一個大于0的常量[20]， Ti(n)表示經過n次行為選擇之后，行為 ai被選擇的次數。 vi(n)表示偏差因子，引入了行為效用值的方差為，以反映該值波動性。

基于索引 I ndex(si,a)的行為選擇機制，一方面逐步考慮具有較大效用的行為，體現了利用的特性；另一方面，隨著迭代的進行，如果某個行為未被選擇或被選擇的次數 Ti(n)很少，那么，在接下來的選擇中會偏向于選擇該行為，體現了探索的特性。

在確定了執行行為后，中繼節點執行行為 ai，然后計算效用值O，并按照式(18)更新Q值。

其中，α (0 < α≤1)是狀態行為的學習因子，表示為

本文Q學習方法具體執行過程如算法1所示。

算法1 Q學習算法

1) 初始化行為訪問次數 Ti(n) = 0

2) 初始化狀態行為值 Q (si,ai) =0 及狀態行為查詢表

3) for episode1=1,I1do

4) 初始化行為向量 a ={a1,a2,…}

5) 對于當前狀態 si

6) for episode2=1,Ite do

7) if episode2=1

8) 隨機選擇一個行為 ai

9) end if

10) if episode2>1

12) 根據

ai←選擇行為

13) end if

14) 執行行為 ai，獲得效用值 Oi，得到下一個狀態 si+1

17) 更新查詢表

18) end for

19) end for

4.2 算法性能分析

定理1 式(10)定義的系統效用函數O的值在不同的系統狀態下有界。

證明見附錄A。

定理2 對于收益O有界的Q值迭代問題，學習因子0<α≤1，且

證明 見附錄B[20]。

4.3 深度行為映射網絡

采用多層的棧式自編碼（SAE,stacked auto-encoder）深度神經網絡模型來建立狀態和行為之間的對應關系，以最快獲取最優決策行為。模型的結構如圖2所示。

圖2 SAE網絡模型

模型的輸入層代表了系統的狀態信息，該層的神經元的個數為 K+M。輸入向量表示為Input = [l1…lKc1…cM]，分別代表了系統中的緩存器的狀態和信道狀態。輸出層神經元代表了行為選擇信息，輸出向量為 O utput = [a(k)a(m)a(j)]，分別表示在該系統狀態下，通過信道 m，以傳輸方式j為用戶k發送數據。該層的神經元個數為K+M+J。隱含層為多層，節點個數由式(21)確定。

其中， ni表示輸入層神經元個數， no表示輸出層神經元個數，Con為1～10的一個常數。

SAE模型使用sigmoid函數作為傳遞函數，訓練過程中的損失函數為 L (x)。

5 算法描述與比較

5.1 算法描述

基于深度Q學習的策略選擇算法流程如圖3所示。首先，使用Q學習算法經過一定時隙的學習獲取一部分狀態和行為數據，這個過程中不對 SAE進行訓練。隨著時間的進行，對于某些狀態逐漸找到最優行為，并存儲于Q查詢表中。使用該表中的信息進行有監督地訓練SAE網絡。當系統轉移到隱藏狀態時，通過 SAE網絡來實現該狀態下的行為映射。執行所推薦的行為并更新Q值，并將該狀態行為信息存儲于Q查詢表中。當后續時刻系統再轉移到該狀態時，直接通過查詢狀態行為表來獲得可執行的行為。

5.2 算法比較

在本文系統模型中，無線節點個數為K，緩存區的長度為L，信道個數為M，信道的狀態個數為C，可用的傳輸方式個數為J。那么，系統的狀態個數為S= (L+1)KCM，對于每一個系統狀態，可選的行為個數為A=KMJ。因此，系統的規?？梢员硎緸镈=SA。

圖3 基于Q學習的SAE行為獲取算法流程

為了驗證本文算法的性能，現分別與策略迭代法[4]、W學習方法[2]和隨機選擇方法進行比較分析。

1) 策略迭代法

當MDP問題被描述為式(23)時，可以通過策略迭代（SI,strategy iteration）法來求解最優決策。

在求解過程中，SI法需要預先知道系統的所有狀態信息和狀態轉移概率。然而，當系統的狀態空間較大時，需要求解與系統狀態等規模的線性方程，即S= (L+1)KCM個線性方程組，每一次迭代的計算復雜度會達到所以該算法易陷入維災問題，在實際問題中并不適用[21]。

2) W學習法

在W學習（WL,W learning）法中，首先使用Q學習方法獲得Q值，然后利用已獲得的值進行W學習。W值代表預計收益和實際收益的差值。

3) 隨機選擇法

隨機選擇（RS,random selection）法是在每一個系統狀態下，在行動集中隨機選擇一個行為執行，所以它的計算開銷較小。

本文算法只針對系統的當前狀態執行算法，不需要過多的環境狀態信息。各個算法的計算復雜度比較如表1所示。可知，本文算法復雜度較低，且不依賴于系統狀態的先驗信息。

表1 算法復雜度比較

6 仿真分析

本文仿真實驗考慮存在K=5個待發送數據的無線節點和一個智能中繼節點。其中，中繼節點可選信道個數為M=3，設定的信道狀態數為C=4，傳輸方式的個數為J=4。無線節點的緩存區長度為L=5。針對此問題，分別使用上述所描述的3種方法和本文方法進行性能對比。仿真的各項參數設置如表 2所示。結果分別通過圖 4～圖8說明。

表2 仿真參數

在I1時隙內是Q學習階段，通過QL方法來獲得最優狀態行為信息并存儲于查詢表中。

然后，使用這些信息來對SAE網絡進行有監督的訓練，并在接下來的時隙I2內進行對比實驗。

圖4所示的是系統分別處于狀態s1={l1=5,c1=3}、s2={l2=9,c2=4}和s3={l3=12,c3=2}時，使用 QL法的行為選擇中的Q值變化曲線。3種狀態在相同的數據到達率(λ=0.1)下，最終Q值逐漸收斂于不同的數值。

圖4 Q學習算法在不同狀態下Q值曲線

在不同的上層數據分組到達率下，不同算法的系統傳輸的數據量對比如圖5所示。由圖5可知，本文算法的數據傳輸量小于SI法的數據傳輸量，但是優于W學習法和RS法。從圖5可以看出，隨著數據分組到達率的增大，系統的吞吐量也逐漸增大。當系統中達到的數據分組越來越多時，系統相應的緩存器的壓力逐漸增加，這樣會使系統的效用減小。因此，在策略尋優時會增加數據的發送量以減小緩存器的壓力。到達率對于RS法影響較小，因為RS法在決策時并不考慮系統的狀態信息。

圖5 系統傳輸數據量對比

圖6 為在不同的數據到達率和不同的算法下系統的平均功耗對比。由圖6可知，RS法相對較為平穩。因為RS法并不受系統狀態信息的影響，所以，數據到達率λ對于RS傳輸方式選擇基本上沒什么影響，另外3種方法的功率則受λ的影響較大。當系統中的數據量較大時，緩存器的壓力較大，迫使中繼節點選擇更好的傳輸方式來發送更多的數據以減小緩存器的壓力，最終使功率消耗較大。3種方法的能耗均呈現出先快速增長，隨后平緩增長的趨勢。因為隨著緩存器中數據的增多，發送的數據越多，能耗越大，故功率曲線增長越快。因為緩存空間有限，當數據量達到了緩存的最大承受限度后，緩存壓力不再增大，因此，最終也趨于平穩。

圖6 系統平均能耗對比

當系統緩存器中的緩存空間較小時，如果下一幀到達的數據分組個數較多，會因為沒有足夠的空間而造成數據丟失。系統的平均分組丟失數如圖 7所示，隨著到達率的逐漸增大，4種算法的分組丟失數均逐漸增加。由于RS法在選擇行為時不考慮功耗和緩存壓力，因此，分組丟失數較大。相對來說其他3種方法的分組丟失數較小。而本文算法的分組丟失數雖然大于SI法獲得的最優值，不過仍小于W學習法的分組丟失數。

圖7 系統平均分組丟失數對比

系統的平均效用對比如圖8所示。由圖8可知，SI法、本文方法和W學習法的效用值均高于RS法。RS法在行為選擇時未考慮組成效用函數的各個參量因素。由圖8可知，本文方法的系統效用值雖然相較SI法小，但仍優于W學習法的效用值。隨著數據分組到達率的增大，這3種效用曲線均呈現出先增大后減小的趨勢。這是因為當λ較小時，系統可以同時選擇合適的行為方式來提升效用值。但是當數據量較大時，雖然系統在盡力傳輸數據但仍然不能做到數據的完全傳輸，同時在傳輸數據量較大時功耗也很大。因此，效用曲線呈現出先增大后減小的趨勢。

圖8 系統平均效用對比

7 結束語

針對無線網絡中的高效傳輸問題，本文建立了基于 MDP的系統模型。MDP模型是一個行為選擇以及狀態轉移模型，通過選擇最優的行為來最大化收益。本文提出使用深度 Q學習的人工智能算法對該MDP的傳輸決策問題進行求解，適合環境狀態信息未知，即狀態轉移概率未知的實際場景。在策略的求解問題中，策略迭代法往往能取得最優的策略，但是該方法易陷入維災問題，且在求解最優策略的過程中依賴于事先知道的狀態轉移概率。本文方案是在當前狀態下進行求解，不需要過多的環境狀態信息；并且，使用深度學習的方法來建立系統狀態和行為之間的映射關系，避免了強化學習過程的較大計算量，實現了快速求解，解決了維災問題。

附錄A 定理1證明

證明 式(10)是由 3個部分組成，分子為收益函數ri,j=v×2j,j= 1 ,2,3,…，表示每一幀能夠發送的數據量，是一個有限值。分母部分為系統代價(式(9))。其中，緩存區的壓力表達式為fk,i=exp(ρlk,i)，而緩存中的數據量是有界整數值。因此，f同樣是離散的有限值。由式(5)和式(6)可知，發送的功率與傳輸方式有關，因此，功率p也是離散有限值。所以，系統效用值有界。證畢。

附錄B 定理2證明

證明 定義初始函數為Q0(si,ai)，對于所有的si∈S和ai∈A均按照式(18)進行更新獲得最優值Q*(si,ai)。

對于函數Q*(si,ai)、O(si,ai)和Q0(si,ai)，使常量ε,η,?,ζ和γ,(0 <γ<1)滿足

其中，0<ε≤η<∞和0≤?≤ζ<∞，因為最優值是未知的，所以ε、η、?和ζ的值不能直接獲得。因此，需證明對于?ε、η、?、ζ，經過迭代后Q(si,ai)可以收斂得到最優。

如果0 ≤?≤ζ<1，那么對于?i=0,1,…，性能函數Qi( si,ai)滿足

下面，通過數學歸納法證明式(27)。

當 i = 0 時，有

同理可得

于是，當 i = 0 時，滿足式(27)。

假設當i=l-1，l=1,2,…時，仍滿足式(27)。那么，當i=l時，有

同理可得

因此，對 ? i = 0 ,1,2,…滿足式(27)。

接下來，證明當0 ≤ ?≤1 ≤ ξ<∞時，滿足

式(32)的左半部分可以通過式(28)和式(30)來證得。對于右半部分，令 i = 0 ，有

根據數學歸納法可以得到式(32)的右半部分。因此，當0 ≤ ?≤ξ<∞，可得對于 ? i = 0 ,1,2,…，評價函數滿足式(27)。

最后，根據以上結論，對于任意的常量ε、η、?和ξ，由式(27)～式(33)，當i→∞ 時，可得式(20)。證畢。

參考文獻：

[1]朱江,徐斌陽,李少謙. 一種基于馬爾可夫決策過程的認知無線電網絡傳輸調度方案[J]. 電子與信息學報,2009,31(8):2019-2023.ZHU J,XU B Y,LI S Q. A transmission and scheduling scheme based on Markov decision process in cognitive radio networks [J]. Journal of Electronics & Information Technology,2009,31(8):2019-2023.

[2]ZHU J,PENG Z Z,LI F. A transmission and scheduling scheme based on W-learning algorithm in wireless networks[C]//8th International ICST Conference on Communications and Networking in China(CHINACOM). 2013: 85-90.

[3]LI H,HAN Z. Competitive spectrum access in cognitive radio networks: graphical game and learning[C]//Wireless Communications and Networking Conference (WCNC). 2010: 1-6.

[4]林曉輝,譚宇,張俊玲,等. 無線傳輸中基于馬爾可夫決策的高能效策略[J]. 系統工程與電子技術,2014,36(7):1433-1438.LIN X H,TAN Y,ZHANG J L,et al. MDP-based energy efficient policy for wireless transmission[J]. Systems Engineering and Electronics,2014,36(7):1433-1438.

[5]WANG H S,MOAYERI N. Finite-state Markov channel-a useful model for radio communication channels[J]. IEEE Transactions on Vehicular Technology,1995,44(1): 163-171.

[6]GAO Q,ZHU G,LIN S,et al. Robust QoS-aware cross-layer design of adaptive modulation transmission on OFDM systems in high-speed railway[J]. IEEE Access,2016,PP(99): 1.

[7]CHEN X,CHEN W. Delay-optimal probabilistic scheduling for low-complexity wireless links with fixed modulation and coding: a cross-layer design[J]. IEEE Transactions on Vehicular Technology,2016: 1.

[8]LAU V K N. Performance of variable rate bit interleaved coding for high bandwidth efficiency[C]//The Vehicular Technology Conference.2000:2054-2058.

[9]CHUNG S T,GOLDSMITH A J. Degrees of freedom in adaptive modulation: a unified view[C]// IEEE Transactions on Communications. 2001:1561-1571.

[10]WEI Q,LIU D,SHI G. A novel dual iterative Q-learning method for optimal battery management in smart residential environments[J].IEEE Transactions on Industrial Electronics,2015,62(4):2509-2518.

[11]NI J,LIU M,REN L,et al. A multiagent Q-learning-based optimal allocation approach for urban water resource management system[J].IEEE Transactions on Automation Science & Engineering,2014,11(1):204-214.

[12]SILVER D,HUANG A,MADDISON C J,et al. Mastering the game of Go with deep neural networks and tree search[J]. Nature,2016,529(7587):484-489.

[13]WEI C,ZHANG Z,QIAO W,et al. An adaptive network-based reinforcement learning method for MPPT control of PMSG wind energy conversion systems[J]. IEEE Transactions on Power Electronics,2016: 1.

[14]KIM T,SUN Z,COOK C,et al. Invited-cross-layer modeling and optimization for electromigration induced reliability[C]// Design Automation Conference. 2016:1-6.

[15]COMSA I S,ZHANG S,AYDIN M. A novel dynamic Q-learning-based scheduler technique for LTE-advanced technologies using neural networks[C]// Conference on Local Computer Networks.2012:332-335.

[16]TENG T H,TAN A H. Fast reinforcement learning under uncertainties with self-organizing neural networks[C]// IEEE / WIC / ACM International Conference on Web Intelligence and Intelligent Agent Technology. 2015:51-58.

[17]KOBAYASHI T,SHIBUYA T,TANAKA F,et al. Q-learning in continuous state-action space by using a selective desensitization neural network[J]. IEICE Technical Report Neurocomputing,2011,111:119-123.

[18]周文云. 強化學習維數災問題解決方法研究[D]. 蘇州: 蘇州大學,2009.ZHOU W Y. Research on the curse of dimensionality in reinforcement learning[D]. Suzhou: Soochow University,2009.

[19]LIU W,LIU N,SUN H,et al. Dispatching algorithm design for elevator group control system with Q-learning based on a recurrent neural network[C]// Control and Decision Conference. 2013:3397-3402.

[20]WEI Q,LEWISF L,SUN Q,et al. Discrete-time deterministic Q-learning: a novel convergence analysis[J]. IEEE transactions on cybernetics,2016: 1-14.

[21]李軍,徐玖平. 運籌學:非線性系統優化[M]. 北京: 科學出版社,2003.LI J,XU J P. Operations research: nonlinear system optimization[M].Beijing: Science Press,2003.