馬占友,張世久，徐　彪

(燕山大學(xué)理學(xué)院,河北秦皇島　066004)

?

T型非搶占優(yōu)先權(quán)MM1排隊(duì)系統(tǒng)

馬占友,張世久，徐彪

(燕山大學(xué)理學(xué)院,河北秦皇島066004)

為了進(jìn)一步優(yōu)化認(rèn)知無(wú)線網(wǎng)頻譜的接入,在將T作為時(shí)間參數(shù)引入排隊(duì)系統(tǒng)的基礎(chǔ)上,提出了一種新的T型非搶占優(yōu)先權(quán)排隊(duì)策略,并將其引入M/M/1排隊(duì)模型中,系統(tǒng)分析并推導(dǎo)出顧客在系統(tǒng)內(nèi)的平均等待時(shí)間、平均逗留時(shí)間以及系統(tǒng)的平均隊(duì)長(zhǎng).最后通過(guò)Matlab軟件對(duì)顧客平均等待時(shí)間進(jìn)行了仿真模擬.

M/M/1排隊(duì)系統(tǒng);優(yōu)先權(quán);T型非搶占優(yōu)先權(quán);認(rèn)知無(wú)線網(wǎng)

0　引言

隨著無(wú)線通信應(yīng)用的不斷發(fā)展,固定的頻譜接入方式已經(jīng)越來(lái)越凸顯它的不足,很多學(xué)者和工程技術(shù)人員都在研究認(rèn)知無(wú)線網(wǎng)絡(luò)的優(yōu)化問(wèn)題.使得主用戶(hù)與次用戶(hù)的頻譜接入更加合理是提高無(wú)線通信效率的重中之重[1],而這就需要運(yùn)用優(yōu)先權(quán)排隊(duì)論做進(jìn)一步研究.

2006年，唐應(yīng)輝等[2]簡(jiǎn)單介紹了搶占和非搶占優(yōu)先權(quán)排隊(duì)系統(tǒng)，文獻(xiàn)[3,4]研究了具有搶占優(yōu)先權(quán)的M/M/1排隊(duì)系統(tǒng),并得出相應(yīng)的性能指標(biāo).2012年，Kim[5]提出了新的T型搶占優(yōu)先權(quán)排隊(duì)策略并分析了系統(tǒng)的性能,文獻(xiàn)[6]進(jìn)一步討論了非搶占有限優(yōu)先權(quán)M/M/1排隊(duì)系統(tǒng)及其性能指標(biāo).

本文在現(xiàn)有研究的基礎(chǔ)上討論T型非搶占優(yōu)先權(quán)M/M/1排隊(duì)系統(tǒng)及其在認(rèn)知無(wú)線網(wǎng)絡(luò)頻譜選擇中的應(yīng)用.頻譜接入技術(shù)中的網(wǎng)絡(luò)信息用戶(hù)分為主用戶(hù)和次用戶(hù)兩個(gè)等級(jí),在搶占優(yōu)先權(quán)排隊(duì)當(dāng)中,如果主用戶(hù)較多,則次用戶(hù)的平均等待接入時(shí)間就會(huì)大大增加,導(dǎo)致次用戶(hù)長(zhǎng)時(shí)間等待,頻譜資源利用率降低,達(dá)不到共享目的,因此需要對(duì)搶占優(yōu)先權(quán)排隊(duì)方式進(jìn)行優(yōu)化,進(jìn)而使得次用戶(hù)在合理情況下接入頻譜.

1　模型描述

T型非搶占優(yōu)先權(quán)M/M/1排隊(duì)模型描述如下:

(i)假設(shè)系統(tǒng)中的主用戶(hù)和次用戶(hù)分別表示為ClassⅠ和ClassⅡ,其中ClassⅠ優(yōu)先權(quán)高于ClassⅡ.兩個(gè)等級(jí)的顧客各自獨(dú)立地按照Poisson過(guò)程到達(dá)系統(tǒng),其參數(shù)分別為λ1和λ2;系統(tǒng)中顧客的服務(wù)時(shí)間服從參數(shù)為μ的指數(shù)分布,所以每位顧客的平均服務(wù)時(shí)間為1/μ.

