现代通信网络中的随机过程

第 3 章 Markov 排队模型及其推广第 3 章 Markov 排队模型及其推广 3.1 M/M/K 队列当到达过程为泊松过程，服务时间为指数分布时，排队问题的解具有极简单的形式。因此这类排队问题也称作“简单队列”。我们首先假定单一服务台系统，也即 M/M/1 队列。 3.1.1 M/M/1 队列长度令 N(t)=在 t 时刻队列长度 Pn(t)=P[N(t)=n] λ=到达率 μ=服务率在 t 以前的累积到达次数 A(t)，具有泊松分布，就是说 [ ( ) tAP = ] n = e n ( ) t t λλ − n ! , n = L,2,1,0 服务时间 S 的密度函数为 ( ) tf = − t µ µ , e µ 0> 由于到达间隔与服务时间都是指数分布，当服务台被占用时，在 h 时间内发生两个事件或两个以上事件（不论是到达或离去）的概率都是 O(h)，而且在两个不相重叠的间隔内发生的事件彼此互为独立。所以 Pn(t+h)可以分解 104

现代通信网络中的排队理论如下： [ ( tNP h ) = n + ] = + + ＋ [ ( ) tNP [ ( ) tNP [ ( ) tNP ( )hO ) 里有一个到达发生 [ ] ( h t,tP n 1 −= + [ ] ( ) t,tPn h = + 无事件发生 [ ] ( h n t,tP 1 = + ＋ ] ) 中一个离去发生 ] ] 由于在（t，t+h）中发生的事件其概率具有平稳性（即与 t 无关）又因为在（0，h）中既无到达也无离去的概率为 h µλ − )( 1 ) ( ) hOh + −= 1 ( ) ( )hOh + µλ + ( 1 − 上式可以写成或者 ( tP n h ) + P = n 1 − P + n ( ( ) ( ) tPht 1 + λ ( ) ( )hOht µ 1 + + n ( ) h µλ + ) − ( tP n + h ) − ( ) tP n = P n 1 − ( ) Pht λ n + 1 + ( ) ) ht hP µλµ n + − ( ( ) ( )hOt + 两边除以 h，再让 h→0，那么 ( ) tP ′ n = P λ n 1 − ( ) t + P µ n 1 + ( ) t − ( ) n,tP µλ n ( ) + = L,, 21 （3-1-1）若 n=0，则 ( tP 0 + h ) = ( )( tP 1 0 − 所以 h λ 1 + ( )hOhtP ( ) µ + ) ( ) tP ′ 0 = ( ) tP µ − 1 ( )tP λ 0 （3-1-2）（3-1-1）、（3-1-2）的解颇为复杂，在这一节里我们只讨论队列在平衡状态时的分布，也即当 t→∞，Pn(t)的解。如果 P n = lim t ∞→ ( ) n,tP n 210= L,,, 存在，那么 ( )∞′nP 必定为零。（3-1-1）与（3-1-2）可以重新改写为 105

第 3 章 Markov 排队模型及其推广 P P µλ 0 1 ( P n,P µ λµλ n n ) P n = + 1 − 1 + + = ⎡ ⎢ ⎣ （3-1-3） = L,, 21 利用 P0+P1+…=1 的关系，我们解得 P n = ⎛ ⎜⎜ ⎝ ⎞ λ ⎟⎟ µ ⎠ n ⎛ ⎜⎜ ⎝ 1 − ⎞ λ ⎟⎟ µ ⎠ n, = L,,, 210 （3-1-4）在上式中λ/μ为服务台的使用率，这个关系可以由 1-P0=λ/μ 或者 L=λW 的关系求得，通常为了方便，我们让ρ=λ/μ 所以 Pn=ρn(1-ρ), n=0,1,2, … （3-1-5）如果ρ<1，那么服务率大于到达率，（3-1-5）是一个几何分布，这时队列长度各个可能的状态是以 N(t)作为一个马尔可夫链时的正常返态，如果ρ ≥1，Pn 或者为零或者为负值，因此（3-1-1）、（3-1-2）不具有平稳分布的解。当 N(t)的状态为无穷大多时，平稳分布就可能不存在。在实际情况下，这几乎就意味着队列长度随着时间的流逝而无限增长。在实例中当到达率大于服务率时，服务系统上的流入量多于流出量，因此队列越来越长，在这里我们要提醒读者的是，首先，如果队列长度有一个上限（比如当队列长到一个程度就不再有到达发生），平稳分布就一定存在（这是因为马尔可夫链为一有限的正常返链），其次，纵然ρ≥1，（3-1-1）、（3-1-2）仍然可以有解只是极限解不存在，第三，如果起始条件为{N(0)=n}，那么由于指数分布的无后效性，我们可以把 N(t)进入 n 态时当作一个更新事件，进而由延迟更新过程的结果，可知更新事件的长期平均发生率等于更新事件发生间隔的均值的倒数，而且这个发生率与起始条件无关。队长的平稳分布本身可以理解为一“时间平均”值，也即在单位时间内队列长度在某一状态的时间长度，这个值等于一单位时间里队列长度进入某一状态的次数与每次返入该状态后停留在 106

现代通信网络中的排队理论该状态时间长度的乘积，让 u[n]表示更新发生间隔的均值，那么[u[n]]-1 就是更新事件的发生率，也就是单位时间内队长变为 n 的次数，如果 n>0，那么每次队长进入 n 状态时其平均停留时间就是（λ＋μ）-1。所以 P u = 1 µλ+ ( )nu （3-1-6）我们也可以用更新报酬定理来证明上式（由读者去证）。在前面我们提到，ρ< 1 时队长的各个状态都为正常返，因此队长的平稳分布存在，其平稳分布实则具有两重意义：第一，平稳分布是{Pn(t)}的极限分布，第二，又是一长期平均值，这个值所表示的是队长 N(t)平均停留在 n 态的相对时间，而各态的相对时间总和为一。假定ρ>1，也即λ>μ，这时我们可以把 N(t)当作到达累积数 A(t)与离去累积数 D(t)的差，由于到达过程为泊松过程，所以 E[A(t)]=λt，假定服务台永远未曾闲置，那么离去过程就等于一个以μ为发生率的泊松过程（因为服务时间为指数随机变量）。所以我们可以写成 E[D(t)]≤μt。（如果服务台曾经闲置过，那么 E[D(t)]≤μt）这样我们就得到 E[N(t)]=E[A(t)]-E[D(t)]≥(λ-μ)t 而当 t→∞，由于λ>μ，所以 E[N(t)]→∞，正如我们所预料的，队列将越来越长。最后我们再讨论ρ=1 的情形。令 πn=P[N(t)回到 0 态|N(0)＝n] Tn=E[回到 0 态所需的步数|N(0)＝n] 在进一步讨论之前，有必要解释一下 Tn 的定义，我们所谓的步数是指事件（到达或离去）发生的次数。“到达 0 态的步数”是说在 N(t)变成零之前总共有多少次事件发生。有时 Tn 也称作 N(t)“第一次抵达零态的时间”均值。用 NK 表示第 K 次事件（第 K 步）发生后 N(t)的状态，那么 107

第 3 章 Markov 排队模型及其推广 πn=P[N(t)回到 0 态|N0＝n，N1=n-1]P[N1=n-1|N0=n] + P[N(t)回到 0 态|N0＝n，N1=n+1]P[N1=n+1|N0=n] 由马尔可夫特性，我们知道 P[N(t)回到 0 态|N0，N1]=P[N(t)回到 0 态| N1]，又从第一章的结果可知。 P[N1 = n -1| N0= n] = P[离去先于到达] = μ/(λ+μ) P[N1 = n +1| N0= n] = P[到达先于离去] = λ/(λ+μ) 因此 π n = λ + µλ π n + 1 + µ + µλ π n （3-1-7） 1 − 在ρ= 1 的假设下， π n = 1 2 π n + + 1 1 2 π n 1 − 令▽n=πn-πn-1，则 ▽n=▽n+1 但是因为π0=1，所以 ▽1=π1-π0=π1-1，▽2=π2-π1=▽1=π1-1 或者π2= 2π1-1 用归纳法，可求得πk= kπ1- (k-1)，k=2，3，… 两边同除以 k，πk/k=π1- (k-1)/ k 让 k→∞，因为πk≤1，所以 0=π1-1 或者π1=1。由此可知πk= k - (k-1) = 1，k=1，2，…这就是说当ρ= 1 时各态均为常返态。接下来我们看一看 Tn 的值如何。 Tn = E[1+回到‘0’态的步数 | N0= n，N1 = n +1] P[N1 = n +1| N0= n] + E[1+回到‘0’态的步数 | N0= n，N1 = n -1] P[N1 = n -1| N0= n] =( T n 1 + ) 1 + λ + µλ ( T + n 1 − ) 1 + µ + µλ 因为ρ= 1， T n = 1 2 T n 1 + + 1 2 T n 1 − + 1 108

现代通信网络中的排队理论用 T0=0 的关系，可以推出即 Tn+1=(n+1)T1 - (n+1)n T 1 = T n n ( n ) 1 − + n, = L,, 32 由于 Tn ≥n，T1 随着 n 变大而为任意大的数，所以在ρ= 1 时，各态均为零常返。现在我们回到（3-1-5）式，让 N 表示在平衡状态下的队长，则 [ NE ] = ∞ ∑ n = 0 nP n = ∞ ∑ n = 0 ) n ρρ ( 1 − n = ρ − ρ 1 （3-1-8） [ NVar ] = [ NE 2 ] ( [ NE ] ) 2 − = ρ ( )2 1 ρ − （3-1-9）应当注意的是，E[N]是一项时间的平均数。也即第一章里提到的由于是在平衡状态下一个任意（随机）时刻看到队长等于 n 的概率，那么这个概率就与队列处于状态 n 的总共时间成比例。假定在 t 时刻队列长度为 n 时，让 In(t)=1，Jn(t)=n ，否则 In(t)=0，Jn(t)=0，n＝0，1，2，…，则： t ∫ 0 p n = lim t ∞→ [ NE ] = lim t ∞→ ds I n ( ) s t ∫ ∑ ∞ 0 t n = 0 J n ( ) s ds t ( ( ) tJ n In ⋅= ( ) ) t n （3-1-10） ∞ ∑ ∫ n 0 n = 0 t I n ds ( ) s t = lim t ∞→ 在下一节我们将讨论几个不同的队长概率分布。 109

第 3 章 Markov 排队模型及其推广 3.1.2 时间平均概率、到达平均概率与离去平均概率在排队论里队列长度的分布至少有三种不同的定义。除去（3-1-10）所表示的时间平均概率之外，还有所谓的“到达平均概率”和“离去平均概率”，令 αj(t)= 在(0，t)之间到达者看到队长为 j 的次数 βj(t)= 在(0，t)之间离去者看到队长为 j 的次数那么 ( )∑∞ j tα 就是在(0，t)之间累积的到达次数，而 =0j ( )∑∞ j tβ 则是累积的离 =0j 去次数。到达平均概率与离去平均概率所表示的队长分布为（注意：队长不包括到达者或离去者本身） α n = = b n = = P [ 一个到达者看到队长为 lim t ∞→ ( ) t α n ( )∑∞ t α j 0j = ] n （3-1-11） P [ 一个离去者看到队长为 lim t ∞↔ ( ) t β n ( )∑∞ t β j 0j = ] n （3-1-12）如果队长为零的状态为一常返态，那么每次队长由零增加为正整数时，不论怎么变化最后仍将返回归零。由零态返回零态之间，如果队长曾经增加到 n，那么每次由 n-1 增加到 n，就必定会由 n 减回到 n-1，这个增减的次数永远相等。但是由 n-1 变成 n 总是由一个到达所引起，而由 n 变为 n-1 时一定有一个顾客离去，到达者看到队长为 n-1 的次数就等于离去者看到队 110

现代通信网络中的排队理论长为 n-1 的次数。再者由零态经过队长增减的变化又复归零时，其到达的累积次数必定等于离去的累积次数。因此由（3-1-11）与（3-1-12）的定义我们可以得知 [定理 3-1] an=bn，n=0,1,2,… （3-1-13）这个关系的存在不以到达过程，服务时间，排队规则，服务系统的类别为前提，（3-1-13）是一个一般存在关系。接下来我们要讨论 pn（时间平均概率）与 bn 的关系。 [定理 3-2] 当到达过程为泊松过程时（λj=λ， ∀ j=0,1,2,…），M/G/1 先到先占的队列里， pn=an=bn，n=0,1,2,… 证明：令 Cj=连续两次 N(t)由 j +1 变为 j 的间隔 Nj=在 Cj 里 N(t)队列服务的人数 M0=在 Cj 里 N(t)队列上离去者看到 N(t)=0 的次数由于指数分布的无后效性，每次 N(t)从 j +1 变为 j 可以视作一个更新事件（有的书上称作“再生事件”，而称 Cj 为“再生周期”），所以 Cj 为一个更新间隔。由于在 Cj 里 N(t)停留在 j 态的时间为一个以λj 为参数的指数变量，那么用更新报酬定理的关系，我们立刻可知（把 N(t)=j 的时间当作报酬） p j = λ1 j ]j [ CE （3-1-14）又由于在 Nj 中只有一个离去者可以看到队长为 j，把 Nj 当作更新间隔长度，同样地由更新报酬定理可得 b j = 1 [ NE ]j 以及 b 0 = [ ] ME ]jNE [ 0 （3-1-15） 111

资料库

现代通信网络中的随机过程_第三章.pdf

相关推荐

课程资源

热门标签

最新资料