非強(qiáng)占有限優(yōu)先權(quán)M/M/1排隊(duì)系統(tǒng)

黃業(yè)文，吳紅，王遠(yuǎn)世

1.華南理工大學(xué) 廣州學(xué)院，廣州 510800

2.中山大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，廣州 510275

非強(qiáng)占有限優(yōu)先權(quán)M/M/1排隊(duì)系統(tǒng)

黃業(yè)文1，吳紅2，王遠(yuǎn)世2

1.華南理工大學(xué) 廣州學(xué)院，廣州 510800

2.中山大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，廣州 510275

1 引言

如今人們的日常工作、生活與互聯(lián)網(wǎng)絡(luò)的關(guān)系越來越密切，常常要求在網(wǎng)絡(luò)通訊中既要保持某類服務(wù)的優(yōu)先性又要保證整體網(wǎng)絡(luò)的穩(wěn)定性。例如一個(gè)節(jié)點(diǎn)上有一臺(tái)服務(wù)器，服務(wù)器的多臺(tái)終端進(jìn)行不同課程的遠(yuǎn)程實(shí)時(shí)教學(xué)，同時(shí)少部分終端在進(jìn)行教學(xué)研討以及教學(xué)反饋等，此時(shí)既要優(yōu)先保證實(shí)時(shí)教學(xué)視頻流傳輸，同時(shí)也要保證少數(shù)終端的教學(xué)討論等正常網(wǎng)絡(luò)活動(dòng)。如何同時(shí)滿足這兩方面的要求，是一個(gè)十分有意義的研究課題，涉及到了優(yōu)先權(quán)排隊(duì)系統(tǒng)的討論。文獻(xiàn)[1]對(duì)強(qiáng)占及非強(qiáng)占優(yōu)先權(quán)系統(tǒng)進(jìn)行基本研究；文獻(xiàn)[2-5]討論分析了幾種優(yōu)先級(jí)系統(tǒng)的性能；文獻(xiàn)[6-11]更為深入地研究了非強(qiáng)占優(yōu)先權(quán)的排隊(duì)系統(tǒng)。從非強(qiáng)占優(yōu)先權(quán)排隊(duì)系統(tǒng)的研究[1]知道，在有優(yōu)先權(quán)的排隊(duì)系統(tǒng)中如果所有數(shù)據(jù)幀大部分有優(yōu)先權(quán)時(shí)，則有優(yōu)先權(quán)的數(shù)據(jù)幀的平均等待時(shí)間并不會(huì)縮短多少，此時(shí)，無優(yōu)先權(quán)的數(shù)據(jù)幀的平均等待時(shí)間卻會(huì)大大延長，甚至有時(shí)候會(huì)產(chǎn)生嚴(yán)重的隊(duì)列擁塞，導(dǎo)致排隊(duì)系統(tǒng)崩潰的結(jié)果。如果直接將優(yōu)先權(quán)排隊(duì)系統(tǒng)在實(shí)時(shí)視頻流傳輸中進(jìn)行應(yīng)用，可能會(huì)產(chǎn)生服務(wù)器被實(shí)時(shí)視頻流報(bào)文長時(shí)期霸占的無解狀態(tài)。因此需要對(duì)優(yōu)先權(quán)進(jìn)行限制，目的為了解除優(yōu)先權(quán)隊(duì)列源比較大的報(bào)文長期霸占服務(wù)器的狀態(tài)，使得在有限優(yōu)先權(quán)下，系統(tǒng)能夠很好地繼續(xù)進(jìn)行服務(wù)，穩(wěn)定性較好，不至于產(chǎn)生系統(tǒng)崩潰。本文以有限優(yōu)先權(quán)的報(bào)文在Internet中的傳輸為模型，對(duì)非強(qiáng)占有限優(yōu)先權(quán)M/M/1排隊(duì)系統(tǒng)進(jìn)行研究。

2 系統(tǒng)假設(shè)

非強(qiáng)占有限優(yōu)先權(quán)M/M/1排隊(duì)系統(tǒng)假設(shè)如下：

（1）顧客分為兩個(gè)等級(jí)，第1級(jí)享有最高優(yōu)先權(quán)，第2級(jí)享有次優(yōu)先權(quán)。

（2）顧客到達(dá)系統(tǒng)服從參數(shù)為λi的Poisson分布，λi為第i級(jí)顧客的平均到達(dá)率，i=1，2。

（3）服務(wù)員為每一級(jí)別的顧客服務(wù)的時(shí)間均服從參數(shù)為μ的負(fù)指數(shù)分布，平均服務(wù)時(shí)間為，μ為第i級(jí)顧客的平均服務(wù)率，i=1，2。

