休假MX/G/重试次数的随机递归关系和稳定状态下的母函数表达式

理论计算机科学电子笔记253（2009）33-44www.elsevier.com/locate/entcs一种带休假的MX阿马尔·艾萨尼Houari Boumediene（USTHB），BP.32，El Alia，Bab Ez Zouar，16111，Algeria摘要本文给出了休假MX/G/重试次数是由一个任意的概率法，这是独立的客户在重试组的数量。我们认为这是一种充满活力的解释，因为客户的服务不需要不仅是随机时间，而且是具有任意概率分布的随机量的能量。当系统变空时，服务器将关闭并休假。所需的随机能量也是任意分布的。 我们推导出一个随机递归关系，它可以用作我们的队列的离散事件模拟算法。 其次，我们给出了稳定状态下轨道上顾客数的母函数的显式表达式，并给出了随机分解性质的显式表示。最后，我们将展示如何获得性能指标的利益和最优控制参数的休假和重试政策。关键词：重试排队，休假，批到达，能量解释，最优控制，随机分解。1介绍排队系统是对通信和运输网络、生产线、操作系统、运输网络等进行建模的重要工具。服务器代表客户对资源的访问，队列容量模型资源限制和服务前的存储。在经典模型中，发现服务器阻塞（繁忙或无序）的到达加入具有特定服务规则（FIFO，LIFO或RANDOM）的队列，或者被认为是丢失单元（Erlang模型）。两个有趣的研究方向已经介绍了与实际技术的演变。 第一个人认为，一个到达谁发现 服务器忙加入重试组或“轨道”（一种用于辅助源的队列），并连续重复其尝试，直到服务器能够提供服务。否则，如果服务器可用，到达的客户立即开始服务。这种模型被称为具有重复呼叫或重试队列的系统[10]、[6]。1571-0661 © 2009 Elsevier B.V. 在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2009.10.00434A. Aissani/电子笔记理论计算机科学253（2009）33休假（可移动或移动服务器）模型是另一种在文献中广泛研究的模型，早期与生产系统有关[9]。当系统为空时，服务器可以被关闭，并进行随机长度的休假。当系统中单元的累积大于固定阈值N或在固定时间段T之后，服务器被打开。管理人员将休假期引入模型中，以模拟次要任务（预防性维护，优先工作，电池充电，安全行动等）的空闲时间。几个实际的研究系统分析原则使用类似的排队模型或没有休假。示例1.1 [无线移动中的电池电源管理[16].] 在无线技术（ad hoc网络、无线互联网设备、射频识别设备）中，许多由电池供电的大多休眠的移动节点彼此通信。为了节省能量，移动主机周期性地唤醒以服务传入的传输。更确切地说，允许移动设备（或电池）休假以校准时间量，即： 允许电池自行充电的空闲时间。因此，电池寿命可以在服务的客户数量增加的意义上增加。然而，当它们没有接收任何数据时，保持清醒将是不节能的。 这引起涉及能量消耗和延迟之间或能量效率（在服务分组中花费的能量）和捕获速率（当接收机唤醒时到达的分数）之间的权衡。在这些工作中，通常假设每个发送的分组（即，在贝叶斯理论的语言中，客户）消耗与分组大小（或传输比特率、无线链路设计等）成比例的能量。 时速团结在这项研究中，消费速度是由一些名义值，可以是不同的（更大或更小）的单位。我们也可以参考更复杂的模型，使用动态规划来最大化服务质量，但要遵守长期平均功耗的上限[7]。实施例1.2 【转控制 议定书（TCP）in 互联网[15]。 当调度器在服务器休假的其他地方进行分配。这个想法在[15]中被用来对无线IP网络中的TCP性能进行例1.3 [PCS呼叫终止控制[18].] 用于从网络（或蜂窝站）重新转发呼叫终止SETUP消息的方案用于防止它们的丢失，这将使得不可能建立呼叫。空协议对应于这样的事实，即在小区站中的寻呼信道队列中登记的消息被循环地转发到无线区域，而重试现象对应于当网络没有接收到响应消息示例1.4 [寻呼信道过载或对蜂窝网络的攻击[17].] 在基站的寻呼信道被表示为具有 N+1 个 队 列 的 排 队 系 统 ， 其 中 N 是 寻 呼 信 道 的 时 隙 数 ， 即 在 码 分 多 址（CDMA）网络中N = 32或N = 64，每个小区由A. Aissani/电子笔记理论计算机科学253（2009）3335≤−{Gi，i≥}≥Gzi=0Gi zkthgi G gi≥Σ基站在64个沃尔什码上操作）。在这些队列中，N个用于存储时隙消息，一个用于非时隙消息。这里所用的系统方法是，休假状态对应于时隙业务，实际系统。在这项工作中，重试和能量参数被忽略。在下面的部分中，我们将对我们的模型进行更详细的描述。第3节是专门介绍的基本随机过程描述的动态我们的队列。这种低级形式主义使用一般分布（而不是指数分布）来描述原子事件。 我们还提供系统的离散事件仿真算法。在第四节中，我们给出了系统稳定状态下服务器状态和轨道长度的联合分布以及系统规模分布的母函数的显式表达式。虽然这些表达式看起来很麻烦，但它们允许获得平均性能指标（平均系统大小，平均等待时间等）。 用一种简单的方式 因此，它们可以用于例如，通过比较，用于测试更复杂的工具。在第5节中，我们展示了一个明确的形式的随机分解性质，显示休假和重试的效果。这是模型的另一个简化属性，我们展示了它是如何有用的，以获得一些平均性能指标。休假和重试策略的最优控制出现在第6节和第7节。 最后，我们在第8节中给出了一个数值例子，展示了如何使用所给出的结果进行系统的设计。 这里省略了所有的证明，因为它们与的[3]。2模型描述和符号主客户到达单个服务器的概率服从复合泊松过程，且到达率λ> 0。 在一个到达时期，到达批次中的主要（新鲜）客户数遵循具有生成函数的任意离散分布 1（）=∞i和阶乘矩为（k）（1）（0为∞i=0gi=1）。如果服务器正忙或在到达端口时处于真空状态，则整个batch加入重试组（无限容量），而如果服务器空闲，则到达的单元之一开始服务，其余的加入重试组。任何客户在到达时接受服务或在重试时接受服务，在服务完成后将永远离开系统。从轨道访问服务器的策略由任意概率分布R（x）=P（τ）支配x），其中τ是随机数重审的时间我们用r（s）=E（e-sτ）表示相应的Laplace-Stieltjes变换，r1，r2表示一阶矩。如果R（x）= 1e−νx，我们得到所谓的在这种情况下的系统的示例策略是服务器需要搜索客户的模型[6]。让Sn是服务第n-位客户的工作量。 我们假设序列{S n，n≥1}由独立同分布的随机变量组成，其公共分布函数为H（x）= P（S0。如果在时间t，一个主要或次要客户带着所需的工作x到达，并且如果服务器是空闲的，那么服务将在时间t+x/α完成。我们假设，服务器离开的假期随机长度每当系统将变空。单个休假所需的功是一个速度为β的非负随机变量V。分布函数V（x）=P（V0，并且对于每θ=、42A. Aissani/电子笔记理论计算机科学253（2009）33--联系我们个存在的客户，每单位时间都会产生等待成本h >0。只有当积累了足够的客户（或能量）时，服务器才会打开。从第3节可以看出，在时间间隔（0，t）内的开采成本C（t），t0是一个再生过程，再生点为γn， 也是一个累积过程[19]。A. Aissani/电子笔记理论计算机科学253（2009）3343√∫≤≥.通过使用累积过程的基本定理[19]，可以证明对于静态策略，单位时间的平均利用时间成本可以表示如下（十七）C=limC（t）= S+hE（M），t→∞tE（L）其中E（L）=E（V）/（1−ρ）r（λ）β是一个循环的平均长度考虑到注释5.2给出的E（M）的表达式，我们得到了成本函数的显式表达式（十八）C（T）=Sβ（1−ρ）r（λ）+h（λg1T+λ），T2β其中，λ是与T无关的常数。将公式18关于T进行微分，并将结果设为零，我们得到T=β[2S（1−ρ）r（λ）]/λg1h。敏感性分析研究重试分布R（. ）对最优值T_（？）设θz= 1，如果x z，θz= 0，如果x≥z.还记得R+上具有平均值m的分布函数是NBUE（新的比预期中使用的更好）当且仅当x∞F（y）dym F<$ （x）forx0.如果我们逆不等式，我们得到分布NWUE（新的比预期中使用的差）。所有人的阶级指数分布是这两类非参数分布之间的边界。定理6.1·如果重试时间分布R（x）具有有限个一阶矩r1和r2，则T的最优值有界如下（19）TLTTU，其中上界和下界分别由下式给出：（二十）TL=θ0（eλr1g1− （g1−1) −λg1h1/α）β2S（g1eλr1−（g1−1）−λg1h1/α）λg1h(21)Tθ=θ（r（λ）g-（g-1）−λgh/α）β。2S（g1rU（λ）−g1（1+λh1/α）+1），U0U1 1 1 1和λg1h1（二十二）（）=r2−r1+r2−λ（r+（r−r2）/r2）rU λ1er2r21 21 1，• 如果重试时间分布R（x）是NBUE，则（二十三）TLTNBUETEXP、44A. Aissani/电子笔记理论计算机科学253（2009）33−其中，对于具有NBUE重试时间分布的SRV系统，T_N_B_UE是其最优的变量策略值;对于文献[3]中研究的具有常数重试的能量SRV系统，T_E_X_P是其最优的变量策略值。注6.2当重试时间分布未知时，不等式（19）给出了最优T值的上下界，但我们有关于前两个矩的部分信息。对于第二个不等式（23），我们使用关于重试时间分布的年龄类的部分信息A. Aissani/电子笔记理论计算机科学253（2009）33452∗≤≤=1λ+δ−7再审策略的最优控制我们现在研究当系统在T−策略下运行时重试分布函数R（x）我们注意到，（二十四）（ （））=Sβ（1 −ρ）r（λ）+.+[1 − r（λ）]（g2r（λ）+ θ）<$C R.h η1T g1r（λ）+（1−g1）−λg1h1/α仅取决于实值r（λ），0r（λ）1、不在于具体方面再测时间分布R（x）的n=E（MF）+E（MRV），θ为常数。因此，问题简化为选择使成本函数（24）最小化的单个最优值q=r（λ）定理7.1使成本函数（24）最小化的最优值q_n• 若q≥Sβg1/hT，则qq= 1，• 如果<$Sβg1/hT，则q<$是方程Γ（q）=Sβg1/hT的解，其中 ω = λg1/α +（g1− 1）/g1。哪里（二十五）Γ（）=g3α2+2g2 [1−g1−λh1/α]q+[θ+λg1h1（g2+θ）/α+g2（1−g1）]q11和（二十六）十一，（g1q+1−g1−λg1h1/α）23g2+θ+λ（1 −λg1h1/α）28数值示例在本节中，我们将给出一些数值示例。以前得到的结果可以很容易地以表格或交互界面的形式在软件中显示出来以帮助经理做出决定。例如，在表1中，我们给出了最优值T，相应的最小期望成本C（T）和不同α值的负载。 在这里，我们设置 λ=g1= 1，g2=h2= 0，h1= 0. 25，h= 2，S= 10，r（λ）= 0。5. 我们观察到最小期望值与β无关。而最优值T_∞随着α的增大而增大，而负载减小。作为说明，我们考虑示例1（第1节）的简单版本，其中移动设备的电池是服务器，客户是传输的分组。 在一些作品中[16]，能量效率被定义为服务数据包所花费的能量的分数，在我们的情况下由c=p1给出。 =λg1h1/α=0. 25/α，α=1，所以c=0。25.捕获率被定义为发现移动唤醒的到达的分数，即 λ（p0. +p1。）=λ（1 p2. ）=λ λ+δρ，在随机休假的情况下。表1示出了对于不同的消耗电荷α值，在唤醒发生之后的最佳充电量。.46A. Aissani/电子笔记理论计算机科学253（2009）33表1最优值T和相应的最小期望费用α0.60.70.8151030100ρ0.830.710.620.50.10.050.010.005T4.55.96.87.910.610.811.011.1C（T）13.69.17.66.65.55.55.45.49结论本文给出了带休假的重试MX/G/1排队的能量形式。算法（1）可以在关于独立性和/或等分布的相当一般的假设下应用我们已经描述了控制休假或重试协议的设计这种低级建模形式主义使用一般分布（而不是指数分布）来描述原子事件。因此，它可能有助于开发高级描述语言，如随机Petri网或过程代数[12]。确认我要感谢匿名的参考者对早期草案提出的非常有益的意见和建议。引用[1] Aissani，Artalejo J.R.，On the Single Server Retrial Queue Subject to Breakdowns，Choosing Systems30，（1998），309-231.[2] Aissani A.，一种具有穷举休假的MX/G/1重试排队系统，统计与管理系统学报，第3期（2000），269-286.[3] Aissani A.，M/G/1重试休假排队系统的最优控制系统工程，卷。17，N4，（2008），487-502.[4] 阿尔特曼·E Nain P.，服务员重复休假的M/G/1排队的最优控制，IEEE Trans.自动化- 是的卷38，（1993），776-775.[5] 小阿尔塔莱霍，服务台具有常数重复尝试的M/G/1排队系统的分析结果：24，N6，（1997），493-504.[6] 小阿尔塔莱霍，戈麦斯-科拉尔A.，Retrial Questions：An Questimic Approach，Springer，Berlin，2008.[7] 阿塔·B Zakariadis K.E.，在衰落下行链路信道中的动态功率控制受到能量约束，嵌入式系统，（2007），55，41-69。[8] 乔杜里·G具有伯努利休假表的两阶段分批到达重试系统188，N2，（2007），1455-1466.[9] 多希·T带休假的休假制度--一项调查，休假制度（1986年），129-166。[10] Falin G.I.坦普尔顿J.G.C.，Retrial Questions，Chapman and Hil，Chichester，1997.[11] Furham S.W.，库珀R. B M/M/1广义休假排队的随机分解，运筹学，33，（1985），1117-1129。A. Aissani/电子笔记理论计算机科学253（2009）3347[12] Gharbi N.，Ioualalen M.，使用广义随机Petri网的重试排队系统的性能分析，理论计算机科学电子笔记，卷。65，N6，（2002）.[13] Gnedenko B.V.I.N.，Introduction to Chaoeing Theory，2nd edition，Birkhauser，Boston，（1989）.[14] Kernane T. Aissani A.，稳定性与多功能的政策，应用数学和随机分析杂志，卷。2006，Article ID 54359，1-16.[15] T.E. Klein，K.K. Leung，H. Zheng，Enhanced Scheduling Algorithms for Improved TCP Performance在Wireless IP Networks，Proceedings of IEEE Global Telecommunications Conference（Globe-com），Dallas，TX，November 2004，2744-2748中。[16] Prabhu B.J.，Chockalingam A.，夏尔马五世，无线移动设备中电池电源管理方案的性能分析，Proc.Wireless Communications and Networking Conference WCNC 2002，Vol.2，（2002），825-831。[17] J中士Zang H.，Bolot J.C.，寻呼信道过载或攻击对蜂窝网络的影响，第五届ACM无线安全研讨会论文集，（2008），75-84。[18] 志方岛，铃木S.，高桥Y.，伊原T Nakanishi T. PCS呼叫终止控制的丢失概率评估IEICE电子、通信和计算机科学基础汇刊。卷E82-A，N7，1230-1237。[19] Tijms H.C.，随机模型：一种数学方法，Wiley，Chichester，1994年。