负顾客到达的Geo/G/1重试排队系统及在通信网中的应用

彭懿

摘 要 研究了具有负顾客到达和一般重试时间的离散时间Geo/G/1重试排队系统. 分析了其嵌入马氏链，得到了系统稳态存在的充要条件， 利用补充变量法得到了系统演化的平衡方程组. 通过求解这些平衡方程得到了嵌入马氏链的平稳分布. 进而得到了一系列重要的排队性能指标. 最后将此排队系统应用到蜂窝移动通信通信网中.数值实例说明系统各参数对排队性能指标的影响程度.

关键词 离散时间排队系统；重试；负顾客；马尔可夫链；蜂窝移动通信网络

中图分类号 O122 文献标识码 A 文章编号 1000-2537（2015）04-0068-06

Abstract A discrete-time Geo/G/1 retrial queueing system with negative customers and general retrial times was studied. The Markov chain embedded to the considered queueing system was analyzed. The system state distribution as well as the orbit size and the system size distributions were obtained in terms of their generating functions， which yield exact expressions for different performance measures. Besides， the stability condition of the system was derived. Finally， an application to the cellular mobile communication network is provided and some numerical examples are provided to illustrate the impact of several parameters on some crucial performance characteristics of the system.

Key words discrete-time queueing system； retrial； negative customer； Markov chain； cellular mobile communication network

近年来， 越来越多的排队论学者感兴趣带负顾客的排队系统， 这是因为带负顾客的排队系统在计算机通信网络和制造系统中有广泛应用. 负顾客排队系统由 Gelenbe[1] 于1989年最先引入， 目的是用来模拟神经网络. 正顾客为通常意义上的顾客， 即到达系统接受服务后离开系统. 相对于正顾客而言， 负顾客通常不接受服务， 而对系统起破坏作用. 负顾客到达系统时若系统中无正顾客， 则离开系统而对系统无任何影响； 若有正顾客， 则按某种指定的移除法从系统中带走一个或多个正顾客， 同时其自身也离开系统. “负顾客”概念的引入带来各种各样的应用. 带负顾客的排队系统在计算机通信网络、生产制造系统、图像识别与处理和生物脑神经网络的模拟中有着非常重要的应用. 尤其在随机神经网络领域里， “负顾客”的概念起着非常关键的作用. 关于“负顾客”的理论和应用探讨的文献也随之越来越多[2-4]. 上世纪有关带负顾客排队系统的主要研究方法及成果可参见Gelenbe [5]和Artalejo[6]. 研究带负顾客的排队系统可以对生产制造系统， 信号机操作系统， 生物脑神经系统， 计算机病毒对计算机数据的影响， 通信网络中信元的转移与丢失， 电话网络中呼叫的转移与丢失等提供一定的优化依据. 关于带负顾客的离散时间排队系统的文献不多. Atencia[7]和 Moreno[8] 研究了带负顾客的离散时间Geo/Geo/1排队系统. Wang 和 Zhang[9]分析了带负顾客的离散时间Geo/Geo/1重试排队系统. Wu等人[10]考虑了一个顾客具有优先权和不耐烦性质的离散时间Geo/G/1重试排队系统. 本文将负顾客引入到重试时间为一般分布的离散时间Geo/G/1重试排队系统中，得到了一系列重要的排队性能指标，同时说明了该排队系统在蜂窝移动通信网络中的应用.

1 模型描述

考虑一个单服务台的离散时间重试排队系统. 在离散时间排队系统中， 时间轴被分割成等长的时隙. 在考虑的离散时间重试排队系统中的所有事件（例如顾客的到达和离去以及重试组中的顾客重试等） 都只能发生在时隙的分点处. 因此， 所有事件可能在同一时刻发生. 这样就必须规定这些事件发生的先后顺序. 这里考虑早到系统（EAS）. 假设时间轴被标记为0，1，…，m，…. 则正顾客和负顾客的到达、重试依次只能发生在时隙首端（m，m+）处， 而服务完成只能发生于时隙（m-，m）处. 这里m-表示时刻m前一瞬间， m+表示时刻m后一瞬间. 关于早到系统及相关概念可参见Hunter[11]报道.

