轮询系统的演进及发展

柳虔林，赵东风，丁洪伟，蔡 煜

(1.中国人民解放军77302部队，云南昆明650051;2.云南大学信息学院，云南 昆明650091)

0 引言

轮询是一类重要的理论研究模型，其研究起源可追溯到20世纪50年代后期，相关学者将设备检修以及交通信号控制等抽象为轮询模型，并采用概率论、排队论等数学理论加以分析和研究，使此项研究工作上升到理论化和系统化阶段［1-4］。轮询系统具有独到的接入控制和高效的调度、查询功能，可对相应的控制模型进行有效分析，并对其控制机制进行改进。在生产实践活动的需求牵引下，轮询系统因具有公平性、灵活性、高效性和实用性等特性［5，6］，在具体实践中得到了广泛应用，使此项领域的研究得以不断充实、完善和发展。

1 轮询系统原理

1.1 基本模型

轮询系统基本模型可以表述为［7-10］:由一个服务台(器)和N个队列(终端)组成，服务台(器)依据一定的规则按一个方向依次对每一个队列(终端)进行操作，最后一个队列(终端)操作完成后再返回第一个队列(终端)，这样便实现由N个队列(终端)共享一个或多个资源，应用时由一个或多个逻辑上的中心按照一定的周期顺序对各个队列(终端)进行查询，对有服务需求的队列(终端)提供资源的使用权。

轮询系统基本模型如图1所示。从模型中不难看出，轮询系统的控制过程包括队列(终端)中队员(信息分组)的到达过程、服务台(器)对队员(信息分组)的服务过程和队列(终端)间的转换查询过程。轮询系统的性能通常由以下几个基本要素来决定:

① 服务台(器)对各队列(终端)的查询顺序;

②服务台(器)每查询一个队列(终端)时所能服务的队员(信息分组)数;

③同一队列(终端)中队员(信息分组)的服务顺序;

④队员(信息分组)到达过程，服务台(器)对队员(信息分组)的服务过程以及查询询转换过程所服从的概率分布。

图1 轮询系统基本模型图

第1个要素决定轮询系统是静态还是动态的。对于静态系统，服务台(器)查询各队列(终端)的顺序保持固定不变;对于动态系统，服务台(器)查询队列(终端)的顺序随时间或控制机制而变化。第2个要素由不同的轮询服务策略来决定。目前，主要的策略有完全服务、门限服务和限定K服务。第3个要素由同一队列(终端)中队员(信息分组)的服务顺序来确定，其规则有 FCFS(First Come First Service)、LCFS(Last Come First Service)、PS(Processor Sharing)、ROS(Random Order of Service)、SJF(Shortest Job First)、FP(Fixed Priorities)等［2，8，11］。第4个要素表明轮询系统可以采用3个过程(到达过程、服务过程和转换过程)来进行描述。其中的到达过程由队员(信息分组)到达率(Arrival Rate)这一随机变量所服从的概率分布来表示;服务过程由服务台(器)按相应服务规则对队员(信息分组)进行传输服务时间(Service Time)这一随机变量所服从的概率分布来表示;轮询转换过程由服务台(器)轮询相邻队列(终端)所需转换时间(Switchover Time)这一随机变量所服从的概率分布来表示。基于以上4个要素，可根据实际需求建立相应的轮询系统模型来进行描述。

1.2 分类

根据国内外学者研究，轮询系统大致可分为以下几类［2-11］:

①根据服务台(器)查询每个数据队列(终端)时，服务队员(信息分组)多少的方式可将其分为门限服务、完全服务和限定K服务3种类型;

②按不同分析方法可将其分为连续时间系统和离散时间系统;

③按缓冲区大小情况可将其分为每个队列(终端)只有单个队员(信息分组)的容量和容量无限的系统;

④按转换时间为零与否可将其分为有转换时间和无转换时间(并行)的系统;

⑤按照各队列(终端)相应参数所遵从的概率分布相同与否可将其分为对称系统和非对称系统;

⑥根据各队列(终端)是否可享有服务优先级情况可将其分为区分优先级和不区分优先级的系统，即系统可以是严格意义上依次查询，也可以根据优先级情况调整顺序查询;

⑦按系统是否能够进行解析的情况可将其分为精确解析系统和近似解析系统。

1.3 特性参数

