M2M小數據業務的IEEE 802.11WLAN分析模型

王雅輝，遲學芬

（吉林大學 通信工程學院，吉林 長春 130012）

1 引言

物聯網就是把世界上所有的機器都連接到一張通信網中，使所有的機器都具備聯網和通信的能力，M2M 是物聯網當前最普遍的應用形式[1,2]。M2M 的通信需要多種網絡的支撐，包括 GSM、CDMA、TD-SCDMA等蜂窩網絡，WLAN、WPAN等專用無線網絡以及 Internet等各種網絡[3]。由于WLAN具有中小范圍覆蓋和高速率接入等顯著優勢，3GPP及3GPP2等組織皆考慮了WLAN與第三代移動通信的融合問題，既能彌補移動業務中速率的不足，又能提高業務移動性和覆蓋面。運營商所建設的以3G為主體、以WLAN為重要補充的無線寬帶數據網將成為M2M通信的最佳承載平臺。

目前，國內外對M2M的學術研究尚處于起步階段，有限的研究結果主要集中于M2M基本應用問題，如市場預測、支撐平臺、業務管理、終端模塊等[4]。對 M2M 業務數學建模和基于特定網絡模型（如WLAN）性能評價的研究報道幾乎是空白。3GPP定義了7類35種M2M業務，本文研究最典型、也是最重要的一類M2M業務——小數據（small data）業務，其基本特點為具有巨大的隨機業務數量、每次通信數據量小，且具有時延容忍、耐性重試特性。本文基于排隊理論，針對IEEE 802.11，建立M2M小數據業務的網絡分析模型，基于業務特性優化WLAN。

在基于排隊理論的 WLAN研究領域，研究成果集中于WLAN服務時間建模和WLAN的系統性能分析。Bianchi提出的二維馬爾可夫鏈模型廣泛應用于關于IEEE 802.11協議DCF (distributed coordination function) 的性能分析中，但是這個分析模型存在一些明顯的缺陷[5]，后來很多文獻對DCF做了深入的研究，改進了Bianchi的模型。ZA推導了一個飽和時延，考慮了信道忙時退避計數器停止[6]；H.Wu提出了限制發送失敗后的重發次數[7]；Z.H.Velkov分析了信道有誤碼的情況[8]；有的文獻還研究了吞吐量極限，指出了隱藏終端的影響等。真實的網絡狀況一般是非飽和的，有些文章將Bianchi的飽和模型直接擴展到非飽和情況，增加了一個或多個“空閑”狀態來代表沒有數據幀要發送的情況，分析網絡的非飽和程度對吞吐量的影響。為了提供準確的時延分析，很多學者研究了 DCF的排隊行為。Liu等將隊列長度作為一個新維度，建立了3-D Markov鏈模型研究DCF性能，模型較復雜[9]。還有一種方法是把 DCF描述為封閉的排隊網絡，將每個退避級數作為其中的一個 G/G/∞隊列[10,11]。更多的研究成果是基于 Bianchi的排隊理論分析系統，如用M/G/1建模WLAN[12]。后來，Vardakas用ON_OFF模型代替Poisson分布描述數據到達過程，表征業務的突發性[13]。基于G/G/1的隊列模型，由于計算復雜，依賴于幾個近似參數，導致分析結果與仿真比較有很大差別[14]。考慮到實際系統容量有限，有的研究用M/G/1/K排隊系統建模WLAN，但是，他們沒有考慮信道差錯，而且，數據幀到達都是經典的Poisson過程[15,16]。

目前的研究都致力于更精確地建模和改善WLAN的DCF機制，而很少考慮針對業務的DCF優化問題；同時，為了簡化排隊系統求解，大多數研究采用了適合語音業務的經典的Poisson分布作為到達過程。當M2M業務大量應用于通信系統時，系統業務源將呈現強烈異構特性，因此，研究面向業務的機制優化具有重要意義。

根據M2M的小數據業務的時延容忍、耐性重試特性，本文提出了一種大時間尺度退避機制，用二項式分布取代均勻分布，用二維馬爾科夫鏈建模了具有大時間尺度退避機制的802.11服務過程，推導了服務時間的概率分布。同時，通過參數控制，實現了退避機制的網絡自適應特性。針對 WLAN的非理想信道和非飽和狀態，提出了IPP/G/1/K的離散時間排隊模型。IPP (interrupted poisson process)的多態特性適于描述M2M小數據業務的突發性，同時IPP融合了到達的概率分布和時間特性。通過求解IPP/G/1/K排隊系統，得到M2M業務的吞吐量、時延等QoS參量。算法仿真實驗結果表明，本文提出的大時間尺度退避機制，優化了802.11的性能，緩解了大量M2M小數據業務引起的沖突，增大了系統的吞吐量。

