基于強化學習的802.11ax上行鏈路調度算法

黃新林 鄭人華

(同濟大學電子與信息工程學院 上海 201800)

1 引言

如今，無線局域網(Wireless Local Area Network, WLAN)的用戶數正不斷增長。除此之外，物聯網(Internet of Things, IoT)的迅猛發展也帶來了大量需要接入無線網絡的機器設備，導致在有限的地理區域內存在許多的接入點(Access Point,AP)和更多的站點(STAtion, STA)。同時，在物聯網場景下，醫療、火警、交通等方面的傳輸業務相對于普通業務有更高的服務質量(Quality of Service,QoS)要求，上傳數據時需要保證這些業務的優先級和實時性等。在上述的密集用戶環境(dense user environments)中，來自相鄰設備的干擾增加以及來自信道爭用的嚴重沖突導致網絡性能下降，無法提供良好的用戶體驗。因此，IEEE標準協會(IEEE Standards Association, IEEE-SA)標準委員會于2014年3月批準了802.11ax[1]協議以提高每個用戶的平均吞吐量并應對密集接入問題。802.11ax的上行鏈路包括兩種接入方式：隨機接入(Random Access, RA)和調度接入(Scheduled Access, SA)[2]。為了保證物聯網設備上傳數據的準確性和傳輸的低延時，需要減少沖突，使用調度接入是更好的選擇。本文研究的重點是正交頻分多址(Orthogonal Frequency Division Multiple Access, OFDMA)技術和802.11ax上行鏈路的調度接入問題。

調度接入算法并非新的研究方向，長期演進(Long Term Evolution, LTE)已經使用了OFDMA技術并且對調度問題進行了深入的研究[3]，調度算法包括首次最大擴展(First Maximum Expansion,FME)、遞歸最大擴展(Recursive Maximum Expansion, RME)等[4]。使用運營商頻段的LTE，可以進行時域和頻域兩個維度的調度，即可以對每個資源塊(Resource Block, RB)進行單獨分配。802.11ax則不行，因為它還保留了載波偵聽多路訪問/沖突避免(Carrier Sense Multiple Access with Collision Avoid, CSMA/CA)技術。該技術已經固定了管理幀、數據幀和幀間隔的時間長短，所以無法實現時域維度的調度。除此之外，802.11ax上行鏈路調度的子信道資源，即資源單元(Resource Unit, RU)[5]的大小可變，使得LTE的調度算法難以遷移到802.11ax中。

802.11ax中上行鏈路的傳輸效率很大程度上取決于這些RU的調度方式。標準中提供了靈活的框架，卻沒有定義任何調度算法，這給本文的研究帶來了可能性。Bankov等人[6]提出了一種通用的方法，可用于使現有的LTE調度器能適應802.11ax的特性，并證明OFDMA是在密集用戶環境中提供高質量服務的關鍵技術。Wang等人[7]針對實際的上行鏈路RU調度問題，提出了兩種實用算法：貪婪算法和遞歸算法，仿真結果表明遞歸調度非常接近最優調度。

以上的研究均沒有關注密集用戶環境下的物聯網場景，并且泛化能力不足。物聯網場景具有接入量大、實時性要求高、低功耗等特點，不同業務具有不同的QoS要求。針對這個場景，本文提出一種基于強化學習的802.11ax上行鏈路調度算法。首先建立系統模型并將RU調度問題轉化為0-1背包問題；然后引入指針網絡模型并使用演員-評論家(Actor-Critic)[8]強化學習算法進行訓練，增強算法的泛化能力；最后使用訓練好的模型去調度RU資源，并在上行鏈路中進行仿真。仿真結果表明，在物聯網場景下相比于經典的調度算法，本文算法具有更好的表現，能夠保證各個STA的QoS要求和公平性，并且具有更好的穩定性和用戶體驗。

2 IEEE 802.11ax的上行鏈路

