基于Q-learning的隨機接入碰撞問題的研究

徐方圓 張治中 李 晨

(重慶郵電大學通信與信息工程學院 重慶 400065)

0 引 言

隨著物聯網的飛速發展，未來將會出現更多的機器與機器(M2M)場景。M2M通信的多樣性取決于合適的無線接入網絡。到2020年，M2M設備的數量會超過500億，這意味著大大地增加了人控制機器的復雜性。蜂窩網絡的覆蓋性、漫游指標等特點使得無線空口通信更適合M2M，有利于M2M之間的通信[1]。LTE網絡已經將M2M作為新服務應用的關鍵性技術[2]。然而，蜂窩網絡的最初設計是為人與人(H2H)通信而設計的，故M2M與H2H共存的情況是必然的。M2M主要進行UL鏈路的傳輸，而H2H相比M2M而言，DL鏈路傳輸更為普遍。另外，由于H2H主要支持語音呼叫、視頻流、上網和社交媒體，因此H2H需要基本的網絡服務要求。相反，M2M更多的是面向設備與設備之間的業務，具有較小的數據業務載荷。另外，M2M設備在蜂窩中的數量可能是海量的，蜂窩網絡的小區內可能有成千上萬個M2M設備[3]，會導致設備在接入基站的過程中發生隨機接入擁塞。這是因為設備在訪問基站的速率大大增加導致設備接入的沖突的概率加大。因此，隨機接入信道的擁塞問題成為M2M中必要解決問題。

本文主要在M2M與H2H共存場景下提出了一種基于Q-learning隨機接入退避算法來降低在隨機接入信道中的擁塞率，從而增加了隨機接入信道的吞吐量。3GPP提出的其他解決方案包括時隙接入方案、基于Pull的方案、M2M特定的退避方案和RACH資源的動態分配[4]。3GPP提出的解決方案的方法需要eNB的直接參與，因此需要修改現有網絡標準和5G的信令。但是修改標準和信令改變了現有H2H用戶的操作模式。本文主要目的是為了提高隨機接入的吞吐量，同時又不會影響標準的統一性。本文中，Q-Learning算法主要對M2M設備中隨機接入流量進行智能控制。本文基于這兩種方案上M2M與H2H場景進行建模，將5G無線幀劃分為H2H幀和M2M幀，利用Q-learning智能算法對M2M場景中的設備進行狀態分析、動作轉移，獎勵更新。

1 隨機接入碰撞分析

在M2M場景中，主要是機器連接4G基站然后進行上行數據的傳輸。而在H2H中，主要是用戶連接5G基站進行下行傳輸。圖1描述了H2H與M2M共存的場景，主要從兩個方面來分析：(1) 5G網絡滿足多用戶接入和低時延傳輸，多用戶的傳輸速率過高會導致用戶接入時發生碰撞，故在此場景下需要解決H2H的接入通信問題；(2) M2M大量的設備容易造成隨機接入信道發生過載，故在此場景下需要解決容量過載問題。最后，5G與4G基站同時關聯核心網中MME/S-GW。在關聯的過程中，容易導致H2H與M2M的幀發生沖突。時延敏感的機器類通信設備MTCD直接和基站進行通信，對時延不敏感的M2M終端按照業務屬性或位置劃分成不同的群組，通過機器類通信網關MTC和基站進行通信[7]。

圖1 H2H與M2M共存場景

1.1 時隙Aloha RACH接入(SA-RACH)方案

SA-RACH是H2H用來訪問蜂窩網絡中的RACH的現有方案，該方案對于所有蜂窩網絡標準都是通用的，因為它們都將RACH用于控制信道。但是，隨機接入信道的結構和排列方式有所不同。例如，GSM協議將時間劃分為多個相等大小的時隙，稱為RACH時隙，這些時隙映射到網絡中的重復幀結構上[5]。

