請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/31346完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 林永松 | |
| dc.contributor.author | Yeong-Cheng Tzeng | en |
| dc.contributor.author | 曾勇誠 | zh_TW |
| dc.date.accessioned | 2021-06-13T02:44:28Z | - |
| dc.date.issued | 2006 | |
| dc.date.submitted | 2006-10-26 | |
| dc.identifier.citation | [1] B. Li. “End-to End Fair Bandwidth Allocation in Multi-hop Wireless Ad Hoc Networks”, Proc. IEEE ICDCS 2005, Columbia, OH, June 2005.
[2] H. H. Yen and F. Y. S. Lin, “Near-Optimal Delay Constrained Routing in Virtual Circuit Networks”, Proc. IEEE Infocom 2001, Anchorage, Alaska USA , April 2001. [3] I. F. Akyildiz, X. Wang, and W. Wang, “Wireless Mesh Networks: A Survey”, Elsevier Computer Networks, vol. 47, no. 4, pp. 445–487, March 2005. [4] J. Jun and M. Sichitiu, “The Nominal Capacity of Wireless Mesh Networks”, IEEE Wireless Communications, vol. 10, no. 5, pp. 8-14, October 2003. [5] J. Padhye, R. Draves, and B. Zill, “Routing in Multi-Radio, Multi-Hop Wireless Mesh Networks”, Proc. ACM MOBICOM 2004, Philadelphia, PA, September 2004. [6] K. T. Cheng and F. Y. S. Lin, “Minimax End-to-end Delay Routing and Capacity Assignment for Virtual Circuit Networks”, Proc. IEEE Globecom, pp. 2134-2138, 1995. [7] M. Fisher, “Optimal Solution of Scheduling Problems Using Lagrange Multipliers: Part I.”, Operations Res., vol. 21, pp. 1114-1128, 1973. [8] M. Fisher, “The Lagrangean Relaxation Method for Solving Integer Programming Problems”, Management Science, vol. 27, pp. 1-18, 1981. [9] N. B. Salem and J. P. Hubaux, “A Fair Scheduling for Wireless Mesh Networks”, Proc. IEEE WiMesh 2005, Santa Clara, CA, September 2005. [10] P. De, A. Raniwala, S. Sharma, and T.C. Chiueh, “Design Considerations for a Multihop Wireless Network Testbed”, IEEE Communications Magazine, vol. 43, no. 10, pp. 102-109, October 2005. [11] R. Bruno, M. Conti, and E. Gregori, “Mesh Networks: Commodity Multihop Ad Hoc Networks”, IEEE Communications Magazine, vol. 43, no. 3, pp. 123–131, March 2005. [12] R. Karrer, A. Sabharwal, and E. Knightly, “Enabling Large-scale Wireless Broadband: The Case for TAPs”, Proc. ACM HotNets-II, Cambridge, MA, November 2003. [13] S. T. Sheu and J. H. Chen, “MR2RP: The Multi-Rate and Multi-Range Routing Protocol for Ad Hoc Wireless Networks”, Proc. IEEE ISCC 2002, Italy, July 2002. [14] T. J. Tsai and J. W. Chen, “IEEE 802.11 MAC Protocol over Wireless Mesh Networks: Problems and Perspectives”, Proc. IEEE AINA 2005, Taiwan, R.O.C., March 2005. [15] V. Gambiroza, B. Sadeghi, and E. Knightly, “End-to-End Performance and Fairness in Multihop Wireless Backhaul Networks”, Proc. ACM MOBICOM 2004, Philadelphia, PA, September 2004. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/31346 | - |
| dc.description.abstract | 無線網狀網路(WMN)是另一項可實現寬頻存取網際網路的「最後一哩(last mile)」技術。為了能在無線網狀網路中，提供多媒體應用服務，例如：視訊會議、網路電話(VoIP)，服務品質 (QoS)的保證將是至關重要的目標。這是因為多媒體應用對於延遲及延遲變異非常的敏感。如果能良好規劃網路及理想地部署網際網路閘道，每個行動用戶將可以享受到服務品質保證的多媒體應用服務。
在本研究中，我們針對網路服務提供者，在如何佈署出口閘道設施，及在滿足服務品質下如何安排路徑、分配頻寬等決策，提供一個解答。為了解決此問題，我們針對服務品質保證需求，包括端到端的平均延遲需求，以及端對端的延遲變異需求，提出一個數學模型。此演算法的基本方法為拉格蘭氏鬆弛法（Lagrangean Relaxation）及次梯度法（subgradient）。 | zh_TW |
| dc.description.abstract | 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. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-13T02:44:28Z (GMT). No. of bitstreams: 1 ntu-95-R93725047-1.pdf: 953838 bytes, checksum: bd8fd10cae9f87ddd80ab1dd8097ddbb (MD5) Previous issue date: 2006 | en |
| dc.description.tableofcontents | 謝 詞 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 53 | |
| dc.language.iso | en | |
| dc.subject | 出口閘道設施指定 | zh_TW |
| dc.subject | 無線網狀網路 | zh_TW |
| dc.subject | 考量服務品質之路由規劃 | zh_TW |
| dc.subject | 最佳化 | zh_TW |
| dc.subject | 拉格蘭日鬆弛法 | zh_TW |
| dc.subject | Backhaul Assignment | en |
| dc.subject | QoS Constrained Routing Assignment | en |
| dc.subject | Lagrangean Relaxation Method | en |
| dc.subject | Optimization | en |
| dc.subject | Wireless Mesh Network | en |
| dc.title | 無線網狀網路下考量端對端服務品質之 出口閘道設施指定及路由演算法 | zh_TW |
| dc.title | Backhaul Assignment and Routing Algorithms with End-to-End QoS Constraints in Wireless Mesh Networks | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 95-1 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 呂俊賢,陳郁堂 | |
| dc.subject.keyword | 無線網狀網路,出口閘道設施指定,考量服務品質之路由規劃,最佳化,拉格蘭日鬆弛法, | zh_TW |
| dc.subject.keyword | Wireless Mesh Network,Backhaul Assignment,QoS Constrained Routing Assignment,Optimization,Lagrangean Relaxation Method, | en |
| dc.relation.page | 56 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2006-10-30 | |
| dc.contributor.author-college | 管理學院 | zh_TW |
| dc.contributor.author-dept | 資訊管理學研究所 | zh_TW |
| 顯示於系所單位： | 資訊管理學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-95-1.pdf 未授權公開取用 | 931.48 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。