唐柏榮， 王知人， 涂建新， 李泉林

(1.燕山大學(xué)計算數(shù)學(xué)系 河北秦皇島066004;2.燕山大學(xué)管理科學(xué)與工程系 河北秦皇島066004)

，即增廣流體模型弱不穩(wěn)定．必要性證

0 引言

排隊網(wǎng)絡(luò)服務(wù)顧客的效率高低與排隊網(wǎng)絡(luò)是否穩(wěn)定密切相關(guān)，而排隊網(wǎng)絡(luò)收益與排隊網(wǎng)絡(luò)服務(wù)顧客的效率也是密切相關(guān)的，因此排隊網(wǎng)絡(luò)的穩(wěn)定性問題倍受關(guān)注．許多學(xué)者對具有多個顧客類的排隊網(wǎng)絡(luò)的穩(wěn)定性問題進(jìn)行了研究，如文獻(xiàn)［1-2］得出了具有多個顧客類的排隊網(wǎng)絡(luò)穩(wěn)定的充分條件，其主要條件是排隊網(wǎng)絡(luò)相應(yīng)的流體模型穩(wěn)定．一些學(xué)者對每個服務(wù)站具有單服務(wù)臺的排隊網(wǎng)絡(luò)的穩(wěn)定性問題進(jìn)行了研究，如文獻(xiàn)［3］中每個到達(dá)者隨機選取兩個服務(wù)臺，然后加入較短的隊列，得到了隊長的漸近分布存在的充分條件．文獻(xiàn)［4］得到隊長過程正常返的充分條件．文獻(xiàn)［5］中到達(dá)間隔時間和服務(wù)時間都服從一般分布，當(dāng)J=2時通過流體模型得到了一個排隊網(wǎng)絡(luò)穩(wěn)定的充要條件以及一個排隊網(wǎng)絡(luò)不穩(wěn)定的充分條件．一些學(xué)者對每個服務(wù)站具有多服務(wù)臺的排隊網(wǎng)絡(luò)的穩(wěn)定性問題進(jìn)行了研究，如文獻(xiàn)［6］研究了具有J個服務(wù)站且每個服務(wù)站都具有N個服務(wù)臺的排隊網(wǎng)絡(luò)，到達(dá)間隔時間和服務(wù)時間都服從指數(shù)分布，一個突出的特點是出現(xiàn)了檢驗數(shù)分布的概念．每個到達(dá)者和每個接受完服務(wù)但仍留在網(wǎng)絡(luò)的顧客都要加入到一個服務(wù)臺集(樣本)中的某個最短隊列，得到了q過程和r過程正常返的充分條件和必要條件．與文獻(xiàn)［6］中模型不同的是，文獻(xiàn)［7］的模型中每個到達(dá)者選取的樣本所包含的服務(wù)臺數(shù)不變;而文獻(xiàn)［8-9］的模型中外部到達(dá)過程與服務(wù)站相關(guān)，而不是與檢驗數(shù)分布相關(guān)，通過流體模型得到在一些假設(shè)下流體逼近存在．文獻(xiàn)［10］研究的是具有K個更新到達(dá)流和N個服務(wù)臺的JSQ(進(jìn)入最短隊列)網(wǎng)絡(luò)，每個到達(dá)者進(jìn)入選擇集(服務(wù)臺集)中具有最短隊列的服務(wù)臺前排隊，而且每個顧客的服務(wù)時間服從一般分布，而本文中每個到達(dá)者在哪個服務(wù)臺前排隊是與檢驗數(shù)分布有關(guān)的，并且到達(dá)流都是泊松到達(dá)流，每個顧客的服務(wù)時間服從指數(shù)分布．綜上所述，對于具有負(fù)載平衡動態(tài)路由選擇的網(wǎng)絡(luò)的穩(wěn)定性研究尚不多見．

鑒于此，作者在文獻(xiàn)［5-6］的研究基礎(chǔ)上，對每個服務(wù)站具有多服務(wù)臺、出現(xiàn)了檢驗數(shù)分布的概念、每個到達(dá)者和每個接受完服務(wù)但仍留在網(wǎng)絡(luò)的顧客都要加入到一個服務(wù)臺集(樣本)中的某個最短隊列，即利用概率知識對具有負(fù)載平衡動態(tài)路由選擇的排隊網(wǎng)絡(luò)的穩(wěn)定性問題進(jìn)行了隨機分析，所用的方法與文獻(xiàn)［11］類似．

