具有時變馬爾可夫調制服務速率的M2M 小數據業務排隊分析模型

遲學芬，胡 廣，陳 潔，董 雯，王春悅

(吉林大學 通信工程學院，長春130012)

0 引 言

M2M(Machine to machine)業務大體分為監控視頻類業務(SVS)和小數據類業務(SDS)。當SVS 和SDS 共享網絡服務時，實時SVS 優先占用網絡帶寬，非實時SDS 占用網絡剩余帶寬。因此如何在保證實時業務網絡服務的前提下，定性、定量地評估網絡對小數據類業務的服務能力，從而實現最優網絡資源控制成為人們廣泛關注的問題。從排隊論的角度分析，SDS 接受的網絡服務的服務率是由SVS 狀態空間決定的隨機變量。從包級別分析，SVS 包的到達和服務均為隨機過程，因此，系統對SDS 的服務過程是疊加在SVS隨機過程上的另一個復雜隨機過程，這增加了分析SDS 服務特性的難度。

相對于經典排隊理論，可變服務速率排隊系統分析更為復雜，可供參考文獻有限。Boxma等［1］研究了M/G/1 排隊系統，在這個系統中服務率是變化的。Pan［2］研究了具有可變輸入率、服務率和不耐煩顧客的M/M/1 隊列，分析了如何維持服務率以取得最大利益。Lebedev 等［3］研究了服務率隨請求數變化的重試隊列，得到了穩態概率的顯示表達式。Zhou 等［4］研究了具有馬爾可夫調制服務時間的單服務器隊列，得到系統的平均隊長和平均等待時間等性能指標。Allen等［5］研究了具有時變到達率和服務率的多服務器系統，并且獲得了隊列長度分布。以上研究都假設服務率的改變發生在一個包完成服務時刻，因此求解復雜度降低。文獻［6］研究了馬爾可夫調制服務率的隊列，在一個請求的服務過程中服務率可變。針對M2M 業務可變服務率的研究，文獻［7］研究了H2H、M2M 業務共享LTE 網絡資源時的可變服務率包級排隊系統，得到海量M2M業務對H2H 業務性能的影響。文獻［8］研究了帶有門限的休假排隊系統，將H2H 業務的休假期看作是M2M 業務的服務期，研究了海量M2M 業務對H2H 平穩語音業務的影響。

由于SDS 包在接受服務期間，其服務率隨SVS 的狀態時變，因此各個SDS 包的服務時間并非獨立同分布，無法用經典排隊論方法來求解。本文采用3GPP 建議的beta 分布對SDS 數據包到達過程［9］進行建模，采用多態MMPP 對視頻環境過程［10］進行建模，運用隨機過程分析理論、排隊論和概率論分析時變馬爾可夫調制服務率下SDS的服務特性，得到SDS 的網絡服務時間的均值和方差。數值仿真試驗結果表明，SDS 平均服務時間受SVS 的突發度、到達率和服務率影響，而不受視頻環境過程的狀態變化速率影響，SDS 的服務時間還與自身的到達率有關。

1 系統建模

1.1 業務源建模

選取3GPP 建議的beta 分布對SDS 數據包的到達過程進行建模，即SDS 包的到達時間間隔服從beta 分布。beta 分布定義在區間［0，1］上，用參數(a，b)描述，其概率密度函數f(x)為:

通過選擇不同的參數(a，b)，beta 分布可以描述不同的到達特性。beta 分布的期望和方差分別為:

為了描述視頻業務的突發性和相關性，同時還能得到可行的解析解，本文采用MMPP-2 對SVS 數據包的到達過程進行建模。MMPP-2 用4個參數{α，β，r1，r2}表示［10］，圖1 為MMPP-2 的狀態轉移圖。

圖1 MMPP-2 的狀態轉移圖Fig.1 State transition diagram of MMPP-2

SVS 平均到達率為:

SVS 到達率的平方變差系數為:

式中:α、β 分別為狀態S1和S2的平均到達率;r1為狀態S1到S2的轉移率;r2為狀態S2到S1的轉移率。

1.2 系統建模

在M2M 組網中，實時SVS 優先占用系統帶寬，具有時延容忍特性的SDS 占用系統的剩余帶寬。本文將SVS 的狀態看作環境過程Z(t)，SDS的服務率隨環境過程Z(t)時變，將SDS 的隊長看作隨機過程X(t)，系統模型如圖2 所示。

圖2 系統模型Fig.2 System model

