李龍鎮(zhèn)

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

0 引言

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

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

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

1.1 泊松分布

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

①同質(zhì)性：電話呼叫到達(dá)的速率λ對(duì)時(shí)間來(lái)說(shuō)是個(gè)常數(shù)；

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

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

因?yàn)槊總€(gè)Rj是具備獨(dú)立性的隨機(jī)變量，所以Nt滿足二項(xiàng)式分布。由此我們得到：

因?yàn)椋?/p>

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

設(shè)定μ等于λt，則得到標(biāo)準(zhǔn)的泊松分布：

1.2 指數(shù)分布

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

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

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

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

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

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

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

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

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

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

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

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

圖2 隊(duì)列處理器速度為9600時(shí)的分組平均延遲時(shí)間

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

圖3 隊(duì)列處理器速度為9000時(shí)的分組平均延遲時(shí)間

圖4 隊(duì)列處理器速度為10200時(shí)的分組平均延遲時(shí)間

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

3 結(jié)論

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