具有加入最短隊(duì)列規(guī)則的Jackson網(wǎng)絡(luò)的性能分析

程慧慧，辛超楠

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

0 引言

排隊(duì)網(wǎng)絡(luò)是一類重要的排隊(duì)模型，在實(shí)際中應(yīng)用廣泛.很多學(xué)者經(jīng)常通過(guò)減少隊(duì)列長(zhǎng)度，縮短顧客等待時(shí)間或提高系統(tǒng)服務(wù)速率來(lái)提高排隊(duì)網(wǎng)絡(luò)的性能，比較常用的研究方法是加入最短隊(duì)列規(guī)則(join the shortest queue,JSQ).

Ephremides 等[1]提出：當(dāng)?shù)竭_(dá)的顧客被分配到兩個(gè)相似的指數(shù)服務(wù)器之一時(shí)，在已知兩個(gè)服務(wù)器上的隊(duì)列長(zhǎng)度時(shí)，最佳決策是將顧客分配到較短的隊(duì)列.Johri[2]證得JSQ規(guī)則最小化了服務(wù)速率依賴于狀態(tài)的排隊(duì)系統(tǒng)的顧客數(shù)和等待時(shí)間.當(dāng)排隊(duì)系統(tǒng)中的隊(duì)列數(shù)目N較大時(shí)，在引入JSQ規(guī)則后會(huì)變成高維的交互系統(tǒng)，這樣的排隊(duì)系統(tǒng)可以利用平均場(chǎng)模型來(lái)研究.平均場(chǎng)理論最早應(yīng)用于統(tǒng)計(jì)物理[3-4]，其優(yōu)點(diǎn)是可以通過(guò)求確定性系統(tǒng)的解來(lái)研究排隊(duì)系統(tǒng)的一些性質(zhì).Dawson等[5]針對(duì)隊(duì)列間具有交互作用的大型排隊(duì)網(wǎng)絡(luò)，利用平均場(chǎng)近似的方法研究了排隊(duì)網(wǎng)絡(luò)的極限特征及其平穩(wěn)分布.Dawson等[6]針對(duì)具有JSQ規(guī)則的大型排隊(duì)網(wǎng)絡(luò)，利用平均場(chǎng)近似研究了排隊(duì)網(wǎng)絡(luò)的一些極限特征，并證實(shí)了在JSQ規(guī)則下排隊(duì)網(wǎng)絡(luò)的性能得到了提高.

Jackson網(wǎng)絡(luò)是一種經(jīng)典的排隊(duì)網(wǎng)絡(luò)[7]，由J.R.Jackson[8]于1957年提出.Jackson網(wǎng)絡(luò)廣泛應(yīng)用于計(jì)算機(jī)系統(tǒng)和調(diào)度問(wèn)題中[9-11]，因此研究如何提高網(wǎng)絡(luò)的性能這一問(wèn)題就顯得非常有必要.Martin等[12]對(duì)經(jīng)典的Jackson網(wǎng)絡(luò)進(jìn)行修改，使每個(gè)節(jié)點(diǎn)具有N個(gè)隊(duì)列，顧客到達(dá)一個(gè)節(jié)點(diǎn)后隨機(jī)地選擇m個(gè)隊(duì)列，然后加入m個(gè)隊(duì)列當(dāng)中最短的一個(gè)，證得此時(shí)排隊(duì)網(wǎng)絡(luò)的平穩(wěn)分布呈超指數(shù)收斂，并且縮短了隊(duì)列的平均隊(duì)長(zhǎng).Azaron等[13]通過(guò)優(yōu)化控制Jackson網(wǎng)絡(luò)中所有節(jié)點(diǎn)的服務(wù)速率和到達(dá)速率，使得網(wǎng)絡(luò)最短路徑的期望值最小.Xia[14]研究了開(kāi)放Jackson網(wǎng)絡(luò)的準(zhǔn)入控制問(wèn)題，證明了最優(yōu)控制策略具有閾值形式.Imry等[15]在開(kāi)放Jackson網(wǎng)絡(luò)中利用節(jié)點(diǎn)生成法，得出了使系統(tǒng)的平均作業(yè)數(shù)和響應(yīng)時(shí)間最小化的服務(wù)速率的再分配方法.Timmer等[16]考慮了一個(gè)具有獨(dú)立節(jié)點(diǎn)的Jackson網(wǎng)絡(luò)，每個(gè)節(jié)點(diǎn)可以通過(guò)調(diào)節(jié)顧客總的到達(dá)率(不依賴于狀態(tài))來(lái)減少排隊(duì)系統(tǒng)總的預(yù)期等待時(shí)間.Ansorena[17]利用封閉Jackson網(wǎng)絡(luò)模型，得到了使碼頭運(yùn)營(yíng)利益最大化的具體方案.晉良海等[18]通過(guò)構(gòu)建安檢系統(tǒng)的Jackson排隊(duì)網(wǎng)絡(luò)模型，優(yōu)化安檢系統(tǒng)服務(wù)參數(shù)，縮短了旅客提取行李的平均等待隊(duì)長(zhǎng).

