一種基于雙隊列模型的分布式MTD接入方法*

曹 遜，王 聰，趙幾航，吳 霞，姚遠翔

（陸軍工程大學，江蘇 南京 210001）

0 引 言

機器到機器（Machine to Machine，M2M）通信是物聯網（Internet of Things，IoT）中的重要組成部分，目標是在最少的人工干預下實現不同機器設備之間的自主通信[1]。據估計，到2025年，物聯網設備的數量將接近200億臺[2]。長期演進網絡（如LTE、5G）因其廣泛覆蓋、基礎設施完善等優點，為大規模機器類型通信（massive Machine Type Communication，mMTC）提供了現實基礎。然而，作為一種針對人與人（Human to Human，H2H）通信的技術，LTE網絡部署M2M通信面臨諸多挑戰[3]，其中之一就是M2M通信中的MTDS密度通常非常高[4]，會引起激烈的競爭，并顯著降低隨機接入（Random Access，RA）過程的接入效率。因此，正確設計用于M2M通信的RA協議尤為重要[5]。為了緩解激烈的競爭，已有許多方案被提出，包括自適應調整退避參數。它又分為調整接入類禁止因子q[6-8]和統一退避窗口（Unified Backoff window，UB）大小[9]，需適當調整RA過程中分配的前導碼（Random Access Preamble，RAP）數量和時隙長度[10-12]，或者將所有機器類型設備（Machine Type Device，MTD）進行分組等[13]。上述方法中，自適應調整接入等級限制（Access Class Barring，ACB）因子和退避窗口大小的方案更受關注。該方法的關鍵在于準確設置最佳參數，并隨網絡變化及時進行調整。一般來說，可以將其分為集中式方案[14-16]和分布式方案[17-20]。

在集中式方案中，基站（Base Station，BS）確定退避參數，然后將它們廣播到網絡中的所有MTD。以前的大多數工作[6,8,14,16-21]提出，BS根據實時網絡狀態來確定積壓的MTD的數量（即網絡中待接入的MTD）。例如，通過每個時隙[14]中的空閑RAP數量和每個時隙[16]中成功的RAP或沖突的RAP的數量來估計積壓MTD數量，并估算最優參數，然后BS向網絡中的每個MTD廣播建議的退避參數。在接收到來自BS的消息后，MTDS隨后相應地執行RA過程。在這些方法中，BS需要跟蹤積壓的MTDS的實時數量。這通常是時變的，很難捕獲。網絡狀態信息的不準確可能導致網絡性能從最優降級。此外，每個時隙的廣播消息會給網絡帶來巨大的開銷。

文獻[22]對每個MTD建立了馬爾科夫模型，分析其狀態轉移的穩態概率。研究發現，BS可以根據網絡狀態的統計信息（如每個MTD的平均分組到達速率、系統中的MTD數量）計算最優退避參數，而不是跟蹤網絡實時狀態（如每時隙待接入的MTD請求數量）。通過BS確定的最優ACB參數，可以實現最佳的網絡性能，如最大化吞吐量或最大化接入成功率。本文吞吐量定義為平均每時隙接入成功的請求數量。然而，作為一種集中式方法，BS需要每個MTD上傳自己的分組到達速率。此外，當網絡狀態發生變化時，BS需要實時向范圍內的設備廣播最新的ACB參數。考慮到M2M通信中傳輸的數據包一般較短，這種集中式的方案會帶來很大的信令開銷。根據文獻[18]，這個問題在MTD數量較大時會變得嚴重。

鑒于此，分布式算法更加適合mMTC場景下的通信。文獻[17-18]分別提出了基于機器學習和博弈論或者優化分解的分布式方案。Hussain等人[19]提出一種基于強化學習的分布式時隙分配方案。文獻[20]提出一種在海量M2M通信中保證不同業務類型的服務質量保證的迭代算法。文獻[23]提出了一個新框架來保證H2H通信資源的高優先級，同時滿足M2M通信的多樣化需求。上述工作雖然都是分布式方案，但要么選擇了無沖突的時隙，要么是為了滿足不同M2M設備的業務需求，都無法實現網絡的最大化吞吐量。此外，因缺乏顯式表達式，大多數算法都需要迭代，造成分布式調整的效率較低。

