通信網(wǎng)理論分析

第2章通信網(wǎng)理論分析2.1排隊論基礎(chǔ)1.排隊模型基本概念只有一個服務(wù)員的單服務(wù)員排隊模型是最簡單的排隊模型。它由一個服務(wù)員和一個代表隊列的方框組成，如圖2.1所示。圖中的λ是顧客到達(dá)率或稱系統(tǒng)負(fù)荷，例如，在電話網(wǎng)中它表示單位時間內(nèi)發(fā)生的呼叫次數(shù)（呼叫/秒）；在分組交換網(wǎng)中表示單位時間發(fā)生的分組信息數(shù)（分組/秒）。μ是顧客離去率或稱系統(tǒng)服務(wù)率，它的單位與λ

相同。例如，在分組網(wǎng)中，μ

是由分組長度（bit）和鏈路傳輸速率（bit/s）所決定，其單位是分組/秒。例如，一條速率C

=

2

400bit/s的傳輸鏈路，在傳輸一個長度為1

000bit的分組時，其服務(wù)率μ=

2.4分組/秒。圖2.1單服務(wù)員排隊模型系統(tǒng)負(fù)荷與系統(tǒng)容量之比稱為服務(wù)強(qiáng)度或鏈路利用率，即ρ=

λ

/μ，這是排隊論中的一個重要的參數(shù)。對于單服務(wù)員排隊模型，當(dāng)ρ

趨近或超過1時，就會進(jìn)入阻塞，時延迅速增大，到達(dá)的分組被阻塞。對于一般的排隊系統(tǒng)，有一套A/B/C表示符號，A表示顧客到達(dá)的分布特性，B表示服務(wù)員的服務(wù)分布特性，C表示服務(wù)員的個數(shù)。有時采用A/B/C/K/M這樣的符號，A、B、C的含義不變，K表示排隊系統(tǒng)的容量，省略這一項表示K→∞；M表示潛在的顧客數(shù)，對于潛在顧客數(shù)M→∞時，也可省去此項。常見的幾種排隊系統(tǒng)模型符號表示如下。

M/M/1排隊：表示泊松到達(dá)、指數(shù)服務(wù)特性、一個服務(wù)員的排隊系統(tǒng)。這里符號M來自馬爾可夫（Markov）過程，用來表示泊松過程或相應(yīng)的指數(shù)分布。

M/M/m排隊：表示泊松到達(dá)、指數(shù)服務(wù)分布特性、m個服務(wù)員的排隊系統(tǒng)。

M/G/1排隊：表示泊松到達(dá)、服務(wù)時間服從一般分布的單服務(wù)員排隊系統(tǒng)。

M/D/1排隊：表示泊松到達(dá)、服務(wù)時間為常數(shù)的單服務(wù)員排隊系統(tǒng)。為了對泊松過程進(jìn)行定義，在時間軸上取一個很小的時隙Dt，如圖2.2所示。用下面3個表述來對泊松過程進(jìn)行定義。①在時隙△t中有一個顧客到達(dá)的概率定義為λ△t

+o(△t)，o(△t)表示△t的更高階項，當(dāng)△t

→0時，它更快地趨于0；λ

是一比例常數(shù)，且λ△t

<<1。②在△t中沒有顧客到達(dá)的概率是1?λ△t

+o(△t)。③到達(dá)是無記憶的，即在長度為△t的一個時隙內(nèi)的顧客到達(dá)，與以前或以后的時隙中的到達(dá)無關(guān)。圖2.2用于定義泊松過程的時隙圖2.3泊松到達(dá)的時間間隔利用上述3點，我們可以求得在T間隔內(nèi)有k個顧客到達(dá)的概率p(k)，由下式給出：

p(k)=(l

T)ke?l

T/k!（k

=

0，1，2，…）

（2.1）這就是熟知的泊松分布。其平均值E(k)和方差由下式給出:

（2.2）

（2.3）式中，l

為速率參數(shù)，它代表泊松到達(dá)的平均速率。圖2.3所示為隨機(jī)到達(dá)的示意圖，相繼到達(dá)之間的時間間隔為t，顯然，t

