M/M/n模型的高負荷極限及仿真

摘 要： 通過對于標準的多服務臺隊列M/M/n模型的負荷過程的高負荷極限的證明來解釋鞅定理，該系統為泊松到達，指數服務。通過對所考慮的負荷過程進行流體刻畫，并且使用鞅方法來證明多服務臺隊列M/M/n模型的負荷過程的高負荷極限，并得到所考慮的負荷過程收斂的結論。在高負荷條件下使用Matlab編程對此過程進行仿真模擬，模擬仿真以產生隨機數的方式來進行計算，為今后排隊論中證明隨機過程（比如等待時間，流失過程，放棄過程等）的收斂提供了新的方法。

關鍵詞： 多服務臺隊列； 泊松到達； 指數服務； 高負荷極限

中圖分類號： TN911?34 文獻標識碼： A 文章編號： 1004?373X（2013）20?0011?03

排隊現象是日常生活中經常出現的情況，大家通過研究不同模型的隊長，負荷等指標獲得排隊系統的穩定性。鞅理論早在1939年就被前人提出[1]，Ward Whitt首先將鞅理論應用到排隊論中[2]，為不同模型的高負荷極限的證明提供了一種新的思路。

1 介 紹

本文的主要內容是對[M/M/n]模型[3]的負荷過程的高負荷極限的鞅的表達式做出推導和證明。這種理論關于今后對其高負荷極限的證明是非常有效的，但是也是非常困難的。因此，先考慮[M/M/n]模型，泊松到達，指數服務。

在此致力于研究[M/M/n]模型，令到達率為[λ]，服務率為[μ]。令[W（t）]為[t]時刻的負荷過程，初始時負荷為[0]。另外考慮到達率允許增加的情況，在第[n]個模型中的到達率可以表示為：

[λn≡nμ， n≥1] （1）

[Wn（t）]為[t]時刻第[n]個模型的負荷，現在建立整個負荷過程[{Wn（t）：t≥0}]當[n→∞]時的極限。現在，考慮刻畫過程[{Xn（t）：t≥0}]定義為：

[Xn（t）≡Wn（t）n， t≥0] （2）

假設初始時[Xn（0）?X（0）]當[n→∞]時，[Wn（0）]與到達過程和服務過程無關。且[{Xn（t）：t≥0}]在[D]空間上收斂。

2 QED規則下的多服務臺的高負荷極限

建立多服務臺馬爾可夫模型的高負荷極限[4]，在QED規則下考慮一系列多服務臺模型的高負荷極限，由條件[nμ-λnn→βμ，n→∞]給出。

3 樣本路徑結構

直接從隨機過程[W]的樣本路徑開始，然后基于輸入過程和服務時間來得出不同的結構。對于單位概率泊松過程的隨機時間改變，首先，用[C（t）]表示[[0，t]]內的累積輸入量，[S（t）]表示[[0，t]]內的累積服務量[3]。假設[{C（t）：t≥0}]和[{S（t）：t≥0}]為實值的有非負非降且右連續的樣本路徑的隨機過程。初始時系統的負荷為[W（0）]且[W（0）]是獨立于[C（t）]和[S（t）]的隨機變量。[C]是由概單位率的泊松過程刻畫的，速率為[λ]，令[Cλ（t）=C（λt），t≥0]，因此，[Cλ]是速率為[λ]的泊松過程；[S]是由單位概率的泊松過程刻畫的，速率為[μ]，令[Sμ（t）=S（μt），t≡0]，[Sμ]是速率為[μ]的泊松過程。[L（t）]為閑期，[X（t）]為潛在負荷過程，且[X（t）≡W（0）+Cλ（t）-Sμ（t），t≡0]，則：

4 鞅的表達式

4.1 鞅引用

定義1（[Ft]?鞅） 一個隨機過程[M={M（t）：t≥0}]在[σ]?域[F≡{Ft：t≡0}]上被稱為鞅：若[M（t）]為[Ft]?適應的，對于任意的[t≡0]有[E[M（t）]<∞]，并且對于任意的[t≡0]，[s>0]，[E[M（t+s）Ft]=M（t）]是依概率1成立的，若[E[M（t+s）Ft]≡M（t）]是依概率1成立的，則稱[M（t）]為下鞅[2]。

引理1（非負下鞅的Doob?Meyer分解定理） 若[Y]是具有非負樣本路徑的下鞅，對于任意的[t]有[E[Y（t）]<∞]，且[Y]對[σ]?域流[F={Ft}]是[F]?適應的，則存在一個[F]可預測過程[A]，稱為[Y]的補償，使得[A]具有非負非降樣本路徑，對于任意的[t]有[E[A（t）]<∞]，且[M≡Y-A]是一個[F]?鞅，其中[A]是惟一確定的[2]。

定義2（平方可積鞅） 對于適應某[σ]?域流的鞅[M={M（t）：t≥0}]，若任意[t≥0]，有[E[M（t）2]<∞]成立，則稱次鞅為平方可積鞅[2]。若[M]是一個平方可積鞅，則[M2={M（t）2：t≥0}]是一個具有非負樣本空間的下鞅，并且滿足[D-M]分解定理的條件。一個平方可積鞅的可預測平方變差寫為[M={M（t）：t≥0}]，是下鞅的補償，且[M2-M]是適應于某一合適的[σ]?域的鞅。

4.2 鞅表示

