負顧客到達的Geo/G/1重試排隊系統及在通信網中的應用

彭 贅

（長沙師范學院初等教育系，中國長沙 410100）

負顧客到達的Geo/G/1重試排隊系統及在通信網中的應用

彭 贅*

（長沙師范學院初等教育系，中國長沙 410100）

研究了具有負顧客到達和一般重試時間的離散時間Geo/G/1重試排隊系統.分析了其嵌入馬氏鏈，得到了系統穩態存在的充要條件，利用補充變量法得到了系統演化的平衡方程組.通過求解這些平衡方程得到了嵌入馬氏鏈的平穩分布.進而得到了一系列重要的排隊性能指標.最后將此排隊系統應用到蜂窩移動通信通信網中.數值實例說明系統各參數對排隊性能指標的影響程度.

離散時間排隊系統；重試；負顧客；馬爾可夫鏈；蜂窩移動通信網絡

近年來，越來越多的排隊論學者感興趣帶負顧客的排隊系統，這是因為帶負顧客的排隊系統在計算機通信網絡和制造系統中有廣泛應用.負顧客排隊系統由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］報道.

假設到達過程、服務過程和重試過程都是相互獨立的.

2 模型分析及排隊性能指標

在時刻m+，系統的演化行為可由馬爾可夫過程｛Ym；m≥1｝來刻畫，其中Ym=（Cm，ξ0，m，ξ1，m，Nm），Cm根據服務臺空閑或忙而取值0或1，Nm表示重數組中的顧客數.若Cm=0且Nm＞0，則ξ0，m表示剩余重試時間.若Cm=1，則ξ1，m表示正在接受服務的顧客的剩余服務時間.

易知，過程｛Ym，m≥1｝是此排隊系統的嵌入馬氏鏈，其狀態空間為｛（0，0）；（0，i，k）：i≥1，k≥1；（1，i，k）：i≥1，k≥0｝.本文的主要工作是求馬爾可夫鏈｛Ym，m≥1｝的平穩分布：

令pyy′=P｛Ym+1=y′|Ym=y｝表示該鏈的一步轉移概率，則根據系統的運行規律有：

若i≥1，k≥1，

若i≥1，k≥0，

描述系統平穩分布的Kolmogorov方程為

其中δi，j是Kronecker記號.歸一化條件為

為求解方程（1）～（3），引入如下母函數：

將方程（5）和（6）兩邊同乘以xi，然后對i求和，有

在方程（7）和（8）中令x=1，得到

將方程（9）代入（10）并解出φ1（1，z），得到

將式（11）代入式（9）并解出φ0（1，z），得到

在式（7）中令x=1-pˉq，在式（8）中令x=（pz+ˉp）ˉq得

將式（11）和式（12）分別代入式（13）和式（14），得到

其中

由式（15）和式（16）得

最后，下述定理以母函數的形式給出了Kolmogorov方程組的解.通過這些母函數，可求得此嵌入馬氏鏈的平穩分布及其性質.

定理1此嵌入馬氏鏈平穩分布的概率母函數為

其中

證 證明上述定理只需將式（11），（12），（17）和（18）代入式（7）和式（8），即可推導出母函數φ0（x，z）和φ1（x，z）.最后再利用歸一化條件可確定常數π0，0.

注1 注意到系統穩態存在的條件是π0，0＞0，即

3 數值實例及在蜂窩移動通信網絡中的應用

圖1描繪了系統空的概率π0，0關于參數q的變化趨勢.π0，0是關于負顧客到達率q的遞增函數.負顧客到達率q對服務臺忙的概率φ1（1，1）的影響效果由圖2給出.π0，0是關于負顧客到達率q的遞增函數.此外，觀察到服務臺忙的概率與重試間隔時間無關.這是因為幾何分布具有無記憶性.

圖3說明了重試組中的平均顧客數關于參數q的變化趨勢.由圖3可以看出，重試組中的平均顧客數隨著負顧客到達率的增大而單調遞減，這個結論也是顯而易見的.必須說明的是當q趨近于1時，重試組平均隊長L0幾乎不受參數r0的影響.而且，隨著q的減小，不同的r0值對L0的影響效果變得較發散.

圖1 π0，0關于q的變化趨勢Fig.1 π0，0versus q for different r0

圖2 φ1（1，1）關于q的變化趨勢Fig.2 φ1（1，1）versus q for different r0

圖4給出了負顧客到達率對顧客平均逗留時間的影響效果.由圖4可知，顧客的平均逗留時間隨著負顧客到達率的增大而減少.這是由于負顧客的移除作用而引起的.

圖3 L0關于q的變化趨勢Fig.3 L0versus q for different r0

圖4 平均逗留時間關于q的變化趨勢Fig.4 W versus q for different r0

［1］ GELENBE E.Random neural networkswith 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］.JAppl Probab，1991，28（2）：656-663.

［3］ GELENBE E.G-networkswith triggered customermovement［J］.JAppl Probab，1993，30（2）：742-748.

［4］ GELENBE E.G-networks：a unifyingmodel 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 JOper Res，2000，126（1）：231-232.

［6］ ARTALEJO JR.G-networks：A versatile approach forwork removal in queueing networks［J］.Eur JOper 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 queuewith 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 queuewith preferred and impatient customers［J］.ApplMath Model，2013，37（8）：2552-2561.

［11］ HUNTER JJ.Mathematical techniques ofapplied probability，vol.2，discrete-timemodels：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.

（編輯 陳笑梅）

A Geo/G/1 Retrial Queueing System w ith Negative Customers and Its Application in Communication Networks

PENG Yi*
（Junior Education Department，Changsha Normal University，Changsha 410100，China）

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 aswell as the orbit size and the system size distributionswere obtained in terms of their generating functions，which yield exact expressions for different performancemeasures.Besides，the stability condition of the system was derived.Finally，an application to the cellularmobile 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.

discrete-time queueing system；retrial；negative customer；Markov chain；cellularmobile communication network

O122

A

1000-2537（2015）04-0068-06

10.7612/j.issn.1000-2537.2015.04.012*

2015-02-27

國家自然科學基金資助項目（11201489）

*通訊作者，E-mail：pengyiqueue@163.com