周宗好，石志巖

（1.黃山學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，安徽黃山245041；2.江蘇大學(xué)理學(xué)院，江蘇鎮(zhèn)江212013）

無(wú)線通信網(wǎng)絡(luò)中的M/G/1重試排隊(duì)模型

周宗好1，石志巖2

（1.黃山學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，安徽黃山245041；2.江蘇大學(xué)理學(xué)院，江蘇鎮(zhèn)江212013）

為了使無(wú)線網(wǎng)絡(luò)的節(jié)點(diǎn)盡可能的節(jié)約電能，本文討論睡眠喚醒機(jī)制下網(wǎng)絡(luò)節(jié)點(diǎn)的動(dòng)態(tài)排隊(duì).當(dāng)無(wú)線網(wǎng)絡(luò)節(jié)點(diǎn)中緩存隊(duì)列變空時(shí)，節(jié)點(diǎn)即不發(fā)送也不接收數(shù)據(jù)包并且進(jìn)入一段隨機(jī)長(zhǎng)度的休假期.為了使模型具有更一般的適用性，考慮節(jié)點(diǎn)對(duì)數(shù)據(jù)包傳輸時(shí)間分布為一般分布.基于上述要求本文研究了帶有空竭服務(wù)的單重休假、一般重試時(shí)間的M/G/1排隊(duì)系統(tǒng)，求得系統(tǒng)穩(wěn)態(tài)存在的充分必要條件.利用向量馬氏過(guò)程(VMP)的方法求得系統(tǒng)的各項(xiàng)排隊(duì)指標(biāo).求解的結(jié)論可用于優(yōu)化無(wú)線通信網(wǎng)絡(luò)的各項(xiàng)性能指標(biāo).

無(wú)線通信網(wǎng)絡(luò)；穩(wěn)態(tài)分布；馬氏鏈；空竭服務(wù)

1引言

無(wú)線網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)電能的需求也在不斷地提高，因此采用有效的功率管理(powermanagement)機(jī)制使節(jié)點(diǎn)降低能耗是無(wú)線網(wǎng)絡(luò)設(shè)計(jì)首先需要考慮的因素[1].另外，作為無(wú)線網(wǎng)絡(luò)的另一個(gè)重要因素，網(wǎng)絡(luò)的QoS也必須得到有效的保障，降低網(wǎng)絡(luò)節(jié)點(diǎn)能耗和保障網(wǎng)絡(luò)QoS的折衷問(wèn)題已經(jīng)成為近幾年無(wú)線網(wǎng)絡(luò)中的研究熱點(diǎn)之一，本文就無(wú)線通信網(wǎng)絡(luò)中的排隊(duì)系統(tǒng)在工作中節(jié)點(diǎn)常因無(wú)數(shù)據(jù)傳輸而休假[2]；常因?yàn)榱斯?jié)省資源而具有空竭服務(wù)[3-4]；也就是筆者考慮的帶有空竭服務(wù)的M/G/1排隊(duì)模型.

2模型描述

無(wú)線網(wǎng)絡(luò)節(jié)點(diǎn)可視為排隊(duì)系統(tǒng)的服務(wù)臺(tái)，它負(fù)責(zé)傳送到達(dá)的數(shù)據(jù)流.節(jié)點(diǎn)工作在兩種狀態(tài)：活動(dòng)(active)狀態(tài)和睡眠(sleep)狀態(tài).在活動(dòng)狀態(tài)，節(jié)點(diǎn)具有較高的能耗，處于此狀態(tài)的網(wǎng)絡(luò)節(jié)點(diǎn)主要工作在三個(gè)階段：傳輸期、空閑期和休假期，其中傳輸期和空閑期為活動(dòng)狀態(tài)，并作假設(shè)：

數(shù)據(jù)包到達(dá)服從參數(shù)為λ的Poisson流，數(shù)據(jù)包到達(dá)受阻則離開(kāi)服務(wù)區(qū)域進(jìn)入無(wú)限位置的重試軌道(orbit)，并且按照FCFS規(guī)則排隊(duì)等待.系統(tǒng)服務(wù)完一個(gè)數(shù)據(jù)包后，若orbit中沒(méi)有數(shù)據(jù)包則系統(tǒng)直接進(jìn)入休假期，即空竭服務(wù)規(guī)則.重試時(shí)間間隔和數(shù)據(jù)包的服務(wù)時(shí)間、處理器休假時(shí)間都服從一般分布函數(shù)A(x)、B(x)和V(x)；它們的密度函數(shù)、拉普拉斯司梯階變換(LST)、一階矩及二階矩分別為統(tǒng)只有在服務(wù)時(shí)間里才發(fā)生故障，失效率為μ，數(shù)據(jù)包已經(jīng)服務(wù)過(guò)的時(shí)間有效.假定數(shù)據(jù)包的到達(dá)時(shí)間間隔、服務(wù)時(shí)間、處理器的休假時(shí)間分布相互獨(dú)立.

