非強占有限優先權M/M/1排隊系統

黃業文，吳紅，王遠世

1.華南理工大學 廣州學院，廣州 510800

2.中山大學 數學與計算科學學院，廣州 510275

非強占有限優先權M/M/1排隊系統

黃業文1，吳紅2，王遠世2

1.華南理工大學 廣州學院，廣州 510800

2.中山大學 數學與計算科學學院，廣州 510275

1 引言

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

2 系統假設

非強占有限優先權M/M/1排隊系統假設如下：

（1）顧客分為兩個等級，第1級享有最高優先權，第2級享有次優先權。

（2）顧客到達系統服從參數為λi的Poisson分布，λi為第i級顧客的平均到達率，i=1，2。

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

3 系統理論分析

3.1 系統隊長與等待隊長

對于整個排隊系統，不區分第1級還是第2級顧客，那么該系統是一個顧客按參數λ的Poisson分布到達，到達的時間間隔和服務員為每個顧客服務的時間均服從負指數分布，平均服務率為μ的M/M/1排隊系統，得系統平均隊長[1]：

系統平均等待隊長[1]：

3.2 顧客在系統中的等待時間

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

（a）到達系統的顧客為第1級顧客A。

（b）到達系統的顧客為第2級顧客B。

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

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

（1）顧客A排在隊末等待在其之前排隊的顧客平均服務時間之和T1：

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

（a2）第2級顧客不足夠按間隔α插位排隊，在A排隊等待期間，陸續到達的第2級顧客仍不足夠按間隔α插位排隊。第1級顧客A到來的時候，他就排在隊末等待服務，在A等待服務期間到來的第2級顧客會排在A之前進行服務，因此A在系統中所用的平均等待排隊時間Wq1a2由3部分組成：

（1）顧客A排在隊末等待在其之前排隊的顧客平均服務時間之和T1=ρ1Wq1a2。

（3）在顧客A排隊等待期間，陸續到達的第2級顧客優先插隊造成的平均耽誤時間之和T3。由于顧客A所需排隊等待時間為Wq1a2，在此期間內，第2級顧客到達的平均人數為Wq1a2λ2，其需要的平均服務時間T3=Wq1a2λ2ES2=ρ2Wq1a2，因此可得：

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

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

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

（1）正在排隊等待服務的排在顧客B之前的第1級顧客和全部第2級顧客平均服務時間之和T1。此時，第2級顧客平均排隊等待時間為ρ2Wq2b1，則相應的第1級顧客排隊等待時間為αρ2Wq2b1。

插隊排進顧客B的時候，系統正在服務的顧客是隨機的，因此一般情況下在B之前的第1級顧客不會剛好是第2級顧客的α倍，若系統當時排隊隊列的第1位顧客不是第2級顧客，這時第1級顧客數會比第2級顧客數的α倍要多。總之，在B之前會插隊排進比第2級顧客的α倍更多的第1級顧客，多出的第1級顧客數在0到α之間，記多出的平均插隊人數為b，則b個顧客接受服務的時間為，

下面計算b的值，有3種計算方法：

②Poisson概率法。當B到達系統時，若正在接受服務的顧客為第2級顧客，其后應該接著排的是α個第1級顧客，然后又是1個第2級顧客……則B之前會多出α個第1級顧客插隊排隊。這個事件出現的概率可以歸結為出現1個第2級顧客的概率p(1，λ2)；若當B到達系統時，發現正在接受服務的顧客為第1級顧客，之后是第2級顧客，則B之前會多出0個第1級顧客插隊排隊。這個事件的概率等于出現1個第1級顧客的概率p(1，λ1)；若B到達系統排隊時，發現正在接受服務的顧客為第1級顧客，之后是1個第1級顧客，接著是1個第2級顧客，此時B之前會多出1個第1級顧客插隊排隊。該事件的概率為p(2，λ2)……。由此可得：

③系統概率法。類似于Poisson概率法的討論，只是計算概率時以第1級顧客出現1個的概率為ρ1，第2級顧客出現1個的概率為ρ2來進行計算，因此

以上就是計算b值的3種方法，在用Matlab模擬實驗得出最優方法為系統概率法。

（b2）第2級顧客足夠按間隔α插位排隊，在顧客B排隊等待期間，陸續到達第1級顧客后，第2級顧客仍足夠按間隔插插位排隊。第2級顧客B在系統中所用的平均等待排隊時間由3部分組成。