本文根據文獻[22]對MTD設備在網絡中狀態的分析，建立馬爾科夫狀態轉移圖，分析得到各個狀態的穩態概率，推導吞吐量的顯式表達式，提出了一種新的分布式算法。通過這種算法，每個MTD可以根據自身的統計信息估計網絡中的設備數量，進而確定最優ACB參數，可實現最大化網絡吞吐量。具體來說，在同質網絡中，每個MTD具有相同的數據包到達速率，每個設備根據相同的初始ACB參數計算自己一段時間內的接入成功率（本文接入成功率定義為一段時間接入成功的請求數量與總的發起的請求數量的比值），再根據一個顯式表達式估算系統中的設備總數，進而確定最佳ACB參數，從而實現最大化網絡吞吐量。

根據上述描述，初始ACB參數和估計區間大小的設置對該算法性能有重要影響。這兩個參數的選擇應當保證在估計值的準確性和估計所需時間之間取得平衡。在較長的估計區間下，MTD可以更準確估計網絡參數，實現更大的網絡吞吐量。但時，如果MTD數量變化較快，估計的數量就會不準確，無法實現最大化吞吐量。與D-ACB方案[16]和EPBACB方案[17]比較發現，中心式算法雖然也可以更新每時隙的最優退避參數，但它們信令開銷較大，無法實現最大化吞吐量。相比之下，所提出的分布式方案可以在更低的信令開銷下實現更大的吞吐量。

本文安排如下：第1節介紹系統模型和分析；第2節根據傳輸成功率的隱式表達式，提出最優退避參數的估計算法；第3節進行性能仿真分析；最后總結全文。

1 系統模型和初步分析

為了簡化分析，考慮存在n個MTD試圖接入單BS的場景。根據現行標準，MTD設備的RA過程分為4步，如圖1所示。

第1步：MTD先從RAP池中隨機選擇一個RAP將其發送至BS。因RAP之間的正交性，選擇不同RAP的設備之間互不干擾。

第2步：BS對每個收到的RAP生成隨機接入響應（Random Access Response，RAR）消息，為每個RAP分配時頻資源塊（Resource Block，RBs）并廣播到每個MTD。

第3步：每個MTD根據BS廣播的RAR消息，在指定的RB上向BS發起其接入請求。注意，mMTC場景下，大量選擇了相同RAP的MTD在同一RB上發起接入，此時BS不能區分這些MTD發生沖突。

第4步：BS給每個成功解碼的接入請求設備發送競爭解決消息，其他競爭失敗的設備將退避一段時間。

為了緩解RA過程中的沖突問題，已經提出了很多方案，其中ACB方案和退避算法應用最廣。簡單來說，ACB機制是通過BS向所有MTD廣播一個ACB因子q，q∈(0,1]。所有MTD在選擇RAP發送前都要先生成一個0～1的隨機數與q比較，只有小于q時，設備才可以執行RA過程。退避算法則是給每個接入失敗的MTD加上一個退避時間，即失敗后的MTD不能立即再次發起接入，要在[0,W-1]范圍內隨機選擇一個值Ws，在再次執行RA之前等待Ws時隙。

文獻[21]針對M2M通信的RA過程，為每個設備建立雙重隊列模型。如圖2所示，每個MTD包含一個數據隊列和一個請求隊列。數據隊列存儲每個MTD到達的數據包，當數據隊列非空時，MTD將產生接入請求，即請求隊列非空。需要注意，請求隊列最多只能有一個請求。當請求成功傳輸至BS時，將同時清空數據隊列和請求隊列。

基于圖2的雙隊列模型，分析每個MTD在每個時隙可能處于下列3種狀態——通過ACB校驗并傳輸成功狀態T、未通過ACB校驗為狀態0、通過ACB校驗但傳輸失敗進入退避狀態Ws。根據上述分析，可得馬爾科夫狀態轉移圖，見圖3。

分析圖3，當MTD通過ACB校驗且請求傳輸成功時，則設備保持在狀態T。設MTD請求傳輸成功概率為p，則保持在狀態T的概率為qp，q為ACB因子。當設備通過ACB校驗但請求傳輸失敗，則設備均勻散布到W個退避窗口上，概率為q(l-p)/W。此外，當設備沒有通過ACB校驗時，則從T轉移到狀態0，概率為l-q+q(l-p)/W。當設備處于狀態0時，意味著設備ACB校驗失敗，將于下一時隙再次接入，并以概率qp轉移到狀態T。若傳輸失敗，則同樣等概率轉移到退避狀態，概率為q(l-p)/W。其他情況則保持在狀態0不變。處于退避狀態的設備以概率l每時隙向上一狀態轉移。

