周宗好， 朱翼雋， 石志巖

(1.黃山學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院，安徽 黃山245041;2.江蘇大學(xué)理學(xué)院，江蘇 鎮(zhèn)江212013)

0 引 言

在現(xiàn)代通信網(wǎng)絡(luò)中，一種有效的建模方式就是假設(shè)信息到達(dá)為馬爾科夫過程，能夠很好的描述到達(dá)過程的突發(fā)性和周期性，它包括了泊松過程、PH更新過程及調(diào)制的泊松過程(Markov Modulated Poisson Process，MMPP)等［1-2］.

在經(jīng)典的排隊系統(tǒng)中總是假設(shè)服務(wù)臺不會發(fā)生故障的，這顯然不符合現(xiàn)實的. 實際上服務(wù)臺總是受一些不可預(yù)測的因素影響而發(fā)生故障不能工作，例如在通信網(wǎng)絡(luò)中，信號的中斷、線路損壞等因素都導(dǎo)致信道不可用，都稱之為故障. 因此，文獻(xiàn)［3，4］研究了M/G/1 可修排隊系統(tǒng)，并且朱翼雋等［5］帶重試策略的可修排隊系統(tǒng)的詳細(xì)的可靠性指標(biāo).但是故障的到達(dá)類似于系統(tǒng)信息流的到達(dá)一樣，到達(dá)過程不是泊松流能精確描述的，而上面提到的文獻(xiàn)都是假設(shè)故障到達(dá)間隔時間分布是指數(shù)分布.因此，對帶有馬爾科夫故障流與泊松故障流排隊系統(tǒng)的性能比較研究顯得具有重要的意義了.

對于可修系統(tǒng)的維護(hù)策略已經(jīng)被廣泛的研究［6～7］，例如有故障修理、元件替換和定期維修等，但是對于通信系統(tǒng)來說，為了維持通信的即時性和服務(wù)質(zhì)量，采用備用一定數(shù)量的服務(wù)臺替換因故障不能工作的服務(wù)臺是提高服務(wù)質(zhì)量提高效率的重要方法.因此本文中我們考慮服務(wù)臺數(shù)量為無限的數(shù)據(jù)包到達(dá)是Markov 流的排隊模型.

1 模型描述

考慮數(shù)據(jù)包到達(dá)流為Markov 流，服務(wù)臺對信息服務(wù)時間為指數(shù)分布的MAP/M/c 可修排隊系統(tǒng)，系統(tǒng)有k 個等待位置的緩沖器且故障到達(dá)為Markov 流，c 個服務(wù)臺處于工作狀態(tài)，備用服務(wù)臺數(shù)目為無限.當(dāng)工作狀態(tài)的服務(wù)臺一旦發(fā)生故障，則備用的服務(wù)臺立即替代工作，發(fā)生故障的服務(wù)臺進(jìn)入等待修理的隊列，按先到先服務(wù)規(guī)則等待修理，并且假定系統(tǒng)只有一個修理工. 服務(wù)臺的故障到達(dá)流為馬爾科夫過程MAP1，它的有J1× J1維隱馬爾科夫鏈J1(t)、矩陣表示(C0，C1)、生成元矩陣C(1)= C0+ C1以及1 × J1維的穩(wěn)態(tài)概率向量θ1和到達(dá)率分別為λ1= θ1C(1)eJ1.

數(shù)據(jù)包的到達(dá)流為馬爾科夫過程MAP2，它的有J2× J2維隱馬爾科夫鏈J2(t)、矩陣表示(D0，D1)、生成元矩陣D(1)= D0+ D1以及1 × J2維的穩(wěn)態(tài)概率向量θ2和到達(dá)率λ2= θ2D(1)eJ2.到達(dá)的數(shù)據(jù)包如果發(fā)現(xiàn)在崗的個服務(wù)臺全部被占則進(jìn)入緩沖器，如果緩沖器的位置也全部被占，則其離開系統(tǒng)，即數(shù)據(jù)包丟失. 數(shù)據(jù)包的服務(wù)時間和服務(wù)臺的修理時間分別服從參數(shù)為μ1和μ2的指數(shù)分布.故障的到達(dá)過程MAP1、數(shù)據(jù)包的到達(dá)過程MAP2、數(shù)據(jù)包的服務(wù)時間及服務(wù)修理時間是相互獨立的.

