排队论算法++(含ppt)课件.ppt

1,排队论及其应用Lecture2随机过程固定服务时间;2个服务器；无限个等待位；First-come-first-serve通常假定无限个等待位和FCFS，因此常用A/B/X描述一个排队系统比如，M/M/1，M/M/c，等等,24,排队系统常见的性能指标,客户等待时间客户在队列中等待的时间(Lq)客户在整个排队系统中消耗的时间(L)=队列等待时间+服务时间客户在排队系统中的累积程度等待队列中的客户数目(Nq)整个排队系统中的客户数目(N)=等待队列客户数目+正在接受服务的客户数目,空闲服务器服务器空闲的时间比例系统设计目标：提高服务器利用率，缩短客户等待时间等等，目标往往是相互矛盾的,25,26,G/G/1和G/G/c上的一般性结论,单位时间个客户到达，一个服务器单位时间能够服务个客户，客户到达时间间隔和服务时间任意分布，1个或者c个服务器，无限等待位。G/G/1或者G/G/c。定义1：客户不断累积，越来越多0，取值空间为0,1,2,.。如果X(t)=n，则称这个随机过程描述的系统在时间t处于状态En，n=0，1，2，.。如果出生速率n和死亡速率n满足以下条件，则称这个随机过程为生灭过程。状态转移只能EnEn+1，n=0，1，2，.。如果在时间t系统位于状态En，则在一小段时间t,t+h)发生状态转移EnEn+1的概率是nh+o(h)。如果在时间t系统位于状态En，则在一小段时间t,t+h)发生状态转移EnEn-1的概率是nh+o(h)。如果在时间t系统位于状态En，则在一小段时间t,t+h)发生其它转移的概率o(h)。,36,2019/12/13,37,可编辑,令Pn(t)=PX(t)=n在时间t+h，系统仍然在状态En的概率Pn(t+h)，有四种情况在时间t系统位于状态En，t,t+h)状态没有发生改变在时间t系统位于状态En-1，t,t+h)发生一个出生事件在时间t系统位于状态En+1，t,t+h)发生一个死亡事件在时间t系统位于上述状态以外的状态,38,情况1发生的概率情况2发生的概率情况3发生的概率情况4发生的概率综合4种情况,39,整理取h0对n1当n=0初始条件，t=0时，系统位于状态Ei，所有n=0，称为纯生过程，“人口爆炸”如果纯生过程n=，即为泊松过程所有n=0，称为纯灭过程，“种群消亡”,40,稳态生灭过程,当t，系统状态Pn(t)不随时间改变。称这种状态为稳态（Stationary或者steady-state）记，稳态下稳态下对任意一个状态，“进入该状态的概率=退出该状态的概率”,41,对状态0，对其它任意一个状态i，解线性方程组可得稳态生灭过程各状态概率当有无限个状态，生灭过程的稳态解为生灭过程有稳态接的必要和充分条件为,42,例一个单服务器排队系统，无等待位。假设客户到达是一个速率为的泊松过程，服务器服务时间服从指数分布，服务速率为，即单位时间服务1/个客户。求解：没有等待位，系统只有两个状态，“0”和“1”根据生灭过程方程,43,解微分方程稳态，t。直接求解稳态，用“流入=流出”计算稳态状态概率,44,45,例考虑一个单服务器的生灭过程系统中。系统只能够容纳3个客户，到达速率(012)=(3,2,1)，服务（死亡）速率为(123)=(1,2,2)。计算稳态下各状态概率，并计算有效到达速率和客户等待时间W求解生灭过程(p0,p1,p2,p4)=(0.117647,0.352941,0.352941,0.176471),例：在eMule网络上，文件被用户下载以后，该用户默认共享这个文件。考虑eMule网络上的一个文件，新的用户下载并共享这个文件可以视为一个速率为的泊松过程，；对每个共享源，由于各种原因（用户、系统、硬件），单位时间这个共享源不再共享这个文件的概率是。问这个文件有n个共享源的概率？n是任意非负整数。解答：这是一个生灭过程，出生率，新共享源出现服从泊松分布，i=死亡率，某时刻有i个共享源时的死亡率为i=i,46,当i，共享源增多当i，共享源减少,进一步处理eMule网络中文件的共享源个数取决于文件的流行程度，以及用户的共享意愿,47,这是一个泊松分布,马尔科夫过程,随机过程X(t),tT满足如下条件，则称它是一个马尔科夫过程，给定时间点集合ti，t1t2t3u，根据全概率公式，连续时间马尔科夫链的CK公式如下,63,矩阵形式,令u=0，令为连续时间马尔科夫链在时间t位于状态i的概率，为初始状态概率上式可以写为,64,连续时间马尔科夫链状态转移公式，与初始状态无关,65,如果令则有从泊松过程的定义可知，上式为泊松过程，泊松过程是一个连续时间马尔科夫过程,66,如果假设根据CK公式，令u=0,67,t0考虑所有初始状态，有矩阵形式为,68,对泊松过程。其中qj=，qrj=（r=j-1），其余为0考虑生灭过程,69,嵌入式马尔科夫链,嵌入式马尔科夫链：将连续时间马尔科夫链表示为离散时间马尔科夫链方式：每个事件的发生时间定义为离散的时间点例如，生灭过程的转移概率为,70,证明生灭过