（1）正在排隊等待服務的所有第1級顧客和第2級顧客平均服務時間之和：

（2）等待正在服務的服務員空閑出來的平均時間：

（3）在顧客B排隊等待期間，陸續到達的第1級顧客優先插隊造成的平均耽誤時間之和T3。第1級顧客到達的平均人數為Wq2b2λ1，其需要的平均服務時間為T3=Wq2b2λ1ES1= ρ1Wq2b2，因此可得：

（b3）第2級顧客足夠按間隔α插位排隊，在顧客B排隊等待期間，陸續到達第1級顧客后，第2級顧客不足夠按間隔α插位排隊。在顧客B排隊等待期間，陸續到達的第1級顧客優先插隊在顧客B之前的m個顧客造成的平均耽誤時間之和T3。這里顧客數m由兩部分構成，第一部分是插隊排在顧客B之前的陸續到達的αWq2b3λ2-Wq1b3λ1個第1級顧客，第二部分是由于隨機情況產生的b個插隊排隊人數，b的確定參照（b1），所以

因此，可得：

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

這時發現：

因為對于顧客B，（b1）和（b3）情形都是屬于第2級顧客不足夠按間隔α插位排隊的情形。

相等的還有：

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

下面計算各種情形出現的概率，記lsi為系統內第i級排隊等待的顧客數，i=1，2，包括正被服務和排隊等候的顧客，

先計算（b1）情形的概率pb1，此時ls1≥αls2，所以

3.3 顧客在系統中的逗留時間

顧客在系統中的平均逗留時間等于顧客在系統中的平均排隊時間加上平均服務時間。記Wsi為第i級顧客在系統中的平均逗留時間，則

3.4 不同優先級的隊長

第1、2級顧客在系統內等待的平均等待隊長：

4 模擬實驗結果

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

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

下面比較非強占有限優先權排隊系統和一般的非強占優先權排隊系統在不同情況下的運行結果，取λ1=3.85，λ2=0.15，μ=5，α=10作為有限優先權模型進行模擬。同時，由于當參數α=∞時，模型就變成第1組有完全優先權的非強占優先權排隊系統模型，可以取α=100和α=10 000進行模擬。當第1級顧客被服務1 000次時，統計1次各項平均數據，一共統計100次，其第2級顧客平均排隊等待時間結果對比，如圖1所示。

圖1 λ1=3.85，λ2=0.15，μ=5的第2級顧客平均排隊等待時間圖

5 結論

由模擬實驗知，本文討論非強占有限優先權M/M/1排隊系統時，提出的系統概率法得出的理論結果是恰當的，并且本文模型相對一般非強占優先權排隊模型，其系統顧客等待時間更加趨于穩定，更好地規避了系統崩潰風險。本文模型是為了解決計算機網絡應用中碰到的遠程教育視頻流傳輸問題提出的，至此本文給出了諸如顧客在系統中的等待時間等一些較好的結果，對問題的解決起到了一定的作用。但本文的研究工作只是初步的，例如實際中服務器可能不止一臺，而且本文對顧客到來假設服從Poisson分布也可以進行改進。下一步將對模型進行完善，使模型有更好的實際應用價值。

[1]陸傳賚.排隊論[M].北京：北京郵電大學出版社，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，Fantacci 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]寧玉新.一種處理多優先級業務的新模型[J].青島大學學報，2002，17（3）：1-6.

[9]王科，舒勤，李成.信元調度中的優先級排隊研究[J].通信技術，2009，42（11）：133-137.

[10]侯冬倩.反饋后優先非搶占的M/M/1排隊系統的等待隊長分析[J].山東理工大學學報：自然科學版，2009，23（3）：4-7.

[11]邊軍輝，尹文運，龐秀梅，等.M/G/1的反饋后優先排隊但非搶占的排隊系統的初步分析[J].江漢大學學報：自然科學版，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

以計算機網絡中實時視頻流傳輸的實際應用為基礎，建立非強占有限優先權M/M/1排隊系統模型；對該系統模型進行分析研究，推導出顧客在系統內的的平均等待時間、平均逗留時間和平均隊長。

排隊論；非強占；有限優先權；M/M/1排隊系統

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.

黃業文（1979—），男，講師，主要研究方向：數理統計，計算機網絡與分布計算，模式識別；吳紅（1966—），女，副教授；王遠世（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