第二章網(wǎng)內(nèi)業(yè)務分析1ppt課件§1排隊論基礎

常見現(xiàn)象：顧客+服務→排隊系統(tǒng)矛盾統(tǒng)一

2ppt課件

廣義化： 通信中：呼叫——線路 信息包——分組交換機 移動體——服務區(qū)

計算機：總線指令——CPU處理 數(shù)據(jù)流——存儲器

其它：敵機——防空設施

客機——跑道

3ppt課件復雜性：在于隨機性——到達與離去（服務率）均不確定——工作于隨機狀態(tài)

資源少——顧客排隊長——服務質(zhì)量下降

資源多——服務閑置——資源浪費

4ppt課件目標：為顧客提供滿意服務同時提高資源利用率。（與統(tǒng)計參數(shù)和工作方式有關）在通信網(wǎng)的業(yè)務分析和性能計算中，排隊論是不可缺少的5ppt課件2.1.1、基本概念

m-窗口數(shù)，表示資源的量?？赏瑫r向顧客提供服務的設施數(shù)。（單窗口排隊系統(tǒng)m=1；多窗口排隊系統(tǒng)m>1）λ-顧客到達率（平均）μ-系統(tǒng)服務率（平均）1.排隊系統(tǒng)三要素:m，λ，μ6ppt課件平均到達時間

:

平均到達率λ——單位時間到達顧客數(shù)

或

(n(T)——T內(nèi)到達數(shù)）

λ↓——負荷輕

λ-顧客到達率（平均）7ppt課件同理——平均服務時間μ：系統(tǒng)服務率（平均）8ppt課件

此三量可已知或可測出，但描述排隊系統(tǒng)，此三要素不充分。

主要取決于ti

和τi的統(tǒng)計特性（分布）和排隊規(guī)則。9ppt課件2、統(tǒng)計特性（分布）和排隊規(guī)則。常見排隊系統(tǒng)的假設平穩(wěn)性：

[a，a+t]內(nèi)到達k個顧客（或離去）的概率與a無關，只與t有關。無后效性顧客到達時刻相互獨立不相交區(qū)間內(nèi)到達顧客數(shù)相互獨立系統(tǒng)顧客數(shù)具有馬氏性稀疏性：

Δt內(nèi)到達2個或2個以上顧客概率為0

有限區(qū)間內(nèi)的k為有限，或10ppt課件(1)T內(nèi)有k個顧客到達的概率在以上假設下：

T內(nèi)到達顧客數(shù)為kΔ內(nèi)有1顧客到達概率——Δ·λΔ內(nèi)無顧客到達概率——1-Δ·λ

有2個到達概率——

11ppt課件據(jù)無后效性,獨立據(jù)二項分布,N個貝努利分布T內(nèi)有k個到達的概率:

12ppt課件（2）到達間隔t的概率密度a（t）到達間隔t——連續(xù)變量把t分N份，到達間隔為t的概率：

（N個Δ內(nèi)無到達，第N+1個必到達）

若t的概率密度a（t）存在，則有：指數(shù)分布13ppt課件（3）服務時間的概率密度以上結果亦適用于服務過程，

可得14ppt課件綜上所述，在以上三個假設下？？？？？？：

顧客到達和離去均為泊松流，均值λ，二階矩λ(λ+1)

相鄰事件發(fā)生的間隔負指數(shù)分布，均值1/λ，二階矩1/λ2

具有馬爾可夫性，稱M分布稱最簡單流15ppt課件（4）運行方式及規(guī)則規(guī)定：排隊系統(tǒng)的運行性能不僅與上述的統(tǒng)計分布有關，還與系統(tǒng)預先規(guī)定的工作方式有關。包括服務規(guī)則和排隊規(guī)則：16ppt課件按服務規(guī)則分：1）先到先服務：常見情況2）后到先服務：不常見情況3）優(yōu)先制服務：顧客分優(yōu)先級17ppt課件按排隊規(guī)則分：1）等待型：不拒絕系統(tǒng)。若窗口不空，就依次排隊等待，直到被服務完畢后離去。2）截止型：分為損失制、拒絕系統(tǒng)系統(tǒng)已有n個顧客等待，顧客到來時，就被拒絕。分為如下2種即時拒絕：如窗口數(shù)為m,m=n,滿，則顧客到達后立即被拒絕，被拒絕排隊等待（電話網(wǎng)）延遲拒絕：m<n,允許等待一定數(shù)量，超n，再拒絕

(帶緩沖存儲的數(shù)據(jù)通信）18ppt課件(1)隊長k：某時刻觀察系統(tǒng)內(nèi)滯留的顧客數(shù)。(2)等待時間w:顧客從到達至開始被服務這段時間。(3)服務時間

：一個顧客被服務的時間(4)系統(tǒng)時間s，或稱系統(tǒng)停留時間：顧客從到達至離開的這段時間。S=w+

(5)系統(tǒng)效率：平均窗口占用率目標參量：（分析排隊系統(tǒng)時的主要求解指標)19ppt課件(6)穩(wěn)定性指標：對于不拒絕系統(tǒng)，當?shù)竭_率λ與服務率

