《排队论大学课件11_马尔科夫排队网络》由会员分享，可在线阅读，更多相关《排队论大学课件11_马尔科夫排队网络（23页珍藏版）》请在金锄头文库上搜索。
1、第七章第七章 马尔可夫排队网络马尔可夫排队网络 l 三种队长分布的关系 l Burke定理 l 开马尔可夫排队网络 l 闭马尔可夫排队网络 到达与离开时的队长分布的关系到达与离开时的队长分布的关系 l下面我们研究三种时刻队长分布的关系 lpn-=P(顾客到达时系统中已有n个顾客) lPn=P(N=n)=平稳分布队长为n的概率 lpn+=P(顾客离开系统时系统还有n个顾客的 概率) 到达与离开时的队长分布的关系到达与离开时的队长分布的关系 lG/G/1系统pn- =pn+ N(t) t n+1 n 跟踪N(t)实际走过的一条路线 到达与离开时的队长分布的关系到达与离开时的队长分布的关系 l 假定
2、从状态n上跳到状态n+1的次数为An(t) 从状态n+1下跳到状态n的次数为Dn(t) l 由于到达与离去是一个一个发生的，并且n-n+1与n+1- n是交错发生的。所以到t时刻为止，An(t)与Dn(t)至多相 差1 l 设A(t)、D(t)为从任何状态开始上跳一步的总次数和下跳 一步的总次数，在统计平衡条件下，有： 到达与离开时的队长分布的关系到达与离开时的队长分布的关系 M/GM/G系统到达时刻看到的的队长分布系统到达时刻看到的的队长分布 与队长分布的关系与队长分布的关系 l M/G系统有pn-(t)= pn(t)，即任意时刻，到达的顾客看到的队长分布等 于系统队长的分布 l 证明 令A
3、(t, t+t)表示在t, t+t)时间时间 内到达了一个顾顾客，则则 因为输为输 入流是泊松流，所以A(t, t+t)发发生的概率是 t+o(t)，与 N(t)=n这这个事件无关。所以 结论结论 lG/G排队系统pn- =pn+ 即到达的顾客与离开的顾客所看到的队长 分布是相等的 lM/G排队系统中pn- =pn+ =pn 即顾客为泊松流到达的排队系统中，到达 的顾客与离开的顾客看到的队长分布与系 统的队长分布都相等 马尔可夫排队网络马尔可夫排队网络 l 我们前面学习的情况，都是顾客只请求一种服务，服务完 离去，这种系统叫做单节点系统或叫单节点网络。 l 如果一个排队系统只是一个节点，那么多
4、个节点就可以组 成一个排队网络。每个节点都含有一个服务机构和排队机 构，是一个简单的排队系统，当顾客离开某个排队系统节 点就进入下一个节点。例如数据包在通信网中传输 12 3 到达 到达 到达 离开 离开 离开 排队网络(注意不要与状态流图混淆) 马尔可夫排队网络马尔可夫排队网络 l定义： 马尔可夫排队网络指的是各节点外部到达顾客流 是泊松流，各节点的服务时间是负指数分布的网 络系统。 l关注的问题： 网络结构描述了节点之间的允许的转移 使用随机过程对顾客流的描述例如离开节点i的 顾客都立即进入节点i1，则前者的顾客离去间 隔时间就是后者的顾客到达间隔时间 马尔可夫排队网络马尔可夫排队网络 一
5、个二节点的级联网络一个二节点的级联网络 l 举例，假定1号节点是一个M/M/1排队系统 2号节点的顾客输入流就是1号节点的顾客输出流 考虑1号节点顾客离开的间隔时间，假定其服从分布d(t) ，d(t)的拉普拉斯变换为D*(x)。1号节点的服务时间分布 的拉普拉斯变换为B*(x)，顾客到达间隔时间分布的的拉 普拉斯变换为A*(x)。有： 12 ？ 马尔可夫排队网络马尔可夫排队网络 一个二节点的级联网络一个二节点的级联网络 l 情况一：前面顾客离开后，后面接着有顾客来接受服务 两顾客离开的间隔时间就是后面顾客的服务时间 l 情况二：前面顾客离开后，系统顾客为0 两顾客离开的间隔时间是后面顾客到达的
6、间隔时间后面顾客 服务的时间 后一个顾客前一个顾客 前一个顾客后一个顾客 马尔可夫排队网络马尔可夫排队网络 一个二节点的级联网络一个二节点的级联网络 l 情况一出现的概率顾客离开时发现系统中有顾客的概率 顾客到达时发现系统中有顾客的概率统计平衡时系统 队长不为0的概率 l 同理，情况二出现的概率1- l 所以 l 可见，M/M/1排队系统的顾客输出流是泊松流，并且强度 与其输入流强度相同 马尔可夫排队网络马尔可夫排队网络BurkeBurke定理定理 lBurke定理 在平稳状态下，M/M/n排队系统的顾客离开的过 程为泊松过程，离开率等于到达率。并且M/M/n 是唯一具有此种性质的FCFS排队
7、系统。 马尔可夫排队网络马尔可夫排队网络 一个二节点的级联网络一个二节点的级联网络 l 因此，此时再看2号节点 2号节点的输入流是强度为的泊松流，所以2号节点也是 一个普通的M/M/1排队系统，并且可以与1号节点独立分 开讨论。 lBurke定理： 多个M/M/n排队系统连接在一起所形成的网络， 每个节点能够依旧保持原本M/M/n的特性。 12 泊松流 开马尔可夫排队网络开马尔可夫排队网络 l （Jackson定理）假定排队网络由N个节点组成，且满足如 下条件 每个节点都是一个./M/n排队系统，节点i有ni个服务窗，每个服 务窗独立工作，平均服务时间为1/i。 顾客从网络外部到达第i个节点的
8、流是参数为i的泊松流 在节点i服务完的顾客以概率pij到达节点j或者以 的概率 离开网络系统 设节点i的总平均到达率为i（包括网络外部的到达率i和其他节 点到达节点i的全部到达率之和），则i满足方程组 设在节点i处有ki个顾客，则系统的状态记做（k1,k2,kN）设在 统计平衡条件下的概率为P(k1,k2,kN),如果iniui l 则 pi(ki)是节点i在统计平衡条件下有ki个顾客的概率。 开马尔可夫排队网络开马尔可夫排队网络 lJackson定理的直观理解 N个节点的马尔可夫网络，如果把到达节点i的合 流理解成是强度为i的泊松流，则节点i就是一个 独立的排队系统，从而整个网络的状态概率是
9、各 个节点相应状态概率的乘积。 求解开马尔可夫排队网络模型的步骤： l求解各个节点的顾客平均到达率 l分别求解各个节点的目标参量 开马尔可夫排队网络例题开马尔可夫排队网络例题 l 多重程序二阶段循环模型。在多重程序的计算机系统中， 一些程序同时存在主存储器中，每一程序有中央处理机指 令和输入输出指令组成。当输入输出器处理某一程序的输 入输出时，直到它完成这种输入或输出此程序才执行中央 处理机处理的其他程序指令。这种程序就是这样在中央处 理机与输入输出器之间循环，直到全部完成为止。每一程 序在存储器中处于四种状态之一：等待中央处理机处理， 在中央处理机中执行，等待输入输出器处理，在输入输出 器中
10、执行。表示如图 输入输出器中央处理机 1 2 p 1p 开马尔可夫排队网络例题开马尔可夫排队网络例题 l 程序到达是参数为的泊松流，又中央处处理机、输输入输输出 器的工作时间时间 都是负负指数分布，参数为为1、2，中央处处 理机和输输入输输出器前均设设有排队队等待位置。当一程序在 中央处处理机上处处理完成时时，或以概率p离开系统统，或以概 率q1p在输输入输输出器前排队队等待。当在输输入输输出器 处处完成服务务后，该该程序再反馈馈到中央处处理机前排队队等待 。这样这样 循环环反复，直到全部操作完为为止。此处处假定有无 限个等待位置，试试求相应应的目标标参量 输入输出器中央处理机 1 2 p 1
11、p 闭马尔可夫排队网络闭马尔可夫排队网络 l 什么是闭马尔可夫排队网络 如果一个马尔可夫排队网络没有从网络外部的到 达流，也不向网络外部输出。整个网络内共有K 个顾客保持不变，顾客只是在网络内部节点之间 移动。 闭马尔可夫排队网络闭马尔可夫排队网络 l 设网络有N个节点组成，满足下面的条件： 每个节点都是一个./M/n排队系统，节点i有ni个服务 窗，每个服务窗独立工作，平均服务时间为1/i。 顾客只能在网络内部节点之间转移，不能走出网络 ，网络外部也无顾客到达，系统中由K个顾客。 顾客在节点i服务完后转移到节点j的概率是pij 设节点i的总平均到达率为i ，则i满足方程组 设 闭马尔可夫排队网络闭马尔可夫排队网络 证明过程略，最终结果为 随堂测验随堂测验 4 4 l 一个三节点的马尔可夫排队网络，如图，1215（分 组/秒）, 320（分组/秒）。分组在各节点间的转发情况 可表示为：， l 每一节点服务速率U50（分组/秒），求： 网络中平均分组数 每一分组在网络中的总平均停留时间 平均吞吐量 12 3 12 3 知识回顾知识回顾 Knowledge Knowledge ReviewReview