泊松過程[C（t）]，[S（t）]和新過程[C（λt）]，[S（μt）]都是具有非降非負樣本路徑，在合適的[σ]?域下，這些隨機過程都是下鞅，再減去補償就得到所要的鞅，通過這種方式所構造的鞅[M]將被證明是平方可積鞅，且滿足鞅表示[M2-M]。為了構造鞅表示，必須先考慮合適的[σ]?域[5][F={Ft：t≥0}]，其中[Ft≡σ（W（0），C（s），S（s）），t≥0]，包含所有零集。以下過程將被證明是[F]?鞅：

證明：由引理1及單位跳躍計數，可知這些條件滿足補償的定義，對于由停止定理[2]提供的單位概率泊松過程的隨機時間改變的PQV 定理，再由文獻[6]，運用鞅的停止定理及文獻[7]和文獻[8]中的結論可得。

5 結 論

考慮[Wn（t）]的刻畫過程：

6 證明定理1

證明：應用連續映射定理在刻畫的鞅表達式上，由隨機過程極限知刻畫的鞅弱收斂到獨立的布朗運動[（Mn，1（t），Mn，2（t））?（λB1，μB2）]，在[D2≡D×D]上， [n→∞]。[B1]，[B2]是兩個獨立的布朗運動。應用連續映射定理得[7]：

[Mn，1（t）-Mn，2（t）?λB1-μB2dλ+μB在D上，n→∞] （14）

[B]是一個單獨的標準布朗運動。然后運用函數[f：D×R→D]，由[（y，b）]決定[x]的連續映射定理來確定鞅表達式：

[x（t）=b+y（t）-inf0≤s≤t{[b+y（s）]∧0}，t≥0] （15）

式中：[y]可由[Mn，1-Mn，2]來表示；[b]可由[Xn（0）]給出。式（14）中的隨機過程有連續樣本路徑，[f：D×R→D]是可測的，在連續極限處連續。首先刻畫泊松過程：

[MC，n（t）≡C（nt）-ntn，MS，n（t）≡S（nt）-ntn，t≥0] （16）

將證明刻畫鞅弱收斂到獨立標準布朗運動：

[（Mn，1，Mn，2）?（λB1，μB2） 在D2上] （17）

定理2（獨立泊松過程的FCLT） 若[C]和[S]都是獨立的概率-1的泊松過程，那么在[D2≡D×D]上，[n→∞]：

[MC，nt，MS，nt?B1，B2] （18）

式中：[MC，n（t），MS，n（t）]是上述刻畫過程；[B1，B2]是標準布朗運動。可以證明式（17）的極限，現在介紹一個確定的和隨機的時間改變。為此，令[e（t）≡t，t≥0]。

由此：

[ΦC，n（t）≡λntn=λt≡（λe）（t）] （19）

[ΦS，n（t）≡μntn=μt≡（μe）（t），t≥0] （20）

將建立以下可被看做FWLLN的流體極限，已經依分布收斂到一個確定的極限。為此，建立一個流體極限，考慮隨機過程：

[ψS，n（t）≡Wn（t）n，t≥0] （21）

定理3（流體極限） 定義引理1的條件成立，則[2]：

[ΨS，n（t）?ωλ在D上，n→∞] （22）

式中[ω（t）=1，t≥0]。

定理4（所有流體極限的FCLT） 若條件（22）成立，則：

[Mn，1，Mn，2?λB1，μB2 在D2上] （23）

證明：由式（18）～式（20）及隨機過程極限中的定理可知：

[MC，nt，λe，MS，nt，μe）?B1，λe，B2，μe 在D4上] （24）

由連續映射定理及文獻[1]中的定理，可以得到：

[Mn，1，Mn，2≡MC，nt°λe，MS，nt°μe ?B1°λe，B2°μe 在D2上，n→∞] （25）

由布朗運動的基本性質可知：

[（B1°λe，B2°μe）d（λB1，μB2）]

那么在：

[Mn，1-Mn，2?λB1-μB2dλ+μB 在D上，n→∞] （26）

由此定理1得證。

7 模擬仿真

仿真是通過顧客信息矩陣及隊列信息矩陣來實現。仿真圖中的橫軸為時間，縱軸為負荷，由圖1可以看出取[t=800，t=1 000]時，負荷都趨于平穩，即仿真效果良好，結論與實際相符。

8 結 語

本文在前人研究的基礎上，對排隊系統中“負荷”指標做出鞅證明，并通過Matlab軟件做出模型仿真并加以分析。仿真結果表明，仿真效果良好，與實際相符。

參考文獻

[1] ROSS S M. 隨機過程[M].北京：中國統計出版社，1997.

[2] PANG Guo?dong， RISHI Talreja， WHITT Ward. Martingale proofs of many?server heavy?traffic limits for Markovian queues [M]. New York： Springer， 2007.

[3] WHITT Ward. Stochastic?process limits [M]. New York： Springer， 2002.

[4] ROGERS L C G， WILLIAMS D. Diffusions， Markov processes and martingales： Volume 2 [M]. Ito Calculus： Wiley， 1987.

[5] 嚴士健，王雋驤，劉秀芳.概率論基礎[M].北京：科學出版社，1982.

[6] MANDELBAUM A， PAT G. State?dependent stochastic networks [J]. Annals of Applied Probability， 1998， 8（2）： 569?646.

[7] KHOSHNEVISAN D. Multiparameter processes： an introduction on random fields [M]. New York： Springer， 2002.

[8] DALEY D J， VERE?JONES D. An introduction to the theory of point processes [M]. New York： Springer， 2003.

[9] PATRICK Billingsley. Convergence of probability measures [M]. Chicago： Wiley?Interscience Publication， 1999.