目前關(guān)于Jackson網(wǎng)絡(luò)的研究基本上都是時(shí)齊的，對(duì)非時(shí)齊的Jackson網(wǎng)絡(luò)的研究較少.本文在文獻(xiàn)[5-6]的啟發(fā)下，將JSQ規(guī)則引入具有大量節(jié)點(diǎn)的Jackson網(wǎng)絡(luò)中，利用平均場(chǎng)近似的方法研究非時(shí)齊Jackson網(wǎng)絡(luò)的相關(guān)性質(zhì).

1 模型簡(jiǎn)介

假設(shè)Jackson網(wǎng)絡(luò)中含有J個(gè)節(jié)點(diǎn)(J很大但有限).在節(jié)點(diǎn)i∈{1,2,3,…,J}處，單位時(shí)間內(nèi)從系統(tǒng)外部進(jìn)入該節(jié)點(diǎn)的顧客數(shù)服從參數(shù)為λ′的泊松分布，顧客在該節(jié)點(diǎn)接受服務(wù)的時(shí)間服從參數(shù)為μ的指數(shù)分布.在第i個(gè)節(jié)點(diǎn)接受完服務(wù)后立刻以pij的概率進(jìn)入第j個(gè)節(jié)點(diǎn)，并在那里等候接受服務(wù)，或者以pi0的概率離開(kāi)系統(tǒng)，

記P:=(pij)，pij表示從節(jié)點(diǎn)i到節(jié)點(diǎn)j的轉(zhuǎn)移概率，并且有一到達(dá)率為Jλs的泊松到達(dá)流，顧客從該到達(dá)流加入排隊(duì)網(wǎng)絡(luò)中的最短隊(duì)列.

設(shè)E={0,1,2,…}，T≥0，DT(E)(D∞(E))

表示從[0,T]((0,∞))到E的右連續(xù)且具有左極限的函數(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á)速率為λi，服務(wù)速率為μi,i=1,2,…的M/M/1隊(duì)列的隊(duì)長(zhǎng)過(guò)程{Y(t),t≥0}是一個(gè)生滅過(guò)程，對(duì)應(yīng)的Q矩陣為

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

針對(duì)前面所描述的交互系統(tǒng)，記X(J)(t)=(X1(J)(t),…,XJ(J)(t))，其中Xk(J)(t)表示節(jié)點(diǎn)k處的顧客數(shù)量，k=1,…,J.X(J)(t)的概率分布為P(J)∈P(D∞(EJ)).令x=(x1,…,xJ)∈EJ，EJ表示E的J維笛卡爾積，則X(J)(t)的轉(zhuǎn)移速率為

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

網(wǎng)絡(luò)對(duì)應(yīng)的算子為

其中，ek是第k個(gè)分量為1，其余均為0的J維向量.

首先定義交互函數(shù)h:E×P(E)→R+:

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

(1)

其中〈ν,f〉表示f與ν的積分.

且有

(2)

因?yàn)槊總€(gè)節(jié)點(diǎn)具有相同的作業(yè)規(guī)律，所以通過(guò)研究節(jié)點(diǎn)k來(lái)研究排隊(duì)系統(tǒng)的相關(guān)性質(zhì)，方便起見(jiàn)稱之為典型隊(duì)列.

定義1假設(shè)u∈P(E)，如果ut(·)=P°Xt-1(·)滿足非線性主方程(1),且u0=u，P的初始分布為u，則稱P∈P(D∞(E),F)為非線性主方程的解.如果對(duì)任意的j∈E，有

P(Xt+s=j|Ft)=p(t,Xt;t+s,j),

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

則P是馬爾可夫解.

(a)如果定義

則

(3)

其中

(b)如果u0({0})=1，則

(4)

(5)

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

