單服務(wù)器隊列的仿真分析

李龍鎮(zhèn)

（延邊大學(xué)工學(xué)院，吉林延吉，133002）

0 引言

單服務(wù)器隊列(M/M/1)存在于社會生活中的方方面面，比如電話交換機系統(tǒng)、路由器緩沖區(qū)、鐵路購票系統(tǒng)、商場付款隊列、理發(fā)店排隊理發(fā)隊列等，因此出現(xiàn)了很多對單服務(wù)器隊列的研究文章，并取得了一定的成果[1～4]。

本文利用概率與數(shù)理統(tǒng)計學(xué)上的概率分析工具，通過分析和導(dǎo)出單服務(wù)器隊列的概率統(tǒng)計模型，導(dǎo)出了泊松分布模型，并以泊松分布模型為基礎(chǔ)導(dǎo)出了指數(shù)分布模型，并以此為基礎(chǔ)導(dǎo)出了單服務(wù)器隊列的仿真模型，最后利用計算機網(wǎng)絡(luò)仿真軟件OPNET對單服務(wù)器隊列進行了詳細的仿真分析，確定出服務(wù)器的數(shù)據(jù)處理速度與隊列中的數(shù)據(jù)等待時間的相互關(guān)系，并以圖形方式直觀地加以表示。

1 單服務(wù)器隊列的概率統(tǒng)計模型分析

1.1 泊松分布

為了導(dǎo)出泊松分布統(tǒng)計模型，我們以傳統(tǒng)的電話交換機為例，假設(shè)在時間段[0,t]內(nèi)在隨機時間X1,X2,…有電話呼叫到達電話交換機。在這里我們做了兩個假定：

①同質(zhì)性：電話呼叫到達的速率λ對時間來說是個常數(shù)；

②獨立性：在不同的時段內(nèi)到達的電話呼叫數(shù)是獨立的隨機變量。

設(shè)定在區(qū)間[0,t]內(nèi)到達的電話呼叫個數(shù)為Nt，則根據(jù)同質(zhì)性可以得出Nt的期望值E[Nt]=λt。把區(qū)間[0,t]劃分為n個相同小段，則每個小段區(qū)間為t/n。當n足夠大時，每個小段內(nèi)呼叫數(shù)只能是0或者1。設(shè)定Rj為第j個小段內(nèi)的呼叫數(shù)，則Rj只能是0或者1，Rj滿足概率值為pj的伯努利分布，即pj=λt/n。在區(qū)間[0,t]內(nèi)的所有呼叫總數(shù)可以表示為：

因為每個Rj是具備獨立性的隨機變量，所以Nt滿足二項式分布。由此我們得到：

因為：

組合以上公式，我們得到：

設(shè)定μ等于λt，則得到標準的泊松分布：

1.2 指數(shù)分布

我們定義 Ti=Xi-Xi-1為相互時間間隔，定義T1=X1為呼叫第一次到來的時間。為了觀察T1的概率分布，我們關(guān)心在t時間之后第一次呼叫到來的情況，即在[0，t]時間段沒有呼叫到來，可以用下面的公式表示：

即：T1滿足參數(shù)為λ的指數(shù)分布，對于T2我們假定T1=s，然后計算它們的條件概率：

由于公式結(jié)果與s無關(guān)，所以我們得出T2滿足指數(shù)分布，即：

同理對任何Ti都能導(dǎo)出其滿足指數(shù)分布，所以我們得出結(jié)論：對具有參數(shù)λ的泊松分布X1，X2，X3，…來說，其X1，X2-X1，X3-X2，…是獨立的隨機變量，都滿足具有參數(shù)λ的指數(shù)分布。

2 單服務(wù)器隊列的仿真模型分析

為了能用計算機程序設(shè)計仿真單服務(wù)器隊列，需要求出泊松分布或者指數(shù)函數(shù)的反函數(shù)。但由于無法求出泊松分布的反函數(shù)，所以重點就是求出指數(shù)函數(shù)的反函數(shù)。設(shè)定指數(shù)函數(shù)的分布函數(shù)為F(x),其反函數(shù)為Y,均勻分布函數(shù)為U，則可以實現(xiàn)下面的公式：

設(shè)定F(x)=u,則：

由于1-u和u都是分布在(0，1)之間的均勻分布函數(shù)，為了方便計算，可用u代替1-u，所以最終反函數(shù)可用下式表示：