研究和分析一个具体的轮询系统的首要目标是要获取系统特性参数［2-9，13-16］。轮询系统的特性参数主要有平均排队队长 (Mean Queue Length，MQL)、平均循环周期 (Mean Cyclic Period，MCP)、系统吞吐量 (System Throughput，ST)、平均等待时延(Mean Waiting Time，MWT)以及平均响应时间(Mean Response Time，MRT)等。其中，MQL 为队列(终端)中队员(信息分组)的平均数量(长度);MCP为服务台(器)相继2次访问同一队列(终端)的时间;ST为单位时间内系统传输服务的队员(信息分组)数;MWT为自队列(终端)中队员(信息分组)到达直至其开始接受服务的时间;MRT为平均等待时延加上平均服务时间;MQL、MCP和SL通常为系统的一阶特性参数(在限定服务系统中，MQL为二阶特性参数，因为它需要通过二阶特性求解才能得出)，而MWT和MRT为系统的二阶特性参数，MWT是解析较为困难且非常重要的一个参数。获取上述参数通常按3个步骤来进行。首先是要建立起相应的数学模型或仿真实验平台;其次是要解析出系统特性参数表达式，或模拟出轮询控制机制，并求算(模拟)出具体参数值;最后就是依据所获取的特性参数来衡量或改进系统的控制性能，为系统应用打下坚实的理论基础。

2 轮询系统研究概况

在20世纪50年代后期，作为一个种检测手段和方法，轮询模式应用到设备检修控制过程，既降低了设备故障率，还提高了生产效率，使生产商在设备运营中收到良好效益［8，9］;生产商根据控制需求情况对轮询模式进行改进，使轮询模式上升到一种技术层面;相关学者将设备检修以及交通信号控制等技术抽象为轮询模型，并采用概率论和排队论(Queuing Theory)等数学理论加以研究，使轮询技术研究上升到理论化和系统化阶段［2-11］。20世纪60年代，2队列的轮询系统模型被用于交通信号控制中;随着队列增加，系统描述的参数增加，系统状态表示的难度也增加［3］。20世纪70年代，随着计算机网络的出现，轮询系统理论被用于多个计算机终端共享一台中央主机的数据传输网络中［4］。20世纪80年代，轮询系统理论在计算机局域网的研究中得以不断充实和发展。如令牌环(Token Ring)协议中通过令牌的循环传递，获得令牌的站点即获得了控制信道发送信息的权利，以此来实现数据通信，这种机制正是轮询系统理论在计算机局域网调度控制中的具体应用［5-9］。20世纪90年代，轮询系统理论应用到ATM(Asynchronous Transfer Mode)网络中，使ATM网络较好地实现信道资源共享，显示了轮询控制这种方式所具有的良好时延保障特性，该特性在多处理器计算机系统以及工业制造中又得到了进一步的应用［13-15］。进入21世纪，轮询系统理论又应用到工业过程控制、交通运输调度、物流系统管理、智能交通信号控制、设备故障检测、各种总线系统、无线电台组网、数据链、宽带无线通信网络、WLAN、WSN、蓝牙网络、Ad Hoc网络、4G 网络、WiMAX、EPON(Ethernet Passive Optical Network)、OFDM(Orthogonal Frequency Division Multiplexing)、RFID系统(Radio Frequency Identification Systems)以及社会经济等领域中，较好地解决了资源优化分配与调度控制等问题［1，2，10-12，16-26］。

3 分析方法

从国内外学者对轮询系统理论的研究和分析情况看，不同学者所采用的方法也不尽相同。其中，常见的分析方法有大致有以下几种:①缓冲区占有法(Buffer Occupancy Method)［3］;② 站点时间法(Station-Time Method)［5］;③ 后代集方法 (Descendant Set Method)［15］;④ 均值分析法(Mean Value Analysis Method)［2，11］;⑤ 嵌入式 Markov 链(Embedded Markov Chain Method)和概率母函数方法(Probability Generating Function Method)［1，7-9］;⑥ 计算机模拟仿真法(Computer Simulation Method)。前面5种方法能够针对一般的轮询模型进行分析，也能够计算出一阶特性参数(如MQL、MCP);对于二阶特性(如MWT)，精确计算的难度比较大，有的方法只能给出近似解，对于三阶特性(平均等待时延的方差)，有的方法因计算相当复杂，只能得出近似解［2，5，11，15］;对于较为复杂的轮询系统模型(如混合服务、优先级服务和多级轮询等)，有的方法很难建立数学模型，只能通过仿真实验给出结果［2，16，19，20］;对于限定(K≥1)服务系统的平均等待时延，因计算难度较大，多数学者采用近似计算或通过模拟仿真实验给出结果［12，22］。由此可见，轮询系统的性能分析不是任何时候都能够得出各基本参数的精确解析式，有时只能得出近似的关系式，有时只能通过大量仿真实验来得到相关参数值，这是长期困扰轮询系统研究者们的难题。对轮询系统的研究，大多是建立模型或寻求一定的方法来分析、求解出MQL和MCP等一阶特性参数;对于MWT等二阶特性参数的分析，大多采用近似方法进行分析，有的采用仿真实验方法进行分析，有的要通过解复杂度为tn的方程组才能得到精确结果［13-15］。60多年来，国内外学者针对实践中不断出现的轮询系统模型，一直在寻求有效方法来获取系统特性参数，以此分析和评价系统性能指标，最终把模型用于生产实践。

