服务时间累积量控制的GeoX/G/1排队的稳态队长.pdf
《服务时间累积量控制的GeoX/G/1排队的稳态队长.pdf》由会员分享,可在线阅读,更多相关《服务时间累积量控制的GeoX/G/1排队的稳态队长.pdf(16页珍藏版)》请在咨信网上搜索。
1、考虑服务台的启动由服务台闲期所有到达的服务时间累积之和(即顾客即将被服务的时间累积量)控制的离散时间批到达GeoX/G/1排队服务系统。顾客成批到达系统,当顾客的被服务时间累积量超过某个非负整数D时,服务台立刻为顾客提供服务直到忙期结束(此策略被称为D策略)。该模型可为无线传感网络的从业者提供一些理论基础。首先,在准备工作中,讨论了忙期开始时刻的顾客数、服务时间累积量以及服务台的忙期和闲期分布;然后,通过闲、忙期到达顾客的分类和概率分析方法,研究了系统的离去时刻稳态队长和任意时刻n+的稳态队长分布的概率母函数。作为特例,分析得到了离散时间GeoX/G/1排队和D策略离散时间Geo/G/1排队的
2、队长分布结果。最后,模拟分析了一类无线传感节点,并在数值上获得了节点的最低能耗。关键词:成批到达;服务时间累积量;队长分布;无线传感节点;最小能耗分类号:AMS(2010)60K25;90B22中图分类号:O226文献标志码:A0引引引言言言由于在计算机、信息通讯和无线传感网络等方面的重要应用,离散时间控制排队越来越受到研究者的关注。人们通过考虑进入系统的顾客数(F策略和有限缓冲空间1)、服务员是否在岗(T策略23)、服务的不同速率(各种工作休假策略45)以及等待顾客的个数(N策略1,3,6)和等待顾客的服务时间累积量(D策略7)等,实现对离散时间排队系统的控制,进而达到整个系统的最优运行和经
3、济利益最大化目的。值得注意的是,离散时间排队与连续时间排队有一些本质的区别,比如,单服务台连续时间类型的排队M/G/1中各个时刻的队长分布是一样的,而在单服务台离散时间类型的排队Geo/G/1中,各个时刻的队长分布有可能是不一样的,研究更加复杂。另外,在有关离散时间排队的上述各种策略中,不同假设的T策略、工作休假策略和N策略已得到了较多的研究,但目前文献对F策略和D策略的离散时间排队研究还很不够。就D策略而言,一个研究的难点在于各种包含D服务策略的排队中,由于服务台闲期和忙期内所有到达的被服务时间具有不同的独立性,所以不能通过队长的概率母函数分解关系分析稳态队长分布;忙期也不能直接应用分枝过程
4、方法得到。因此,不能像T策略与N策略排队一样,可以通过随机分解和分枝过程来求出队长和忙期分布,对包含D服务策略的离散时间类型排队,需要运用有效收稿日期:2021-01-22.作者简介:刘仁彬(1972),男,博士,副教授.研究方向:排队模型及其应用.基金项目:国家自然科学基金(71571127);重庆市自然科学基金面上项目(CSTB2022NSCQ-MSX1160).606工程数学学报第40卷的方法分析队长和忙期等排队指标;再次,在目前为数不多的D服务策略离散时间类型排队研究中,尚无文献考虑批到达排队的情形,而众所周知,在各种离散时间控制排队的应用中,顾客的成批到达是一种更贴近实际的较一般情况
5、。基于此,本文研究一类服务时间累积量控制的离散时间类型批到达排队GeoX/G/1,考虑了服务台忙闲期所有到达的被服务时间有相依和独立的差异性,通过分析服务台的忙、闲期、忙期开始时刻的顾客数和服务时间累积量分布以及将服务台忙、闲期所有的到达进行分类,并借助概率讨论的方法,研究了顾客离开时留下的稳态队长和任意时刻n+的稳态队长分布,首次揭示了这类批到达离散时间控制排队忙期分布的特殊结构。作为特例,也得到了一些特殊离散时间类型排队模型的稳态队长分布结果。本文提出的数学模型可以用来模拟一类无线传感节点对数据信息元的接收和处理。在一个这样的传感节点中,一个被接收的数据信息元的处理就相当于一个到达系统的顾
6、客的被服务,等待处理的数据信息元就是逗留在传感节点中等待服务的顾客,传感节点中处理信息元的无线服务器就相当于给顾客服务的服务台,所以可以把传感节点看成一个排队服务系统。为了节约有限的能量从而使传感节点有较长的运行寿命,Jiang等8从控制排队论的角度对传感节点提出了依据信息元处理时间累计量来启动数据元处理的能量节约设计方案。但Jiang等8的节能设计方案是基于将一个无线传感节点看成一个单个到达的连续时间类型M/G/1排队服务系统来进行处理。而众所周知,无线传感节点中数据信息元的出现间隔时间和处理时间都是不同的整数时间,且信息元的出现可能个别出现或几个一起出现更符合批到达的特点,故把该传感节点模
7、拟成一个离散时间类型的成批到达排队服务系统更为合理,比Jiang等8运用的单个到达的连续时间类型排队模型更加符合客观实际。另外,应用本文获得的理论分析结果可在数值上讨论传感节点的最佳节能方案。1系系系统统统模模模型型型和和和预预预备备备工工工作作作本文考虑的由服务时间累积量控制的离散时间批到达排队系统的假设如下:1)考虑一个有延迟进入的晚到达离散时间批到达GeoX/G/1排队,即顾客的成批到达过程是某参数p(0 p 1)的Bernoulli过程,p是一个时隙(n,n)(n=0,1,2,)内到一批顾客的概率;每批到达系统的顾客数X相互独立、均服从相同的任意概率分布Pr(X=i)=gi(i=1,2
8、,),且数学期望E(X)和矩E(X(X 1)都是有限值;2)顾客被服务的开始时刻和服务完顾客的离去时刻都发生在时隙(n,n+)(n=1,2,3,)内。顾客的被服务时间Sk(k 1)相互独立也服从相同的任意概率分布,其概率分布和概率母函数分别为s(n)=Pr(Sk=n),n=1,2,S(z)=i=1ziPrSk=i,|z|1,并且数学期望E(S)和矩E(S2)均有限。假设s(0)=0,即服务时间以概率1取正整数;顾客批按到达的先后顺序被安排服务,同一批顾客被服务的顺序是随机的,服务台是一个顾客一个顾客地进行服务。如果到达的顾客发现服务台正在繁忙时需等待前面的顾客服务完才能接受服务;第4期刘仁彬,
9、等:服务时间累积量控制的GeoX/G/1排队的稳态队长6073)如果在服务台闲期所有到达的被服务时间累积之和(即顾客的被服务时间累积量)超过某个事先确定的非负整数D时,则空闲服务台马上启动为等待顾客提供服务并且一直持续到系统为空。我们称这种启动停止策略为空竭D服务策略。在全文中,我们采用一些记号如下:x=1 x,0 x j;=E(X)E(S);W(z)=iziPrW=i,|z|1:相应的离散随机变量W的概率母函数;S(k)(n)=PrS1+S2+Sk n(1 k n):独立同分布服务时间k重卷积的概率分布函数(S(0)(n)=1,S(k)(n)=0,k n 1);s(k)(n)=PrS1+S2
10、+Sk=n(1 k n):独立同分布服务时间k重卷积的概率分布(s(1)(n)=s(n),s(k)(n)=0,k n 1);显然s(k)(n)=S(k)(n)S(k)(n 1)(n k+1),s(k)(n),n k是s(n),n 1的k重卷积,即s(k)(n)=s(n),k=1,n 1,nk+1j=1s(j)s(k1)(n j),2 k n n 1;g(k)n=Pr(X1+X2+Xk=n)(k n):k批顾客到达n个的概率;Sg=S1+S2+SX:一批顾客的被服务时间累积量;sg(n)=Pr(Sg=n)=j=1gjs(j)(n)(n 1):一批顾客服务时间累积量的概率分布;Sg(n)=Pr(S
11、g n):一批顾客服务时间累积量的概率分布函数;S(k)g(n)=Pr(Sg,1+Sg,2+Sg,k n):k批顾客服务时间累积量的概率分布函数;QD:忙期开始时的顾客数;UD=S1+S2+SQD:忙期开始时顾客的服务时间累积量。为了讨论顾客离去时刻和任意时刻n+的稳态队长分布,作为一些准备工作,我们需要先得到忙期开始时刻的的顾客数、被服务时间累积量以及服务台忙期和闲期的概率分布。本文的研究是在稳态条件下进行分析,即交通强度=E(X)E(S)D,(4)UD(z)=n=D+1znPrUD=n=Sg(z)1 Sg(z)Dn=1znk=1s(k)g(n),(5)E(UD)=dUD(z)dz?z=1=
12、E(S)E(X)1+Dk=1S(k)g(D),(6)E(UD(UD 1)=d2UD(z)dz2?z=1=E(S(S 1)E(X)1+S(k)g(D)+2E(Sg)Dn=1nk=1s(k)g(n).(7)证明在模型假设的空竭D服务策略下,如果服务台忙期开始时刻的服务时间累积量为n(n D),则首批到达的服务时间累积量等于n,或者头k(k 1)批到达的服务时间累积量为y(0 D,(8)其概率母函数为UD(z)=n=D+1znsg(n)+n=D+1znDy=1k=1s(k)g(y)sg(n y)=n=1znsg(n)Dn=1znsg(n)+n=D+1znny=1sg(n y)k=1s(k)g(y)n
13、=D+1znny=D+1sg(n y)k=1s(k)g(y)第4期刘仁彬,等:服务时间累积量控制的GeoX/G/1排队的稳态队长609=n=1znsg(n)Dn=1znsg(n)+n=D+1znk=1s(k+1)g(n)y=D+1zyn=y+1znysg(n y)k=1s(k)g(y)=n=1znsg(n)Dn=1znsg(n)+n=1znk=2s(k)g(n)Dn=1znk=2s(k)g(n)Sg(z)y=kzyk=1s(k)g(y)Dy=kzyk=1s(k)g(y)=n=1znk=1s(k)g(n)Dn=1znk=1s(k)g(n)Sg(z)k=1(Sg(z)kDy=kzyk=1s(k)g
14、(y)=Sg(z)1 Sg(z)Dn=1znk=1s(k)g(n).(9)于是,计算易得忙期的开始时刻服务时间累积量的数学期望和二阶矩。1.3服务台的闲期和忙期定理3设服务台的闲期和忙期的长度分别为ID和BD,则其概率母函数和数学期望分别为ID(z)=k=1(pz1 pz)kS(k1)g(D)S(k)g(D),(10)E(ID)=dID(z)dz?z=1=1p1+Dk=1S(k)g(D),(11)BD(z)=U(pz+pzBg(z),(12)E(BD)=dBD(z)dz?z=1=E(S)E(X)1 1+Dk=1S(k)g(D),(13)这里Bg(z)表示经典的离散时间类型批到达排队GeoX/G
15、/1中以一批顾客开始的忙期的概率母函数,其均值E(Bg)=(E(S)E(X)/(1 )。证明记j(j=1,2,)为第j批和第j+1批顾客的到达间隔时间,则由于各批顾客的到达过程是参数p的Bernoulli过程,得j(j 1)独立同几何分布,其概率母函数为pz/(1 pz)。第k批到达的服务时间超过D的概率为S(k1)g(D)S(k)g(D),可得ID(z)=E(zID)=k=1E(z1+2+k)S(k1)g(D)S(k)g(D)=k=1(pz1 pz)kS(k1)g(D)S(k)g(D).(14)610工程数学学报第40卷设服务台忙期BD最开始的一段长度为UD的时间内到达批数为,记B表示忙期B
16、D内从这批顾客开始的剩余忙期长度,则BD=UD+B,且B可分解为B=Bg,1+Bg,2+Bg,,其中Bg,i(i 1)同分布且独立,表示离散时间类型的经典成批到达排队GeoX/G/1中以一批顾客开始的忙期长度,其数学期望E(Bg)=(E(S)E(X)/(1 )。于是,服务台忙期的长度BD有如下的概率母函数BD(z)=E(zBD)=m=D+1mk=0E(zm+Bg,1+Bg,2+Bg,k|UD=m,=k)Pr(UD=m,=k)=m=D+1mk=0zm(Bg(z)kPr(UD=m)Ckmpk pmk=m=D+1zm(p+pBg(z)mPr(UD=m)=U(pz+pzBg(z).(15)由此计算易得
17、服务台忙期和闲期长度的数学期望。注1文献3得到了T策略(N策略)排队GeoX/G/1中忙期长度的概率母函数是Q(B1(z)(这里Q(z)表示T策略(N策略)排队GeoX/G/1中忙期开始时刻的队长概率母函数,B1(z)表示经典的离散时间类型批到达GeoX/G/1排队中以一个顾客开始的忙期的概率母函数),这表明T策略(N策略)的批到达排队的忙期分布由忙期开始时刻的队长分布确定。由(15)式可见,D策略的批到达排队的忙期分布由忙期开始时刻服务时间累积量的分布确定,这一特殊结构不同于T策略(N策略)成批到达排队的忙期分布的结构。值得注意的是,本文研究的服务台忙期具有独特的组成,即服务台忙期等于忙期开
18、始时刻的服务时间累积量和从这段累积服务时间内到达批数开始的剩余忙期之和,再利用了经典忙期的分枝过程结果分解这段剩余忙期。从上述证明过程可以看出,这种处理方法也可用来分析包含D策略的其他复杂控制排队模型的忙期分布。注2根据忙循环的定义可知,一个忙循环的数学期望E(CD)=E(ID)+E(BD)=1p(1 )1+Dk=1S(k)g(D),从而得到服务台忙和闲的概率分别为E(BD)E(CD)=,E(ID)E(CD)=1 .2队队队长长长分分分析析析众所周知,在广义休假离散时间GeoX/G/1排队中,稳态下任意时刻n+的队长概率第4期刘仁彬,等:服务时间累积量控制的GeoX/G/1排队的稳态队长611
19、母函数P(z)和经典GeoX/G/1排队系统任意时刻n+稳态队长概率母函数PGeoX/G/1(z)满足如下分解关系3,910P(z)=PGeoX/G/1(z)L(z),(16)这里PGeoX/G/1(z)=(1 )(1 z)S(p+pX(z)S(p+pX(z)z,L(z)表示广义休假引起的附加队长概率母函数。不像N策略或T策略的离散时间类型成批到达GeoX/G/1排队,上述队长的概率母函数分解关系在本文的排队中将不再有效。这是由于在D策略下,当忙期开始时刻的等待顾客数QD=k(k=1,2,)时,这些等待顾客的被服务时间S1,S2,Sk满足S1+S2+Sk D,即对服务台闲期内的所有到达而言,它
20、们的被服务时间S1,S2,SQD不是独立的,而是取决于忙期开始时刻的所有到达个数QD。由于这一相依性不满足系统队长的概率母函数分解关系的服务时间独立性条件,因此要得到本文考虑的排队系统中任意时刻n+的稳态队长分布,需要寻求行之有效的分析方法进行研究。注意到在广义休假离散时间类型GeoX/G/1排队系统中,稳态下任意时刻n+的队长概率母函数P(z)和离去时刻留下的稳态队长概率母函数(z)满足关系45,911P(z)=(z)E(X)(1 z)1 X(z).(17)于是,我们可以考虑顾客离去时留下的系统队长分布。注意到在本文研究的系统中,对服务台忙期的所有到达,其服务时间彼此独立,对服务台闲期的所有
21、到达,其服务时间具有相依性,这种差异性将对离去队长产生重大影响。因此,我们先分别分析服务台闲、忙期到达系统的任一顾客离去时刻留在系统的队长分布,再根据顾客的不同类型获得稳态下任意顾客的离去时留下的系统队长的概率母函数(z),最后再导出稳态下任意时刻n+的队长概率母函数P(z)。注意到一个顾客在服务台闲期内到达的概率IC=E(QD)pE(X)E(CD)=1 ,在服务台忙期内到达的概率BC=1 IC=。设一个服务台闲期(忙期)到达系统的顾客离开时留下的系统队长的概率母函数是idle(z)(busy(z),则对稳态下任意顾客的离去时刻留下的系统队长的概率母函数(z),有(z)=ICidle(z)+B
22、Cbusy(z)=(1 )idle(z)+busy(z).(18)设r表示服务台闲期内最后到达的一个顾客在忙期BD内的离去时刻,Lr表示该时刻系统中留下的队长,则Lr等于忙期BD的最开始时间段UD内的所有到达,且其概率母函数Lr(z)=UD(p+pX(z)、数学期望E(Lr)=pE(X)E(UD)。注意到在服务台忙期BD之内,时刻r以后的系统队长过程等价于离散时间类型的经典GeoX/G/1排队的忙期之内从顾客数Lr开始的系统队长过程,于是根据广义休假的离散时间类型成批到达排队GeoX/G/1的分解结论11,可得如下定理。612工程数学学报第40卷定理4一个服务台忙期之内的到达离开系统时留下的系
23、统队长,其概率母函数为busy(z)=1GeoX/G/1(z)eLr(z)=(1 )(1 z)S(p+pX(z)S(p+pX(z)z1 UD(p+pX(z)pE(X)E(UD)(1 z),(19)其中eLr(z)=1 Lr(z)E(Lr)(1 z)=1 UD(p+pX(z)pE(X)E(UD)(1 z)表示同分布并且相互独立的随机变量序列Lr生成的更新过程中向后常返时间的概率母函数,1GeoX/G/1(z)=(1 )(1 z)S(p+pX(z)S(p+pX(z)z为从一个顾客开始的离散时间类型的经典成批到达排队GeoX/G/1的忙期中一个到达离去时留下的顾客数的概率母函数表达式。定理5一个服务
24、台闲期之内的到达离开系统时留下的系统队长,其概率母函数为idle(z)=Dx=1 p+pX(z)xDxw=0i=1k=0zkgi+kE(QD)xy=1s(i)(x y)j=1s(j)g(y)s(k)(w)QDxw(z)+Dx=1 p+pX(z)xw=Dxk=1zki=1xy=1s(i)(x y)j=1s(j)g(y)gi+kE(QD)s(k)(w)+Dx=1 p+pX(z)xDxw=0i=1k=0zkgi+kE(QD)s(i)(x)s(k)(w)QDxw(z)+x=D+1 p+pX(z)xk=0zki=1gi+kE(QD)Dy=1s(i)(x y)j=1s(j)g(y)+Dx=1 p+pX(z
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 服务 时间 累积 控制 Geo 28 29 _G_1 排队 稳态 队长
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。