ALOHA協議和它的后繼CSMA/CD都是隨機訪問或者競爭發送協議。ALOHA是按照用戶的需求進行隨機接入和發送數據。然而，當多個用戶同時需求發送數據時，容易產生碰撞。當發生碰撞時，傳輸幀容易受到破壞。因此，在ALOHA協議中，發送方可以在發送數據的過程中進行沖突檢測，將接收到的數據與緩沖區的數據進行比較，就可以知道數據幀是否遭到破壞。如果發送方知道數據幀遭到破壞(即檢測到沖突)，那么它可以等待一段隨機長的時間后重發該幀。時隙ALOHA協議的思想是用時鐘來統一用戶的數據發送。辦法是將時間分為離散的時間片，用戶每次必須等到下一個時間片到來才能開始發送數據，從而避免了用戶發送數據的隨意性，減少了數據產生沖突的概率，提高了信道的利用率。

純時隙ALOHA的實現方案：當用戶進行上行傳輸時，會開啟一段時間窗，等待基站的回應?；臼盏缴闲袀鬏敂祿r，會發送ACK信號。當多個用戶同時收到ACK信號時，會發送碰撞，多個用戶會等待一段時間后再繼續傳輸。Slotted ALOHA是在純ALOHA幀的基礎上進行分段處理，它把頻道在時間上分段，每個傳輸點只能在一個分段的時隙開始處進行傳送。每次傳送的數據必須少于或者等于一個頻道的一個時間分段。這樣極大地減少了傳輸頻道的沖突。

由圖2和圖3可知，兩種時隙下的隨機接入吞吐量呈現先增大后減小的趨勢。在隨機接入吞吐量一定的情況下，Slotted ALOHA時隙適用于流量更大的場景。由于所有標準都使用Slotted Aloha的盲目性質來訪問RACH，所以當多個用戶在同一時隙中發送請求時會發生沖突。故此方案應用在設備量巨大的情況下行不通。由于分槽ALOHA適用于流量大的場景，故在本文中以分槽ALOHA為基準，對H2H與M2M場景共存下的隨機接入過程碰撞進行研究。當前學術界主要是用分槽ALOHA對隨機接入碰撞為題進行研究。進一步分析基于Q-learning的分槽時隙方案。

圖2 Slotted ALOHA協議吞吐量

圖3 純ALOHA協議的吞吐量

1.2 基于Q-learning的Slotted ALOHA方案

在這種方法中，Q-learning用于控制RACH訪問中的M2M流量。Q-learning是強化學習的簡化版本，其中算法在學習時提供最佳的系統收斂性。將此方案與SA-RACH結合使用可減少沖突的總數，因為在學習收斂后(每個M2M用戶都有唯一的專用RACH時隙時)，M2M用戶之間不會發生沖突。文獻[8]已經使用類似的方法來提高Slotted Aloha在無線傳感器網絡中的吞吐性能。因此，本文方法是在H2H與M2M場景下結合RACH接入方案。為了實現強化學習，M2M流量利用RACH或虛擬時隙(RA)的虛擬幀，稱為主蜂窩幀中的M2M幀，如圖4所示。為了獲得最佳的學習結果，使M2M幀的大小(時隙數)等于M2M用戶數。通過M2M基于幀這種形式來進行RACH訪問，每個用戶僅訪問M2M幀中的一個時隙。通過式(1)更新Q值。

Q′=(1-A)×Q+A×r

(1)

式中：Q為當前的Q值；A為學習因子；r為獎勵/懲罰因子取決于隨機接入請求的狀態，當隨機接入成功時，r的取值為1，當隨機接入失敗時，r的取值為0。此過程導致每個M2M的時隙具有不同的Q值，用戶始終選擇具有最大Q值的時隙，如果多個時隙具有相同的Q值，則用戶將隨機選擇一個。在穩定狀態下(每個用戶找到專用時隙時)，由于隨機訪問和重傳策略會增加沖突，因此H2H用戶仍然會受到干擾。這將導致比專用M2M時隙中獲得更多的懲罰，在某些情況可能會使用戶丟失該時隙。

