高负荷条件下G-网扩散逼近的鞅方法
|
摘要
随着1991年Gelenb首次提出“负顾客”的概念,带有正顾客和“负顾客”的G-网络得到了广大学者的关注。近年来,人们从不同的角度对G-网也做出了大量的研究,其主要应用在神经网络系统、遗传学管理系统、电脑安全系统等。1939年,法国概率学家Levy首先提出了鞅的概念,此后美国概率学家Doob将鞅的概念进行了推广,提出了下鞅的概念,并对它做了很多系统性的研究。Burkholder D.L.,Meyer P.等在此基础之上,又进行了一系列的研究工作,从而就形成了近代鞅理论。随着鞅理论在概率论和随机过程中地位的日益突出,鞅方法已经成为研究随机过程和排队论的强有力工具。在本篇文章中主要运用鞅方法来研究高负荷条件下G-网队长过程的扩散逼近。我们首先给出鞅的有关知识,并在此基础之上应用非负下鞅的Doob-Meyer分解定理构造出两类特殊的G-网模型：二阶串联系统和二阶并联系统队长过程的鞅分解表示,进而给出其刻画过程的鞅分解表示,然后再运用概率测度收敛和随机过程极限的有关知识来研究其扩散逼近过程。并且将其结论推广到一般G-网模型,给出一般G-网模型中队长过程在高负荷条件下的扩散逼近过程,表明了鞅方法在研究G-网模型时的可行性和有效性。在本篇论文的最后一章也将给出二阶串联系统队长过程的数值模拟仿真,并画出其图像,验证了二阶串联系统的高负荷极限定理。
The concept of 'negative customer' was introduced for the first time in 1991, from then on, the G-networks with positive customers and 'negative customers' became the focus of the scholars. In recent years, G-networks have been extensively studied from different directions, including neural network modeling, computer networks, genetic regulatory systems, and so on. In 1939, the probability of scientist Levy gave the concept of martingale. Then Doob developed that concept, and introduced the concept of sub-martingale. Based on that, Burkholder D.L. and Meyer P. made a series of studies, contributing to the formation of the modern martingale theory. With the increasingly prominent status of martingale theory in probability and stochastic processes, martingale method has become a powerful tool in stochastic processes and queuing theory. In this paper, we study in the diffusion approximation of state-dependent G-networks under heavy traffic. At first, we we'd like to give the associated knowledge of martingale. And using Doob-Meyer decomposition for nonnegative sub-martingales, we construct the martingale decomposition of two types of networks, including two queues in tandem and two-layer network. Then we will present the martingale representation for the scaled queuelength processes. On that basis, we want to study the diffusion approximation processes of queuelength processes in the two models, using the knowledge in convergence of probability measures and stochastic-process limits. What's more, we will present the heavy-traffic limits of queuelength process, which applies the conclusions of the two special models. According to that, we show the feasibility and validity of the martingale method in queuing network. At the last chapter of this paper, we will simulate the queuelength process in the model of two queues in tandem and draw the images, which verifies the heavy traffic limit theorem of two queues in tandem.
The concept of 'negative customer' was introduced for the first time in 1991, from then on, the G-networks with positive customers and 'negative customers' became the focus of the scholars. In recent years, G-networks have been extensively studied from different directions, including neural network modeling, computer networks, genetic regulatory systems, and so on. In 1939, the probability of scientist Levy gave the concept of martingale. Then Doob developed that concept, and introduced the concept of sub-martingale. Based on that, Burkholder D.L. and Meyer P. made a series of studies, contributing to the formation of the modern martingale theory. With the increasingly prominent status of martingale theory in probability and stochastic processes, martingale method has become a powerful tool in stochastic processes and queuing theory. In this paper, we study in the diffusion approximation of state-dependent G-networks under heavy traffic. At first, we we'd like to give the associated knowledge of martingale. And using Doob-Meyer decomposition for nonnegative sub-martingales, we construct the martingale decomposition of two types of networks, including two queues in tandem and two-layer network. Then we will present the martingale representation for the scaled queuelength processes. On that basis, we want to study the diffusion approximation processes of queuelength processes in the two models, using the knowledge in convergence of probability measures and stochastic-process limits. What's more, we will present the heavy-traffic limits of queuelength process, which applies the conclusions of the two special models. According to that, we show the feasibility and validity of the martingale method in queuing network. At the last chapter of this paper, we will simulate the queuelength process in the model of two queues in tandem and draw the images, which verifies the heavy traffic limit theorem of two queues in tandem.
引文
[1]Gelenbe E. Product-form queueing networks with negative and positive customers [J]. Appl.Prob.,1991,28:656-663
[2]Gelenbe E. G-networks with triggered cumstomer movement [J]. Appl.Prob.,1993,30: 742-748
[3]Chao X. and Pinedo M. On generalized networks of queues with positive and negative arrivals [J].Prob Eng Inf Sci.,1993,7:301-334
[4]Chao X. Networks of queues with customers, signals and arbitrary service time distributions [J].Operations Research,1995,43:537-550
[5]Gelenbe E. G-networks with signals and batch removal[J].Prob Eng Inf Sci.,1993,7:335-7:335-342
[6]Henderson W. Queueing networks with negative customers and negative queueing lengths [J].Appl.Prob.,1993,30:931-942
[7]Gelenbe E. G-networks:A unifying model for neural and queueing networks [J].Annals of Operations Research,1994,48:433-461
[8]Boucherie R J. and Van Dijk N M.Local balances in queueing networks with positive and negative customers [J].Annals of Operations Research,1994,48:463-492
[9]Chao X. and Pinnedo M. Networks of queues with batch services signals and product form solutions [J].Operations Research Letters,1995,18:237-242
[10]Fourneau J.M., Gelenbe E. and Suros R. G-networks with multiple classes of negative and positive customers[J].Theoretical computer science,1996,155:141-156
[11]Chao X. A queueing network model with catastrophes and product form solution [J]. Operations Research,1995,18:75-79
[12]Gelenbe E. and Fourneau. G-networks with resets [J].Performance Evaluation,2002,12: 179-191
[13]Gelenbe E. and Schassberger R. Stability of product form G-networks [J]. Prob Eng Inf Sci.,1992,6:271-276
[14]Gomez-Corra A. and Martos E. Performance of two-stage tandem queues with blocking: the impact of several flows of signals[J]. Performance Evaluation,2006,63:910-938
[15]Gomez-Corra A.On a tandem G-network with blocking [J]. Adv. Appl. Prob.,2002,34: 626-661
[16]Leite S.C. and Fragoso M.D. On the analysis of G-queues under heavy traffic[J]. Proceeding Proceedings of the 47th IEEE Conference on Decision and Control Cancum, 2008,9-11
[17]Harrison P.G. Compositional reversed Markov processes with applications to G-networks[J]. Performance Evaluation,2004,57:379-408
[18]Harrison P.G. and Pitel E. The M/G/l queue with negative customers[J]. Adv.Appl.Prob., 1996,28:540-566
[19]Gelenbe E. Random neural networks with negative and positive signals and product form solution[J].Neural Computation,1989,1:502-511
[20]Atalay V. and Gelenbe E. Parallel algorithm for color texture generation using the random neural network model[J].Pattern Recognition Artificial Intelligence,1992,6: 437-446
[21]Atalay V., Gelenbe E. and Yalabik N. The random neural network model for texture generation[J]. Pattern Recognition Artificial Intelligence,1992,6:131-141
[22]Artalejo J.R. G-networks:a versatile approach for work removal in queueing networks [J].Europ.Operat.Res.,2000,126:233-249
[23]Arazi A.,Ben-Jacob E. and Yechiali U. Bridging genetic networks and queueing theory [J]. Math.Meth.Operat.Res.,2005,62:453-466
[24]Gelenbe E. Steady-state solution of probabilistic gene regulatory networks[J].Phy.Rev.E., 2007,76:031903(8)
[25]朱翼隽,陈燕.负顾客排队系统的研究进展[J].江苏大学学报(自然科学版),2004,25(1)：48-51
[26]Levy P. Theorie de I.Addition des Variables Aleatoires Gauthier-Villars.Pairs,1939,20-36.
[27]Doob J.L. Stochastic Processes.John Wiley and Sons[J].Inc.,1953,1-5
[28]Bremaud P. Point Processes and Queues Martingale Dynamics[M]. New York: Springer,1981,122-155
[29]Iglehart D.L. Limit diffusion approximations for the many server queue and the repairman problem[J]. Adv.Appl.Prob.,1965,2:429-441
[30]Borovkov A. A. On limit laws for service processes in multi-channel systems (in Russian) [J].Siberian Math,1967,8:746-763.
[31]Borovkov A.A. Asymptotic methods in queueing theory[M]. New York:Wiley,1984, MR0745620
[32]Whitt W. On the heavy-traffic limit theorem for GI/G/∞ queues[J].Adv.Appl.Prob., 1982,14:171-190.
[33]Glynn P.W. and Whitt W. A new view of the heavy-traffic limit theorem for the infinite-server queue[J]. Adv.Appl.Prob.,1991,23:188-209
[34]Massey W.A. and Whitt W. Networks of infinite-server queue with nonstationary Poisson input[J].Queueing systems,1993,13:183-250.
[35]Mandelbaum A. and Pats G.. State-dependent queues:approximations and applications.In Stochastic Networks,F.P.Kelly,R.J.Williams,Institute for Mathematics and its Applica-tions,Vol.New York:Springer,1995,71:239-282.
[36]Mandelbaum A. and Pats G. State-dependent stochastic networks.Part I:Applications and Applications with continuous diffusion limits[J].Ann.Appl.Prob.,1998,8:569-646.
[37]Puhalskii A.A. andReiman M.I. The multiclass GI/PH/N queue in the Halfin-Whitt regime[J]. Adv.Appl.Prob.,2000,32:564-595.
[38]Whitt W. Heavy-traffic limits for the G/H2*/n/m queue[J]. Math.Oper.Res.,2005,30:1-27
[39]Kogan T., Liptser R.Sh. and Smorodinskii A.V. Gaussian diffusion approxima- tions of closed Markov models of computer networks[J]. Problems.Inform.Transmission,1986, 22:38-51
[40]Liptser R.Sh. and Shiryayev A.N. Theory of Martingales[M].Netherlands:Kluwer,1989, (English translation of 1986 Russian edition)
[41]Kurtz T. Representations of Markov processes as multiparameter time changes[J].Ann. Probability,1980,8:682-715
[42]Ethier S.N. and Kurtz T.G. Markov processes:characterization and convergence[M]. New York:Wiley,1986, MR0838085
[43]严加安.鞅与随机积分引论[M].上海出版社,1981,96-103
[44]王梓坤.随机过程论[M].北京：科学出版社,1978,48-59
[45]王寿仁.概率论基础与随机过程[M].北京：科学出版社,1997,18-24
[46]Guodong pang, Rishi Talreja and Whitt W. Martingale proofs of many-Server heavy-traffic limits for Markovian queues[J]. Probability Surveys,2007, Vol(4):193-267
[47]Karatzas and Shreve S. Brownian motion and stochastic calculus[M]. New York: Springer,1988, MR0917065
[48]Mandelbaum A., Massey W.A. and Reiman M.I. Strong approximations for Markovian sercice networks[J]. Queueing systems,1998,30:149-201
[49]Jacod J. and Shiryayev A.N. Limit theorems for stochastic processes[M]. New York: Springer,1987, MR0959133
[50]Khoshnevisan D. Multiparameter processes:an introduction to random fields[M]. New York:Springer,2002,MR1914748
[51]Daley D.J. and Vere-Jones D. An introduction to the theory of point processes[M]. New York:Springer,2003:325-386
[52]Rebolledo R. Central limit theorems for local martingales[J]. Zeitschirift Wahrscheinlich-keitstheorie verw,1980,51:269-286
[53]Whitt W. Proof of the martingale functional central limit theorem[J]. Probability Surveys, 2007,4:268-302
[54]Rogers L.C.G. and Williams D. Diffusions, Markov processes and martingales.Volume 2: Ito Calculus[M]. New York:Wiley,1987, MR0921238
[55]Vander A.W. Martingales,diffusions and financial mathematics lecture note.2006, Available at:https://www.math.vu.nl/sto/onderwijs/mdfm/
[56]Leite S.C. and Marcelo D.F. Diffusion approximation of state-dependent G-networks under heavy traffic[J]. Adv.Appl.Prob.,2008,45:347-362
[57]Kushner H.J. Heavy traffic analysis of controlled queueing and communication networks[M]. New York:Springer,2001
[2]Gelenbe E. G-networks with triggered cumstomer movement [J]. Appl.Prob.,1993,30: 742-748
[3]Chao X. and Pinedo M. On generalized networks of queues with positive and negative arrivals [J].Prob Eng Inf Sci.,1993,7:301-334
[4]Chao X. Networks of queues with customers, signals and arbitrary service time distributions [J].Operations Research,1995,43:537-550
[5]Gelenbe E. G-networks with signals and batch removal[J].Prob Eng Inf Sci.,1993,7:335-7:335-342
[6]Henderson W. Queueing networks with negative customers and negative queueing lengths [J].Appl.Prob.,1993,30:931-942
[7]Gelenbe E. G-networks:A unifying model for neural and queueing networks [J].Annals of Operations Research,1994,48:433-461
[8]Boucherie R J. and Van Dijk N M.Local balances in queueing networks with positive and negative customers [J].Annals of Operations Research,1994,48:463-492
[9]Chao X. and Pinnedo M. Networks of queues with batch services signals and product form solutions [J].Operations Research Letters,1995,18:237-242
[10]Fourneau J.M., Gelenbe E. and Suros R. G-networks with multiple classes of negative and positive customers[J].Theoretical computer science,1996,155:141-156
[11]Chao X. A queueing network model with catastrophes and product form solution [J]. Operations Research,1995,18:75-79
[12]Gelenbe E. and Fourneau. G-networks with resets [J].Performance Evaluation,2002,12: 179-191
[13]Gelenbe E. and Schassberger R. Stability of product form G-networks [J]. Prob Eng Inf Sci.,1992,6:271-276
[14]Gomez-Corra A. and Martos E. Performance of two-stage tandem queues with blocking: the impact of several flows of signals[J]. Performance Evaluation,2006,63:910-938
[15]Gomez-Corra A.On a tandem G-network with blocking [J]. Adv. Appl. Prob.,2002,34: 626-661
[16]Leite S.C. and Fragoso M.D. On the analysis of G-queues under heavy traffic[J]. Proceeding Proceedings of the 47th IEEE Conference on Decision and Control Cancum, 2008,9-11
[17]Harrison P.G. Compositional reversed Markov processes with applications to G-networks[J]. Performance Evaluation,2004,57:379-408
[18]Harrison P.G. and Pitel E. The M/G/l queue with negative customers[J]. Adv.Appl.Prob., 1996,28:540-566
[19]Gelenbe E. Random neural networks with negative and positive signals and product form solution[J].Neural Computation,1989,1:502-511
[20]Atalay V. and Gelenbe E. Parallel algorithm for color texture generation using the random neural network model[J].Pattern Recognition Artificial Intelligence,1992,6: 437-446
[21]Atalay V., Gelenbe E. and Yalabik N. The random neural network model for texture generation[J]. Pattern Recognition Artificial Intelligence,1992,6:131-141
[22]Artalejo J.R. G-networks:a versatile approach for work removal in queueing networks [J].Europ.Operat.Res.,2000,126:233-249
[23]Arazi A.,Ben-Jacob E. and Yechiali U. Bridging genetic networks and queueing theory [J]. Math.Meth.Operat.Res.,2005,62:453-466
[24]Gelenbe E. Steady-state solution of probabilistic gene regulatory networks[J].Phy.Rev.E., 2007,76:031903(8)
[25]朱翼隽,陈燕.负顾客排队系统的研究进展[J].江苏大学学报(自然科学版),2004,25(1)：48-51
[26]Levy P. Theorie de I.Addition des Variables Aleatoires Gauthier-Villars.Pairs,1939,20-36.
[27]Doob J.L. Stochastic Processes.John Wiley and Sons[J].Inc.,1953,1-5
[28]Bremaud P. Point Processes and Queues Martingale Dynamics[M]. New York: Springer,1981,122-155
[29]Iglehart D.L. Limit diffusion approximations for the many server queue and the repairman problem[J]. Adv.Appl.Prob.,1965,2:429-441
[30]Borovkov A. A. On limit laws for service processes in multi-channel systems (in Russian) [J].Siberian Math,1967,8:746-763.
[31]Borovkov A.A. Asymptotic methods in queueing theory[M]. New York:Wiley,1984, MR0745620
[32]Whitt W. On the heavy-traffic limit theorem for GI/G/∞ queues[J].Adv.Appl.Prob., 1982,14:171-190.
[33]Glynn P.W. and Whitt W. A new view of the heavy-traffic limit theorem for the infinite-server queue[J]. Adv.Appl.Prob.,1991,23:188-209
[34]Massey W.A. and Whitt W. Networks of infinite-server queue with nonstationary Poisson input[J].Queueing systems,1993,13:183-250.
[35]Mandelbaum A. and Pats G.. State-dependent queues:approximations and applications.In Stochastic Networks,F.P.Kelly,R.J.Williams,Institute for Mathematics and its Applica-tions,Vol.New York:Springer,1995,71:239-282.
[36]Mandelbaum A. and Pats G. State-dependent stochastic networks.Part I:Applications and Applications with continuous diffusion limits[J].Ann.Appl.Prob.,1998,8:569-646.
[37]Puhalskii A.A. andReiman M.I. The multiclass GI/PH/N queue in the Halfin-Whitt regime[J]. Adv.Appl.Prob.,2000,32:564-595.
[38]Whitt W. Heavy-traffic limits for the G/H2*/n/m queue[J]. Math.Oper.Res.,2005,30:1-27
[39]Kogan T., Liptser R.Sh. and Smorodinskii A.V. Gaussian diffusion approxima- tions of closed Markov models of computer networks[J]. Problems.Inform.Transmission,1986, 22:38-51
[40]Liptser R.Sh. and Shiryayev A.N. Theory of Martingales[M].Netherlands:Kluwer,1989, (English translation of 1986 Russian edition)
[41]Kurtz T. Representations of Markov processes as multiparameter time changes[J].Ann. Probability,1980,8:682-715
[42]Ethier S.N. and Kurtz T.G. Markov processes:characterization and convergence[M]. New York:Wiley,1986, MR0838085
[43]严加安.鞅与随机积分引论[M].上海出版社,1981,96-103
[44]王梓坤.随机过程论[M].北京：科学出版社,1978,48-59
[45]王寿仁.概率论基础与随机过程[M].北京：科学出版社,1997,18-24
[46]Guodong pang, Rishi Talreja and Whitt W. Martingale proofs of many-Server heavy-traffic limits for Markovian queues[J]. Probability Surveys,2007, Vol(4):193-267
[47]Karatzas and Shreve S. Brownian motion and stochastic calculus[M]. New York: Springer,1988, MR0917065
[48]Mandelbaum A., Massey W.A. and Reiman M.I. Strong approximations for Markovian sercice networks[J]. Queueing systems,1998,30:149-201
[49]Jacod J. and Shiryayev A.N. Limit theorems for stochastic processes[M]. New York: Springer,1987, MR0959133
[50]Khoshnevisan D. Multiparameter processes:an introduction to random fields[M]. New York:Springer,2002,MR1914748
[51]Daley D.J. and Vere-Jones D. An introduction to the theory of point processes[M]. New York:Springer,2003:325-386
[52]Rebolledo R. Central limit theorems for local martingales[J]. Zeitschirift Wahrscheinlich-keitstheorie verw,1980,51:269-286
[53]Whitt W. Proof of the martingale functional central limit theorem[J]. Probability Surveys, 2007,4:268-302
[54]Rogers L.C.G. and Williams D. Diffusions, Markov processes and martingales.Volume 2: Ito Calculus[M]. New York:Wiley,1987, MR0921238
[55]Vander A.W. Martingales,diffusions and financial mathematics lecture note.2006, Available at:https://www.math.vu.nl/sto/onderwijs/mdfm/
[56]Leite S.C. and Marcelo D.F. Diffusion approximation of state-dependent G-networks under heavy traffic[J]. Adv.Appl.Prob.,2008,45:347-362
[57]Kushner H.J. Heavy traffic analysis of controlled queueing and communication networks[M]. New York:Springer,2001