连续时间完全服务与门限服务两级轮询系统性能研究

杨志军 刘征 丁洪伟

摘 要：在信息分组以连续时间规律到达系统的基础上，对于轮询系统中不同优先级的业务问题，提出区分优先级的两级轮询服务模型。首先，在该模型中，低优先级站点采用门限服务，高优先级站点采用完全服务;然后，在高优先级转低优先级时，将传输服务与转移查询并行处理来降低服务器在查询转换期间所耗费的时间，提高轮询系统的效率;最后，运用马尔可夫链和概率母函数的方法建立了系统的数学模型，通过对数学模型精确解析，得到了连续时间两级服务系统每个站点的平均排队队长和平均等待时间的表达式，精确解析出平均排队队长和平均等待时间的值。仿真实验结果表明：理论计算值与实验仿真值近似相等，说明理论分析正确合理。该模型既能保障低优先级站点服务质量，又能为高优先级站点提供优质服务。

关键词：轮询系统;优先级;平均排队队长;平均等待时间;概率母函数

Abstract： For the fact that information groups arrive at the system in a continuous time， a two-level polling service model with different priorities was proposed for the business problems of different priorities in the polling system. Firstly， gated service was used in sites with low priority， and exhaustive service was used in sites with high priority. Then， when high priority turned into low priority， the transmission service and the transfer query were processed in parallel to reduce the time cost of server during query conversion， improving the efficiency of polling system. Finally， the mathematical model of system was established by using Markov chain and probabilistic parent function. By accurately analyzing the mathematical model， the expressions of average queue length and average waiting time of each station of continuous-time two-level service system were obtained. The simulation results show that the theoretical calculation value was approximately equal to the experimental simulation value， indicating that the theoretical analysis is correct and reasonable. The model provides high-quality services for high-priority sites while maintaining the quality of services in low-priority sites.

Key words： polling system; priority; average queue length; average waiting time; probabilistic parent function

0 引言

轮询是一种资源调度控制的方法，通过这种方法可以实现资源的有效分配并实现资源共享[1-2]。根据到达系统的信息分组以离散时间或连续时间规律到达将轮询服务系统分为离散时间轮询系统和连续时间轮询系统。按服务策略可以分为门限、完全和限定三种轮询服务系统[3-4]，而随着不断的研究，在三种服务策略的基础上区分优先级的混合服务策略成为了人们研究的重点。在近几年的研究中，提出了各种各样的区分优先级的混合服务策略。在这些策略中，轮询系统既保证了队列优先级的需求，又避免空闲查询时空闲造成的时间延迟，达到了提高系统利用率、减少时延的效果[5]。通过对区分优先级的混合服务策略系统平均排队队长、循环周期和平均等待时间等特性的研究，验证了区分优先级带来的性能提升。由于区分优先级对系统性能上的提升，该类轮询服务系统可以被广泛应用于各行各业中。在通信网络中，可以用于蓝牙技术和IEEE 802.11无线局域网的研究或是在Web服务器的路由器和I/O子系统中的调度策略[5-6];在订单分拣中，优先级轮询控制系统具有良好的稳定性和高效率，确保了优先订单顾客得到更优质的服务以及每一个顾客享有的同等的公平性[7-8];在军事领域中，可以更好地实现整个作战范围内的战场资源共享，最终实现战场指挥、通信、控制、情报、信息以及综合保障等功能的一体化[9-10]。