本文建立包級排隊模型，假定M2M 組網的系統容量為S;SVS 包的帶寬需求為D;到達過程服從MMPP-2 分布;逗留時間服從參數為μ 的指數分布。采用二維變量(Y1，Y2)(Y1={0，1，…，N}，Y2={1，2})描述系統中SVS 的狀態，第1 維表示系統中正在接受服務的SVS 包的個數，N 為滿足條件ND ≤S 的最大正整數，即任意時刻，SVS 所占用的系統帶寬不能超過系統容量;第2維表示SVS 包的到達相位。由于系統的剩余帶寬只與正在接受服務的SVS 包個數有關，與SVS包到達相位無關。因而環境過程處于狀態(i，k)時，SDS 可利用的系統帶寬為vi，vi=S－iD。SDS包的到達時間間隔服從beta(a，b)分布，為了保證到達系統的包具有無記憶性，假定SDS 包長服從參數為u 的指數分布，則環境狀態為(i，k)時SDS 的服務率為θi=uvi。

假定在無窮小時間內，SVS 最多只能到達或者服務一個包，則環境過程Z(t)是一個二維馬爾可夫過程，其無窮小生成矩陣Q 如下:

式中:

環境過程Z(t)的穩態概率矩陣P 通過下式求解:

式中:Q 為2(N+1)階方陣;P 為2(N+1)維行向量;e 為2(N+1)維單位列向量。

2 模型求解

2.1 SDS 包開始接受服務時Z(t)狀態概率空間

運用隨機過程分析理論、概率論和馬爾可夫排隊理論，分析Z(t)處于狀態(i，k)的穩態概率pik、SDS 包到達系統時Z(t)處于狀態(i，k)的概率及SDS 包開始接受服務時Z(t)處于狀態(i，k)的概率πik之間的相互關系。

如果第n 個SDS 包到達系統時立刻接受系統服務，則令In=1，否則In=0。

式中:γ(γ ＞0)為第n 個SDS 包到達系統時接受系統服務的概率。

式中:γik為第n 個SDS 包到達系統時，環境狀態為(i，k)時，這個包接受服務的比例。

式中:N(n)為前n 個到達系統的包中接收系統服務的包個數。

由上面的定義可以得到:

因而第n 個SDS 包到達系統時Z(t)處于狀態(i，k)的概率可以表示為:

化簡式(15)得:

式(16)兩邊令n 趨于無窮，由于γ ＞0，則N(n)也趨于無窮，得到和πik極限概率之間的關系為:

將式(18)代入式(17)中，得出:

由式(11)和(12)可以得出:

當SDS 到達率趨于0 時，到達時間間隔趨于無窮大，此時可以認為一個包到達系統后立刻接受系統服務。SDS 到達率為0 時，和πik分別表示為和它們之間的關系為:

當數據包的到達時間間隔服從負指數分布時，包到達系統時系統狀態的分布和系統狀態的穩態分布是相同的，這個重要的性質為PASTA(Possion arrivals see time averages)［11］。本文利用最小二乘法擬合，通過仿真得出當a=1，b ＞3 時，beta(a，b)與負指數分布具有類似的統計特性，可以較好地近似為負指數分布。因此在滿足以上要求的參數時，利用PASTA 可以得到π*ik 和pik之間的關系為:

(3)πik和pik之間的關系

由式(20)(22)可知，當SDS 到達率分別趨于0 和無窮時，SDS 包開始接受服務時Z(t)處于狀態(i，k)的概率πik與Z(t)處于狀態(i，k)的穩態概率之間關系可以表示為:

當SDS 到達率為其他值時，無法得到SDS 包開始接受服務時Z(t)處于狀態(i，k)的概率πik關于穩態概率pik的閉式解。因此分析到達率趨于零和無窮這兩種特殊情況，然后用這兩種特殊情況作近似分析。

2.2 SDS 包服務特性分析

由于SDS 服務率只與系統中接受服務的SVS包個數有關，因此在分析SDS 包服務過程時只考慮SVS 狀態第一維的影響。假設SDS 包開始接受服務時，Z(t)處于狀態(i，Y2)，定義該SDS 包的服務時間為Ti，它的服務可以分為兩種情況:

(1)服務完成之后，Z(t)仍然處于狀態(i，Y2)，即該SDS 包在環境狀態(i，Y2)下接受完服務。此時服務時間可以表示為Hi，由于環境狀態為(i，Y2)時，SDS 包的服務率為θi，因此Hi服從參數為θi的指數分布。