1 預(yù)備知識

首先介紹負(fù)載平衡模型并給出模型的假設(shè)．

定義1 對于任意的θ∈Θ，存在一個相應(yīng)的具有到達(dá)時間序列{ξθ(n):n≥1}的外部到達(dá)過程，被稱為θ型外部到達(dá)過程．

假設(shè)每個服務(wù)臺都是非閑置的和每個服務(wù)臺的服務(wù)規(guī)則都是先進(jìn)先出．由于θ型外部到達(dá)過程，第1個顧客到達(dá)的時刻為 ξθ(1);第 n － 1、n個顧客的到達(dá)時間間隔為 ξθ(n)，n≥2．ηi，k(n)，n≥1 表示被服務(wù)臺(i，k)服務(wù)的第n個顧客的服務(wù)時間．假設(shè)對任意的θ∈Θ都有{ξθ(n):n≥1}獨立且同分布;對任意的(i，k)∈C都有{ηi，k(n):n≥1}獨立同分布;所有到達(dá)間隔時間序列和所有服務(wù)時間序列都相互獨立．若A為集合，則表示A中元素的個數(shù);若y為向量，則表示y的1范數(shù)．JSQ表示加入最短隊列，并且排隊網(wǎng)絡(luò)簡稱為網(wǎng)絡(luò)．

以下介紹網(wǎng)絡(luò)狀態(tài)和網(wǎng)絡(luò)過程．

用 X(t)=(Z(t)，U(t)，V(t))表示網(wǎng)絡(luò)在 t時刻的狀態(tài)，其中，Z(t)={Zi，k(t):(i，k)∈ C}，U(t)={Uθ(t):θ∈ Θ}，V(t)={Vi，k(t):(i，k)∈ C}．Zi，k(t)表示 t時刻服務(wù)臺(i，k)的隊長;Uθ(t)表示 t時刻 θ型外部到達(dá)過程的剩余到達(dá)間隔時間;Vi，k(t)表示(i，k)服務(wù)臺中正在服務(wù)的顧客在t時刻的剩余服務(wù)時間，則狀態(tài)空間S為R2NJ+|Θ|的子集．假設(shè)網(wǎng)絡(luò)過程X={X(t):t≥0}右連續(xù)且具有左極限，則由文獻(xiàn)［1］的命題2．1可知，X是強馬爾可夫過程．

2 流體模型

先給出描述JSQ網(wǎng)絡(luò)動態(tài)行為的關(guān)系式組．

用 Ai，k(t)表示［0，t］中外部和內(nèi)部到達(dá)服務(wù)站 i中并要被服務(wù)臺(i，k)服務(wù)的顧客數(shù);Eθ(t)表示［0，t］中由于θ型外部到達(dá)過程而從網(wǎng)絡(luò)外部到達(dá)的顧客數(shù);Di(t)表示［0，t］中服務(wù)站i上接受完服務(wù)的顧客數(shù);Ti，k(t)，Ii，k(t)分別表示［0，t］中服務(wù)臺(i，k)的工作時間積累和空閑時間積累;Si，k(t)表示服務(wù)臺(i，k)花費t單位時間服務(wù)完的顧客數(shù);Φi，θ(n)表示從服務(wù)站i上離去的前n個顧客獲得檢驗數(shù)分布θ的個數(shù)．當(dāng)(i，k)∈C及t≥0時，描述JSQ網(wǎng)絡(luò)的動態(tài)如下:

因為Si，k(Ti，k(t))表示在［0，t］中服務(wù)臺(i，k)服務(wù)完的顧客數(shù)，Ai，k(t)表示［0，t］中外部和內(nèi)部到達(dá)服務(wù)站i中并要被服務(wù)臺(i，k)服務(wù)的顧客數(shù)，所以有

因為t時刻服務(wù)臺(i，k)的隊長至少為空，所以有

因為 Ti，k(t)，Ii，k(t)分別表示［0，t］內(nèi)服務(wù)臺(i，k)的工作時間積累和空閑時間積累，所以有

因為服務(wù)臺(i，k)都是非閑置的，所以有

如果對任意的 u∈ (s，t)都有 Zi，k(u)＞ 0，則

因為Si，k(Ti，k(t))表示在「0，t■內(nèi)服務(wù)臺(i，k)服務(wù)完的顧客數(shù)，Di(t)表示［0，t］內(nèi)服務(wù)站i上接受完服務(wù)的顧客數(shù)，所以有

