【作者】 丁洪伟；

【导师】 赵东风；

【作者基本信息】 云南大学 ， 通信与信息系统， 2011， 博士

【摘要】 轮询系统理论是排队论中多队列顾客共享服务资源的理论。早期的工业过程控制中的指令传输、计算机通信网络中的信道资源分配、公共交通的车辆调度等,无不采用高可靠性的轮询控制策略。相关学者将设备故障检测、工业过程控制、多址接入控制、资源分配调度等采用轮询系统模型进行表征,并利用概率论、排队论、随机过程理论等加以研究,使其成为实际应用分析和研究的一类重要模型。随着信息网络技术的快速发展,轮询系统有了更广泛的应用,轮询系统理论早已成为网络资源分配和MAC控制协议中重要的控制理论。在轮询技术不断发展的今天,轮询排队理论研究也获得更新的成果,这对通信网络系统、计算机系统、交通运输、物流系统和工业过程控制等产生了较大的技术推动作用。轮询系统分析的目标是要建立起与轮询控制机制相吻合的数学模型及其函数关系式,精确解析出系统平均排队队长、平均循环周期、吞吐量、平均等待时延等特性参数的表达式。在这些参数中,平均等待时延是分析特定轮询系统时最为关键的特性参数。轮询系统模型由1个服务台(器)和N个排队队列(终端)组成,服务台依次轮询系统中的各队列,并为队列提供服务。模型中的排队顾客的到达过程、服务台提供服务的时间、服务台轮询转移时间都是随机过程,此数学模型表征出一个N维概率随机过程的复杂系统。基本轮询系统大致包括门限(Gated)服务型、完全(Exhaustive)服务型和限定(Limited- K)服务型三种类型。限定服务(K=1)轮询系统有较好的公平服务特性,但信息分组的等待时延较长。完全服务轮询系统中信息分组的等待时延最短,但服务的公平性较差。门限服务轮询系统的等待时延介于两者之间。在实际的通信网络MAC控制协议中,大部分采用多种轮询系统的混合控制系统。近年来,轮询模型已广泛用于多种系统的性能分析；在通信与计算机领域,它还专门作为诸如按需分配、多址接入控制等性能评价的准则。长达六十多年的轮询系统研究与探索实践表明：轮询系统模型是一种有效的分析工具,轮询系统理论是一种重要的资源分配和共享理论；轮询系统因其控制方式具有公平性、灵活性和实用性而得到了广泛的应用,使此项工作得以不断充实、完善和发展。本学位文针对通信网络中信息分组业务的平衡性和突发性,提出了一种多级门限服务的轮询系统控制模型。该系统在服务的公平性和信息分组时延性方面都有较好的特性,同时也能较好处理突发性业务,为其提供优质的QoS服务。本学位论文在构建多级门限服务轮询系统的分析模型的基础上,获得系统的平均排队队长、平均轮询周期和信息分组的平均等待时延等性能指标的精确解析结果,并通过计算机仿真实验验证了理论分析的正确性。轮询系统的应用由早期的设备故障检修逐渐拓展到交通运输调度、物流控制管理、通信网络、计算机网络、无线传感器网络、Ad Hoc网络以及社会资源配置等领域,并产生了积极有效的技术推动作用。迄今为止,对轮询系统理论的研究还在深入持续地开展和进行,一些新的系统模型不断出现,一些新的解析方法不断更新,一些新的应用领域不断拓展。进入二十一世纪以来,无线通信网络中的移动性、自组织性、高效性、节能性成为研究的热点。在上述研究工作中,先进的、性能优越的多业务MAC控制协议成为学科研究工作中的重要课题。本学位论文由六章组成,各章具体内容如下：第一章为绪论,主要介绍了轮询系统的概念、轮询系统的演进过程、轮询系统研究现状以及论文研究的背景情况。第二章详细地介绍了轮询系统中完全服务、门限服务和限定服务三种服务策略,并采用嵌入式马尔可夫链和多维概率母函数分析方法对三种轮询系统的性能进行了分析比较。第三章主要介绍了离散时间多级门限服务的轮询系统模型,并采用嵌入式马尔可夫链、概率母函数以及系统状态方程求解方法对该模型进行了精确解析；获得了系统的平均循环周期、平均排队队长、信息分组的平均等待时延的精确解析结果。在运行环境和初始参数相同的情况下建立仿真实验平台,用仿真实验结果与理论分析结果一致,说明了理论分析的正确性；将多级门限服务的轮询系统模型与普通门限服务轮询系统及完全服务轮询系统进行比较分析。第四章主要介绍了连续时间多级门限服务的轮询系统模型,采用嵌入Markov链理论对此轮询系统进行了分析,获得了轮询时刻系统队长的概率母函数,和信息分组等待时延变量的LST式,获得了系统的平均循环周期、平均排队队长、信息分组的平均等待时延的精确解析结果。在运行环境和初始参数相同的情况下进行计算仿真实验,计算机仿真实验结果说明了理论分析的正确性。第五章在介绍无线计算机网络(WBAN、WPAN、WLAN、WMAN、WWAN以及Ad Hoc)发展情况基础上,介绍了IEEE 802.11 PCF控制协议进行分析,把离散时间多级门限服务的轮询系统模型用于IEEE 802.11 PCF轮询调度机制,使其MAC控制协议的性能得到改进。介绍了无线传感器网络发展历史和其体系结构,介绍了WSN中PCF控制协议,对WSN中的MAC控制协议进行分析,把连续时间多级门限服务的轮询系统模型用于WSN分簇轮询控制,使得其MAC控制协议的性能得到改进。对Ad Hoc网络的起源和定义做了介绍,介绍了Ad Hoc网络中PCF控制协议,对Ad Hoc网络中的MAC控制协议进行分析,把离散时间多级门限服务的轮询系统模型用于Ad Hoc网络分簇轮询控制,得到了改进的MAC控制协议的性能指标。第六章对全文进行总结,包括本学位论文的主要研究成果和存在的问题做出了说明,今后的发展方向和今后课题的研究工作做了展望。更多还原