(6)

這一微分方程組與文獻(xiàn)[6]中的式(7)一致，同理可得結(jié)果(a).其中拉普拉斯變換保證了解的唯一性.

針對(duì)交互系統(tǒng)X(J)(t)=(X1(J)(t),…,XJ(J)(t))，定義

(7)

δx表示在單點(diǎn)x處的狄克拉測(cè)度.{UJ(t)}t≥0描述了隊(duì)長(zhǎng)的經(jīng)驗(yàn)分布的變化過(guò)程；PJ表示經(jīng)驗(yàn)測(cè)度過(guò)程{UJ(t)}t≥0的概率分布.

定義2假設(shè)u∈P1(E)，如果滿足以下條件：

1)P°X0-1=u；

2)P°Xt-1=ut；

(Xs)ds,Ft,P)是鞅.

則稱P∈P(D∞(E),F)是鞅問(wèn)題[u,Ω‖ut‖]的解.

引理得證.

(8)

由引理1可得

取s=0，可得

(9)

設(shè)

PJ(E)=

UJ(t)是D∞(PJ(E))上的馬爾可夫測(cè)度值過(guò)程,該過(guò)程的轉(zhuǎn)移速率矩陣為

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

(10)

利用泰勒公式可得

(11)

整理得

(12)

因?yàn)閧UJ：J≥1}在D∞(PJ(E))上是弱緊的，所以對(duì)任意的{J′}?{J},存在{J″}?{J′}，使得UJ″弱收斂到U.當(dāng)J趨于無(wú)窮時(shí)，由式(9)和(12)可知P∞是以G為生成元的鞅問(wèn)題的解，

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

令f(x)=x和f(x)=x2，可得

與文獻(xiàn)[19]中的定理1.1的證明過(guò)程相似.因此可知U(t)是非線性主方程(1)的解，由命題1可知解是唯一的，定理證明完畢.

3 平穩(wěn)分布

定理2在JSQ系統(tǒng)中，假設(shè)λ+λs<μ，則唯一的平穩(wěn)分布為

π0JSQ=1-ρ,πkJSQ=ρ(1-σ)σk-1,k≥1，

(14)

其中：

證明由定理1可知極限典型隊(duì)列在時(shí)刻t的Q矩陣可表示為

在平穩(wěn)條件λ+λs<μ下，如果時(shí)間t趨于∞，則

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

所以

最終可得

證畢.

如果一個(gè)智能客戶可以隨機(jī)地加入一個(gè)隊(duì)列，則對(duì)應(yīng)的Q矩陣為

(15)

對(duì)JSQ系統(tǒng)和J∞Q系統(tǒng)的平穩(wěn)分布進(jìn)行對(duì)比可得：

(1)π0JSQ=π0J∞Q，兩個(gè)系統(tǒng)的空閑率是相等的.通過(guò)計(jì)算可得JSQ系統(tǒng)和J∞Q系統(tǒng)的平均到達(dá)率和平均服務(wù)速率均相等，因此空閑率相等.平均到達(dá)率為

平均服務(wù)速率為

圖1 JSQ系統(tǒng)與J∞Q系統(tǒng)的平穩(wěn)分布對(duì)比

由圖1可得，存在k0，當(dāng)1≤kπkJ∞Q；當(dāng)k≥k0時(shí)，πkJSQ<πkJ∞Q.

(3)JSQ的平均隊(duì)長(zhǎng)小于J∞Q的平均隊(duì)長(zhǎng).

JSQ的平均隊(duì)長(zhǎng)為

J∞Q的平均隊(duì)長(zhǎng)為

綜上所述，JSQ規(guī)則下的Jackson網(wǎng)絡(luò)的性能得到了提高.

4 結(jié)語(yǔ)

將加入最短隊(duì)列規(guī)則引入Jackson網(wǎng)絡(luò)中，建立了一個(gè)平均場(chǎng)相互作用模型，從極限結(jié)果的角度研究了該網(wǎng)絡(luò)的性能.結(jié)果表明：隊(duì)列長(zhǎng)度的經(jīng)驗(yàn)分布收斂到非線性主方程的唯一解；將加入最短隊(duì)列模型和智能到達(dá)者隨機(jī)加入J個(gè)隊(duì)列中的任意一個(gè)的模型進(jìn)行對(duì)比，得出加入最短隊(duì)列規(guī)則提高了Jackson網(wǎng)絡(luò)的性能.