2 生成元矩陣

馬爾科夫過程ζ(t)= {X1(t)，X2(t)，J1(t)，J2(t)}的狀態(tài)空間為:

按字典序排列馬爾科夫鏈{ζt，t ≥0}的狀態(tài)空間S的元素，可得其生成元矩陣Q 具有QBD 結(jié)構(gòu)為:

這里的矩陣塊A0，A，B，C 分別為:

把上面方程(1)～(3)按k = 0，1，…，K 相加，得到:

又因為C(1)⊕D(1)不變向量的唯一性和πe =1，可以得到:

因此可以得到下列定理:

定理1 具有生成元矩陣Q 的馬爾科夫過程{ζt，t ≥0}是正常返的充要條件是:ρ = λ1/μ1＜1.證明: 因為馬爾科夫過程{ζt，t ≥0}的生成元矩陣具有QBD 結(jié)構(gòu)，由文獻(xiàn)［8］知道它的正常返的充要條件是πCeJ1J2＜πBeJ1J2，因此我們計算得:

設(shè)在穩(wěn)態(tài)條件下，具有生成元矩陣Q 系統(tǒng)的穩(wěn)態(tài)概率向量為ˉ且，因此我們可以得到下列定理:

定理2 馬爾科夫過程{ζt，t ≥0}存在唯一的穩(wěn)態(tài)概率向量ˉx 滿足ˉxQ2= 0，ˉxe∞= 1.其元素為:

其中，向量x(0)由下列矩陣方程給出:

這里的率陣R 是矩陣方程R2B+RA+C = 0 的最小非負(fù)解，它的譜半徑SP(R)＜1，由文獻(xiàn)［8］知道R 是矩陣序列{R(n)，n ≥0}的極限= R，其中矩陣序列的按下列方法確定的:

率陣 R 的迭代計算直到滿足不等式maxi，j［Ri，j(n + 1)- Ri，j(n)］ ＜ ε 為 止. 這 里Ri，j(n)是矩陣R(n)第i 行、第j 列的元素，ε 為迭代計算的精度.

3 系統(tǒng)排隊指標(biāo)

系統(tǒng)中恰有k 個數(shù)據(jù)包在等待服務(wù)的概率為:

系統(tǒng)中等待服務(wù)數(shù)據(jù)包的平均對長為:

4 服務(wù)臺的可靠性指標(biāo)

服務(wù)臺的可用度:

服務(wù)臺的故障頻度:

系統(tǒng)中等待修理的服務(wù)臺的平均對長為:

5 數(shù)值例子

在本節(jié)用兩個例子來計算模型的服務(wù)臺的可靠度和故障頻度，主要是為了說明備用服務(wù)臺數(shù)目對系統(tǒng)指標(biāo)的影響.

例1 設(shè)μ1= μ2= 1，2.馬爾科夫過程MAP2定義為:

先引入馬爾科夫過程MAP2的相關(guān)系數(shù)ccor的概念［2］:

由此可以計算得到上面的馬爾科夫過程MAP2的相關(guān)系數(shù)ccor= 0.05，并且記為MAP2(0.05).馬爾科夫過程MAP1被定義為MAP1(0.06)，其形式如下:

從表1 中，我們可以看出模型的穩(wěn)態(tài)概率向量ˉx(i，k)隨等待位置K 的變化情況，從數(shù)據(jù)上可以看出穩(wěn)態(tài)條件下，系統(tǒng)的概率向量ˉx(i，k)受等待位置K 的變影響較小.

