具有时变马尔可夫调制服务速率的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 状态时变。基于排队理论、概率论和随机过程分析理论，分析了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.