具有加入最短队列规则的Jackson网络的性能分析

程慧慧，辛超楠

(华北水利水电大学 数学与统计学院，河南 郑州 450046)

0 引言

排队网络是一类重要的排队模型，在实际中应用广泛.很多学者经常通过减少队列长度，缩短顾客等待时间或提高系统服务速率来提高排队网络的性能，比较常用的研究方法是加入最短队列规则(join the shortest queue,JSQ).

Ephremides 等[1]提出：当到达的顾客被分配到两个相似的指数服务器之一时，在已知两个服务器上的队列长度时，最佳决策是将顾客分配到较短的队列.Johri[2]证得JSQ规则最小化了服务速率依赖于状态的排队系统的顾客数和等待时间.当排队系统中的队列数目N较大时，在引入JSQ规则后会变成高维的交互系统，这样的排队系统可以利用平均场模型来研究.平均场理论最早应用于统计物理[3-4]，其优点是可以通过求确定性系统的解来研究排队系统的一些性质.Dawson等[5]针对队列间具有交互作用的大型排队网络，利用平均场近似的方法研究了排队网络的极限特征及其平稳分布.Dawson等[6]针对具有JSQ规则的大型排队网络，利用平均场近似研究了排队网络的一些极限特征，并证实了在JSQ规则下排队网络的性能得到了提高.

Jackson网络是一种经典的排队网络[7]，由J.R.Jackson[8]于1957年提出.Jackson网络广泛应用于计算机系统和调度问题中[9-11]，因此研究如何提高网络的性能这一问题就显得非常有必要.Martin等[12]对经典的Jackson网络进行修改，使每个节点具有N个队列，顾客到达一个节点后随机地选择m个队列，然后加入m个队列当中最短的一个，证得此时排队网络的平稳分布呈超指数收敛，并且缩短了队列的平均队长.Azaron等[13]通过优化控制Jackson网络中所有节点的服务速率和到达速率，使得网络最短路径的期望值最小.Xia[14]研究了开放Jackson网络的准入控制问题，证明了最优控制策略具有阈值形式.Imry等[15]在开放Jackson网络中利用节点生成法，得出了使系统的平均作业数和响应时间最小化的服务速率的再分配方法.Timmer等[16]考虑了一个具有独立节点的Jackson网络，每个节点可以通过调节顾客总的到达率(不依赖于状态)来减少排队系统总的预期等待时间.Ansorena[17]利用封闭Jackson网络模型，得到了使码头运营利益最大化的具体方案.晋良海等[18]通过构建安检系统的Jackson排队网络模型，优化安检系统服务参数，缩短了旅客提取行李的平均等待队长.

目前关于Jackson网络的研究基本上都是时齐的，对非时齐的Jackson网络的研究较少.本文在文献[5-6]的启发下，将JSQ规则引入具有大量节点的Jackson网络中，利用平均场近似的方法研究非时齐Jackson网络的相关性质.

1 模型简介

假设Jackson网络中含有J个节点(J很大但有限).在节点i∈{1,2,3,…,J}处，单位时间内从系统外部进入该节点的顾客数服从参数为λ′的泊松分布，顾客在该节点接受服务的时间服从参数为μ的指数分布.在第i个节点接受完服务后立刻以pij的概率进入第j个节点，并在那里等候接受服务，或者以pi0的概率离开系统，

记P:=(pij)，pij表示从节点i到节点j的转移概率，并且有一到达率为Jλs的泊松到达流，顾客从该到达流加入排队网络中的最短队列.

设E={0,1,2,…}，T≥0，DT(E)(D∞(E))

表示从[0,T]((0,∞))到E的右连续且具有左极限的函数空间.记Xt(ω)=X(t,ω)=ω(t)，也可以记做X(t)=X(t,ω)，其中ω∈DT(E).Ft=σ{X(s),0≤s≤t}表示由{X(s),0≤s≤t}生成的最小σ代数，F=σ{X(t),t≥0}表示由{X(t),t≥0}生成的最小σ代数.P(D∞(E),F)表示(D∞(E),F)上的全体概率测度的集合.Pp(E)表示E上的p阶矩有限的概率测度的集合,p∈N+.P(E)表示E上的所有概率测度的集合.

2 平均场近似

到达速率为λi，服务速率为μi,i=1,2,…的M/M/1队列的队长过程{Y(t),t≥0}是一个生灭过程，对应的Q矩阵为

对应的算子Ω为