設(shè)C(t)=i表示節(jié)點(diǎn)所處的狀態(tài)(i=0,1,2,分別表示在時(shí)刻t節(jié)點(diǎn)處于空閑、服務(wù)和休假期)；N(t)表示在時(shí)刻t在orbit中的數(shù)據(jù)包數(shù)；當(dāng)C(t)=0且N(t)>0時(shí)，ξi(t)(i=0,1,2)分別表示在時(shí)刻t逝去的重試、服務(wù)和休假時(shí)間.馬爾可夫過(guò)程的狀態(tài)空間為：

令a(x),b(x),v(x)分別表示在時(shí)刻t重試、服務(wù)和休假的風(fēng)險(xiǎn)率函數(shù)，即有：

3穩(wěn)態(tài)條件分析

系統(tǒng)的到達(dá)過(guò)程為Poisson流，由Burke定理知馬爾可夫過(guò)程C(t),N(t),ξ0(t),ξ1(t),ξ2(t)}的穩(wěn)態(tài)概率分布存在當(dāng)且僅當(dāng)

4 模型求解及相關(guān)指標(biāo)

t≥0,i≥0,x≥0.

由補(bǔ)充變量法可得系統(tǒng)穩(wěn)態(tài)的微分方程組：

邊界條件為：

正則性條件：

利用上面的（1）-（11）式，討論系統(tǒng)的穩(wěn)態(tài)分布,令：

把上面微分方程(1)-(10)取概率母函數(shù)，并把i從0到∞求和得:

由(16)-(18)得：

把(25)乘以v(x)，并從0到∞積分，考慮(1)式得：

由(21)知：

把(22)代入(20)式得：

把(23)、(28)、(24)、(27)式代入(19)式,同時(shí)考慮(21)與(26)式得：

把(29)式代入(28)式整理得：

再把(29)、(30)、(27)式代入(22)-(24)式可得：

運(yùn)用LH0spital法則和正則性條件：P0,0+P0(1)+P1(1)+P2(1) =1經(jīng)整理得：

5 排隊(duì)指標(biāo)

根據(jù)以上求得的概率母函數(shù)可以求得一下結(jié)論：

（1）節(jié)點(diǎn)處于空閑、服務(wù)與休假期的概率分別為：

（2）系統(tǒng)中數(shù)據(jù)包數(shù)、orbit中的數(shù)據(jù)包數(shù)的概率母函數(shù)分別是：

進(jìn)一步可得系統(tǒng)的平均數(shù)據(jù)包數(shù)和orbit中隊(duì)列的平均數(shù)據(jù)包數(shù)分別為：

（3）系統(tǒng)中的數(shù)據(jù)包平均等待時(shí)間與平均逗留時(shí)間分別為：

6 結(jié)束語(yǔ)

本文針對(duì)無(wú)線通信網(wǎng)絡(luò)的數(shù)據(jù)包服務(wù)時(shí)間為一般分布的M/G/1型排隊(duì)模型進(jìn)行了求解，該模型概括了服務(wù)時(shí)間是定長(zhǎng)分布、指數(shù)分布及Erlang分布的特殊情況，從而使其具有普遍的適用性.模型還進(jìn)一步考慮了無(wú)線通信網(wǎng)絡(luò)的數(shù)據(jù)包的重試傳輸、節(jié)能空竭服務(wù)與休假策略，因此模型的結(jié)論具有重要的應(yīng)用價(jià)值.

〔1〕KrishnaKB,Arivudainambi,TheM/G/1Retrial QueuewithBernoulliVacationGeneralRetrialTimes [J],ComputersandMathematics.2002,43(1-2):15-30.

〔2〕周宗好,朱翼雋,馮艷剛.具有Bernoulli休假的M/G/1重試可修排隊(duì)系統(tǒng)[J].運(yùn)籌學(xué)學(xué)報(bào),2008,12(1):71-82.

〔3〕朱翼雋,周宗好,馮艷剛.具有優(yōu)先權(quán)的M/G/1重試可修排隊(duì)系統(tǒng)[J].自動(dòng)化學(xué)報(bào),2008,34(2):195-201.

〔4〕MorenoP,AnM/G/1retrialtimewithrecurrentcustomersandgeneralretrialtimes[J],AppliedMathematics andComputation,2004,159(3):651-666.

〔5〕KrishnaKB,PavaiMS,VijayakumarA,TheM/G/1 retrialqueuewithfeedbackandstartingfailures[J], AppliedMathematicalModelling,2002,26(11):1057-1075.

〔6〕AtenciaI.,MorenoP,Asingle-serverretrialqueue withgeneralretrialtimesandBernoulliSchedule[J], AppliedMathematicsandComputation,2005,162(2): 855-880.

〔7〕TakacsL.Introductiontothetheoryofqueues[M], NewYork:OxfordUniversityPress,1962:1-355.

O226

A

1673-260X（2013）06-0001-03

國(guó)家自然科學(xué)基金資助項(xiàng)目(11226210)；安徽省高校省級(jí)自然科學(xué)研究項(xiàng)目(KJ2013B272)；黃山學(xué)院科研啟動(dòng)項(xiàng)目(2012xkjq008)