IEEE 802.11ax是一項WLAN標準，其標準草案由 I E E E 標準協會的T G a x 工作組制定。802.11ax制定之初所關注的就是密集用戶環境，其設計思想與以往的802.11標準存在差異。由于非授權頻段的資源有限，因此為了提高資源利用率從而克服密集接入問題，引入了OFDMA，雙向多用戶多輸入多輸出(Multi-User Multiple-Input Multiple-Output, MU-MIMO)等技術，并采取了最高支持1024-正交振幅調制(Quadrature Amplitude Modulation, QAM)的調制方式，基本服務集(Basic Service Set, BSS)著色等措施[9]。

802.11ax標準中的信道被劃分成若干大小為78.125 kHz的子載波(tone)。一定數量的子載波構成了標準中的RU。根據子載波數的不同，RU可以分為7種，它們分別為：26 tones,52 tones,106 tones,242 tones,484 tones,996 tones和2×996 tones。因此，OFDMA將現有的802.11ax信道(大小包括20, 40, 80和160 MHz)劃分為一個個包含特定數量子載波的RU。如圖1所示，20 MHz信道可以被劃為若干大小不同的RU，不考慮MU-MIMO的情況下最多可容納9個STA同時上傳數據。如何分配這些RU給各個STA的方案并未在標準中定義，這為找到改善頻譜效率的優化調度算法提供了可能性。

圖1 使用各種大小的RU劃分20 MHz的信道

如圖2所示是實際系統中的802.11ax上行鏈路調度接入過程[10]。按照時間順序，AP總共會向所有STA發送3個觸發幀以獲取特定的反饋信息或進行資源調度。首先，AP會發送類型為緩存狀態報告輪詢(Buffer Status Report Poll, BSRP)的觸發幀1，請求各STA反饋緩存狀態報告(Buffer Status Reports, BSR)信息，其中包含調度所需的緩存數據量和QoS值。然后，AP會使用調度算法計算每個STA應該如何分配RU。再發送多用戶請求發送(Multi-User Request To Send, MU-RTS)幀，即觸發幀2，來實際分配RU資源，從而避免上行鏈路沖突的發生，盡可能提高每個用戶的吞吐量。各STA在接收到該幀后需要反饋準許發送(Clear To Send, CTS)幀，告知AP已知曉并認可當前的資源分配[11]。AP接收到CTS后會接著發送觸發幀3，通知各STA開始在對應的RU上進行上行鏈路傳輸。值得注意的是，由于802.11ax的上行傳輸是基于幀的，所以當存在不同步的情況時，需要在數據幀最后添加PAD。最后，當上行鏈路的數據傳輸完成后，AP會向各STA發送多站點塊確認(Multi-Station Block Acknowledgement, MS-BA)幀進行確認。

圖2 基于OFDMA的802.11ax上行鏈路調度接入過程

常用的調度算法有輪詢算法和比例公平算法。Filoso等人[12]設計了一種基于比例的資源分配算法(Proportional-based Resource Allocation, PRA)，該算法利用各個STA上傳的QoS信息和緩存數據量進行有效的RU分配，并同時考慮了優先級和公平性，但其算法結構固定，無法應對更為復雜的網絡環境。而Bai等人[13]提出了一種自適應STA分組算法，該算法使用基于BSR的兩階段機制來克服IEEE 802.11ax面對的密集網絡挑戰。自適應分組算法雖然能夠利用分組來有效避免沖突，減少系統能耗。但是其分組方案較為復雜，且每個分組會輪流使用信道，這導致它只能較好地保障公平性和組內優先級排布，而缺乏組與組之間優先級的保障。本文所提調度算法旨在將自適應RU調度問題抽象成背包問題，并使用指針網絡模型和強化學習算法予以解決。最終讓AP合理分配RU資源給各個STA，實現優先級和公平性的雙重保障，并具備較強的泛化能力和調節能力。

3 基于強化學習的上行鏈路調度算法