(ii)設(shè)ρi=λi/μ表示服務(wù)強(qiáng)度,i=1,2;ρ=ρ1+ρ2,λ=λ1+λ2；Si為第i級(jí)顧客所需的服務(wù)時(shí)間,E(Si)=1/μ,i=1,2；T為時(shí)間參數(shù),且T≥1/μ.在為ClassⅠ顧客服務(wù)時(shí),系統(tǒng)每隔時(shí)間T就會(huì)將隊(duì)伍中首位ClassⅡ顧客插入隊(duì)伍中并為其服務(wù),而正在被服務(wù)的ClassⅠ顧客則被中止,等待插入的ClassⅡ顧客服務(wù)完畢再繼續(xù);而系統(tǒng)在被中止的ClassⅠ顧客重新接受服務(wù)時(shí)重新開(kāi)始計(jì)時(shí),時(shí)間T之后再插入ClassⅡ顧客并為其服務(wù);此后重復(fù)前面的過(guò)程,直至系統(tǒng)中沒(méi)有顧客(如圖1).當(dāng)時(shí)間T內(nèi)所有ClassⅠ顧客都被服務(wù)完后,ClassⅡ顧客自動(dòng)按照先到先服務(wù)的順序接受服務(wù).

(iii)假設(shè)同類(lèi)顧客按照先到先服務(wù)(FCFS)規(guī)則接受服務(wù),ClassⅠ比ClassⅡ有優(yōu)先權(quán),顧客的到達(dá)與服務(wù)過(guò)程獨(dú)立.

圖1　系統(tǒng)開(kāi)始服務(wù)后ClassⅠ顧客和ClassⅡ顧客的排隊(duì)情況

2　系統(tǒng)性能分析

令Lqi是第i級(jí)顧客的平均等待人數(shù),Wqi是第i級(jí)顧客的平均等待服務(wù)時(shí)間,i=1,2.

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

因顧客分為兩個(gè)等級(jí),所以本文也分為兩種情況進(jìn)行討論.

2.1.1到達(dá)系統(tǒng)的顧客為ClassⅠ顧客A當(dāng)?shù)竭_(dá)系統(tǒng)的顧客為ClassⅠ時(shí)(如圖2),將ClassⅠ顧客分為三種不同的情形：(X1)，(X2)和(X3).

圖2　ClassⅠ顧客A進(jìn)入系統(tǒng)時(shí)顧客的排隊(duì)情況

設(shè)Lq1xj表示(Xj)情形下ClassⅠ顧客的平均等待隊(duì)長(zhǎng),Wq1xj表示(Xj)情形下ClassⅠ顧客的平均等待時(shí)間,其中j=1,2,3.

(X1)顧客A進(jìn)入系統(tǒng)時(shí)ClassⅡ顧客足夠滿足按照時(shí)間間隔T插隊(duì).在這種情況下,顧客A的平均等待時(shí)間Wq1x1為以下三個(gè)時(shí)間之和:

因此,

(1)

(X2)顧客A進(jìn)入系統(tǒng)時(shí),ClassⅡ顧客不足夠滿足按照時(shí)間間隔T向前插隊(duì),加上顧客A等待被服務(wù)的過(guò)程中新進(jìn)入系統(tǒng)的ClassⅡ顧客還是不足夠按照時(shí)間間隔T向前插隊(duì),則顧客A的平均等待時(shí)間Wq1x2為以下三個(gè)時(shí)間之和:

因此,

(2)

(X3)顧客A進(jìn)入系統(tǒng)時(shí),ClassⅡ顧客不足夠滿足按照時(shí)間間隔T向前插隊(duì),但是在顧客A等待服務(wù)的過(guò)程中新進(jìn)入系統(tǒng)的ClassⅡ顧客足夠滿足按照時(shí)間間隔T向前插隊(duì),則顧客A的平均等待時(shí)間為以下三個(gè)時(shí)間之和:

因此,

(3)

2.1.2到達(dá)系統(tǒng)的顧客為ClassⅡ顧客B當(dāng)?shù)竭_(dá)系統(tǒng)的顧客為ClassⅡ時(shí)(如圖3),ClassⅡ顧客分為三種不同的情形:(Y1),(Y2)和(Y3).

圖3　ClassⅡ顧客B進(jìn)入系統(tǒng)時(shí)顧客的排隊(duì)情況

設(shè)Lq2yj表示(Yj)情形下ClassⅡ顧客的平均等待隊(duì)長(zhǎng),Wq2yj表示(Yj)情形下ClassⅡ顧客的平均等待時(shí)間,其中j=1,2,3.

