离散时间的完全服务并行优化轮询排队系统特性分析

保利勇; 丁新昱; 丁洪伟; 官铮; 葛俊阳

doi:10.12263/DZXB.20220827

您当前的位置：

首页 >

文章列表页 >

离散时间的完全服务并行优化轮询排队系统特性分析

学术论文 | 更新时间：2025-12-11

- 离散时间的完全服务并行优化轮询排队系统特性分析
- An Exact Analysis of Discrete Time Polling Queuing System Based on Parallel Optimization Exhaustive Service
- 电子学报 2024年52卷第3期页码：838-848
- 作者机构：
  
  云南大学信息学院，云南昆明 650091
- 作者简介：
  
  [ "保利勇男，1975年生于云南楚雄.现为云南大学信息学院副教授，硕士生导师.2011年获得博士学位.研究方向为通信网络MAC层多址接入理论、冲突分界和混沌扩频通信等.E-mail: bly.yx@163.com" ]
  [ "丁新昱男，1998年生于山西运城.云南大学硕士研究生.研究方向为轮询多址接入理论.E-mail: 591077396@qq.com" ]
  [ "丁洪伟男，1964年生于云南景洪.现为云南大学信息学院教授，博士生导师.研究方向为轮询系统、随机多址通信系统." ]
  官铮女，1982年生于云南普洱.现为云南大学信息学院副教授，硕士生导师.主要研究方向为无线传感器网络、网络接入技术、系统性能分析和优化等．
  葛俊阳男，1994年生于河南封丘.云南大学硕士研究生.研究方向为轮询多址接入理论.
- 基金信息：
  
  国家自然科学基金(61072079;61461053)
- DOI：10.12263/DZXB.20220827
  中图分类号： TP393
- 收稿：2022-07-14，
  
  修回：2023-05-09，
  
  纸质出版：2024-03-25
- 稿件说明：
移动端阅览
保利勇,丁新昱,丁洪伟,等.离散时间的完全服务并行优化轮询排队系统特性分析[J].电子学报,2024,52(03):838-848.

BAO Li-yong, DING Xin-yu, DING Hong-wei, et al.An Exact Analysis of Discrete Time Polling Queuing System Based on Parallel Optimization Exhaustive Service[J].Acta Electronica Sinica, 2024, 52(03): 838-848.
保利勇,丁新昱,丁洪伟,等.离散时间的完全服务并行优化轮询排队系统特性分析[J].电子学报,2024,52(03):838-848. DOI：10.12263/DZXB.20220827

BAO Li-yong, DING Xin-yu, DING Hong-wei, et al.An Exact Analysis of Discrete Time Polling Queuing System Based on Parallel Optimization Exhaustive Service[J].Acta Electronica Sinica, 2024, 52(03): 838-848. DOI：10.12263/DZXB.20220827

摘要

轮询是一种依次有序服务的系统资源动态调度机制.针对服务器在站点间查询、服务和转移过程中的流水线作业方式导致了系统整体服务效率较低的问题，本文提出了完全服务的并行优化轮询系统.首先，构建了系统的单服务器多队列排队模型和相应的系统状态方程，并精确解析出系统特性参数的完整数学解析表达式.此外，还提出了一种系统状态稳定性的判定方法，对不同负载状态下的系统稳定性进行了定量分析.计算机仿真的统计分析结果与理论计算值相一致.最后，系统性能分析表明，在保持周期性、无冲突服务的基础上，系统的队长、时延特性和稳定状态下负载能力均得到了较大的提高.

Abstract

Polling is a dynamic scheduling mechanism of system resources with orderly services. Considering the low service efficiency of the whole system in the pipelining process of the server

this paper proposes a novel system of parallel optimization polling based on an exhaustive service policy. Firstly

the systematic single-server multi-queue queuing model and its equations of state transfer are constructed. Secondly

the complete mathematical analytical expressions of the system characteristic parameters are accurately analyzed. In addition

