刘斌：今天的报告题目是重试排队系统及其应用，打算讲两个问题，第一个问题是重试排队系统中，重试成功的条件概率。 首先讲一讲什么是重试排队，图中所显示的是一些服务台，这个Primary customers，我们翻译成是原始顾客，原始顾客来自于外部，这些顾客试图得到服务，服务台的服务。当这些顾客到达时，如果服务台都在忙，那这些顾客就不能得到立刻的服务。那么，这些顾客呢，就会成为叫做重试顾客，Retrial customers。重试顾客呢，我们把他假想是在一个orbit里面，这些顾客呢，会在迟一点的时候呢，重新尝试进入系统，得到服务。 有关重试排队系统的研究呢，已经有一段时间了，它的应用背景呢，最初是从电话服务系统，电话服务中心，顾客请求获得服务，通过电话请求服务。那么如果所有的服务台或者接收人员都很忙，那么他们的请求呢就不能得到立刻的满足，那这些顾客呢，会在迟一些的时候会重新尝试，重新打定律，重新尝试。 那么现在呢，这种重试排队的问题呢，实际上它的应用背景已经不局限于这个电话服务系统，像计算机网络。典型的，比如说一个局域网，这个局域网里面有很多工作站，这些工作站它们之间需要communication，是通过一些传输媒介所实现的。那么，比如说有一个机器，有一个工作站想传输它的数据，它首先要获得这些传输媒介。当他们不能获得传输媒介的时候，他就不能得到马上的服务。他必须在迟一些的时候进行重试。所以，这里你就看到了重试现象在计算机网络中也找到了应用。 关于这方面研究的文献呢，有两本专著了。第一本是Falin和Tempeton在1997年的一本专著，在第二本是相对迟一些，十年以后，这个Astalejo和他的合作者在2008年的时候写了一本书。此外还有很多中述，我这里列了三篇中述，有关重试排队的一些细节的角色呢，我这里这个角色呢，是关于MMC系统，首先这个原始顾客，或者说Primary customers，他那个到达过程是一个过程，他的到达力一个常数纳姆达。那么在orbit里面那个Retry customers，他们retry的这个行为是独立的。也就是说，这个Retsyw customer，它会在一定的间隔时间以后，重新retry，直到他们得到服务，或者直到他们找到了一个空闲的服务台。这个间隔的retry时间呢，是指数分布，它的那个力呢是miu。 我们假设原始顾客和setry的重试顾客，他们的服务时间都是相同的，都是指数分布。服务力是，有关这个系统的数学描述，客化系统的状态，我们需要两个变量，一个就是大写的N，N（t）表示在orbit里面的重试顾客的数目。C呢，表示服务台，繁忙的服务台的个数。C和N加在一起，实际上就组成了一个过程，一个随即过程。实际上，它是一个连续时间的过程。 它的状态空间，很显然它的状态空间是一个无限状态空间。你看这个C是服务台的个数，因为总共有小c个顾客的服务台，所以说，忙的顾客台的个数是不可能超过C的，所以它的取值实际是0和C之间。但是在orbit里面的重试顾客的数呢，它可以是任意的非负整数。也就是说，它可以是没有重试顾客的，或者说有一个重试顾客，一直到无穷。 所以说呢，因为这个orbit中间呢，重试顾客数可以取到无穷。所以，它的状态空间是无限状态空间。关于这个系统的性能指标，比较主要的性能指标有下列，像对藏，也就是说在osbit里面的重试顾客的个数。还有等待时间，当系统处于稳态的时候，每个顾客的等待时间，从他的到达到获得服务这个间隔的时间。还有盲区，系统从不空开始，到再一次空，这个时间间隔叫盲区。 还有个就是说，叫做重试的次数，叫做Number of retrice。重复的次数是我们所关心的，我们以后想用这个大写的R去表示从事的次数，确切地说呢，它是在这个原始顾客最终得到服务，比如说原始顾客到达，由于没有服务台，他变成重试顾客。那么，重试顾客，最终呢，他要做一系列的重试，最终得到服务。那么，在他最终得到服务之前，他重试了多少次。这个变量，我们用大写的R来表示。 有关这个R的研究，1986年，FalinM/M/1系统，也就是说单个的服务台系统获得了一些结果。他那个结果呢，是关于R的某函数，也就是说，R是一个随机变量，这个随机变量的母函数的表达是，用这母函数来刻划这个随即变量的分布。我想展示一下它的结果，这个是一个母函数，这个母函数的表达，你看这里是含有Z1、Z2，而Z1、Z2的表达式呢，我这里已经给出了。而且呢，这个母函数本身实际写成一种积分形式，应该说是还是比较复杂的。你看这个积分的背脊函数，上面有A-1，B-1，而这个A本身又是Z的函数，Z1、Z2的函数。所以，可以想像，这么复杂的表达式，从这个表达式上你要获得