(2)服務未完成，Z(t)的狀態改變。假定SDS 包在Z(t)處于狀態(i，Y2)時未完成服務，Z(t)第一步跳轉到狀態(j，Y2)，跳轉時間表示為Gij。顯然，Ti等于狀態(i，Y2)與狀態(j，Y2)之間的跳轉時間Gij加上跳轉到狀態(j，Y2)后的服務時間。

由于SDS 包的服務時間服從指數分布，因此跳轉到狀態(j，Y2)之后所剩余的SDS 工作量依然服從參數為u 的指數分布，跳轉到狀態(j，Y2)后的服務時間可以表示為Tj。由上述分析可得Ti的表達式為:

式中:Gij為Z(t)狀態(i，Y2)到(j，Y2)之間的跳轉時間。

顯然，Z(t)第一維各態之間的跳轉率是一個二維矩陣，而Hi是服從一維參數θi的指數分布。由于SDS 的服務率只與當前時刻環境過程Z(t)的第一維狀態有關，因此本文忽略Z(t)第二維到達相位的影響，用平均到達率、平均服務率來表示Z(t)第一維各態間的跳轉率。將Gij簡化為一維，同時不改變各環境狀態下SDS 包的服務率。因此Z(t)的無窮小生成矩陣Q 可以表示為Q1，則Gij服從參數為的指數分布，其中是無窮小生成矩陣Q1中的元素。

利用LS 變換求解Ti的均值和方差。對式(26)兩邊進行LS 變換得到:

式(27)兩邊同時對s 求一階導數和二階導數并令s=0，得到以下等式:

求解式(28)和(29)可得出E(Ti)和E(Ti2)(i={0，1，…，N})。

SDS 的服務時間均值和方差可以表示為:

分別將式(23)(24)代入到式(30)(31)中，可以得出上述兩種特殊到達率下SDS 服務時間的均值和方差。

當SDS 到達率為其他值時，無法得到服務時間的閉式表達式。因此，本文研究上述兩種特殊情況，用上述兩種特殊情況作近似分析。假定SDS 到達率趨于無窮時所求得的平均服務時間為T∞，當SDS 包的到達時間間隔剛超過T∞時，SDS隊列穩定，平均服務時間可以近似認為是T∞。當SDS 到達時間間隔很大時可以用到達率為0 來近似。

3 仿真試驗及結果分析

通過仿真研究了SVS 優先占用服務器帶寬時服務器對SDS 的服務能力及SDS 的服務特性。主要研究了SVS 對SDS 服務特性的影響。設置仿真參數為:S=1.4;D=0.325;u=10;a=1;b=3.5;μ=1 ～20;SVS 平均到達率ρv=1 ～10個/ms;SVS 的平方變差系數Cv=0.14 ～0.70。

首先，分析SVS 的突發度對SDS 服務特性的影響，采用Cv來描述SVS 的突發度。取ρv=5，μ=3。圖3 為在兩種特殊SDS 到達率下，SVS 的突發度對SDS 服務時間均值和方差的影響。分析圖3 可知，SVS 的Cv越大，SDS 的平均服務時間越小，SDS 的服務時間越穩定。這是因為在SVS 平均到達率一定而Cv增大時，SVS 沒有包到達的時間段變長。對于SDS 而言，它的平均服務率增大，因此服務時間減小。

然后，分析SVS 的到達率對SDS 服務時間的影響，取μ=3，如圖4(a)所示。從圖4(a)可以看出SDS 的服務時間隨著SVS 到達率的增大而增大，最終趨于某一定值。這是由于當SVS 的到達率增大時，任意時刻系統中正在接受服務的SVS包的個數增多，SDS 可用的系統剩余帶寬減少，因此它的服務時間增大。當SVS 的到達率增大到一定程度時，任意時刻系統中正在接受服務的SVS 包個數達到N 的概率趨近于1，此時剩余帶寬趨于定值，因此SDS 的服務時間最終趨于定值。

圖3 SDS 服務時間均值和方差Fig.3 Average service time and variance of service time of SDS

接下來分析SVS 服務率對SDS 平均服務時間的影響。由圖4(b)可以看出，SVS 的服務率增大時，SDS 的平均服務時間減小，并最終趨于定值。顯然，在SVS 到達率一定的情況下，服務率增大，服務器用更短的時間服務完等量的SVS包。因此，服務器對SDS 包的平均服務率增大，SDS 的服務時間減小。當SVS 的服務率遠大于到達率時，服務器對SVS 的服務時間可以忽略，此時SDS 可用的系統帶寬趨于恒定，因此SDS 服務時間隨著SVS 服務率的增大最終趨于定值。