之比（稱為排隊系統(tǒng)強度）大于窗口數(shù)m時，平均顧客到達數(shù)將大于平均顧客離去數(shù)，顧客的隊將越來越長，平均等待時間將趨于無限大，系統(tǒng)不穩(wěn)定。小于窗口數(shù)m時，系統(tǒng)是穩(wěn)定的(

<m)。對于截止型系統(tǒng)，因為隊長被限制，即使排隊強度大于m，系統(tǒng)仍然可以穩(wěn)定工作。

=λ/

20ppt課件隊長k

排隊長度—t瞬間系統(tǒng)內(nèi)的顧客數(shù)（含在窗口的）

k—離散隨機變量三種觀察：dk—顧客到達時觀察隊長為k的概率（不包括剛到達的顧客）rk—顧客服務完畢離去時觀察隊長為k的概率（不包括正在離去的顧客）。（以上為有條件抽樣）pk—（服務員）隨機觀察隊長為k的概率在最簡系統(tǒng)中，pk=rk=dk

—平均隊長，又稱系統(tǒng)數(shù)

21ppt課件等待時間w從到達

開始服務的時間，是連續(xù)隨機變量，其統(tǒng)計平均為：

—平均等待時間（網(wǎng)絡中等待時延的主要部分）其它時延，如傳輸時延和處理時延較小22ppt課件服務時間

開始接受服務

服務完畢離去

—平均服務時間

23ppt課件到達

離去

s=w+

對任何排隊系統(tǒng)，有系統(tǒng)時間s，或稱系統(tǒng)停留時間24ppt課件系統(tǒng)效率

平均窗口占用率共m個窗口，某時刻如有r個被占用，則25ppt課件

=λ/

穩(wěn)定性指標26ppt課件不拒絕系統(tǒng)：27ppt課件

仍然穩(wěn)定

截止型系統(tǒng)：28ppt課件排隊系統(tǒng)表示符號：A/B/m(N,n)A—

到達規(guī)律，分布a(t)（到達時間間隔）B—

服務規(guī)律，分布b(τ)（服務時間間隔）m—窗口數(shù)N—顧客源，潛在顧客數(shù)，省略為

n—截止隊長，省略為

，不拒絕29ppt課件常見分布：30ppt課件M—指數(shù)分布31ppt課件將討論:基本：M/M/1M/M/m(n)中級：M/G/1G/M/1高級：G/G/132ppt課件解法：

確定狀態(tài)變量，如k

畫狀態(tài)轉移圖

列狀態(tài)轉移方程

求解目標參量33ppt課件設平均到達率為，平均服務率為。取隊長為狀態(tài)變量建立系統(tǒng)的差微分方程。

1、狀態(tài)圖與狀態(tài)方程

—t時刻，系統(tǒng)內(nèi)有k個顧客的概率（k=0,1,2,…）二、M/M/1問題34ppt課件t時刻，k狀態(tài)則：

Δt—Δt內(nèi)到達1人概率

