超市模型的实时动态控制及其数值分析-论文.pdf

《超市模型的实时动态控制及其数值分析-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、应用概率统计第三十卷ChineseJournalofAppliedProbability第二期2014年4月andStatisticsVo1．30No．2Apr．2014超市模型的实时动态控制及其数值分析冰李泉林杜晔王盟代桂蓉(燕山大学经济管理学院，秦皇岛，066004)摘要超市模型是针对大型并行排队网络所进行的实时动态控制的随机负载平衡策略，它在计算机网络、云计算、制造系统、交通网络等领域有着重要的实际应用价值．本文考虑了超市模型中的若干重要问题：实时动态控制模式；效率比较；平均场黑洞；马氏变动环境；稳定性

2、；固定点；系统性能评价等等．同时，本文也通过数值算例研究了上述重要问题包括对顾客加入最短队列的超市模型与服务台服务最长队列的超市模型进行了性能比较，给出了他们效率的优劣分析；在超市模型中对控制到达过程机制进行了三种情况的对比；对马氏变动环境下的超市模型进行了性能评价．关键词：超市模型，随机负载平衡策略，随机变动环境，平均场黑洞，性能评价，固定点，稳定性．学科分类号：TP393，O211．61，0226．§1．引言资源管理与任务调度已经成为当今计算机网络的重要研究方向，特别是目前的云计算与云制造又极大地推动了计

3、算机网络资源管理的系统性研究．在过去的十多年中，随机负载平衡策略一直是计算机网络资源管理的主流研究方向，它是一种在计算机网络中操作简单、方便使用的集中化分配资源方法．近年来的研究成果表明：一个简单的随机负载平衡策略在一些大型网络的资源管理中可以取得系统性能方面的有效改进，例如减少冲突，降低逗留时间，提高处理能力等等．目前，在计算机网络领域中随机负载平衡策略已经被广泛地应用于数据中心、呼叫中心、分布式内存机、网络的任务分配与路径选择等重要的实际系统中．在另一个方面，这种随机负载平衡策略也可以在医院挂号、高速路收

4、费、海关通道等实际问题中比较容易地找到它的应用环境．马氏过程与排队论已经被应用于研究随机负载平衡策略，这就形成了超市模型的一个重要研究方向．就像本文中的图1和图2所示，超市模型一般地都采用实时动态控制机制，这就使得众多的服务台相互关联、相互依赖；而这种相依性使得超市模型中的大型排队网络变得异常复杂．于是，经典的排队论与马氏过程不能直接应用到对超市模型的研究中．到目前为止，超市模型分析仍然是一个崭新的研究方向，有着许多重要的实际问题需要解决．国家自然科学基金(71271187)资助．本文2013年5月14日收到

5、，2013年9月2日收到修改稿doi：10．3969／j．issn．i001—4268．2014．02．002应用概率统计第三十卷近年来，国内外一些学者已经使用排队论与马氏过程来研究超市模型．对于简单的超市模型(即顾客到达是泊松过程，服务时间服从指数分布)，Vvedenskaya等(1996)$~m无穷维马尔可夫过程序列的算子半群给出了平均场极5~(Mean—fieldlimit)，这就表明当服务台的个数趋于无穷大时，超市模型中的各个排队过程具有渐进独立性；利用这种平均场极限，他们研究了系统的平稳分布并得到了

6、一个重要结论：每个服务台上的稳态队长呈现出双重指数衰变的尾分布．这也说明了超市模型对整体排队系统的性能结构有着实质性的改善．Mitzenmacherf1996)$0用密度相依的跳跃马尔可夫过程分析了这个超市模型并且获得了相同的结论；Turnerf1998)对这个超市模型提出了鞅的分析方法，并且给出了比较详细的计算机模拟结果．Graham(2000a，2000b，2005)研究了这个超市模型样本空间的极限演化过程：无论最初开始于哪一个初始状态，当服务台数趋于无穷大时，这个超市模型的众多排队过程是渐进独立的．Lu

7、czak~INorrisf2oo5)给出了这个超市模型的强逼近结果．随后，Luczak和McDiarmid(2006，2007)证明了在这个超市模型中最长队长的估计阶为(1oglogN)／logd+(二}(1)．Bramson等(2010，2012)将超市模型中的服务时间推广到一般分布，讨论了各个服务台之间的渐进独立性，并分析了每个服务台稳态队长的尾部分布．Li等(2011，2010)推广了超市模型的服务时间~,JPH分布和顾客输入为马氏到达过程．Vvedenskaya和Suhov(1997)，Mitzenm

8、acher等(2001)及Li和Dai(2013)提供了研究超市模型的三个综述报告．本文的目的是来介绍近年来国内外学者在超市模型研究领域中已经获得一些重要的模型类别和研究成果，详细地讨论了超市模型中的三个重要问题：(1)实时动态控制模式，包括输入控制、服务控制、双重控制(即，输入与服务的混合控制)；特别是在服务控制中我们提出了一个国际上的公开难题：平均场黑洞．(2)固定点计算，在上述三种控制模式下分