轮询系统的三个基础模型适用于不同的环境。完全服务是一种简单、可靠、有效的服务策略，采用这种服务策略的系统平均排队队长和平均等待时延最短，非常适合于数据信息量少且高优先级的站点;限定服务的服务规则是一个站点接受服务时，站点内有且只有一个信息分组被服务，所以，当到达普通站点的信息分组数较大时，采用限定服务的轮询系统平均排队队长和信息分组平均等待时间会过长。当信息分组到达数较小时，就可以考虑采用限定服务。本文设定普通站点信息分组到达数较大时，采用门限服务，所以，本文针对连续时间的轮询服务系统，提出区分优先级的完全门限服务策略的两级控制轮询系统模型[11-13]。在该模型中，普通站点（N个）采取门限服务，中心站点（1个）采取完全服务，服务完一个普通站点就开始服务中心站点，当中心站点服务完时，又开始服务下一个普通站点。针对上述过程，本文首先通过马尔可夫链和概率母函數建立其数学模型，再推出其一阶特性量平均排队队长和循环查询周期的精确表达式;然后对模型的二阶特性量进行了分析，在此基础上对平均等待时间进行了解析;最后，通过Matlab仿真对理论结果进行了验证。

1 系统模型

连续时间两级优先级轮询控制系统由一个服务器和N+1个站点组成。因为实际生活中，服务系统中往往会出现一个服务质量要求较高的中心任务或核心任务，其他多个普通业务服务要求质量较低，普通业务之间需要公平对待地实际需求，所以，本文中N个站点为普通站点采取门限服务策略，1个站点为中心站点采取完全服务策略。在服务过程中，服务器优先对高优先级的中心站点服务，当中心站点的所有数据信息量发送完时，服务器开始对i（i=1，2，…，N）站点普通站点服务，在该模型中，中心站点转普通站点采用并行服务模式，所以当服务器从中心站点转向普通站点时，就不需要一个查询转换时间，直接对普通站点进行服务。当普通站点i完成服务时，服务器经历一个查询转换时间再一次转向中心站点对其服务，服务完成后，对i+1号普通站点服务，该模型查询顺序如图1所示。

设定在tn时刻，服务器开始对普通站点i（i=1，2，…，N）进行服务，定义随机变量ξi（n）是第i个站点中等待发送的数据信息量，h表示中心站点，定义h上的数据信息量为ξh（n），所以，在tn时刻，整个系统状态随机变量为{ξ1（n），ξ2（n），…，ξN（n），ξh（n）};设定tn*时刻，服务器从站点i转向中心站点h服务，定义系统状态随机变量为{ξ1（n*），ξ2（n*），…，ξN（n*），ξh（n*）};设tn+1时刻，普通站点i+1开始接受服务，定义系统状态变量为{ξ1（n+1），ξ2（n+1），…，ξN（n+1），ξh（n+1）}。

系统的状态可以用马尔可夫链来描述，该马尔可夫链是非周期的和各态历经的。

1.1 系统工作条件

根据轮询系统基本模型所示，同时结合其控制机制和特点，对系统工作条件作如下设定：

1）进入各个站点内等待发送的数据信息量的到达过程是相互独立的Poisson分布，到达率是λ;

2）任何一个站点发送信息分组的时间变量服从于相互独立的、同分布的概率分布，其变量的拉普拉斯变换（Laplace Transform， LST缩写词中的S，对应英文全称中的哪个单词？英文全称正确吗？请明确。回复：正确，其英文全称及缩写是参考大学已学的《信号与系统》这本书以及多篇毕业论文写的，按照我的理解是LST的意思是拉普拉斯S变换，因为在拉普拉斯变换中是将时域t转换为S域，即将t转换为s。）为（s），均值为β=-′（0），二阶原点距为υβ=″（0）;

3）任何两个相邻站点之间的查询转换时间变量服从于相互独立的、同分布的概率分布，其变量的拉普拉斯变换为（s），均值为γ=-′（0），二阶原点距为υγ=″（0）;

4）中心站点对在任一时隙内到达的数据信息量进行完全服务所需时间的随机变量服从于一个相互独立、同分布的概率分布，其分布的概率母函数为H（z）;

5）设定服务系统中任何一个队列的缓存容量足够大，不存在数据信息量丢失的情况发生;

6）每一个加入进队列的数据信息量，将会按照先到先服务（First Come First Served， FCFS）的方法接受服务。

定义随机变量如下：