圖4 重復沖突丟失專用時隙例子

圖4顯示了M2M用戶(M1)如何由于重復沖突而丟失專用時隙的示例。M1在M2M時隙1中，此時M1的Q值為Q+3，H1為H2H時隙并在M1時隙處開始傳輸，那么M1時隙與H1時隙發生沖突。然后M1的值就會變成Q+2。由于H2H的窗口值為3，當處于M2時隙時，H1正好又與M2時隙發生碰撞，此時M2的值就會變成Q+1。當到達M3時隙時，H1正好又與M3發生碰撞。此時M3時隙的值變成Q+1。最后再經過一次碰撞到達M4時隙，此時M4的Q值就會變成Q。在這個過程中，M2M時隙會不斷地接受懲罰使得Q值減小。當減小到低于一個閾值時，該時隙丟失。這就造成了M2M時隙重復沖突丟失。為了解決這個問題，文獻[5]中提出了一種改進的Q-learning的算法。為減少影響，更改上面介紹的懲罰規則。這里，懲罰已經變得可變，這取決于參與其中的用戶觀察到的重傳次數碰撞。因此，當發生碰撞時，Q值使用以下方法更新(懲罰)受影響的時隙：

Q′=(1-α)Q-αK

(2)

式中：(KH2H)i是參與沖突的第i個H2H用戶觀察到的重傳次數；KM2M是受影響的M2M用戶觀察到的重傳次數。此方程的目的是為了減小懲罰值，從另外一個角度來說是為了降低H2H用戶接入流量對M2M時隙的影響。

在現有的蜂窩網絡上支持M2M意味著H2H用戶將與M2M用戶共享/競爭蜂窩網絡資源。因此，應該通過解決資源競爭來設計一種更好的共存方式。用戶之間的交互級別由生成的單個負載控制，以構成系統的總流量負載?？偭髁康谋磉_式如下：

Gtotal=GH2H+GM2M

(4)

式中：G為流量的總負載；GH2H為H2H場景下的用戶流量負載；GM2M為M2M場景下機器流量的總負載。仿真參數如表1所示。

表1 仿真參數

如圖5所示，比較了常規的蜂窩的SA-RACH方案的吞吐量與經過Q-learning學習后QL-RACH方案吞吐量，得出結論：(1) 兩種接入方式中，經過Q-learning學習的QL-RACH吞吐量隨流量的增大呈線性增加，而常規的蜂窩SA-RACH的吞吐量隨隨機接入信道流量的增大而先增加后減小。(2) Q-learning學習的QL-RACH的吞吐量會收斂于最佳的吞吐量值，由于SA-RACH信道的容量較低，信道性能變得不穩定，RACH吞吐量在臨界點后立即下降。這是由于聚合的流量超過了Slotted Aloha支持的信道容量，導致隨機接入信道不穩定。

圖5 QL-RACH與SA-RACH方案的吞吐量比較

2 改進的基于Q-learning的Slotted ALOHA方案

在使用Q-learning來學習單用戶組的隨機接入信道存在著很多缺陷。當單一接入M2M組或者接入H2H組時，Q-learning學習時的吞吐量明顯比SA-RACH好。但是，多個用戶組同時接入SA-RACH時，當達到臨界點時會出現吞吐量急速下降，而使用Q-learning學習后的多用戶組同時接入QL-RACH能夠降低吞吐量急劇下降對系統的影響。因此，本文提出了多用戶組隨機接入方案。

2.1 Q-learning場景建模

對于多用戶的接入方案，使用改進的方案是基于Q-Learning的分槽ALOHA方案。它的優點是對于高流量場景下的接入問題根據用戶接入閾值K能夠迅速判別UE的接入狀態，大大增加了系統接入效率，同時能夠滿足海量吞吐量指標。具體步驟如下：

步驟1初始化多個用戶組場景。

步驟2定義M2M組用戶狀態矩陣S(X,Y)定義，M2M組用戶動作A(X,Y)。

