排队时间

2024-10-14

排队时间（共4篇）

排队时间篇1

在多媒体通信网络中,通常采用优先级策略来满足多媒体业务流的QoS(QualityofService)需求。优先级策略又分为静态(static)和动态(dynamic)两类:静态优先级能够较好地满足高优先级业务流的性能指标,但有时会造成低优先级业务流延时和丢包率的增加;而动态优先级可以改善这个问题,在满足高优先级业务流性能的同时,可以减少低优先级业务流的延时、降低低优先级业务流的丢包率,从而在多媒体网络中得到了广泛的应用。

关于动态优先级队列的性能分析,有了一些研究成果[1,2,3,4],但目前的研究大多是基于连续时间,而现代通信网络多为数字通信网络,采用离散时间模型来分析网络性能更为准确,由此采用基于离散时间的D-MAP/PH/1排队模型来研究动态优先级队列。对于带有优先级的D-MAP/PH/1排队模型,文献[5]给出了相应的分析,而结合动态优先级的D-MAP/PH/1排队模型目前还未发现。在以上文献的研究基础上,通过矩阵几何解的方法求解该模型的平稳分布,进而得出模型的各项性能指标。

1排队模型描述

考虑到网络业务流的相关性和突发性,假设网络中业务流到达过程为一类m状态的离散时间马氏到达过程(discrete-time Markovian arrival process, D-MAP),且该过程包含高、低两类优先级业务流的到达[5],其中高优先级为延时敏感业务流(如语音、视频),低优先级为延时不敏感业务流(如数据)。该D-MAP相应的参数矩阵可由随机阵D0、D11、D12和D2描述,其基础马氏链的转移概率矩阵有D=D0+D11+D12+D2。其中元素(D0)ij表示一个时隙内过程由i转到j且没有到达的概率,(D11)ij表示高优先级有一个到达的概率,(D12)ij表示低优先级有一个到达的概率,(D2)ij表示高、低优先级均有到达的概率。高、低优先权数据包的到达率分别为:λ1=η(D11+D2)e,λ2=η(D12+D2)e。其中η为D的左不变概率向量,满足ηD=η和ηe=1,e为相应维数分量全为1的列向量。D-MAP具有一般性,可以更好地刻画业务流的相关性和突发性,它是马尔科夫调制伯努里过程(MMBP)以及伯努里过程等特殊到达过程的扩展。

假设高、低两类业务流的服务时间均服从离散PH分布[5,6,7],且分别有n1阶PH分布(α(1),T(1))和n2阶PH分布(α(2),T(2))。PH分布具有稠密性,它可以拟合任意非负随机变量的分布,且比较适于拟合服务时间分布[6]。

高、低两类业务流到达后若得不到及时地调度,则分别进入各自的缓存队列(容量分别为K1和K2)排队等待。两类业务流的服务规则由低优先级队长决定,遵循带有伯努里转换的队长门限(queue-length-threshold, QLT)调度策略[3,4],如图1所示。若低优先级队列长度低于门限L,则调度器只为高优先级业务流服务,此时高优先级业务流具有抢占优先权;否则调度器以概率p为低优先级业务流服务,以概率q=1-p为高优先级业务流服务;此外,若高、低优先级缓存有一个为空,则调度器只为另一个不空的队列服务。

由以上描述可知,该队列模型为一类基于伯努里转换QLT调度策略的D-MAP/PH/1排队系统。

2模型分析

2.1系统状态转移概率矩阵

令I $_{n}^{1}$ 和I $_{n}^{2}$ 分别表示n时刻系统中高、低优先级顾客(业务流)数(包括正在被服务的顾客);Jn表示n时刻顾客到达过程所处的状态;Fn表示n时刻服务台(调度器)所处的状态,Fn=0、1、2分别表示服务台空闲、正在为高优先级和低优先级顾客服务;S $_{n}^{1}$ 和S $_{n}^{2}$ 分别表示n时刻高、低优先级顾客在服务过程中的位相。再令Zn=(I $_{n}^{1}$ ,I $_{n}^{2}$ ,Jn,Fn,S $_{n}^{1}$ ,S $_{n}^{2}$ ),n≥0,则Zn为马尔科夫链,有状态空间Ω=Ω1∪Ω2∪ Ω3∪Ω4∪Ω5。其中Ω1={(0,0,0,j),1≤j≤m}表示系统中没有顾客,且到达过程处于位相j;Ω2={(i1,i2, 1,j,s1),1≤i1≤K1+1,0≤i2≤L,1≤j≤m,1≤s1≤n1}表示系统中低优先级队列长度低于门限L,且服务台正为高优先级顾客服务,服务位相为s1;Ω3={(i1,i2,1,j,s1),1≤i1≤K1+1,L<i2≤K2+1,1≤j≤m,1≤s1≤n1},表示系统中低优先级队列长度等于或高于门限L,且服务台正为高优先级顾客服务,服务相位为s1;Ω4={(i1,i2,2,j,s2),1≤i1≤K1+1,L<i2≤K2+1,1≤j≤m,1≤s2≤n2}表示系统中低优先级队列长度高于门限L,且服务台正为低优先级顾客服务,服务相位为s2;Ω5={(0,i2,2,j,s2), 1≤i2≤K2+1,1≤j≤m,1≤s2≤n2}表示系统中只有低优先级顾客,且服务相位为s2。