ui（n）表示服务器从普通站点i查询转换到中心站点h所耗费的时间;vi（n）表示普通站点i向服务器发送数据信息量所耗费的时间;vh（n*）表示中心站点h向服务器发送数据信息量所耗费的时间; μj（ui）表示在ui（n）时间内进入第j（j=1，2，…，N，h）个站点的数据信息量;ηj（vi）表示在vi（n）时间内进入第j（j=1，2，…，N，h）个站点的数据信息量;ηj（vh）表示在vh（n*）时间内进入第j（j=1，2，…，N，h）个站点的数据信息量。

1.2 概率母函数

为构建该模型系统的数学模型，本文引入了概率母函数。上述马尔可夫链在∑Ni=1λi βi+λh βh=∑Ni=1ρi+ρh<1的条件下达到平稳状态[14]，在平稳状态下的概率母函数为：

对连续时间型系统进行分析时，需要对系统关键参数进行拉普拉斯变换。函数的拉普拉斯变换定义为：

对于以参数λ到达的泊松过程，时间t内到达的顾客数对应的概率母函数为：

在tn*时刻，服务器开始对中心站点h服务时，系统状态变量的概率母函数为：

在tn+1时刻，服务器开始对i+1号普通站点服务时，系统状态变量的概率母函数为：

2 轮询系统的一阶和二阶特性

2.1 平均排队队长

定义在tn时刻第i号站点开始传输服务时，第j号站点中平均存储的数据息量为i（j），则：

根据式（4）～（6）得到i号普通站点的平均排队队长的表达式为：

同理可得，中心站点h的平均排队队长的表达式为：

ih（h）表示服务器在服务完普通站点i，转到中心站点h后，这段时间内进入中心站点h的所有数据信息量的平均排队队长。

2.2 循环查询周期

轮询系统的循环周期为该系统内所有队列根据服务规则进行一次服务所花费时间的统计平均值，即服务器相邻两次开始服务同一队列的时间差，所以，连续两级轮询系统的循环周期为：

2.4 平均等待时间

数据信息量的等待时间是指一个数据信息量从进入一个站点到其被服务器服务的等待时间，系统的平均等待时间是指进入一个站点的所有数据信息量等待的平均时间。本文中E（WGi）和E（WGh）分别代表普通站点与中心站点的平均等待时间，根据参考文献[15-16]可得其平均等待时间为：

3 仿真实验及性能分析

3.1 實验仿真

本文实验通过Matlab仿真上述建立的连续两级轮询系统服务模型。在模型仿真过程中，需要满足以下条件[14，17]：

1）各站点的参数变量都应当服从相同的分布，普通站点之间的到达率相同但与中心站点的到达率不同;

2）任一时隙内进入各站点的数据信息量都满足泊松分布;

3）轮询系统满足∑Ni=1λi βi+λh βh=∑Ni=1ρi+ρh=Nρ+ρh<1稳态条件。

在仿真实验中，算法的复杂度为常数，算法时间效率高，所以，为了确保实验值的准确性，每次仿真实验的系统循环次数为30万。

在仿真实验中，首先验证了理论值的准确性，分别对8个、10个普通站点的系统模型进行了仿真，仿真结果与理论值的对比结果在表1中;其次通过改变系统中的总负载，观察分析了平均排队队长和平均等待时间的变化规律，如图2～3所示;最后，通过实验仿真，分析了中心站点对普通站点的影响，如图4～5所示。

站点数站点到达率服务率转换率到达率、服务率、转换率的单位是否应该是百分数？即在后面加上“/%”？还是“服务率、转换率”的后面加上/%，因为到达率的单位已经是小数了。注：如服务率写为服务率/%，其下的数字2，即表示2%。而到达率后面加上/%，其中的数字0.0015，即表示0.0015%。请务必清晰表达。

回复：到达率、服务率、转换率均表示均值，到达率表示一个时隙内到达每个站点的平均信息分组数，服务率表示服务一个信息分组数的平均时间，转换率表示服务器从一个站点转向另一个站点所要的平均时间。所以，在这里率仅表示均值的意思无百分率的含义在里面。