3 系統(tǒng)理論分析

3.1 系統(tǒng)隊(duì)長與等待隊(duì)長

對(duì)于整個(gè)排隊(duì)系統(tǒng)，不區(qū)分第1級(jí)還是第2級(jí)顧客，那么該系統(tǒng)是一個(gè)顧客按參數(shù)λ的Poisson分布到達(dá)，到達(dá)的時(shí)間間隔和服務(wù)員為每個(gè)顧客服務(wù)的時(shí)間均服從負(fù)指數(shù)分布，平均服務(wù)率為μ的M/M/1排隊(duì)系統(tǒng)，得系統(tǒng)平均隊(duì)長[1]：

系統(tǒng)平均等待隊(duì)長[1]：

3.2 顧客在系統(tǒng)中的等待時(shí)間

在系統(tǒng)平穩(wěn)之后，當(dāng)?shù)?級(jí)顧客A到達(dá)系統(tǒng)時(shí)，若系統(tǒng)空閑，則可直接接受服務(wù)員服務(wù)；若服務(wù)員正忙著，他不能強(qiáng)占服務(wù)員進(jìn)行服務(wù)，而只能在部分第2級(jí)顧客前排隊(duì)等待服務(wù)。當(dāng)?shù)?級(jí)顧客B到達(dá)系統(tǒng)時(shí)，若系統(tǒng)空閑，則可直接接受服務(wù)員服務(wù)；若服務(wù)員正忙著，他或者由于系統(tǒng)之前服務(wù)了α個(gè)第1級(jí)顧客而插隊(duì)排在隊(duì)伍前面的位置，或者只能排在隊(duì)末等待服務(wù)。記排隊(duì)等待服務(wù)的第i級(jí)顧客平均人數(shù)為Lqi，第i級(jí)顧客的平均排隊(duì)等待時(shí)間是Wqi，其中i=1，2。分兩種情況討論：

（a）到達(dá)系統(tǒng)的顧客為第1級(jí)顧客A。

（b）到達(dá)系統(tǒng)的顧客為第2級(jí)顧客B。

先討論第1種情況（a），到達(dá)系統(tǒng)的顧客為第1級(jí)顧客A，把兩隊(duì)列合并排隊(duì)，這時(shí)顧客A在系統(tǒng)中所用的平均等待排隊(duì)時(shí)間分為3種情形（aj），記第i級(jí)顧客排隊(duì)等待服務(wù)的平均人數(shù)為Lqiaj，平均等待時(shí)間為Wqiaj，i=1，2，j=1，2，3。對(duì)這3種情形的討論如下。

（a1）第2級(jí)顧客足夠按間隔α插位排隊(duì)。此時(shí)，第1級(jí)顧客A在系統(tǒng)中所用的平均等待排隊(duì)時(shí)間Wq1a1由兩部分組成：

（1）顧客A排在隊(duì)末等待在其之前排隊(duì)的顧客平均服務(wù)時(shí)間之和T1：

（2）等待正在服務(wù)的服務(wù)員空閑出來的平均時(shí)間T2。剩余服務(wù)時(shí)間記作Se，其均值為：

（a2）第2級(jí)顧客不足夠按間隔α插位排隊(duì)，在A排隊(duì)等待期間，陸續(xù)到達(dá)的第2級(jí)顧客仍不足夠按間隔α插位排隊(duì)。第1級(jí)顧客A到來的時(shí)候，他就排在隊(duì)末等待服務(wù)，在A等待服務(wù)期間到來的第2級(jí)顧客會(huì)排在A之前進(jìn)行服務(wù)，因此A在系統(tǒng)中所用的平均等待排隊(duì)時(shí)間Wq1a2由3部分組成：

（1）顧客A排在隊(duì)末等待在其之前排隊(duì)的顧客平均服務(wù)時(shí)間之和T1=ρ1Wq1a2。

（3）在顧客A排隊(duì)等待期間，陸續(xù)到達(dá)的第2級(jí)顧客優(yōu)先插隊(duì)造成的平均耽誤時(shí)間之和T3。由于顧客A所需排隊(duì)等待時(shí)間為Wq1a2，在此期間內(nèi)，第2級(jí)顧客到達(dá)的平均人數(shù)為Wq1a2λ2，其需要的平均服務(wù)時(shí)間T3=Wq1a2λ2ES2=ρ2Wq1a2，因此可得：

其中，T1、T2類似（a2）情形所求。