根據上述分析，可以得到各個狀態的穩態概率：

式中：p為請求成功傳輸的穩態概率。在同質網絡中，所有MTD的成功傳輸概率相同。從式（1）可以看出，只有一個設備處于狀態T，其他設備只能處于狀態0或退避狀態時，設備才可以接入成功。

先分析RA過程的吞吐量和平均接入時延性能?？紤]系統中共包含N個MTD和R個RAP可用，前導碼的選擇是隨機的，所以每個前導碼可以視為被n=N/R個MTD選擇。又因為RAP之間的正交性，選擇不同前導碼的設備之間互不干擾，只需要考慮選擇同一前導碼的設備之間的競爭關系。下面都將前導數量R設為1，系統內設備數量設為n。結合分析，在單個RAP情況下，一個MTD要接入成功，其他MTD要么數據隊列為空，要么數據隊列非空但處于退避狀態或未通過ACB檢驗處于狀態T或0。

根據文獻[21]，可以得到單RAP系統中每個設備接入請求的成功傳輸穩態概率p的隱式表達式和吞吐量的表達式：

在單個RAP前提下，如果有某個設備接入請求成功傳輸，則其他所有競爭設備一定沒有通過ACB校驗，因此可以推導出單個MTD接入成功率的關于ACB因子q和設備數量n之間的顯式表達式：

對式（4）關于q和n求偏導，可以得到q=1/n或q=1-e-1/n。根據泰勒公式可知，在n數量較大時，二者相等，此時p取最大值e-1，即每個前導碼可以實現的最大吞吐量為e-1。據此可知，單個RAP條件下MTD接入請求成功傳輸的概率最大值為e-1。將此結果代入式（2），可得：

可以得到最大化成功率時的最佳ACB參數q*和W*應滿足：

式中：n為系統中總的設備數量；λ為每個設備數據包到達速率。本文假設為同質網絡，所有設備λ相等。另外，因為λ為統計參數，每個MTD可以輕易獲取。

根據上述分析，只要知道系統中所有待接入的MTD數量n和每個MTD數據包的到達速率λ，就可以確定最佳的ACB因子q*和W*。簡單的思想是通過BS統計MTD的數量，再根據MTD的反饋獲知λ，確定最佳ACB因子后再廣播到所有設備。

2 分布式吞吐量優化算法

根據最優退避參數的閉合公式，本文討論了一種基于BS的集中式方法。但是，M2M通信的數據包普遍較短，而集中式算法的信令開銷較大，在mMTC場景下得不償失。因此，將針對每個單獨的MTD提出一種分布式方法，每個MTD獨立確定自己的最佳ACB參數，以優化網絡吞吐量。

在同質網絡環境中，假設所有MTD具有相同的數據包到達速率，先考慮只有單個RAP的情況，即系統中可用RAP數量為1，競爭設備數量為n。根據式（6），每個MTD既可以調整ACB因子q，也可以調整退避窗口W的大小。本文假設給定退避窗口大小W，則最佳ACB因子q*可以確定為

每個MTD的數據包到達速率λ可知，退避窗口W大小給定時，為了確定最佳ACB因子q*，需要知道MTD的總數n。

根據式（5），可以得到n的表達式為

從式（2）可知，只要給定系統初始的q和W，n數量和數據包到達速率λ保持不變，就可以得到穩定的請求傳輸成功率p。只要根據給定的q和W，每個MTD統計自己一段時間Te內總的發起接入請求數nt與傳輸成功接入請求數ns之間的比值，就可得到接入請求成功傳輸的穩態概率的估計值：

將式（9）代入式（8），可得：

將式（10）代入式（7），可得：

據此，可以得到最佳ACB因子的估計值。為了簡化計算，本文將退避窗口W的大小設置為1，則每個MTD的最佳ACB因子估計值為：

根據上述分析，得到分布式MTD最佳ACB因子確定算法。

輸入：數據包到達速率λ；在估計時間T內成功傳輸的請求數量ns(T)和總傳輸數量nt(T)；初始ACB因子q；