正、负顾客的到达分别服从参数为p和q的几何到达过程. 服务台前无等待位置. 因此， 若正顾客到达系统时发现服务台空闲则立即接受服务， 服务结束后离开系统； 否则进入重试组排在队尾. 只允许重试组队首的顾客重试. 服务时间独立同分布服从一般分布{si}∞i=1， 其概率母函数和n阶矩分别为S（x）=∑∞i=1sixi和βn. 重试间隔时间服从一般分布{ri}∞i=0， 其概率母函数和数学期望分别为R（x）=∑∞i=1rixi和μ. 负顾客到达系统时带走一个正在服务的正顾客但自身不接受服务， 对重试组中的正顾客也无任何影响.

假设到达过程、服务过程和重试过程都是相互独立的.

3 数值实例及在蜂窝移动通信网络中的应用

这一节， 给出该排队系统在蜂窝移动通信网络中的一个应用以及几个数值实例. 蜂窝移动通信是采用蜂窝无线组网方式，在终端和网络设备之间通过无线通道连接起来，进而实现用户在活动中可相互通信. 其主要特征是终端的移动性，并具有越区切换和跨本地网自动漫游功能. 蜂窝移动通信业务是指经过由基站子系统和移动交换子系统等设备组成蜂窝移动通信网提供的话音、数据、视频图像等业务. 考虑包含蜂窝移动通信网络中的一个蜂窝， 假设其包含一个基站和一个提供服务的通道. 假设原始呼叫到达通道是服从参数为p的几何到达过程. 原始呼叫到达系统时， 若通道忙于处理呼叫则受阻而进入重试组. 此外， 通道在处理呼叫时并不很安全可靠. 有时候通道可能受到病毒或抑制信号的攻击， 一旦受到攻击， 则正在服务的呼叫将会损失. 假设“攻击”到达系统服从参数为p的几何到达过程. 由此可知蜂窝移动通信网络可用带负顾客的离散时间重试排队系统来模拟. 其中“攻击”可看作是负顾客. 考虑4个性能指标： 系统空的概率π0，0， 服务台忙的概率1（1，1）， 重试组平均队长L0和平均逗留时间W. 为了数值例子演示的方便， 假设服务时间服从参数为0.6的几何分布， 即S（x）=3x5-2x. 重试间隔时间也服从几何分布， 其概率母函数为R（x）=r01-0x. 这里选取任意的到达率：p=0.4. 当然， 以下所有例子中的参数值均在系统稳态条件成立的条件下选取. 数值结果由图1～图4给出. 在每个图中， 都画出了3根曲线分别对应于r0=0.2， 0.6 和 0.9.

参考文献：

[1] GELENBE E. Random neural networks with negative and positive signals and product form solution[J]. Neural Comput， 1989，25（1）：502-510.

[2] GELENBE E. Product-form queueing networks with negative and positive customers[J]. J Appl Probab， 1991，28（2）：656-663.

[3] GELENBE E. G-networks with triggered customer movement[J]. J Appl Probab， 1993，30（2）：742-748.

[4] GELENBE E. G-networks： a unifying model for neural and queueing networks[J]. Ann Oper Res， 1994，48（1）：433-461.

[5] GELENBE E. The first decade of G-networks[J]. Eur J Oper Res， 2000，126（1）：231-232.

[6] ARTALEJO J R. G-networks： A versatile approach for work removal in queueing networks[J]. Eur J Oper Res， 2000，126（1）：233-249.

[7] ATENCIA I， MORENO P. A single-server G-queue in discrete-time with geometrical arrival and service process[J]. Perform Eval， 2005，59（1）：85-97.

[8] ATENCIA I， MORENO P. The discrete-time Geo/Geo/1 queue with negative customers and disasters[J]. Comput Oper Res， 2004，31（6）：1537-1548.

[9] WANG J， ZHANG P. A discrete-time retrial queue with negative customers and unreliable server[J]. Comput Ind Eng， 2009，56（4）：1216-1222.

[10] WU J， WANG J， LIU Z. A discrete-time Geo/G/1 retrial queue with preferred and impatient customers[J]. Appl Math Model， 2013，37（8）：2552-2561.

[11] HUNTER J J. Mathematical techniques of applied probability， vol. 2， discrete-time models： techniques and applications[M]. New York：Academic Press， 1983.

[12] ATENCIA I， MORENO P. A discrete-time Geo/G/1 retrial queue with general retrial times[J]. Queueing Syst， 2004，48（1）：5-21.

（编辑 陈笑梅）