是一個連續(xù)分布的正隨機(jī)變量。對于泊松到達(dá)，可以證明t

服從指數(shù)分布，其概率密度函數(shù)f(t

)可由下式給出：

f(t)=le?lt（t

≥0）這一指數(shù)分布的平均值E(t

)為它的方差為：

=1/l2例如，某電話局忙時平均呼叫率為每小時1

000次，則平均來話間隔E(t

)

=

3.6s，平均來話間隔為10s的概率為0.94。2.

M/M/1，M/G/1，M/D/1排隊模型1）．M/M/1排隊模型

M/M/1排隊模型是一個符合泊松到達(dá)、指數(shù)服務(wù)時間、按先進(jìn)先出（FIFO）規(guī)則服務(wù)的單服務(wù)員排隊模型。圖2.4所示為M/M/1排隊模型示意圖，圖中顧客到達(dá)率為l

。圖2.4

M/M/1排隊模型我們首先利用此模型來分析該系統(tǒng)的相關(guān)統(tǒng)計特性：系統(tǒng)中的平均顧客數(shù)E(n)、平均排隊長度E(q)、顧客在系統(tǒng)中的平均逗留時間E(T)和平均等待時間E(w)等。假設(shè)，當(dāng)系統(tǒng)中有n個顧客時，稱此系統(tǒng)處于狀態(tài)n，與此對應(yīng)出現(xiàn)該狀態(tài)的概率為Pn。由此，我們可以用圖2.5表示M/M/1排隊系統(tǒng)的狀態(tài)轉(zhuǎn)移關(guān)系。例如，圖中“1”表示系統(tǒng)中有一個顧客，相應(yīng)的出現(xiàn)概率為P1，依此類推。圖2.5

M/M/1排隊系統(tǒng)的狀態(tài)圖在系統(tǒng)狀態(tài)圖中，有顧客到達(dá)時，狀態(tài)以l

速率向右轉(zhuǎn)移一步；有顧客完成服務(wù)時狀態(tài)以速率m

向左移動一步。在系統(tǒng)處于統(tǒng)計平衡狀態(tài)下，可列出系統(tǒng)統(tǒng)計平衡方程：（2.4）平衡方程是通過穩(wěn)態(tài)平衡原理來建立的，等式兩邊分別表示脫離狀態(tài)n的速率與由狀態(tài)n?1或n+1進(jìn)入狀態(tài)n的速率。在系統(tǒng)穩(wěn)態(tài)平衡條件下，脫離n狀態(tài)與進(jìn)入n狀態(tài)保持平衡，所有等式兩邊相等。根據(jù)此平衡方程，我們可以得到：在M/M/1排隊系統(tǒng)的存儲容量為無窮大時，可以利用概率歸一性條件：求得：

于是，可以得到無限存儲容量M/M/1排隊的平衡狀態(tài)概率：

（2.5）式中，r

＜1是上式能夠成立的必要條件。為使平衡得以存在，隊列的到達(dá)率或負(fù)荷必須小于輸出容量m

。如果在無限長排隊模型中Pn這一條件不滿足，隊列就會隨時間持續(xù)不斷地增長，而永遠(yuǎn)達(dá)不到平衡點。圖2.6所示為當(dāng)r

=

0.5時狀態(tài)概率的圖形表示。圖2.6

M/M/1狀態(tài)概率（r

=

0.5）根據(jù)所得到的狀態(tài)概率Pn，可以求得不同的排隊統(tǒng)計特性。根據(jù)隨機(jī)變量平均值的定義，排隊系統(tǒng)中的平均顧客數(shù)（包括正在被服務(wù)的一個）可以表示為（2.6）由平均隊長可以求得排隊平均時延，這可以利用Little公式進(jìn)行。Little公式是排隊論中的一個重要公式，它說明了平均到達(dá)率l

、平均時延E(T)和平均隊長E(n)三者之間的關(guān)系。

應(yīng)用Little公式，M/M/1排隊的平均時延E（T）可以表示為