4 轮询系统研究的重要方向

鉴于轮询系统在不同领域的广泛应用，激发了研究者不断改进轮询系统的分析方法，使系统解析的精确度不断提高，同时还改进和拓展了传统的轮询系统模型，提高了轮询系统控制性能。随着研究的不断深入，相关理论研究成果又反过来促进轮询系统的应用和发展，实现理论分析和应用实践相辅相成、共同提高的目标。当前，轮询系统研究的重要方向集中体现在以下几个方面:

①系统特性参数精确解析:轮询系统的精确解析一直是该领域研究的重点和难点，尤其是二阶特性以及高阶特性(如平均排队队长方差、平均等待时延方差等)的分析，多数情况下得不到精确解，并且理论计算的复杂度和难度都很大［1，2，11，13］;

②基本要素优化调整:依据轮询系统的基本模型，结合实际应用中的具体要求和问题的复杂性，需要对轮询系统的基本要素进行不断地优化和调整，但系统性能特性分析的难度将进一步加大［11，19，20，22］;

③服务策略优化组合:服务策略的选择决定了每个站点的服务时间和服务效率，选择合适的服务策略是改进系统性能的重要方法;有时单一的服务策略是不够的，需要综合利用多种服务策略的混合模式来满足实际应用的需要，服务策略的选择既要考虑到服务的具体需求，又要考虑到公平性;服务策略可以是既定的，也可以是随机的，此时系统分析的难度将会增大［11，12，19，22］;

④服务顺序控制调整:同一队列(终端)内的队员(信息分组)顺序通常有 FCFS、LCFS、PS、ROS 和SJF等;队员(信息分组)在接受完服务后就离开或发送出去，也可以在服务完成后按一定概率转到其他队列(终端)继续等待，形成轮询系统内队列(终端)间的路由方式，这与实际通信应用中的自动重发机制(ARQ)或选择重发机制(SR-ARQ)等是相对应的，反映此项研究的成果还较为鲜见［11］;

⑤优先级多级轮询服务:区分业务优先级控制的轮询系统成为当前研究的一个热点;此类系统能够充分考虑站点所处特殊地位和作用，将特殊站点进行分级，形成多级轮询系统，特殊站点则作为高优先进行区分服务，普通站点作为低优先级进行服务，此时系统模型的建立及解析成为一个难点课题［2，21，23］;

⑥ 新业务需求研究:WLAN、WiMAX、WSN、Ad Hoc、EPON、OFDM和RFID等代表着21世纪网络的先进技术，具有广泛的应用空间，但如何对网络资源进行有效分配、管理和调度，并根据实时性、公平性、重要性和QoS要求，合理地分配数据(排队)和带宽一直是该领域研究的热点课题，如何从理论上采用精确解析方法来对其MAC协议的接入控制和轮询调度策略作进一步分析、优化并改进系统总体性能，是该领域研究的难点课题［6，10，12，14，20，22，24，25］;

⑦多服务器轮询系统研究:长期以来，轮询系统基本模型以及以此拓展的系统模型通常设定为单一的逻辑服务器，采用相应的控制机制对系统内各站点进行轮询调度;在实际应用中，有许多情形需要系统内有多个服务器实施轮询调度，由此带来的轮询控制问题变得更为复杂，这方面的研究成果也比较少见［22］;

⑧非对称轮询系统研究:在非对称系统中，允许定义各站点特性的随机变量具有不同的分布参数，允许各站点位置移动(如Ad hoc网络)，因而具有更为广泛的实用性;但如何提出系统控制模型?怎样建立数学模型?能否精确解析系统特性参数?采用何种方式进行仿真和验证?这些都是长期困扰研究者们的难题［5，13，19，24］。

5 结束语

轮询系统的演进历程及其发展、应用情况表明:轮询系统理论是一种重要的资源分配和共享理论，生产实践活动中的诸多系统可以抽象为轮询系统模型来加以研究和分析;轮询所特有的接入控制和高效调度、查询功能，使其成为一种非常有用的工具，可对通信、计算机等领域中的控制模型进行有效分析，结合网络系统资源如何进行有效分配、管理和调度，并根据实时性、公平性、重要性以及QoS保障服务等要求，对相应的控制机制进行改进;随着轮询系统在不同领域的广泛应用，激发了一大批研究者不断改进轮询系统的分析方法，在不断提高系统控制性能的同时，还促使轮询系统的研究向更高的深度和广度延伸和拓展，使其发挥出更多、更好的效益。

［1］ 赵东风，丁洪伟，赵一帆，等.多级门限服务轮询系统MAC离散时间控制协议模型分析［J］.电子学报，2010，38(7):1495-1500.