再接著討論第2種情況（b）。到達(dá)系統(tǒng)的顧客為第2級(jí)顧客B，將兩隊(duì)隊(duì)列分開排隊(duì)進(jìn)行討論，這時(shí)，該顧客B在系統(tǒng)中所用的平均等待排隊(duì)時(shí)間亦分為3種情形（bj），記第i級(jí)顧客排隊(duì)等待服務(wù)的平均人數(shù)為Lqibj，平均等待時(shí)間為Wqibj，i=1，2，j=1，2，3。對(duì)這3種情形的討論如下。

（b1）第2級(jí)顧客不足夠按間隔α插位排隊(duì)。Wq2b1由兩部分組成：

（1）正在排隊(duì)等待服務(wù)的排在顧客B之前的第1級(jí)顧客和全部第2級(jí)顧客平均服務(wù)時(shí)間之和T1。此時(shí)，第2級(jí)顧客平均排隊(duì)等待時(shí)間為ρ2Wq2b1，則相應(yīng)的第1級(jí)顧客排隊(duì)等待時(shí)間為αρ2Wq2b1。

插隊(duì)排進(jìn)顧客B的時(shí)候，系統(tǒng)正在服務(wù)的顧客是隨機(jī)的，因此一般情況下在B之前的第1級(jí)顧客不會(huì)剛好是第2級(jí)顧客的α倍，若系統(tǒng)當(dāng)時(shí)排隊(duì)隊(duì)列的第1位顧客不是第2級(jí)顧客，這時(shí)第1級(jí)顧客數(shù)會(huì)比第2級(jí)顧客數(shù)的α倍要多?？傊?，在B之前會(huì)插隊(duì)排進(jìn)比第2級(jí)顧客的α倍更多的第1級(jí)顧客，多出的第1級(jí)顧客數(shù)在0到α之間，記多出的平均插隊(duì)人數(shù)為b，則b個(gè)顧客接受服務(wù)的時(shí)間為，

下面計(jì)算b的值，有3種計(jì)算方法：

②Poisson概率法。當(dāng)B到達(dá)系統(tǒng)時(shí)，若正在接受服務(wù)的顧客為第2級(jí)顧客，其后應(yīng)該接著排的是α個(gè)第1級(jí)顧客，然后又是1個(gè)第2級(jí)顧客……則B之前會(huì)多出α個(gè)第1級(jí)顧客插隊(duì)排隊(duì)。這個(gè)事件出現(xiàn)的概率可以歸結(jié)為出現(xiàn)1個(gè)第2級(jí)顧客的概率p(1，λ2)；若當(dāng)B到達(dá)系統(tǒng)時(shí)，發(fā)現(xiàn)正在接受服務(wù)的顧客為第1級(jí)顧客，之后是第2級(jí)顧客，則B之前會(huì)多出0個(gè)第1級(jí)顧客插隊(duì)排隊(duì)。這個(gè)事件的概率等于出現(xiàn)1個(gè)第1級(jí)顧客的概率p(1，λ1)；若B到達(dá)系統(tǒng)排隊(duì)時(shí)，發(fā)現(xiàn)正在接受服務(wù)的顧客為第1級(jí)顧客，之后是1個(gè)第1級(jí)顧客，接著是1個(gè)第2級(jí)顧客，此時(shí)B之前會(huì)多出1個(gè)第1級(jí)顧客插隊(duì)排隊(duì)。該事件的概率為p(2，λ2)……。由此可得：

③系統(tǒng)概率法。類似于Poisson概率法的討論，只是計(jì)算概率時(shí)以第1級(jí)顧客出現(xiàn)1個(gè)的概率為ρ1，第2級(jí)顧客出現(xiàn)1個(gè)的概率為ρ2來進(jìn)行計(jì)算，因此

以上就是計(jì)算b值的3種方法，在用Matlab模擬實(shí)驗(yàn)得出最優(yōu)方法為系統(tǒng)概率法。

（b2）第2級(jí)顧客足夠按間隔α插位排隊(duì)，在顧客B排隊(duì)等待期間，陸續(xù)到達(dá)第1級(jí)顧客后，第2級(jí)顧客仍足夠按間隔插插位排隊(duì)。第2級(jí)顧客B在系統(tǒng)中所用的平均等待排隊(duì)時(shí)間由3部分組成。

（1）正在排隊(duì)等待服務(wù)的所有第1級(jí)顧客和第2級(jí)顧客平均服務(wù)時(shí)間之和：

（2）等待正在服務(wù)的服務(wù)員空閑出來的平均時(shí)間：