式（2.7）的圖形表示如圖2.7所示，這一關(guān)系式對所有排隊系統(tǒng)，包括具有優(yōu)先級排隊規(guī)則的系統(tǒng)都是適用的。（2.7）（2.8）圖2.7

M/M/1排隊的平均隊長上面已經(jīng)分析了E(n)和E(T)。在M/M/1排隊中還有另外兩個統(tǒng)計量，即平均等待時間E(w)和平均等待顧客數(shù)量E(q)，它們之間的關(guān)系為：（2.9）（2.10）這4個統(tǒng)計量可以歸納為與l

、m

的關(guān)系：（系統(tǒng)中平均隊列長度）（顧客平均時間延遲）（平均等待顧客數(shù)）（顧客平均等待時間）可以將上述分析推廣到存儲容量為N的有限隊列排隊系統(tǒng)。這時與無限隊列排隊系統(tǒng)相比，平衡方程還是維持原狀，所不同的是邊界條件n

=

N。N對應(yīng)的狀態(tài)概率的歸一性條件為（2.11）E(n)lm=-l我們可以求得

所以有限隊列M/M/1排隊的狀態(tài)概率為排隊系統(tǒng)全滿的概率為

上述公式可用于計算分組的丟失率。（2.12）（2.13）（2.14）2）．M/G/1和M/D/1排隊對于排隊模型的到達(dá)過程和服務(wù)時間分布來說，它們是以馬爾可夫無記憶特性為基礎(chǔ)的這里將分析推廣到另一種情況，即一般服務(wù)時間分布，因此，分組或呼叫可以有任意（但已知）長度或服務(wù)分布。然而，到達(dá)過程仍為泊松的，假定是單服務(wù)機(jī)且隊列緩存器（等候室）是無限大的。根據(jù)Kendall標(biāo)記法，這種排隊稱作M/G/1排隊，其中G顯然指一般（general）服務(wù)分布?？梢宰C明平均隊列長度E(n)和經(jīng)過隊列的平均時延E(T)分別由下列表達(dá)式確定。（2.15）（2.16）這些公式是以兩個俄國數(shù)學(xué)家命名的，稱為Pollaczek-Khinchine公式（帕拉恰克－辛欽公式）。參數(shù)r

仍由給出，為平均到達(dá)率（泊松），這兩個表達(dá)式與M/M/1的相應(yīng)結(jié)果（兩式中括號前的項）看來是緊密相聯(lián)系的。這是一個值得注意的結(jié)果：泊松到達(dá)和任意服務(wù)分布排隊的平均隊列占用量（和相應(yīng)的時延）可由具有相同平均服務(wù)時間的指數(shù)服務(wù)分布排隊的結(jié)果乘以一個校正因子得到。式（2.15）和式（2.16）括號中的校正因子與服務(wù)分布的方差s2和服務(wù)率平均值的平方1/m2之比有關(guān)。為平均服務(wù)時間。參量s為服務(wù)時間分布的方差。2回憶指數(shù)分布的方差為s2

=

1/m2，即平均值的平方。在式（2.15）和式（2.16）中，設(shè)s2

=

1/m2，則可得到以前推導(dǎo)的M/M/1排隊的結(jié)果。當(dāng)s2增大，s2

>

1/m2時，相應(yīng)的平均隊長和時延也隨之增大。另一方面，當(dāng)s2

<

1/m2時，平均隊長和時延比M/M/1的結(jié)果小。作為一個特例，令所有顧客（分組或呼叫）都具有相同的服務(wù)長度1/m。這樣，s2

=

0，則有：（2.17）

顧客服務(wù)時間固定不變的排隊稱作M/D/1排隊，字母D表示確定的（det

erminIstic）服務(wù)時間。這是M/G/1排隊的一個特例，它的排隊長度和時延最小。如果r

不太大，可利用M/M/1的結(jié)果得到和。當(dāng)，M/D/1的結(jié)果與M/M/1的結(jié)果相差50%。（2.18）

3