由于状态空间Ω有限,则该马尔科夫链存在唯一的平稳分布,根据模型描述,其一步转移概率矩阵P可表示为如下分块形式:

$Ρ = (\begin{matrix} B_{00} & B_{01} \\ B_{10} & A_{1} & A_{0} \\ A_{2} & A_{1} & A_{0} \\ ⋱ & ⋱ & ⋱ \\ A_{2} & A_{1} & A_{0} \\ A_{2} & A_{1} + A_{0} \end{matrix})$

。

上面矩阵中:

$B_{00} = (\begin{matrix} B_{00}^{00} & B_{00}^{01} \\ B_{00}^{10} & B_{00}^{1} & B_{00}^{0} \\ B_{00}^{2} & B_{00}^{1} & B_{00}^{0} \\ ⋱ & ⋱ & ⋱ \\ B_{00}^{2} & B_{00}^{1} & B_{00}^{0} \\ B_{00}^{2} & B_{00}^{1} + B_{00}^{0} \end{matrix})$

其中B $_{00}^{00}$ =D0表示一个时隙内高、低优先级均无到达的一步转移概率矩阵;B $_{00}^{01}$ =D12⨂α(2)表示高优先级无到达,低优先级到达一个并进入服务台服务的一步转移概率矩阵;B $_{00}^{10}$ =D0⨂T0(2)表示高、低优先级均无到达,且低优先级服务完一个的一步转移概率矩阵;同理可求得B00及转移概率矩阵P中其余各分块矩阵,具体表示如下:

$\begin{array}{l} B_{01} = \begin{matrix} 0 \\ 1 \\ ⋮ \\ L - 1 \\ L \\ L + 1 \\ L + 2 \\ ⋮ \\ Κ_{2} \\ Κ_{2} + 1 \end{matrix} (\begin{matrix} B_{01}^{00} & B_{01}^{01} \\ B_{01}^{10} & B_{01}^{1} & B_{01}^{0} \\ ⋱ & ⋱ & ⋱ \\ B_{01}^{10} & B_{01}^{1} & B_{01}^{0} \\ B_{01}^{10} & B_{01}^{1} & B_{01}^{2} \\ B_{01}^{10} & B_{01}^{3} & B_{01}^{2} \\ B_{01}^{4} & B_{01}^{3} & B_{01}^{2} \\ ⋱ & ⋱ & ⋱ \\ B_{01}^{4} & B_{01}^{3} & B_{01}^{2} \\ B_{01}^{4} & B_{01}^{3} + B_{01}^{2} \end{matrix}) ‚ \\ B_{01}^{00} = D_{11} ⨂ α (1) ‚ B_{01}^{01} = D_{2} ⨂ α (1) ‚ B_{01}^{10} = D_{11} ⨂ Τ^{0} (2) \cdot α (1) ‚ B_{01}^{1} = D_{11} ⨂ Τ (2) \cdot e \cdot α (1) + D_{2} ⨂ Τ^{0} (2) \cdot α (1) ‚ \\ B_{01}^{0} = D_{2} ⨂ Τ (2) \cdot e \cdot α (1) ‚ \\ B_{01}^{2} = [\begin{matrix} 0 & D_{2} ⨂ Τ (2) \end{matrix}] ‚ \end{array}$

B $_{01}^{3}$ =[D2⨂T0(2)α(1)q D11⨂T(2)+D2⨂T0(2)α(2)p],

B $_{01}^{4}$ =[D11⨂T0(2)α(1)q D11⨂T0(2)α(2)p];

$\begin{array}{l} B_{10} = \begin{matrix} 0 \\ 1 \\ ⋮ \\ L \\ L + 1 \\ ⋮ \\ Κ_{2} \\ Κ_{2} + 1 \end{matrix} (\begin{matrix} B_{10}^{00} & B_{10}^{0} \\ B_{10}^{1} & B_{10}^{0} \\ ⋱ & ⋱ \\ B_{10}^{1} & B_{10}^{0} \\ B_{10}^{3} & B_{10}^{2} \\ ⋱ & ⋱ \\ B_{10}^{3} & B_{10}^{2} \\ B_{10}^{3} + B_{10}^{2} \end{matrix}) ‚ \\ B_{10}^{00} = D_{0} ⨂ Τ^{0} (1) ‚ B_{10}^{0} = D_{12} ⨂ Τ^{0} (1) \cdot α (2) ‚ B_{10}^{1} = D_{0} ⨂ Τ^{0} (1) \cdot α (2) ‚ \\ B_{10}^{3} = (\begin{matrix} D_{0} ⨂ Τ^{0} (1) \cdot α (2) \\ 0 \end{matrix}) ‚ \\ B_{10}^{2} = (\begin{matrix} D_{12} ⨂ Τ^{0} (1) \cdot α (2) \\ 0 \end{matrix}) ； \end{array}$