在本節中，首先介紹本文建立的上行鏈路系統模型，再提出自適應RU調度問題，然后使用指針網絡對問題進行建模，并利用Actor-Critic強化學習算法對指針網絡進行訓練，從而實現IEEE 802.11ax上行鏈路的RU調度。本文提出的基于強化學習的802.11ax上行鏈路調度算法，用于幫助AP給每個STA合理分配RU資源，以實現有效而公平的通信。

3.1 系統模型

本文建立的系統模型是由1個AP和nSTA個STA構成的物聯網場景下的802.11ax網絡，研究的數據傳輸路徑是上行鏈路。本文的調度算法要使用到所有STA的BSR，其中包含它們的緩存數據量和QoS值。QoS值指示了STA業務的優先級，如表1所示。其數值越小對應的優先級就越高，對傳輸數據低延遲的要求也越高[14]。

表1 QoS值與業務類型對應關系

為了便于仿真實驗對系統模型進行一些簡化：

(1) 僅考慮了調度接入的RU分配。

(2) 僅將1個RU分配給1個STA，不考慮MU-MIMO。

(3) 每次AP將RU分配給STA的數據流時，將占用一個完整的時間窗(Tw)時間。

(4) 所有仿真使用相同的信道帶寬。

3.2 自適應RU調度問題

對于以上系統模型，理想情況下，只要保證QoS值小(優先級高)的STA能優先獲取RU，及時上傳數據就能完成有效的通信。但對于實際場景并非如此，由于物聯網場景下，連接數巨大，QoS值小的STA數量太多，可能會導致某些QoS值大(優先級低)的STA長期處于等待RU分配的狀態，使得整個網絡的公平性無法保障。

因此，為了評估調度算法能否既滿足了QoS需求又保障了公平性，本文設計一種價值函數。根據STA上行數據流的數據量、QoS值和等待時間，共同計算該STA傳輸數據的價值，價值越高表示數據流在上行鏈路中的傳輸優先級越高。

3.3 指針網絡模型

背包問題是一類經典的組合優化問題。在面對大規模的背包問題時，傳統的啟發式算法并不能保證得到最優解。因此本文提出使用指針網絡模型來解決背包問題，并用強化學習算法來訓練指針網絡。

表2 不同MCS與不同RU大小情況下的數據傳輸速率(Mbps)

圖3 指針網絡結構圖

3.4 指針網絡訓練過程

強化學習通過與環境互動不斷改善策略，使得最終獲得的累計獎勵最大化[17]，是解決組合優化問題的重要機器學習算法。本文使用Actor-Critic算法來優化指針網絡的參數θ，將指針網絡作為Actor。在輸入序列為c，策略為p的情況下定義解碼器輸出的價值之和為V(π|c)。因此，Actor的最大化目標函數為式(10)

為獲得最優的調度策略需要最大化目標函數，使用策略梯度方法優化指針網絡參數θ。根據REINFORCE算法，可以得出訓練目標的梯度為式(11)。為保證價值越高的實例被選擇的概率越大，需要采用隨機梯度上升法來更新網絡參數，如果采用梯度下降法更新，則式(11)要取相反數

其中，b(c)是 不依賴策略p的基線函數，目的是減小

最終，使用Actor-Critic算法訓練指針網絡的過程如表3所示。

表3 Actor-Critic算法訓練指針網絡的過程

3.5 算法實際調度過程