2 M2M小數據業務模型

機器類通信(MTC, machine type communication)業務的特性與傳統的人與人通信 (H2H, human to human)業務的業務特性差異很大。M2M 業務類型繁多，不可能找到一個通用模型來描述所有 M2M業務。M2M 小數據業務特征可概括為低移動性、時間容忍、分組交換、小數據傳輸、大業務數量[17]。遙感勘測、自動售貨機就是典型的M2M小數據業務。假定每個站點的 M2M小數據業務到達為 IPP過程。在 IPP過程中，ON狀態時數據到達，OFF狀態時，沒有任何數據到達，它適合描述業務的突發性。IPP過程可以看作是二態 MMPP (Markov modulated poisson process)的一個特例，有轉移概率矩陣R和到達概率矩陣Λ分別為

平穩概率分布

其中，r1和r2分別表示ON、OFF狀態之間的轉移速率；λ為ON狀態時數據的到達速率。

3 IEEE 802.11MAC延時模型

IEEE 802.11無線局域網MAC層的DCF方式采用CSMA/CA機制。幀傳輸后，如果SIFS (short inter frame spacing)時間沒有收到確認幀ACK，則認為此幀丟失或碰撞，于是這個幀就會按照二進制指數退避(BEB, binary exponential backoff)算法進行退避、重傳。

將每個幀的發送過程建模為一個Markov鏈。幀離開站點的狀態（例如成功發送或丟棄）是退避機制Markov鏈的吸收態。為了獲得平均轉變到吸收態的時間，應用一般狀態轉移圖推導MAC層服務時間。

3.1 大時間尺度退避過程

在IEEE 802.11 DCF標準中，數據幀發生沖突后要按二進制指數退避算法退避，即競爭窗口乘2，然后從中以均勻分布隨機選取一個值作為退避值。此算法在網絡中活動STA (station)數量較少時的性能較好，因為競爭不激烈，并且競爭信道的退避等待時間較少；而當活動STA數量較大時，這種優勢就會被因競爭信道發生沖突而重傳浪費的信道資源所抵消，甚至被超過。

M2M 業務不同于具有用戶主動權的 H2H業務，M2M 終端大多是可控的終端，而且很多業務對時延不敏感，當網絡擁塞時可以多退避一段時間后再重試接入。本文考慮到M2M的這些特點，針對非實時小數據業務，提出大時間尺度隨機退避的接入控制算法。算法的核心思想是優化 DCF退避機制，按更大的概率選取大的退避值，而不是以相等的概率均勻選擇退避時間。這樣以退避時間為代價來緩解站點的競爭碰撞。本文提出用二項式分布取代均勻分布，推導了二項式分布的系統接入過程，得到服務時間的概率分布。二項式分布的概率參數pb決定概率分布特性，為此，本文估計當前活動STA數量，動態調整pb，從而使算法具有網絡自適應特性。

二項式(binomial)分布是一種離散型分布，概率公式為

正好為二項式展開的各項，所以不難驗證

CSMA/CA退避算法的最小時間間隔為一個時隙σ。令s(t)表示在時隙t站點退避級數(0,1,…,α)的隨機過程，其中α為重傳限制次數，設最大退避級數為m，b(t)表示在時隙t站點的退避計時器取值(0,1,…,Wi-1)的統計過程。

式(5)中，W0是初始競爭窗口，Wi是指退避級數為i時的競爭窗口大小。標準DCF算法中，b(t)是一個取值范圍內的均勻分布，均值為。改用二項式分布，有：

均值為(Wi- 1 )pb，當 pb＞0.5時，二項式分布比均勻分布的退避時間均值要大，這也就是本文稱其稱為“大時間尺度”退避的原因。

由于b(t)、s(t)都取決于一個幀的傳輸歷史以及曾經碰撞的次數，所以都不是Markov過程。但是，如果假設每一次試圖發數據幀卻失敗的概率p恒定且相互獨立，則{s(t), b(t)}是一個二維離散時間Markov鏈，如圖1所示。

圖1 Markov鏈狀態轉移圖

則圖1的一步轉移概率可以表示為

bi,k=Pr{ s( t)=i, b( t)=k},0≤i≤α,0≤k≤Wi為該Markov鏈的穩態分布，根據狀態轉移圖，則有：

