离散事件系统的Markov模型在呼叫接入控制中的应用
|
摘要
随着高新技术的迅猛发展,现实世界中涌现了大量的复杂人造系统即离散事件系统(DES),它作为计算机控制与系统科学的一门新兴分支在最近的二三十年里得到了蓬勃发展。典型的例子有通信系统中的呼叫接入控制。然而,现在对离散事件系统建模的研究,还远不是成熟和完善的。尤其是基于Markov模型的分析不是很全面,因此有必要基于Markov模型对DES进行分析。此外,基于DES统计性能层次的Markov决策过程的优化问题是近年来研究热点。本文将Markov模型的分析方法应用于呼叫接入控制问题,研究了它的策略优化算法。概括起来,论文主要包括以下几方面的内容:
1、基于Markov模型的离散事件系统的分析
利用马尔科夫链的结果,在离散事件系统逻辑层次基础上,对DES的Markov模型的稳态和暂态特性,分别从时间参数连续和离散的情况下,分四个情况进行了分析,文章还讨论了DES模型统计性能层次与逻辑层次之间的联系。
在此基础上,结合DES的统计性能层次研究系统平均性能及其优化,目的寻找一个呼叫接入控制策略使长期平均报酬达到最大,采用动态规划的方法,使性能势与Markov决策过程方法相结合,推导出策略优化算法。
2、呼叫接入控制系统的计算机仿真实验。
在1的基础上,采用单个样本轨道的仿真,设计一种效率较高的在线仿真算法。用函数逼近的技术以适合的平均代价梯度来在线更新策略参数,算法迭代最终得到平均代价准则的最优化策略。
Discrete event system(DES) is an important applied classification of computer control.The typical example is admission control of communication system which is a relatively commonly see problem of queuing network.In this paper,we apply the analytical method of Markov model to the problem of admission control of communication system,and the algorithm of policy optimization is investigated.
in summary,the main researches in this paper are as follows:
1.analysis of discrete event system based on Markov model.
Results of Markov chain are used under the circumstances of the automaton model which belongs to logical level of discrete event system(DES) to analyze probability distribution of steady states and transient states of Markov model of DES,respectively based on two conditions of discrete-time parameter and continuous-time parameter.In addition,relationship between statistic performance level and logical level of DES is discussed too.
On this basis,combined with statistic performance level of DES,the average performance of system and optimization are discussed in order to find a policy of admission control communication system which makes maximum long-term average compensation.Performance potentials and Markov control process are combined to deduce the algorithm of policy optimization,making use of dynamic programming(DP).
2.The computer simulation experiment of admission control of communication system based on the results of 1,a relatively high efficiency-online simulation algorithm is designed by simulating a single sample path.The policy parameters are updated online by appropriate gradients of average cost,using the approximation of function.The optimal strategy of average-cost criteria is gotten after iteration of algorithm finally.
1、基于Markov模型的离散事件系统的分析
利用马尔科夫链的结果,在离散事件系统逻辑层次基础上,对DES的Markov模型的稳态和暂态特性,分别从时间参数连续和离散的情况下,分四个情况进行了分析,文章还讨论了DES模型统计性能层次与逻辑层次之间的联系。
在此基础上,结合DES的统计性能层次研究系统平均性能及其优化,目的寻找一个呼叫接入控制策略使长期平均报酬达到最大,采用动态规划的方法,使性能势与Markov决策过程方法相结合,推导出策略优化算法。
2、呼叫接入控制系统的计算机仿真实验。
在1的基础上,采用单个样本轨道的仿真,设计一种效率较高的在线仿真算法。用函数逼近的技术以适合的平均代价梯度来在线更新策略参数,算法迭代最终得到平均代价准则的最优化策略。
Discrete event system(DES) is an important applied classification of computer control.The typical example is admission control of communication system which is a relatively commonly see problem of queuing network.In this paper,we apply the analytical method of Markov model to the problem of admission control of communication system,and the algorithm of policy optimization is investigated.
in summary,the main researches in this paper are as follows:
1.analysis of discrete event system based on Markov model.
Results of Markov chain are used under the circumstances of the automaton model which belongs to logical level of discrete event system(DES) to analyze probability distribution of steady states and transient states of Markov model of DES,respectively based on two conditions of discrete-time parameter and continuous-time parameter.In addition,relationship between statistic performance level and logical level of DES is discussed too.
On this basis,combined with statistic performance level of DES,the average performance of system and optimization are discussed in order to find a policy of admission control communication system which makes maximum long-term average compensation.Performance potentials and Markov control process are combined to deduce the algorithm of policy optimization,making use of dynamic programming(DP).
2.The computer simulation experiment of admission control of communication system based on the results of 1,a relatively high efficiency-online simulation algorithm is designed by simulating a single sample path.The policy parameters are updated online by appropriate gradients of average cost,using the approximation of function.The optimal strategy of average-cost criteria is gotten after iteration of algorithm finally.
引文
[1]王兴富,谷红伟,戴学丰.马尔可夫链在离散事件系统中的应用[J].自动化技术与应用,2000,19(3):35-36.
[2]杜雪樵,惠军.随机过程[M].合肥:合肥工业大学出版社,2006,1-126.
[3]郑大钟,赵千川.离散事件动态系统[M].北京:清华大学出版社,2001,1-21.
[4]韩江洪,郑淑丽,陆阳,魏振春,于筑国.离散事件控制系统规则化描述方法的研究[J].合肥工业大学学报(自然科学版),2005,28(9):1081-1084.
[5]唐昊,韩江洪,高隽.连续时间Markov控制过程的平均代价最优鲁棒控制策略[J].中国科学技术大学学报,2004,34(2):119-225.
[6]殷保群,李衍杰,奚宏生,周亚平.一类可数Markov控制过程的最优平稳策略[J].控制理论与应用,2005,22(1):43-46.
[7]唐昊,奚宏生,殷保群.Markov控制过程基于单个样本轨道的在线优化算法[J].控制理论与应用,2002,19(6):865-871.
[8]CaoX R.Semi-Markov decision problems and performance sensitivity analysis[J].IE EE Trans on Automatic Control,2003,48(5):758-769.
[9]P.J.Ramadge and W.M.Wonham.The Control of Discret Event System,Proc.IEEE,1989,77(1):81-98.
[10]Zhang L H,Zhang Y H.Ergodicity of a Class of Single Death Processes[J].Chinese Journal of Applied Probability and Statistics,2007,23(4):377-383(in Chinese)
[11]Chen,M.F.,From Markov Chains to Non-Equilibrium Particle Systems,World Scientific,Singapore,Fist Edition 1992;Second Edition 2004.
[12]Cao X R,Chen H F.Perturbation realization,potentials,and sensit ivity analysis of Markov processes[J].IEEE Trans on Autom Contr,1997,42(10):1382-1393.
[13]周亚平,奚宏生,殷保群,孙德敏.Markov控制过程基于性能势的平均代价最优策略[J].自动化学报,2002,28(6):904-910.
[14]周亚平,奚宏生,殷保群,唐昊.连续时间Markov决策过程在呼叫接入控制中的应用[J].控制与决策,2001,Vol.16 Supp 1:795-799.
[15]P Marbach,J N Tsitsiklis.Simulation-based optimization of Markov reward processes[J].IEEE Trans on AutomContr,2001,46(2):1912209.
[16]ARAPOSTATHIS A,BORKAR V S,FERNANDEZ-GAUCHER,etal Discrete-time controlled Markov processes with average cost criterion:asurvey[J].SIAMJ of Control Optimization,1993,31(2):282-344.
[17]RAUL Montes-de-Oca.The average cost optimality equation for Markov control processes on Borel spaces[J]System and Control Letters,1994,22(5):351-357.
[18]SENNOT L I.Another set of conditions for average optimality in Markov control processes[J].Systems and Control Letters,1995,23(2):147-151.
[19]CAO X R.The relations among potentials,perturbation analysis,and Markov decision processes[J].Discrete Event Dynamic Systems:Theory and Applications,1998,8(1):71-78.
[20]CAO X R.A unified approach to Markov decision problems and per-formance sensitivity analysis[J].Automatica,2000,36(5):771-774.
[21]YIN Baoqun,ZHOU Yaping,XI Hongsheng,etal.Sensitivity formulas of performance in two-server cyclic queuing networks with phasetype distributed service times[J].Int Trans on Operation Research,1999,6(6):649-663.
[22]CINLAR E.Introduction to Stochastic Processes[M].Englewood Cliffs,NJ:Prentice-hall,1975.
[23]KEMENY J G,SNELL J L.Potentials for denumerable Markov chains[J].J of Mathematical Analysis and Applications,1960,3(1):196-260.
[24]PUTERMAN M L.Markov Decision Processes:Discrete Stochastic Dynamic Programming[M].New York:Wiley,1994.
[25]P.J.Ramadge and W.M.Wonham.The Control of Discret Event System,Proc.IEEE,1989,77(1):81-98.
[26]Sun W,Khargonekar P P,Shim D.Solution to the positive real control problem for linear time2invariant systems.IEEETransactions on Automatic Cont rol,1994,39(10):2034-2046
[27]Xie L,Soh Y C.Positive real control problem for uncertain linear time2invariant systems.Systems and Control Letters,1995,24(2):265-271
[28]Aliyu M D S.Passivity and stability of nonlinear systems with Markovian jump parameters.In:Proceedings of the American Control Conference,San Diego,California,USA:IEEE Press,1999,2:953-957
[29]Krasovskii N N,Lidskii E A.Analyticldesign of controllers in systems with random attributes.Automation and Remote Control,1961,22(I2III):1021-1025
[30]张丽华,张余辉。一类单死过程的遍历性[J]。应用概率统计,2007,23(4):377-383
[31]殷保群,周亚平,杨孝先,等.状态相关闭排队网络中的性能灵敏度公式[J].控制理论与应用,1999,16(2):255-257.
[32]王丽姿Markov排队模型在医院管理中的应用[J]。中国医院统计2007,14(2):125-126
[33]赵树进,杨哲,钟拥军.基于排队论的医疗工作流程重组[J].中国医院管理,2003,23(4):10-12、
[34]刘飞 苏宏业 褚健 含参数不确定性的马尔可夫跳变过程鲁棒正实控制[J].自动化学报2003,29(5),761-766
[35]代桂平,殷保群,李衍杰,奚宏生 半Markov控制过程基于性能势仿真的并行优化算法[J].中国科学技术大学学报,2006,36(2):183-186
[36]邹长春,周亚平,殷保群,等.基于性能势理论对闭排队网络进行梯度估计的并行仿真算法[J].中国科学技术大学学报,1999,29(1):21229.
[37]代桂平,殷保群,李衍杰,等.半Markov控制过程在平均代价准则下的迭代优化 算法[J].中国科学技术大学学报,2005,35(2):2022207.
[38]高飞 张洪钺 带马尔科夫参数时滞容错控制系统稳定性分析 北京航空航天大学学报 2006。32(5)
[39]胡奇英,刘建墉.马尔可夫决策过程引论[M].西安:西安电子科技大学出版社,2000.
[40]盛友招.排队论及其在计算机通信中的应用[M】.北京:北京邮电大学出版社.2000
[41]孙海荣,李乐民,何家福.ATM网络中Pareto分布的ON～OFF业务源对CBR业务时延性能的影响Ⅲ.电子学报,1998,26(7):74-78.
[42]李建东.信息网络理论基础[M】.西安:西安电子科技大学出版社,2001.
[2]杜雪樵,惠军.随机过程[M].合肥:合肥工业大学出版社,2006,1-126.
[3]郑大钟,赵千川.离散事件动态系统[M].北京:清华大学出版社,2001,1-21.
[4]韩江洪,郑淑丽,陆阳,魏振春,于筑国.离散事件控制系统规则化描述方法的研究[J].合肥工业大学学报(自然科学版),2005,28(9):1081-1084.
[5]唐昊,韩江洪,高隽.连续时间Markov控制过程的平均代价最优鲁棒控制策略[J].中国科学技术大学学报,2004,34(2):119-225.
[6]殷保群,李衍杰,奚宏生,周亚平.一类可数Markov控制过程的最优平稳策略[J].控制理论与应用,2005,22(1):43-46.
[7]唐昊,奚宏生,殷保群.Markov控制过程基于单个样本轨道的在线优化算法[J].控制理论与应用,2002,19(6):865-871.
[8]CaoX R.Semi-Markov decision problems and performance sensitivity analysis[J].IE EE Trans on Automatic Control,2003,48(5):758-769.
[9]P.J.Ramadge and W.M.Wonham.The Control of Discret Event System,Proc.IEEE,1989,77(1):81-98.
[10]Zhang L H,Zhang Y H.Ergodicity of a Class of Single Death Processes[J].Chinese Journal of Applied Probability and Statistics,2007,23(4):377-383(in Chinese)
[11]Chen,M.F.,From Markov Chains to Non-Equilibrium Particle Systems,World Scientific,Singapore,Fist Edition 1992;Second Edition 2004.
[12]Cao X R,Chen H F.Perturbation realization,potentials,and sensit ivity analysis of Markov processes[J].IEEE Trans on Autom Contr,1997,42(10):1382-1393.
[13]周亚平,奚宏生,殷保群,孙德敏.Markov控制过程基于性能势的平均代价最优策略[J].自动化学报,2002,28(6):904-910.
[14]周亚平,奚宏生,殷保群,唐昊.连续时间Markov决策过程在呼叫接入控制中的应用[J].控制与决策,2001,Vol.16 Supp 1:795-799.
[15]P Marbach,J N Tsitsiklis.Simulation-based optimization of Markov reward processes[J].IEEE Trans on AutomContr,2001,46(2):1912209.
[16]ARAPOSTATHIS A,BORKAR V S,FERNANDEZ-GAUCHER,etal Discrete-time controlled Markov processes with average cost criterion:asurvey[J].SIAMJ of Control Optimization,1993,31(2):282-344.
[17]RAUL Montes-de-Oca.The average cost optimality equation for Markov control processes on Borel spaces[J]System and Control Letters,1994,22(5):351-357.
[18]SENNOT L I.Another set of conditions for average optimality in Markov control processes[J].Systems and Control Letters,1995,23(2):147-151.
[19]CAO X R.The relations among potentials,perturbation analysis,and Markov decision processes[J].Discrete Event Dynamic Systems:Theory and Applications,1998,8(1):71-78.
[20]CAO X R.A unified approach to Markov decision problems and per-formance sensitivity analysis[J].Automatica,2000,36(5):771-774.
[21]YIN Baoqun,ZHOU Yaping,XI Hongsheng,etal.Sensitivity formulas of performance in two-server cyclic queuing networks with phasetype distributed service times[J].Int Trans on Operation Research,1999,6(6):649-663.
[22]CINLAR E.Introduction to Stochastic Processes[M].Englewood Cliffs,NJ:Prentice-hall,1975.
[23]KEMENY J G,SNELL J L.Potentials for denumerable Markov chains[J].J of Mathematical Analysis and Applications,1960,3(1):196-260.
[24]PUTERMAN M L.Markov Decision Processes:Discrete Stochastic Dynamic Programming[M].New York:Wiley,1994.
[25]P.J.Ramadge and W.M.Wonham.The Control of Discret Event System,Proc.IEEE,1989,77(1):81-98.
[26]Sun W,Khargonekar P P,Shim D.Solution to the positive real control problem for linear time2invariant systems.IEEETransactions on Automatic Cont rol,1994,39(10):2034-2046
[27]Xie L,Soh Y C.Positive real control problem for uncertain linear time2invariant systems.Systems and Control Letters,1995,24(2):265-271
[28]Aliyu M D S.Passivity and stability of nonlinear systems with Markovian jump parameters.In:Proceedings of the American Control Conference,San Diego,California,USA:IEEE Press,1999,2:953-957
[29]Krasovskii N N,Lidskii E A.Analyticldesign of controllers in systems with random attributes.Automation and Remote Control,1961,22(I2III):1021-1025
[30]张丽华,张余辉。一类单死过程的遍历性[J]。应用概率统计,2007,23(4):377-383
[31]殷保群,周亚平,杨孝先,等.状态相关闭排队网络中的性能灵敏度公式[J].控制理论与应用,1999,16(2):255-257.
[32]王丽姿Markov排队模型在医院管理中的应用[J]。中国医院统计2007,14(2):125-126
[33]赵树进,杨哲,钟拥军.基于排队论的医疗工作流程重组[J].中国医院管理,2003,23(4):10-12、
[34]刘飞 苏宏业 褚健 含参数不确定性的马尔可夫跳变过程鲁棒正实控制[J].自动化学报2003,29(5),761-766
[35]代桂平,殷保群,李衍杰,奚宏生 半Markov控制过程基于性能势仿真的并行优化算法[J].中国科学技术大学学报,2006,36(2):183-186
[36]邹长春,周亚平,殷保群,等.基于性能势理论对闭排队网络进行梯度估计的并行仿真算法[J].中国科学技术大学学报,1999,29(1):21229.
[37]代桂平,殷保群,李衍杰,等.半Markov控制过程在平均代价准则下的迭代优化 算法[J].中国科学技术大学学报,2005,35(2):2022207.
[38]高飞 张洪钺 带马尔科夫参数时滞容错控制系统稳定性分析 北京航空航天大学学报 2006。32(5)
[39]胡奇英,刘建墉.马尔可夫决策过程引论[M].西安:西安电子科技大学出版社,2000.
[40]盛友招.排队论及其在计算机通信中的应用[M】.北京:北京邮电大学出版社.2000
[41]孙海荣,李乐民,何家福.ATM网络中Pareto分布的ON～OFF业务源对CBR业务时延性能的影响Ⅲ.电子学报,1998,26(7):74-78.
[42]李建东.信息网络理论基础[M】.西安:西安电子科技大学出版社,2001.