與指針網絡訓練過程類似，構建新的指針網絡模型，將訓練好的參數θ導入到新的模型中，形成調度策略p?(π?|c)。然后在每個時間窗中，將各個STA的數據流編碼為2維向量ci=(wi,vi)。 再將nSTA個站點組成的背包實例序列c={ci}ni=ST1A輸入到指針網絡的編碼器中，通過解碼器結合注意力機制輸出選擇的背包實例序列π?(

4 仿真實驗與對比分析

本文使用pytorch搭建了用于求解802.11ax上行鏈路自適應RU調度問題的指針網絡，并使用Actor-Critic算法對其進行了訓練，最終實現了基于強化學習的上行鏈路調度算法，在指針網絡中設置輸入層大小為2，隱藏層大小l為128，訓練采用Adam優化器，學習率設定為10–4。同時，為模擬真實場景，在MATLAB中使用WLAN工具箱搭建了802.11ax上行鏈路仿真模型，并按照實際系統設置參數。在仿真模型中設置信道帶寬(背包大小)為20 MHz，并且采用TGax NLOS室內信道模型；時間窗大小Tw為 1 ms；STA數量nSTA為120；STA的天線數為4，但未使用MU-MIMO技術；信道編碼方式則采用LDPC。仿真過程中，將超參數、指針網絡參數和各STA的等待時間等參數直接存儲于AP中。并將指針網絡模型加載到AP中。同時，在RU分配之前，調度所需的緩存數據量和QoS值會由各STA上傳給AP。保證了AP在每次調度RU資源之前都能即時獲得需要的所有參數。而在上行傳輸結束后，還可以根據AP實際接收的數據得到各STA的吞吐量和數據流價值，便于算法測試以及對比分析。

本文算法的仿真結果如圖4所示。圖4展示了其中5個STA在上行傳輸中吞吐量隨時間變化的結果，用于分析QoS值在本文算法中的影響。每個STA的總緩存數據量為37 MB，MCS都為7，因為MCS相同所以吞吐量可以直接反映出占用RU資源的大小。STA1, STA21, STA41, STA61, STA81的QoS值分別為1, 2, 3, 4, 5。由于這5個STA涵蓋了所有可選的QoS值，將它們作為其余QoS值與之相同STA的代表，便于展示。從圖4可以看出，QoS值較小的STA能夠優先獲得AP調度的RU資源，并且RU的平均大小也比QoS值較大的站點更大，所以平均吞吐量較高，因此能夠在相同緩存數據量的情況下，更早地結束上行傳輸。同時，QoS值較大的STA雖然優先級較小，但并未產生“餓死”現象，雖然平均吞吐量較低，但也能被AP分配到適當的RU資源。并且從圖4中30 s之后展示的曲線來看，QoS值較大的STA在優先級較高STA的信息傳輸完畢后，還能在本文算法的調度下立即獲取更大的RU資源，保持了較高的信道利用率，沒有造成資源浪費。因此，可以總結：本文算法既能夠保證QoS值較小的STA可以優先傳輸大量數據、占用更大的RU資源，又能保證整個上行鏈路的公平性，不會造成“餓死”現象的發生。

圖4 本文算法的吞吐量隨時間變化的仿真結果

IEEE 802.11ax中的調度算法有輪詢調度算法、PRA算法和自適應分組算法。因此，接下來會將本文所提上行鏈路調度算法與3者相比較，分析優劣與適用場景。

如圖5所示，是4種算法對于STA1(q1=1,m1=7)和STA63(q63=4,m63=5)的RU調度情況在吞吐量上的直接反映，STA1和STA63分別代表了QoS值較小和QoS值較大的兩種STA。從圖5(a)可以看出相比于另外3種調度算法，本文算法能夠優先且穩定地分配更大的RU資源給QoS值較小的STA，保證業務優先級高數據流的低延時和高吞吐，讓STA1在30 s以內就能將數據上傳完畢，早于其他算法。而在圖5(b)也可以看出，本文算法相比于另外3種算法略微延長了QoS值較大的STA63的傳輸時間。雖然STA63的平均吞吐量較小，但并未出現“餓死”現象，說明本文算法保證了STA之間的公平性，且調度RU資源過程相較于PRA算法更穩定。圖5(c)則展示了各算法在STA業務類型隨時間變化時的適應能力。圖中STA1的QoS值在最初5 s內為1，5～15 s變為5，15 s后一直保持為2，而其余STA的業務類型保持不變。從仿真結果可以發現除輪詢算法以外的3種算法都具有QoS自適應能力，且本文算法與自適應分組算法的業務類型跟蹤能力較PRA算法更優秀，調節更及時，吞吐量波動更小，傳輸更穩定。

圖5 4種算法下STA1和STA63的吞吐量隨時間變化的仿真結果

4種算法的仿真結果中，各個STA的平均等待時間也有所不同。如表4所示是5個STA代表在4種算法中因AP連續未分配RU資源而等待的平均時間。總體來看，輪詢算法和自適應分組算法的平均等待時間較公平，即不具備優先級區分。自適應分組算法組內具有一定優先級保障，組間則沒有，其平均等待時間與分組數正相關。而本文算法和PRA算法都對各STA實現了優先級劃分，且本文算法平均等待時間更短。說明本文算法兼具優先級和公平性保障，既能讓優先級高的業務平均等待時間更短，又能保證不同STA的平均等待時間相差不大。即實現了更穩定而公平的RU調度。

表4 4種算法下5個STA代表的平均等待時間(ms)

圖6展示了在4種算法的調度過程中，上行鏈路數據流總價值隨時間變化的情況。可以發現，本文算法在調度開始的55 s內，上行數據流的總價值都是高于另外3種算法的，而輪詢算法、PRA算法和自適應分組算法的總價值平均來看基本持平。除此之外，若將整個仿真時間段內的總價值取均值，可以得到對4種算法的總體評價。為了檢驗本文算法模型的泛化能力，將802.11ax網絡的STA數量nSTA依次設置為80, 100, 120, 140, 160，并進行相同的對比實驗，仿真結果如圖7所示。可以看出本文算法模型雖然只按照nSTA=120進行訓練，但是訓練后的模型可以應用到STA數量更多或更少的場景中，并且本文算法在各場景中的表現依然優于另外3種調度算法，足以證明本文算法的有效性和優秀的泛化能力。

圖6 4種算法上行鏈路數據流總價值隨時間變化的仿真結果

圖7 4種算法上行鏈路數據流平均總價值與STA數量的關系

綜上所述，本文的調度算法對優先級的保障是優于輪詢算法、PRA算法和自適應分組算法的，并且相較于PRA算法更加穩定和公平，有效增強了802.11ax上行鏈路的傳輸性能。雖然本文算法的復雜度相較于另外3者略高：由于需要先編碼再解碼所以時間復雜度為O(2nSTA)，另外3種算法則為O(nSTA)；AP需要額外存儲指針網絡的參數所以空間復雜度為O(3nSTA+2l)，輪詢和自適應分組算法則為O(nSTA)， PRA算法為O(2nSTA)。對于結構較簡單、計算能力較差的AP來說不太適合。但是在密集用戶環境下的物聯網場景中，本文算法具有更好的表現，更能滿足AP調度RU資源時對公平性和有效性的需求。

5 結束語

為解決密集用戶環境下802.11ax 上行鏈路的自適應RU調度問題。針對物聯網場景，本文提出了一種基于強化學習的802.11ax上行鏈路調度算法。該算法應用在WLAN的AP上，用于向所有接入該AP的STA調度RU資源。首先，根據物聯網場景的特點建立通信系統模型；然后，在系統模型的基礎上提出802.11ax上行鏈路的自適應RU調度問題，并將該問題轉換為背包問題；之后，使用Actor-Critic強化學習算法訓練用于解決背包問題的指針網絡，并存儲訓練后的網絡參數；最后，在仿真平臺上使用訓練好的網絡參數進行上行鏈路RU資源調度和數據傳輸實驗。通過與輪詢算法、PRA算法和自適應分組算法對比可以發現，本文算法在密集用戶環境下的物聯網場景中表現更優，相比于其他調度算法更能滿足優先級和公平性的需求，分配資源的過程也更加穩定而有效，同時算法所訓練的模型具有很好的泛化能力，對于實際應用場景有一定的實用價值。