根據式(7)和式(9)可以表示為

根據式(8)和式(10)可得：

根據歸一化條件可以推導出0,0b如式(12)所示。

定義τ為站點在任一時隙發送數據幀的概率，則

最后τ變為式(14)。

只有既沒有碰撞也沒有比特差錯時，才能成功的傳輸一個幀，因此，計算p通過：

其中，pc為任一時隙發生碰撞的概率，pe為數據差錯概率，它們的計算公式分別為

其中，p0是沒有數據幀要發送的概率，ε是比特差錯率，f(i)幀長度的概率分布，Nmin、Nmax分別是最小和最大幀長度，單位均為byte。通過聯立式(14)和式(15)，可以求出τ和p，進而可得到pc。如圖2所示，碰撞概率pc和站點數量的關系，大尺度退避機制降低了系統碰撞率。二項分布概率pb越大，碰撞率越低，站點數量越多，效果越明顯。

圖2 數據發生碰撞的概率pc與站點數量的關系

3.2 碰撞和成功發送過程

令Ts表示成功傳輸數據幀所需的時間，Tc表示數據沖突持續的時間，DCF 2種接入方式下有不同的表達式[18]。

1) 基本機制

其中，DATAs、DATAc分別表示成功傳輸和碰撞的數據幀所需的時間，DIFS (distributed inter frame spacing)是DCF協議中使用的一種幀間間隔。等式中的參數均以時隙為單位，設傳輸最小、最大幀長度所占的時隙數分別為σmin、σmax。隨機變量Ts的概率生成函數(PGF, probability generation function)為

對于Tc，它是由最長的碰撞幀決定的。假定3個或更多幀同時碰撞的概率可以忽略，則

其中，FY(i)是f(i)的概率累積分布函數。

2) RTS/CTS機制

采用RTS/CTS (request to send/clear to send)接入方式能提高網絡的吞吐率，降低沖突所浪費的時間，所以一般情況下，IEEE 802.11無線網絡都會采用RTS/CTS方式。碰撞只會發生在RTS中，有：

顯然，Tc是一個定值，它的PGF為

3.3 退避計時器遞減過程

在退避過程中，如果信道空閑，退避計時器每隔一個空閑時隙就減 1。否則，當檢測到一個正在進行的成功傳輸，退避計時器會被凍結一個 Ts時間；如果站點間有碰撞，會凍結Tc時間。

這里定義2個概率qt和qs，其中qt表示其他站點中至少有一個占用信道進行傳輸的概率，即在退避過程中檢測到信道忙的概率；qs表示在考慮的時隙，當前站點沒有發送，其他(n-1)個站點中只有一個數據幀占用信道成功傳輸的概率，即在退避過程中檢測到信道忙，同時又檢測信道無沖突的概率。則有：

可以理解為在一個時隙σ之后，退避計時器以(1-qt)的概率減1，以概率qs保持原狀態Ts時間，以概率(qt-qs)保持原狀態Tc時間，所以退避計時器的遞減過程是一個Markov過程，它的狀態轉移圖3所示。

圖3 退避遞減過程的狀態轉移圖

令 Hd(z)表示退避計時器遞減過程所需時間的PGF，根據Mason公式，有：

3.4 MAC層服務時間

MAC層中數據幀的整個發送過程可以看作是一個z域的線性系統[19]，令Hi(z)表示第i退避級數時退避過程所需時間的PGF，根據其服務系統的傳遞函數系統框圖，可得：

令 μ-1為MAC層的平均服務時間，由式(30)和概率生成函數的性質，有：

概率分布函數(PDF, probability distribution function)與PGF有以下關系：

要計算MAC層服務時間的PDF，即求得gk，直接反z變換的復雜度很大，所以本文采用了Lattice-Poisson估計算法[20]

其中，Re()表示復數的實數部分。式(33)是通過將G(z)在半徑為r(0＜r＜1)的圓上積分得到的。估計值與真實值gk之間的誤差為

當r2k很小時，近似誤差為r2k，令r=10-γ/2k，則精確度為10-γ，本文中設定γ=8。

圖4和圖5是站點數量n=10時MAC層服務時間的概率分布圖，其中圖4的μ-1=7.017 8ms，圖5的μ-1=8.539 3ms。可以看到，RTS/CTS方式的接入時延要大于基本方式，這是因為，前者可以避免較大數據幀發送碰撞時造成的時間浪費，同時也帶來了RTS和CTS控制幀的額外開銷。由于M2M的數據幀長度較小，RTS/CTS方式反而沒有了優勢。