（3）在顧客B排隊(duì)等待期間，陸續(xù)到達(dá)的第1級(jí)顧客優(yōu)先插隊(duì)造成的平均耽誤時(shí)間之和T3。第1級(jí)顧客到達(dá)的平均人數(shù)為Wq2b2λ1，其需要的平均服務(wù)時(shí)間為T3=Wq2b2λ1ES1= ρ1Wq2b2，因此可得：

（b3）第2級(jí)顧客足夠按間隔α插位排隊(duì)，在顧客B排隊(duì)等待期間，陸續(xù)到達(dá)第1級(jí)顧客后，第2級(jí)顧客不足夠按間隔α插位排隊(duì)。在顧客B排隊(duì)等待期間，陸續(xù)到達(dá)的第1級(jí)顧客優(yōu)先插隊(duì)在顧客B之前的m個(gè)顧客造成的平均耽誤時(shí)間之和T3。這里顧客數(shù)m由兩部分構(gòu)成，第一部分是插隊(duì)排在顧客B之前的陸續(xù)到達(dá)的αWq2b3λ2-Wq1b3λ1個(gè)第1級(jí)顧客，第二部分是由于隨機(jī)情況產(chǎn)生的b個(gè)插隊(duì)排隊(duì)人數(shù)，b的確定參照（b1），所以

因此，可得：

其中，T1、T2類似（b2）情形所求。

這時(shí)發(fā)現(xiàn)：

因?yàn)閷?duì)于顧客B，（b1）和（b3）情形都是屬于第2級(jí)顧客不足夠按間隔α插位排隊(duì)的情形。

相等的還有：

由式（3）～（10），解得：

下面計(jì)算各種情形出現(xiàn)的概率，記lsi為系統(tǒng)內(nèi)第i級(jí)排隊(duì)等待的顧客數(shù)，i=1，2，包括正被服務(wù)和排隊(duì)等候的顧客，

先計(jì)算（b1）情形的概率pb1，此時(shí)ls1≥αls2，所以

3.3 顧客在系統(tǒng)中的逗留時(shí)間

顧客在系統(tǒng)中的平均逗留時(shí)間等于顧客在系統(tǒng)中的平均排隊(duì)時(shí)間加上平均服務(wù)時(shí)間。記Wsi為第i級(jí)顧客在系統(tǒng)中的平均逗留時(shí)間，則

3.4 不同優(yōu)先級(jí)的隊(duì)長

第1、2級(jí)顧客在系統(tǒng)內(nèi)等待的平均等待隊(duì)長：

4 模擬實(shí)驗(yàn)結(jié)果

為驗(yàn)證理論的正確性，用Matlab進(jìn)行模擬實(shí)驗(yàn)。表1給出了λ1=2.85，λ2=0.15，α=3，μ取不同值的幾種結(jié)果，其中λ1、λ2單位τ為512 bit時(shí)間。

表1 λ1=2.85，λ2=0.15，α=3，μ取不同值的結(jié)果

下面比較非強(qiáng)占有限優(yōu)先權(quán)排隊(duì)系統(tǒng)和一般的非強(qiáng)占優(yōu)先權(quán)排隊(duì)系統(tǒng)在不同情況下的運(yùn)行結(jié)果，取λ1=3.85，λ2=0.15，μ=5，α=10作為有限優(yōu)先權(quán)模型進(jìn)行模擬。同時(shí)，由于當(dāng)參數(shù)α=∞時(shí)，模型就變成第1組有完全優(yōu)先權(quán)的非強(qiáng)占優(yōu)先權(quán)排隊(duì)系統(tǒng)模型，可以取α=100和α=10 000進(jìn)行模擬。當(dāng)?shù)?級(jí)顧客被服務(wù)1 000次時(shí)，統(tǒng)計(jì)1次各項(xiàng)平均數(shù)據(jù)，一共統(tǒng)計(jì)100次，其第2級(jí)顧客平均排隊(duì)等待時(shí)間結(jié)果對(duì)比，如圖1所示。

圖1 λ1=3.85，λ2=0.15，μ=5的第2級(jí)顧客平均排隊(duì)等待時(shí)間圖

5 結(jié)論

由模擬實(shí)驗(yàn)知，本文討論非強(qiáng)占有限優(yōu)先權(quán)M/M/1排隊(duì)系統(tǒng)時(shí)，提出的系統(tǒng)概率法得出的理論結(jié)果是恰當(dāng)?shù)模⑶冶疚哪Ｐ拖鄬?duì)一般非強(qiáng)占優(yōu)先權(quán)排隊(duì)模型，其系統(tǒng)顧客等待時(shí)間更加趨于穩(wěn)定，更好地規(guī)避了系統(tǒng)崩潰風(fēng)險(xiǎn)。本文模型是為了解決計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)用中碰到的遠(yuǎn)程教育視頻流傳輸問題提出的，至此本文給出了諸如顧客在系統(tǒng)中的等待時(shí)間等一些較好的結(jié)果，對(duì)問題的解決起到了一定的作用。但本文的研究工作只是初步的，例如實(shí)際中服務(wù)器可能不止一臺(tái)，而且本文對(duì)顧客到來假設(shè)服從Poisson分布也可以進(jìn)行改進(jìn)。下一步將對(duì)模型進(jìn)行完善，使模型有更好的實(shí)際應(yīng)用價(jià)值。

