排队论11课件.pptVIP

第七章 马尔可夫排队网络 到达与离开时的队长分布的关系 下面我们研究三种时刻队长分布的关系 pn-=P(顾客到达时系统中已有n个顾客) Pn=P(N=n)=平稳分布队长为n的概率 pn+=P(顾客离开系统时系统还有n个顾客的概率) 到达与离开时的队长分布的关系 G/G/1系统pn- =pn+ 到达与离开时的队长分布的关系 假定从状态n上跳到状态n+1的次数为An(t) 从状态n+1下跳到状态n的次数为Dn(t) 由于到达与离去是一个一个发生的，并且n-n+1与n+1-n是交错发生的。所以到t时刻为止，An(t)与Dn(t)至多相差1 设A(t)、D(t)为从任何状态开始上跳一步的总次数和下跳一步的总次数，在统计平衡条件下，有： 到达与离开时的队长分布的关系 M/G系统到达时刻看到的的队长分布与队长分布的关系 M/G系统有pn-(t)= pn(t)，即任意时刻，到达的顾客看到的队长分布等于系统队长的分布 证明 令A(t, t+?t)表示在[t, t+?t)]时间内到达了一个顾客，则 因为输入流是泊松流，所以A(t, t+?t)发生的概率是 ??t+o(?t)，与N(t)=n这个事件无关。所以 结论 G/G排队系统pn- =pn+ 即到达的顾客与离开的顾客所看到的队长分布是相等的 M/G排队系统中pn- =pn+ =pn 即顾客为泊松流到达的排队系统中，到达的顾客与离开的顾客看到的队长分布与系统的队长分布都相等 马尔可夫排队网络 我们前面学习的情况，都是顾客只请求一种服务，服务完离去，这种系统叫做单节点系统或叫单节点网络。 如果一个排队系统只是一个节点，那么多个节点就可以组成一个排队网络。每个节点都含有一个服务机构和排队机构，是一个简单的排队系统，当顾客离开某个排队系统节点就进入下一个节点。例如数据包在通信网中传输 马尔可夫排队网络 定义： 马尔可夫排队网络指的是各节点外部到达顾客流是泊松流，各节点的服务时间是负指数分布的网络系统。 关注的问题： 网络结构－描述了节点之间的允许的转移 使用随机过程对顾客流的描述－例如离开节点i的顾客都立即进入节点i＋1，则前者的顾客离去间隔时间就是后者的顾客到达间隔时间 马尔可夫排队网络一个二节点的级联网络 举例，假定1号节点是一个M/M/1排队系统 2号节点的顾客输入流就是1号节点的顾客输出流 考虑1号节点顾客离开的间隔时间，假定其服从分布d(t)，d(t)的拉普拉斯变换为D*(x)。1号节点的服务时间分布的拉普拉斯变换为B*(x)，顾客到达间隔时间分布的的拉普拉斯变换为A*(x)。有： 马尔可夫排队网络一个二节点的级联网络 情况一：前面顾客离开后，后面接着有顾客来接受服务 两顾客离开的间隔时间就是后面顾客的服务时间 情况二：前面顾客离开后，系统顾客为0 两顾客离开的间隔时间是后面顾客到达的间隔时间＋后面顾客服务的时间 马尔可夫排队网络一个二节点的级联网络 情况一出现的概率＝顾客离开时发现系统中有顾客的概率＝顾客到达时发现系统中有顾客的概率＝统计平衡时系统队长不为0的概率＝? 同理，情况二出现的概率＝1- ? 所以 可见，M/M/1排队系统的顾客输出流是泊松流，并且强度与其输入流强度相同 马尔可夫排队网络－Burke定理 Burke定理 在平稳状态下，M/M/n排队系统的顾客离开的过程为泊松过程，离开率等于到达率。并且M/M/n是唯一具有此种性质的FCFS排队系统。 马尔可夫排队网络一个二节点的级联网络 因此，此时再看2号节点 2号节点的输入流是强度为?的泊松流，所以2号节点也是一个普通的M/M/1排队系统，并且可以与1号节点独立分开讨论。 Burke定理： 多个M/M/n排队系统连接在一起所形成的网络，每个节点能够依旧保持原本M/M/n的特性。 开马尔可夫排队网络 （Jackson定理）假定排队网络由N个节点组成，且满足如下条件 每个节点都是一个./M/n排队系统，节点i有ni个服务窗，每个服务窗独立工作，平均服务时间为1/?i。 顾客从网络外部到达第i个节点的流是参数为?i的泊松流 在节点i服务完的顾客以概率pij到达节点j或者以 的概率离开网络系统 设节点i的总平均到达率为?i（包括网络外部的到达率?i和其他节点到达节点i的全部到达率之和），则?i满足方程组 设在节点i处有ki个顾客，则系统的状态记做（k1,k2,…,kN）设在统计平衡条件下的概率为P(k1,k2,…,kN),如果?iniui 则 pi(ki)是节点i在统计平衡条件下有ki个顾客的概率。 开马尔可夫排队网络 Jackson定理的直观理解 N个节点的马尔可夫网络，如果把到达节点i