具有加入最短隊(duì)列規(guī)則的大型排隊(duì)網(wǎng)絡(luò)的穩(wěn)定性研究

程慧慧， 辛超楠

(華北水利水電大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,河南 鄭州 450046)

0 引言

排隊(duì)網(wǎng)絡(luò)是一類重要的排隊(duì)模型，在實(shí)際中應(yīng)用非常廣泛，例如在ATM(automated teller machine)后臺(tái)服務(wù)管理器中，隊(duì)列的數(shù)量很容易達(dá)到數(shù)百個(gè)。針對(duì)這樣的排隊(duì)網(wǎng)絡(luò)，為了提高網(wǎng)絡(luò)性能，引入了“平衡”的概念，這種概念廣泛使用于計(jì)算機(jī)和電信網(wǎng)絡(luò)中的建模、控制和調(diào)度等方面[1-2]。排隊(duì)網(wǎng)絡(luò)中經(jīng)常采用的負(fù)載平衡策略是通過減少隊(duì)列長(zhǎng)度、縮短顧客等待時(shí)間、提高系統(tǒng)服務(wù)速率來提高網(wǎng)絡(luò)的性能。

負(fù)載平衡機(jī)制大致可以分為[3]：基于改變服務(wù)速率的方法，基于改變到達(dá)速率的方法，或者將這兩種方法相結(jié)合達(dá)到負(fù)載平衡的作用。加入最短隊(duì)列規(guī)則(join the shortest queue, JSQ)是常用的平衡機(jī)制之一，這種平衡機(jī)制已經(jīng)在隊(duì)列數(shù)目N較小的排隊(duì)系統(tǒng)中得到了廣泛的研究。例如HAIGHT F A[4]研究了兩個(gè)隊(duì)列系統(tǒng)中到達(dá)者加入最短隊(duì)列的情況下的隊(duì)長(zhǎng)分布。FLATTO L等[5]研究了兩個(gè)平行隊(duì)列中加入JSQ規(guī)則后，排隊(duì)系統(tǒng)的平穩(wěn)分布和平均隊(duì)長(zhǎng)。JOHRI P K[6]將JSQ規(guī)則拓展到服務(wù)速率依賴于狀態(tài)的排隊(duì)系統(tǒng)，得出了JSQ規(guī)則最小化了系統(tǒng)中的顧客數(shù)量和長(zhǎng)期平均響應(yīng)(等待)時(shí)間。MARTIN J B等[7]在經(jīng)典Jackson網(wǎng)絡(luò)的基礎(chǔ)上引入JSQ規(guī)則，研究了排隊(duì)系統(tǒng)隊(duì)長(zhǎng)的分布特征。

當(dāng)排隊(duì)系統(tǒng)中的隊(duì)列數(shù)目N較大時(shí)，在引入平衡策略后會(huì)變成高維的交互系統(tǒng)，難以進(jìn)行精確的性能分析。此時(shí)的排隊(duì)網(wǎng)絡(luò)可以看作是一個(gè)具有相互作用的排隊(duì)系統(tǒng)，這樣的排隊(duì)系統(tǒng)一般可以利用平均場(chǎng)模型來研究，該研究方法的主要優(yōu)點(diǎn)是可以通過求確定性系統(tǒng)的解來研究排隊(duì)系統(tǒng)的一些性質(zhì)。平均場(chǎng)理論最早應(yīng)用于統(tǒng)計(jì)物理[8-9]，后來陸續(xù)應(yīng)用于排隊(duì)論[10]和博弈論[11]等問題中。VVEDENSKAYA N D等[12]針對(duì)簡(jiǎn)單超市模型，利用平均場(chǎng)極限研究了排隊(duì)系統(tǒng)的平穩(wěn)分布和隊(duì)長(zhǎng)分布。DAWSON D A等[3]針對(duì)隊(duì)列間具有交互作用的大型排隊(duì)網(wǎng)絡(luò)，利用平均場(chǎng)近似的方法研究了排隊(duì)網(wǎng)絡(luò)的極限特征及其平穩(wěn)分布。DAWSON D A等[13]針對(duì)具有JSQ規(guī)則的大型排隊(duì)網(wǎng)絡(luò)，利用平均場(chǎng)近似研究了排隊(duì)網(wǎng)絡(luò)的一些極限特征，并且證實(shí)了在JSQ規(guī)則下排隊(duì)網(wǎng)絡(luò)的性能得到了提高。