M/M/m排隊到達(dá)率與離開率依賴于系統(tǒng)狀態(tài)的排隊系統(tǒng)如圖11.19所示，其相應(yīng)的穩(wěn)態(tài)狀態(tài)轉(zhuǎn)移關(guān)系如圖2.8所示。參數(shù)ln?1表示系統(tǒng)由狀態(tài)（n?1）進(jìn)入狀態(tài)n的顧客到達(dá)率，Pn表示系統(tǒng)處于狀態(tài)n的平衡概率，mn是在系統(tǒng)處于狀態(tài)n條件下的顧客離去率。根據(jù)離開狀態(tài)n的離去率等于進(jìn)入狀態(tài)n的到達(dá)率，可以得到系統(tǒng)的平衡方程：圖2.8與狀態(tài)相關(guān)的排隊系統(tǒng)與狀態(tài)相關(guān)的排隊狀態(tài)圖解平衡方程，可以求得系統(tǒng)的平衡概率Pn：式中，P0為概率常數(shù)，可以利用概率歸一性條件來求解。（2.19）

M/M/m排隊是與狀態(tài)相關(guān)的排隊的一個例子。在一個分組交換網(wǎng)中，如果統(tǒng)計集中器或分組交換機(jī)有m條出局中繼線，且輸出隊列的到達(dá)和離去均為指數(shù)統(tǒng)計特性，則該系統(tǒng)就是M/M/m排隊系統(tǒng)，其排隊模型如圖2.9所示。在此系統(tǒng)中，如果只有一個分組要傳輸，它立即以服務(wù)率m受到任一中繼線服務(wù)。如果有m個或更多的分組，則m條中繼線都被占用。因此在系統(tǒng)中，可以得到：圖2.9

M/M/m排隊模型利用上述條件和式（11.27），可以得到平衡概率：

式中：（2.21）（2.20）

M/M/m排隊的一個特殊情況是m為無窮大，這相當(dāng)于在分組交換或電路交換的情況下，傳輸線或中繼線的數(shù)量總是等于需要傳輸?shù)姆纸M和呼叫數(shù)，因而永遠(yuǎn)不會有阻塞的可能性，這時平衡狀態(tài)概率為：P0=e?r與狀態(tài)相關(guān)的排隊的第2個例子是M/M/N/N系統(tǒng)，這是一個有N個服務(wù)員但沒有等待室的排隊系統(tǒng)，并當(dāng)n

=

N時，將所有的到達(dá)阻塞掉。這一系統(tǒng)的排隊模型如圖2.10所示。這里ln

=

l，mn

=

nm，1≤n≤N。圖2.10

M/M/N/N排隊模型在這個系統(tǒng)中，ln

=

l，mn

=

nm，概率歸一性條件為（2.22），把這些條件應(yīng)用于式（11.16），可以求得：

這一公式就是求解電話系統(tǒng)阻塞概率的愛爾蘭B公式。

當(dāng)n

=

N時出現(xiàn)阻塞，因此阻塞概率PB為（2.23）2.2電路交換網(wǎng)分析1．呼損清除傳統(tǒng)的電話交換網(wǎng)是電路交換網(wǎng)。一個由若干個交換節(jié)點和交換節(jié)點間的中繼鏈路組成的電話交換網(wǎng)，如果在交換節(jié)點的全部出線都被占用的情況下仍有新的呼叫發(fā)生，交換節(jié)點向用戶送忙音，表示將這個呼叫從交換系統(tǒng)中清除，這種現(xiàn)象稱為呼損。對于交換節(jié)點來講，如果呼叫到達(dá)是泊松過程，中繼線群是全利用度線群，當(dāng)系統(tǒng)發(fā)生呼叫阻塞時，該呼叫會被立即清除，則該系統(tǒng)達(dá)到統(tǒng)計平衡狀態(tài)時，呼叫損失概率可以按愛爾蘭B公式進(jìn)行計算：

B(N，A)

=

（2.24）式中，B(N，A)表示流入話務(wù)量為A，中繼線數(shù)為N時的呼損概率，式中用A代替式（11.22）中的ρ，即

A

=λ/μ

（2.25）

