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

徐方圓 張治中 李 晨

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

0 引 言

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

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

1 隨機接入碰撞分析

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

圖1 H2H與M2M共存場景

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

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

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

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

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

圖2 Slotted ALOHA協(xié)議吞吐量

圖3 純ALOHA協(xié)議的吞吐量

1.2 基于Q-learning的Slotted ALOHA方案

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

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

(1)

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

圖4 重復(fù)沖突丟失專用時隙例子

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

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

(2)

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

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

Gtotal=GH2H+GM2M

(4)

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

表1 仿真參數(shù)

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

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

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

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

2.1 Q-learning場景建模

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

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

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

步驟3初始化Q值矩陣，M2M用戶組開始學(xué)習(xí)。

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

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

步驟6將Q2-Q1的值更新到Q矩陣中，將下一狀態(tài)更新為當(dāng)前狀態(tài)。

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

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

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

圖7 H2H和M2M場景下不同優(yōu)先級用戶的學(xué)習(xí)方案

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

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

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

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

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

3 結(jié) 語

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