由于任何計算機程序設(shè)計語言都具備產(chǎn)生(0,1)之間隨機數(shù)的隨機函數(shù)，所以可利用該公式對指數(shù)函數(shù)進行模擬，即對單服務(wù)器隊列進行仿真分析。為了簡化解決問題的復(fù)雜度，可以采用現(xiàn)有的仿真軟件，而不是利用某個計算機語言編程對其求解，所以本文采用已有仿真功能的OPNET[5～6]計算機仿真軟件對單服務(wù)器隊列進行仿真分析。

單服務(wù)器隊列在OPNET的節(jié)點圖如圖1所示，數(shù)據(jù)源模塊的設(shè)定如下：分組相互時間間隔為Exp(1)秒,分組大小為Exp(9000)位元，處理模型為acb_ fi fo，即先進先出隊列。在OPNET中，隊列本身包括緩沖區(qū)和處理器，隊列的設(shè)置如下：隊列處理器的處理速度為9600位元。由于處理完的分組繼續(xù)占據(jù)內(nèi)存，影響計算機系統(tǒng)的效率，所以再加上退出模塊，負責(zé)銷毀處理完畢的分組。仿真分析的重點在分組相互時間間隔、分組的大小以及隊列處理器的處理速度對隊列中的分組平均延遲時間的影響。為了簡化問題分析方法，我們假設(shè)分組相互時間間隔以及分組的大小不變，只是通過調(diào)整隊列處理器的處理速度來分析隊列中的分組平均延遲時間，通過多次仿真分析，發(fā)現(xiàn)在現(xiàn)有的條件下，即隊列處理器的處理速度為9600位元情況下，下調(diào)600個位元，即隊列分組處理器的處理速度為9000位元時，隊列的平均延遲時間開始增長，不趨向于穩(wěn)定。即系統(tǒng)緩沖區(qū)里的分組越來越多，最終導(dǎo)致系統(tǒng)崩潰。而當對處理器的處理速度設(shè)為10200位元時，隊列的平均延遲時間開始減少，大約一直減少到8秒左右。這對于實際情況也非常符合，即處理器的處理速度越快，隊列里的待處理事項也會越來越少。

圖1 OPNET仿真單服務(wù)器隊列的模塊圖

圖2為圖1模塊圖的仿真結(jié)果，在這里分組相互時間間隔為Exp(1)秒,分組大小為Exp(9000)位元，處理模型為acb_ fi fo，隊列處理器的處理速度為9600位元，從仿真結(jié)果可以看出平均延遲時間大約為15秒，系統(tǒng)隨著仿真時間的延長趨于穩(wěn)定。

圖2 隊列處理器速度為9600時的分組平均延遲時間

圖3為圖1模塊圖的仿真結(jié)果，在這里分組相互時間間隔為Exp(1)秒,分組大小為Exp(9000)位元，處理模型為acb_ fi fo，隊列處理器的處理速度為9000位元，可以看出隊列中分組平均延遲時間隨著仿真時間在同步增加，即隊列中等待處理的分組數(shù)目不斷增加，導(dǎo)致系統(tǒng)發(fā)生堵塞，最終會引起系統(tǒng)崩潰。

圖3 隊列處理器速度為9000時的分組平均延遲時間

圖4 隊列處理器速度為10200時的分組平均延遲時間

圖4為圖1模塊圖的仿真結(jié)果，在這里分組相互時間間隔為Exp(1)秒,分組大小為Exp(9000)位元，處理模型為acb_ fi fo，隊列處理器的處理速度為10200位元，可以看出隊列中分組平均延遲時間大約為8秒，系統(tǒng)隨著仿真時間的延長趨于穩(wěn)定。

3 結(jié)論

由于單服務(wù)器隊列應(yīng)用于現(xiàn)實社會中的各個角落，所以對其分析顯得非常重要。本文以單服務(wù)器隊列概率與數(shù)理統(tǒng)計模型入手，首先進行了詳細的理論分析，用概率與數(shù)理統(tǒng)計方式導(dǎo)出泊松分布和指數(shù)分布，然后再導(dǎo)出指數(shù)分布的反函數(shù)，即單服務(wù)器隊列的仿真函數(shù)，再用計算機網(wǎng)絡(luò)仿真軟件OPNET對其進行了仿真分析，主要以改變隊列處理器的數(shù)據(jù)處理速度來分析隊列中的分組平均延遲時間，通過仿真結(jié)果可以看出隊列處理器的數(shù)據(jù)處理速度對于延遲時間起到非常重要的作用，隊列處理器數(shù)據(jù)處理速度低，則延遲時間一直在上升，導(dǎo)致隊列內(nèi)等待處理的分組數(shù)目不斷上升，最終導(dǎo)致系統(tǒng)堵塞以至崩潰。至于分組相互時間間隔和分組大小對單服務(wù)器隊列的影響有待于以后進一步的研究。