$\begin{array}{l} A_{1} = \begin{matrix} 0 \\ 1 \\ ⋮ \\ L - 1 \\ L \\ L + 1 \\ L + 2 \\ ⋮ \\ Κ_{2} \\ Κ_{2} + 1 \end{matrix} (\begin{matrix} A_{1}^{1} & A_{1}^{0} \\ 0 & A_{1}^{1} & A_{1}^{0} \\ ⋱ & ⋱ & ⋱ \\ 0 & A_{1}^{1} & A_{1}^{0} \\ 0 & A_{1}^{1} & A_{1}^{2} \\ A_{1}^{3} & A_{1}^{4} & A_{1}^{5} \\ A_{1}^{6} & A_{1}^{4} & A_{1}^{5} \\ ⋱ & ⋱ & ⋱ \\ A_{1}^{6} & A_{1}^{4} & A_{1}^{5} \\ A_{1}^{6} & A_{1}^{4} + A_{1}^{5} \end{matrix}) ‚ \\ A_{1}^{1} = D_{0} ⨂ Τ (1) + D_{11} ⨂ Τ^{0} (1) \cdot α (1) ‚ \\ A_{1}^{0} = D_{12} ⨂ Τ (1) + D_{2} ⨂ Τ^{0} (1) \cdot α (1) ‚ \end{array}$

$A_{1}^{2} = [D_{12} ⨂ Τ (1) + D_{2} ⨂ Τ^{0} (1) α (1) q D_{2} ⨂ Τ^{0} (1) α (2) p]$ ,

$A_{1}^{4} = [\begin{matrix} D_{0} ⨂ Τ (1) + D_{11} ⨂ Τ^{0} (1) α (1) q & D_{11} ⨂ Τ^{0} (1) α (2) p \\ D_{12} ⨂ α (1) ⨂ Τ^{0} (2) q & D_{0} ⨂ Τ (2) + D_{12} ⨂ Τ^{0} (2) α (2) p \end{matrix}]$

$A_{1}^{5} = [\begin{matrix} D_{12} ⨂ Τ (1) + D_{2} ⨂ Τ^{0} (1) \cdot α (1) \cdot q & D_{2} ⨂ Τ^{0} (1) \cdot α (2) \cdot p \\ 0 & D_{12} ⨂ Τ (2) \end{matrix}]$

$A_{1}^{3} = (\begin{matrix} 0 \\ D_{0} ⨂ α (1) ⨂ Τ^{0} (2) \end{matrix})$

$A_{1}^{6} = (\begin{matrix} 0 & 0 \\ D_{0} ⨂ α (1) ⨂ Τ^{0} (2) \cdot q & D_{0} ⨂ Τ^{0} (2) \cdot α (2) \cdot p \end{matrix})$

;

$A_{2} = \begin{matrix} 0 \\ ⋮ \\ L - 1 \\ L \\ L + 1 \\ ⋮ \\ Κ_{2} \\ Κ_{2} + 1 \end{matrix} (\begin{matrix} A_{2}^{1} & A_{2}^{0} \\ ⋱ & ⋱ \\ A_{2}^{1} & A_{2}^{0} \\ A_{2}^{1} & A_{2}^{2} \\ A_{2}^{3} & A_{2}^{4} \\ ⋱ & ⋱ \\ A_{2}^{3} & A_{2}^{4} \\ A_{2}^{3} + A_{2}^{4} \end{matrix})$

A $_{2}^{1}$ =D0⨂T0(1)·α(1),A $_{2}^{0}$ =D12⨂T0(1)·α(1),

$A_{2}^{2} = [\begin{matrix} D_{12} ⨂ Τ^{0} (1) \cdot α (1) \cdot q & D_{12} ⨂ Τ^{0} (1) \cdot α (2) \cdot p \end{matrix}]$ ,

$A_{2}^{3} = (\begin{matrix} D_{0} ⨂ Τ^{0} (1) \cdot α (1) \cdot q & D_{0} ⨂ Τ^{0} (1) \cdot α (2) \cdot p \\ 0 & 0 \end{matrix})$

$A_{2}^{4} = (\begin{matrix} D_{12} ⨂ Τ^{0} (1) \cdot α (1) \cdot q & D_{12} ⨂ Τ^{0} (1) \cdot α (2) \cdot p \\ 0 & 0 \end{matrix})$

;

$\begin{array}{l} A_{0} = \begin{matrix} 0 \\ 1 \\ ⋮ \\ L - 1 \\ L \\ L + 1 \\ L + 2 \\ ⋮ \\ Κ_{2} \\ Κ_{2} + 1 \end{matrix} (\begin{matrix} A_{0}^{1} & A_{0}^{0} \\ 0 & A_{0}^{1} & A_{0}^{0} \\ ⋱ & ⋱ & ⋱ \\ 0 & A_{0}^{1} & A_{0}^{0} \\ 0 & A_{0}^{1} & A_{0}^{2} \\ A_{0}^{3} & A_{0}^{4} & A_{0}^{5} \\ A_{0}^{6} & A_{0}^{4} & A_{0}^{5} \\ ⋱ & ⋱ & ⋱ \\ A_{0}^{6} & A_{0}^{4} & A_{0}^{5} \\ A_{0}^{6} & A_{0}^{4} + A_{0}^{5} \end{matrix}) ‚ \\ A_{0}^{1} = D_{11} ⨂ Τ (1) ‚ A_{0}^{0} = D_{2} ⨂ Τ (1) ‚ \end{array}$

$A_{0}^{2} = [\begin{matrix} D_{2} ⨂ Τ (1) & 0 \end{matrix}] ‚ A_{0}^{3} = (\begin{matrix} 0 \\ D_{11} ⨂ α (1) ⨂ Τ^{0} (2) \end{matrix})$