1：在初始ACB因子q條件下，運行T個時隙；

2：統計T時隙內總共發起的接入請求的數量nt(T)和成功傳輸的接入請求數量ns(T)；

3 仿真結果與分析

仿真采用事件驅動型仿真。在單個RAP條件下，當n個MTD試圖接入BS且只有一個設備通過ACB校驗選擇前導碼時，接入請求才可以傳輸成功。系統中每個MTD的數據分組到達服從參數為λ的伯努利過程。MTD先以初始q運行一段時間，統計接入請求傳輸成功率，并估算系統中設備數量，再以估算最佳ACB參數。運行一段時間后，再次估算最佳ACB參數，以適應網絡狀態變化。

從分布式最優ACB因子估計算法可以看出，估計時間T和初始ACB因子q是兩個關鍵參數。圖4給出了當估計時間T和數據包到達速率λ一定時，估計設備數量與實際真實數量之間的比較曲線，以及估計估計最優ACB因子與理論最優ACB因子之間的比較。需要說明的是，估計時間T=105個時隙，實際設備數量n=100，分析最佳ACB因子q*=0.01，λ=0.08。

從圖4可以看出，在初始ACB因子較小時（遠小于最優ACB因子q*=0.01），即使估計時間較長（T=105個時隙），算法依然無法準確估計系統中的MTD數量，導致估算的最優ACB參數與分析獲得的最優ACB參數差距較大，系統無法實現最大化網絡吞吐量；當初始ACB因子接近q*時，可以十分準確地估計出系統中的MTD數量，計算出最接近q*的估計；當初始q較大時（q＞0.1以上），估計的MTD數量開始出現抖動，偏離最優值，但整體表現依然優于q較小時。根據式（4），當q較小時，在n=100固定的情況下，p的最大值也無法達到最優值e-1。每個時隙只有極少部分、甚至沒有設備可以通過ACB校驗，若想要獲取準確的接入成功率，需要非常長的一段時間。而當q較大時，每時隙可以通過的設備數量較多，可以在較短時間內獲取較為準確的成功率，進而準確估算系統中MTD的數量。但是，如果初始q過大，則可能導致長時間沒有設備接入成功，系統始終處于擁塞狀態。隨著數據隊列積壓的數據增加，初始成功率降低，導致無法準確估算MTD數量。從圖5可以看出：q較小時，無論n如何變化，p始終保持較低；q較大時（處于最優ACB參數附近），隨著n增加，成功率p可以處于較大位置，與前面分析的情況一致。

圖6進一步給出了在初始ACB因子q固定時，隨著估計時間T變化的算法表現。在q=0.001時，隨著T增加，估計設備數量越來越接近真實值。但是，可以明顯看出，從估計時間較少提升到3×104時隙時，性能提升較大，可以較為準確地估計出MTD數量，并給出接近最佳ACB因子的。但是，隨著估計時間的繼續增加，性能沒有明顯提升，因為系統中的ACB因子已經調整到最優ACB因子附近，無法進一步增加網絡吞吐量。

圖7將本文方法與兩種經典集中式方法進行比較，可以發現所提方法可以始終保持較高的吞吐量表現。這是因為在系統內MTD數量較為穩定時，本文方法通過長時間觀察可以準確估計出系統中的MTD數量。此外，集中式算法需要MTD與BS之間的額外通信，會增加信令開銷。相比之下，本文的分布式算法由每個MTD自行決定ACB參數，無需BS頻繁廣播更新，可以節約一部分的信令開銷。

4 結 語

本文針對同質mMTC場景，以最大化網絡吞吐量為目標，提出了一種分布式最優ACB因子確定算法。通過分析與仿真發現，該算法的初始ACB因子q和估計時間T對其性能有較大影響。通過仿真表明，在系統內MTD數量較為穩定，且估計時間和初始q選擇較為恰當時，算法可以較為準確地估計出系統中的MTD數量，計算出接近最優ACB因子的近似值，實現最大化網絡吞吐量。與傳統集中式算法相比，該算法有較低的信令開銷，且吞吐量更好。但是，該方法也存在潛在的問題。因為ACB參數由每個MTD自行決定，某些MTD可能會故意設置較高的ACB因子以獲取更高的接入優先級，會導致網絡資源分配的公平性變差。如何解決這一問題有待進一步研究。