本文將在服務(wù)速率依賴于顧客數(shù)的大型排隊(duì)網(wǎng)絡(luò)中引入JSQ規(guī)則，利用平均場(chǎng)近似的方法研究排隊(duì)系統(tǒng)的相關(guān)性質(zhì)。事實(shí)上,這一排隊(duì)網(wǎng)絡(luò)可以看作是一個(gè)反應(yīng)擴(kuò)散過程，對(duì)它的研究不僅具有很強(qiáng)的理論意義，而且也有很大的現(xiàn)實(shí)意義。此類排隊(duì)模型能夠在調(diào)度優(yōu)化等方面起到很大的作用，可以廣泛地應(yīng)用于計(jì)算機(jī)和電信網(wǎng)絡(luò)當(dāng)中。

1 模型簡(jiǎn)介

這一排隊(duì)網(wǎng)絡(luò)是由N個(gè)獨(dú)立的先到先服務(wù)(first come first serve, FCFS)的M/M/1隊(duì)列組成(N≥1)，其中每個(gè)隊(duì)列的等待區(qū)的容量是無限的，服務(wù)速率為μi,i=1,2,…(i表示顧客數(shù))，每個(gè)隊(duì)列均有一個(gè)到達(dá)率為λ的泊松到達(dá)，并且有一個(gè)額外的到達(dá)率為Nλs的泊松到達(dá)流，顧客可以從該到達(dá)流加入排隊(duì)網(wǎng)絡(luò)中的最短隊(duì)列。在本文所研究的排隊(duì)網(wǎng)絡(luò)中，所有隊(duì)列的運(yùn)行機(jī)制是一樣的，所以性能相同，可以通過研究其中的一個(gè)隊(duì)列來研究排隊(duì)網(wǎng)絡(luò)的平穩(wěn)性問題，方便起見稱這個(gè)隊(duì)列為典型隊(duì)列。

設(shè)E={0,1,2,…}，T≥0，DT(E)(D∞(E))表示從[0,T]((0,∞))到E的右連續(xù)且具有左極限的函數(shù)空間，它描述了單個(gè)隊(duì)列從t=0到T時(shí)刻(或∞)的樣本路徑。記Xt(ω)=X(t,ω)=ω(t)，也可以記做X(t)=X(t,ω)，其中ω∈DT(E)。Ft=σ{X(s),0≤s≤t}表示由{X(s),0≤s≤t}生成的最小σ代數(shù)，F(xiàn)=σ{X(t),t≥0}表示由{X(t),t≥0}生成的最小σ代數(shù)。P(D∞(E),F)表示(D∞(E),F)上的全體概率測(cè)度的集合。Pp(E)表示E上p階矩有限的概率測(cè)度的集合，p∈N+。P(E)表示E上的所有概率測(cè)度的集合。

2 平均場(chǎng)近似

到達(dá)速率為λ，服務(wù)速率為μi,i=1,2,…的M/M/1隊(duì)列的隊(duì)長(zhǎng)過程{Y(t),t≥0}是一個(gè)生滅過程，對(duì)應(yīng)的Q矩陣如下

對(duì)應(yīng)的算子Ω為

其中#A表示集合A中元素的個(gè)數(shù)，1A(·)表示集合A上的示性函數(shù)，當(dāng)A是一個(gè)單點(diǎn)x，則1A=1x。

因此，Q過程{X(N)(t),t≥0}是唯一的。

如果f∈Cb(EN)，則對(duì)應(yīng)的算子Ω(N)為

其中ek是第k個(gè)分量為1其余均為0的N維向量。由文獻(xiàn)[14]的定理2.1和推論2.2可知：

P(N)°X(N)(0)-1=u?N，

則稱P(N)是算子Ω(N)唯一的鞅解，其中u?N是EN上一維邊際測(cè)度為u的概率測(cè)度。

首先定義交互函數(shù)h

其中ms(ν)=min{k≥0,ν({k})>0}表示概率測(cè)度ν在E上的支集的最小點(diǎn)。下面引入非線性主方程