A表示系統(tǒng)的業(yè)務(wù)強(qiáng)度，對于電話網(wǎng)就是系統(tǒng)承受的電話負(fù)荷（話務(wù)量）。例如，電話網(wǎng)的平均來話率λ=

300次/時，每次通話平均時間2min（即1/μ

=

2min），則此電話網(wǎng)的流入話務(wù)量A

=

10Erl。話務(wù)量單位用Erl（愛爾蘭，Erlang），是為了紀(jì)念丹麥話務(wù)理論家A.K.Erlang而命名的。話務(wù)量單位也可以用每小時百秒呼（ccs）來表示。Erl與ccs的關(guān)系是：Erl

=

36ccs。利用愛爾蘭B公式可以在一定的中繼線和流入話務(wù)量的情況下計算系統(tǒng)的呼損概率。舉例如下：假定某電話局在上午9:00～10:15有500次呼叫發(fā)生，每次呼叫平均占用時間為200s，中繼輸出線有29條，求呼損概率。解：

平均來話率為

l

=

500/(75×60)

=

0.111

1次/秒平均占用時間為

1/m

=

200s流入話務(wù)量為

A

=

呼損概率為

B(29，22.2)

=

=

0.031

2

=

22.2Erl愛爾蘭B公式是在求解阻塞概率或中繼線數(shù)中常用的計算公式。話務(wù)量、中繼線數(shù)和阻塞概率三者之間的關(guān)系已經(jīng)制成相應(yīng)圖或表，以便查閱。圖2.11及表11.3給出了在各種不同的中繼線數(shù)的情況下，呼損概率與流入話務(wù)量之間的關(guān)系。在實際中，呼損概率用下列遞推關(guān)系：（m=1，2，…，N）

（2.26）式中，初始值B(0，A)

=

1。由以上分析可知，在流入話務(wù)量之中，除大部分完成通話外，還有一部分被阻塞。完成通話部分話務(wù)量可以表示為

A‘

=

A[1?B(N，A)]（2.27）在上例中，容易算出完成話務(wù)量為

A'

=

22.2[1?0.0312]

=

21.5(Erl)

=

74%圖2.11呼損清除系統(tǒng)的阻塞概率對于此交換系統(tǒng)，我們可以進(jìn)一步求出出線的利用率：

η

=

2.3分組交換數(shù)據(jù)網(wǎng)分析在分組交換網(wǎng)中，分組信息在每一個節(jié)點被存儲、轉(zhuǎn)發(fā)而產(chǎn)生時延。交換節(jié)點的存儲、轉(zhuǎn)發(fā)功能可以用一個無限容量緩沖器的M/M/1排隊模型來表示，如圖2.12所示。為了分析分組信息時延，假定分組信息到達(dá)時，在緩沖器內(nèi)已有n個分組在等待發(fā)送。因此，要發(fā)送的分組信息通過節(jié)點的時延由等待時間和服務(wù)時間兩部分組成，即

T

=

等待時間+服務(wù)時間圖2.12交換節(jié)點中的緩沖過程模型等待時間是分組信息在節(jié)點上等待鏈路空閑所消耗的時間，服務(wù)時間是分組在鏈路傳輸時間的總和。在分組網(wǎng)中，每個分組信息在鏈路上的服務(wù)時間即傳輸時間為

式中1/m'是分組信息的平均長度（比特/分組），Ci是鏈路i的容量或速率（bit/s）。為了計算在節(jié)點的的等待時間，我們?nèi)员３謫畏?wù)員排隊系統(tǒng)的假設(shè)條件，于是可求得平均等待時間為（2.38）（2.29）式中l(wèi)i是鏈路i的分組到達(dá)率，單位為（分組/秒）。則分組通過節(jié)點和鏈路i的平均時延為（2.30）端—端平均時延圖2.13所示為由多個節(jié)點組成的分組交換網(wǎng)。分析端－端的平均時延，需要考慮從源點到目的地所經(jīng)過的路由上每段鏈路造成的時延影響。同時，由于路由中途經(jīng)的節(jié)點處可能會有新的分組發(fā)生，因此，我們在計算從源點發(fā)生的分組在經(jīng)過路由中各節(jié)點對時延的影響