［2］ BOON M A A，ADAN I J B F，BOXMA O J.A Polling Model with Multiple Priority Levels［J］.Performance Evaluation，2010，67(1):468-484.

［3］ KONHEIM A G，BERND M.Service in a Loop System［J］.Journal of the Association for Computing Machinery，1972，19(1):92-108.

［4］ RUBIN I，De MORAES L F.Message Delay Analysis for Polling and Token Multiple-access Schemes for Local Communication Networks［J］.IEEE Journal on Selected Areas in Communications，1983，1(3):935-947.

［5］ FERGUSO M J，AMINETZAH Y J.Exact Results for Nonsymmetric Token Ring Systems［J］.IEEE Transactions on Communications，1985，31(5):223-231.

［6］ ELAD P.IEEE 802.11n Development:History，Process and Technology［J］.IEEE Communication Magazine，2008，46(7):48-55.

［7］ HIDEAKI T.Mean Message Waiting Times in Symmetric Multiqueue Systems with Cyclic Service［J］.Performance Evaluation，1985，5(4):271-277.

［8］ LEVY H，SIDI M.Polling Systems:Applications，Modeling and Optimization［J］.IEEE Transactions on Communications，1990，38(10):1750-1759.

［9］ TAKAGI H.Application of Polling Models to Computer Networks［J］.Computer Networks，1991，22(3):193-211.

［10］ TAO Li，LOGOTHETIS D.Analysis of a Polling System for Telephony Traffic with Application to Wireless Lans［J］.IEEE Transactions on Wireless Communications，2006，5(6):1284-1293.

［11］ BOXMA O，BRUIN J，BRIAN F.Sojourn Times in Polling Systems with Various Service Disciplines［J］.Performance Evaluation，2009，66(5):621-639.

［12］ LIU Qian-lin，ZHAO Dong-feng，ZHOU Dong-ming.An Analytic Model for Enhancing IEEE 802.11 Coordination Function Media Access Control Protocol［J］.European Transactions on Telecommunications，2011，22(6):332-338.

［13］ HWANG L C.An Exact Analysis of an Asymmetric Polling System with Mixed Service Discipline and General Service Order［J］.Computer Communications，1997，20(10):1293-1299.

［14］ FANTACCI R，ZOPPI L.Performance Evaluation of Polling Systems for Wireless Local Communication Networks［J］.IEEE Transactions on Vehicular Technology，2000，49(6):2148-2157.

［15］ KONHEIM A G.Descendent set:an Efficient Approach for Analysis of Polling Systems［J］.IEEE Transactions on Communications，1994，42(8):1245-1253.

［16］王智，申兴发，于海斌，等.两类服务对象轮询模型的平均运行周期［J］.计算机学报，2004，27(9):1213-1220.

［17］ JANE Y Y，CHONG PETER H J.A Survey of Clustering Schemes for Mobile Ad Hoc Networks［J］.IEEE Communications Surveys ＆ Tutorials，2005，7(1):32-48.

［18］ CAO Chun-sheng，YIN Ru-po，ZHANG Wei-dong.Mean Waiting Time Approximation for a Real Time Polling System［J］.High Technology Letters，2007，13(2):136-139.

［19］ CHANG Ben-jye ，Chen Yan-ling.Adaptive Hierarchical Polling and Markov Decision Process Based CAC for Increasing Network Reward and Reducing Average Delay in IEEE 802.16 WiMAX Networks［J］.Computer Communications，2008，31(10):2280-2292.

［20］ LIN Xiao-hui，KWOK Yu-kwong，WANG Hui.Cross-layer Design for Energy Eficient Communication in Wireless Sensor Networks［J］.Wireless Communications and Mobile Computing，2009，9(2):251-268.

［21］柳虔林，赵东风，赵一帆.基于优先级服务的两级轮询系统性能分析［J］.解放军理工大学学报:自然科学版，2011，12(3):223-228.

［22］ INATY E.A Multiservice WLAN Using a Radio Resource Scheduler［J］.European Transactions on Telecommunications，2010，21(1):90-100.

［23］ LIU Qian-lin，ZHAO Dong-feng，ZHAO Yi-fan.An EfficientPriority Service Modelwith Two-level-polling Scheme［J］.High Technology Letters，2011，17(3):245-251.

［24］ LIM W，YANG Y，MILOSAVLJEVIC M.Multicast Polling for 10G-EPON［J］.Electronics Letters，2012，48(9):513-514.

［25］ IYENGAR R，SIKDAR B.A Queueing Model for Polled Service in WiMAX/IEEE 802.16 Networks［J］.IEEE Transactions on Communications，2012，60(7):1777-1781.

［26］ WANG Hong-gang，PEI Chang-xing，SU Bo.Collision-free Arbitration Protocol for Ative RFID Systems［J］.Journal of Communications and Networks，2012，14(1):34-39.