(Y1)顧客B進(jìn)入系統(tǒng)時(shí),系統(tǒng)中的ClassⅡ顧客不足夠滿足按照時(shí)間間隔T插隊(duì)，此時(shí)顧客B的平均等待時(shí)間Wq2y1為以下三個(gè)時(shí)間之和:

因此,

(4)

(Y2)顧客B進(jìn)入系統(tǒng)時(shí),系統(tǒng)中的ClassⅡ顧客足夠滿足按照時(shí)間間隔T插隊(duì)，此時(shí)顧客B的平均等待時(shí)間Wq2y2為以下三個(gè)時(shí)間之和:

因此,

(5)

(Y3)顧客B進(jìn)入系統(tǒng)時(shí),系統(tǒng)中的ClassⅡ顧客足夠滿足按照時(shí)間間隔T插隊(duì),但在顧客B等待被服務(wù)的時(shí)間里,新到達(dá)的ClassⅠ顧客使得ClassⅡ顧客不再足夠按照時(shí)間間隔T插隊(duì),這時(shí)Wq2y3為以下三個(gè)時(shí)間之和:

因此,

(6)

從式(1),(3)式和(4),(6)式中解得:

根據(jù)上述分析得到:在(X1)和(Y2)情形下,ClassⅠ顧客的平均等待時(shí)間是相等的,即Wq1x1=Wq1y2.同理可以得到,Wq2x2=Wq2y1,Wq2x3=Wq2y1.

進(jìn)一步結(jié)合(1)～(6)式,可以得到

(d)在(Y1)情形下,Lq1≥μTq2,所以,

(f)在(Y3)情形下,它的概率與Py1,Py2之和為1,所以,

綜上所述,可以得到

2.2待定參數(shù)b

上述公式包含唯一的待定參數(shù)b,為了進(jìn)一步確定Wq1,Wq2，以下在三種取值方法下對(duì)b值分別加以確定.

1)均值法.假設(shè)b在[0,T]上服從均勻分布,則b=T/2.

2)強(qiáng)度法.假設(shè)系統(tǒng)中第i等級(jí)顧客的服務(wù)強(qiáng)度為ρi=λi/μ,則

3)概率法.假設(shè)系統(tǒng)的平均最大服務(wù)量為μT,則

將上述所有公式代入Wq1,Wq2中,即可得到相應(yīng)的平均等待時(shí)間.

2.3平均逗留時(shí)間及隊(duì)長(zhǎng)

顧客在系統(tǒng)中的平均逗留時(shí)間等于平均等待時(shí)間與平均服務(wù)時(shí)間之和.令Wi表示第i級(jí)顧客的平均逗留時(shí)間,i=1,2,則

根據(jù)Little公式[1],可以得到ClassⅠ和ClassⅡ顧客的平均等待隊(duì)長(zhǎng)分別為:

3　仿真結(jié)果

為了驗(yàn)證b的三種取值方法哪種更加合理,用Matlab對(duì)b的相關(guān)函數(shù)即ClassⅠ和ClassⅡ顧客的平均等待時(shí)間Wq1,Wq2進(jìn)行仿真模擬,其中λ1=1,λ2=2,T=5,μ分別取值5,8,10，結(jié)果見(jiàn)表1.

表1　當(dāng)λ1=1,λ2=2,T=5,μ取不同值時(shí)的平均等待時(shí)間

(a)λ1=1,λ2=2,T=25

(b)λ1=1,λ2=2,T=100

由表1結(jié)果可知,三種取值方法中,概率法條件下的Wq1,Wq2與仿真結(jié)果最為接近,說(shuō)明概率法最符合真實(shí)情況.

對(duì)比本文所介紹的新的優(yōu)先權(quán)模型和傳統(tǒng)的搶占型優(yōu)先權(quán)模型發(fā)現(xiàn),當(dāng)T變大的時(shí)候,兩個(gè)模型越來(lái)越相似.為了證明T型非搶占優(yōu)先權(quán)M/M/1排隊(duì)系統(tǒng)優(yōu)于搶占優(yōu)先權(quán)M/M/1排隊(duì)系統(tǒng),將T放大,分別取值25,100,進(jìn)行ClassⅡ顧客平均等待時(shí)間的仿真模擬，結(jié)果見(jiàn)圖4.