步驟3初始化Q值矩陣，M2M用戶組開始學習。

步驟4產生隨機值Rand(0，1)，當此值大于用戶設定的閾值K，且為接入態時，在用戶動作矩陣A選擇一個合適的值在幀上進行傳輸，否則被判定為非接入態。此時更新Q值矩陣，并把更新的最大的Q值賦給動作矩陣A。

步驟5生成兩個Q值分別為Q1和Q2，其中Q1代表當前的M2M用戶組下學習的Q值，Q2代表更新后的Q值。計算Q2=reward+r×max(Q[next_state]);

步驟6將Q2-Q1的值更新到Q矩陣中，將下一狀態更新為當前狀態。

多用戶組Q-learning接入方案流程如圖6所示。

圖6 多用戶組Q-learning接入方案

多用戶組是將H2H用戶組和M2M用戶組進行分類。在H2H場景中，將用戶組優先級分為高、中、低三個等級。分別記為H2H_1、H2H_2、H2H_3。H2H_1代表搶占用戶，H2H_2代表緊急用戶，H2H_3代表普通用戶。在M2M場景中，將設備分為M2M_1、M2M_2兩種類型。M2M_1代表著M2M中訪問流量高的設備組，M2M_2表示著訪問流量低的設備組。如圖7所示，a1、a2、a3分別代表H2H_1、H2H_2、H2H_3的優先級權重。b1、b2分別代表M2M_1和M2M_2優先級權重。權重越大，代表優先級越高，在流量相同的情況下分配的信道資源越多，吞吐量越大。在H2H與M2M共存的情況下，分別在H2H與M2M中選擇一組進行Q-learning學習。

圖7 H2H和M2M場景下不同優先級用戶的學習方案

2.2 多用戶組SA-RACH與QL-RACH方案

通過分別使用兩種方案得出不同優先級的用戶組學習的情況。當采用傳統的SA-RACH處理時，仿真參數由表1可知。由圖8可知，H2H使用傳統的蜂窩接入方案時吞吐量會隨著流量的增加而降低。M2M使用傳統的蜂窩接入方案時，吞吐量會隨著流量的增加先增加后減小。在H2H和M2M中，隨著隨機接入流量的增加，優先級高的用戶組隨機接入吞吐量要比優先級低的用戶組隨機接入吞吐量要低。使用傳統的方案進行接入都存在這一個共同的問題，在高流量的場景下，由于隨機接入信道容量有限，故吞吐量都會趨近于0。

圖8 多用戶組采用SA-RACH方案處理仿真圖

由圖9可知，同一用戶組使用Q-learning學習的多用戶組方案的吞吐量會隨著流量的增大收斂于一個最優值。不同用戶組在同一場景下吞吐量取決于優先級大小，優先級越大，在流量一定的情況下，吞吐量越大。這樣解決了在M2M和H2H共存場景中隨機接入信道容量不足而引起的吞吐量下降的問題。

圖9 多用戶組采用SA-RACH與QL-RACH方案吞吐量對比

3 結 語

本文分析了H2H與M2M共存場景。分別分析了純時隙ALOHA與Slotted ALOHA的吞吐量，結果顯示：當流量很大時，這兩種接入方式吞吐量趨近于0。為了解決這個問題，本文又分析了一種基于Q-learning的隨機接入方案，這種方案是學習用戶數量接入問題。然而，在H2H用戶較多的時候，容易在時隙上面發生碰撞，導致最終的Q值不斷減小。在此基礎上提出了一種降低H2H用戶接入流量對M2M時隙的影響的方案。最后，提出了Q-learning具體算法，并在不同優先級用戶組進行分析。最后通過仿真對比，發現使用Q-learning學習的多用戶組方案吞吐量最終會收斂于一個最優值，而使用傳統的SA-RACH方案的吞吐量最終會趨近于0。故解決了在信道容量有限的情況下吞吐量不足的問題。后期將會在D2D與M2M共存場景中分析隨機接入碰撞問題。