輪詢系統的演進及發展

柳虔林，趙東風，丁洪偉，蔡 煜

(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)這一隨機變量所服從的概率分布來表示?；谝陨?個要素，可根據實際需求建立相應的輪詢系統模型來進行描述。

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.