從圖4可以發(fā)現(xiàn),當(dāng)T變大時(shí),ClassⅡ顧客的平均等待時(shí)間也在變大,這說(shuō)明模型變?yōu)閾屨夹詢(xún)?yōu)先權(quán)排隊(duì)模型時(shí),ClassⅡ顧客的平均等待時(shí)間比本文介紹的T型非搶占優(yōu)先權(quán)M/M/1排隊(duì)系統(tǒng)要大,這會(huì)使得系統(tǒng)中的ClassⅡ顧客對(duì)于服務(wù)效率感到不滿,而在實(shí)際的認(rèn)知無(wú)線網(wǎng)絡(luò)頻譜選擇中,也會(huì)造成次用戶(hù)的頻譜選擇效率低下.

4　結(jié)論

在分析T型非搶占優(yōu)先權(quán)M/M/1排隊(duì)系統(tǒng)時(shí),計(jì)算了相應(yīng)的平均等待時(shí)間、平均逗留時(shí)間、平均隊(duì)長(zhǎng),并通過(guò)平均等待時(shí)間與仿真結(jié)果的對(duì)比,得到假設(shè)的三種取值方法當(dāng)中,概率法為b取值的最優(yōu)方法.T型非搶占優(yōu)先權(quán)M/M/1排隊(duì)系統(tǒng)與搶占優(yōu)先權(quán)M/M/1排隊(duì)系統(tǒng)的對(duì)比表明,T型非搶占優(yōu)先權(quán)M/M/1排隊(duì)系統(tǒng)更加合理,更有利于優(yōu)化服務(wù)系統(tǒng).

[1]齊永.試論認(rèn)知無(wú)線網(wǎng)絡(luò)中頻譜接入技術(shù)[J].電子技術(shù)與軟件工程,2014(19):42.

[2]唐應(yīng)輝,唐小我.排隊(duì)論——基礎(chǔ)與分析技術(shù)[M].北京：科學(xué)出版社,2006.

[3]李杰.基于具有強(qiáng)插優(yōu)先級(jí)的M/M/1型排隊(duì)系統(tǒng)網(wǎng)絡(luò)延遲分析[J].電子商務(wù),2013(4):314.

[4]張宏波,史定華.M/M/1搶占優(yōu)先權(quán)排隊(duì)平穩(wěn)指標(biāo)的尾部分析[J].系統(tǒng)科學(xué)與數(shù)學(xué),2014,34(1):1.

[5]KIM K.T-preemptive priority queue and its application to the analysis of an opportunistic spectrum access in cognitive radio networks[J].Computers and Operations Research,2012,39(7):1394.

[6]黃業(yè)文,吳紅,王遠(yuǎn)世.非搶占有限優(yōu)先權(quán)M/M/1排隊(duì)系統(tǒng)[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(13):80.

(責(zé)任編輯馬宇鴻)

M/M/1 queueing system with T-non-preemptive priority

MA Zhan-you,ZHANG Shi-jiu,XU Biao

(College of Science,Yanshan University,Qinhuangdao 066004,Hebei,China)

To optimize a spectrum access in cognitive radio network,a new priority discipline is proposed,which called T-non-preemptive priority discipline,T is a time parameter.T-non-preemptive priority discipline in an M/M/1 queueing system is studied,and then the average waiting time,the average dwell time and the average queue length are obtained while customers stay in the queueing system.Finally,the average waiting time with respect to different parameters is simulated by aid of Matlab software.

M/M/1 queueing system;priority;T-non-preemptive priority;cognitive radio network

10.16783/j.cnki.nwnuz.2016.02.007

2015-06-15;修改稿收到日期:2015-07-17

國(guó)家自然科學(xué)基金資助項(xiàng)目(61472341);河北省自然科學(xué)基金資助項(xiàng)目(A2014203096,G2013203169);燕山大學(xué)青年教師自主研究計(jì)劃項(xiàng)目(13LGA017)

馬占友(1974—),男，吉林松原人,教授，碩士研究生導(dǎo)師.主要研究方向?yàn)榕抨?duì)論及網(wǎng)絡(luò)性能分析.

E-mail:mzhy55@ysu.edu.cn

O 226

A

1001-988Ⅹ(2016)02-0029-05