最后分析隨機過程Z(t)變化速率對SDS 服務特性的影響。由于SDS 到達時間間隔剛超過到達率趨于無窮時求出的平均服務時間T∞，用到達率趨于無窮這種特殊情況來近似分析。隨機過程Z(t)的變化速率與SVS 的到達率和服務率有關，引入放大因子g 來反映隨機環境過程Z(t)的變化速率，g 值越大表示隨機過程Z(t)變化得越快。圖4(c)為放大因子g 對SDS 服務時間均值和方差的影響。

圖4 SDS 服務特性Fig.4 Service feature of SDS

從圖4(c)可以看出:g 值的變化基本不會影響SDS 的平均服務時間;而隨著g 值的增大，SDS服務時間的方差不斷減小，最終趨于恒定值。這是因為當環境過程變化速率增大到一定程度時，在一個SDS 包服務期間，環境過程已經遍歷了所有的狀態，SDS 包的服務率趨于所有環境狀態下服務率的平均值。因此它的服務時間比較穩定，服務時間的方差趨于定值。

根據模型求解部分可知，當SDS 到達率不同時，SDS 包開始接受服務時的環境狀態概率空間不同，因此SDS 服務時間不同。由圖3 和圖4 可以看出，當SDS 到達率為無窮時，服務時間明顯比到達率為0 時小，然而很難得到SDS 包服務時間關于它的到達率的閉式解。

4 結束語

分析了在SVS 優先占用系統帶寬時，網絡對SDS 的服務能力及SDS 的服務特性?？紤]到SDS的時延容忍特性，將SDS 的服務率看作隨SVS 狀態時變?；谂抨犂碚摗⒏怕收摵碗S機過程分析理論，分析了SDS 的服務過程;在滿足一定要求的參數下推導得到SDS 服務時間的均值和方差。為SVS 優先占用系統帶寬時SDS 的服務分析提供了一種可行的方法，為網絡資源控制提供了理論依據。仿真試驗結果表明，SDS 的服務時間與SVS 到達的突發度、到達強度和服務率及SDS 自身到達率有關。

［1］Boxma O J，Kurkova I A.The M/G/1 queue with two service speeds［J］.Advances in Applied Probability，2001，33(2):520-540.

［2］Pan Quan-ru.The research and application of M/M/1/N queuing model with variable input rates，variable service rates and impatient customers［J］.World Academy of Science，Engineering and Technology，2011，51:1037-1040.

［3］Lebedev E A，Ponomarov V D.Retrial queues with variable service rate［J］.Cybernetics and Systems Analysis，2011，47(3):434-441.

［4］Zhou Y P，Gans N.A single-server queue with Markov modulated service times［EB/OL］.［2013-09-15］.URL:http://fic.wharton.upenn.edu/fic/papers/99/9940.pdf.

［5］Allen F，Ming L.A queuing system with time varying rates［J］.Statistics and Probability Letters，2009，80(5-6):386-389.

［6］Mahabhashyam S R，Gautam N.On queues with markov modulated service rates［J］.Queuing Systems，2005，51:89-113.

［7］遲學芬，石佳琳，張嘉盛，等.異質業務到達下共享服務器系統服務模式研究［J］.北京郵電大學學報，2013，36(6):75-78.Chi Xue-fen，Shi Jia-lin，Zhang Jia-sheng，et al.On service mode of a server sharing system with heterogeneous services arrival［J］.Journal of Beijing University of Posts and Telecommunications，2013，36(6):75-78.

［8］遲學芬，吳迪，劉丹.帶有門限的IBP+MMBP/Geo/1/K 休假排隊系統［J］.吉林大學學報:工學版，2013，43(3):781-787.Chi Xue-fen，Wu Di，Liu Dan.IBP+MMBP/Geo/1/K vacation queuing system with threshold［J］.Journal of Jilin University(Engineering and Technology Edition)，2013，43(3):781-787.

［9］Jian X，Zeng X P，Jia Y J，et al.Beta/M/1 model for machine type communication［J］.IEEE Communication Letters，2013，17(3):584-587.

［10］Kang S H，Kim Y H，Sung D K，et al.An application of markovian arrival process(MAP)to modeling superposed ATM cell streams［J］.IEEE Transactions on Communications，2002，50(4):633-642.

［11］Kulkarni V G.Modeling and Analysis of Stochastic Systems［M］.Second Edition.Boca Raton:CRC Press，1995.