如果 Μ ?J，0≤s≤t且對任意的k，l=1，2，…，N，i∈ Μ，j∈J－ Μ，及u∈(s，t)都有Zi，k(u)＞Zj，l(u)，則有

式(7)和(8)執(zhí)行了顧客的JSQ路由選擇行為．

下面介紹流體極限的概念，先給出一個引理．

證明 因為{ξθ(n)，n≥1}，θ∈Θ是獨立同分布隨機變量序列

由文獻(xiàn)［1］的定理4．1，給出了流體極限的定義．

定義2 對任意一個滿足(9)～(11)的ω及任意一個使得{xr/r:r＞0}有界的初始狀態(tài)集{xr:r＞0}，必存在一個子序列rn→∞ 使得在［0，∞)的任意一個緊集上都一致收斂到=(·)，(·)，(·)，(·))，則稱為流體極限．

因為a．s．是幾乎必然的意思，所以(9)成立;同理，(10)成立．

其中，xr=(zr，ur，vr)，則稱為無延遲的流體極限．

根據(jù)文獻(xiàn)［12］知，如果利用流體極限來研究網(wǎng)絡(luò)的穩(wěn)定性問題，則只需考慮無延遲的流體極限．

為了獲得流體模型關(guān)系式組，先給出引理2．

式(13)～(19)為流體模型關(guān)系式組，其解稱為流體模型的解．都 Lipschitz連續(xù)以及(13)～ (19)成立即可，在文獻(xiàn)［2］中可以找到另外兩個要證的結(jié)論．設(shè)ω滿足(9)～(11)，則可以選取xr的子序列xrn使得對某個(·)，在非負(fù)有理數(shù)集上恒有

證明 只需證明

同理可得

在先進(jìn)先出規(guī)則下，用 Γi，k(n)表示服務(wù)臺(i，k)服務(wù)完的前 n個顧客的服務(wù)時間之和，則恒有Γi，k(Si，k(Ti，k(t)))≤ Ti，k(t) ＜ Γi，k(Si，k(Ti，k(t))+1)，即

由(10)可知，對任意給定的ε＞0以及足夠大的n，(23)的最右邊項都小于等于

而對任意給定的ε＞0以及足夠大的n，(23)的最左邊項都大于等于

取n→∞，夾逼得

由(11)、(24)可知，當(dāng)n→∞ 時，

與上一段的證明類似，由(9)可知

所以當(dāng)(7)、(8)中 s→ t時，(18)、(19)成立．又因為(·)Lipschitz連續(xù)，所以(·)也 Lipschitz連續(xù)．如果選取一個子序列 rn使得(0)存在，由(1)、(24)和(27)可知因為(·)和(·)都Lipschitz連續(xù)，所以(·)也Lipschitz連續(xù)．由(1)、(2)、(24)、(27)以及(28)可知，(13)、(14)成立．當(dāng)(5)中 s→ t時，由(22)、(28)可知，(17)成立．引理2證畢．

下面給出流體模型穩(wěn)定和弱不穩(wěn)定的定義，為了將網(wǎng)絡(luò)和其相應(yīng)的流體模型聯(lián)系起來，給出了引理3和引理4．

引理3［1］如果流體模型穩(wěn)定，則馬爾可夫過程是Harris正常返的．

引理4［14］如果流體模型弱不穩(wěn)定，則馬爾可夫過程不穩(wěn)定，即對每個固定的初始狀態(tài)x，當(dāng)t→∞時都以概率1收斂到無窮．

3 增廣流體模型

其中，Ρx－a．s．表示初始狀態(tài)為x時以概率1收斂．所以對每個具有固定的初始狀態(tài)的流體極限，都有

