1、2017 年国家自然科学奖推荐公示项目名称：随机网络中分块结构马氏过程的无穷维消元与分解的计算理论研究主要完成人：李泉林（燕山大学） 、林闯（清华大学） 、郭朋飞（香港理工大学） 、田乃硕（燕山大学） 、王金亭（北京交通大学）一、项目名称：随机网络中分块结构马氏过程的无穷维消元与分解的计算理论研究二、推荐单位意见推荐单位 河北省科学技术厅通讯地址 河北省石家庄市裕华东路 105 号 邮政编码 050011联 系 人 杨玲 联系电话 0311-85829164电子邮箱 传 真推荐意见：该项目在马氏过程的计算理论及其在目前热点排队系统与计算机网络等实际领域中的应用取得了突破性进展，为分块结构的马
2、氏过程（包括马氏更新过程、马氏保持过程） 、多类排队系统以及大规模计算机网络的性能评价提供了强有力的理论基础与数学方法。特别地，该项目首次建立了一般马氏过程的两类RG-分解，为求解无穷维线性方程组提供了一套新的计算理论体系。研究成果在国内外相关的学术界中产生了较大影响。该项目建立了包括构造性地提出了一般马氏过程的两类RG-分解；为马氏更新过程与马氏报酬过程提供了两类RG-分解框架下的新理论新方法；奠定了随机系统稳态解与瞬态解的RG-分解计算理论基础；建立了扰动马氏过程的两类RG-分解计算方法，从而开拓了演化博弈论研究的新空间；解决了诸如拟平稳分布与尾部分布渐近性的马氏过程理论中的著名难题。应用
3、两类RG-分解的理论方法，研究了国际热点的排队系统，开拓在网络与信息环境下服务经济与服务管理中排队博弈模型与信息经济决策的新空间，首次提出了网络安全中随机模型的定量分析方法。该项目的研究成果，特别是8篇代表性论著获得了排队论与随机过程领域诸如M.F. Neuts，M. Miyazawa，G. Latouche, V. Ramaswami和P.G. Taylor等著名学者的积极评价。推荐该项目申报2017年度国家自然科学奖一等奖。声明：本单位遵守国家科学技术奖励条例及其实施细则的有关规定，承诺遵守评审工作纪律，所提供的推荐材料真实有效，且不存在任何违反中华人民共和国保守国家秘密法和科学技术保密规
4、定等相关法律法规及侵犯他人知识产权的情形。如有材料虚假或违纪行为，愿意承担相应责任并接受相应处理。如产生争议，保证积极调查处理。法人代表签名： 推荐单位（盖章） 年 月 日 年 月 日二、项目简介随机网络是目前国际上排队论与应用概率等领域中的一个热点前沿研究方向，在计算机网络与制造系统等领域有着广泛的应用。随着信息技术、网络技术与制造技术的快速发展，各类实际网络系统日趋庞大复杂。要对这些复杂随机系统进行性能评价、优化设计与动态控制，其精确解一般是不存在的；即使存在，也要对系统模型进行大大简化。基于此，随机网络的数值解不仅是实际工程的迫切需要，而且它所面对的一些重要问题也需要尽快解决。因此，随机
5、网络的计算理论已经成为许多实际网络系统发展中急需突破的重要研究课题。分块结构的马氏过程是随机网络研究中的一个核心理论部分，它是支撑乘积解与平均场理论的前提基础。本项目对一般（分块结构）马氏过程开展了系统性的研究，多项成果属原创性贡献，处于国际前沿，得到了国内外的广泛认可，为本领域近年来国际上的一项重要理论研究突破。其主要研究成果如下：（1）提出了一般（分块结构）马氏过程的两类 RG-分解；利用 RG-分解将线性方程组求解的高斯消元法从有限维拓展到了无穷维，建立了无穷维线性方程组求解的一个新型的 RG-分解理论框架，从而奠定了随机网络数值计算的理论基础。随机模型的数值计算研究开始于国际著名学者
6、M.F. Neuts 的矩阵几何解（1981） 。注意到 Neuts 的矩阵几何解仅仅适用于两类特殊结构（GI/M/1 型、M/G/1 型）的马氏过程，因此作为拓展矩阵几何解的一个重要理论突破，本项目通过 RG-分解给出了一般（分块结构）马氏过程的数值计算，并且建立了一个完整的计算理论体系。（2）在一般（分块结构）马氏过程研究中，两类 RG-分解不仅发挥着关键性的理论架构作用，而且也是一个有用的基本关系公式，如同 Random Walks中 Wiener-Hopf 因子一样。本项目利用两类 RG-分解解决了马氏过程理论研究中的若干重要难题与热点问题，例如一般马氏过程的拟平稳分布；马氏过程的尾部
7、渐近性分析；马氏过程的各类报酬泛函计算及其敏感性分析等等。另一方面，本项目也构建了马氏更新过程与马氏报酬过程的两类 RG-分解，由此两类RG-分解能够被用于研究更宽的随机系统，如马氏决策过程、演化博弈与随机博弈等等。（3）针对服务经济是国际经济发展中的主流方向，本项目研究了在网络与信息环境下服务经济与服务管理中的排队博弈模型以及信息经济决策，利用两类 RG-分解开拓了排队经济的算法空间。本项目系统研究了休假排队系统并建立了随机分解的理论体系；研究了重试排队、共享排队与流体排队等国际热点难点的排队系统；解决了计算机网络中诸如网络安全与服务质量等重要问题。在本项目中，8 篇代表性论著总计 SCI
8、他引 293 次，他引 978 次；获得了排队论与随机过程领域诸如 M.F. Neuts，M. Miyazawa，G. Latouche, V. Ramaswami 和 P.G. Taylor 等著名学者的积极评价；获得了教育部提名国家科学技术奖（自然）一等奖、北京市科学技术（自然）二等奖、河北省科学技术奖（自然）二等奖。三、客观评价8 篇代表性论著总计 SCI 他引 293 次，他引 978 次，受得了排队论与随机过程领域多位著名学者的积极评价。获得了教育部提名国家科学技术奖（自然）一等奖、北京市科学技术（自然）二等奖、河北省科学技术奖（自然）二等奖。（1）代表作1利用 RG-分解建立了一般
9、马氏过程（或随机网络）的计算理论体系，是拓展 Neuts 的矩阵几何解的一个重要理论突破，为这个领域中代表性的学术成就之一。国际上多位著名学者对代表作1给予了好评与高度关注。在代表性引文1 中，法国 著名随机过程专家 Vincent Vigon 评价：“In many special cases, this factorization leads to interesting methods to compute invariant measures and more generally to study structured Markov chains as the one appearin
10、g in queuing systems cf. Cao, Li, Zhao 1719. Recently, a book by Li 16 was completely devoted to this subject.”; “When we work with structured Markov chains, many techniques have been invented to access these factors. Most of them are developed in Lis book 16.” 俄罗斯著名排队专家 S.F. Yashkov 在纪念 A.K. Erlang
11、 诞生一百周年专辑 Foreword to the thematical issue “centenary of the queuing theory”中将代表作 1列为 20 余本的重要学术著作之一。美国著名排队论专家 C. Knessl 在SIAM Review, 2010, Vol. 54 (1), 193196中评价：“This book deals with computing aspects of Markov chains, such as stationary and transient probability distributions, first passage time
12、s, and visiting times to certain states. this book is well organized, The results apply to large classes of stochastic models.” 加拿大著名排队论专家 Myron Hlynka 在Mathematical Reviews, MR2604162 (2011f:60141)中评价：“The book uses a wide variety of methods and creates a welcome unifying presentation. This book is
13、 a great book with which a young researcher might quickly move into serious analysis of applied queueing models.” 加拿大著名排队论专家 Qiming He 在 Springer 专著Fundamentals of Matrix-Analytic Methods评价： “(vii) Li (2010) for matrix-analytic methods, Wiener-Hopf factorization, and structured Markov chains.”“ A co
14、mprehensive treatment of RG-factorization in matrix-analytic methods can be found in Li (2010).” （2）代表作2是休假排队领域中的一个代表性专著。代表性引文2评价：“using the framework of queues with server vacations (Tian and Zhang 2006) .” ；荷兰著名排队论专家I. Adan在论文Queueing Systems, 2006, Vol. 62, 1-33评价：“there exists a significant numb
15、er of papers and books on vacation queueing systems (see, e.g., 23 and 24).”（3）代表作3首次研究了比较一般的 GI/G/1 型马氏过程的稳态概率尾部分布的渐近性问题，这是近年来国际上马氏过程的渐近性理论研究中的一个热点难点课题。代表性引文3评价：“ By using other method to analyse (2.12), below, such as those, for example, in 13 and 14, it is likely that this restriction can be lift
16、ed.” 日本著名排队论与随机过程专家 M. Miyazawa 在论文Advances in Applied Probability, 2004, Vol.36, 1231-1251评价： “In particular, the decay rate of the stationary distribution is considered for the light tailed case by Li and Zhao 13. Classical approaches, such as using matrix computations or complex variables, are al
17、so useful. These may provide us with more detailed information, particularly when the background state space is finite (see, e.g., 13).”（4）代表作4首次对一般拟生灭过程（QBD）构造了两类 RG-分解，并且利用两类 RG-分解研究了随机积分泛函的一些重要理论问题。代表性引文4评价：“The technique was based on the RG-factorization for an arbitrary irreducible Markov chain
18、 introduced in 14 and developed in 15,16,12”。法国著名随机过程专家 F. AvramTop, 2011, 317-335评价：“ the approach we adopted in this paper, the Gaussian elimination, also called RG factorization, see the recent book of Li (2010)”；“The systematic use of the factorizations seems to have started only recentlysee for
19、 example Li and Cao (2004)”。（5）代表作5首次将顾客的自主决策引入到了休假排队系统。代表性引文5评价： “ on vacation queueing systems and strategic customers, Guo and Hassin (2011) and Guo and Zhang (2013) (for proactive servers). analyze the effect of the information on the strategic behavior of the customers (see, e.g., Whitt 1999, G
20、uo and Zipkin 2007, Hassin 2007, Armony et al. 2009, and Guo and Hassin 2011)”。（6）代表作6属于较早考虑顾客的排队过程是由顾客自主决策形成的内生过程，研究了不同信息利用水平对排队系统性能的影响。代表性引文6评价：“they estimate the expected delay, as is common in the literature that considers customer choice in queuing systems (see, e.g., Guo and Zipkin 2007 ).”。代表
21、作6 在排队经济学领域中受到了广泛关注，包括美国工程院院士 W. Whitt 的一系列研究工作：Operations Research, 2009, 57, 66-81 ， Management Science, 2009, Vol. 55, 1729-1742 ， Operations research, 2011, Vol. 59, 1106-1118 。（7）代表作7在网络安全中首次针对DoS攻击建立了一个排队模型，开拓了网络安全研究到量化分析方法的随机模型新领域。代表性引文7评价：“ there have been few proposals for analytical models
22、 . The traditional tool has been that of simulation. This fact represents a drawback in the study of DoS attacks, This problem has been discussed recently by some authors, e.g., 15 ”。（8）代表作8首次在重试排队系统中研究了服务台故障与维修以及它们对系统性能的影响。代表性引文8评价：“Wang et al. (2001) modeled the M/G/1 queue as a retrial queue and
23、assumed that arrivals seeing the server either busy or down would return to the system until they were served.”四、代表性论文专著目录1 Quan-Lin Li (2010). Constructive Computation in Stochastic Models with Applications: The RG-Factorizations. Tsinghua University Press; Springer, 692 pages.2 Naishuo Tian; Zhe G
24、eorge Zhang (2006). Vacation Queueing Models: Theory and Applications. Springer, 385 pages.3 Quan-Lin Li; Y.Q. Zhao (2005). Light-tailed asymptotics of stationary probability vectors of Markov chains of GI/G/1 type. Advances in Applied Probability, Vol. 37, No. 4, 10751093.4 Quan-Lin Li; J. Cao (200
25、4). Two types of RG-factorizations of quasi-birth-and-death processes and their applications to stochastic integral functionals. Stochastic Models, Vol. 20, No. 3, 299340.5 Pengfei Guo; Refael Hassin (2011). Strategic behavior and social optimization in Markovian vacation queues. Operations research
26、, Vol. 59, No. 4, 986-9976 Pengfei Guo; Paul Zipkin (2007). Analysis and comparison of queues with different levels of delay information. Management Science, Vol. 53, No. 6, 962-970.7 Y. Wang; Chuang Lin; Quan-Lin Li; Y.G. Fang (2007). A queueing analysis for the denial of service (DoS) attacks in c
27、omputer networks. Computer Networks, Vol. 51, 35643573.8 Jinting Wang; J. Cao; Quan-Lin Li (2001). Reliability analysis of the retrial queue with server breakdowns and repairs. Queueing Systems, Vol. 38, No. 4, 363380.五、主要完成人情况（1）李泉林，排名 1，行政职务：无，技术职称：教授，工作单位：燕山大学，完成单位：清华大学。对本项目技术创造性贡献：构造性地提出了一般（分块结构
28、）马氏过程的两类 RG-分解；利用 RG-分解将线性方程组求解的高斯消元法从有限维拓展到了无穷维，建立了无穷维线性方程组求解的一个新型的 RG-分解理论框架。构建了马氏更新过程与马氏报酬过程的两类 RG-分解，由此 RG-分解方法能够被用于研究更宽的随机系统，如马氏决策过程、演化博弈与随机博弈等。这就奠定了随机网络数值计算的主要基础理论。利用 RG-分解方法解决了一些重要的随机系统的性能评价、优化设计和动态控制等重要问题，如重试排队、共享排队、流体排队、计算机网络以及制造系统等。占本人工作量的 90%。 （对第 1、2 项科学发现做出了贡献，见代表作1, 3, 4, 7, 8） 。（2）林 闯
29、，排名 2，行政职务：无，技术职称：教授，工作单位：清华大学，完成单位：清华大学。对本项目技术创造性贡献：主要从事计算机网络和服务计算的性能评价与优化研究，针对计算机系统和网络中的服务质量评价和分析问题，提出了基于行为的多队列到达系统量化分析模型 ，给出了非马尔科夫过程的建模方法，并利用 RG-分解理论成果得到了一种高效求解方法，成功应用于网络安全 DoS 攻击和邮件安全攻击等系统的分析，开启了网络攻击定量分析的新研究空间。占本人工作量的 80%。 （对第 4 项科学发现做出了贡献，见代表性论文7，1） 。（3）郭朋飞，排名 3，行政职务：副系主任，技术职称：副教授，工作单位：香港理工大学，完成单位：香港理工大学。对本项目技术创造性贡献：在理论方面，在国际上较早考虑了顾客依据信息进行自主决策以及不同信息环境对整个排队系统的性能影响，阐明了更充分的信息并不一定会导致系统更优并且给出了相应的信息更优的充分条件。拓展研究对象到休假排队系统并首次阐明了在此类系统中顾客的排队博弈行为存在多个均衡解。在应用方面，对多种具有顾客自主到达过程的服务系统进行了建模分析，包括呼叫中心和安检系统。在公立与私立相混营的医疗服务系统方面，阐明了单纯扩大公立医疗系统产能并不定能减轻公立系统常见的拥堵问题。这些研究成果开拓了一个新的重要的排队经济决策研究方向。