回复：因为问题简单，我这里可以简单说明一下。这个问题是关于到达率、服务率和转换率的单位是否为百分数？其实，在这里这三个参数均表示各自代表的均值，其单位不能是百分数。至于这里的“率”是代表一种均值。比如到达率是指一个时隙内到达每个站点的平均信息分组数，其单位不含有百分数的意思。

3.2 性能分析

1）在表1中，本文通過设定普通站点数8、10，分别对这两种情况作了仿真实验，从表中数据可以看出，系统的平均排队队长和平均等待时间的实验值与理论值差距极小，验证了系统理论分析的正确性。

2）在图2～3中，本文通过改变系统总负载，得到了普通站点和中心站点的平均排队队长和平均等待时间的变化曲线。从图中曲线可以看出，两类站点的平均排队队长和平均等待时间在总负载低的条件下，变化平缓，随着总负载的增大，在总负载达到一定值后，总负载的极小变化也能对平均排队队长和平均等待时间造成很大的影响。

3）在图4～5中，本文通过一级门限服务系统和连续两级系统的对比，观察了中心站点对普通站点的影响。为了客观的分析，在该实验中，设定一级门限服务的站点到达率、服务时间和转换时间与两级连续系统的普通站点到达率、服务时间和转换时间相等，中心站点的到达率为普通站点的十分之一。由图可以看出，当中心站点的到达率远小于普通站点时，普通站点的平均排队队长和平均等待时间变化不大。

4）从表1、图2～5可以看出，中心站点的平均排队队长与平均等待时间都远远小于普通站点，这说明了系统优先级站点与低优先级站点的区分度还是比较高的，达到了高优先级站点快速、高效地接受服务，低优先级站点之间可以公平接受服务的目的。

4 结语

本文采取了一种连续时间完全服务与门限服务的轮询系统，即在低优先级的普通站点采取门限服务，在高优先级的中心站点采取完全服务。基于嵌入式马尔可夫链与概率母函数得到了系统的精确数学解析，通过实验仿真验证了理论分析的正确性。在理论分析正确的基础上，又通过实验仿真，分析了总负载对系统的影响以及中心站点对普通站点的影响。通过分析，本文得出在总负载低时，系统的平均排队队长和平均等待时间变化缓慢，在总负载到达一定值时，系统的性能将大幅下降，每个站点等候的数据信息量与每个数据信息量等候服务的时间都将大幅增加;而通过一级门限服务系统与该系统比较，可以看出在中心站点的到达率较低时，中心站点对普通站点的影响很小，这说明了该连续时间两级轮询控制系统的优越性，在基本不牺牲低优先级普通站点的性能条件下，为高优先级中心站点提供优质的服务。

参考文献 （References）

[1] WANG X M， DU L J， ZHANG Y， et al. Priority queue based polling mechanism on seismic equipment cluster monitoring[J]. Cluster Computing， 2017， 20（1）： 661-619.

[2] BOON M A A， VANDERMEI R D， WINANDS E M M. Applications of polling systems[J]. Surveys in Operations Research and Management Science， 2011， 16（2）： 67-82.

[3] BOXMA O J， KELLA O， KOSINSKI K M. Queue lengths and workloads in polling systems[J]. Operations Research Letters， 2011， 39（6）： 401-405.

[4] CHU Y Q， LIU Z M. The impact of priority policy in a two-queue Markovian polling system with multi-class priorities[C]// Proceedings of the 12th International Conference on Queueing Theory and Network Applications. Berlin： Springer， 2017： 282-296.

[5] 孙洋洋，杨志军.无线传感器网络轮询系统分析研究[J].电子测量技术，2018，41（15）：100-104.（SUN Y Y， YANG Z J. Analysis and research of wireless sensor network polling system[J]. Electronic Measurement Technology， 2018， 41（15）： 100-104.）

