負(fù)顧客到達(dá)的Geo/G/1重試排隊(duì)系統(tǒng)及在通信網(wǎng)中的應(yīng)用

彭懿

摘 要 研究了具有負(fù)顧客到達(dá)和一般重試時(shí)間的離散時(shí)間Geo/G/1重試排隊(duì)系統(tǒng). 分析了其嵌入馬氏鏈，得到了系統(tǒng)穩(wěn)態(tài)存在的充要條件， 利用補(bǔ)充變量法得到了系統(tǒng)演化的平衡方程組. 通過(guò)求解這些平衡方程得到了嵌入馬氏鏈的平穩(wěn)分布. 進(jìn)而得到了一系列重要的排隊(duì)性能指標(biāo). 最后將此排隊(duì)系統(tǒng)應(yīng)用到蜂窩移動(dòng)通信通信網(wǎng)中.數(shù)值實(shí)例說(shuō)明系統(tǒng)各參數(shù)對(duì)排隊(duì)性能指標(biāo)的影響程度.

關(guān)鍵詞 離散時(shí)間排隊(duì)系統(tǒng)；重試；負(fù)顧客；馬爾可夫鏈；蜂窩移動(dòng)通信網(wǎng)絡(luò)

中圖分類(lèi)號(hào) O122 文獻(xiàn)標(biāo)識(shí)碼 A 文章編號(hào) 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

近年來(lái)， 越來(lái)越多的排隊(duì)論學(xué)者感興趣帶負(fù)顧客的排隊(duì)系統(tǒng)， 這是因?yàn)閹ж?fù)顧客的排隊(duì)系統(tǒng)在計(jì)算機(jī)通信網(wǎng)絡(luò)和制造系統(tǒng)中有廣泛應(yīng)用. 負(fù)顧客排隊(duì)系統(tǒng)由 Gelenbe[1] 于1989年最先引入， 目的是用來(lái)模擬神經(jīng)網(wǎng)絡(luò). 正顧客為通常意義上的顧客， 即到達(dá)系統(tǒng)接受服務(wù)后離開(kāi)系統(tǒng). 相對(duì)于正顧客而言， 負(fù)顧客通常不接受服務(wù)， 而對(duì)系統(tǒng)起破壞作用. 負(fù)顧客到達(dá)系統(tǒng)時(shí)若系統(tǒng)中無(wú)正顧客， 則離開(kāi)系統(tǒng)而對(duì)系統(tǒng)無(wú)任何影響； 若有正顧客， 則按某種指定的移除法從系統(tǒng)中帶走一個(gè)或多個(gè)正顧客， 同時(shí)其自身也離開(kāi)系統(tǒng). “負(fù)顧客”概念的引入帶來(lái)各種各樣的應(yīng)用. 帶負(fù)顧客的排隊(duì)系統(tǒng)在計(jì)算機(jī)通信網(wǎng)絡(luò)、生產(chǎn)制造系統(tǒng)、圖像識(shí)別與處理和生物腦神經(jīng)網(wǎng)絡(luò)的模擬中有著非常重要的應(yīng)用. 尤其在隨機(jī)神經(jīng)網(wǎng)絡(luò)領(lǐng)域里， “負(fù)顧客”的概念起著非常關(guān)鍵的作用. 關(guān)于“負(fù)顧客”的理論和應(yīng)用探討的文獻(xiàn)也隨之越來(lái)越多[2-4]. 上世紀(jì)有關(guān)帶負(fù)顧客排隊(duì)系統(tǒng)的主要研究方法及成果可參見(jiàn)Gelenbe [5]和Artalejo[6]. 研究帶負(fù)顧客的排隊(duì)系統(tǒng)可以對(duì)生產(chǎn)制造系統(tǒng)， 信號(hào)機(jī)操作系統(tǒng)， 生物腦神經(jīng)系統(tǒng)， 計(jì)算機(jī)病毒對(duì)計(jì)算機(jī)數(shù)據(jù)的影響， 通信網(wǎng)絡(luò)中信元的轉(zhuǎn)移與丟失， 電話(huà)網(wǎng)絡(luò)中呼叫的轉(zhuǎn)移與丟失等提供一定的優(yōu)化依據(jù). 關(guān)于帶負(fù)顧客的離散時(shí)間排隊(duì)系統(tǒng)的文獻(xiàn)不多. Atencia[7]和 Moreno[8] 研究了帶負(fù)顧客的離散時(shí)間Geo/Geo/1排隊(duì)系統(tǒng). Wang 和 Zhang[9]分析了帶負(fù)顧客的離散時(shí)間Geo/Geo/1重試排隊(duì)系統(tǒng). Wu等人[10]考慮了一個(gè)顧客具有優(yōu)先權(quán)和不耐煩性質(zhì)的離散時(shí)間Geo/G/1重試排隊(duì)系統(tǒng). 本文將負(fù)顧客引入到重試時(shí)間為一般分布的離散時(shí)間Geo/G/1重試排隊(duì)系統(tǒng)中，得到了一系列重要的排隊(duì)性能指標(biāo)，同時(shí)說(shuō)明了該排隊(duì)系統(tǒng)在蜂窩移動(dòng)通信網(wǎng)絡(luò)中的應(yīng)用.

1 模型描述