現(xiàn)選擇一個緊集K?S，使得 π(K)=∫SΡ(z，u，v)(X(t)∈ K)dπ(z，u，v)＞ 0，t≥0．因為對任意的 x ＞ 0，都有 Ρ(ξθ(1)≥ x)=1 － Ρ，所以存在一個 t0＞ 0，使得對任意的(z，u，v)∈ K 都有 Ρ(z，u，．因此有

故由(30)得到(29)．引理5證畢．

式(13)～(19)及式(29)為增廣流體模型關(guān)系式組，其解稱為增廣流體模型的解．

引理6對證明馬氏過程不是Harris正常返非常有用，因為只需要證明增廣流體模型弱不穩(wěn)定即可．

4 主要結(jié)果

文獻(xiàn)［5］研究的是單服務(wù)臺情形，而作者研究的是至少具有兩個服務(wù)站、每個服務(wù)站至少具有兩個服務(wù)臺的情形;文獻(xiàn)［6］中服務(wù)強度恒為1，而作者研究的是服務(wù)強度與服務(wù)站有關(guān)，即文中的模型較文獻(xiàn)［5－6］復(fù)雜，所以通過假設(shè)1使得模型稍微簡單一些．

假設(shè)1 對任意一個 θ∈Θ，p*i，pi，θ都與i無關(guān)．對于 Μ?，令PΜ=PiΜ，假設(shè)p*＜1，p*=p*i，pθ=p，λ*= Λ ．i，θJ

證明 因為屬于同一服務(wù)站的服務(wù)臺對稱，所以Μ滿足(19)．由(19)有

將(32)減去(33)得

由(34)和(35)得

將(36)、(37)代入(33)得

由(13)、(37)有

將(38)代入(39)即可得到(31)．引理7證畢．

由引理7，對任意這樣的t，有

由(41)可知流體模型穩(wěn)定．由引理3可知充分性證畢．

再證必要性．根據(jù)引理6，只需證明如果(40)不成立，增廣流體模型則弱不穩(wěn)定．設(shè)存在Μ?J→使(40)不成立．設(shè)為一個具有(0)=0特點的增廣流體模型的解．

由(13)、(18)得

將(43)代入(42)，得

由(29)得

因為Μ使(40)不成立以及(44)，所以對所有的t≥0，都有

令畢．所以定理1證畢．

，即增廣流體模型弱不穩(wěn)定．必要性證

證明 由(13)、(18)得

在(19)中取 Μ =J，由(13)、(19)得

將(47)代入(46)，得

由引理8可知，對所有的t＞0有·f (t)＞ 0．從而f(t)＞ 0，因此對所有的t＞ 0，有 Z－(t) ＞0．故流體模型弱不穩(wěn)定，由引理4可知定理2得證．

［1］ Dai Jiangang.On the positive Harris recurrence of multiclass queueing networks:a unified approach via fluid limit models［J］.The Annals of Applied Probability，1995，5(1):49-77.

［2］ Maury B.Stability of Queueing Networks［M］.Berlin:Springer，2008:81-131.

［3］ Vvedenskaya N D，Dobrushin R L.Queueing system with the shortest of two queues:an asymptotic approach［J］.Problems of Information Transmission，1996，32(1):15-29.

［4］ Foley R D，Mcdonald D R.Join the shortest queue:stability and exact asymptotics［J］.The Annals of Applied Probability，2001，11(3):569-607.

［5］ Dai Jiangang，Hasenbein J J，Kim B.Stability of join-the-shortest-queue networks［J］.Queueing Systems，2007，57(4):129-145.

［6］ Suhov Y M，Vvedenskaya N D.Fast Jackson networks with dynamic routing［J］.Problems of Information Transmission，2002，38(2):136-153.

［7］ Martin J B，Suhov Y M.Fast Jackson networks［J］.The Annals of Applied Probability，1999，9(3):854-870.

［8］ 郭永江.每個節(jié)點具有多服務(wù)臺的Jackson網(wǎng)絡(luò)流體逼近的收斂速度［J］.系統(tǒng)科學(xué)與數(shù)學(xué)，2008，28(9):1118-1133.

［9］ Chen Hong.Fluid limits and diffusion approximations for networks of multi-server queue in heavy traffic［J］.Discrete Event Dymamic Systems，1994，4(3):269-291.

［10］ Bramson M.Stability of join the shortest queue networks［J］.The Annals of Applied Probability，2011，21(4):1568-1625.

［11］趙湘育，王東煒，張剛.網(wǎng)絡(luò)系統(tǒng)可靠度和單元概率重要度的隨機模擬分析［J］.鄭州大學(xué)學(xué)報:理學(xué)版，2009，41(4):108-111.

［12］ Bramson M.Stability of two families of queueing networks and a discussion of fluid limits［J］.Queueing Systems，1998，28(1/2/3):7-31.

［13］徐麗.函數(shù)列一致連續(xù)和一致收斂及等度連續(xù)的關(guān)系［J］.上海電力學(xué)院學(xué)報，2007，23(3):284-287.

［14］ Dai Jiangang.A fluid-limit model criterion for instability of multiclass queueing networks［J］.The Annals of Applied Probability，1996，6(3):751-757.