this paper attempts a method to quantitatively analyze the system stability under different load states. The statistical analysis result of the computer is consistent with the theoretical calculation value. Moreover

the system performance analysis shows that the queuing length

waiting delay characteristics and load capacity in steady state of the polling system have been greatly improved while maintaining periodic and conflict-free services.

关键词

Keywords

references

TEYMOORI P , SOHRABY K , KIM K . A fair and efficient resource allocation scheme for multi-server distributed systems and networks [J ] . IEEE Transactions on Mobile Computing , 2016 , 15 ( 9 ): 2137 - 2150 .

FRALIX B . A new look at a smart polling model [J ] . Mathematical Methods of Operations Research , 2018 , 88 ( 3 ): 339 - 367 .

XU J , GAUTAM N . On competitive analysis for polling systems [J ] . Naval Research Logistics , 2020 , 67 ( 6 ): 404 - 419 .

VLADLMIR V , OLGA S . Polling systems and their application to telecommunication networks [J ] . Mathematics , 2021 , 9 ( 2 ): 117 .

BIANCHI G . Performance analysis of the IEEE 802.11 distributed coordination function [J ] . IEEE Journal on Selected Areas in Communications , 2000 , 18 ( 3 ): 535 - 547 .

TOUMI M , SEMCHEDINE F . Improving the throughput in lightly disturbed IEEE 802.11 DCF saturated network using the fragmentation mechanism under basic access Mode [J ] . Wireless Personal Communications , 2021 , 118 ( 4 ): 2383 - 2397 .

DVIR N , HASSIN R , YECHIALI U . Strategic behaviour in a tandem queue with alternating server [J ] . Queueing Systems , 2020 , 96 ( 3 ): 205 - 244 .

ABHISHEK , BOON M A A , BOXMA O J , et al . A single-server queue with batch arrivals and semi-Markov services [J ] . Queueing Systems , 2017 , 86 ( 3 ): 217 - 240 .

BORST S , BOXMA O J . Polling: Past, present, and perspective [J ] . TOP , 2018 , 26 ( 3 ): 335 - 369 .

TAKAGI H . Mean message waiting times in symmetric multi-queue systems with cyclic service [J ] . Performance Evaluation , 1985 , 5 ( 4 ): 271 - 277 .

赵东风 , 郑苏民 . 查询式完全服务排队模型分析 [J ] . 电子学报 , 1994 , 22 ( 5 ): 102 - 107 .

ZHAO D F , ZHENG S M . Analysis of a polling model with exhaustive service [J ] . Acta Electronica Sinica , 1994 , 22 ( 5 ): 102 - 107 . (in Chinese)

LEE G , SHIN S , JEONG J . Efficient hybrid polling for ultra-low latency storage devices [J ] . Journal of Systems Architecture , 2022 , 122 : 102338 .

JIANG T , LU X Z , LIU L , et al . Strategic behavior of customers and optimal control for batch service polling systems with priorities [J ] . Complexity , 2020 , 2020 : 6015372 .

RAN W X , LIU S , ZHANG Z . A polling-based dynamic order-picking system considering priority orders [J ] . Complexity , 2020 , 2020 : 4595316 .

BOON M A A , ADAN I J B F , BOXMA O J . A polling model with multiple priority levels [J ] . Performance Evaluation , 2010 , 67 ( 6 ): 468 - 484 .

PEREL E , PEREL N , YECHIALI U . A polling system with‘join the shortest - serve the longest' policy [J ] . Computers & Operations Research , 2020 , 114 : 104809 .

MEYFROYT T M M , BOON M A A , BORST S C , et al . Performance of large-scale polling systems with branching-type and limited service [J ] . Performance Evaluation , 2019 , 133 : 1 - 24 .

YANG Z J , MAO L , YAN B , et al . Performance analysis and prediction of asymmetric two-level priority polling system based on BP neural network [J ] . Applied Soft Computing , 2021 , 99 : 106880 .