圖4 MAC層服務時間的PDF(基本接入方式)

圖5 MAC層服務時間的PDF(RTS/CTS方式)

4 IPP/G/1/K排隊模型

將每個站點的緩存隊列建模為一個IPP/G/1/K排隊系統，其中，“IPP”指站點的業務到達過程都服從相同參數的IPP模型，服務時間分布“G”為已求得的一般函數MACT，“1”表示單服務器（即同一時間信道只能為一個數據幀服務），緩存隊列長度為“K”。令J(t)(t≥0)表示在時隙t時IPP的狀態，是一個二態不可約馬爾可夫鏈；A(t)表示在[0,t)時間內IPP過程到達的數據幀數。則有：

IPP過程的瞬時到達率為P(t)=eRt，那么可得

令X(t)表示時隙t緩存隊列中的數據幀數，tn表示第n個數據幀離開瞬間的時刻。這樣使就分別是tn之后排隊系統的狀態和IPP的狀態，{Xn, Jn, n≥0}過程是一個二維的離散時間Markov鏈，可以稱其為{X(t),J(t),t≥0}的嵌入馬爾可夫鏈。有限的狀態空間為{0,1,…,K-1}×{1,2}，一步轉移概率矩陣[21]

令πk,j是(Xn, Jn)的極限概率，穩態概率矢量π=(π0, π1,…,πK-1)，πk=(πk,1,πk,2),0≤k≤K-1，通過求解線性系統πP=π，πe=1可以得到π，其中e=(1,1,…,1)T，全1的列向量，維數與π相同。

利用顧客離去時間嵌入馬爾可夫鏈的方法研究IPP/G/1/K隊列，并在這些特定時刻得到一個穩定的解，現在還必須研究任意時刻[22]。

設{X(t),J(t)}任意時刻的極限概率為xk,j，則有：

令x=(x0, x1,…,xK)，xk=(xk,1,xk,2)，系統忙的概率

在嵌入時刻點與任意時刻穩態概率的關系為

有效到達率λ*=θΛe ，可以得到各QoS參量，平均隊長Q、阻塞率L、平均等待時間W、吞吐量S分別為

5 算法仿真結果分析

本文算法仿真以IEEE 802.11b DSSS作為物理層，采用基本接入方式，站點均處于非飽和狀態，站點間的信道為非理想信道。根據IEEE 802.11標準，系統參數設置如表1所示。M2M業務到達是IPP過程，IPP參數通過NS2業務仿真確定，如表2所示，有效到達速率為1.2Mbit/s。在實驗室NS2系統仿真平臺上仿真了WLAN M2M業務系統，收集數據，完成業務參數擬合（實驗室并行研究課題）。但是，仿真平臺上對于M2M業務的模擬具有一定主觀性。隨著M2M的應用，可以根據實測數據進一步修正、優化業務到達模型、參數。

表1 802.11 DSSS PHY層和MAC層參數

表2 IPP模型參數

根據第3節和第4節的推導和本節的參數設置，可得到系統的時延、平均隊長、阻塞率、吞吐量與站點數量的關系，如圖6所示。從圖6可以看出，大時間尺度退避機制引起系統平均隊長和平均時延的增加，但是，圖6(c)和圖6(d)顯示出，大時間尺度退避機制帶來系統阻塞率的降低和吞吐量的上升，而且，隨著站點數量的增加，吞吐量提高的效果越來越顯著。M2M業務對時延的容忍性強，可以多次重試，而且，終端數量大（業界預測，M2M終端的數量將是H2H終端數量的30倍），因此，以時延的適當增加換來系統吞吐量的上升，阻塞率的下降，這樣的改進算法對M2M通信是有效的。

圖6 各QoS參量與站點數的關系

6 結束語

本文針對M2M小數據業務的特點，首次以IPP過程模擬M2M小數據業務的到達分布，而且模型中的各參量可以根據業務特性動態調整。基于二維Markov模型研究了DCF的平均介質訪問延遲的數學建模過程，提出大時間尺度退避算法，推導了MAC層服務時間的概率分布。結果表明，用二項式分布選擇隨機退避時間能夠有效解決原有退避機制的高碰撞率問題，提高 WLAN的網絡性能。本文將IEEE 802.11 WLAN的M2M站點建模為一個IPP/G/1/K離散時間排隊系統，通過對這個排隊模型的求解，得到M2M小數據業務在WLAN中的排隊特性，如平均隊長、排隊時延、吞吐量等。算法仿真結果表明，本文提出的算法，提高了系統的吞吐量，尤其在站點數量大的條件下，算法顯示出更明顯的效果。