考慮一個(gè)單服務(wù)臺(tái)的離散時(shí)間重試排隊(duì)系統(tǒng). 在離散時(shí)間排隊(duì)系統(tǒng)中， 時(shí)間軸被分割成等長(zhǎng)的時(shí)隙. 在考慮的離散時(shí)間重試排隊(duì)系統(tǒng)中的所有事件（例如顧客的到達(dá)和離去以及重試組中的顧客重試等） 都只能發(fā)生在時(shí)隙的分點(diǎn)處. 因此， 所有事件可能在同一時(shí)刻發(fā)生. 這樣就必須規(guī)定這些事件發(fā)生的先后順序. 這里考慮早到系統(tǒng)（EAS）. 假設(shè)時(shí)間軸被標(biāo)記為0，1，…，m，…. 則正顧客和負(fù)顧客的到達(dá)、重試依次只能發(fā)生在時(shí)隙首端（m，m+）處， 而服務(wù)完成只能發(fā)生于時(shí)隙（m-，m）處. 這里m-表示時(shí)刻m前一瞬間， m+表示時(shí)刻m后一瞬間. 關(guān)于早到系統(tǒng)及相關(guān)概念可參見(jiàn)Hunter[11]報(bào)道.

正、負(fù)顧客的到達(dá)分別服從參數(shù)為p和q的幾何到達(dá)過(guò)程. 服務(wù)臺(tái)前無(wú)等待位置. 因此， 若正顧客到達(dá)系統(tǒng)時(shí)發(fā)現(xiàn)服務(wù)臺(tái)空閑則立即接受服務(wù)， 服務(wù)結(jié)束后離開(kāi)系統(tǒng)； 否則進(jìn)入重試組排在隊(duì)尾. 只允許重試組隊(duì)首的顧客重試. 服務(wù)時(shí)間獨(dú)立同分布服從一般分布{si}∞i=1， 其概率母函數(shù)和n階矩分別為S（x）=∑∞i=1sixi和βn. 重試間隔時(shí)間服從一般分布{ri}∞i=0， 其概率母函數(shù)和數(shù)學(xué)期望分別為R（x）=∑∞i=1rixi和μ. 負(fù)顧客到達(dá)系統(tǒng)時(shí)帶走一個(gè)正在服務(wù)的正顧客但自身不接受服務(wù)， 對(duì)重試組中的正顧客也無(wú)任何影響.

假設(shè)到達(dá)過(guò)程、服務(wù)過(guò)程和重試過(guò)程都是相互獨(dú)立的.

3 數(shù)值實(shí)例及在蜂窩移動(dòng)通信網(wǎng)絡(luò)中的應(yīng)用

這一節(jié)， 給出該排隊(duì)系統(tǒng)在蜂窩移動(dòng)通信網(wǎng)絡(luò)中的一個(gè)應(yīng)用以及幾個(gè)數(shù)值實(shí)例. 蜂窩移動(dòng)通信是采用蜂窩無(wú)線組網(wǎng)方式，在終端和網(wǎng)絡(luò)設(shè)備之間通過(guò)無(wú)線通道連接起來(lái)，進(jìn)而實(shí)現(xiàn)用戶(hù)在活動(dòng)中可相互通信. 其主要特征是終端的移動(dòng)性，并具有越區(qū)切換和跨本地網(wǎng)自動(dòng)漫游功能. 蜂窩移動(dòng)通信業(yè)務(wù)是指經(jīng)過(guò)由基站子系統(tǒng)和移動(dòng)交換子系統(tǒng)等設(shè)備組成蜂窩移動(dòng)通信網(wǎng)提供的話(huà)音、數(shù)據(jù)、視頻圖像等業(yè)務(wù). 考慮包含蜂窩移動(dòng)通信網(wǎng)絡(luò)中的一個(gè)蜂窩， 假設(shè)其包含一個(gè)基站和一個(gè)提供服務(wù)的通道. 假設(shè)原始呼叫到達(dá)通道是服從參數(shù)為p的幾何到達(dá)過(guò)程. 原始呼叫到達(dá)系統(tǒng)時(shí)， 若通道忙于處理呼叫則受阻而進(jìn)入重試組. 此外， 通道在處理呼叫時(shí)并不很安全可靠. 有時(shí)候通道可能受到病毒或抑制信號(hào)的攻擊， 一旦受到攻擊， 則正在服務(wù)的呼叫將會(huì)損失. 假設(shè)“攻擊”到達(dá)系統(tǒng)服從參數(shù)為p的幾何到達(dá)過(guò)程. 由此可知蜂窩移動(dòng)通信網(wǎng)絡(luò)可用帶負(fù)顧客的離散時(shí)間重試排隊(duì)系統(tǒng)來(lái)模擬. 其中“攻擊”可看作是負(fù)顧客. 考慮4個(gè)性能指標(biāo)： 系統(tǒng)空的概率π0，0， 服務(wù)臺(tái)忙的概率1（1，1）， 重試組平均隊(duì)長(zhǎng)L0和平均逗留時(shí)間W. 為了數(shù)值例子演示的方便， 假設(shè)服務(wù)時(shí)間服從參數(shù)為0.6的幾何分布， 即S（x）=3x5-2x. 重試間隔時(shí)間也服從幾何分布， 其概率母函數(shù)為R（x）=r01-0x. 這里選取任意的到達(dá)率：p=0.4. 當(dāng)然， 以下所有例子中的參數(shù)值均在系統(tǒng)穩(wěn)態(tài)條件成立的條件下選取. 數(shù)值結(jié)果由圖1～圖4給出. 在每個(gè)圖中， 都畫(huà)出了3根曲線分別對(duì)應(yīng)于r0=0.2， 0.6 和 0.9.

參考文獻(xiàn)：

[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.

（編輯 陳笑梅）