Δt—Δt內(nèi)離去1人概率35ppt課件t+Δt時刻處于k狀態(tài)（概率），由下述情況形成：t為k-1態(tài)，Δt內(nèi)到達1人，無人離去，概率:t為k+1態(tài)，Δt內(nèi)離去1人，無到達：t為k態(tài)，Δt內(nèi)到達1人，離去1人:t為k態(tài)，Δt內(nèi)無到達，無離去:36ppt課件37ppt課件即柯爾莫哥洛夫方程。

38ppt課件k=0,需重寫:

原1人,去1人

Δtp1(t)

原0人,無人到(1-Δt)p0(t)p0(t+Δt)=

Δtp1(t)+(1-Δt)p0(t)

得:

至此，得M/M/1完整狀態(tài)方程:

39ppt課件上式，已由

，

表示轉移，得狀態(tài)轉移圖：40ppt課件2、穩(wěn)態(tài)解

物理意義：到達與離去平衡，pk(t)與t無關

數(shù)學描述：41ppt課件42ppt課件求p0:用歸一化條件

p0——系統(tǒng)無人概率（空閑率）1-p0=

—系統(tǒng)有人概率（忙概率）

忙

太大

不穩(wěn)得通解：43ppt課件平均隊長

44ppt課件k的方差

45ppt課件46ppt課件47ppt課件等待時間w

若系統(tǒng)已有k人,即處于K狀態(tài),來一人的等待時間w是為前面k個人的服務時間總和即:

因為

i相互獨立，則wk是k個獨立變量之和，所以，wk

的特征函數(shù)為k個

i的特征函數(shù)之積。48ppt課件

i的特征函數(shù):(b(τ)概率的付氏變換)k個

i和的特征函數(shù)

49ppt課件因為k為離散變量,故w的特征函數(shù):

50ppt課件w的密度:平均等待時間:

w的方差:

系統(tǒng)時間(平均停留)

反驗Little公式:

51ppt課件至此,得M/M/1結論如下:

52ppt課件53ppt課件

所以,M/M/1主要矛盾集中在

的選取服務質(zhì)量與系統(tǒng)效率之間的矛盾解決目標:保證穩(wěn)定運行條件下提高效率

M/M/1系統(tǒng)的主要缺點是服務質(zhì)量與系統(tǒng)效率的的矛盾。解決的辦法有兩種

措施:（1）增加窗口數(shù)（增大效率，但投資加大）（2）截止排隊長度，即采用拒絕型系統(tǒng)（降低系統(tǒng)質(zhì)量（顧客被拒絕），換取效率和穩(wěn)定性）將上述兩個方法結合為截止多窗口排隊系統(tǒng)

54ppt課件三、M/M/m(n)問題

常見多窗口排隊方式有兩種：混合排隊（M/M/m(n))分別排隊(為M個獨立的M/M/1)55ppt課件M/M/m(n)排隊模型

窗口數(shù)為m,截止隊長為n.每個窗口的服務率均為，服務時間和到達間隔均為指數(shù)分布。即：

窗口服務時間總到達率令:

56ppt課件令系統(tǒng)內(nèi)顧客數(shù)k為狀態(tài)變量，此時，只有n+1種狀態(tài)。K<=m時，有k個窗口在被占用，則服務率為k

,當m<k<n時，m個窗口均被占用，則服務率為k。57ppt課件穩(wěn)態(tài)方程:page3858ppt課件當k=n時，pk=pn,為顧客被拒絕概率：

可見：

拒

，當k>n時,pk=0,永穩(wěn)定以拒絕換穩(wěn)定59ppt課件M/M/m(n)的平均等待時間

只算

情況即可

k=m等1人k=m+1等2

對k等k-m+1人60ppt課件所以:61ppt課件M/M/m(n)的幾種特例62ppt課件a)當n=m.為多窗口即時拒絕系統(tǒng)

63ppt課件b)當n

,為多窗口非拒絕系統(tǒng),數(shù)學的M/M/m問題

拒絕概率pc=0

平均等待的