我们首先讲这个MM1系统，M1重试排队的系统。我用这个下标Ti表示间隔重试时间，也就是说DI减一个重试和第二次重试的间隔时间。我们用这个大写的SK表示从事的时刻，所以说，SK实际上是TN的求和。S0表示时间点0，这些是一些记号。我们用VK表示一个条件概率，这个条件概率呢，S0是0嘛，在S0这个时刻，ZS0是等于1，这就意味着，因为只有一个服务台，这就意味着服务台繁忙，1表示有一个服务台繁忙。那服务台繁忙，那个新到达的那个原始顾客就不能得到服务，他会变成重试顾客。 所以，条件呢，是CS0一直到CSKN就等于，也就是说前面的这个重试的K-1次重试都是不成功的，因为服务台都是处于忙状态，1表示忙状态。那么第K次的成功了，这个概率是多少，那就是说，概率CSK等于0，等于0表示这个服务台是空闲了，也就是说DK是尝试，在时刻SK这一点尝试，发现服务台是空闲的。那么，重试的顾客就获得了服务，就开始获得服务。所以，VK实际上是条件概率，是重试成功的，在第K次重试成功的条件概率，以至前K-1次都不成功。 所以，我们要研究这个条件概率，就是实际上等价于说我们要获得这个VK。那么，如果去获得这个VK呢，我们有没有一些记号，假设这个Na（0）表示贴了标签的顾客到达的时候，在这个orbit这里面已经有了重试顾客的次数。也就是说，你可以想想，贴了标签的顾客到达，此时此刻他看到的系统中，在这个orbit里已经有的。关于这个Na和C10，他们的联合分布我们是有表达式。这个表达式呢，在Falin的书上，1997年的书上有了。所以说这个联合分布是有表达式的，也就是说在时刻0这个时候，时刻0是我们加上了稳态时刻有一个贴了标签的顾客到达，看了系统是繁忙的，这个概率是有的，这是我们的一个起点。 那么我们把这个Na在0点的这个值，这个0点是起始点的值，我们把这个定义稍微延拖一下，延拖到他到达以后，然后一次不成功，两次不成功，延拖到一般的时间T上面。那么，我们可以说，通过这样的延拖，T就是在它还没有获得重试成功之前，都是有定义的，这是一些技术处理。 下面我们引入这个Vk，带着两个下标，这个是什么呢，大家比较一下这个句号跟以前的这个VK没有底下这个jn这个下标。那时候呢，这个条件部分，就是在这个竖杠后面的部分是相同的，也就是说前面的重试都不成功。里面的这个CSK，原先写VK的时候，都没有下标的时候，这个前面实际上是等于0的，现在我们一般的说，不仅把它细化，不仅是有0，还有1。而且我们把这个orbit里的重试顾客数也记录下来了，所以我们有这么一个表达式，VK、JN，很容易发现JN和VK的关系。VK是重试成功的条件概率，就是与之前面的条件不成功，DK是成功的，那么它是一个和了，里面是VK、ZN，0N，这个0表示服务台空闲，N表示在orbit里面有N个重试顾客。 他们有这么一个关系，所以说要想知道VK，我就必须知道VK、JN。那么，现在我们就把注意力就放在这上面，关键是这个VK、JN。VK、JN实际上是时间马斯链在一个特殊时代的状态，有很密切的联系。我们把注意力放在这些S0、S1、S2一直到SK这些时间点上去。我们在这些点上来看这个马斯过程，实际上我们会得到一个离散时间的马斯过程。那么，我们引入这个离散式的马斯过程，引入它的转移概率。我们用这个小写的P，带着两对下标，第一个是EM，第二个是JN。 那么表示什么呢，初始的状态是EM，也就是E表示服务台忙，M表示有M个重试顾客，J表示呢，J可以是0，可以是1，取不同的值。N表示有N个重试顾客，也就是说，我们要看这个两个，从上一次的重试时间到下一次的重试时间，系统状态转移的概率，是用这个小P来表示，带两个下标了。这个小P可以写成一个，因为你想两次重试的时间间隔是指数分布，从指数分布密度嘛，我后面这个积分表达里面的miu乘上1的，负的miu t，所以我们可以写出这个转移概率的几种表达式。 那么通过简单的推导，会发现这个转移概率实际上miu乘上P，这个P心实际上是拉不拉斯变化，实际上是下列函数的拉不拉斯变换。拉布拉丝变换实际上是连续马克夫过程状态转移的拉布拉斯变化。所以，你看这个这么一个函数，P那些下标后面的一个T函数的变换。所以，我们待会儿要研究这个连续时间马斯过程的生态节。原因是我们需要获得这个P心，因为P心和原来的那个P有很紧密的联系。