Design Of Scheduling Algorithms In Multi-Queue Multi-Server Systems

In recent years,the rapid development of wireless communication technologies,especially the mobile communication technologies that went through Global System for Mobile Communications(GSM),Code Division Multiple Access(CDMA),Long Term Evolution(LTE)and 5th-Generation New Radio(5G),have promoted the development of the communication industry.How to exploit the radio resource efficiently is a hot research topic that has been discussed in the communications industry,and the wireless resource scheduling as the core part of the wireless resource management has drawn a lot of attention of scientific researchers.The traditional wireless resource management aims at making more profits from the view of operators,for example,maximizing the system throughput,mining the system delay,and mining the packet loss.Based on the principle of customer first,mobile operators pay more attention to quality of user experience,therefore the object of this thesis is to improve the user perceived throughput by several scheduling techniques.The Orthogonal Frequency Division Multiplexing(OFDM),a technology in physical layer,is introduced for wireless communication systems,which greatly improves the throughput of the system.The communication models based on OFDM can be modeled as Multi-Queue Multi-Server(MQMS)systems.The traffic flow is usually burst and channels are usually time-varying.Hence,we study MQMS systems with a random arrival process and time-varying server rate in this thesis.We have designed a channel assignment technique and the scheduling for joint flow control and channel allocation technique to increase the user perceive throughput while ensure the stability of queues.In addition,we also study the stability region characterization of MQMS systems.Finally,for LTE system,we have designed a scheduling priority function in order to improve the user perceive throughput with the guarantee of fairness among users.The main contributions of this dissertation are stated as follows.Firstly,The communication process with a random arrival can be modeled a MQMS system.We propose a novel scheduling scheme to improve the Quality of Experience(Qo E).The Qo E is evaluated by a novel indicator named System User-Perceived Throughput(SUPT).According to the property of the traffic,the stochastic optimization problem for SUPT can be transformed into utility maximization under the constraint of queue stability.We propose a drift-plus-penalty scheduling algorithm by modifying max weight.A Nike function for queue length replaces the queue length as the weight,and the proposed scheduling algorithm achieve a balance between delay and utility.Furthermore,we prove the stability of the queues based on the Foster-Lyapunov theorem and analyze the delay boundary under proposed scheduling algorithm.Compared with several classical scheduling policies,the effectiveness of the proposed is verified in three different scenarios.The simulation results show proposed policy achieves more efficient trade-off between SUPT and system delay,and is capable of maintaining system stability as max weight(MW)regardless of the system load.Secondly,we study the stability regions of the dual-connectivity multi-queue multi-server(DC MQMS)system and fluid model MQMS.First,we derive the stability region of the MQMS systems by a finite set of inequalities.The stability region indicates the characterization of the maximal input rate vectors supported by the system,which is useful for network management.Considering several numerical examples,we study the DC MQMS and fluid model MQMS.The results show the stability regions are related to the system scale such as the number of servers,the number of queues and the average server rate.Moreover,the characterization of the stability region is demonstrated under an ON/OFF channel model.Thirdly,we design a cross-layer scheduling algorithm for joint flow control and resource allocation to optimize the time-average utility function for a DC MQMS system.We consider two cases,i.e.,the input rate belongs to the stability region and the input rate exceeds the stability region.Two scheduling algorithms for joint flow control and resource allocation are proposed using the Lyapunov drift and optimization method,and the performance on the utility function and queue delay is analyzed.Compared with the Maximum Weight(MW)and Round Robin(RR)scheduling policies,the proposed algorithm improves SUPT greatly while maintain the throughput nondecreasing in first case,and compared with Leaky Bucket(LB)the proposed algorithm decreases the system delay greatly while maintain the system throughput and fairness-throughput in second case.Finally,we design a scheduling algorithm based on scheduling priority for LTE system to improve the overall system Qo E.A new scheduling algorithm named Percent Proportional Fair(PPF)is proposed for the reality burst traffic.To evaluate the user experience,we introduce two measure indicators,average User Perceived Throughput(UPT)and User Perceived Throughput-cut(UPT-cut).In order to improve the average UPT with fairness guarantee,we design the scheduling priority by considering the ratio of the amount of transmitted data to the total amount of burst data.At the same time,an allocation matrix is introduced so as to avoid bandwidth waste.We build the wireless communication scenario based on LTE,comparing the PPF scheduler with the classical Proportional Fair(PF)scheduler and Fair Allocation High Throughput(FAHT)scheduler,and the simulation results show the improvement of average UPT while ensuring fairness among the users.Besides,the performance of PPF scheduling is analyzed in various system scenarios.