$A_{0}^{4} = (\begin{matrix} D_{11} ⨂ Τ (1) & 0 \\ D_{2} ⨂ α (1) ⨂ Τ^{0} (2) \cdot q & D_{11} ⨂ Τ (2) + D_{2} ⨂ Τ^{0} (2) \cdot α (2) \cdot p \end{matrix}) ‚$

$A_{0}^{5} = (\begin{matrix} D_{2} ⨂ Τ (1) & 0 \\ 0 & D_{2} ⨂ Τ (2) \end{matrix})$

$A_{0}^{6} = (\begin{matrix} 0 & 0 \\ D_{11} ⨂ α (1) ⨂ Τ^{0} (2) \cdot q & D_{11} ⨂ Τ^{0} (2) \cdot α (2) \cdot p \end{matrix})$

。

上面矩阵分块中0表示相应阶数元素全为零的矩阵,符号⨂为Kronecker乘法[8],T0(1)= e-T(1)·e,T0(2)=e-T(2)·e。

2.2稳态分析

由2.1节得到的转移概率矩阵P的矩阵结构可知,P为拟生灭(quasi-birth-death, QBD[6,7])型结构阵,下面求解该马氏链的平稳分布。记:

$(Ι^{1}, Ι^{2}, J, F, S^{1}, S^{2}) = \lim_{n \to \infty} Ζ_{n} = \lim_{n \to \infty} (Ι_{n}^{1}, Ι_{n}^{2}, J_{n}, F_{n}, S_{n}^{1}, S_{n}^{2})$ ;

π00j0=Pr{I1=0,I2=0,J=j,F=0},1≤j≤m;

π00=(π0010,π0020,…,π00j0,…,π00m0);

π0i2j2s2=Pr{I1=0,I2=i2,J=j,F=2,S2=s2},

1≤i2≤K2+1,1≤j≤m,1≤s2≤n2;

π0i2=(π0i211,…,π0i21n2,π0i221,…,π0i22n2,…,π0i2m1,…,

π0i2mn2),1≤i2≤K2+1;

πi1i2j1s1=Pr{I1=i1,I2=i2,J=j,F=1,S1=s1},

1≤i1≤K1+1,0≤i2≤L+1,1≤j≤m,1≤s1≤n1;

πi1i2j2s2=Pr{I1=i1,I2=i2,J=j,F=2,S2=s2},

1≤i1≤K1+1,L+1<i2≤K2+1,1≤j≤m,1≤s2≤n2;

πi1i2=(πi1i2111,…,πi1i211n1,πi1i2211,…,πi1i221n1,…,πi1i2m11,

…,πi1i2m1n1),1≤i1≤K1+1,0≤i2≤L+1;

πi1i2=(πi1i2111,…,πi1i211n1,πi1i2121,…,πi1i212n2,…,πi1i2m11,…,

πi1i2m1n1,πi1i2m21,…,πi1i2m2n2),1≤i1≤K1+1,L+1<i2≤K2+1;

πi1=(πi10,πi11,…,πi1i2,…,πi1K2,πi1K2+1),

0≤i1≤K1+1,0≤i2≤K2+1;

π=(π0,π1,…,πi1,…,πK1,πK1+1),

0≤i1≤K1+1。

π为对应于转移概率矩阵P的稳态概率向量,有平衡方程πP=π,于是可得到下列矩阵方程组:

${\begin{cases} π_{0} B_{00} + π_{1} B_{10} = π_{0}, \\ π_{0} B_{01} + π_{1} A_{1} + π_{2} A_{2} = π_{1}, \\ π_{i_{1}} A_{0} + π_{i_{1}} A_{1} + π_{i_{1} + 1} A_{2} = π_{i_{1}}, 1 < i_{1} \leq Κ_{1}, \\ π_{Κ_{1}} A_{0} + π_{Κ_{1} + 1} (A_{1} + A_{0}) = π_{Κ_{1} + 1} 。 \end{cases}$

这些方程可递推地求解如下。

(1)由最后一个方程可得:πK1+1=πK1·A0·(I-A0-A1)-1=πK1·RK1+1,其中I为单位阵。

(2)将(1)得到的结果依次向上代入并递推可得:当2≤i1≤K1时,πi1=πi1-1·Ri1,其中Ri1=A0·(I-A1-Ri1+1·A2)-1。

(3)将(2)得到的结果代入第二个方程可得:π1=π0·R1,其中R1=B01·(I-A1-R2·A2)-1。

(4)由以上几步可得: $π_{i_{1}} = π_{0} \cdot \hat{R}_{i_{1}}$ ,其中: $\hat{R}_{i_{1}} = \prod_{j = 0}^{i_{1}} R_{j} ‚ R_{0} = Ι ‚ 0 \leq i_{1} \leq Κ_{1} + 1$ 。

(5)将(3)得到的结果代入第一个方程可得:π0·(B00+R1·B00-I)=0,再结合下列正规化条件则可确定π0:

$π \cdot e = \sum_{i_{1} = 0}^{Κ_{1} + 1} π_{i_{1}} \cdot e = π_{0} \sum_{i_{1} = 0}^{Κ_{1} + 1} \hat{R}_{i_{1}} \cdot e = 1$ 。

2.3性能指标

由2.2节分析可得到以下性能指标:

(1)稳态条件下系统中高、低优先级数据包的个数即稳态队长分别为:

$Ρ (i_{1}) = π_{i_{1}} \cdot e ‚ Ρ (i_{2}) = \sum_{i_{1} = 0}^{Κ_{1} + 1} π_{i_{1} i_{2}} \cdot e$ ;

进而高、低优先权数据包的平均队长分别为:

$\bar{L}_{1} = \sum_{i_{1} = 1}^{Κ_{1} + 1} i_{1} \cdot π_{i_{1}} \cdot e ‚ \bar{L}_{2} = \sum_{i_{2} = 1}^{Κ_{2} + 1} i_{2} \cdot (\sum_{i_{1} = 0}^{Κ_{1} + 1} π_{i_{1} i_{2}} \cdot e)$ 。

(2)高、低优先级业务流的阻塞概率,即缓存满的概率分别为:

$Ρ_{l o s s 1} = π_{Κ_{1} + 1} \cdot e ‚ Ρ_{l o s s 2} = \sum_{i_{1} = 0}^{Κ_{1} + 1} π_{i_{1} Κ_{2} + 1} \cdot e$ 。

(3)直接运用little定理,可得高、低优先权数据包的平均延时分别为:

$\bar{W}_{1} = \frac{\sum_{i_{1} = 1}^{Κ_{1} + 1} i_{1} \cdot π_{i_{1}} \cdot e}{λ_{1}} ‚ \bar{W}_{2} = \frac{\sum_{i_{2} = 1}^{Κ_{2} + 1} i_{2} \cdot (\sum_{i_{1} = 0}^{Κ_{1} + 1} π_{i_{1} i_{2}} \cdot e)}{λ_{2}}$ 。

3结束语

在多媒体网络中采用动态优先级可以较好地实现高、低优先级业务流的性能。采用离散时间D-MAP/PH/1排队模型来研究多媒体网络动态优先级队列,运用矩阵几何解的方法,分析了该模型的稳态分布,得到了主要的网络性能指标。

摘要：动态优先级队列能够较好地满足多媒体网络业务流的多种QoS需求。采用离散时间的D-MAP/PH/1排队模型来研究动态优先级队列,并应用矩阵分析的方法,对该排队模型的稳态分布进行分析,得到了系统的主要性能指标:两类业务流的平均队长、阻塞概率和平均延时等结果。

关键词：动态优先级队列,离散时间排队,D-MAP/PH/1,矩阵几何解

参考文献

[1]Fratini S.Analysis of a dynamic priority queue.Commun Stat Stoch Model,1990;6(3):415—444

[2]Lee D,Sengupta B.Queueing analysis of a threshold based priority scheme for ATM networks.IEEE/ACM Trans Netw,1993;1(6):709—717

[3]Choi B,Choi D I.An analysis of M,MMPP/G/l queue with QLT scheduling policy and Bernoulli schedule.IEICE Trans-Commun,1998;81B(1):13—22

[4]Choi D I,Lee Y.Performance analysis of a dynamic priority queue for traffic control of bursty traffic in ATM networks.IEE Proc-Com-mun,2001;148(3):181—187

[5]Alfa A S.Matrix-geometric solution of discrete time MAP/PH/1pri-ority queue.Naval Research Logistics,1998;45:23—50

[6]Neuts M F.Matrix-geometric solutions in stochastic models.Balti-more:The Johns Hopkins University Press,1981

[7]田乃硕,李泉林.PH分布及其在随机模型中的应用.应用数学与计算数学学报,1995;9(2):1—15

[8]GrahamA.Kronecker products and matrixcalculus with applications.New York:Horwood Halsted Press,1981

排队时间篇2

我院门诊病人取药高峰时段为上午10:00——12:00，下午13:30——14:30。西药房正常情况下开3个取药窗口，中药房开1个取药窗口。

排队取药等候时间长的原因

1、正常工作流程占用时间长。

取药流程：药房工作人员收到取药人就诊卡——刷卡——打印处方——审方——调配——核对——发药——交代用法和注意事项，按每张处方平均需要2分钟计算，每个窗口每小时只能调配30张处方，上午取药高峰时段的两个小时时间，3个取药窗口只能调配不到200张处方。虽时有排队现象，但每个取药窗口排队一般不超过5人。

2、替午人员接班后，其余工作人员下班早。

排队时间篇3

各种原因导致的城市道路交通拥挤已经成为常态并明显制约了城市的运行效率, 由此衍生的各种问题, 如排放 (emission) , 事故 (accident) 也在消耗着城市资源;如北京的“通勤困扰指数”已为全球前三, 持续地改进交通状况的任务紧迫而艰巨。在城市内部可主要通过发展公交等多种出行方式分担以缓解拥挤;在城市外围, 公共交通网络覆盖度及道路密度降低, 进出城仍以机动车为主且集中度提高, 尤其在城际高速公路联络线与城市快速路网的结合部, 大量不同性质车流快速交汇、转换, 极易造成阻塞并蔓延为网络形态;如北京城区北部的八达岭、京张, 东南部的京津塘高速等及关联的快速路等。2010年8月14日开始持续10余天的G 6京藏高速公路北京段 (原八达岭高速公路) 的大拥堵, 引起了广泛的关注[1];2010年9月17日, 北京市区出现大面积、长时间拥堵, 晚高峰时拥堵路段超过140条, 车速低于20km/h, 二至五环全面拥堵, 拥堵主要集中在二环、三环、四环等环路的连接路口及互通式立交桥处。各条高速公路进城联络线拥堵也十分严重, 尤其在环路出入口, 车辆排队严重, 总体拥堵时段长达11h[2]。大范围长时间的结合部路网的拥堵, 迫使人们去寻找解决方法。作为其中一种主要的控制方式, 结合部路网匝道交通控制受到关注。

1匝道多目标协调控制

匝道控制是一种比较有效预防和缓解道路拥堵的控制方式[3], 属于多目标协调与优化问题;其中存在多个彼此冲突的目标, 如主线的密度与速度、速度与流量、匝道排队长度及等待时间与主线速度等。某个目标的改善可能引起其他目标性能的降低, 如主线密度的升高会引起速度的降低, 密度的降低又可能会引起匝道排队长度的增加及等待时间的延长等, 同时使多个目标达到最优是比较困难的, 只能在各个目标之间进行协调, 以使所有设定的控制目标尽可能达到一个理想值。

控制目标值的选取直接决定后续控制方程的建立和控制效果的评价, 这里有两个问题需要注意:

(1) 如何选择指标可以既反映主线的状态同时也反映匝道的状态, 既要达到道路管理和控制的目标, 又要兼顾道路使用者的实际情况;

(2) 主线和匝道的状态, 既要避免信息冗余, 也要避免息缺失。

统筹考虑主线状态与匝道约束的情况下的协调控制, 其中包含的匝道排队的描述以及控制参数的确定值得深入探讨。

2一种新的匝道排队等待时间模型

2.1传统的匝道等待时间模型及分析

以往的研究中, 对于主线及匝道的系统时间[4—9]一般采用TTS (TotalTimeSpent-系统总时间, 包括所有主线车辆的行驶时间及匝道车辆的等待时间) 、FTT (FreewayTravelTime-主线车辆的行驶时间) 或FQT (FreewayQueuingTime-主线延误时间) , 其中匝道排队等待时间 (一般称为匝道延误-Ramp Delays) 均采用匝道特定控制周期内的等待车辆数与控制周期时长的简单关系式来表示, 实质为总体排队时间 (Tt) , 其计算一般使用l (j) 与T的乘积之和 (单匝道排队等待时间) 或积分形式 (多匝道时排队等待时间的综合) , 即:

式 (1) 中, l (j) 表示第j个周期内的排队等待车辆数, T表示控制周期的长度;式 (2) 表示多个匝道的总的排队等待时间, 其中i=1, 2, …, m表示匝道编号, li (j) 表示第i个匝道在第j个周期内的排队等待车辆数, 这种模型中Tt仅是l (j) 与T的函数, 由于T一般不变, 则Tt就仅决定于动态的排队长度l (j) , 实质上是一个参数。其他的研究中, 也有在此基础上发展的考虑多匝道协同控制时的各匝道排队等待时间的公平性问题[10], 即利用匝道排队等待时间与匝道平均等待时间设计了平均等待时间的方差指标, 其实质还是属于总体排队时间 (Tt) 概念的应用, 如式 (3—5) 所示。

其中, 式 (3—5) 中, t (k) 及tm (k) 分别表示所有受控匝道车辆排队平均等待时间及匝道m的等待时间, n为受控入口匝道数, k为受控周期数。这种计算的思想依然来源于Tt的概念, 将匝道排队的车辆视作相同的整体, 只反映了某一个周期内特定匝道的排队等待车辆数这一个特征, 并不能反映排队等待车辆中个体的差异以及排队形成的原因。在比较特殊的情况下, 此指标的应用效果也很好 (在后续4.相关分析与结论中会对此情况进行详细的对比说明) 。但是更一般的情况下, 对于匝道排队等待时间长度的描述以及多匝道排队等待时间公平性的判断上就会造成信息缺失。可以认为, Tt的计算属于宏观层面, 在更一般的情况下, 需要考虑微观个体车辆之间的差别和特性。

例如, 有若干个入口匝道i=1, 2, …, m, …n, 假设在所有受控周期kT (k=1, 2, …, j, …) 内所有匝道的排队等待长度li (j) 完全相同, 那么按照前述关于匝道排队等待时间的描述模型计算, 则每一个受控周期内所有匝道的等待是完全公平的, 此时t (k) =tm (k) , Var=0。如果这种现象形成的原因是因为其中有若干个匝道的控制律序列一直很小, 入口流率需求也较小, 即d (j) 与r (j) 相当, 这种情况下, 匝道排队形成之后变化不大;而另有一些匝道d (j) 与r (j) 都较大, 这种情况下, 表面上所有匝道形成的排队长度l (j) 是相同的, 但在前一类型的匝道中, 车辆等待往往超过一个周期, 可能从匝道入口处进入匝道到匝道出口汇入主线需要若干个周期, 这期间, 车辆一直参与形成排队, 这一部分时间也必须计算在排队等待时间之内, 此时, t (k) ≠tm (k) , Var≠0, 在特殊情况下, 有可能出现Var=1, 而这种情况, 按照以往的模型是无法反映出来的。那么, 从以上的分析可以看出, 即使表面上所有匝道的排队长度是一样的, 但是排队中的个体车辆经过的周期数是不一样的, 等待时间是不同的, 排队的累积时间也就出现了差别。在实际的匝道控制中, 往往出现这种情况, 对此问题的探讨具有比较重要的现实意义。因此, 有必要采取新的思路, 建立新的模型描述这种现象。

2.2以循环等待时间为基础的匝道等待时间模型

本质上, 以往研究中的总体排队时间 (Tt) 实际上是在每个控制周期开始时对以往所有车辆排队形成的等待时间进行清零处理然后重新计算, 掩盖了匝道中部分车辆等待超过一个周期的情况, 使得信息丢失。而且在多目标的协调控制中, 如果相关的匝道指标l (j) 和d (j) 以及主线交通流指标qp (j) 均比较小的情况下, 将产生Tt基本保持不变 (满足控制目标, 控制方程结果较优) 而Ts持续增加 (远大于控制目标) 的矛盾, 将有部分车辆进入连续循环等待状态而无法刺激产生有效的r (j) , 如图1。

由于l (j) 是d (j) 与r (j) 的函数, 即l=f (d, r) , 而单车等待时间仅与j=k时的累积l (k) 、j>k时的 r (j) 及T有关, 与j>k时的d (j) 无关。因此, 本文提出一种新的匝道排队等待时间模型, 其中考虑单车的匝道等待累积时间Ts。

在改进的匝道排队等待时间的模型描述中, d (j) 意义不变, r (j) 可表示主线的服务率, 借鉴信号控制交叉口过饱和交通流情况下的车辆等待时间的计算方法, 设计了基于排队论思想的一般单车等待累积时间Ts为:

$\sum_{j = k + 1}^{n}$ rjT= $\sum_{j = 0}^{k}$ (dj-rj) T+1 (6)

Ts= (n-k-1) T (7)

在模型设计的基础上, 在本文后续的控制中采用Ts-Tt指标:其中Ts为单车等待时间之和, Ts-Tt在定义为循环等待时间, 用以计算匝道排队等待的车辆是否存在等待多个周期的情况。如果Ts-Tt=0, 表示一个内匝道排队等待的车辆可以全部进入主线;同理, 如果Ts-Tt指标小表明r (j) 可以有效疏解排队, 指标大表明匝道排队中部分车辆有循环等待现象。同时, 由于Ts-Tt计算的是累计值, 即使匝道排队等待的车辆较少, 通过Ts-Tt也可以明显反映出等待时间的大小, 而仅通过Tt的计算则会出现信息丢失的情况, 无法反映真实的排队等待时间大小。

3 基于Ts-Tt的控制方程

在控制方程的第一步, 需要确定控制目标参数, 其中需要注意一下原则:

(1) 评价各参数之间需尽量减少信息冗余

交通流时空关联性强, 尤其在区域有限时各断面各交通流参数之间存在强烈相关性。在控制中, 既要根据控制目标选取合适的参数, 又要避免指标参数之间的信息重叠, 减少信息冗余, 用尽量少的指标反映最重要、最丰富的信息。

(2) 需要在主线与匝道等系统之间达到平衡

匝道控制本身的目的就是在至少两个系统之间寻求一种总体优化, 这其中包括了受控匝道、受控匝道出入口分别关联的主线等, 如果是多匝道的协同控制, 包括的系统更多, 系统内部的划分也更为复杂, 而匝道控制目标要充分反映各系统的变化。

(3) 评价需要反映现实情况。在评价中, 需要把握宏观交通流的变化特征, 应主要关注于宏观指标的变化和相互之间的关系。另一方面, 需要充分反映控制结果与实际情况的对比, 如排队长度与匝道容量的对比, 总体排队时间 (主线行驶时间与匝道个体车辆排队等待时间累积值之和) 前后的差异等。

根据以上3条原则, 在匝道多目标的协调控制方程的建立及后续的控制效果的评价中, 选取目标参数如下:

结合匝道控制的实质和宏观交通流本身的参数关联, 控制保持ρdown (k) <ρcr, 使qdown (k) =qdown (k) + r (k) 最大, 因此选择主线最大流量作为控制目标;主线区间速度和密度满足一定的关系, 而行程时间决定于区间速度, 因此在选择qdown (k) 后, 其他参数可不选择, 以避免信息冗余;考虑主线入口匝道对相连道路的排队队列溢出的影响, 选择l (k) ;考虑匝道本身用户的公平, 可以选择Tt。而匝道控制与交叉口信号控制性质不同, l (k) 和特定周期段内的Tt之间存在联系, 两者之间信息冗余度大;根据前述分析, Ts更具一般性。因此, 本文中单匝道协同控制目标确定为:qdown (k) 、l (k) 以及Ts-Tt三项。

综合以上分析, 单匝道协同控制问题的描述可总结为:对于已知时间段 (本研究为高峰期) 主线和匝道交通流状态以及辨识或设定的vf、ρcr等参数, 在满足主线及匝道约束的条件下, 求解控制序列r (j) , 设定合理的权重Q、S及R, 使得目标函数P最大。

P= $\sum_{j = 0}^{k}$ [Qqdown (k) T-Sl (k) T-R (Ts-Tt) T] (8)

控制状态方程可表示为

$\vec{X} (k + 1) = f (\vec{X} (k), r (k), \vec{D} (k))$ (9)

式 (9) 是一个强耦合、多扰动的非线性方程, 其中的 $\vec{X} (k) = [ρ_{d o w n} (k), l (k), t_{s}]$ 为输入变量, r (k) 为输出变量, $\vec{D} (k) = [q_{u p} (k), d (k)]$ 为扰动变量。

4 相关分析与结论

结合式 (8—9) , 对实地交通流数据进行处理, 利用ALINEA计算控制律, 并与无控制 (No Ctrl.) 时进行对比, 探讨本文提出的模型在对匝道排队等待时间的描述和控制中的作用。

在控制期间, 匝道排队的形成与长度规模主要取决于所有受控周期内动态的匝道调节率r (j) 和车辆到达率d (j) 之差的累积值的大小, 在实际中会出现以下4中情况:

(1) 如果r (j) 持续大于 d (j) , 匝道调节可以有效疏解排队, 则Ts等于Tt, 此时Ts-Tt=0, 即每个周期形成的排队在周期末都可以放行进入主线, 不存在等待超过一个周期的情况。但是这种情况往往出现在主线交通流的低密度区, 主线车流量小, 可汇流间隙较大, 或者d (j) 较小的情况, 此时一般不需要进行匝道控制, 系统可以进行自我调节。

(2) 在r (j) 与 d (j) 相当的情况下, 或者在所有受控周期内r (j) 与 d (j) 的累积值相当但是r (j) 不稳定, 出现时大时小的情况时, 此时Ts与Tt 差别不大。外在表现为在匝道控制过程中会出现某几个周期内Ts-Tt略大于零, 然后很快归零的情况, 如No Ctrl.的第3、7-8周期。

(3) 如果r (j) 持续小于 d (j) , 但差值较小时, 此时的Ts略大于Tt, Ts-Tt也维持在一个较小的区间, 匝道排队等待车辆中有很少部分的车辆等待时间超过一个周期。如No Ctrl.时的第1-15周期, ALINEA控制时的第 1-17周期。

(4) 如果r (j) 持续小于 d (j) 且差值较大时, 匝道调节无法有效疏解匝道入口流量, 则部分车辆等待超过一个周期, 这时Ts快速增加, Tt也同时增加, 但增加速率较Ts小, Ts-Tt同向增加但增速也小于Ts, 最典型的如ALINEA控制时的第18周期之后的Ts变化。

在 (2) 、 (3) 和 (4) 几种状态下, 匝道排队都会出现类似于信号交叉口控制中的“过饱和”情况, 只是程度不同。在这几种状态下, 如果仅使用Tt参数描述匝道等待情况, 部分车辆循环等待的信息将被掩盖, 这也是以往研究中一个忽略的问题。同时, Ts-Tt指标也从一个方面说明了匝道控制律算法的优异程度不仅取决于疏解总量的大小, 也取决于控制的稳定程度和抑制突变的能力。

本文提出了一种新的匝道排队等待模型, 并作为控制目标确定了相应的匝道多目标的协调控制方程, 通过实验对比, 表明所提模型可以有效的避免匝道控制中的信息缺失现象, 为未来系统的优化控制提供了有效的方法。

摘要：针对匝道多目标协调优化控制方程确立中的控制参数选择问题, 分析了现有研究中存在的信息冗余以及匝道排队状态描述中的信息缺失问题。基于排队论思想, 建立了一种新的考虑单车等待累积时间的匝道车辆排队时间模型, 并设计了表征循环等待时间的参数作为控制目标参数。在确立控制方程之后, 对两种不同情况下的控制做了对比, 结果表明, 所提模型可以有效避免匝道排队描述不符合实际的情况, 为控制方程的建立以及控制评价提供了一种新的思路和解决方法。

关键词：交通工程,匝道控制,总体匝道等待时间,单车等待累积时间,循环等待时间

参考文献

[1]http://www.cnn.com/2010/WORLD/asiapcf/08/23/china.traffic.jam/index.html ref=all search

[2]http://china.huanqiu.com/roll/2010-09/1111459.html

[3]Twin cities ramp meter evaluation final report.The Minnesota Depart-ment of Transportation (Mn/DOT) &Cambridge Systematics, Inc., 2001, Oakland, California, USA.

[4]Wattleworth J A.Peak-period analysis and control of a freeway sys-tem.Highway Research Record, 1965;157:1—21

[5]Papageorgiou M, Kotsialos A.Freeway ramp metering:an overview.IEEE Transactions on Intelligent Transportation Systems, 2002;3:271—281

[6]Ben-Akiva M, Cuneo D, Hasan M, et al.Evaluation of freeway con-trol using a microscopic simulation laboratory.Transportation Re-search Part C, 2003;11:29—50

[7]Papamichail I, Kotsialos A, Margonis I, et al.Coordinated ramp me-tering for freeway networks-Amodel-predictive hierarchical control ap-proach.Transportation Research Part C, 2010;18:311—331

[8]Kotsialos A, Papageorgiou M.Efficiency and equity properties of freeway network-wide ramp metering with AMOC.Transportation Re-search Part C, 2004;12:401—420

[9]Kotsialos A, Papagorgiou M, Mangeas M, et al.Coordinated and in-tegrated control of motorway networks via non-linear optimal control.Transportation Research Part C, 2002;10:65—84