[1] International Telecommunication Union. Internet Reports 2005: the Internet of Things [R]. Geneva: ITU, 2005.

[2] TAN L, WANG N. Future Internet: the Internet of things[A]. IEEE ICACTE[C]. 2010.376-380.

[3] MARTINEZ C J J. How to selecting the optimum communications technology in intelligent hybrids nodes? A comparative view of IEEE 802.11b, bluetooth and UWB working together[A]. Future Information Technology (Future Tech)[C]. 2010.1-6.

[4] ANDERS O. M2M Traffic Characteristics[D]. Stockholm: Kungliga Tekniska H?gskolan, 2009.

[5] BIANCHI G. Performance analysis of IEEE 802.11 distributed coordination function [J]. IEEE JSAC, 2000, 18(3): 535-547.

[6] ZIOUVA E, ANTONAKOPOULOS T. CSMA/CA performance under high traffic conditions: throughput and delay analysis[J]. Computer Communications, 2002, 25(3): 313-321.

[7] WU H, PENG Y, LONG K. Performance of reliable transport protocol over IEEE 802.11 wireless LAN: analysis and enhancement[A]. Proc IEEE INFOCOM[C]. 2002. 599-607.

[8] HADZI V Z, SPASENOVSKI B. Saturation throughput–delay analysis of IEEE 802.11 DCF in fading channel[A]. Proc IEEE ICC[C].2003. 121-126.

[9] LIU R P, SUTTON G J, COLLINGS I B. A new queueing model for QoS analysis of IEEE 802.11 DCF with finite buffer and load[J]. IEEE Transactions on Wireless Communications, 2010, 9(8): 2664-2675.

[10] CHOI J, YOO J, KIM C K. A novel performance analysis model for an IEEE 802.11 wireless LAN [J]. IEEE Communication Letters, 2006,10(5): 335-337.

[11] 薛俊晗, 張曉敏, 陳高明. 基于排隊模型的無線局域網性能分析[J].計算機工程, 2010, 36(10): 133-139.XUE J H, ZHANG X M, CHEN G M. Performance analysis of wireless LAN based on queuing model[J]. Computer Engineering, 2010,36(10): 133-139.

[12] LEE W, WANG C G, SOHRABY K. On use of traditional M/G/1 model for IEEE 802.11 DCF in unsaturated traffic conditions[A].IEEE WCNC[C]. 2006.1933-1937.

[13] VARDAKAS J S, SIDIROPOULOS M K, LOGOTHETIS M D.Performance behaviour of IEEE 802.11 distributed coordination function[J]. IET Circuits Devices Syst, 2008, 2(1): 50-59.

[14] TICKOO O, SIKDAR B. Queueing analysis and delay mitigation in IEEE 802.11[A]. Proc IEEE INFOCOM[C]. HongKong, China, 2004.1404-1413.

[15] OZDEMIR M, MCDONALD A B. A queuing theoretic model for IEEE 802.11 DCF using RTS/CTS[A]. Proc IEEE Workshop LANMAN[C]. 2004. 33-38.

[16] ZHAI H, KWON Y, FANG Y. Performance analysis of IEEE 802.11 MAC protocols in wireless LANs[J]. Wiley J Wirel Commun Mob Comput, 2004, 4(8): 917-931.

[17] 3GPP TS 22.368 V1.0.0 (2009-08), Service Requirements for Machine-Type Communications[R].

[18] PARK C G, HAN D H, AHN S J. Performance analysis of MAC layer protocols in the IEEE 802.11 wireless LAN[J]. Telecommunication Systems, 2006, 33(1-3): 233-253.

[19] ZHENG Y, LU K, WU D. Performance analysis of IEEE 802.11 DCF in imperfect channels[J]. IEEE Trans Veh Technol, 2006, 55(5): 1648-1656.

[20] ABBATE J, WHITT W. Numerical inversion of probability generating functions[J]. Oper Res Lett, 1992, 12(4): 245-251.

[21] GROSS D, HARRIS C M. Fundamentals of Queueing Theory (Third Edition)[M]. New York: John Wiley & Sons, Inc, 1998.

[22] BAIOCCHI A, BLEFARI M N. Steady-state analysis of the MMPP/G/l/K queue [J]. IEEE Transactions on Communications, 1993,41(4): 531-534.