陳光禎臺灣大學：電信工程學研究所李宇軒Li, Yu-ShiuanYu-ShiuanLi2007-11-272018-07-052007-11-272018-07-052005http://ntur.lib.ntu.edu.tw//handle/246246/58641我們藉著研究在有線網路中具「最佳延遲」(delay-optimal)特性的最早截止時間優先(Earliest Deadline First)排程政策，來把握能保證有限延遲的充份條件的本質。透過這個研究及決定式服務品質保證(deterministic QoS guarantee)理論架構激發的靈感，提出用以描述無線通道狀態變化的特徵。藉著檢視幾個重要排程案例，發現只依照截止時間設計資訊的排程政策不適用於無線網路，尤其是在通道被嚴重干擾的狀況中。我們討論了幾個可能改善的途徑，並利用PGPS (Packet by Packet Generalized Processor Sharing)的設計觀念及在最早截止時間優先排程政策下保證有限延遲的充份條件提出新的排程政策。我們推導出可達到的延遲上限及可排程區域的部份結果，但所找出的最糟案例說明描述無線通道的特徵需要加以改進，使可達到的延遲上限能更好。In this thesis, we capture what sufficient condition is essential to guarantee bounded delay by investigating Earliest Deadline First (EDF) scheme, which is delay-optimal in wireline system. By the inspiration of the investigation and theoretical architecture of deterministic QoS guarantee, a characterization of wireless channel variation is proposed. By examining several critical scenarios under such characterization, we conclude that scheduling scheme based on only deadline emergency is not appropriate in wireless channel, especially when the channel is interfered severely. Some possible improving approaches are discussed. We propose new scheduling schemes based on the concept of design of PGPS and the sufficient condition of EDF. Partial results of achievable delay bound and scheduling region is derived. Nevertheless, the worst case and its approximation illustrate that the characterization of wireless channel should be improved such that the delay bound can be better.摘要 i 誌謝 iii Abstract v Chapter 1 Introduction 1 Chapter 2 Preliminary Results and Architecture model 5 2.1 Modeling and Basic Assumptions of Wireline network 6 2.2 Minimum Sufficient Bandwidth under EDF Scheme 8 2.3 Assumptions of Wireless Network and Cs(t)-constraint 14 Chapter 3 Design Principles of Scheduling Scheme in the presence of Interference 17 3.1 Critical Scenarios under Scheduling Schemes based on Deadline Emergency 17 3.2 Design Principles of Scheduling Scheme robust to Interference 22 3.2.1 Summary on Critical Scenarios 22 3.2.2 Suggested Design Principles 24 3.2.3 Our Approach in Designing a new Scheme 25 Chapter 4 Proposed Algorithm and Its Performance Analysis 29 4.1 Algorithm for always Backlogged Sessions and its Performance Analysis 30 4.1.1 Problem Simplification and our Proposed Scheme 30 4.1.2 Bandwidth Curve Analysis of the case n=2 31 4.1.3 Bandwidth Curve Analysis of the case n>2 37 4.1.4 Evaluation of Achievable Delay Bound in the Simplified Problem 41 4.2 Algorithm for General Cases and Part of Performance Analysis 44 4.3 Simulation Results 53 Chapter 5 Conclusions 57 Bibliography 611132111 bytesapplication/pdfen-US服務品質排程無線網路Quality of Serviceschedulingwireless networkthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/58641/1/ntu-94-R92942030-1.pdf