例2 在這個例子中，馬爾科夫過程MAP2被定義為MAP2(0.1)，其矩陣表示為:

馬爾科夫過程MAP1分別用下列五個到達(dá)過程表示:

1.指數(shù)分布(EXP):C0= ˉc(-1);C1= ˉc(1)

2. 超指數(shù)分布(HEX):

3. 愛爾朗分布(ERL):

表1 當(dāng)μ1 = μ2 = 1.2 時，x(i，k)的值

5. MAP1(0.2):

圖1 故障流到達(dá)率λ1 與平均隊長E［N1］與關(guān)系圖

圖1是反映模型的性能指標(biāo)隨故障流的基礎(chǔ)到達(dá)率λ1的變化情況，我們可以得到下列重要的結(jié)論:模型性能指標(biāo)(數(shù)據(jù)包的受阻率Pb、數(shù)據(jù)包的平均隊長E［N2］和故障服務(wù)臺的平均隊長E［N1］)隨故障流的基礎(chǔ)到達(dá)率λ1的增加而迅速增加;進(jìn)一步可以看出，不同的到達(dá)流對這些指標(biāo)的影響也是非常大的，其中，愛爾朗到達(dá)流引起的數(shù)據(jù)包擁塞最小，而相關(guān)系數(shù)越大的馬爾科夫流引起的數(shù)據(jù)包擁塞越大.

6 結(jié) 論

考慮到隨著通信網(wǎng)絡(luò)的發(fā)展，網(wǎng)絡(luò)中的數(shù)據(jù)包(包括語音呼叫、文字信息、圖片等數(shù)據(jù)業(yè)務(wù))往往具有爆發(fā)性和周期性，用傳統(tǒng)的泊松流是不能完全的刻畫網(wǎng)絡(luò)信息流的特性.本文采用馬爾科夫數(shù)據(jù)包到達(dá)流和故障到達(dá)流替代傳統(tǒng)的泊松流，通過比較分析發(fā)現(xiàn)兩者對系統(tǒng)性能指標(biāo)影響差距很大，因此，本模型為建立更精確的排隊模型提供一定理論依據(jù).

［1］ W. Joris，S. Bart，B. Herwing.Performance Analysis of a Single ATM Queue with a Priority Scheduling［J］.Computer ＆ Operational Research，2003，30 (12):1807 -1829.

［2］ J. R. Artalejo，S. R. Chakravarthy. Computational Analysis of the Maximal Queue Length in the MAP/M/c Retrial Queue［J］.Applied Mathematics and Computation，2006，183(2):1399 -1409.

［3］ C. Gautam，T. Lotfi.An M/G/1 Queue with Two Phases of Service Subject to the Server Breakdown and Delayed Repair［J］. Applied Mathematical Modelling，2009，33 (6):2699 -2709.

［4］ A. B. Khalid，D. Alexander，K. Arseniy，Y. Suleimen.Investigation of the M2/G2/2/∞N Queue with Restricted Admission of Priority Customers and its Application to HSDPA Mobile Systems［J］.Computer Networks，2009，53(8):1186 -1201.

［5］ 朱翼雋，周宗好，馮艷剛.具有優(yōu)先權(quán)的M/G/1 重試可修排隊系統(tǒng)［J］.自動化學(xué)報，2008 34:195 -201.

［6］ Z. M. Liu，J. B. Wu，G. Yang.An M/G/1 Retrial G-queue with Preemptive Resume and Feedback under N -policy Subject to the Server Breakdowns and Repairs［J］. Computers ＆ Mathematics with Applications，2009，58(9):1792 -1807.

［7］ P. O. Rafaek，M. C. Delia. A Multiple System Governed by a Quasi-birth - and - death Process［J］. Reliability Engineering and System Safety，2004，84 (2):187 -196.

［8］ M. F. Neuts. Matrix - geometric Solutions inStochastic Models［M］. Baltimore:The Johns Hopkins University Press，1981:1-40.