针对前面所描述的交互系统，记X(J)(t)=(X1(J)(t),…,XJ(J)(t))，其中Xk(J)(t)表示节点k处的顾客数量，k=1,…,J.X(J)(t)的概率分布为P(J)∈P(D∞(EJ)).令x=(x1,…,xJ)∈EJ，EJ表示E的J维笛卡尔积，则X(J)(t)的转移速率为

其中：#A表示集合A中元素的个数；1A(·)表示集合A上的示性函数；当A是一个单点x时，有1A=1x.

网络对应的算子为

其中，ek是第k个分量为1，其余均为0的J维向量.

首先定义交互函数h:E×P(E)→R+:

其中ms(ν)=min{k≥0,ν({k})>0}表示概率测度ν在E上的支集的最小点.下面引入非线性主方程：

(1)

其中〈ν,f〉表示f与ν的积分.

且有

(2)

因为每个节点具有相同的作业规律，所以通过研究节点k来研究排队系统的相关性质，方便起见称之为典型队列.

定义1假设u∈P(E)，如果ut(·)=P°Xt-1(·)满足非线性主方程(1),且u0=u，P的初始分布为u，则称P∈P(D∞(E),F)为非线性主方程的解.如果对任意的j∈E，有

P(Xt+s=j|Ft)=p(t,Xt;t+s,j),

其中转移函数满足

则P是马尔可夫解.

(a)如果定义

则

(3)

其中

(b)如果u0({0})=1，则

(4)

(5)

其中u(t)(·)=P°X-1(t)(·).

(6)

这一微分方程组与文献[6]中的式(7)一致，同理可得结果(a).其中拉普拉斯变换保证了解的唯一性.

针对交互系统X(J)(t)=(X1(J)(t),…,XJ(J)(t))，定义

(7)

δx表示在单点x处的狄克拉测度.{UJ(t)}t≥0描述了队长的经验分布的变化过程；PJ表示经验测度过程{UJ(t)}t≥0的概率分布.

定义2假设u∈P1(E)，如果满足以下条件：

1)P°X0-1=u；

2)P°Xt-1=ut；

(Xs)ds,Ft,P)是鞅.

则称P∈P(D∞(E),F)是鞅问题[u,Ω‖ut‖]的解.

引理得证.

(8)

由引理1可得

取s=0，可得

(9)

设

PJ(E)=

UJ(t)是D∞(PJ(E))上的马尔可夫测度值过程,该过程的转移速率矩阵为

对应的算子为

(10)

利用泰勒公式可得

(11)

整理得

(12)

因为{UJ：J≥1}在D∞(PJ(E))上是弱紧的，所以对任意的{J′}⊂{J},存在{J″}⊂{J′}，使得UJ″弱收敛到U.当J趋于无穷时，由式(9)和(12)可知P∞是以G为生成元的鞅问题的解，

GF(ν)=f′(〈ν,φ〉)〈ν,Ωh,νφ〉.

令f(x)=x和f(x)=x2，可得

与文献[19]中的定理1.1的证明过程相似.因此可知U(t)是非线性主方程(1)的解，由命题1可知解是唯一的，定理证明完毕.

3 平稳分布

定理2在JSQ系统中，假设λ+λs<μ，则唯一的平稳分布为

π0JSQ=1-ρ,πkJSQ=ρ(1-σ)σk-1,k≥1，

(14)

其中：

证明由定理1可知极限典型队列在时刻t的Q矩阵可表示为

在平稳条件λ+λs<μ下，如果时间t趋于∞，则

由πQ=0，π=(π1,π2,…)可得

所以

最终可得

证毕.

如果一个智能客户可以随机地加入一个队列，则对应的Q矩阵为

(15)

对JSQ系统和J∞Q系统的平稳分布进行对比可得：

(1)π0JSQ=π0J∞Q，两个系统的空闲率是相等的.通过计算可得JSQ系统和J∞Q系统的平均到达率和平均服务速率均相等，因此空闲率相等.平均到达率为

平均服务速率为

图1 JSQ系统与J∞Q系统的平稳分布对比

由图1可得，存在k0，当1≤kπkJ∞Q；当k≥k0时，πkJSQ<πkJ∞Q.

(3)JSQ的平均队长小于J∞Q的平均队长.

JSQ的平均队长为

J∞Q的平均队长为

综上所述，JSQ规则下的Jackson网络的性能得到了提高.

4 结语

将加入最短队列规则引入Jackson网络中，建立了一个平均场相互作用模型，从极限结果的角度研究了该网络的性能.结果表明：队列长度的经验分布收敛到非线性主方程的唯一解；将加入最短队列模型和智能到达者随机加入J个队列中的任意一个的模型进行对比，得出加入最短队列规则提高了Jackson网络的性能.