西安电子科技大学：《通信网络基础》课程教学资源（讲义）第三章 网络的时延分析（时延模型）3.3.2 服务员有休假的M/G/1排队模型

M/G/1型排队系统

M/G/1型排队系统

Xidian Univ. M/G/A型排队系统 用户数不具有无后效性 。服务过程 6假定第个用户的服务时间为X,X是独立同分布的， 6与到达间隔相互独立。 令X={X1,X2,},则服务时间的均值和二阶矩为 平均服务时间=X=X)月 服务时间的二阶矩=X2=EX2} Broadband Wireless Communications Laboratory,Xidian University

Xidian Univ. Broadband Wireless Communications Laboratory, Xidian University M/G/1型排队系统  服务过程 假定第i个用户的服务时间为Xi，Xi是独立同分布的， 与到达间隔相互独立。 令 ，则服务时间的均值和二阶矩为 平均服务时间＝ ＝ 服务时间的二阶矩＝ ＝ X = {X1 , X 2 ,} X { } µ 1 E X = 2 X { }2 E X 用户数不具有无后效性

Xidian Univ. PK公式 ÷下面我们将证明，M/G/1排队系统的平均等待时间 为 AX2 W 21-p) 其中， p=么=双 该式称为P-K(Pollaczek-Khinchin)公式。 roadband Wireless communications caboratory.xidian university

Xidian Univ. Broadband Wireless Communications Laboratory, Xidian University  下面我们将证明，M/G/1排队系统的平均等待时间 为  其中，  该式称为P-K（Pollaczek-Khinchin）公式。 P-K公式 ( ρ) λ − = 2 1 2 X W λ X µ ρ = λ =

Xidian Univ. PK公式 。根据上述P-K公式，应用Little定理，可以得该系统的 平均时延为 7=灭+W=求+ 元X2 2(1-p) ÷平均队列长度为 2x2 No=iW= 21-p) ”系统中的平均用户数为 2x2 N=λT=λX+ 21-p） Broadband Wireless Communications Laboratory,Xidian University

Xidian Univ. Broadband Wireless Communications Laboratory, Xidian University P-K公式  根据上述P-K公式，应用Little定理,可以得该系统的 平均时延为  平均队列长度为  系统中的平均用户数为 ( ) 2 2 1 X T XW X λ ρ =+=+ − ( ρ) λ λ − = = 2 1 2 2 X N Q W ( ρ) λ λ λ − = = + 2 1 2 2 X N T X

Xidian Univ. PK公式 ÷如果G=M,即服务时间服从指数分布，M/M/1, X2= AX2 W三 2(1-p) 22(1-p)(1-p) 如果服务时间是常量，即M/D/1 等待时间是M/M/1 x=以 X2= 系统的一半 X W= 2(1-p) 22(1-p） 2μ(1-p) Broadband Wireless Communications Laboratory,Xidian University

Xidian Univ. Broadband Wireless Communications Laboratory, Xidian University P-K公式  如果G＝M，即服务时间服从指数分布，M/M/1，  如果服务时间是常量，即M/D/1 2 2 2 µ X = µ X = 1 2 2 1 µ X = ( ) ( ) ( ) 2 2 2 1 21 21 1 X W λ ρ λ ρ µ ρµ ρ = = = − −− ( ) ( ) ( ) 2 2 1 1 21 21 2 1 X W λ ρ λ ρ µ ρ µρ = = = − −− 等待时间是M/M/1 系统的一半

Xidian Univ PK公式 P-K公式证明的思路是基于对平均剩余服务时间(Mean Residual Service Time)的求解。设第i个用户到达系统 时，第1个用户正在接受服务，其剩余服务时间为Ri,此 时等待队列中有i个用户， i-N, 服务员 第1个用户正在接受服务 第个用户 到达 N个用户 1正在接受服务 第个用户到达剩余服务时间R 等待服务 (a) () Broadband Wireless Communications Laboratory,Xidian University

Xidian Univ. Broadband Wireless Communications Laboratory, Xidian University P-K公式  P-K公式证明的思路是基于对平均剩余服务时间（Mean Residual Service Time）的求解。设第i个用户到达系统 时，第l个用户正在接受服务，其剩余服务时间为Ri，此 时等待队列中有Ni个用户

Xidian Univ. i-1…i-W 服务员 PK公式 第个用户 到达 N个用户 1正在接受服务 等待服务 设第k个用户的服务时间为X,则由图可知，用户的等待时间为 W=R,+N,个用户的服务时间=R+ k=i-N ·对上式求平均得 -ER)E x ER)+X.EN,} W=lim W;R=lim ER)No =E Ni) i-→00 W-R+XNo-R+-Ng-R+2W-R+pW W R 1-0 roadband Wireless communications caboratory.xidian university

Xidian Univ. Broadband Wireless Communications Laboratory, Xidian University P-K公式  设第k个用户的服务时间为Xk，则由图可知，用户i的等待时间为  对上式求平均得 i i W W →∞ = lim ∑ − = − = + = + i 1 k i N i i i i k i W R N 个用户的服务时间 R X { } { i} { i} i k i N Wi E Ri E X k E R X E N i = + •         = + ∑ − = − 1 W R XN Q R N Q R λW R ρW µ µ = + = + = + = + 1 1 − ρ = 1 R W { i} i R E R →∞ = lim N Q = E{Ni}

Xidian Univ. PK公式 ÷假定系统有稳态解，且具有各态历经性，则剩余服务时间 可用下图表示 空闲 时间t M Broadband Wireless Communications Laboratory,Xidian University

Xidian Univ. Broadband Wireless Communications Laboratory, Xidian University P-K公式  假定系统有稳态解，且具有各态历经性，则剩余服务时间 可用下图表示 空闲

Xidian Univ. PK公式 为了方便起见，取为 rt)=0的时刻，则[0，t1区间 的平均剩余服务时间为 时间平均=集合平均 R=加2 式中，M()表示[0，t]区间内已服务的用户数。 上式可 以写成 M(t 系统稳态时，到达率=退去率 1 M( R,=2 i=1 M( 式中第二项为平均到达率，第三项为i的二阶矩。 时间x

Xidian Univ. Broadband Wireless Communications Laboratory, Xidian University P-K公式  为了方便起见，取t为 的时刻，则[0,t]区间 的平均剩余服务时间为  式中，M(t)表示[0，t]区间内已服务的用户数。 上式可 以写成  式中，第二项为平均到达率，第三项为Xi的二阶矩。 r(t) = 0 ( ) ( ) 2 1 0 2 1 1 1 i M t i t t X t r d t R ∫ ∑= = τ τ = ( ) ( ) M (t) X t M t R M t i i i ∑= = • • 1 2 2 1 时间平均=集合平均 系统稳态时，到达率=退去率 Rt

Xidian Univ. PK公式 g令t>0 ,得R=x R Ax2 W= Wax2 1-p 21-p) ÷即使P<1，如果X2o，则 W→0 。它说明，如果有少量用户有非常长的服务时间，一旦这些用 户被服务，将导致队列非常长。 Broadband Wireless Communications Laboratory,Xidian University

Xidian Univ. Broadband Wireless Communications Laboratory, Xidian University P-K公式  令 ，得  即使 ，如 果 ，则  它说明，如果有少量用户有非常长的服务时间，一旦这些用 户被服务，将导致队列非常长。 t → ∞ 2 2 1 R = λ X ( ρ) λ ρ − = − = 1 2 1 2 R X W 2 W ∝ X ρ < 1 → ∞ 2 X W → ∞