(1)

Ωh,u(t)f(i)=(λ+h(i,u(t)))(f(i+1)-f(i))+μi(f(i-1)-f(i)))1{i≥1}。

(2)

P(Xt+s=j|Ft)=p(t,Xt;t+s,j),P-a.s.，

其中轉(zhuǎn)移函數(shù)滿足

則稱P是馬爾可夫解。

由(1)和(2)可知，典型隊(duì)列在時(shí)刻t的Q矩陣為

(3)

其中u(t)(·)=P°X-1(t)(·)。

在文獻(xiàn)[13]中，由N個(gè)獨(dú)立的FCFS的M/M/1隊(duì)列組成的排隊(duì)網(wǎng)絡(luò)，每個(gè)隊(duì)列均有一個(gè)到達(dá)率為λ的泊松到達(dá)，服務(wù)速率為μ，并且有一個(gè)額外的到達(dá)率為Nλs的泊松到達(dá)流，顧客從該到達(dá)流加入網(wǎng)絡(luò)中的最短隊(duì)列。在λ+λs<μ,u0{0}>0的條件下，證得對(duì)任意時(shí)刻t均有u(t,0)>0。假設(shè)本文的服務(wù)速率μi滿足λ+λs<μi，并且infμi>μ，i=1,2,…。此時(shí)與文獻(xiàn)[13]相比，隊(duì)列的服務(wù)速率變大，所以空閑率變大，因此，在此假設(shè)下同樣可以有u(t,0)>0。這時(shí)Q矩陣(3)可以轉(zhuǎn)化為

矩陣(3)對(duì)應(yīng)的算子為Ωh,u(t)f(i)=(λ+h(i,u(t)))(f(i+1)-f(i))+μi(f(i-1)-f(i)))1{i≥1},i∈E。

3)假設(shè)j<0時(shí)qij=0，則C=sup{g(j1,j2):j2>j1≥0,j1,j2∈E}<∞，其中

因此，由文獻(xiàn)[15]的定理1.2可知，非線性主方程(1)的解存在且唯一。

(4)

δx表示在單點(diǎn)x處的狄克拉測(cè)度。{UN(t)}t≥0描述了隊(duì)長(zhǎng)的經(jīng)驗(yàn)分布的變化過程，假設(shè)PN表示經(jīng)驗(yàn)測(cè)度過程{UN(t)}t≥0的概率分布。

定義2假設(shè)u∈P1(E)。如果滿足條件

1)P°X0-1=u；

2)P°Xt-1=ut；

定理1假設(shè)λ+λs<μi,i=1,2,…，并且在初始時(shí)刻排隊(duì)系統(tǒng)中沒有顧客，即對(duì)所有的N均有UN(0)({0})=1。如(4)所定義的{UN(t)}t≥0在過程弱收斂的意義下收斂到非線性主方程的唯一解。

(5)

(6)

由引理2可得

取s=0，由(6)可得

(7)

對(duì)應(yīng)的算子為

(8)

某起 110KV高壓斷路器發(fā)生拒動(dòng)，經(jīng)過檢查可以發(fā)現(xiàn)，在機(jī)械與后臺(tái)的指示燈都處于合閘的狀態(tài)下，分閘的線圈可以通過二次引線處流膠。而線圈過熱時(shí)，進(jìn)行分閘動(dòng)鐵心的動(dòng)作就會(huì)發(fā)生卡滯，將分閘線圈進(jìn)行拆解檢查，發(fā)現(xiàn)主分閘線圈的電阻是0，而動(dòng)鐵心完全卡死，無法動(dòng)作。這時(shí)的線圈漆包線也由于過熱而被燒壞。此時(shí)使用備用的分線圈電阻是112 Ω，處于正常狀態(tài)，而動(dòng)鐵心的動(dòng)作保持正常。

利用泰勒展開可得

因此(8)式可化簡(jiǎn)為

(9)

取K=λ+λs+μ′+1,μ′=supμi，由(9)可知轉(zhuǎn)移速率以NK為界，轉(zhuǎn)移幅度小于或等于|φ|/N。由于{UN：N≥1}在D∞(PN(E))上是弱緊的，所以對(duì)任意的{N′}?{N}存在{N″}?{N′}使得UN″弱收斂到U，其中{U(t),t≥0}是一個(gè)測(cè)度值過程。由(7)和(9)式可知P∞是以G為生成元的鞅問題的解

