林永松臺灣大學：資訊管理學研究所曾勇誠Tzeng, Yeong-ChengYeong-ChengTzeng2007-11-262018-06-292007-11-262018-06-292006http://ntur.lib.ntu.edu.tw//handle/246246/54311無線網狀網路(WMN)是另一項可實現寬頻存取網際網路的「最後一哩(last mile)」技術。為了能在無線網狀網路中，提供多媒體應用服務，例如：視訊會議、網路電話(VoIP)，服務品質 (QoS)的保證將是至關重要的目標。這是因為多媒體應用對於延遲及延遲變異非常的敏感。如果能良好規劃網路及理想地部署網際網路閘道，每個行動用戶將可以享受到服務品質保證的多媒體應用服務。 在本研究中，我們針對網路服務提供者，在如何佈署出口閘道設施，及在滿足服務品質下如何安排路徑、分配頻寬等決策，提供一個解答。為了解決此問題，我們針對服務品質保證需求，包括端到端的平均延遲需求，以及端對端的延遲變異需求，提出一個數學模型。此演算法的基本方法為拉格蘭氏鬆弛法（Lagrangean Relaxation）及次梯度法（subgradient）。Wireless mesh networks (WMNs) are an alternative technology for last-mile broadband Internet access. To enable multimedia applications such as video-conferencing and voice over IP (VoIP) in WMNs, the guarantees of Quality-of-Service (QoS) are very essential. This is because multimedia applications are very sensitive to delay and delay jitter. If the network is well designed and Internet gateways are optimally deployed, each mobile host can enjoy QoS-guaranteed multimedia applications. In this thesis, we propose the solution to the network service providers’ decisions on how many backhauls they should deploy and how they assign the paths and bandwidth for each mobile host with QoS guaranteed. To solve the problem, a mathematical model is proposed which focuses on generic QoS requirements, including end-to-end mean delay requirement and end-to-end delay jitter requirement for each mobile host. The basic approach to the algorithm is Lagrangean Relaxation and the subgradient method.謝 詞 I 論文摘要 III THESIS ABSTRACT V List of Tables IX List of Figures XI Chapter 1 Introduction 1 1.1 Background 1 1.2 Motivation 3 1.3 Literature Survey 4 1.3.1 Wireless Mesh Networks 4 1.3.2 End-to-end Performance 5 1.4 Proposed Approach 7 1.5 Thesis Organization 7 Chapter 2 Problem Formulation 9 2.1 Problem Description 9 2.2 Notation 12 2.3 Problem Formulation 15 Chapter 3 Solution Approach 21 3.1 Introduction to the Lagrangean Relaxation Method 21 3.2 Lagrangean Relaxation 24 3.2.1 Subproblem 1 (related to decision variable ηbk) 27 3.2.2 Subproblem 2 (related to decision variable zbs) 28 3.2.3 Subproblem 3 (related to decision variable xp) 29 3.2.4 Subproblem 4 (related to decision variable as) 30 3.2.5 Subproblem 5 (related to decision variable γsuv) 31 3.2.6 Subproblem 6 (related to decision variable ysuv and fuv) 32 3.2.7 Subproblem 7 (related to decision variable κns) 34 3.3 The Dual Problem and the Subgradient Method 35 Chapter 4 Getting Primal Feasible Solution 37 4.1 Lagrangean Relaxation Results 37 4.2 Getting Primal Heuristic 37 4.2.1 Assign Mobile Host Heuristic 38 4.2.2 Routing Heuristic 39 4.2.3 Add Backhaul Heuristic 40 Chapter 5 Computational Experiments 43 5.1 Experiment Environment 43 5.2 Simple Algorithms and Metrics 43 5.3 Experiment Scenarios 44 5.4 Grid Network with Different Number of TAPs 45 5.5 Random Network with Different Number of TAPs 46 5.6 Hexgonal Network with Different Number of TAPs 47 5.7 Random Network with Different Data Flow 48 5.8 Experiment Discussion 49 Chapter 6 Conclusion 51 6.1 Summary 51 6.2 Future Work 51 References 53953838 bytesapplication/pdfen-US無線網狀網路出口閘道設施指定考量服務品質之路由規劃最佳化拉格蘭日鬆弛法Wireless Mesh NetworkBackhaul AssignmentQoS Constrained Routing AssignmentOptimizationLagrangean Relaxation Methodotherhttp://ntur.lib.ntu.edu.tw/bitstream/246246/54311/1/ntu-95-R93725047-1.pdf