-
摘要: 基于区分业务优先级和提高系统时延性能的网络需求，提出了依托站点状态的两级轮询控制系统.系统在混合服务两级轮询模型的基础上，根据站点缓冲区状态采用并行调度方式仅对有数据分组的活动站点提供服务.该模型既能满足区分站点优先级的需求又能避免空闲查询，从而提高系统利用率、降低等待时延.采用嵌入式马尔科夫链和概率母函数的方法对该系统建立数学模型，对系统平均等待时延特性进行了精确解析.通过理论计算与仿真实验结果的对比验证了理论分析的正确性，与已有两级轮询系统相比，具有更好的时延性能.Abstract: Based on priority differentiation and the system efficiency, this paper proposes a station dependent two-level polling system. The mixed service two-level polling system is extended by using queue state-dependent routing, in which only active stations with information packets could be visited by server. The scheme meets the requirement not only for conflict free but also for priority differentiation and efficiency, and provides a lower latency. An embedded Markov chain framework is set up to drive the closed-form expression for the mean waiting time. Numerical examples demonstrate that theoretical and simulation results are identical and the new system has a better efficiency at both key station and normal station.
-
Key words:
- Polling system /
- priority queue /
- performance evaluation /
- time-delay
-
轮询系统作为一类基于预约的调度控制模型,在计算机通信网络、交通控制、工业控制等领域得到广泛的运用[1].无线通信网络中随机多址接入方式易于实现分布式网络接入控制[2],但基于中心控制的轮询多址接入方式可以提供无冲突的信息接入,常被用于为时延敏感类业务提供时延保障[3].
在传统基于时分多址(Time devision multiple access,TDMA)的调度策略中,空闲侦听不仅浪费网络资源、增加能耗还会造成时延的增加.连续时隙分配方法[4]通过对忙站点持续分配时隙避免传输过程中的空闲侦听;Rasul等在此基础上通过对末尾数据包的标识,使接收者在完成数据接收后可以立即进行站点切换[5];在典型轮询系统完全服务方式中,服务器查询各站点完成缓冲队列中所有信息分组的服务后经过一个查询转换时间后服务下一站点,并行调动策略将查询和服务过程并行处理,使得服务器对忙站点的查询不再消耗查询转换时间[6]. 然而,上述方法由于调度表的生成独立于站点状态,在对空闲站点的处理中,接收者均需要在分配的第一个时隙没有收到数据后才能切换至下一个发送者;尤其当站点持续空闲,接收者在每轮时隙分配中都要对每个空闲站点进行空闲侦听. 可以看出,固定顺序的调度策略存在灵活性较差、资源利用率低(尤其在低负载环境下)和不能提供区分优先级服务不足.
针对区分优先级问题,文献[7-8]提出在队列内按顾客类型进行优先级区分.针对站点优先级的区分,文献[9-11]提出了区分排队优先权的两级轮询系统模型. 然而,上述模型中服务器按照固定路径查询包括空闲站点在内的所有站点,使信道利用率受到限制. 在前期工作中[6],我们采用并行调度两级轮询策略,在服务时间大于查询转换时间的条件下,针对忙站点将服务器的查询过程和服务过程并行处理,但仍然没有解决服务器对空闲站点的无效查询问题.文献[12]中提出区分站点状态的分布式组网方式用于提高Adhoc网络传输效率,但未针对节点优先级的区分问题展开讨论.
针对上述问题,本文基于动态轮询路径访问思想[13-14]提出了依托站点状态的两级轮询系统模型(Station-dependent two-level polling,SDTLP).系统根据站点是否有信息发送需求将其区分为活动状态和休眠状态;每轮查询依托站点缓冲区状态更新轮询表,服务器仅对有发送请求的活动站点进行查询; 另一方面,活动站点的服务过程按照混合服务两级轮询机制;服务过程与查询过程采用并行处理提供区分优先级服务. 此外,利用马尔科夫链和概率母函数的分析方法[15-16],本文深入分析了模型的时延特性;最后通过仿真实验验证了理论分析的正确性及系统有效性.
1. 系统模型
1.1 模型描述
如图 1所示,依托站点状态的两级轮询系统工作原理为:轮询系统由N个普通站点 $j,j=1,\cdots,N$ 和1个中心站点h组成.站点具有两种工作状态: 1) 活动状态,站点缓冲区中有信息分组需要发送; 2) 休眠状态: 缓冲区为空,如图 1中站点 $i.$ 每一轮服务开始前根据站点状态对轮询表进行更新,使服务器仅对活动站点进行查询.由于服务器查询的站点均有信息等待服务,因此在满足服务时间不小于查询转换时间的条件下,服务器可以在当前站点的服务过程中采用捎带技术完成下一个站点的查询,在对当前站点服务完成后立即开始对后继站点的服务. 在此服务期间,服务器在站点间的切换不再耗费查询转换时间还消除了空闲查询,从而降低信息分组发送的平均等待时间. 服务过程中,按照两级轮询原则,服务器每服务一个普通站点后都要转向中心站点,待中心站点完成信息发送后,服务器再转向下一个活动状态的普通站点.服务器对中心站点按照完全服务方式:每次服务需将缓冲区内信息分组完全清空才转至下一站点,对普通站点按照限定( $k=1$ )服务方式: 每次轮询仅发送1个信息分组.
1.2 变量说明及模型假设条件
定义随机变量 $\xi_i(n)$ 表示服务器在tn 时刻轮询普通站点 $i(i=1,2,\cdots,N)$ 时站点i缓存中等待的信息分组数; 此时,中心站点h缓存中排队等待服务的信息分组数为 $\xi_h(n)$ ,系统排队长度的状态变量为: $\{\xi_1(n),\cdots,\xi_i(n),\cdots,\xi_N(n),\xi_h(n)\}$ .服务器在 $t^*_n$ 时刻完成普通队列服务开始轮询中心站点,此时系统状态变量为 $\{\xi_1(n^*),\cdots,\xi_i(n^*),\cdots,\xi_N(n^*),\xi_h(n^*)\}$ . 服务器按完全服务策略服务中心站点,工作结束后在 $t_{n+1}$ 时刻轮询 $i+1$ 号普通队列,系统状态变量为 $\{\xi_1(n+1),\xi_2(n+1),\cdots,\xi_i(n+1),\cdots,\xi_N(n+1),\xi_h(n+1)\}$ .
由于 $t_{n+1}$ 时刻的系统状态变量仅与 $t_n^*$ 时刻的系统状态有关,同时 $t_n^*$ 时刻的系统状态变量仅与tn时刻的系统状态 有关,具有无后效性质,且轮询系统内的站点数量是相对确定,因此服务开始时刻系统的状态是可数的,由离散时间可数状态变量即构成嵌入式Markov链.在系统稳定条件( $\sum_{i=1}^N\rho_{i}+\rho_{h}<1 $ )下,该Markov过程是齐次、非周期、不可约和各态历经的,并且有唯一的稳态分布[17].
为建立系统数学模型,定义如下变量:
: i号普通站点的服务时间;
: 在期间到达站点 $j(j=1,2,\cdots,N,h)$ 的顾客数;
$S_{h,l}$ : 服务中心站点中第l个信息分组的服务时间;
$V_{h,m}$ : 服务器按照完全服务策略,清空第m时隙到达中心站点的所有信息分组所耗费的时间,包括服务期间新到达分组.
模型建立时,假设系统满足以下工作条件:
1) 各站点中信息分组按照独立同分布的Poisson过程到达,普通站点概率分布的母函数、 均值和二阶特性分别为 $A_i(z_i)$ , $\lambda_i=A'_i(1)$ 和 $\sigma_{\lambda i}^2=A''_i(1)+\lambda_i-\lambda_i^2$ ;中心队列概率分布的母函数、均值和方差分别为 $A_h(z_h)$ , $\lambda_h=A'_h(1)$ 和 $\sigma_{\lambda h}^2=A''_h(1)+\lambda_h-\lambda_h^2$ ;
2) 服务器服务各站点中一个信息分组的时间服从于一个相互独立、同分布的概率分布,普通站点概率分布的母函数、均值和方差分别为 $B_i(z_i)$ , $\beta_i=B_i'(1)$ 和 $\sigma_{\beta i}^2=B_i''(1)+\beta_i-\beta_i^2$ ;中心站点概率分布的母函数、均值和方差分别为 $B_h(z_h)$ , $\beta_h=B_h'(1)$ 和 $\sigma_{\beta h}^2=B_h''(1)+\beta_h-\beta_h^2$ ;
3) 服务器对在任一时隙期内进入中心站点的信息分组进行完全服务所需时间的随机变量都服从于一个相互独立、同分布的概率分布,其分布的概率母函数为 $F(z_h)$ ;
4) 各站点缓冲区足够大无信息溢出;
5) 服务器按先到先服务的原则服务;
6) 两级优先控制轮询系统工作在离散时间状态,时间轴按单位时隙划分.
1.3 概率母函数
根据第1.1节中描述的工作原理,系统在各时刻的状态变量存在以下关系:
当服务器在 $t_{n+1}$ 时刻轮询 $i+1$ 普通队列时,有:
$\begin{align} \xi_j(n+1)= \left\{ \begin{array}{ll} \xi_j(n^*)+\eta_j( u_h), & j eq h \\ 0, & j=h \\ \end{array} \right.\end{align}$
(1) 当服务器在 $t_n^*$ 时刻轮询中心队列时,有:
$ \xi_j(n^*)= \left\{ \begin{array}{ll} \xi_j(n)+\eta_j( u_i),& j eq i \\ \xi_i(n)+\eta_i( u_i)-1,& j=i \\ \end{array},\ \xi_i(n) eq 0 \right.$
(2) $\xi_j(n^*)= \left\{ \begin{array}{ll} \xi_j(n),& j eq i \\ 0,& j=i \\ \end{array},\ \xi_i(n)= 0\right.$
(3) 轮询系统的状态变化可以用马尔科夫链来描述,在系统稳定条件下,该马尔科夫过程是齐次、不可约、非周期的,并且有唯一的稳态分布.定义稳态下的概率母函数:
$\begin{align}\ \lim_{n\rightarrow\infty}P[\xi_j(n)=x_j;j=1,2,\cdots,N,h]=\\\pi_i(x_1,x_2,\cdots,x_i,\cdots,x_N,x_h)\end{align}$
(4) $\begin{align} & {{G}_{i}}({{z}_{1}},{{z}_{2}},\cdots ,{{z}_{i}},\cdots ,{{z}_{N}},{{z}_{h}})=~ \\ & ~\sum\limits_{{{x}_{1}}=0}^{\infty }{\cdots }\sum\limits_{{{x}_{N=0}}}^{\infty }{\sum\limits_{{{x}_{h}}=0}^{\infty }{z_{1}^{{{x}_{1}}}\cdots z_{N}^{{{x}_{N}}}z_{h}^{{{x}_{h}}}{{\pi }_{i}}({{x}_{1}},{{x}_{2}},\cdots ,}} \\ & {{x}_{i}},\cdots ,{{x}_{N}},{{x}_{h}}),i=1,\cdots ,N \\ \end{align}$
(5) 根据母函数定义,在 $t_{n+1}$ 轮询服务i+1号站点时系统状态变量的概率母函数为:
$\begin{align}G_{i+1}(z_1,z_2,\cdots,& z_N,z_h)=\\&\lim_{n\rightarrow\infty}{\rm E}\Bigg(\prod_{j=1}^Nz_j^{\xi_i^{(n+1)}}z_h^{\xi_h^{(n+1)}}\Bigg)\end{align}$
(6) 将式(1)~(3)代入计算得出:
$\begin{align}G_{i+1}&(z_1,z_2,\cdots,z_N,z_h) =G_{ih}\Bigg(z_1,z_2,\cdots,\\& z_N,B_h\Bigg(\prod_{j=1}^NA_j(z_j)F_h\Bigg(\prod_{j=1}^NA_j(z_j)\Bigg)\Bigg)\Bigg)\end{align}$
(7) 服务器在 $t_n^*$ 轮询服务中心站点时,系统状态变量的概率母函数为:
$\begin{align}G_{ih}(z_1,z_2,\cdots,& z_N,z_h)=\\&\lim_{n\rightarrow\infty}{\rm E}\Bigg(\prod_{j=1}^Nz_j^{\xi_i^{(n^*)}}z_h^{\xi_h^{(n^*)}}\Bigg)\end{align}$
(8) 将式(1)~(3)代入计算得出:
$\begin{align}G_{ih}&(z_1,z_2,\cdots,z_N,z_h)=\\&\frac{1}{z_i}B_i\Bigg(\prod_{j=1}^NA_j(z_j)A_h(z_h)\Bigg)[G_i(z)-G_i(z)|_{z_i=0}]+\\&\Bigg[G_i(z)|_{z_i=0}-G_i(z)|_{z_i,\cdots,z_N,z_h=0} +\\&\prod_{j=1}^NA_j(z_j)A_h(z_h)G_i(z)|_{z_i,\cdots,z_N,z_h=0}\Bigg]\end{align}$
(9) 其中, $A_i(z_i)$ , $ B_i(z_i)$ , $F_h(z_h)$ 含义如第1.2节所述, ${z}$ 为 $N+1$ 维向量( $z_1,\cdots,z_N,z_h$ ), $G_i({z})|_{z_i=0}$ 代表了当服务器当前查询站点缓冲区为空时的系统状态; $G_i({z})|_{z_i,\cdots,z_N,z_h=0}$ 表示系统中所有站点缓冲区均为空时的系统状态.
2. 模型分析
2.1 一阶特性分析
定义在tn时刻开始服务i号站点时,j号站点缓冲区中信息分组的平均数量为 $g_i(j)$ ,在 $t_n^*$ 时刻开始服务h站点时,j号站点缓冲区中信息分组的平均数量为 $g_{ih}(j)$ ,可以由系统变量概率母函数一阶偏导求取:
${{g}_{i}}(j)=\underset{{{z}_{1}},\cdots ,{{z}_{i}},\cdots ,{{z}_{N}},{{z}_{h}}\to 1}{\mathop{\lim }} \frac{\partial {{G}_{i}}(z)}{\partial {{z}_{j}}}$
(10) ${{g}_{i0}}(j)=\underset{{{z}_{1}},\cdots ,{{z}_{i-1}},{{z}_{i+1}}\cdots ,{{z}_{N}},{{z}_{h}}\to 1}{\mathop{\lim }} \frac{\partial {{G}_{i}}(z){{|}_{{{z}_{i}}=0}}}{\partial {{z}_{j}}}$
(11) ${{g}_{i00}}(j)=\underset{{{z}_{1}},\cdots ,{{z}_{N}},{{z}_{h}}\to 0}{\mathop{\lim }} \frac{\partial {{G}_{i}}(z){{|}_{{{z}_{1}},\cdots ,{{z}_{N}},{{z}_{h}}=0}}}{\partial {{z}_{j}}}$
(12) ${{g}_{ih}}(j)=\underset{{{z}_{1}},\cdots ,{{z}_{i}},\cdots ,{{z}_{N}},{{z}_{h}}\to 1}{\mathop{\lim }} \frac{\partial {{G}_{ih}}(z)}{\partial {{z}_{j}}}$
(13) 其中, $i=1,2,\cdots,N,j=1,2,\cdots,N,h$ .
将 $\lim_{z_1,\cdots,z_N,z_h\rightarrow 1}G_{i}({z})|_{z_i=0}$ 记为 $G_{i0}$ , $\lim_{z_1,\cdots,z_N,z_h\rightarrow 1}G_i({z})|_{z_1,\cdots,z_N,z_h=0}$ 记为 $G_{i00}$ ,将概率母函数表达式(7)和式(9)代入,求一阶偏导可得:
${c}g_{ih}(j)=\rho(1-G_{i0})+g_i(j)+\lambda_jG_{i00}$
(14) $g_{ih}(i)=(\rho-1)(1-G_{i0})+g_i(i)+\lambda_iG_{i00}$
(15) $g_{ih}(h)=\lambda_h\beta_i(1-G_{i0})+\lambda_hG_{i00}$
(16) $g_{i+1}(i)=g_{ih}(i)+g_{ih}(h)\lambda_i\beta_h(1+F_h'(1))$
(17) $g_{i+1}(j)=g_{ih}(j)+g_{ih}(h)\lambda_j\beta_h(1+F_h'(1))$
(18) 将式(14)~(16)代入式(17)和式(18)计算 $\Sigma_{j=1}^Ng_{j+1}(k)$ 得出系统一阶特性存在如下关系:
$\begin{align}1-G_{i0}=\frac{N\lambda}{1-\rho_h-N\rho}G_{i00}\end{align}$
(19) 定义平均查询周期 $\overline{\theta}$ 表示服务器按照轮询表完成一轮服务所耗费的平均时间,根据系统模型得出平均查询周期如下:
$\begin{align}\overline{\theta}=\frac{1-G_{i0}}{\lambda}=\frac{N}{1-\rho_h-N\rho}G_{i00}\end{align}$
(20) 2.2 二阶特性分析
定义系统状态概率母函数二阶偏导为:
$g_i(j,k)=\lim_{z_1,\cdots,z_N,z_h\rightarrow1}\frac{\partial^2 G_i(z)}{\partial z_j\partial z_k}$
(21) $g_{ih}(j,k)=\lim_{z_1,\cdots,z_N,z_h\rightarrow1}\frac{\partial^2 G_{ih}(z)}{\partial z_j\partial z_k}$
(22) $g_{i0}(j,k)=\lim_{z_1,\cdots,z_{i-1},z_{i+1}\cdots,z_N,z_h\rightarrow 1}\frac{\partial^2 G_i(z)|_{z_i=0}}{\partial z_j\partial z_k}$
(23) ${{g}_{i00}}(j,k)=\underset{{{z}_{1}},\cdots ,{{z}_{N}},{{z}_{h}}\to 0}{\mathop{\lim }} \frac{{{\partial }^{2}}{{G}_{i}}(z){{|}_{{{z}_{1}},\cdots ,{{z}_{N}},{{z}_{h}}=0}}}{\partial {{z}_{j}}\partial {{z}_{k}}}$
(24) 其中, $i=1,2,\cdots,N,j,k=1,2,\cdots,N,h$ .
将概率母函数表达式(7)和式(9)代入计算二阶偏导可得系统二阶特性参数方程组,化简后,得到信息分组排队队长概率分布二阶特征量 $g_i(i)$ 和 $g_{ih}(h,h)$ 的解析式如下:
$\begin{align} & g_i(i)=\frac{C}{2}\Big\{\frac{1}{(1-\rho_h-N\rho)(1-\rho_h)}\times \\ & ~~~~~~~~~~~~\Big[\rho_h\frac{A''(1)}{\lambda}(1-\rho_h^2+A_h''\beta_h^2+\lambda_hB_h'')+\\ & ~~~~~~~~~~~~NB''(1)\lambda^2+N\beta A''(1)\Big]+\frac{\lambda}{1-\rho_h}+ \\ & ~~~~~~~~~~~~\frac{\lambda_h\lambda B_h''(1)}{1-\rho_h-N\rho}\Big\}+C \end{align}$
(25) $\begin{align}g_{ih}(h,h)=B''(1)\lambda_h^2(1-G_{i0})+\beta A_h''(1)+\\ & ~~~~~~~~~~~~~~~~~~~~\beta A_h''(1)G_{i00}\end{align}$
(26) 其中, $C=1-G_i({z})|_{z_i=0}$ . $g_i(i)$ 表示普通站点接受查询时刻缓冲区中信息分组的平均排队队长.
2.3 吞吐量
系统吞吐量G是指单位时间内完全服务系统所能传输的信息分组数:
$\begin{align}G=N\rho+\rho_h=N\lambda\beta+\lambda_h\beta_h\end{align}$
(27) 2.4 平均等待时延
定义信息分组平均等待时延E $(W_j),j=1,2,\cdots,N,h$ ,为从该信息分组到达站点j到服务器开始对其服务的平均间隔时间.普通站 $i,i=1,\cdots,N$ 采用限定( $k=1$ )服务,根据服务规则普通站点平均等待时间[18]:
$\begin{align}{\rm E}\left(W_i\right)=\frac{1}{\lambda C}g_i(i)-\frac{1}{\lambda}-\frac{A''(1)}{2\lambda^2}\end{align}$
(28) 将式(25)代入得出普通站点平均等待时延闭式解析式:
$\begin{align}&{\rm E}(W_i)=\frac{1}{2\lambda}\Bigg\{\frac{1}{(1-\rho_h-N\rho)(1-\rho_h)}\Bigg[\rho_h\frac{A''(1)}{\lambda}\times \\&(1-\rho_h^2+A_h''\beta_h^2+\lambda_hB_h''(1))+NB''(1)\lambda^2+\\&N\beta A''(1)\Bigg]+\frac{\lambda}{1-\rho_h}+\frac{\lambda_h\lambda B_h''(1)}{1-\rho_h-N\rho}\Bigg\}-\frac{A''(1)}{2\lambda^2}\end{align}$
(29) 中心站点h采用完全服务,根据服务规则中心站点平均等待时间[19]:
$\begin{align}{\rm E}\left(W_h\right)=\frac{g_{ih}(h,h)}{2\lambda_hg_{ih}(h)}-\frac{A_h''(1)}{2\lambda_h^2(1+\rho_h)}+\frac{\lambda_hB_h''(1)}{2(1-\rho_h)}\end{align}$
(30) 将式(16)和(26)代入得出中心站点平均等待时延闭式解析式:
$\begin{align}{\rm E}\left(W_h\right)=&\frac{1}{2(1-\rho_h)}(1-\rho_h+N\lambda B''(1)+\\&\lambda_hB_h''(1))-\frac{A_h''(1)}{2\lambda_h^2(1+\rho_h)}\end{align}$
(31) 3. 数值分析
根据以上所建立的依托站点状态两级轮询(SDTLP)系统模型,在系统稳定条件下进行数值计算和仿真实验,SDTLP系统性能指标理论值由式(26)和式(31)计算得出.
仿真实验在Matlab 2012b平台上完成,通过函数生成 $\lambda_i$ 为均值的泊松分布随机序列,模拟各站点中单位时间内信息分组的到达数量. 仿真步骤如下:
Initialization: arrive rate $\lambda$ and $\lambda_h$ ,serve time $\beta$ and $\beta_h$ ,the number of normal station N,and the current time: t. Generate the information packets sequenceaccording to the arrive rate.
for $i=1: N$
update the number of packets in station i
if (station i is active)
serve one packet in station i
update t
while (the buffer of station h is not empty)
serve one packet in station h
update t
end
$i=i+1$
else
$i=i+1$
end
end
仿真模拟的通信过程处于理想状态,即所有信息分组成功发送,丢包率和重传率为零,归一化后时间轴按时隙划分,信息分组到达率以分组/时隙为单位、服务率以时隙为单位.图 2至图 3得出理论计算与仿真实验的结果一致.
图 2 平均等待时延与系统参数的关系Fig. 2 Relationship between the mean waiting time and thesystem parameters图 2(a)和图 2(b)分别描述了系统平均等待时延与站点信息分组到达率和站点服务时间的关系,如图所示,当系统负载随站点的信息分组到达率或站点服务时间增加时,普通站点和中心站点的平均等待时延得到了很好的区分,中心站点在负载明显大于普通站点时仍能 保持较小的等待时延.
图 3描述了系统吞吐量与站点信息分组达到率之间的关系,如图所示,当系统吞吐量随站点信息分组到达率的加大呈线性增加趋势. 另一方面,如图 2所示,到达率的加大同时造成平均等待时延的增加,因此,在考虑如何提高系统吞吐量时还应以时延性能作为约束.
SDTLP控制方式的核心为通过每轮服务开始前更新轮询表,提供区分站点状态的查询服务以提高服务效率.与已有顺序查询的两级轮询控制策略比较,我们得出如下分析结果:
1) 图 4(a)和图 4(b)分别展示了在相同参数环境下,并行调度两级轮询控制系统[11]和本文所述系统(SDTLP)的比较.如图所示,SDTLP系统中心站点和普通站点的平均等待时延均低于并行调度两级轮询系统.
2) 轮询控制方式下系统吞吐量和站点平均等待时延均随着系统负载增加而提高,因此在提高系统吞吐量的同时还应考虑控制平均等待时延.图 4(c)为当普通站点到达率增加时系统普通站点平均等待时延与吞吐量关系的比较,如图所示,在相同的平均等待时间下,SDTLP可实现更高的吞吐量.
3) 文献[10]为保证公平性,对中心站点和普通站点分别采用门限服务和完全服务,简记为门限--完全系统;而本文从充分保证中心站点服务优先权的角度设置中心站点为完全服务,普通站点为限定 $k = 1$ 服务,通过仅对活动站点提供查询来保证系统整体服务效率.图 5所示为门限--完全系统和SDTLP系统的比较,根据文献[10]中分析结果,在此选取站点平均排队队长为比较指标.如图 5所示,SDTLP系统的中心站点和普通站点平均排队队长均小于完全--门限控制系统.这是因为尽管SDTLP中服务每次查询普通站点仅允许其发送1个信息分组,但由于服务器不再查询空闲站点使得忙站点能够以较小的循环周期得到更高频率的访问,两类站点服务效率均得以提升.
图 5 吞与门限--完全系统平均排队队长比较( $\lambda_h=0.1,\lambda=0.05,\beta_h=\beta=1,\gamma=1$ )Fig. 5 Comparison of mean queue length with gated-exhaustivemodels4. 结论
轮询系统的应用在满足避免数据冲突的同时,还应该同时考虑系统的灵活性和利用率,使得系统具有更好的效率与合理性,从而满足实际应用的需求.
本文提出了依据用户妥善安排的两级轮询控制系统模型.通过区分站点状态,仅轮询有发送需求的站点,根据站点需求调整轮询路径、减少查询损耗、提高系统利用率、降低时延.采用嵌入式马尔科夫链和概率母函数的方法建立了系统模型,精确解析了系统平均等待时延性能指标.
需要指出的是,为了得出系统平均等待时延的精确解析表达式,本文假设普通站点具有对称性,在后续的工作中将针对非对称系统以及不同服务方式下的控制模型作进一步的研究.
-
图 2 平均等待时延与系统参数的关系
Fig. 2 Relationship between the mean waiting time and thesystem parameters
-
[1] Boon M A A, van der Mei R D, Winands E M M. Applications of polling systems. Surveys in Operations Research and Management Science, 2011, 16(2):67-82 doi: 10.1016/j.sorms.2011.01.001 [2] 赵继军, 谷志群, 薛亮, 李志华, 关新平. WSN中层次型拓扑控制与网络资源配置联合设计方法. 自动化学报, 2015, 41(3):646-660 http://www.aas.net.cn/CN/abstract/abstract18641.shtmlZhao Ji-Jun, Gu Zhi-Qun, Xue Liang, Li Zhi-Hua, Guan Xin-Ping. A joint design method of hierarchical topology control and network resource allocation for wireless sensor networks. Acta Automatica Sinica, 2015, 41(3):646-660 http://www.aas.net.cn/CN/abstract/abstract18641.shtml [3] Panagiotakis A, Nicopolitidis P, Papadimitriou G I, Sarigiannidis P G. Performance increase for highly-loaded RoF access networks. IEEE Communications Letters, 2015, 19(9):1628-1631 doi: 10.1109/LCOMM.2015.2456911 [4] Zhao W B, Tang X Y. Scheduling sensor data collection with dynamic traffic patterns. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(4):789-802 doi: 10.1109/TPDS.2012.163 [5] Rasul A, Erlebach T. Reducing idle listening during data collection in wireless sensor networks. In:Proceedings of the 10th International Conference on Mobile Ad-hoc and Sensor Network. Maui, USA:IEEE, 2014.16-23 https://www.computer.org/csdl/proceedings/msn/2014/7394/00/index.html [6] Guan Z, Zhao D F, Zhao Y F. A discrete time two-level mixed service parallel polling model. Journal of Electronics (China), 2012, 29(1-2):103-110 doi: 10.1007/s11767-012-0781-3 [7] Boon M A A, Adan I J B F, Boxma O J. A two-queue polling model with two priority levels in the first queue. Discrete Event Dynamic Systems, 2010, 20(4):511-536 doi: 10.1007/s10626-009-0072-9 [8] Boon M A A, Adan I J B F, Boxma O J. A polling model with multiple priority levels. Performance Evaluation, 2010, 67(6):468-484 doi: 10.1016/j.peva.2010.01.002 [9] 刘强, 张中兆, 张乃通. 排队优先权站点轮询系统的平均周期时间. 通信学报, 1999, 20(2):86-91 http://www.cnki.com.cn/Article/CJFDTOTAL-TXXB902.014.htmLiu Qiang, Zhang Zhong-Zhao, Zhang Nai-Tong. Mean cyclic time of queueing priority station polling system. Journal of China Institute of Communications, 1999, 20(2):86-91 http://www.cnki.com.cn/Article/CJFDTOTAL-TXXB902.014.htm [10] 杨志军, 丁洪伟, 陈传龙. 完全服务和门限服务两级轮询系统E(x)特性分析. 电子学报, 2014, 42(4):774-778 http://www.cnki.com.cn/Article/CJFDTotal-DZXU201404023.htmYang Zhi-Jun, Ding Hong-Wei, Chen Chuan-Long. Research on E(x) characteristics of two-class polling system of exhaustive-gated service. Acta Electronica Sinica, 2014, 42(4):774-778 http://www.cnki.com.cn/Article/CJFDTotal-DZXU201404023.htm [11] Liu Q L, Zhao D F, Zhou D M. An analytic model for enhancing IEEE 802.11 point coordination function media access control protocol. European Transactions on Telecommunications, 2011, 22(6):332-338 doi: 10.1002/ett.v22.6 [12] 何敏, 赵东风, 刘心松. 移动Ad hoc网络分布式并行接入控制协议分析. 系统工程与电子技术, 2007, 29(3):443-448 http://www.cnki.com.cn/Article/CJFDTOTAL-XTYD200703031.htmHe Min, Zhao Dong-Feng, Liu Xin-Song. Analysis of a distributed parallel access control protocol for mobile ad hoc networks. Systems Engineering and Electronics, 2007, 29(3):443-448 http://www.cnki.com.cn/Article/CJFDTOTAL-XTYD200703031.htm [13] Dorsman J P L, Boxma O J, van der Mei R D. On two-queue Markovian polling systems with exhaustive service. Queueing Systems, 2014, 78(4):287-311 doi: 10.1007/s11134-014-9413-y [14] Dorsman J P, Borst S C, Boxma O J, Vlasiou M. Markovian polling systems with an application to wireless random-access networks. Performance Evaluation, 2015, 85-86:33-51 doi: 10.1016/j.peva.2015.01.008 [15] 余淼, 胡占义. 高阶马尔科夫随机场及其在场景理解中的应用. 自动化学报, 2015, 41(7):1213-1234 http://www.aas.net.cn/CN/abstract/abstract18696.shtmlYu Miao, Hu Zhan-Yi. Higher-order Markov random fields and their applications in scene understanding. Acta Automatica Sinica, 2015, 41(7):1213-1234 http://www.aas.net.cn/CN/abstract/abstract18696.shtml [16] 李庆奎, 李梅, 贾新春. 具有Markov跳变参数的闭环供应链系统切换控制. 自动化学报, 2015, 41(12):2081-2091 http://www.aas.net.cn/CN/abstract/abstract18781.shtmlLi Qing-Kui, Li Mei, Jia Xin-Chun. Switching control of closed-loop supply chain systems with Markovian jumping parameters. Acta Automatica Sinica, 2015, 41(12):2081-2091 http://www.aas.net.cn/CN/abstract/abstract18781.shtml [17] Kim J, Kim B. Stability of a cyclic polling system with an adaptive mechanism. Journal of Industrial and Management Optimization, 2015, 11(3):763-777 http://cn.bing.com/academic/profile?id=2315384942&encoded=0&v=paper_preview&mkt=zh-cn [18] 赵东风, 李必海, 郑苏民. 周期查询式限定服务排队系统研究. 电子科学学刊, 1997, 19(1):44-49 http://www.cnki.com.cn/Article/CJFDTOTAL-DZYX199701007.htmZhao Dong-Feng, Li Bi-Hai, Zheng Su-Min. Study of polling systems with limited service. Journal of Electronics, 1997, 19(1):44-49 http://www.cnki.com.cn/Article/CJFDTOTAL-DZYX199701007.htm [19] 赵东风, 郑苏民. 查询式完全服务排队模型分析. 电子学报, 1994, 22(5):102-107 http://www.cnki.com.cn/Article/CJFDTOTAL-DZXU405.018.htmZhao Dong-Feng, Zheng Su-Min. Analysis of a polling model with exhaustive service. Acta Electronica Sinica, 1994, 22(5):102-107 http://www.cnki.com.cn/Article/CJFDTOTAL-DZXU405.018.htm -
下载:
下载:
计量
- 文章访问数: 1544
- HTML全文浏览量: 207
- PDF下载量: 656
- 被引次数: 0
