（系统工程专业论文）基于排队论的通信网络QoS研究.pdf

江苏大学硕士研究生学位论文 摘要 通信网络的q o s ( 服务质量) 对未来网络技术的研究、应用和发 展具有举足轻重的意义。本课题从排队论角度出发，研究通信网络 q o s ，建立排队模型并加以分析，以解析公式的方式对关键的q o s 性 能指标进行描述。 首先，研究区分服务链路中a f 组数据流在网络核心节点中的排 队，采用m a r k o v 随机环境模拟a f 组数据流的带宽变化规律，分析 了网络边界节点对a f 组数据流采用的w r e d 缓存管理机制，随后 提出一类带有w r e d 缓存管理机制的m m p p + m m p p m m p p 1 k 队 列模型，求解模型并得到相关的q o s 性能指标。 然后，为通信网络中的动态优先权队列建立一类基于离散时间的 d m 删p h 1 排队模型，通过矩阵分析的方法求解该模型的平稳分 布，进而得出两类数据流的平均队长、阻塞概率和平均等待时间等 q o s 性能指标。 最后，为功率管理机制下无线自组织网络节点建立了一类带有空 闲启动和优先权机制且缓存容量有限的空竭服务多重休假 d b m a p p h 1 排队模型，对该排队模型进行了稳态分析并求解出相 应的q o s 性能指标，最后通过数值例子分析不同的负载情况下空闲 期和睡眠期对网络性能的影响。 对上述的三种模型，到达过程为p o i s s o n 过程的推广，模型更能 体现现实意义，从而较好地研究了通信网络的o o s 性能指标。 关键词：排队论，通信网络，q o s ，区分服务，动态优先权，功率管 理，自组织网络 江苏大学硕士研究生学位论丈 a b s t r a c t t h eq o s ( q u a l i t yo fs e r v i c e ) o fc o m m u n i c a t i o nn e t w o r kw i l lb ea l l - i m p o r t a n tt o t h er e s e a r c h ，a p p l i c a t i o na n dd e v e l o p m e n to ft h ef u t u r en e t w o r k st e c h n i q u e f r o mt h e a n g l eo fq u e u et h e o r y ，t h i sp a p e rt r i e st os t u d yt h eo o so fc o m m u n i c a t i o nn e t w o r k , a n db u i l dt h ec o r r e s p o n d i n gq u e u em o d e l s b ya n a l y z i n gt h em o d e l s ，w eo b t a i nt h e p i v o t a lq o sp e r f o r m a n c em e a s u r e sa st h ef o r mo fa n a l y s i sf o r m u l a s f i r s t l y , t h eq u e u eo fa fs t r e a ma tt h en e t w o r kn o d eu n d e rt h ed i f f s e r vl i n ki s s t u d i e d t h eb a n d w i d t hc h a n g e sr u l eo ft h ea fs t r e a mi ss i m u l a t e db yu s i n gm a r k o v r a n d o me n v i r o n m e n t t h ew r e dw h i c hi su s e df o ra fs t r e a m sb u f f e rm a n a g e m e n t m e c h a n i s ma tt h en e t w o r kn o d ei sa n a l y z e d a n dt h e nt h em m p p + m m p p f m m p p 1 k q u e u em o d e lw i mw r e db u f f e rm a n a g e m e n tm e c h a n i s mi sp r o p o s e d ，a l s o t h e c o r r e l a t i v eq o sp e r f o r m a n c ep a r a m e t e r s f i ed e r i v e db yt h es o l u t i o no ft h em o d e l s e c o n d l y , t h ed - m a p p h 1q u e u em o d e lb a s e o nd i s c r e t et i m ei sb u i l tf o r d y n a m i cp r i o r i t yq u e u ei nc o m m u n i c a t i o nn e t w o r k b yu s i n gt h em e t h o do fm a t r i x a n a l y s i s ，t h es t e a d y s t a t ed i s t r i b u t i o no ft h eq u e u ei sa n a l y s e d ，a n dt h em a i no o s p e r f o r m a n c em e a s u r e s a r eo b t a i n e ds u c ha s a v e r a g eq u e u el e n g t h ，b l o c k i n g p r o b a b i l i t ya n da v e r a g ed e l a yt i m eo f t h et w ot r a f f i c f i n a l l y ，t h eb u f f e r - l i m i t e dd b m a p p i - i im u l t i p l ev a c a t i o nq u e u i n gm o d e l 丽t l l i d l e s e t u pa n dp r i o r i t ym e c h a n i s m si sb u i l tb a s e do nt h ew i r e l e s ss e l f - o r g a n i z e d n e t w o r kn o d e su n d e rp o w e rm a n a g e m e n tm e c h a n i s m s t h es t e a d y - s t a t ed i s t r i b u t i o n o ft h eq u e u i n gm o d e li so b t a i n e da n dt h em a i nq o sp e r f o r m a n c em e a s u r e s f i ed e 打v e d a l s ot h ei d l ea n ds l e e pp e r i o d s i n f l u e n c eo nt h ep e r f o r m a n c eo fn e t w o r k su n d e r d i f f e r e n tl o a d si sa n a l y z e db yu s i n gn u m e r i c a li l l u s t r a t i o n t h ea r r i v a lp r o c e s s e sw h i c h f i eg e n e r a l i z e dt op o i s s o np r o c e s s f i ea d o p t e di nt h e t h r e em o d e l sa b o v em e n t i o n e d t h e r e f o r et h em o d e l sc a ns a t i s f yt h ea c t u a lc o n d i t i o n a n dt h eq o sp e r f o r m a n c em e a s u r e so fc o m m u n i c a t i o nn e t w o r kc a nb es t u d i e db e a e f k e yw o r d s ：q u e u et h e o r y ，c o m m u n i c a t i o n n e t w o r k , q u a l i t y o f s e r v i c e ， d i f f e r e n t i a t e ds e r v i c e s ，d y n a m i cp r i o r i t y , p o w e rm a n a g e m e n t ， s e l f - o r g a n i z e dn e t w o r k s 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存和汇编本学位论文。 保密口 本学位论文属于，在年我解密后适用本授权书。 不保密团 学位论文作者签名：豇坤 z 口d 分年f z 月f 6 日 燧名：格衫 q r 年| - 窍6 1 日 独创性申明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已注明引用的内容以外，本论文不 包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完 全意识到本声明的法律结果由本人承担。 学位论文作者签名：盏件 日期：2 0 0 ? 年f 2 月佑日 江苏大学硕士研究生学位论文 1 1 研究背景 第一章绪论 服务质量( q u a l i t yo fs e r v i c e ，o o s ) 是日常生活中人们再熟悉不过的字眼。 顾名思义，服务质量往往体现了消费者对服务者所提供服务的满意程度，是对服 务者服务水平的一种度量和评价。通信网络作为信息和通讯等服务的提供者，同 样存在服务质量优劣的问题。 事实上，从通信网络系统诞生伊始，就一直存在提高系统的服务性能和服务 质量的问题，因此，通信网络的q o s 问题实际上由来已久。随着i n t e m e t 规模的 不断扩大，各种各样的网络服务争相涌现，先进的多媒体系统层出不穷。由于实 时业务对网络传输时延、时延抖动等特性较为敏感，当网络上有突发性高的n 曙 或者含有图像文件的帅等业务时，实时业务就会受到很大影响；另一方面， 多媒体业务占去了大量的带宽，这样，现有网络要保证的关键业务就难以得到可 靠的传输。解决这些问题的最简单的办法当然是增大带宽，但是，由于这种方法 代价高昂，所以并不十分可行。这就要求网络管理者对不同的服务区别管理，而 不能对所有的数据包一视同仁。于是，各种q o s 技术应运而生。目前，通信网 络的q o s 问题已经成为国际网络研究领域最重要、最富有魅力的研究领域之一， 对未来网络技术的研究、应用和发展具有举足轻重的意义。 在文献【l 】中给出了q o s 的定义：决定用户满意程度的具有积累影响的服务需 求，这些需求经常用一些量级的参数表示。简单地说，q o s 能够对数据包进行合 理的排队，对含有内容标识的数据包进行优化，并对其中特定的数据包附以较高 的优先级，从而加速传输的进程，并实现实时交互。通过q o s ，网络可以按照业 务量的类型或级别加以区分，并能够依次对各级别进行处理。 排队论是用来建模和系统性能评价的传统方法。所谓性能评价( p e r f o r m a n c e e v a l u a t i o n ) 2 1 3 1 1 4 5 1 是指对系统的动态行为进行研究和优化，包括对实际系统的 行为进行测量和模型，按照一定的性能要求对方案进行选择，对现有系统的性能 缺陷和瓶颈进行改进，对未来系统的性能进行预测，以及在保证一定q o s 的前提 下进行设计。性能评价已有相当长的发展历史，它最先用于设计、测量通信系统， 确保系统的传输和开关特性、保证一定的q o s ；后来又被用于解决稀有资源的分 江苏大学硕士研究生学位论文 配问题：现在性能评价技术已经被广泛用于计算机和通信领域中。 排队论通过对服务对象的到来及服务时间的统计研究，得出一些性能指标的 统计规律，然后根据这些规律来改进服务系统的结构或重新组织被服务对象，使 得服务系统既能满足服务对象的需要，又能使系统的费用最经济或某些指标最 优。如果我们将网络中的分组视为排队论中的顾客，将交换机造成的时延看作为 排队论中的服务过程，显然，排队理论将对网络协议的制定、提高网络q o s 起到 一定的指导作用，同时网络技术的发展也为排队理论提供了广阔的应用舞台。 1 2 研究的目标与内容 研究的目标是应用排队理论，为一些q o s 机制管理下的通信网络建立排队模 型，在此基础上求出相应模型的解析解，得到衡量通信网络服务质量的q o s 性能 参数，如平均延时、丢包率、吞吐量等量化指标，为研究通信网络q o s 以及评价 网络性能提供了理论依据。 研究的内容主要是针对： 1 、利用m a r k o v 随机环境模拟区分服务体系中a f 组数据流的带宽变化情形， 提出一类带有缓存管理机制的队列模型并求解主要的q o s 性能指标。 2 、采用基于离散时间的d m 删p h 1 排队模型来研究动态优先权队列，通过 矩阵几何解的方法求解该模型的平稳分布，进而得出模型的各项q o s 性能指标。 3 、采用一类带有空闲启动和优先权机制的空竭服务多重休假排队模型来 研究无线自组织网络性能和节点能耗，使用矩阵分析的方法，求解功率管理机制 下无线网络的o o s 性能指标，并通过数值例子分析不同的负载情况下空闲期和睡 眠期对网络性能的影响。 1 3 本文组织结构 本文分为六章，第一章为绪论。第二章为通信网服务质量( o o s ) 及其排队 模型，介绍通信网q o s 的概况，以及通信网q o s 研究中一些基本的排队模型分析 方法。第三章为有关排队理论及工具，介绍本课题研究中用到的一些理论。本课 题研究是建立在第二、三章研究成果基础之上的。第四章为区分服务链路中确保 型数据流的性能分析。第五章为基于离散时间的动态优先权队列性能分析。第六 章为功率管理机制下无线自组织网络性能分析。后三章是本课题的工作重点。 2 江苏大学硕士研究生学位论文 第二章通信网服务质量( o o s ) 及其排队模型 2 1 通信网服务质量( o o s ) 概述 q o s 定义了一个系统的非功能化特征，通常是指用户对通信系统提供的服务 的满意程度。在计算机通信网络中，q o s 的目标是获得更加确定的通信行为，以 便能够安全可靠地保护网络承载的信息，并更加高效地使用网络资源。具体而言， q o s 是指网络为用户提供的一组可以测量的预定义的服务参数，包括时延、时延 抖动、带宽和分组丢失率等，也可以看成是用户和网络达成的需要双方遵守的协 定。q o s 论坛将q o s 定义为网络元素( 包括应用、主机或者路由器等网络设备 等) 对网络数据的传输承诺的服务保证级别。r f c2 3 8 6 6 d p 描述为：q o s 是网络 在传输数据流时要求满足的一系列服务请求。此处的服务具体是指数据包( 流) 经过若干网络节点所接受的传输服务，强调端到端或网络边界到边界的整体性。 q o s 反映了网络元素( 例如路由器) 在保证信息传输和满足服务要求方面的能力。 不同的应用有不同的q o s 要求，简单而言，q o s 是指网络需要提供给应用实现 正常功能所需的性能级别保证。 2 2 保证0 0 s 的一般机制 在一个统计共享资源系统如因特网中，保证q o s 的最基本方法可以表述为 以下4 个简单的步骤【7 】【8 】： 1 、定义服务种类。在网络节点比如交换机和路由器中，各种信息包将进行 不同的处理。 2 、分配给每个种类一定数量的资源来传输信息包。例如，种类1 需要整个链 路带宽的3 0 ，资源的分配可以是静态或者是动态的。 3 、把引入的信息包分类成不同的服务种类。各种服务种类的质量依赖于进 入这个种类的流量和分配给这个种类的资源量。许多方法可以用来调整服务质 量。例如，一个路由器可以通过动态调整资源分配使得一些种类的服务比其他种 类具有比较小的丢包率。另一个例子，可以给某一种类较高优先级以使得它更快 得到处理和有比较小的时延。 4 、控制每个服务种类的流量。为了保证服务质量，进入一个种类的流量不 3 江苏大学硕士研究生学位论文 能超过分配给它的资源。这可以通过控制信息进入或者采用资源预留来实现。控 制信息进入是指当某一种类的包太多就丢掉一些包，而资源预留是指发信号给路 由器来确知其是否还有资源，如果发送方得到路由器的许可，就可以发包。 如果所有路由器已经实现这4 个步骤，就可以保证端到端的服务。除非当路 由器的性能出现瓶颈的时候，否则这4 个步骤就足够能实现q o s 机制。 2 3 当前in t e r n e t 支持q o s 保障概况 迄今为止，i n t e r n e t 网络的q o s 问题已经进行了大量研究，其中最引入注目 的成果是i n t e r n e t 工程任务组( i n t e m e te n g i n e e r i n gt a s kf o r c e ，i e t f ) 先后提出 的集成服务( i n t e g r a t e ds e r v i c e ：i n t s e r v 9 ) 体系结构和区分服务( d i f f e r e n t i a t e d s e r v i c e s ，d i f f s e r v 1 0 1 ) 体系结构。前者基于资源预留协议( r e s o u r c er e s e r v a t i o n p r o t o c o l ，r s v p h i ) ，可以为实时业务提供确保的服务质量，但是可扩展性较差 和实现复杂等缺点限制了它在骨干网络中的使用，主要用于小型网络和局域网。 区分服务体系结构可以根据不同的服务级别协定( s e r v i c el e v e l a g r e e m e n t ，s l a ) 为各种业务提供一定级别的服务质量，并且由于可扩展性较好和实现简单的特点 而被推荐用于核心骨干网络。 1 、综合服务体系结构 现有的i n t e m e t 最初是面向非实时的、单一的数据类型通信而设计的。口协 议提供的是一种无连接网络层传输服务，必须辅以其他的高层协议才能更好地实 现端到端的可靠传输。由于缺少必要的q o s 控制或保证，这种传统的p 传输服 务称为“尽力而为 型服务( b e s t - e f f o r ts e r v i c e s ) ，而这种尽力而为型服务无法为 多媒体通信提供o o s 保证。为了满足i n t e m e t 多媒体应用实时传输的需求，i e t f 定义了综合服务模型i n t s e r v 。 在服务层次上，除了原来的尽力而为型服务外，i n t s e r v 还以每个流( 单独 的或聚集的) 为基础，提供了两种端到端的面向实时传输的服务；在实现的层次 上，i n t s e r v 方案需要所有的路由器在控制路径上处理每个流的信令消息并维护 每个流的路径状态和资源预留状态，并且在数据路径上执行基于流的分类、调度 和缓冲区管理；在技术层次上，i n t s e r v 依靠资源预留协议r s v p 提供q o s 协商 机制，依靠接纳控制( a d m i s s i o nc o n t r 0 1 ) 决定链路或网络节点是否有足够的资 源满足用户的资源预留请求，依靠传输控制( t r a f f i cc o n t r 0 1 ) 将口分组分类成不 4 江苏大学硕士研究生学位论文 同的传输流，并根据每个流的状态对分组的传输实施q o s 路由( r o u t i n g 6 ) 传输 调度( s c h e d u l i n g ) 等控制。 综合服务模型的目的是使m 网能够提供具有q o s 的传输，并定义新的服务 在每个应用流中用资源预留来满足对q o s 要求较为严格的实时应用( 如声音、 视频等) 的需求。i n t s e r v 是基于流的( 单独的或聚集的) 、状态相关的体系结构， 依赖于每个流( p e r - f l o w ) 的状态和对每个流的管理。这种实现机制一方面使 i n t s e r v 能够提供状态无关的体系结构具有更高的灵活性和更好的服务级别保证 的保证，但同时也导致了i n t s e r v 的可扩展问题和鲁棒性问题，后果是实现复杂、 难于应用。 2 、区分服务体系结构 在i n t s e r v 体系的发展遭遇巨大障碍的时候，区分服务( d i f f s e r v ) 应运而生。 d i f f s e r v 是由i n t s e r v 发展而来的，它采用了i e t f 的基于r s v p 的服务分类标准， 抛弃了分组流沿路节点上的资源预留。d i f f s e r v 的目标在于简单有效，以满足实 际应用对可扩展性的要求，其实现途径是： ( 1 ) 简化网络内部节点的服务机制。在内部节点只进行简单的调度转发，而 流状态信息的保存与流监控机制的实现等只在边界节点进行，内部节点是状态无 关的。 ( 2 ) 简化网络内部节点的服务对象。采用聚集传输控制，服务对象是流聚集 ( s t r e a ma g g r e g a t e ) 而非单流，单流信息只在网络边界保存和处理。 具体而言，网络边界节点根据用户的流规定( p r o f i l e ) 和资源预留信息将进 入网络的单流分类、整形、聚合为不同的流聚集，这种聚集信息存储在每个口 包头的d s ( d i f f e r e n t i a t e ds e r v i c e s ) 标记域( f i e l d ) 中，称为d s 标记( d i f f e r e n t i a t e d s e r v i c e sc o d e p o i n t ，d s c p t l 2 1 1 1 3 1 ) ；内部节点在调度转发口包时根据包头的d s c p 选择特定质量的调度转发服务，其外部特性称为逐点行为( p e r - h o p b e h a v i o r ， p h b ) 。网络边界对单流做分类聚合与网络内部对聚集流提供特定质量的调度转 发服务，这两个过程通过m 包头内的d s c p 协同起来。 i n t s e r v 和d i f f s e r v 的设计和实现有着完全不同的目标和原则，但这两种 i n t e r a c tq o s 标准都不能彻底的实现整个网络的端到端q o s 。为此，可考虑将 i n t s e r v ，r s v p 和d i f f s e r v 看作互相补充的技术，将其结合，互相协同，共同实 现端到端的q o s 提供机制。与此同时，多协议标签交换技术( m u l 卸r o t o c o ll a b e l 5 江苏大学硕士研究生学位论文 s w i t c h i n g ，m p l s ) 在缓存网络拥塞和保障服务质量方面具有独特的优势，它能 够同区分服务模型、集成服务模型以及a t m 网络相结合，用于实施流量工程。 虽然这些体系结构和技术并不能从根本上解决i n t e r n e t 上各种业务的o o s 保障， 但在很大程度上缓解了该问题。 2 。4 移动网络上提供o o s 保障概况 随着移动通信的不断发展和多媒体业务的日益普及，在移动网络上提供q o s 保障的研究逐渐成为一个热点。移动网络可以分为有基础设施支持的移动网络 ( 如蜂窝移动网络) 和不依赖基础设施的移动网络( 如a dh o e 网络) 。蜂窝移 动网络是一种通过基础设施( 如基站和中心节点) 进行集中控制和管理的移动网 络，其面临的主要技术难点是如何实现基础设施之间的平滑切换和移动主机的无 缝通信问题，对此已经进行了大量有意义的研究，并提出了包括小区切换机制和 移动口在内的大量的协议和相关技术。无线自组织网络( a d h o e 网络) 是一种 典型的不依赖基础设施的移动网络，与有线网络和传统蜂窝网络不同，对于拓扑 经常发生变化、带宽很窄、能源和内存非常受限的a dh o c 网络而言，提供o o s 支持是一个复杂而全新的课题。a dh o e 网络中的移动主机处理能力受限，通常 靠电池供电，并且容易受到干扰，无线信道的质量差并且网络带宽很有限。因此， 在a dh o e 网络中，如何合理地、有效地利用无线网络资源，提高数据传输性能， 进而为各种业务提供服务质量保障，即a dh o c 网络对o o s 的支持就成为一个较 为突出的问题。 2 5 排队模型综述 2 5 1 排队论的基本概念 排队论( o u e u e i n gs y s t e m ) 是运筹学的一个重要分支，它主要研究由于顾客 的到达和离开以及服务器的工作和休假，而引起的队伍的积累和消散问题。上世 纪3 0 年代初，丹麦数学家、电气工程师a ke r l a n g 把概率理论应用于电话通话问 题，从而开创了这门应用数学学科。3 0 年代中期，w f e l l e r 引进生灭过程，排队 论逐渐被数学界承认为- f - j 重要学科。从此，随着研究的深入，排队理论日益得 到了广泛的应用。人们发现通信系统，网络设计、计算机存储、物流调度等的各 种现象都可以通过排队模型来描述，同时应用相应排队理论的研究成果，可以指 6 江苏大学硕士研究生学位论文 导各种策略设计，给国民经济的发展带来了巨大的贡献。 排队系统由三部分组成：顾客、服务台、排队室，顾客是服务台的服务对象。 描述一个排队系统需要三个方面内容：( 1 ) 输入过程，( 2 ) 服务过程，( 3 ) 排队规则。 我们采用d g k e n d a l l 在1 9 5 3 年提出的记号：懈来描述一个排队系统，x 表 示相继到达时间间隔的概率分布，y 表示服务台对单个顾客服务时间的分布，z 表示服务台个数，a 表示系统容量( 排队室大小) ，m 一负指数分布，d 一定长 分布，g 一般分布，e x 一爱尔朗分布，f c f s 一先到先服务，l c f s 一后到先服务， p r i o r i t yq u e u e i n g _ 优先权排队等。 2 5 2 排队论的经典研究方法和成果 从二十世纪初e d a i l g 开创性地对通讯流进行研究至今，经典的排队理论己被 历代数学家充分地发展和研究。 经典的排队理论建立在模型满足马氏性的基础上，探讨平稳状态下系统的队 长、等待时间等统计特征量。一般来说，经典排队理论的求解方法主要有三类： 一为k e n d a l l 1 4 】提出的嵌入马氏链方法( e m b e d d e dm a r k o vc h a i n ) ，并被发展至 马氏更新方法。这种方法关键通过寻找过程的再生点或马氏点，运用马氏链的技 巧或建立更新方程来得到系统的统计特征量。二是c o x 提出的补充变量法【1 5 1 ，该 方法通过增加变量，构造向量马氏过程( v 1 衄) ，从而建立密度演化方程，并 求解各种统计特征量。三是n e u t s 提出的q b d 过程理论【1 6 1 ，他将生灭过程的方法 加以推广和引申，逐渐形成了一套可以处理一系列相关于p h ，m a p ( 马氏到达) , 7 及t b m a p ( 批马氏到达1 分布所构成的排队模型。尤其值得提出的是q b d 理论己形 成了完整的算法程序，为排队论模型的研究提供了较好的实证结果。 半个世纪以来经典排队理论的主要成果大致可总结如下【1 7 】：( 1 ) 得到了所有 单服务台排队模型在到达间隔和服务时间相互独立条件下的稳态解。( 2 ) 对于多 服务台排队系统，得到了在服务时间满足指数分布的稳态解。( 3 ) 优先排队模型 也得到了比较明确的结果，尤其在输入流满足泊松分布以及优先级固定的情况下 的排队。( 4 ) 开、闭网络系统也得到了部分重要结果。随着研究的深入，各种复 杂但符合实际的模型被大量研究，例如带休假的排队模型、拥有不耐烦顾客的排 队模型以及带有灾难的清除排队模型等等。 7 江苏大学硕士研究生学位论文 第三章有关排队理论及工具 本章主要讲述本课题研究中所用到的一些关于排队系统的基本理论，主要有 以下几部分组成：矩阵的k r o n e c k e r 积与k r o n e c k e r 和、p h 分布、马尔科夫到达过 程、生灭过程与拟生灭过程( q b d ) 、g i m 1 与m g 1 型结构矩阵、随机环境等。 下面将对这部分内容做简单介绍。 3 1 矩阵的k r o n e c k e r 积与k r o n e c k e r 和1 8 1 定义3 1 设a 、b 分别为，l lx m 2 和，l lx n 2 阶矩阵，它们的k r o n e c k e r 积ao 召 是嘲，l lx n h n 2 阶矩阵，写成分块形式： 40 b = 口1 1 。曰口1 2 b q 槐2 。b q 2 。曰口2 2 b 口2 他。召 口i ，l l l 曰 口鸭2 b a j ，i i 卅2 。b ( 3 1 ) 定义3 2 设4 、b 分别为m 和n 阶方阵，它们的k x o n e c k e r 和定义为： 4 0 b = a o l + j 二圆曰( 3 2 ) 其中l 和l 分别为n 和m 阶单位阵( 本文后面出现的指定阶数的单位阵均按照 此处的规定) 。 3 2p h 分布例2 0 1 定义3 3 设在有限状态空间e = n2 ，m ，m + q 上以m + l 为吸收状态的马 尔科夫( m a r k o v ) 过程为弘 ，t 田，其无穷小生成元为： q = 曙： ， 其中，r 为m x m 阶非奇异矩阵，对角元素为负，表示过程在某状态的滞留时间 特性，其余元素非负，表示状态转移概率与滞留时间的比率；m 维非零向量r o 满 足t e + t o = 0 ，并设m + l 维行向量( 口，+ 。) 为过程的初始概率向量，且有 口e + = 1 ；0 是适当维数元素全为零的列向量，p 是适当维数元素全为1 的列 向量( 本文后面出现的0 和e 均按照此处的规定) 。那么过程由初始状态出发最 8 江苏大学硕士研究生学位论文 终进入吸收状态所需时间的概率分布为： f = 1 6 1 e x p ( t 砷p ，x 0 ( 3 4 ) 由上式定义的概率分布为连续型p h 分布，( 口，r ) 称为f ( 力的一个表示。可 以看出，解析p h 分布的关键在于确定初始概率向量口和m x m 阶非奇异矩阵r 。 定义3 4 设在有限状态空间e = 凸2 ，m ，m + q 上的m a r k o v 链，肌+ 1 为吸收 状态，其转移概率矩阵表示成分块形式： p = h 1 ) ( 3 5 ) l o 、 其中，m 阶方阵z 是随机子阵，元素瓦o ，并有t p p ，列向量t o = ( i - d p ， j 为适当阶数的单位阵( 本文后面出现的，均按照此处的规定) ，i t 是非奇异 的。m a r k o v 链的初始分布是( 口，+ 1 ) ，满足口p + + l = 1 。上述m a r k o v 链吸收前 转移步数x 的分布，即： a 出弘母黪2 。 e h _ ：式定义的概率分布为离散型p h 分布。称( 口，d 是x 或分布 见，k 0 ) 的 m 阶p h 表示。 定理3 1p h 分布的有限混合仍是p h 分布。若慨，见，a ) 是概率分布， 有p h 表示 ( n r ( j ) ) ，则有限混合f = a f 1 + p 2 e + + 见最有p h 表示 ( 厂，l ) ，这里：7 = m 口( 1 ) ，p 2 口( 2 ) ，p k 口 ”，工= d i a g ( t ( 1 ) ，r ( 2 ) ，丁 ) ) 。 定理3 2p h 分布类在【0 ，+ 呦上全部概率分布的类中稠密。 3 3 马尔科夫到达过程2 1 1 2 2 m 3 1 马尔科夫到达过程( m a r k o va r r i v a lp r o c e s s ，m a p ) 由n e u t s 引入瞄】，它作 为泊松过程的推广，适应于矩阵解析方法和便于数值计算。设d 是具有m 个状 态的马氏过程的无穷小生成元，其平稳概率向量为万。考虑肌m 矩阵序列 见，k o ，它具有如下性质：矩阵圾，k 1 ，非负，矩阵0 0 的对角元为负且d o 非 奇异，并且有：d = 眈。 对于离散m a p ，d 是不可约随机矩阵，其不变概率向量为万。取，k 0 ， 9 江苏大学硕士研究生学位论文 是子随机矩阵，满足j d = e 巩，且矩阵j 一或非奇异。 k - - 0 定义3 5 1 考虑m 状态的马氏更新过程 ( q ，j 。) ，n 田，在每一状态转移时 刻对应于到达顾客数厶。随机变量 q ) 是标记状态，它在仙2 ，m ) 内取值， p 。) q 0 ) ，是逗留时刻，其中厶= o 。转移概率矩阵的第( i ，j ) 元素由下式给出： p r q 。= j f ，厶= | j ，以x i q t2 f ) 2j ：e x p ( d o u ) d u 见，k l ，x o ( 3 7 ) 以上定义是对于连续马尔科夫到达过程，若对于离散马尔科夫到达过程 ( d m a p ) ，相应的转移概率矩阵为：慨) 圾，k 1 ，1 ，0 。 m a p 是转移概率矩阵具有特殊形式的马尔科夫更新过程( 可能批量到达) ， 对单个到达情形所有的见，k 2 ，均为0 。特别地，p h 更新过程和马尔科夫调制 泊松过程( m a r k o v m o d u l a t e dp o i s s o np r o c e s s ，m m p p 2 5 】) 均为m a p ，其中对表 示为( 口，d 的p h 分布有：o o = t ，4 = t o 口( 其中t o = 一t p ) ，而对马尔科 夫调制泊松过程有：d o = d - a ，q = a ( 其中以是对角矩阵) 。 两个或多个m a p 的叠加是m a p 。若两个连续m a p 有参数矩阵 见( f ) ，i = 1 ，刁，则它们的叠加有参数矩阵： 圾= 见( 1 ) o 眈( 2 ) ，k 0( 3 8 ) 对离散m a p ，相应的公式为： k 眈= 或( 1 ) 呱，( 2 ) ，k o ( 3 9 ) v - - 0 这是由于在离散情形( 批量) 到达可能同时发生。 m a p 的稳态到达率为： 名= 万七珥p k - i 其中1 是随机矩阵d 的不变概率向量，即1 满足万d = 0 ，1 e = 1 。 3 4 生灭过程汹1 与拟生灭过程( 0 b o ) 川1 9 1 2 0 1 ( 3 1 0 ) 定义3 6 非负整数集 0 ，1 ， 上的m a r k o v 过程 x ( f ) ，t 0 ，如果其无穷小 生成元有下列三对角形式： 1 0 江苏大学硕士研究生学位论文 q = 一气凡 “弋五+ “) 鲍弋如+ 鲍) 五 以弋无+ 以) ( 3 1 1 ) 则称仁( f ) ，t 吣是一个生灭过程， 五，n 0 称为生率， 以，l 0 ) 称为灭率。 生灭过程的最基本特征是：在充分短的时间内，过程只能转移到相邻的状态 上，即当址斗o 时，有： p r y o + ) = 七i x ( t ) = j ，= 乃缸+ o ( 纷& + 0 ( 出) 1 - ( 乃+ , j ) a t + o ( a t ) o ( a t ) k = j + 1 扣j - 一l , j h ( 3 1 2 ) k j = r ， l k - j l _ 2 定义3 7 考虑一个二维m a r k o v 过程仁o ) ，( f ) ，有状态空间 q = ，d ；七0 ，j = 1 ，2 ，m ，状态集 ( 七，1 ) ， ，m ) 称为水平七，k 0 ，如果将 状态按字典顺序排序后，其生成元可写成下列分块三对角形： q =( 3 1 3 ) 则称弘( f ) ，( d ) 是一个拟生灭( q u a s ib i r t ha n dd e a t h ，简记q b d ) 过程，其中所 有子块是m 阶方阵，4 0 ) 有负的对角线元素，并且行和非正，暖和g 都是 非负阵，满足( 4 + g ) p = ( 4 + 嘎+ g ) p ，k 1 。 q b d 是经典生灭过程从一维状态空间到二维状态空间的推广。经典生灭过 程的状态x ( f ) = 七视为被分解成m 个子状态 ，1 ) ，( 后，m ) 。这一结构顺应了刻 画过程在多层次、多相位及变动参数情况下演化的要求。e v 觚s ( 1 9 6 7 ) 首先在排队 论分析中使用这类过程，w 甜l c a e ( 1 9 6 9 ) 在计算机系统研究中也遇到这类过程，并 由他引入了“拟生灭过程”这一术语。 迄今广泛使用的只是一类特殊的q b d ，即生成元q 中的子块从某一水平开 始不再发生变化的情形。这时，过程生成元如： 1 1 c 4 q 晟 g 以 d 4 历 a 墨 江苏大学硕士研究生学位论文 q = ag 置4 q 骂一l4 一lc f - 1 bac bac ( 3 1 4 ) 二十世纪7 0 年代以来，n e u t s ( 1 9 8 1 ) 等系统地发展了处理这种特殊q b d 的矩 阵分析方法，通过求率矩阵来求解。对于一般的q b d ，尚未建立起平行于经典 生灭过程的理论和处理方法。 3 5gi m 1 与m g 1 型结构矩阵侧2 7 1 定义3 8 设马氏链有状态空间e = f r o ，n 1 j ，l i u o ，n f 1 ，1 j 肌 ， 并且转移阵可写成下列分块形式： p = a 。 骂4a 垦44a 马4444 ( 3 1 5 ) 其中民是阶方阵，4 。是，l lx m 矩阵，色 1 ) ：是m x m i 矩阵，4 0 ) 是m 阶方阵，则称户为g i m 1 型结构阵。它是经典g i m i 排队中嵌入马尔科夫链的转 移阵从数值元素到矩阵子块元素的自然推广，并广泛出现于大量涉及p h 分布的 随机模型中。 定义3 9 设马氏链有状态空间e = f r o ，n 1 j 确) u u ，n i 1 ，1 j m ) ， 并且转移阵可写成下列分块形式： p = ( 3 1 6 ) 其中b o 是，l l 阶方阵，色( 七1 ) 和c o 分别是，l ix m 禾i m x m i 阵，4 o ) 是m 阶 方阵，则称户为g i m 1 型结构阵。它是经典m f i 1 排队中嵌入马尔科夫链的转 移阵从数值元素到矩阵子块元素的自然推广，并广泛出现于大量涉及p h 分布的 马4 4 4 ； 暖4 4 a ； 历a a 历d 江苏大学硕士研究生学位论文 随机模型中。 3 6 随机环境1 6 n 列 在经典随机模型理论中，系统的基本参数在运行过程中不再发生变化。然而， 这只是为了数学上便于处理，对随机模型提出的一种理想要求。事实上，许多随 机系统的基本参数本身，在系统运行过程中也随机地变化着。在运行过程中基本 参数也随机变化的系统，称为随机环境下的模型。 在数学上，通常用一个m a r k o v 更新过程描述随机环境。一个m a r k o v 更新过 程是一个二元序列 u 。，x 。) ；万0 ) ，。表示第n 次转移后达到的环境状态，取值 于有限环境状态集仉2 ，m ，x 。是环境过程在一个状态上的逗留时间。过程在 所有转移时刻上是无后效的。m a r k o v 更新过程由初始状态分布和转移率函数矩 阵q ( 力唯一决定。q ( 力是柳阶方阵，它的 ，h ) 元素是 q i 肋( x ) = p r ( 以= 办，叉乙x ) i 以= 七) ，1 七，h m ，x 0 q ( ) 是一个随机阵，它是m a r k o v 更新过程 u 。，邑) ；刀田的嵌) k m a r k o v 链 p 。；咒o ) 的转移概率矩阵。 在实际应用中主要使用m a r k o v 环境，它由一个m 状态的m a r k o v 过程来刻画。 一个周期循环的随机环境可描述如下：设有，个p h 分布：e ，江1 2 9 - - - r ，分别 有鸭阶p h 表示( 呸，霉) ，q p = 1 f _ 1 2 ，构造具有下列生成元的m 蝴过程： q = 互t 1 0 呸0 0 0 0 互r e o a 3 0 0 ： 000 霉一l 硝哆 f q 000 r r 0 1 7 ) 这个m a r k o v 过程刻画了一个，状态的循环随