[6] 苏杨，杨志军，丁阳洋，等.无线传感器网络中轮询系统控制的实现[J].电子测量技术，2018，41（4）：66-70.（SU Y， YANG Z J， DING Y Y， et al. Implementation of polling system control in wireless sensor networks[J]. Electronic Measurement Technology， 2018， 41（4）： 66-70.）

[7] 冉文学，余丽艳.普洱茶配送中心订单分拣完全—并行门限二级轮询控制机理研究[J].物流工程与管理，2018，40（7）：77-81.（RAN W X， YU L Y. Study on complete-parallel threshold polling control mechanism about order-sorting of Puer tea distribution center[J]. Logistics Engineering and Management， 2018， 40（7）： 77-81.）

[8] 冉文学，刘会娟，余丽艳.连续物料订单分拣完全并行限定（k=1）轮询控制机理[J].中国管理科学，2018，26（8）：86-93.（RAN W X， LIU H J， YU L Y. Continuity material order sorting based on the polling control mechanism of exhaustive parallel limited-1[J]. Chinese Journal of Management Science， 2018， 26（8）： 86-93.）

[9] 刘龙军，丁洪伟，柳虔林，等.基于现场可编程门阵列战术数据链中优先级轮询接入控制协议的研究[J].兵工学报，2017，38（2）：305-312.（LIU L J， DING H W， LIU Q L， et al. Research on priority polling access control protocol in FPGA-based tactical data link[J]. Acta Armamentarii， 2017， 38（2）： 305-312.）

[10] 孔维东，王永斌，刘宏波.基于排队论模型的轮询协议数据链系统时延分析[J].火力与指挥控制，2017，42（3）：100-103.（KONG W D， WANG Y B， LIU H B. Research on time delay of polling protocol data link based on queuing theory model[J]. Fire Control and Command Control， 2017， 42（3）： 100-103.）

[11] 杨志军，苏杨，丁洪伟.完全服务和非对称门限服务两级轮询系统特性分析[J].自动化学报，2018，44（12）：2228-2237.（YANG Z J， SU Y， DING H W. Analysis of two-level polling system characteristics of exhaustive service and asymmetrically gated service[J]. Acta Automatica Sinica， 2018， 44（12）： 2228-2237.）

[12] 杨志军，孙洋洋.分忙闲站点的限定（K=2）轮询控制系统分析研究[J].计算机科学，2018，45（11）：70-74.（YANG Z J， SUN Y Y. Analysis and study on limited （K=2） polling control system with busy and idle sites[J]. Computer Science， 2018， 45（11）： 70-74.）

[13] YANG Z J， SUN Y Y， GAN J H. New polling scheme based on busy/idle queues mechanism[J]. International Journal of Performability Engineering， 2018， 14（10）： 2522-2531.

[14] KIM J， KIM B. Stability of a cyclic polling system with an adaptive mechanism[J]. Journal of Industrial and Management Optimization， 2015， 11（3）： 763-777.

[15] 官錚，杨志军，何敏，等.依托站点状态的两级轮询控制系统时延特性分析[J].自动化学报，2016，42（8）：1207-1214.（GUAN Z， YANG Z J， HE M， et al. Study on the delay performance of station dependent two-level polling systems[J]. Acta Automatica Sinica， 2016， 42（8）： 1207-1214.）

[16] 木文浩，保利勇，丁洪伟，等.离散时间闸门式多级门限服务的两级优先级轮询排队系统分析[J].电子学报，2018，46（2）：276-280.（MU W H， BAO L Y， DING H W， et al. An exact analysis of discrete time two-level priority polling system based on multi-times gated service policy[J]. Acta Electronica Sinica， 2018， 46（2）： 276-280.）

[17] SIDDIQUI S， GHANI S， KHAN A A. ADP-MAC： an adaptive and dynamic polling-based mac protocol for wireless sensor networks[J]. IEEE Sensors Journal， 2018， 18（2）： 860-874.