【作者】 保利勇；

【导师】 赵东风；

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

【摘要】 轮询为系统服务资源分配提供了非竞争的访问控制机制,其控制实现过程简洁可靠,可以有效避免接入对象间的竞争冲突,特别在高负载情况下能够获得较优的共享资源利用率。近几十年来,国内外学者对轮询系统的理论研究一直在不断充实和发展,对轮询系统的理论研究取得了丰硕的成果。轮询系统的研究成果也广泛应用于工业控制、通信网络、生产管理和经济发展预测等领域。应用轮询系统模型分析实际问题,对计算机系统及通信网络QoS进行研究,可以定量地分析网络系统性能、评估网络的服务质量。因此,进一步深入对轮询系统的研究有着很重要的现实的意义。轮询系统模型是典型的多队列多服务器排队系统架构,服务器按照队列的次序周期性地访问各个队列。控制过程包括顾客进入队列的到达过程、服务器在队列间的查询转换过程和服务器对各个队列的服务过程,服务器的服务方式可分为门限、完全和限定服务三类基本策略。所以,轮询系统是由三个n维随机过程组成的复杂系统。由此可见,对其一阶系统特性分析如平均排队队长、平均查询周期和二阶系统特性如平均等待时间的精确解析都有很大的难度。应用概率论、排队论、随机过程等理论工具,结合工业过程控制、多址接入控制、资源分配调度等实际应用过程的控制机理,建立起相应的数学分析模型,精确解析出系统的关键性能参数表达式(如平均排队队长、平均查询周期、吞吐量、平均等待时延等),对系统进行定量的性能评估是轮询系统研究的主要内容和难点。由于实际应用需求的不断提升,系统结构的日趋复杂,轮询系统的分析和研究的难度也在不断增大。在近二十年时间里,随着微电子技术与通信理论的迅速发展,通信网络获得了跨越式的发展。由于系统服务资源毕竟是有限的,MAC层协议作为决定资源使用权的技术是提高整体网络性能的重要保障。MAC机制不仅能使共享资源得到充分利用,同时还影响着上层协议的性能实现。所以,高效的MAC机制是系统支持QoS的关键。如何设计出高效的MAC层协议是一个有价值的课题研究方向。随着网络的发展和多媒体业务需求的提升,就需要突破单一轮询服务控制策略的均衡思想,在周期性的访问基础上拓展多样化查询服务次序和混合服务策略等控制措施,使得系统服务性能得到更大的优化和完善。目前,为多优先级业务提供实时的、较优鲁棒性的和高质量的QoS保证是轮询问题研究的热点。本论文在国家自然科学基金项目(No.61072079,“轮询系统理论演进及应用控制协议研究”)、国家自然科学基金项目(No.60362001,“通信网络中动态优先级控制理论及方法研究”)、中央与地方共建高等学校特色优势学科“网络通信与无线通信技术实验室”项目和云南大学理(工)科校级科研项目(No.2007Q021C,“多队列多服务器轮询系统控制策略研究”)的支持下,在两级优先级控制轮询系统模型和概率流控的轮询系统模型详细研究的基础上,重点对通信与计算机领域媒体接入控制MAC协议的控制策略做了比较深入系统的分析和优化,并取得了一些创新性的研究成果,主要创新内容包括：1、论文在总结、归纳门限、完全和限定服务基本轮询系统的控制机理、排队系统建模、对关键性能指标的数学解析过程、仿真实验和系统性能分析的基础上,综合分析了三个基本排队系统的典型特点,指出传统系统体系结构的固有不足,难以满足网络服务进入更高层次的应用需求。从优化与改进查询顺序、服务策略和服务顺序三个基本要素入手,提出了完全与限定混合服务策略控制的两级优先级站点轮询系统,确保了通信网络中高优先级业务的顾客得到更优质网络服务质量保证,优化了系统性能。2、本文进一步以排队理论为基础,采用嵌入式Markov链、多维概率母函数和LST变换等数学分析工具,为该轮询系统及其拓展系统构造出相对完善的数学模型,推导出系统状态变量的概率母函数,并对中心站点和普通站点的平均等待队长、平均查询周期和顾客的平均排队时延进行精确的数学解析和仿真实验分析。理论计算和仿真实验对比分析的结果说明了理论分析与实验的一致性。新的轮询系统模型中实现了区分不同优先级的控制以满足基于优先级服务的实际需求,优化和提高了系统性能,具有较好的公平性、灵活性和针对性。3、本文还提出概率流控的完全服务与限定服务轮询系统,系统模型中各站点信息分组按M/G/1规则,以多重休假和按特定几何概率p批量到达。该模型同样采用嵌入式Markov链和多维概率母函数方法,在连续时间状态下对系统模型进行解析。又采用数值分析和计算机仿真实验方法,在系统运行环境和初始参数相同的情况下,从信息分组到达率、服务时间、系统转换时间以及几何概率p变化等方面进行分析。理论数值分析和计算机仿真实验具有较好的一致性验证了系统模型理论分析的有效性。最后通过系统性能分析验证了该模型除了仍具有优先级完全服务与限定(K=1)服务轮询系统的优点外,通过引入几何概率p的分析方法,起到了业务流量控制(0<p<1)、休眠(p=0)和唤醒(p=1)的功能,使得系统模型在应用研究中更有实用价值。4、本文以Web服务器集群系统、片上网络系统NoC (Network on Chip)以及无线传感器网络WSNs的媒体接入控制MAC协议的调度策略为主要研究对象,详细分析了以上三种网络系统的特点和服务需求,基于优先级的轮询调度算法分别对Web服务器集群系统的负载均衡调度策略、片上网络的仲裁器调度策略(Arbitration policy)和无线传感器网络的分簇调度控制策略做进一步科学的优化,建立了相应的理论模型,完成了对系统性能关键参数的数学解析和仿真实验,结果证明了新的调度策略能基于不同的优先级需求提供针对性的服务质量保障,优化网络系统性能,减低了系统开销,对系统性能的提高有较好的帮助。最后对全文的主要工作及创新点进行了总结,并讨论了论文不完善的方面,指出课题今后研究的方向。更多还原