GF(ν)=f′(〈ν,φ〉)〈ν,Ωh,νφ〉。

與文獻(xiàn)[16]的定理1.1的證明過程相似，令f(x)=x，

令f(x)=x2，

所以

因此可知U(t)是非線性主方程(1)的解且是唯一的，定理證明完畢。

3 平穩(wěn)分布

定理2在JSQ系統(tǒng)中，如果λ+λs<μi,i=1,2,…，則有唯一的平穩(wěn)分布

并且當(dāng)μi=μ時(shí)(i=1,2,…)，JSQ系統(tǒng)的平穩(wěn)分布與文獻(xiàn)[13]中JSQ系統(tǒng)的平穩(wěn)分布一致。

證明已知λ+λs<μi,i=1,2,…，若時(shí)間t趨向于無窮，則Q矩陣可以表示為

由πQ=0,π=(π1,π2,…)得

化簡(jiǎn)得

-π0λ-λs+π1μ1=0,
-π1λ+π2μ2=0,
?
-πk-1λ+πkμk=0,

因此

所以

計(jì)算得

當(dāng)μi=μ時(shí)，

如果智能客戶可以選擇任意一個(gè)隊(duì)列加入(J∞Q：join any queue)，則Q矩陣可以表示為

這是一個(gè)到達(dá)率為λ+λs，服務(wù)速率為μi的M/M/1隊(duì)列。

定理3在J∞Q系統(tǒng)中，如果λ+λs<μi,i=1,2,…，則有唯一的平穩(wěn)分布

證明由πQ=0,π=(π1,π2,…)得

-π0(λ+λs)+π1μ1=0,
π0(λ+λs)-π1(λ+λs+μ1)+π2μ2=0,
?
πk(λ+λs)-πk+1(λ+λs+μk+1)+πk+2μk+2=0,

化簡(jiǎn)得

-π0(λ+λs)+π1μ1=0,
-π1(λ+λs)+π2μ2=0,
?
-πk(λ+λs)+πk+1μk+1=0,

所以

計(jì)算可得

例1由N個(gè)并行的FCFS的M/M/1隊(duì)列組成的排隊(duì)網(wǎng)絡(luò)，其中每個(gè)隊(duì)列有一個(gè)無限容量的等待區(qū)并且服務(wù)速率為μi=i+3,i=1,2,…，每個(gè)隊(duì)列均有一個(gè)到達(dá)率為λ=1的泊松到達(dá)，并且有額外(智能到達(dá))的一個(gè)到達(dá)率為Nλs的泊松到達(dá)流，其中λs=1，顧客將從該到達(dá)流加入最短隊(duì)列。

此時(shí)在JSQ系統(tǒng)中

因此

此時(shí)在J∞Q系統(tǒng)中

因此

下面我們對(duì)兩個(gè)排隊(duì)系統(tǒng)的平穩(wěn)分布進(jìn)行對(duì)比可得

在此種情況下可發(fā)現(xiàn)

因此加入最短隊(duì)列系統(tǒng)的性能得到了提高。

4 結(jié)論

本文利用平均場(chǎng)近似的方法研究了一類由大量隊(duì)列組成的排隊(duì)網(wǎng)絡(luò)，每個(gè)隊(duì)列均有一個(gè)泊松到達(dá)流，除此之外還有來自另外一個(gè)泊松流的顧客加入最短隊(duì)列。通過建立平均場(chǎng)相互作用模型，從極限的角度研究了該網(wǎng)絡(luò)的性能。結(jié)果表明，隊(duì)列長(zhǎng)度的經(jīng)驗(yàn)分布收斂到非線性主方程的解。并且網(wǎng)絡(luò)中任一隊(duì)列的平穩(wěn)分布與修正0處到達(dá)率的M/M/1隊(duì)列的平穩(wěn)分布相似。此外，加入最短隊(duì)列模型與加入任何隊(duì)列模型的平穩(wěn)分布之間的比較表明，加入最短隊(duì)列規(guī)則提高了網(wǎng)絡(luò)的性能。