ADAN I J B F , BOXMA O J , KAPODISTRIA S , et al . The shorter queue polling model [J ] . Annals of Operations Research , 2016 , 241 ( 1 ): 167 - 200 .

KIM B , KIM J . Analysis of the waiting time distribution for polling systems with retrials and glue periods [J ] . Annals of Operations Research , 2019 , 277 ( 2 ): 197 - 212 .

UNCU N . Load balancing in polling systems under different policies via simulation optimization [J ] . International Journal of Simulation Modelling , 2022 , 21 ( 2 ): 273 - 283 .

VAN DER GAAST J P , ADAN I J B F , KOSTER R B M DK . The analysis of batch sojourn-times in polling systems [J ] . Queueing Systems , 2017 , 85 ( 3 ): 313 - 335 .

BOON M A A , BOXMA O J , KELLA O , et al . Queue-length balance equations in multiclass multiserver queues and their generalizations [J ] . Queueing Systems , 2017 , 86 ( 3 ): 277 - 299 .

PAPACONSTANTINOU X , BERTSIMAS D . Relations between the prearrival and the postdeparture state probabilities and the fcfs waiting time distribution in the Ek/G/s queue [J ] . Naval Research Logistics , 1990 , 37 ( 1 ): 135 - 149 .

HEBUTERNE G . Relation between states observed by arriving and departing customers in bulk systems [J ] . Stochastic Processes and Their Applications , 1987 , 27 ( 2 ): 279 - 289 .

BOON M A A , WINANDS E M M . Open problems for critically loaded k-limited polling systems [J ] . Queueing Systems , 2022 , 100 ( 3 ): 281 - 283 .

ADAN I J B F , KULKARNI V G , LEE N , et al . Optimal routeing in two-queue polling systems [J ] . Journal of Applied Probability , 2018 , 55 ( 3 ): 944 - 967 .

JOLLES A , PEREL E , YECHIALI U . Alternating server with non-zero switch-over times and opposite-queue threshold-based switching policy [J ] . Performance Evaluation , 2018 , 126 : 22 - 38 .

罗启鹏 , 保利勇 , 丁洪伟 , 等 . 离散时间并行优化门限服务轮询系统排队特性解析 [J ] . 电子学报 , 2019 , 47 ( 9 ): 1937 - 1942 .

LUO Q P , BAO L Y , DING H W , et al . Performance analysis of discrete time polling queuing system based on parallel optimization gated service [J ] . Acta Electronica Sinica , 2019 , 47 ( 9 ): 1937 - 1942 . (in Chinese)

刘春花 , 赵东风 , 丁洪伟 . 周期查询系统并行调度策略研究 [J ] . 云南大学学报(自然科学版) , 2003 , 25 ( 5 ): 401 - 404 .

LIU C H , ZHAO D F , DING H W . Study of parallel schedules for polling systems with limited service [J ] . Journal of Yunnan University (Natural Science) , 2003 , 25 ( 5 ): 401 - 404 . (in Chinese)

SAFFER Z , TELEK M , HORVÁTH G . Analysis of Markov-modulated fluid polling systems with gated discipline [J ] . Journal of Industrial & Management Optimization , 2021 , 17 ( 2 ): 575 - 599 .

DUDIN A , DUDIN S , KLIMENOK V , et al . Vacation queueing model for performance evaluation of multiple access information transmission systems without transmission interruption [J ] . Mathematics , 2021 , 9 ( 13 ): 1508 .

ZEIFMAN A , KOROLEV V , SATIN Y . Two approaches to the construction of perturbation bounds for continuous-time markov chains [J ] . Mathematics , 2020 , 8 ( 2 ): 253 .

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

两级优先级控制轮询系统研究

移动AdHoc网络中的公平按需多址接入协议

收敛的级联形式自适应IIR滤波器