[1]陸傳賚.排隊(duì)論[M].北京：北京郵電大學(xué)出版社，1993.

[2]Eng K Y.A photogenic knockout switch for high-speed packet networks[J].IEEE J Select Areas Commun，1988，6（7）：1107-1115.

[3]Hluchyi M G，Karol M J.Queuing in high-performance packet switching[J].IEEE J Select Areas Commun，1988，6（9）：1587-1597.

[4]Iliadis I，Denzel W E.Analysis of packet switches with input andoutputqueuing[J].IEEETransonCommun，1993，41（5）：731-740.

[5]Delre E，F(xiàn)antacci R.Performance evaluation of input and output queuing techniques in ATM switching systems[J].IEEE Trans on Commun，1993，41（10）：1565-1575.

[6]Krishna Reedy G V，Nadarajan R.A nonpreemptive priority multiserver queueing system with general bulk service and hetergeneous arrivals[J].Computers and Operations Research，1993，20（4）：447-453.

[7]Kapadia A S.Analysis of a finite capacity nonpreemptive priority queue[J].Computers and Operations Research，1984，11（3）：337-343.

[8]寧玉新.一種處理多優(yōu)先級(jí)業(yè)務(wù)的新模型[J].青島大學(xué)學(xué)報(bào)，2002，17（3）：1-6.

[9]王科，舒勤，李成.信元調(diào)度中的優(yōu)先級(jí)排隊(duì)研究[J].通信技術(shù)，2009，42（11）：133-137.

[10]侯冬倩.反饋后優(yōu)先非搶占的M/M/1排隊(duì)系統(tǒng)的等待隊(duì)長分析[J].山東理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，23（3）：4-7.

[11]邊軍輝，尹文運(yùn)，龐秀梅，等.M/G/1的反饋后優(yōu)先排隊(duì)但非搶占的排隊(duì)系統(tǒng)的初步分析[J].江漢大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，38（1）：8-9.

HUANG Yewen1,WU Hong2,WANG Yuanshi2

1.Guangzhou College,South China University of Technology,Guangzhou 510800,China
2.School of Mathematics and Computational Science,Sun Yat-Sen University,Guangzhou 510275,China

The limited-priority concept is raised based on the practical application on the transmission of a real-time video stream of computer network packet（cell）and a non-preemptive limited-priority M/M/1 queuing system is founded.To analyze and study the system,it deduces the average waiting time,the average dwell time and average queue length while customers stay in the queuing system.

queuing theory;non-preemptive;limited-priority;M/M/1 queuing system

以計(jì)算機(jī)網(wǎng)絡(luò)中實(shí)時(shí)視頻流傳輸?shù)膶?shí)際應(yīng)用為基礎(chǔ)，建立非強(qiáng)占有限優(yōu)先權(quán)M/M/1排隊(duì)系統(tǒng)模型；對(duì)該系統(tǒng)模型進(jìn)行分析研究，推導(dǎo)出顧客在系統(tǒng)內(nèi)的的平均等待時(shí)間、平均逗留時(shí)間和平均隊(duì)長。

排隊(duì)論；非強(qiáng)占；有限優(yōu)先權(quán)；M/M/1排隊(duì)系統(tǒng)

A

TP110.74

10.3778/j.issn.1002-8331.1111-0222

HUANG Yewen,WU Hong,WANG Yuanshi.M/M/1 queuing model under non-preemptive limited-priority.Computer Engineering and Applications,2013,49（13）：80-84.

黃業(yè)文（1979—），男，講師，主要研究方向：數(shù)理統(tǒng)計(jì)，計(jì)算機(jī)網(wǎng)絡(luò)與分布計(jì)算，模式識(shí)別；吳紅（1966—），女，副教授；王遠(yuǎn)世（1964—），男，副教授。E-mail：yewenh@foxmail.com

2011-11-17

2012-01-13

1002-8331（2013）13-0080-05

CNKI出版日期：2012-04-25http://www.cnki.net/kcms/detail/11.2127.TP.20120425.1721.061.html