【Abstract】 Polling provides noncompetition access control for the distribution of the service resources in the system. The completion of its control process is brief and dependable, which will effectively avoid the conflicts caused by customers’competition for service resources and will maintain a higher utility for resources sharing especially in high-loaded situation. Over the past few decades, abundant findings have been produced by scholars at home and abroad in the studies of the polling theories. The findings of polling system have been widely applied in industry control, communications network, production management, traffic and transportation, and economic activities. The polling system model are often used in the analysis of practical issues during which the function and service quality of the system will accordingly be tested via quantificational method. Therefore, it is of great practical significance to promote the researches on polling system.Polling system model is a typical multi-queue multi-server queuing system. The server, following the queuing order, cyclically visits at each queue. The control process covers the arrival service after the customers enter into the queue, the server’s inquiry transformation in the queues, and the server’s service for each queue. The services are divided into three categories of gated, exhaustive, and limited service policies. In this sense, polling system is a complex one formed by three n-dimensional stochastic processes. It is thus difficult to make an accurate analysis on the system’s one-order characteristics like the mean queue length and the mean inquiry cycle, and on the two-order characteristics like the mean waiting time.The key points and special difficulties in the researches on polling system are thus found in the establishment of a corresponding mathematical model by means of probability, queuing, stochastic process and based on the control mechanism of the practical system so as to give accurate analysis on the key performance parameter formulas such as the mean queue length, the mean cyclic time, throughput, and the mean waiting time of customers, and the evaluation on the system’s functions via quantificational methods. Moreover, the difficulties are on the rise in that higher demands of the system are expected for practical use and the structure of the system is getting more and more complex.Polling queuing system is divided into the system of continuous time and the system of discrete time. The former is a queuing model which have long been established and widely applied. The researcher of this study has made a thorough and comprehensive analysis on the above-mentioned three polling systems of basic service policies. Over the past 20 years, communication network has enjoyed accelerated development along with the advancement of microelectronic technology and communications theories. Still, the service resources of the system are limited. MAC layer protocol, determining the right of resources use, becomes the important guarantee to the enhancement of the entire network function. MAC mechanism, the key to the QoS supported by the system, enables the wide use of shared resources while it also influences the performances of the above layers. Therefore, the design of a high-efficiency MAC layer protocol remains a valuable research program. With the increased requirements for network service and multimedia performance, it is urgent to break away from the single polling policy service control policies and to develop new and varied control policies for inquiry service order and mixed service on the basis of cyclic access so that the system service performances will be greatly enhanced and optimized. Currently, the research concentration in polling lies with the establishment of real-time, robust and high-quality QoS for multi-priority services.This dissertation is the research work aiming at the analysis of the two-class priority station polling system under the policies of exhaustive and limited services at the continuous time and the improved system. It also makes a systematic study on the MAC protocol policies in communications and computer fields that have been connected with media. All the research work owes greatly to the supports by the Program of Natural Science Foundation of China (NSFC) (No.61072079,"The Evolution of Polling System and the Study of Applied Control Protocol"), by the NSFC Program (No.60362001, entitled "Theories and Approaches of Dynamic Priority Control in Communication Network"), by the Program of "Network Communication and Wireless Communication Technology Lab" under the Cooperation between the Central Government and the Local Government in support of the peculiar advantageous disciplines of the local institutions of higher learning, and by the Science-Engineering Program of Yunnan University (No.2007Q021C, entitled "The Research on Multi-Queuing Multi-Servers Polling System Control Policy"). This research has produced some creative findings which are seen as follows:1. This research shows that the traditional single system structure can hardly meet the higher requirements of differentiating priority service after a comprehensive analysis is made on the typical features of three fundamental queuing systems based on an overview of the control mechanisms and queuing system modeling of the gated, exhaustive and limited services polling systems, and on the mathematical resolving process, simulated experiment and system function of the key performance indexes. It proposes the idea of the two-class priority station polling system under the exhaustive and limited services control policies, and improved system on the basis of the enhancement and optimization of inquiry order, service policy and service order. The practice has optimized the system performance and has ensured that the high-priority customers in communications network enjoy more qualified service.2. Further, this research, based on queuing theory and the mathematical analyses via Markov chain, multidimensional probability generating function, and Laplace -Stieltjes transformation, has produced a comparatively perfect mathematical model for the polling system and its expanded system, has deduced probability generating function of the system status variable, and has made accurate mathematical resolving and simulated experiment on the mean queue length, the mean inquiry cyclic time, and the mean waiting time of customers at the key and the common stations. The findings from the comparative analysis of the theoretical computing and simulated experiment verify the correspondence of theoretical analyses with simulated experiments. The new polling system modeling has enabled the differentiation of the controls of different priorities so as to satisfy the practical demand for priority services, and has optimized the system performance. It has the evident features of fairness, flexibility and pertinence.3. Meanwhile, this research has proposed a polling system of exhaustive and limited services based on probability flow control. In the system model, information packets of each station, following M/G/1 regulations, arrive in batch by means of multiple vacations and in accordance with geometry probability p. Likewise, the approaches of Markov chain and multiple-probability generating function are applied in the analysis of the model at the continuous time. Moreover, mathematical analysis and computer simulation are conducted, under the circumstances of similar system operation and primary parameters, to expound the arrival rate of information packets, service time, system switching time, and the change of geometry probability p. It turns out that the result of theoretical numerical analysis identifies well with that of computer simulation, which justifies the validity of the theoretical analysis of system model. The result of system operation analysis proves that the system model, in addition to the advantages of the exhaustive and limited services of priority polling stations, has further practical values in applied researches in that it has performed the functions of traffic flow control (0< p< 1), dormancy (p= 0) and awakening (p= 1) via geometry probability p.4. This research aims at the scheduling policies of Web server cluster, and NoC (Network on Chip), and WSNs with the MAC protocol. Detailed analyses are made on the above-mentioned network systems concerning their features and service demands. Based on the priority-based polling schedule Algorithm, scientific optimization is conducted respectively on the load balance scheme policy of the Web Server Cluster System on the basis of Internet application, the SoC Arbitration policy of MPSoC, and the clustering scheme control policy of the WSNs. Corresponding theoretical models are established and mathematical resolving and simulated experiment are conducted on the key parameters of system performance. As a result, it has been testified that the new scheduling strategy works well in providing good service of differentiating priorities according to different demands in WAN, NoC and Wireless Communications Network. Moreover, it optimizes the performance of network system and reduces the expense on system operation. The findings of this research will be of great help in the enhancement of the system performance.Finally, besides a summary of this research, further suggestions are given so as to promote the researches of the similar kind.更多还原