【Abstract】 Polling system theory is the theory of multi-queue customer service resources sharing in queuing theory. Early industrial process control instruction transmission, computer communication network channel resource allocation, scheduling and other public transport vehicles, etc. use the high reliability polling control strategy. Relevant scholars expressed that of equipment fault detection, industrial process control, multiple access control, resource allocation scheduling system by the polling system model, and using probability theory, queuing theory, stochastic processes theory to study, making it an important class of model for the practical application of analysis and study. With the rapid development of information network technology, polling system with a wider range of applications, polling systems theory has become an important control theory of the network resource allocation and MAC control protocol. Today, polling technology development, polling queuing theory obtains more new research results; this creates a larger role in promoting to communication network systems, computer systems, transportation, logistics systems and industrial process control techniques. Analyzing polling system goal is to establish the mathematical model and its functional relation that consistent with the polling control mechanism, solved exactly the expression of the mean queue length, the mean cycle time, throughput, mean waiting time delay (MWT) and other parameters of the system. In these parameters, the mean waiting delay(MWT) of a specific polling system is the most critical parameters. Among them, the MWT is the most important performance measure for analyzing the underlying system.Polling system model consists of a server and N queues, the server polls all queues in turn in the polling system, and provides services for the queue. The customer arrival process, the service time of the server, the server transfer time is random process in queuing model. The mathematical model expressed a complex system of N-dimensional probability random process. The basic polling system includes three types of service, that are gated service, exhaustive service and limited (k=1) service, limited (k=1) service polling system has more equitable service features, but the information packet waiting delay is longer. Gated service polling system has moderate features. Exhaustive service polling system has the shortest information packet waiting delay, but fairness of service is poor. In the actual communication network control protocol, most of the polling systems use a variety of hybrid control system. In recent years, polling model has been widely used in a variety of system performance analysis. In the communication and computer field, it is specifically performance evaluation criteria such as on demand, multiple access control. In the last 60 years, research indicates that polling system model has become an effective tool for analyzing system performance, and it provides a theoretical framework for resource allocation and assignment. Thanks to its impartiality, flexibility and practicality, polling systems have been widely used to analyze the performance of a variety of systems, enable this research to enrich, improve and develop. In this dissertation, M-gated service polling system control model are proposed in communication network for the balance and sudden of information packet service. The fairness of the system and information packet delay characteristics are better, but also to better handle sudden service, providing QoS guarantee. Analyzing polling system models is to set up, and derive closed form expressions to obtain the system parameters, such as the mean queue length (MQL), the mean cyclic period (MCP) and the mean waiting time (MWT). And the polling system performance results are verified through extensive simulations. Polling system gradually extended to other fields by the early equipment fault detection, that includes transportation scheduling, logistics control and management, communication networks, computer networks, wireless sensor networks, Ad Hoc networks, and social resources, etc. and it produces a positive and effective techniques promote effect. So far, the theoretical study of the polling system is still continuing to carry out and conduct in-depth some of the new model emerging, some new analytical method for constantly updated, new applications continue to expand. With coming of 21st century, the research of mobility, self-organization, high efficiency and energy saving for wireless communication becomes hot area, and the up-to-date as well efficient MAC protocol becomes an important subject.The dissertation consists of 6 parts, and it is organized as follows:Chapter 1 introduces the concept and the evolution of the polling system, the current research and the background of the dissertation.Chapter 2 introduces in detail the exhaustive service, gated service and limited (K=1) service polling systems, using the embedded Markov chain theory, the probability generating function and system state equations methodology, and gives performance evaluation. The performance of the three polling system are analyzed and compared.Chapter 3 introduces mainly the discrete-time M-gated service polling system model. Using the embedded Markov chain theory, the probability generating function and system state equations methodology, obtains the probability generating function of the queue length system and LST expression of variable waiting delay information packet. And obtains the accurate expression of mean cycle time, mean queue length, mean waiting time delay of the system. The initial parameters in the operational environment and create under the same simulation platform, using simulation results to verify the correctness of theoretical analysis; and the performance of the M-gated service polling system are analyzed and compared with gated service polling system and exhaustive service.Chapter 4 introduces mainly the continuous-time M-gated service polling system model. Using the embedded Markov chain theory, the probability generating function and system state equations methodology, obtains the probability generating function of the queue length system and LST expression of variable waiting delay information packet. And obtains the accurate expression of mean cycle time, mean queue length, mean waiting time delay of the system. The initial parameters in the operational environment and create under the same simulation platform, using simulation results to verify the correctness of theoretical analysis.Chapter 5 introduces the wireless computer networks development. Describes the IEEE 802.11 PCF control protocol analysis, the discrete-time M-gated service polling system model for the IEEE 802.11 PCF polling scheduling, improves performance of MAC control protocol. Describes the history and development of wireless sensor networks, its architecture, introduces the PCF control protocol in WSN, analyzing MAC control protocol in WSN, the continuous-time M-gated service polling system model is used to the WSN cluster polling control, and improves performance of MAC control protocol. Introduces the PCF control protocol in Ad Hoc Networks, analyzing MAC control protocol in Ad Hoc Network, the discrete-time M-gated service polling system model is used to Ad Hoc network clustering polling control, has been improved in the MAC control protocol performance.Chapter 6 draws the conclusion of the dissertation, including the main thesis of research results and make a description of the problems, and it also points out the future trends of the polling systems and puts forward some challenges.更多还原